Segments

In this package, we use the term segment to refer to pointer values which reference a range in memory. We define two particular forms of segments:

• A basic segment is a value which consists of two pointers, namely begin and end, that define the right-open interval, (begin, end].
• An enriched segment is a value which consists of a basic segment, along with a pointer, namely middle, which points at some location in between begin and end, such that begin <= middle < end.

The following class defines a representation for enriched segments.

template <class Pointer>
class segment {
public:
  
  using pointer_type = Pointer;
  
  // points to the first cell of the interval
  pointer_type begin;
  // points to a cell contained in the interval
  pointer_type middle;
  // points to the cell that is one cell past the last cell of interval
  pointer_type end;
  
  segment()
  : begin(nullptr), middle(nullptr), end(nullptr) { }
  
  segment(pointer_type begin, pointer_type middle, pointer_type end)
  : begin(begin), middle(middle), end(end) { }
  
};

Example

#include <iostream>
#include <string>
#include <assert.h>

#include "chunkedseq.hpp"

int main(int argc, const char * argv[]) {
  
  const int chunk_size = 2;
  using mydeque_type = pasl::data::chunkedseq::bootstrapped::deque<int, chunk_size>;
  
  mydeque_type mydeque = { 0, 1, 2, 3, 4, 5 };
  
  std::cout << "mydeque contains:";
  // iterate over the segments in mydeque
  mydeque.for_each_segment([&] (int* begin, int* end) {
    // iterate over the items in the current segment
    int* p = begin;
    while (p != end)
      std::cout << " " << *p++;
  });
  std::cout << std::endl;
  
  using iterator = typename mydeque_type::iterator;
  using segment_type = typename mydeque_type::segment_type;
  
  // iterate over the items in the segment which contains the item at position 3
  iterator it = mydeque.begin() + 3;
  segment_type seg = it.get_segment();
  
  std::cout << "the segment which contains mydeque[3] contains:";
  int* p = seg.begin;
  while (p != seg.end)
    std::cout << " " << *p++;
  std::cout << std::endl;
  
  std::cout << "mydeque[3]=" << *seg.middle << std::endl;
  
  return 0;
  
}

Output

mydeque contains: 0 1 2 3 4 5
the segment which contains mydeque[3] contains: 2 3
mydeque[3]=3