Fixed-capacity vectors

The fixed-capacity buffer

Type	Description
allocator_type	STL-style allocator class
size_type	size_t
value_type	type of items to be stored in the container
reference	allocator_type::reference
const_reference	allocator_type::const_reference
pointer	allocator_type::pointer
const_pointer	allocator_type::const_pointer

Member	Description
capacity	integer value which denotes the maximum number items that can be contained in the chunk
full() const	returns true iff the container is full (i.e., reached capacity)
empty() const	returns true iff the container is empty
size() const	returns the number of items in the container
back() const	returns a reference to the last item in the container
front() const	returns a reference to the first item in the container
push_back(const value_type& x)	adds value x to the last position of the container
push_front(const value_type& x)	adds value x to the first position of the container
pop_back()	removes the value from the last position of the container
pop_front()	removes the value from the first position of the container
backn(value_type* xs, size_type nb)	copies the last nb items from the container to the memory pointed to by xs
frontn(value_type* xs, size_type nb)	copies the first nb items from the container to the memory pointed to by xs
pushn_back(const value_type* xs, size_type nb)	pushes on the back of the container the nb items from the memory pointed to by xs
pushn_front(const value_type* xs, size_type nb)	pushes on the front of the container the nb items from the memory pointed to by xs
pushn_back(const Body& body, size_type nb)	pushes on the back of the container nb uninitialized items (i.e., default-constructed items), then initializes each item i in the underlying vector vec by applying body(i, vec[i]) (behavior is undefined if size() + nb > capacity)
popn_front(size_type nb)	removes the first nb items from the container
popn_back(size_type nb)	removes the last nb items from the container
popn_front(value_type* xs, size_type nb)	removes the first nb items from the container and leaves the contents in the memory pointed to by xs
popn_back(value_type* xs, size_type nb)	removes the last nb items from the container and leaves the contents in the memory pointed to by xs
swap(Other_chunk& other)	swaps the contents of the chunk with the contents of another chunk of type Other_chunk
transfer_back_to_front(chunk& target, size_type nb)	moves the last nb items from this chunk to the front of the target chunk
transfer_front_to_back(chunk& target, size_type nb)	moves the first nb items from this chunk to the back of the target chunk
get_vec()	returns a reference to the underlying vector container
clear()	erases and deallocates the contents of the container
operator[](size_type ix) const	returns a reference to the item at position ix in the container
segment_by_index(size_type ix) const	returns the segment relative to the given index ix. in particular, the middle of the result segment points to the cell at index ix in the container and beginning and end point to the first and one past the last cell respectively that are both in the same contiguous chunk as the middle cell
index_of_pointer(const value_type* p) const	returns the index in the sequence corresponding to pointer p

For-each loops

The for-each loop operation offers sequential access to the items of a vector. To use the for-each loop, the client must apply the for_each method of the vector, providing the body of the loop as the argument. If it accesses items read only, the body of the loop must provide the following method:

Member function	Description
operator()(reference v)	represents the action of the loop body to perform on the container item referenced by v

Example: using for-each loop to compute a sum of the items of a container c

int sum = 0;
c.for_each([&sum] (reference v) {
    sum += v;
});

Implementations of fixed-capacity vectors provided by our library

This library provides two implementations of fixed-capacity vectors: the pasl::data::fixedcapacity::stack and the pasl::data::fixedcapacity::ringbuffer. Both export the same interface, namely the interface of the fixed-capacity vector, but each has different performance characteristics. The ringbuffer offers slightly slower but still fast constant-time access to both ends of the container. The stack is biased to offer fast access to the end of the container. The disadvantage is that the stack imposes a linear-time cost to push an item on the front of the container. That is, the contents of the container must be shifted right by one position each time an individual item is pushed on the front of the container. However, the contents of the stack need to be shifted right by n positions in order to push n items in bulk at once.

Example: fixed-capacity stack

template <class Array_alloc,
class Item_alloc = std::allocator<typename Array_alloc::value_type> >
class stack {
public:
  
  using size_type = int;
  using value_type = typename Array_alloc::value_type;
  using allocator_type = Item_alloc;
  using segment_type = segment<value_type*>;
  
  static constexpr int capacity = Array_alloc::capacity;
  
private:
  
  size_type bk;     // position of the last allocated cell
  Item_alloc alloc;
  Array_alloc array;
  
  static value_type& subscript(value_type* array, size_type bk, size_type ix) {
    assert(array != NULL);
    assert(ix >= 0);
    assert(ix <= bk);
    return array[ix];
  }
  
public:
  
  stack()
  : bk(-1) { }
  
  stack(const stack& other)
  : bk(-1) {
    if (other.size() == 0)
      return;
    const value_type* ptr = &other[0];
    pushn_back(ptr, other.size());
  }
  
