chunkedseqbase.hpp

Go to the documentation of this file.

#include <assert.h>
#include <iostream>
#include <utility>
#include <vector>
#include <initializer_list>

#include "iterator.hpp"
#include "chunkedseqextras.hpp"

#ifndef _PASL_DATA_CHUNKEDSEQBASE_H_
#define _PASL_DATA_CHUNKEDSEQBASE_H_

namespace pasl {
namespace data {
namespace chunkedseq {

/***********************************************************************/

template <
  class Configuration,
  template <
    class Chunkedseq,
    class Configuration1
  >
  class Iterator=iterator::random_access
>
class chunkedseqbase {
protected:

  using chunk_type = typename Configuration::chunk_type;
  using chunk_search_type = typename Configuration::chunk_search_type;
  using chunk_cache_type = typename Configuration::chunk_cache_type;
  using chunk_measured_type = typename chunk_cache_type::measured_type;
  using chunk_algebra_type = typename chunk_cache_type::algebra_type;
  using chunk_measure_type = typename chunk_cache_type::measure_type;
  using chunk_pointer = chunk_type*;

  using middle_type = typename Configuration::middle_type;
  using middle_cache_type = typename Configuration::middle_cache_type;
  using middle_measured_type = typename middle_cache_type::measured_type;
  using middle_algebra_type = typename middle_cache_type::algebra_type;
  using middle_measure_type = typename middle_cache_type::measure_type;
  using size_access = typename Configuration::size_access;

  using const_self_pointer_type = const chunkedseqbase<Configuration>*;

  static constexpr int chunk_capacity = Configuration::chunk_capacity;

public:

  /*---------------------------------------------------------------------*/
  using config_type = Configuration;
  using self_type = chunkedseqbase<config_type>;
  using size_type = typename config_type::size_type;
  using difference_type = typename config_type::difference_type;
  using allocator_type = typename config_type::item_allocator_type;

  /*---------------------------------------------------------------------*/
  using value_type = typename config_type::value_type;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = value_type*;
  using const_pointer = const value_type*;
  using segment_type = typename config_type::segment_type;

  /*---------------------------------------------------------------------*/
  using cache_type = chunk_cache_type;
  using measured_type = typename cache_type::measured_type;
  using algebra_type = typename cache_type::algebra_type;
  using measure_type = typename cache_type::measure_type;

  using iterator = Iterator<self_type, config_type>;
  friend iterator;

private:

  // representation of the structure: four chunks plus a middle sequence of chunks;
  // for efficient implementation of emptiness test, additional invariants w.r.t. the paper:
  //  - if front_outer is empty, then front_inner is empty
  //  - if back_outer is empty, then back_inner is empty
  //  - if front_outer and back_outer are empty, then middle is empty
  chunk_type front_inner, back_inner, front_outer, back_outer;
  std::unique_ptr<middle_type> middle;

  chunk_measure_type chunk_meas;
  middle_measure_type middle_meas;

  /*---------------------------------------------------------------------*/

  static inline chunk_pointer chunk_alloc() {
    return new chunk_type();
  }

  // only to free empty chunks
  static inline void chunk_free(chunk_pointer c) {
    assert(c->empty());
    delete c;
  }

  template <class Pred>
  middle_measured_type chunk_split(const Pred& p, middle_measured_type prefix,
                                   chunk_type& src, reference x, chunk_type& dst) {
    chunk_search_type chunk_search;
    return src.split(chunk_meas, p, chunk_search, middle_meas, prefix, x, dst);
  }

  /*---------------------------------------------------------------------*/

  bool is_buffer(const chunk_type* c) const {
    return c == &front_outer || c == &front_inner
        || c == &back_inner  || c == &back_outer;
  }

  // ensures that if front_outer is empty, then front_inner and middle (and back_inner)
  // are all empty
  void restore_front_outer_empty_other_empty() {
    if (front_outer.empty()) {
      if (! front_inner.empty()) {
        front_inner.swap(front_outer);
      } else if (! middle->empty()) {
        chunk_pointer c = middle->pop_front(middle_meas);
        front_outer.swap(*c);
        chunk_free(c);
      } else if (! back_inner.empty()) {
        back_inner.swap(front_outer); // optional operation
      }
    }
    assert(! front_outer.empty()
       || (front_inner.empty() && middle->empty() && back_inner.empty()) );
  }

