#ifndef ROW_CACHE_H

#define ROW_CACHE_H

#include <vector>

#include <numeric>

#include <algorithm>

#include <stdexcept>

/**

cache structure adapted to the existing access patterns in

SqliteTableModel. handles many large segments with gaps in between

well.

logical structure resembling a std::vector<std::optional<T>>, but

implementation avoids actually allocating space for the non-empty

optionals, and supports (hopefully) more efficient insertion /

deletion.

actually, this is not even a "cache" - once set, elements are never

thrown away to make space for new elements.

TODO introduce maximum segment size?

**/

template <typename T>

class RowCache

{

public:

using value_type = T;

/// constructs an empty cache

explicit RowCache ();

/// \returns number of cached rows

size_t numSet () const;

/// \returns number of segments

size_t numSegments () const;

/// \returns 1 if specified row is loaded, 0 otherwise

size_t count (size_t pos) const;

/// \returns specified row. \throws if not available

const T & at (size_t pos) const;

T & at (size_t pos);

/// assigns value to specified row; may increase numSet() by one

void set (size_t pos, T && value);

/// insert new element; increases numSet() by one

void insert (size_t pos, T && value);

/// delete element; decreases numSet() by one

void erase (size_t pos);

/// reset to state after construction

void clear ();

/// given a range of rows (end is exclusive), narrow it in order

/// to remove already-loaded rows from both ends.

void smallestNonAvailableRange (size_t & row_begin, size_t & row_end) const;

private:

/// a single segment containing contiguous entries

struct Segment

{

size_t pos_begin;

std::vector<T> entries;

/// returns past-the-end position of this segment

size_t pos_end () const { return pos_begin + entries.size(); }

};

/// collection of non-overlapping segments, in order of increasing

/// position

using Segments = std::vector<Segment>;

Segments segments;

// ------------------------------------------------------------------------------

/// \returns first segment that definitely cannot contain 'pos',

/// because it starts at some later position.

typename Segments::const_iterator getSegmentBeyond (size_t pos) const {

// first segment whose pos_begin > pos (so can't contain pos itself):

return std::upper_bound(segments.begin(), segments.end(), pos, pred);

}

typename Segments::iterator getSegmentBeyond (size_t pos) {

return std::upper_bound(segments.begin(), segments.end(), pos, pred);

}

static bool pred (size_t pos, const Segment & s) { return pos < s.pos_begin; }

// ------------------------------------------------------------------------------

/// \returns segment containing 'pos'

typename Segments::const_iterator getSegmentContaining (size_t pos) const

{

auto it = getSegmentBeyond(pos);

if(it != segments.begin()) {

auto prev_it = it - 1;

if(pos < prev_it->pos_end())

return prev_it;

}

return segments.end();

}

};

template <typename T>

RowCache<T>::RowCache ()

{

}

template <typename T>

size_t RowCache<T>::numSet () const

{

return std::accumulate(segments.begin(), segments.end(), size_t(0),

[](size_t r, const Segment & s) { return r + s.entries.size(); });

}

template <typename T>

size_t RowCache<T>::numSegments () const

{

return segments.size();

}

template <typename T>

size_t RowCache<T>::count (size_t pos) const

{

return getSegmentContaining(pos) != segments.end();

}

template <typename T>

const T & RowCache<T>::at (size_t pos) const

{

auto it = getSegmentContaining(pos);

if(it != segments.end())

return it->entries[pos - it->pos_begin];

throw std::out_of_range("no matching segment found");

}

template <typename T>

T & RowCache<T>::at (size_t pos)

{

return const_cast<T&>(static_cast<const RowCache &>(*this).at(pos));

}

template <typename T>

void RowCache<T>::set (size_t pos, T && value)

{

auto it = getSegmentBeyond(pos);

if(it != segments.begin())

{

auto prev_it = it - 1;

auto d = pos - prev_it->pos_begin; // distance from segment start (>=0)

if(d < prev_it->entries.size())

{

// replace value

prev_it->entries[d] = std::move(value);

return;

}

if(d == prev_it->entries.size())

{

// extend existing segment

prev_it->entries.insert(prev_it->entries.end(), std::move(value));

return;

}

}

// make new segment

segments.insert(it, { pos, { std::move(value) } });

}

template <typename T>

void RowCache<T>::insert (size_t pos, T && value)

{

auto it = getSegmentBeyond(pos);

if(it != segments.begin())

{

auto prev_it = it - 1;

auto d = pos - prev_it->pos_begin; // distance from segment start (>=0)

if(d <= prev_it->entries.size())

{

// can extend existing segment

prev_it->entries.insert(prev_it->entries.begin() + d, std::move(value));

goto push;

}

}

// make new segment

it = segments.insert(it, { pos, { std::move(value) } }) + 1;

push:

// push back all later segments

std::for_each(it, segments.end(), [](Segment &s){ s.pos_begin++; });

}

template <typename T>

void RowCache<T>::erase (size_t pos)

{

auto it = getSegmentBeyond(pos);

// if previous segment actually contains pos, shorten it

if(it != segments.begin())

{

auto prev_it = it - 1;

auto d = pos - prev_it->pos_begin; // distance from segment start (>=0)

if(d < prev_it->entries.size())

{

prev_it->entries.erase(prev_it->entries.begin() + d);

if(prev_it->entries.empty())

{

it = segments.erase(prev_it);

}

}

}

// pull forward all later segments

std::for_each(it, segments.end(), [](Segment &s){ s.pos_begin--; });

}

template <typename T>

void RowCache<T>::clear ()

{

segments.clear();

}

template <typename T>

void RowCache<T>::smallestNonAvailableRange (size_t & row_begin, size_t & row_end) const

{

if(row_end < row_begin)

throw std::invalid_argument("end must be >= begin");

while(row_begin < row_end) {

auto it = getSegmentContaining(row_begin);

if(it == segments.end())

break;

row_begin = it->pos_end();

}

while(row_end > row_begin) {

auto it = getSegmentContaining(row_end - 1);

if(it == segments.end())

break;

row_end = it->pos_begin;

}

if(row_end < row_begin)

row_end = row_begin;

}

#endif // SEGMENTING_CACHE_H