  stack(size_type nb, const value_type& val) {
    pushn_back(const_foreach_body<Item_alloc>(val), nb);
  }
  
  ~stack() {
    clear();
  }
  
  inline size_type size() const {
    return bk + 1;
  }
  
  inline bool full() const {
    return size() == capacity;
  }
  
  inline bool empty() const {
    return size() == 0;
  }
  
  inline bool partial() const {
    return !empty() && !full(); // TODO: could be optimized
  }
  
  inline void push_front(const value_type& x) {
    assert(! full());
    pshiftn<Item_alloc>(&array[0], size(), +1);
    alloc.construct(&array[0], x);
    bk++;
  }
  
  inline void push_back(const value_type& x) {
    assert(! full());
    bk++;
    alloc.construct(&array[bk], x);
  }
  
  inline value_type& front() const {
    assert(! empty());
    return array[0];
  }
  
  inline value_type& back() const {
    assert(! empty());
    return array[bk];
  }
  
  inline value_type pop_front() {
    assert(! empty());
    value_type v = front();
    alloc.destroy(&(front()));
    pshiftn<Item_alloc>(&array.operator[](1), size() - 1, -1);
    bk--;
    return v;
  }
  
  inline value_type pop_back() {
    assert(! empty());
    value_type v = back();
    alloc.destroy(&(back()));
    bk--;
    return v;
  }
  
  void frontn(value_type* dst, size_type nb) {
    assert(size() >= nb);
    copy<Item_alloc>(dst, &array[0], nb);
  }
  
  void backn(value_type* dst, size_type nb) {
    assert(size() >= nb);
    copy<Item_alloc>(dst, &array.operator[](size() - nb), nb);
  }
  
  void pushn_front(const value_type* xs, size_type nb) {
    assert(nb + size() <= capacity);
    pshiftn<Item_alloc>(&array[0], size(), +nb);
    copy<Item_alloc>(&array[0], xs, nb);
    bk += nb;
  }
  
  void pushn_back(const value_type* xs, size_type nb) {
    assert(nb + size() <= capacity);
    copy<Item_alloc>(&array.operator[](size()), xs, nb);
    bk += nb;
  }
  
  template <class Body>
  void pushn_back(const Body& body, size_type nb) {
    assert(nb + size() <= capacity);
    papply<Body>(&array[bk+1], nb, 0, body);
    bk += nb;
  }
  
  void popn_front(size_type nb) {
    assert(size() >= nb);
    destroy_items<Item_alloc>(&array[0], nb);
    pshiftn<Item_alloc>(&array.operator[](nb), size() - nb, -nb);
    bk -= nb;
  }
  
  void popn_back(size_type nb) {
    assert(size() >= nb);
    destroy_items<Item_alloc>(&array[0], size() - nb, nb);
    bk -= nb;
  }
  
  void popn_front(value_type* dst, size_type nb) {
    frontn(dst, nb);
    popn_front(nb);
  }
  
  void popn_back(value_type* dst, size_type nb) {
    backn(dst, nb);
    popn_back(nb);
  }
  
  void transfer_from_back_to_front(stack& target, size_type nb) {
    assert(nb <= size());
    assert(target.size() + nb <= capacity);
    pshiftn<Item_alloc>(&target.array[0], target.size(), +nb);
    popn_back(&target.array[0], nb);
    target.bk += nb;
  }
  
  void transfer_from_front_to_back(stack& target, size_type nb) {
    assert(nb <= size());
    assert(target.size() + nb <= capacity);
    popn_front(&target.array.operator[](target.size()), nb);
    target.bk += nb;
  }
  
  value_type& operator[](size_type ix) const {
    return subscript(&array[0], bk, ix);
  }
  
  value_type& operator[](size_t ix) const {
    return subscript(&array[0], bk, (size_type)ix);
  }
  
  void clear() {
    popn_back(size());
  }
  
  void swap(stack& other) {
    array.swap(other.array);
    std::swap(bk, other.bk);
  }
  
  size_type index_of_last_item() const {
    size_type sz = size();
    return (sz > 0) ? sz - 1 : sz;
  }
  
  segment_type segment_by_index(size_type ix) const {
    segment_type seg;
    seg.begin = &array[0];
    seg.middle = &array[ix];
    seg.end = &array[index_of_last_item()] + 1;
    return seg;
  }
  
  size_type index_of_pointer(const value_type* p) const {
    assert(p >= &array[0]);
    assert(p <= &array[index_of_last_item()] + 1);
    return (size_type)(p - &array[0]);
  }
  
  template <class Body>
  void for_each(const Body& body) const {
    for (size_type i = 0; i < size(); i++)
      body((*this)[i]);
  }
  
  template <class Body>
  void for_each_segment(size_type lo, size_type hi, const Body& body) const {
    body(&array[size_type(lo)], &array[size_type(hi)]);
  }
  
};