  void restore_back_outer_empty_other_empty() {
    if (back_outer.empty()) {
      if (! back_inner.empty()) {
        back_inner.swap(back_outer);
      } else if (! middle->empty()) {
        chunk_pointer c = middle->pop_back(middle_meas);
        back_outer.swap(*c);
        chunk_free(c);
      } else if (! front_inner.empty()) {
        front_inner.swap(back_outer); // optional operation
      }
    }
    assert(! back_outer.empty()
       || (back_inner.empty() && middle->empty() && front_inner.empty()) );
  }

  // ensures that if the container is nonempty, then so is the front-outer buffer
  void ensure_front_outer_nonempty() {
    restore_front_outer_empty_other_empty();
    if (front_outer.empty() && ! back_outer.empty())
      front_outer.swap(back_outer);
    assert(empty() || ! front_outer.empty());
  }

  void ensure_back_outer_nonempty() {
    restore_back_outer_empty_other_empty();
    if (back_outer.empty() && ! front_outer.empty())
      back_outer.swap(front_outer);
    assert(empty() || ! back_outer.empty());
  }

  // assumption: invariant "both outer empty implies middle empty" may be broken;
  // calling this function restores it.
  void restore_both_outer_empty_middle_empty() {
    if (front_outer.empty() && back_outer.empty() && ! middle->empty()) {
      // pop to the front (to the back would also work)
      chunk_pointer c = middle->pop_front(middle_meas);
      front_outer.swap(*c);
      chunk_free(c);
    }
  }

  // ensures that inner buffers are empty, by pushing them in the middle if full
  void ensure_empty_inner() {
    if (! front_inner.empty())
      push_buffer_front_force(front_inner);
    if (! back_inner.empty())
      push_buffer_back_force(back_inner);
  }

  using const_chunk_pointer = const chunk_type*;

  const_chunk_pointer get_chunk_containing_last_item() const {
    if (! back_outer.empty())
      return &back_outer;
    if (! back_inner.empty())
      return &back_inner;
    if (! middle->empty())
#ifdef DEBUG_MIDDLE_SEQUENCE
      return middle->back();
#else
      return middle->cback();
#endif
    if (! front_inner.empty())
      return &front_inner;
    return &front_outer;
  }

  using position_type = enum {
    found_front_outer,
    found_front_inner,
    found_middle,
    found_back_inner,
    found_back_outer,
    found_nowhere
  };

  template <class Pred>
  middle_measured_type search(const Pred& p, middle_measured_type prefix,
                              position_type& pos) const {
    middle_measured_type cur = prefix; // prefix including current chunk
    if (! front_outer.empty()) {
      prefix = cur;
      cur = middle_algebra_type::combine(cur, middle_meas(&front_outer));
      if (p(cur)) {
        pos = found_front_outer;
        return prefix;
      }
    }
    if (! front_inner.empty()) {
      prefix = cur;
      cur = middle_algebra_type::combine(cur, middle_meas(&front_inner));
      if (p(cur)) {
        pos = found_front_inner;
        return prefix;
      }
    }
    if (! middle->empty()) {
      prefix = cur;
      cur = middle_algebra_type::combine(cur, middle->get_cached());
      if (p(cur)) {
        pos = found_middle;
        return prefix;
      }
    }
    if (! back_inner.empty()) {
      prefix = cur;
      cur = middle_algebra_type::combine(cur, middle_meas(&back_inner));
      if (p(cur)) {
        pos = found_back_inner;
        return prefix;
      }
    }
    if (! back_outer.empty()) {
      prefix = cur;
      cur = middle_algebra_type::combine(cur, middle_meas(&back_outer));
      if (p(cur)) {
        pos = found_back_outer;
        return prefix;
      }
    }
    prefix = cur;
    pos = found_nowhere;
    return prefix;
  }

