chunkedseq
container library for large in-memory data sets
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
chunkedseqbase.hpp
Go to the documentation of this file.
1 
13 #include <assert.h>
14 #include <iostream>
15 #include <utility>
16 #include <vector>
17 #include <initializer_list>
18 
19 #include "iterator.hpp"
20 #include "chunkedseqextras.hpp"
21 
22 #ifndef _PASL_DATA_CHUNKEDSEQBASE_H_
23 #define _PASL_DATA_CHUNKEDSEQBASE_H_
24 
25 namespace pasl {
26 namespace data {
27 namespace chunkedseq {
28 
29 /***********************************************************************/
30 
51 template <
52  class Configuration,
53  template <
54  class Chunkedseq,
55  class Configuration1
56  >
57  class Iterator=iterator::random_access
58 >
60 protected:
61 
62  using chunk_type = typename Configuration::chunk_type;
63  using chunk_search_type = typename Configuration::chunk_search_type;
64  using chunk_cache_type = typename Configuration::chunk_cache_type;
65  using chunk_measured_type = typename chunk_cache_type::measured_type;
66  using chunk_algebra_type = typename chunk_cache_type::algebra_type;
67  using chunk_measure_type = typename chunk_cache_type::measure_type;
69 
70  using middle_type = typename Configuration::middle_type;
71  using middle_cache_type = typename Configuration::middle_cache_type;
72  using middle_measured_type = typename middle_cache_type::measured_type;
73  using middle_algebra_type = typename middle_cache_type::algebra_type;
74  using middle_measure_type = typename middle_cache_type::measure_type;
75  using size_access = typename Configuration::size_access;
76 
78 
80 
81 public:
82 
83  /*---------------------------------------------------------------------*/
86  using config_type = Configuration;
89  using size_type = typename config_type::size_type;
90  using difference_type = typename config_type::difference_type;
91  using allocator_type = typename config_type::item_allocator_type;
93 
94  /*---------------------------------------------------------------------*/
97  using value_type = typename config_type::value_type;
100  using const_reference = const value_type&;
101  using pointer = value_type*;
102  using const_pointer = const value_type*;
103  using segment_type = typename config_type::segment_type;
105 
106  /*---------------------------------------------------------------------*/
111  using measured_type = typename cache_type::measured_type;
112  using algebra_type = typename cache_type::algebra_type;
113  using measure_type = typename cache_type::measure_type;
115 
116  using iterator = Iterator<self_type, config_type>;
117  friend iterator;
118 
119 private:
120 
121  // representation of the structure: four chunks plus a middle sequence of chunks;
122  // for efficient implementation of emptiness test, additional invariants w.r.t. the paper:
123  // - if front_outer is empty, then front_inner is empty
124  // - if back_outer is empty, then back_inner is empty
125  // - if front_outer and back_outer are empty, then middle is empty
126  chunk_type front_inner, back_inner, front_outer, back_outer;
127  std::unique_ptr<middle_type> middle;
128 
129  chunk_measure_type chunk_meas;
130  middle_measure_type middle_meas;
131 
132  /*---------------------------------------------------------------------*/
133 
134  static inline chunk_pointer chunk_alloc() {
135  return new chunk_type();
136  }
137 
138  // only to free empty chunks
139  static inline void chunk_free(chunk_pointer c) {
140  assert(c->empty());
141  delete c;
142  }
143 
144  template <class Pred>
145  middle_measured_type chunk_split(const Pred& p, middle_measured_type prefix,
146  chunk_type& src, reference x, chunk_type& dst) {
147  chunk_search_type chunk_search;
148  return src.split(chunk_meas, p, chunk_search, middle_meas, prefix, x, dst);
149  }
150 
151  /*---------------------------------------------------------------------*/
152 
153  bool is_buffer(const chunk_type* c) const {
154  return c == &front_outer || c == &front_inner
155  || c == &back_inner || c == &back_outer;
156  }
157 
158  // ensures that if front_outer is empty, then front_inner and middle (and back_inner)
159  // are all empty
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()) {
165  chunk_pointer c = middle->pop_front(middle_meas);
166  front_outer.swap(*c);
167  chunk_free(c);
168  } else if (! back_inner.empty()) {
169  back_inner.swap(front_outer); // optional operation
170  }
171  }
172  assert(! front_outer.empty()
173  || (front_inner.empty() && middle->empty() && back_inner.empty()) );
174  }
175 
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()) {
181  chunk_pointer c = middle->pop_back(middle_meas);
182  back_outer.swap(*c);
183  chunk_free(c);
184  } else if (! front_inner.empty()) {
185  front_inner.swap(back_outer); // optional operation
186  }
187  }
188  assert(! back_outer.empty()
189  || (back_inner.empty() && middle->empty() && front_inner.empty()) );
190  }
191 
192  // ensures that if the container is nonempty, then so is the front-outer buffer
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());
198  }
199 
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());
205  }
206 
207  // assumption: invariant "both outer empty implies middle empty" may be broken;
208  // calling this function restores it.
209  void restore_both_outer_empty_middle_empty() {
210  if (front_outer.empty() && back_outer.empty() && ! middle->empty()) {
211  // pop to the front (to the back would also work)
212  chunk_pointer c = middle->pop_front(middle_meas);
213  front_outer.swap(*c);
214  chunk_free(c);
215  }
216  }
217 
218  // ensures that inner buffers are empty, by pushing them in the middle if full
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);
224  }
225 
226  using const_chunk_pointer = const chunk_type*;
227 
228  const_chunk_pointer get_chunk_containing_last_item() const {
229  if (! back_outer.empty())
230  return &back_outer;
231  if (! back_inner.empty())
232  return &back_inner;
233  if (! middle->empty())
235  return middle->back();
236 #else
237  return middle->cback();
238 #endif
239  if (! front_inner.empty())
240  return &front_inner;
241  return &front_outer;
242  }
243 
244  using position_type = enum {
245  found_front_outer,
246  found_front_inner,
247  found_middle,
248  found_back_inner,
249  found_back_outer,
250  found_nowhere
251  };
252 
253  template <class Pred>
254  middle_measured_type search(const Pred& p, middle_measured_type prefix,
255  position_type& pos) const {
256  middle_measured_type cur = prefix; // prefix including current chunk
257  if (! front_outer.empty()) {
258  prefix = cur;
259  cur = middle_algebra_type::combine(cur, middle_meas(&front_outer));
260  if (p(cur)) {
261  pos = found_front_outer;
262  return prefix;
263  }
264  }
265  if (! front_inner.empty()) {
266  prefix = cur;
267  cur = middle_algebra_type::combine(cur, middle_meas(&front_inner));
268  if (p(cur)) {
269  pos = found_front_inner;
270  return prefix;
271  }
272  }
273  if (! middle->empty()) {
274  prefix = cur;
275  cur = middle_algebra_type::combine(cur, middle->get_cached());
276  if (p(cur)) {
277  pos = found_middle;
278  return prefix;
279  }
280  }
281  if (! back_inner.empty()) {
282  prefix = cur;
283  cur = middle_algebra_type::combine(cur, middle_meas(&back_inner));
284  if (p(cur)) {
285  pos = found_back_inner;
286  return prefix;
287  }
288  }
289  if (! back_outer.empty()) {
290  prefix = cur;
291  cur = middle_algebra_type::combine(cur, middle_meas(&back_outer));
292  if (p(cur)) {
293  pos = found_back_outer;
294  return prefix;
295  }
296  }
297  prefix = cur;
298  pos = found_nowhere;
299  return prefix;
300  }
301 
302  // set "found" to true or false depending on success of the search;
303  // and set "cur" to the chunk that contains the item searched,
304  // or to the chunk containing the last item of the sequence if the item was not found.
305  // if finger search is enabled, then the routine checks whether `cur` contains a
306  // null pointer or a pointer to a chunk; in the latter case, search starts from
307  // the chunk
308  // precondition: `cur` contains either a `nullptr` or a pointer to a "top chunk";
309  // i.e., a leaf node of the middle sequence
310  template <class Pred>
311  middle_measured_type search_for_chunk(const Pred& p, middle_measured_type prefix,
312  bool& found, const_chunk_pointer& cur) const {
313  position_type pos;
314  prefix = search(p, prefix, pos);
315  found = true; // default
316  switch (pos) {
317  case found_front_outer: {
318  cur = &front_outer;
319  break;
320  }
321  case found_front_inner: {
322  cur = &front_inner;
323  break;
324  }
325  case found_middle: {
326 #ifdef DEBUG_MIDDLE_SEQUENCE
327  assert(false);
328 #else
329  prefix = middle->search_for_chunk(p, prefix, cur);
330 #endif
331  break;
332  }
333  case found_back_inner: {
334  cur = &back_inner;
335  break;
336  }
337  case found_back_outer: {
338  cur = &back_outer;
339  break;
340  }
341  case found_nowhere: {
342  cur = &back_outer;
343  found = false;
344  break;
345  }
346  } // end switch
347  return prefix;
348  }
349 
350  // precondition: other is empty
351  template <class Pred>
352  middle_measured_type split_aux(const Pred& p, middle_measured_type prefix, reference x, self_type& other) {
353  assert(other.empty());
354  copy_measure_to(other);
355  ensure_empty_inner();
356  position_type pos;
357  prefix = search(p, prefix, pos);
358  switch (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);
363  break;
364  }
365  case found_front_inner: {
366  assert(false); // thanks to the call to ensure_empty_inner()
367  break;
368  }
369  case found_middle: {
370  back_outer.swap(other.back_outer);
371  chunk_pointer c;
372  prefix = middle->split(middle_meas, p, prefix, c, *other.middle);
373  back_outer.swap(*c);
374  chunk_free(c);
375  prefix = chunk_split(p, prefix, back_outer, x, other.front_outer);
376  break;
377  }
378  case found_back_inner: {
379  assert(false); // thanks to the call to ensure_empty_inner()
380  break;
381  }
382  case found_back_outer: {
383  prefix = chunk_split(p, prefix, back_outer, x, other.back_outer);
384  break;
385  }
386  case found_nowhere: {
387  // don't split (item not found)
388  break;
389  }
390  } // end switch
391  restore_both_outer_empty_middle_empty();
392  other.restore_both_outer_empty_middle_empty();
393  return prefix;
394  }
395 
396  // precondition: other is empty
397  template <class Pred>
398  middle_measured_type split_aux(const Pred& p, middle_measured_type prefix, self_type& other) {
399  size_type sz_orig = size();
400  value_type x;
401  prefix = split_aux(p, prefix, x, other);
402  if (size_access::csize(prefix) < sz_orig)
403  other.push_front(x);
404  return prefix;
405  }
406 
407  /*---------------------------------------------------------------------*/
408 
409  // take a chunk "c" and push its content into the back of the middle sequence
410  // as a new chunk; leaving "c" empty.
411  void push_buffer_back_force(chunk_type& c) {
412  chunk_pointer d = chunk_alloc();
413  c.swap(*d);
414  middle->push_back(middle_meas, d);
415  }
416 
417  // symmetric to push_buffer_back
418  void push_buffer_front_force(chunk_type& c) {
419  chunk_pointer d = chunk_alloc();
420  c.swap(*d);
421  middle->push_front(middle_meas, d);
422  }
423 
424  // take a chunk "c" and concatenate its content into the back of the middle sequence
425  // leaving "c" empty.
426  void push_buffer_back(chunk_type& c) {
427  size_t csize = c.size();
428  if (csize == 0) {
429  // do nothing
430  } else if (middle->empty()) {
431  push_buffer_back_force(c);
432  } else {
433  chunk_pointer b = middle->back();
434  size_t bsize = b->size();
435  if (bsize + csize > chunk_capacity) {
436  push_buffer_back_force(c);
437  } else {
438  middle->pop_back(middle_meas);
439  c.transfer_from_front_to_back(chunk_meas, *b, csize);
440  middle->push_back(middle_meas, b);
441  }
442  }
443  }
444 
445  // symmetric to push_buffer_back
446  void push_buffer_front(chunk_type& c) {
447  size_t csize = c.size();
448  if (csize == 0) {
449  // do nothing
450  } else if (middle->empty()) {
451  push_buffer_front_force(c);
452  } else {
453  chunk_pointer b = middle->front();
454  size_t bsize = b->size();
455  if (bsize + csize > chunk_capacity) {
456  push_buffer_front_force(c);
457  } else {
458  middle->pop_front(middle_meas);
459  c.transfer_from_back_to_front(chunk_meas, *b, csize);
460  middle->push_front(middle_meas, b);
461  }
462  }
463  }
464 
465  void init() {
466  middle.reset(new middle_type());
467  }
468 
469 public:
470 
471  /*---------------------------------------------------------------------*/
474 
486  init();
487  }
488 
503  init();
504  std::vector<value_type> vals(chunk_capacity, val);
505  const value_type* p = vals.data();
506  auto prod = [&] (size_type, size_type nb) {
507  return std::make_pair(p, p + nb);
508  };
509  stream_pushn_back(prod, n);
510  }
511 
524  chunkedseqbase(const self_type& other)
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) {
531  middle.reset(new middle_type(*other.middle));
532  check();
533  }
535 
536  chunkedseqbase(std::initializer_list<value_type> l) {
537  init();
538  for (auto it = l.begin(); it != l.end(); it++)
539  push_back(*it);
540  }
541 
542  /*---------------------------------------------------------------------*/
545 
557  bool empty() const {
558  return front_outer.empty() && back_outer.empty();
559  }
560 
571  size_type size() const {
572  size_type sz = 0;
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();
578  return sz;
579  }
581 
582  /*---------------------------------------------------------------------*/
585 
588 
604  value_type front() const {
605  assert(! front_outer.empty() || front_inner.empty());
606  value_type v;
607  if (! front_outer.empty()) {
608  return front_outer.front();
609  } else if (! back_inner.empty()) {
610  return back_inner.front();
611  } else {
612  assert(! back_outer.empty());
613  return back_outer.front();
614  }
615  }
616 
632  value_type back() const {
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();
638  } else {
639  assert(! front_outer.empty());
640  return front_outer.back();
641  }
642  }
643 
657  void backn(value_type* dst, size_type nb) const {
658  extras::backn(*this, dst, nb);
659  }
660 
674  void frontn(value_type* dst, size_type nb) const {
675  extras::frontn(*this, dst, nb);
676  }
677 
697  template <class Consumer>
698  void stream_backn(const Consumer& cons, size_type nb) const {
699  extras::stream_backn(*this, cons, nb);
700  }
701 
721  template <class Consumer>
722  void stream_frontn(const Consumer& cons, size_type nb) const {
723  extras::stream_frontn(*this, cons, nb);
724  }
725 
744  assert(n >= 0);
745  assert(n < size());
746  auto it = begin() + n;
747  assert(it.size() == n + 1);
748  return *it;
749  }
750 
769  assert(n >= 0);
770  assert(n < size());
771  auto it = begin() + n;
772  assert(it.size() == n + 1);
773  return *it;
774  }
776 
777  /*---------------------------------------------------------------------*/
780 
795  void push_front(const value_type& x) {
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());
801  }
802  front_outer.push_front(chunk_meas, x);
803  }
804 
818  void push_back(const value_type& 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());
824  }
825  back_outer.push_back(chunk_meas, x);
826  }
827 
847  if (front_outer.empty()) {
848  assert(front_inner.empty());
849  if (! middle->empty()) {
850  chunk_pointer c = middle->pop_front(middle_meas);
851  front_outer.swap(*c);
852  chunk_free(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);
857  }
858  }
859  assert(! front_outer.empty());
860  value_type x = front_outer.pop_front(chunk_meas);
861  restore_front_outer_empty_other_empty();
862  return x;
863  }
864 
883  if (back_outer.empty()) {
884  assert(back_inner.empty());
885  if (! middle->empty()) {
886  chunk_pointer c = middle->pop_back(middle_meas);
887  back_outer.swap(*c);
888  chunk_free(c);
889  } else if (! front_inner.empty()) {
890  front_inner.swap(back_outer);
891  } else if (! front_outer.empty()) {
892  front_outer.swap(back_outer);
893  }
894  }
895  assert(! back_outer.empty());
896  value_type x = back_outer.pop_back(chunk_meas);
897  restore_back_outer_empty_other_empty();
898  return x;
899  }
900 
916  extras::pushn_back(*this, src, nb);
917  }
918 
934  extras::pushn_front(*this, src, nb);
935  }
936 
954  auto c = [] (const_pointer, const_pointer) { };
955  stream_popn_front<typeof(c), false>(c, nb);
956  }
957 
976  void popn_back(size_type nb) {
977  auto c = [] (const_pointer, const_pointer) { };
978  stream_popn_back<typeof(c), false>(c, nb);
979  }
980 
1001  void popn_back(value_type* dst, size_type nb) {
1002  extras::popn_back(*this, dst, nb);
1003  }
1004 
1024  extras::popn_front(*this, dst, nb);
1025  }
1026 
1048  template <class Producer>
1049  void stream_pushn_back(const Producer& prod, size_type nb) {
1050  if (nb == 0)
1051  return;
1052  size_type sz_orig = size();
1053  ensure_empty_inner();
1054  chunk_type c;
1055  c.swap(back_outer);
1056  size_type i = 0;
1057  while (i < nb) {
1058  size_type cap = (size_type)chunk_capacity;
1059  size_type m = std::min(cap, nb - i);
1060  m = std::min(m, cap - c.size());
1061  std::pair<const_pointer,const_pointer> rng = prod(i, m);
1062  const_pointer lo = rng.first;
1063  const_pointer hi = rng.second;
1064  size_type nb = hi - lo;
1065  c.pushn_back(chunk_meas, lo, nb);
1066  push_buffer_back(c);
1067  i += m;
1068  }
1069  restore_back_outer_empty_other_empty();
1070  assert(sz_orig + nb == size());
1071  }
1072 
1094  template <class Producer>
1095  void stream_pushn_front(const Producer& prod, size_type nb) {
1096  if (nb == 0)
1097  return;
1098  size_type sz_orig = size();
1099  ensure_empty_inner();
1100  chunk_type c;
1101  c.swap(front_outer);
1102  size_type n = nb;
1103  while (n > 0) {
1104  size_type cap = (size_type)chunk_capacity;
1105  size_type m = std::min(cap, n);
1106  m = std::min(m, cap - c.size());
1107  n -= m;
1108  std::pair<const_pointer,const_pointer> rng = prod(n, m);
1109  const_pointer lo = rng.first;
1110  const_pointer hi = rng.second;
1111  size_type nb = hi - lo;
1112  c.pushn_front(chunk_meas, lo, nb);
1113  push_buffer_front(c);
1114  }
1115  restore_front_outer_empty_other_empty();
1116  assert(sz_orig + nb == size());
1117  }
1118 
1143  template <class Consumer, bool should_consume=true>
1144  void stream_popn_back(const Consumer& cons, size_type nb) {
1145  size_type sz_orig = size();
1146  assert(sz_orig >= nb);
1147  size_type i = 0;
1148  while (i < 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);
1152  i += m;
1153  }
1154  ensure_back_outer_nonempty(); // to restore invariants
1155  assert(sz_orig == size() + nb);
1156  }
1157 
1182  template <class Consumer, bool should_consume=true>
1183  void stream_popn_front(const Consumer& cons, size_type nb) {
1184  size_type sz_orig = size();
1185  assert(sz_orig >= nb);
1186  size_type i = 0;
1187  while (i < 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);
1191  i += m;
1192  }
1193  ensure_front_outer_nonempty(); // to restore invariants
1194  assert(sz_orig == size() + nb);
1195  }
1196 
1212  void concat(self_type& other) {
1213  if (other.size() == 0)
1214  return;
1215  if (size() == 0)
1216  swap(other);
1217  // push buffers into the middle sequences
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);
1222  // fuse front and back, if needed
1223  if (! middle->empty() && ! other.middle->empty()) {
1224  chunk_pointer c1 = middle->back();
1225  chunk_pointer c2 = other.middle->front();
1226  size_type nb1 = c1->size();
1227  size_type nb2 = c2->size();
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);
1232  chunk_free(c2);
1233  middle->push_back(middle_meas, c1);
1234  // note: push might be factorized with earlier operations
1235  }
1236  }
1237  // migrate back chunks of the other and update the weight
1238  back_inner.swap(other.back_inner);
1239  back_outer.swap(other.back_outer);
1240  // concatenate the middle sequences
1241  middle->concat(middle_meas, *other.middle);
1242  // restore invariants
1243  restore_both_outer_empty_middle_empty();
1244  assert(other.empty());
1245  }
1246 
1248  template <class Pred>
1249  bool split(const Pred& p, reference middle_item, self_type& other) {
1250  size_type sz_orig = size();
1251  auto q = [&] (middle_measured_type m) {
1252  return p(size_access::cclient(m));
1253  };
1254  middle_measured_type prefix = split_aux(q, middle_algebra_type::identity(), middle_item, other);
1255  bool found = (size_access::csize(prefix) < sz_orig);
1256  return found;
1257  }
1258 
1260  template <class Pred>
1261  void split(const Pred& p, self_type& other) {
1262  value_type middle_item;
1263  bool found = split(p, middle_item, other);
1264  if (found)
1265  other.push_front(middle_item);
1266  }
1267 
1279  void split(size_type i, self_type& other) {
1280  extras::split_by_index(*this, i, other);
1281  }
1282 
1293  void split(iterator position, self_type& other) {
1294  extras::split_by_iterator(*this, position, other);
1295  }
1296 
1298  extras::split_approximate(*this, other);
1299  }
1300 
1329  iterator insert(iterator position, const value_type& val) {
1330  return extras::insert(*this, position, val);
1331  }
1332 
1353  return extras::erase(*this, first, last);
1354  }
1355 
1366  void clear() {
1367  popn_back(size());
1368  }
1369 
1390  void swap(self_type& 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);
1398  }
1399 
1401 
1402  friend void extras::split_by_index<self_type,size_type>(self_type& c, size_type i, self_type& other);
1403 
1404  /*---------------------------------------------------------------------*/
1407 
1428  iterator begin() const {
1429  return iterator(this, middle_meas, chunkedseq::iterator::begin);
1430  }
1431 
1457  iterator end() const {
1458  return iterator(this, middle_meas, chunkedseq::iterator::end);
1459  }
1460 
1474  template <class Body>
1475  void for_each(const Body& f) const {
1476  front_outer.for_each(f);
1477  front_inner.for_each(f);
1478  middle->for_each([&] (chunk_pointer p) {
1479  p->for_each(f);
1480  });
1481  back_inner.for_each(f);
1482  back_outer.for_each(f);
1483  }
1484 
1502  template <class Body>
1503  void for_each(iterator beg, iterator end, const Body& f) const {
1504  extras::for_each(beg, end, f);
1505  }
1506 
1522  template <class Body>
1523  void for_each_segment(const Body& f) const {
1524  front_outer.for_each_segment(f);
1525  front_inner.for_each_segment(f);
1526  middle->for_each([&] (chunk_pointer p) {
1527  p->for_each_segment(f);
1528  });
1529  back_inner.for_each_segment(f);
1530  back_outer.for_each_segment(f);
1531  }
1532 
1551  template <class Body>
1552  static void for_each_segment(iterator begin, iterator end, const Body& f) {
1553  extras::for_each_segment(begin, end, f);
1554  }
1555 
1557 
1558  /*---------------------------------------------------------------------*/
1561 
1571  measured_type m = algebra_type::identity();
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());
1578  return m;
1579  }
1580 
1589  return chunk_meas;
1590  }
1591 
1600  chunk_meas = meas;
1601  middle_meas.set_client_measure(meas);
1602  }
1603 
1612  other.set_measure(get_measure());
1613  }
1614 
1616  /*---------------------------------------------------------------------*/
1619  // TODO: instead of taking this ItemPrinter argument, we could assume the ItemPrinter to be known from Item type
1621  template <class ItemPrinter>
1622  void print_chunk(const chunk_type& c) const {
1623  printf("(");
1624  c.for_each([&] (value_type& x) {
1625  ItemPrinter::print(x);
1626  printf(" ");
1627  });
1628  printf(")");
1629  }
1630 
1631  // TODO: see whether we want to print cache
1633 
1634  template <class ItemPrinter, class CachePrinter = DummyCachePrinter>
1635  void print() const {
1636  auto show = [&] (const chunk_type& c) {
1637  print_chunk<ItemPrinter>(c); };
1638  show(front_outer);
1639  printf(" ");
1640  show(front_inner);
1641  printf(" [");
1642  middle->for_each([&] (chunk_pointer& c) {
1643  show(*c);
1644  printf(" ");
1645  });
1646  printf("] ");
1647  show(back_inner);
1648  printf(" ");
1649  show(back_outer);
1650  }
1651 
1652  void check_size() const {
1653 #ifndef NDEBUG
1654  size_type sz = 0;
1655  middle->for_each([&] (chunk_pointer& c) {
1656  sz += c->size();
1657  });
1658  size_type msz = size_access::csize(middle->get_cached());
1659  assert(msz == sz);
1660  size_type sz2 = 0;
1661  for_each([&] (value_type&) {
1662  sz2++;
1663  });
1664  size_type sz3 = size();
1665  assert(sz2 == sz3);
1666 #endif
1667  }
1668 
1669  void check() const {
1670 #ifndef NDEBUG
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());
1677  size_t sprev = -1;
1678  middle->for_each([&sprev] (chunk_pointer& c) {
1679  size_t scur = c->size();
1680  assert(scur > 0);
1681  if (sprev != -1)
1682  assert(sprev + scur > chunk_capacity);
1683  sprev = scur;
1684  });
1685  check_size();
1686 #endif
1687  }
1688 
1689  template <class Add_edge, class Process_chunk>
1690  void reveal_internal_structure(const Add_edge& add_edge,
1691  const Process_chunk& process_chunk) const {
1692  long rootptr = (long)this;
1693  rootptr -= 8;
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);
1704  }
1705 
1707 
1708 };
1709 
1710 /***********************************************************************/
1711 
1712 } // end namespace chunkedseq
1713 } // end namespace
1714 } // end namespace
1715 
1716 #endif
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.
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.
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.
value_type front() const
Accesses last item.
typename config_type::value_type value_type
void push_back(const value_type &x)
Adds item at the end.
void copy_measure_to(self_type &other)
Copies the measurement operator.
size_type size() const
Returns size.
void stream_frontn(const Consumer &cons, size_type nb) const
Consume first items.
void popn_back(Container &c, value_type *dst, size_type nb)
void popn_back(value_type *dst, size_type nb)
Deletes first items.
void stream_popn_front(const Consumer &cons, size_type nb)
Deletes first items.
iterator insert(Container &c, iterator position, const value_type &val)
void stream_backn(const Consumer &cons, size_type nb) const
Consume last items.
void pushn_front(Container &c, const_pointer src, size_type nb)
value_type operator[](size_type n) const
Access item.
void for_each_segment(iterator begin, iterator end, const Body &f)
value_type pop_front()
Deletes first item.
void stream_backn(const Container &c, const Consumer &cons, size_type nb)
void frontn(value_type *dst, size_type nb) const
Access first items.
void split_by_index(Container &c, size_type i, Container &other)
void backn(const Container &c, value_type *dst, size_type nb)
void popn_front(Container &c, value_type *dst, size_type nb)
Definition: algebra.hpp:18
typename Configuration::chunk_type chunk_type
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 stream_frontn(const Container &c, const Consumer &cons, size_type nb)
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.
void split_by_iterator(Container &c, iterator position, Container &other)
chunkedseqbase< config_type > self_type
void swap(self_type &other)
Swaps content.
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.
Extra container operations to be shared by chunked structures.
void for_each_segment(const Body &f) const
Visits every segment of items in the container.
void for_each(iterator beg, iterator end, const Body &f)
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)
void split_approximate(Container &c, Container &other)
STL style iterators for our chunked sequences.
iterator insert(iterator position, const value_type &val)
Inserts items.
void pushn_back(Container &c, const_pointer src, size_type nb)
iterator erase(Container &c, iterator first, iterator last)
const int chunk_capacity
[weighted_split_example]
measure_type get_measure() const
Returns measurement operator.
bool empty() const
Test whether the container is empty.
void frontn(const Container &c, value_type *dst, size_type nb)
chunkedseqbase(std::initializer_list< value_type > l)