17 #include <initializer_list>
22 #ifndef _PASL_DATA_CHUNKEDSEQBASE_H_
23 #define _PASL_DATA_CHUNKEDSEQBASE_H_
57 class Iterator=iterator::random_access
126 chunk_type front_inner, back_inner, front_outer, back_outer;
127 std::unique_ptr<middle_type> middle;
144 template <
class Pred>
148 return src.split(chunk_meas, p, chunk_search, middle_meas, prefix, x, dst);
154 return c == &front_outer || c == &front_inner
155 || c == &back_inner || c == &back_outer;
160 void restore_front_outer_empty_other_empty() {
161 if (front_outer.empty()) {
162 if (! front_inner.empty()) {
163 front_inner.swap(front_outer);
164 }
else if (! middle->empty()) {
166 front_outer.swap(*c);
168 }
else if (! back_inner.empty()) {
169 back_inner.swap(front_outer);
172 assert(! front_outer.empty()
173 || (front_inner.empty() && middle->empty() && back_inner.empty()) );
176 void restore_back_outer_empty_other_empty() {
177 if (back_outer.empty()) {
178 if (! back_inner.empty()) {
179 back_inner.swap(back_outer);
180 }
else if (! middle->empty()) {
184 }
else if (! front_inner.empty()) {
185 front_inner.swap(back_outer);
188 assert(! back_outer.empty()
189 || (back_inner.empty() && middle->empty() && front_inner.empty()) );
193 void ensure_front_outer_nonempty() {
194 restore_front_outer_empty_other_empty();
195 if (front_outer.empty() && ! back_outer.empty())
196 front_outer.swap(back_outer);
197 assert(
empty() || ! front_outer.empty());
200 void ensure_back_outer_nonempty() {
201 restore_back_outer_empty_other_empty();
202 if (back_outer.empty() && ! front_outer.empty())
203 back_outer.swap(front_outer);
204 assert(
empty() || ! back_outer.empty());
209 void restore_both_outer_empty_middle_empty() {
210 if (front_outer.empty() && back_outer.empty() && ! middle->empty()) {
213 front_outer.swap(*c);
219 void ensure_empty_inner() {
220 if (! front_inner.empty())
221 push_buffer_front_force(front_inner);
222 if (! back_inner.empty())
223 push_buffer_back_force(back_inner);
226 using const_chunk_pointer =
const chunk_type*;
228 const_chunk_pointer get_chunk_containing_last_item()
const {
229 if (! back_outer.empty())
231 if (! back_inner.empty())
233 if (! middle->empty())
235 return middle->back();
237 return middle->cback();
239 if (! front_inner.empty())
244 using position_type =
enum {
253 template <
class Pred>
255 position_type& pos)
const {
257 if (! front_outer.empty()) {
259 cur = middle_algebra_type::combine(cur, middle_meas(&front_outer));
261 pos = found_front_outer;
265 if (! front_inner.empty()) {
267 cur = middle_algebra_type::combine(cur, middle_meas(&front_inner));
269 pos = found_front_inner;
273 if (! middle->empty()) {
275 cur = middle_algebra_type::combine(cur, middle->get_cached());
281 if (! back_inner.empty()) {
283 cur = middle_algebra_type::combine(cur, middle_meas(&back_inner));
285 pos = found_back_inner;
289 if (! back_outer.empty()) {
291 cur = middle_algebra_type::combine(cur, middle_meas(&back_outer));
293 pos = found_back_outer;
310 template <
class Pred>
312 bool& found, const_chunk_pointer& cur)
const {
314 prefix = search(p, prefix, pos);
317 case found_front_outer: {
321 case found_front_inner: {
326 #ifdef DEBUG_MIDDLE_SEQUENCE
329 prefix = middle->search_for_chunk(p, prefix, cur);
333 case found_back_inner: {
337 case found_back_outer: {
341 case found_nowhere: {
351 template <
class Pred>
353 assert(other.empty());
355 ensure_empty_inner();
357 prefix = search(p, prefix, pos);
359 case found_front_outer: {
360 prefix = chunk_split(p, prefix, front_outer, x, other.front_outer);
361 middle.swap(other.middle);
362 back_outer.swap(other.back_outer);
365 case found_front_inner: {
370 back_outer.swap(other.back_outer);
372 prefix = middle->split(middle_meas, p, prefix, c, *other.middle);
375 prefix = chunk_split(p, prefix, back_outer, x, other.front_outer);
378 case found_back_inner: {
382 case found_back_outer: {
383 prefix = chunk_split(p, prefix, back_outer, x, other.back_outer);
386 case found_nowhere: {
391 restore_both_outer_empty_middle_empty();
392 other.restore_both_outer_empty_middle_empty();
397 template <
class Pred>
401 prefix = split_aux(p, prefix, x, other);
402 if (size_access::csize(prefix) < sz_orig)
414 middle->push_back(middle_meas, d);
421 middle->push_front(middle_meas, d);
427 size_t csize = c.size();
430 }
else if (middle->empty()) {
431 push_buffer_back_force(c);
434 size_t bsize = b->size();
435 if (bsize + csize > chunk_capacity) {
436 push_buffer_back_force(c);
438 middle->pop_back(middle_meas);
439 c.transfer_from_front_to_back(chunk_meas, *b, csize);
440 middle->push_back(middle_meas, b);
447 size_t csize = c.size();
450 }
else if (middle->empty()) {
451 push_buffer_front_force(c);
454 size_t bsize = b->size();
455 if (bsize + csize > chunk_capacity) {
456 push_buffer_front_force(c);
458 middle->pop_front(middle_meas);
459 c.transfer_from_back_to_front(chunk_meas, *b, csize);
460 middle->push_front(middle_meas, b);
504 std::vector<value_type> vals(chunk_capacity, val);
507 return std::make_pair(p, p + nb);
525 : front_outer(other.front_outer),
526 front_inner(other.front_inner),
527 back_inner(other.back_inner),
528 back_outer(other.back_outer),
529 chunk_meas(other.chunk_meas),
530 middle_meas(other.middle_meas) {
538 for (
auto it = l.begin(); it != l.end(); it++)
558 return front_outer.empty() && back_outer.empty();
573 sz += front_outer.size();
574 sz += front_inner.size();
575 sz += size_access::csize(middle->get_cached());
576 sz += back_inner.size();
577 sz += back_outer.size();
605 assert(! front_outer.empty() || front_inner.empty());
607 if (! front_outer.empty()) {
608 return front_outer.front();
609 }
else if (! back_inner.empty()) {
610 return back_inner.front();
612 assert(! back_outer.empty());
613 return back_outer.front();
633 assert(! back_outer.empty() || back_inner.empty());
634 if (! back_outer.empty()) {
635 return back_outer.back();
636 }
else if (! front_inner.empty()) {
637 return front_inner.back();
639 assert(! front_outer.empty());
640 return front_outer.back();
697 template <
class Consumer>
721 template <
class Consumer>
746 auto it =
begin() + n;
747 assert(it.size() == n + 1);
771 auto it =
begin() + n;
772 assert(it.size() == n + 1);
796 if (front_outer.full()) {
797 if (front_inner.full())
798 push_buffer_front_force(front_inner);
799 front_outer.swap(front_inner);
800 assert(front_outer.empty());
802 front_outer.push_front(chunk_meas, x);
819 if (back_outer.full()) {
820 if (back_inner.full())
821 push_buffer_back_force(back_inner);
822 back_outer.swap(back_inner);
823 assert(back_outer.empty());
825 back_outer.push_back(chunk_meas, x);
847 if (front_outer.empty()) {
848 assert(front_inner.empty());
849 if (! middle->empty()) {
851 front_outer.swap(*c);
853 }
else if (! back_inner.empty()) {
854 back_inner.swap(front_outer);
855 }
else if (! back_outer.empty()) {
856 back_outer.swap(front_outer);
859 assert(! front_outer.empty());
860 value_type x = front_outer.pop_front(chunk_meas);
861 restore_front_outer_empty_other_empty();
883 if (back_outer.empty()) {
884 assert(back_inner.empty());
885 if (! middle->empty()) {
889 }
else if (! front_inner.empty()) {
890 front_inner.swap(back_outer);
891 }
else if (! front_outer.empty()) {
892 front_outer.swap(back_outer);
895 assert(! back_outer.empty());
896 value_type x = back_outer.pop_back(chunk_meas);
897 restore_back_outer_empty_other_empty();
955 stream_popn_front<typeof(c), false>(c, nb);
978 stream_popn_back<typeof(c), false>(c, nb);
1048 template <
class Producer>
1053 ensure_empty_inner();
1060 m = std::min(m, cap - c.size());
1061 std::pair<const_pointer,const_pointer> rng = prod(i, m);
1065 c.pushn_back(chunk_meas, lo, nb);
1066 push_buffer_back(c);
1069 restore_back_outer_empty_other_empty();
1070 assert(sz_orig + nb ==
size());
1094 template <
class Producer>
1099 ensure_empty_inner();
1101 c.swap(front_outer);
1106 m = std::min(m, cap - c.size());
1108 std::pair<const_pointer,const_pointer> rng = prod(n, m);
1112 c.pushn_front(chunk_meas, lo, nb);
1113 push_buffer_front(c);
1115 restore_front_outer_empty_other_empty();
1116 assert(sz_orig + nb ==
size());
1143 template <
class Consumer,
bool should_consume=true>
1146 assert(sz_orig >= nb);
1149 ensure_back_outer_nonempty();
1150 size_type m = std::min(back_outer.size(), nb - i);
1151 back_outer.template popn_back<Consumer,should_consume>(chunk_meas, cons, m);
1154 ensure_back_outer_nonempty();
1155 assert(sz_orig ==
size() + nb);
1182 template <
class Consumer,
bool should_consume=true>
1185 assert(sz_orig >= nb);
1188 ensure_front_outer_nonempty();
1189 size_type m = std::min(front_outer.size(), nb - i);
1190 front_outer.template popn_front<Consumer,should_consume>(chunk_meas, cons, m);
1193 ensure_front_outer_nonempty();
1194 assert(sz_orig ==
size() + nb);
1213 if (other.
size() == 0)
1218 push_buffer_back(back_inner);
1219 push_buffer_back(back_outer);
1220 other.push_buffer_front(other.front_inner);
1221 other.push_buffer_front(other.front_outer);
1223 if (! middle->empty() && ! other.middle->empty()) {
1228 if (nb1 + nb2 <= chunk_capacity) {
1229 middle->pop_back(middle_meas);
1230 other.middle->pop_front(middle_meas);
1231 c2->transfer_from_front_to_back(chunk_meas, *c1, nb2);
1233 middle->push_back(middle_meas, c1);
1238 back_inner.swap(other.back_inner);
1239 back_outer.swap(other.back_outer);
1241 middle->concat(middle_meas, *other.middle);
1243 restore_both_outer_empty_middle_empty();
1244 assert(other.
empty());
1248 template <
class Pred>
1252 return p(size_access::cclient(m));
1254 middle_measured_type prefix = split_aux(q, middle_algebra_type::identity(), middle_item, other);
1255 bool found = (size_access::csize(prefix) < sz_orig);
1260 template <
class Pred>
1263 bool found =
split(p, middle_item, other);
1391 std::swap(chunk_meas, other.chunk_meas);
1392 std::swap(middle_meas, other.middle_meas);
1393 front_outer.swap(other.front_outer);
1394 front_inner.swap(other.front_inner);
1395 middle.swap(other.middle);
1396 back_inner.swap(other.back_inner);
1397 back_outer.swap(other.back_outer);
1429 return iterator(
this, middle_meas, chunkedseq::iterator::begin);
1458 return iterator(
this, middle_meas, chunkedseq::iterator::end);
1474 template <
class Body>
1476 front_outer.for_each(f);
1477 front_inner.for_each(f);
1481 back_inner.for_each(f);
1482 back_outer.for_each(f);
1502 template <
class Body>
1522 template <
class Body>
1524 front_outer.for_each_segment(f);
1525 front_inner.for_each_segment(f);
1527 p->for_each_segment(f);
1529 back_inner.for_each_segment(f);
1530 back_outer.for_each_segment(f);
1551 template <
class Body>
1572 m = algebra_type::combine(m, front_outer.get_cached());
1573 m = algebra_type::combine(m, front_inner.get_cached());
1574 measured_type n = size_access::cclient(middle->get_cached());
1575 m = algebra_type::combine(m, n);
1576 m = algebra_type::combine(m, back_inner.get_cached());
1577 m = algebra_type::combine(m, back_outer.get_cached());
1601 middle_meas.set_client_measure(meas);
1621 template <
class ItemPr
inter>
1625 ItemPrinter::print(x);
1634 template <
class ItemPr
inter,
class CachePr
inter = DummyCachePr
inter>
1637 print_chunk<ItemPrinter>(c); };
1658 size_type msz = size_access::csize(middle->get_cached());
1671 if (front_outer.empty())
1672 assert(front_inner.empty());
1673 if (back_outer.empty())
1674 assert(back_inner.empty());
1675 if (front_outer.empty() && back_outer.empty())
1676 assert(middle->empty());
1679 size_t scur = c->size();
1682 assert(sprev + scur > chunk_capacity);
1689 template <
class Add_edge,
class Process_chunk>
1691 const Process_chunk& process_chunk)
const {
1692 long rootptr = (long)
this;
1694 add_edge((
void*)rootptr, (
void*)&front_outer);
1695 add_edge((
void*)rootptr, (
void*)&front_inner);
1696 add_edge((
void*)rootptr, (
void*)middle.get());
1697 add_edge((
void*)rootptr, (
void*)&back_inner);
1698 add_edge((
void*)rootptr, (
void*)&back_outer);
1699 process_chunk(&front_outer);
1700 process_chunk(&front_inner);
1701 middle->reveal_internal_structure(add_edge, process_chunk);
1702 process_chunk(&back_inner);
1703 process_chunk(&back_outer);
static void for_each_segment(iterator begin, iterator end, const Body &f)
Visits every segment of items in a specified range.
chunkedseqbase()
Empty container constructor.
const value_type * const_pointer
void stream_pushn_back(const Producer &prod, size_type nb)
Adds items at the end.
iterator erase(iterator first, iterator last)
Erases items.
void split(iterator position, self_type &other)
Split by iterator.
void push_front(const value_type &x)
Adds item at the beginning.
#define DEBUG_MIDDLE_SEQUENCE
void reveal_internal_structure(const Add_edge &add_edge, const Process_chunk &process_chunk) const
iterator begin() const
Returns iterator to beginning.
void stream_pushn_front(const Producer &prod, size_type nb)
Adds items at the beginning.
typename value_type::middle_type middle_type
void popn_back(size_type nb)
Deletes last items.
void set_measure(measure_type meas)
Sets measurement operator.
void concat(self_type &other)
Merges with content of another container.
typename chunk_cache_type::measured_type chunk_measured_type
typename config_type::item_allocator_type allocator_type
chunk_type * chunk_pointer
typename config_type::size_type size_type
value_type front() const
Accesses last item.
typename config_type::value_type value_type
typename value_type::chunk_search_type chunk_search_type
void push_back(const value_type &x)
Adds item at the end.
void copy_measure_to(self_type &other)
Copies the measurement operator.
typename value_type::middle_cache_type middle_cache_type
size_type size() const
Returns size.
typename middle_cache_type::measured_type middle_measured_type
void stream_frontn(const Consumer &cons, size_type nb) const
Consume first items.
void popn_back(value_type *dst, size_type nb)
Deletes first items.
typename config_type::difference_type difference_type
void stream_popn_front(const Consumer &cons, size_type nb)
Deletes first items.
void stream_backn(const Consumer &cons, size_type nb) const
Consume last items.
value_type operator[](size_type n) const
Access item.
value_type pop_front()
Deletes first item.
void frontn(value_type *dst, size_type nb) const
Access first items.
typename cache_type::measure_type measure_type
typename cache_type::algebra_type algebra_type
typename chunk_cache_type::algebra_type chunk_algebra_type
typename Configuration::chunk_type chunk_type
chunk_capacity< self_type, config_type > iterator
iterator end() const
Returns iterator to end.
void popn_front(value_type *dst, size_type nb)
Deletes last items.
void popn_front(size_type nb)
Deletes first items.
void split(size_type i, self_type &other)
Split by index.
void for_each(iterator beg, iterator end, const Body &f) const
Visits every item in a specified range.
void for_each(const Body &f) const
Visits every item in the container.
value_type pop_back()
Deletes last item.
void backn(value_type *dst, size_type nb) const
Access last items.
value_type back() const
Accesses first item.
chunkedseqbase(const self_type &other)
Copy constructor.
reference operator[](size_type n)
Access item.
measured_type get_cached() const
Returns cached measurement.
chunkedseqbase(size_type n, const value_type &val)
Fill constructor.
chunkedseqbase< config_type > self_type
void swap(self_type &other)
Swaps content.
chunk_cache_type cache_type
void clear()
Clears items.
void stream_popn_back(const Consumer &cons, size_type nb)
Deletes last items.
void print_chunk(const chunk_type &c) const
void split(const Pred &p, self_type &other)
void pushn_back(const_pointer src, size_type nb)
Adds items at the end.
void for_each_segment(const Body &f) const
Visits every segment of items in the container.
typename value_type::chunk_cache_type chunk_cache_type
void pushn_front(const_pointer src, size_type nb)
Adds items at the beginning.
bool split(const Pred &p, reference middle_item, self_type &other)
typename value_type::size_access size_access
typename chunk_cache_type::measure_type chunk_measure_type
typename cache_type::measured_type measured_type
STL style iterators for our chunked sequences.
iterator insert(iterator position, const value_type &val)
Inserts items.
typename middle_cache_type::measure_type middle_measure_type
const int chunk_capacity
[weighted_split_example]
measure_type get_measure() const
Returns measurement operator.
typename middle_cache_type::algebra_type middle_algebra_type
void split_approximate(self_type &other)
bool empty() const
Test whether the container is empty.
static constexpr int chunk_capacity
chunkedseqbase(std::initializer_list< value_type > l)
const value_type & const_reference
typename config_type::segment_type segment_type