  // set "found" to true or false depending on success of the search;
  // and set "cur" to the chunk that contains the item searched,
  // or to the chunk containing the last item of the sequence if the item was not found.
  // if finger search is enabled, then the routine checks whether `cur` contains a
  // null pointer or a pointer to a chunk; in the latter case, search starts from
  // the chunk
  // precondition: `cur` contains either a `nullptr` or a pointer to a "top chunk";
  // i.e., a leaf node of the middle sequence
  template <class Pred>
  middle_measured_type search_for_chunk(const Pred& p, middle_measured_type prefix,
                                        bool& found, const_chunk_pointer& cur) const {
    position_type pos;
    prefix = search(p, prefix, pos);
    found = true; // default
    switch (pos) {
      case found_front_outer: {
        cur = &front_outer;
        break;
      }
      case found_front_inner: {
        cur = &front_inner;
        break;
      }
      case found_middle: {
#ifdef DEBUG_MIDDLE_SEQUENCE
        assert(false);
#else
        prefix = middle->search_for_chunk(p, prefix, cur);
#endif
        break;
      }
      case found_back_inner: {
        cur = &back_inner;
        break;
      }
      case found_back_outer: {
        cur = &back_outer;
        break;
      }
      case found_nowhere: {
        cur = &back_outer;
        found = false;
        break;
      }
    } // end switch
    return prefix;
  }

  // precondition: other is empty
  template <class Pred>
  middle_measured_type split_aux(const Pred& p, middle_measured_type prefix, reference x, self_type& other) {
    assert(other.empty());
    copy_measure_to(other);
    ensure_empty_inner();
    position_type pos;
    prefix = search(p, prefix, pos);
    switch (pos) {
      case found_front_outer: {
        prefix = chunk_split(p, prefix, front_outer, x, other.front_outer);
        middle.swap(other.middle);
        back_outer.swap(other.back_outer);
        break;
      }
      case found_front_inner: {
        assert(false); // thanks to the call to ensure_empty_inner()
        break;
      }
      case found_middle: {
        back_outer.swap(other.back_outer);
        chunk_pointer c;
        prefix = middle->split(middle_meas, p, prefix, c, *other.middle);
        back_outer.swap(*c);
        chunk_free(c);
        prefix = chunk_split(p, prefix, back_outer, x, other.front_outer);
        break;
      }
      case found_back_inner: {
        assert(false); // thanks to the call to ensure_empty_inner()
        break;
      }
      case found_back_outer: {
        prefix = chunk_split(p, prefix, back_outer, x, other.back_outer);
        break;
      }
      case found_nowhere: {
        // don't split (item not found)
        break;
      }
    } // end switch
    restore_both_outer_empty_middle_empty();
    other.restore_both_outer_empty_middle_empty();
    return prefix;
  }

  // precondition: other is empty
  template <class Pred>
  middle_measured_type split_aux(const Pred& p, middle_measured_type prefix, self_type& other) {
    size_type sz_orig = size();
    value_type x;
    prefix = split_aux(p, prefix, x, other);
    if (size_access::csize(prefix) < sz_orig)
      other.push_front(x);
    return prefix;
  }

  /*---------------------------------------------------------------------*/

  // take a chunk "c" and push its content into the back of the middle sequence
  // as a new chunk; leaving "c" empty.
  void push_buffer_back_force(chunk_type& c) {
    chunk_pointer d = chunk_alloc();
    c.swap(*d);
    middle->push_back(middle_meas, d);
  }

  // symmetric to push_buffer_back
  void push_buffer_front_force(chunk_type& c) {
    chunk_pointer d = chunk_alloc();
    c.swap(*d);
    middle->push_front(middle_meas, d);
  }

  // take a chunk "c" and concatenate its content into the back of the middle sequence
  // leaving "c" empty.
  void push_buffer_back(chunk_type& c) {
    size_t csize = c.size();
    if (csize == 0) {
      // do nothing
    } else if (middle->empty()) {
      push_buffer_back_force(c);
    } else {
      chunk_pointer b = middle->back();
      size_t bsize = b->size();
      if (bsize + csize > chunk_capacity) {
        push_buffer_back_force(c);
      } else {
        middle->pop_back(middle_meas);
        c.transfer_from_front_to_back(chunk_meas, *b, csize);
        middle->push_back(middle_meas, b);
      }
    }
  }

  // symmetric to push_buffer_back
  void push_buffer_front(chunk_type& c) {
    size_t csize = c.size();
    if (csize == 0) {
      // do nothing
    } else if (middle->empty()) {
      push_buffer_front_force(c);
    } else {
      chunk_pointer b = middle->front();
      size_t bsize = b->size();
      if (bsize + csize > chunk_capacity) {
        push_buffer_front_force(c);
      } else {
        middle->pop_front(middle_meas);
        c.transfer_from_back_to_front(chunk_meas, *b, csize);
        middle->push_front(middle_meas, b);
      }
    }
  }

  void init() {
    middle.reset(new middle_type());
  }

public:

  /*---------------------------------------------------------------------*/

  chunkedseqbase() {
    init();
  }

  chunkedseqbase(size_type n, const value_type& val) {
    init();
    std::vector<value_type> vals(chunk_capacity, val);
    const value_type* p = vals.data();
    auto prod = [&] (size_type, size_type nb) {
      return std::make_pair(p, p + nb);
    };
    stream_pushn_back(prod, n);
  }

  chunkedseqbase(const self_type& other)
  : front_outer(other.front_outer),
    front_inner(other.front_inner),
    back_inner(other.back_inner),
    back_outer(other.back_outer),
    chunk_meas(other.chunk_meas),
    middle_meas(other.middle_meas) {
    middle.reset(new middle_type(*other.middle));
    check();
  }
  
  chunkedseqbase(std::initializer_list<value_type> l) {
    init();
    for (auto it = l.begin(); it != l.end(); it++)
      push_back(*it);
  }

  /*---------------------------------------------------------------------*/

  bool empty() const {
    return front_outer.empty() && back_outer.empty();
  }

  size_type size() const {
    size_type sz = 0;
    sz += front_outer.size();
    sz += front_inner.size();
    sz += size_access::csize(middle->get_cached());
    sz += back_inner.size();
    sz += back_outer.size();
    return sz;
  }

  /*---------------------------------------------------------------------*/


  value_type front() const {
    assert(! front_outer.empty() || front_inner.empty());
    value_type v;
    if (! front_outer.empty()) {
      return front_outer.front();
    } else if (! back_inner.empty()) {
      return back_inner.front();
    } else {
      assert(! back_outer.empty());
      return back_outer.front();
    }
  }

  value_type back() const {
    assert(! back_outer.empty() || back_inner.empty());
    if (! back_outer.empty()) {
      return back_outer.back();
    } else if (! front_inner.empty()) {
      return front_inner.back();
    } else {
      assert(! front_outer.empty());
      return front_outer.back();
    }
  }

  void backn(value_type* dst, size_type nb) const {
    extras::backn(*this, dst, nb);
  }

  void frontn(value_type* dst, size_type nb) const {
    extras::frontn(*this, dst, nb);
  }

  template <class Consumer>
  void stream_backn(const Consumer& cons, size_type nb) const {
    extras::stream_backn(*this, cons, nb);
  }

  template <class Consumer>
  void stream_frontn(const Consumer& cons, size_type nb) const {
    extras::stream_frontn(*this, cons, nb);
  }

  value_type operator[](size_type n) const {
    assert(n >= 0);
    assert(n < size());
    auto it = begin() + n;
    assert(it.size() == n + 1);
    return *it;
  }

  reference operator[](size_type n) {
    assert(n >= 0);
    assert(n < size());
    auto it = begin() + n;
    assert(it.size() == n + 1);
    return *it;
  }

  /*---------------------------------------------------------------------*/

  void push_front(const value_type& x) {
    if (front_outer.full()) {
      if (front_inner.full())
        push_buffer_front_force(front_inner);
      front_outer.swap(front_inner);
      assert(front_outer.empty());
    }
    front_outer.push_front(chunk_meas, x);
  }

  void push_back(const value_type& x) {
    if (back_outer.full()) {
      if (back_inner.full())
        push_buffer_back_force(back_inner);
      back_outer.swap(back_inner);
      assert(back_outer.empty());
    }
    back_outer.push_back(chunk_meas, x);
  }

  value_type pop_front() {
    if (front_outer.empty()) {
      assert(front_inner.empty());
      if (! middle->empty()) {
        chunk_pointer c = middle->pop_front(middle_meas);
        front_outer.swap(*c);
        chunk_free(c);
      } else if (! back_inner.empty()) {
        back_inner.swap(front_outer);
      } else if (! back_outer.empty()) {
        back_outer.swap(front_outer);
      }
    }
    assert(! front_outer.empty());
    value_type x = front_outer.pop_front(chunk_meas);
    restore_front_outer_empty_other_empty();
    return x;
  }

  value_type pop_back() {
    if (back_outer.empty()) {
      assert(back_inner.empty());
      if (! middle->empty()) {
        chunk_pointer c = middle->pop_back(middle_meas);
        back_outer.swap(*c);
        chunk_free(c);
      } else if (! front_inner.empty()) {
        front_inner.swap(back_outer);
      } else if (! front_outer.empty()) {
        front_outer.swap(back_outer);
      }
    }
    assert(! back_outer.empty());
    value_type x = back_outer.pop_back(chunk_meas);
    restore_back_outer_empty_other_empty();
    return x;
  }

  void pushn_back(const_pointer src, size_type nb) {
    extras::pushn_back(*this, src, nb);
  }

  void pushn_front(const_pointer src, size_type nb) {
    extras::pushn_front(*this, src, nb);
  }

  void popn_front(size_type nb) {
    auto c = [] (const_pointer, const_pointer) { };
    stream_popn_front<typeof(c), false>(c, nb);
  }

  void popn_back(size_type nb) {
    auto c = [] (const_pointer, const_pointer) { };
    stream_popn_back<typeof(c), false>(c, nb);
  }

  void popn_back(value_type* dst, size_type nb) {
    extras::popn_back(*this, dst, nb);
  }

  void popn_front(value_type* dst, size_type nb) {
    extras::popn_front(*this, dst, nb);
  }

  template <class Producer>
  void stream_pushn_back(const Producer& prod, size_type nb) {
    if (nb == 0)
      return;
    size_type sz_orig = size();
    ensure_empty_inner();
    chunk_type c;
    c.swap(back_outer);
    size_type i = 0;
    while (i < nb) {
      size_type cap = (size_type)chunk_capacity;
      size_type m = std::min(cap, nb - i);
      m = std::min(m, cap - c.size());
      std::pair<const_pointer,const_pointer> rng = prod(i, m);
      const_pointer lo = rng.first;
      const_pointer hi = rng.second;
      size_type nb = hi - lo;
      c.pushn_back(chunk_meas, lo, nb);
      push_buffer_back(c);
      i += m;
    }
    restore_back_outer_empty_other_empty();
    assert(sz_orig + nb == size());
  }

  template <class Producer>
  void stream_pushn_front(const Producer& prod, size_type nb) {
    if (nb == 0)
      return;
    size_type sz_orig = size();
    ensure_empty_inner();
    chunk_type c;
    c.swap(front_outer);
    size_type n = nb;
    while (n > 0) {
      size_type cap = (size_type)chunk_capacity;
      size_type m = std::min(cap, n);
      m = std::min(m, cap - c.size());
      n -= m;
      std::pair<const_pointer,const_pointer> rng = prod(n, m);
      const_pointer lo = rng.first;
      const_pointer hi = rng.second;
      size_type nb = hi - lo;
      c.pushn_front(chunk_meas, lo, nb);
      push_buffer_front(c);
    }
    restore_front_outer_empty_other_empty();
    assert(sz_orig + nb == size());
  }

  template <class Consumer, bool should_consume=true>
  void stream_popn_back(const Consumer& cons, size_type nb) {
    size_type sz_orig = size();
    assert(sz_orig >= nb);
    size_type i = 0;
    while (i < nb) {
      ensure_back_outer_nonempty();
      size_type m = std::min(back_outer.size(), nb - i);
      back_outer.template popn_back<Consumer,should_consume>(chunk_meas, cons, m);
      i += m;
    }
    ensure_back_outer_nonempty();  // to restore invariants
    assert(sz_orig == size() + nb);
  }

  template <class Consumer, bool should_consume=true>
  void stream_popn_front(const Consumer& cons, size_type nb) {
    size_type sz_orig = size();
    assert(sz_orig >= nb);
    size_type i = 0;
    while (i < nb) {
      ensure_front_outer_nonempty();
      size_type m = std::min(front_outer.size(), nb - i);
      front_outer.template popn_front<Consumer,should_consume>(chunk_meas, cons, m);
      i += m;
    }
    ensure_front_outer_nonempty(); // to restore invariants
    assert(sz_orig == size() + nb);
  }

  void concat(self_type& other) {
    if (other.size() == 0)
      return;
    if (size() == 0)
      swap(other);
    // push buffers into the middle sequences
    push_buffer_back(back_inner);
    push_buffer_back(back_outer);
    other.push_buffer_front(other.front_inner);
    other.push_buffer_front(other.front_outer);
    // fuse front and back, if needed
    if (! middle->empty() && ! other.middle->empty()) {
      chunk_pointer c1 = middle->back();
      chunk_pointer c2 = other.middle->front();
      size_type nb1 = c1->size();
      size_type nb2 = c2->size();
      if (nb1 + nb2 <= chunk_capacity) {
        middle->pop_back(middle_meas);
        other.middle->pop_front(middle_meas);
        c2->transfer_from_front_to_back(chunk_meas, *c1, nb2);
        chunk_free(c2);
        middle->push_back(middle_meas, c1);
        // note: push might be factorized with earlier operations
      }
    }
    // migrate back chunks of the other and update the weight
    back_inner.swap(other.back_inner);
    back_outer.swap(other.back_outer);
    // concatenate the middle sequences
    middle->concat(middle_meas, *other.middle);
    // restore invariants
    restore_both_outer_empty_middle_empty();
    assert(other.empty());
  }

  template <class Pred>
  bool split(const Pred& p, reference middle_item, self_type& other) {
    size_type sz_orig = size();
    auto q = [&] (middle_measured_type m) {
      return p(size_access::cclient(m));
    };
    middle_measured_type prefix = split_aux(q, middle_algebra_type::identity(), middle_item, other);
    bool found = (size_access::csize(prefix) < sz_orig);
    return found;
  }

  template <class Pred>
  void split(const Pred& p, self_type& other) {
    value_type middle_item;
    bool found = split(p, middle_item, other);
    if (found)
      other.push_front(middle_item);
  }

  void split(size_type i, self_type& other) {
    extras::split_by_index(*this, i, other);
  }

  void split(iterator position, self_type& other) {
    extras::split_by_iterator(*this, position, other);
  }

  void split_approximate(self_type& other) {
    extras::split_approximate(*this, other);
  }

  iterator insert(iterator position, const value_type& val) {
    return extras::insert(*this, position, val);
  }

  iterator erase(iterator first, iterator last) {
    return extras::erase(*this, first, last);
  }

  void clear() {
    popn_back(size());
  }

  void swap(self_type& other) {
    std::swap(chunk_meas, other.chunk_meas);
    std::swap(middle_meas, other.middle_meas);
    front_outer.swap(other.front_outer);
    front_inner.swap(other.front_inner);
    middle.swap(other.middle);
    back_inner.swap(other.back_inner);
    back_outer.swap(other.back_outer);
  }


  friend void extras::split_by_index<self_type,size_type>(self_type& c, size_type i, self_type& other);

  /*---------------------------------------------------------------------*/

  iterator begin() const {
    return iterator(this, middle_meas, chunkedseq::iterator::begin);
  }

  iterator end() const {
    return iterator(this, middle_meas, chunkedseq::iterator::end);
  }

  template <class Body>
  void for_each(const Body& f) const {
    front_outer.for_each(f);
    front_inner.for_each(f);
    middle->for_each([&] (chunk_pointer p) {
      p->for_each(f);
    });
    back_inner.for_each(f);
    back_outer.for_each(f);
  }

  template <class Body>
  void for_each(iterator beg, iterator end, const Body& f) const {
    extras::for_each(beg, end, f);
  }

  template <class Body>
  void for_each_segment(const Body& f) const {
    front_outer.for_each_segment(f);
    front_inner.for_each_segment(f);
    middle->for_each([&] (chunk_pointer p) {
      p->for_each_segment(f);
    });
    back_inner.for_each_segment(f);
    back_outer.for_each_segment(f);
  }

  template <class Body>
  static void for_each_segment(iterator begin, iterator end, const Body& f) {
    extras::for_each_segment(begin, end, f);
  }


  /*---------------------------------------------------------------------*/

  measured_type get_cached() const {
    measured_type m = algebra_type::identity();
    m = algebra_type::combine(m, front_outer.get_cached());
    m = algebra_type::combine(m, front_inner.get_cached());
    measured_type n = size_access::cclient(middle->get_cached());
    m = algebra_type::combine(m, n);
    m = algebra_type::combine(m, back_inner.get_cached());
    m = algebra_type::combine(m, back_outer.get_cached());
    return m;
  }

  measure_type get_measure() const {
    return chunk_meas;
  }

  void set_measure(measure_type meas) {
    chunk_meas = meas;
    middle_meas.set_client_measure(meas);
  }

  void copy_measure_to(self_type& other) {
    other.set_measure(get_measure());
  }

  /*---------------------------------------------------------------------*/
  // TODO: instead of taking this ItemPrinter argument, we could assume the ItemPrinter to be known from Item type
  template <class ItemPrinter>
  void print_chunk(const chunk_type& c) const  {
    printf("(");
    c.for_each([&] (value_type& x) {
      ItemPrinter::print(x);
      printf(" ");
    });
    printf(")");
  }

  // TODO: see whether we want to print cache
  class DummyCachePrinter { };

  template <class ItemPrinter, class CachePrinter = DummyCachePrinter>
  void print() const {
    auto show = [&] (const chunk_type& c) {
      print_chunk<ItemPrinter>(c); };
    show(front_outer);
    printf(" ");
    show(front_inner);
    printf(" [");
    middle->for_each([&] (chunk_pointer& c) {
      show(*c);
      printf(" ");
    });
    printf("] ");
    show(back_inner);
    printf(" ");
    show(back_outer);
  }

  void check_size() const {
#ifndef NDEBUG
    size_type sz = 0;
    middle->for_each([&] (chunk_pointer& c) {
      sz += c->size();
    });
    size_type msz = size_access::csize(middle->get_cached());
    assert(msz == sz);
    size_type sz2 = 0;
    for_each([&] (value_type&) {
      sz2++;
    });
    size_type sz3 = size();
    assert(sz2 == sz3);
#endif
  }

  void check() const {
#ifndef NDEBUG
    if (front_outer.empty())
      assert(front_inner.empty());
    if (back_outer.empty())
      assert(back_inner.empty());
    if (front_outer.empty() && back_outer.empty())
      assert(middle->empty());
    size_t sprev = -1;
    middle->for_each([&sprev] (chunk_pointer& c) {
      size_t scur = c->size();
      assert(scur > 0);
      if (sprev != -1)
        assert(sprev + scur > chunk_capacity);
      sprev = scur;
    });
    check_size();
#endif
  }

  template <class Add_edge, class Process_chunk>
  void reveal_internal_structure(const Add_edge& add_edge,
                                 const Process_chunk& process_chunk) const {
    long rootptr = (long)this;
    rootptr -= 8;
    add_edge((void*)rootptr, (void*)&front_outer);
    add_edge((void*)rootptr, (void*)&front_inner);
    add_edge((void*)rootptr, (void*)middle.get());
    add_edge((void*)rootptr, (void*)&back_inner);
    add_edge((void*)rootptr, (void*)&back_outer);
    process_chunk(&front_outer);
    process_chunk(&front_inner);
    middle->reveal_internal_structure(add_edge, process_chunk);
    process_chunk(&back_inner);
    process_chunk(&back_outer);
  }


};

/***********************************************************************/

} // end namespace chunkedseq
} // end namespace
} // end namespace

#endif