xdeque.h
// xdeque.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2011
#pragma once
#ifndef Ceda_cxUtils_xdeque_H
#define Ceda_cxUtils_xdeque_H
#include "cxUtils.h"
#include "CedaAssert.h"
#include "MakeIterator.h"
#include "xostream.h"
#include "VectorOfByte.h" // needed for Find
#include <algorithm>
#include <cstddef>
#include <initializer_list>
namespace ceda
{
/*
An xdeque supports efficient push/pop from both ends. Insertion or erase in the middle
of the queue is less efficient, but still reasonable because only elements within a single
page need be moved.
The queue is implemented using a double linked list of pages. Nominally all pages are
supposed to be the same size. However the implementation allows for any page to have any
nonzero number of elements up to the maximum size. This allows for efficient insertion
and deletion in the middle of the queue, and allows for two queues to be joined very
efficiently (simply by merging the linked lists into a single larger linked list). However
it means random access is relatively slow, because it involves stepping through the pages.
A page is never empty (so the xdeque is empty if and only if there are no pages, and
first_ = last_ = nullptr).
Relocability
------------
An xdeque<T> assumes that the elements of type T are relocatable - meaning they can be moved
in memory using memmove operations.
*/
// Copy [s1,s2) to [d1, d1+n) where n = s2-s1
// Can be used to move elements downwards
template <typename T>
void p_copy_down(T* d1, const T* s1, const T* s2)
{
cxAssert(s1);
cxAssert(s2);
cxAssert(d1);
while(s1 < s2)
{
*d1++ = *s1++;
}
}
// Copy [s1,s2) to [d2-n, d2) where n = s2-s1
// Can be used to move elements downwards
template <typename T>
void p_copy_up(T* d2, const T* s1, const T* s2)
{
cxAssert(s1);
cxAssert(s2);
cxAssert(d2);
while(s2 > s1)
{
*--d2 = *--s2;
}
}
#define CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(T) \
inline void p_copy_down(T* d1, const T* s1, const T* s2) { memmove(d1,s1,(s2-s1)*sizeof(T)); } \
inline void p_copy_up(T* d2, const T* s1, const T* s2) { ssize_t n = (s2-s1)*sizeof(T); memmove((octet_t*)d2-n,s1,n); }
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(bool)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(char)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(uint8)
//CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(wchar_t)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(int16)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(uint16)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(int32)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(uint32)
//CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(long)
//CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(unsigned long)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(int64)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(uint64)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(float32)
CEDA_USE_MEMMOVE_P_COPY_UP_DOWN(float64)
#define CEDA_VALIDATE_XDEQUE 0
template <typename T, ssize_t pageSize = 4096/sizeof(T)>
class xdeque
{
private:
struct Page
{
Page() : m_t1(pageSize/2), m_t2(pageSize/2), prev_(nullptr), next_(nullptr) {}
// The amount of the page which is currently filled
ssize_t size() const { return m_t2-m_t1; }
void MoveDown(ssize_t d1, ssize_t s1, ssize_t s2)
{
cxAssert(d1 <= s1);
p_copy_down(m_buffer+d1, m_buffer+s1, m_buffer+s2);
}
void MoveUp(ssize_t d2, ssize_t s1, ssize_t s2)
{
cxAssert(d2 >= s2);
p_copy_up(m_buffer+d2, m_buffer+s1, m_buffer+s2);
}
#if CEDA_VALIDATE_XDEQUE
void Validate() const
{
cxAssert(0 <= m_t1 && m_t1 <= m_t2 && m_t2 <= pageSize);
}
#endif
// Insert space for n elements at position i.
// Returns -1 if insertion cannot be satisfied
//
// [ [ ) )
// 0 t1 | t2 pageSize
// i
ssize_t InsertSpaceInPage(ssize_t i, ssize_t n)
{
cxAssert(0 <= n);
cxAssert(0 <= m_t1 && m_t1 <= m_t2 && m_t2 <= pageSize);
cxAssert(m_t1 <= i && i <= m_t2);
if (n <= m_t1)
{
// Shift left section [m_t1,i) downwards by n
MoveDown(m_t1-n, m_t1, i);
m_t1 = m_t1-n;
return i-n;
}
else if (n <= pageSize-m_t2)
{
// Shift right section [i,m_t2) upwards by n
MoveUp(m_t2+n, i, m_t2);
m_t2 = m_t2+n;
return i;
}
else
{
// Rather simplistically we assume the insertion cannot be satisfied.
return -1;
}
}
ssize_t InsertInPage(ssize_t i, const T& x)
{
cxAssert(0 <= m_t1 && m_t1 <= m_t2 && m_t2 <= pageSize);
cxAssert(m_t1 <= i && i <= m_t2);
i = InsertSpaceInPage(i,1);
cxAssert(i != -1);
m_buffer[i] = x;
return i;
}
// [i1,i2) is assumed to be inside [m_t1,m_t2)
//
// [ [ [ ) ) )
// 0 t1 i1 i2 t2 pageSize
ssize_t EraseRange(ssize_t i1, ssize_t i2)
{
cxAssert(0 <= m_t1 && m_t1 <= m_t2 && m_t2 <= pageSize);
cxAssert(m_t1 <= i1 && i1 <= i2 && i2 <= m_t2);
ssize_t n = i2-i1;
if (n > 0)
{
if (m_t2-i2 < i1-m_t1) // Pick best option - according to which is the smallest piece
{
// Shift right section [i2,m_t2) downwards by n
MoveDown(i1,i2,m_t2);
m_t2 -= n;
return i1;
}
else
{
// Shift left section [m_t1,i1) upwards by n
MoveUp(i2,m_t1,i1);
m_t1 += n;
return i2;
}
}
else
{
return i1;
}
}
T m_buffer[pageSize];
// The range of the page which is currently in use is [m_t1,m_t2)
// where 0 <= m_t1 <= m_t2 <= pageSize
ssize_t m_t1;
ssize_t m_t2;
// Double linked list of pages
Page* prev_;
Page* next_;
};
class PageAllocator
{
public:
PageAllocator() : m_free(nullptr) {}
~PageAllocator()
{
delete m_free;
}
Page* New()
{
if (m_free)
{
Page* p = m_free;
p->prev_ = nullptr;
p->next_ = nullptr;
m_free = nullptr;
return p;
}
else
{
return new Page;
}
}
void Delete(Page* p)
{
cxAssert(p);
if (m_free)
{
delete p;
}
else
{
m_free = p;
}
}
private:
// Points to a free page or nullptr
Page* m_free;
};
// The first and last pages in the linked list
Page* first_;
Page* last_;
// Total number of elements in the deque
ssize_t size_;
PageAllocator m_allocator;
private:
// Insert a new page to the left of p. Returns a pointer to the created page
// If p == nullptr then insert a page at the end
Page* InsertPage(Page* p)
{
Page* left = m_allocator.New();
cxAssert(left->prev_ == nullptr);
cxAssert(left->next_ == nullptr);
if (p)
{
left->next_ = p;
left->prev_ = p->prev_;
if (p->prev_)
{
cxAssert(p->prev_->next_ == p);
p->prev_->next_ = left;
}
else
{
cxAssert(p == first_);
first_ = left;
}
p->prev_ = left;
}
else
{
if (last_)
{
cxAssert(last_->next_ == nullptr);
last_->next_ = left;
left->prev_ = last_;
last_ = left;
}
else
{
cxAssert(size_ == 0);
cxAssert(first_ == nullptr);
first_ = last_ = left;
}
}
return left;
}
// Split page 'left' (which must not be nullptr) so that the first 'i' elements remain on
// 'left' and the remaining elements are moved onto a new page created to the right of
// left. Returns address of the created right page.
//
// left right
//
// [ [------|-------) ) [ [------------) )
// 0 t1 | t2 pageSize 0 t1 t2 pageSize
// i
Page* SplitPage(Page* left, ssize_t i)
{
cxAssert(left);
cxAssert(left->m_t1 < i && i < left->m_t2);
ssize_t n = left->m_t2 - i;
cxAssert(n > 0);
Page* right = InsertPage(left->next_);
right->m_t1 = 0;
right->m_t2 = n;
cxAssert(left->next_ == right);
cxAssert(right->prev_ == left);
// Copy left:[i,t2) to right:[0,n)
p_copy_down(right->m_buffer, left->m_buffer+i, left->m_buffer+left->m_t2);
left->m_t2 = i;
return right;
}
Page* ErasePage(Page* p)
{
cxAssert(p);
Page* prev = p->prev_;
Page* next = p->next_;
if (prev)
{
prev->next_ = next;
}
else
{
cxAssert(first_ == p);
first_ = next;
}
//size_ -= p->size();
m_allocator.Delete(p);
if (next)
{
next->prev_ = prev;
}
else
{
last_ = prev;
}
return next;
}
// Erase pages in range [p1,p2), using nullptr to represent one past the last page
// ErasePages(p,p) is a no-op that returns p. In particular ErasePages(nullptr,nullptr)
// returns nullptr
void ErasePages(Page* p1, Page* p2)
{
if (p1 != p2)
{
cxAssert(p1);
Page* prev = p1->prev_;
if (prev)
{
prev->next_ = p2;
}
else
{
cxAssert(first_ == p1);
first_ = p2;
}
// Delete pages in [p1,p2)
do
{
Page* n = p1->next_;
//size_ -= p1->size();
m_allocator.Delete(p1);
p1 = n;
} while(p1 != p2);
if (p2)
{
p2->prev_ = prev;
}
else
{
last_ = prev;
}
}
}
public:
typedef T value_type;
typedef ssize_t size_type;
typedef ssize_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
~xdeque() { clear(); }
/////////////// constructors //////////////////
xdeque() : first_(nullptr), last_(nullptr), size_(0) {}
xdeque(const xdeque& r, ssize_t ri, ssize_t rn) : first_(nullptr), last_(nullptr), size_(0)
{
cxAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
push_back(r.begin()+ri, r.begin()+ri+rn);
}
xdeque(const T* p, ssize_t pn) : first_(nullptr), last_(nullptr), size_(0)
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
push_back(p,pn);
}
explicit xdeque(ssize_t count, const T& x = T()) : first_(nullptr), last_(nullptr), size_(0)
{
push_back(count, x);
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
xdeque(It r1, It r2) : first_(nullptr), last_(nullptr), size_(0)
{
push_back(r1,r2);
}
xdeque(const T* r1, const T* r2) : first_(nullptr), last_(nullptr), size_(0)
{
cxAssert(r1 <= r2);
push_back(r1,r2);
}
xdeque(const xdeque& r) : first_(nullptr), last_(nullptr), size_(0)
{
push_back(r.begin(), r.end());
}
xdeque(std::initializer_list<T> r) : first_(nullptr), last_(nullptr), size_(0)
{
push_back(r.begin(), r.end());
}
/////////////// //////////////////
#if CEDA_VALIDATE_XDEQUE
void Validate()
{
//Tracer() << "\nSize = " << size_ << " first = " << first_ << " last = " << last_ << '\n';
if (size_ == 0)
{
cxAssert(first_ == nullptr);
cxAssert(last_ == nullptr);
}
else
{
cxAssert(size_ > 0);
cxAssert(first_);
cxAssert(last_);
cxAssert(first_->prev_ == nullptr);
cxAssert(last_->next_ == nullptr);
{
ssize_t s = 0;
Page* p = first_;
while(p)
{
p->Validate();
cxAssert(p->size() > 0);
//Tracer() << "Page " << p << " size " << p->size() << " t1 = " << p->m_t1 << " t2 = " << p->m_t2 << '\n';
s += p->size();
p = p->next_;
}
cxAssert(s == size_);
}
Page* p1 = first_;
Page* p2 = p1->next_;
while(p2)
{
cxAssert(p1->next_ == p2);
cxAssert(p2->prev_ == p1);
p1 = p2;
p2 = p1->next_;
}
cxAssert(p1 == last_);
}
}
#endif
xdeque& operator=(const xdeque& r)
{
if (this != &r) assign(r);
return *this;
}
void swap(xdeque& rhs)
{
using std::swap;
swap(first_, rhs.first_);
swap(last_, rhs.last_);
swap(size_, rhs.size_);
}
ssize_t size() const
{
return size_;
}
void resize(ssize_t newSize, const T& x = T())
{
cxAssert(newSize >= 0);
ssize_t oldSize = size();
if (newSize > oldSize)
{
push_back(newSize-oldSize, x);
}
else
{
erase_range(newSize, oldSize);
}
}
bool empty() const
{
return size_ == 0;
}
const T& front() const
{
cxAssert(first_);
cxAssert(first_->size() > 0);
return first_->m_buffer[first_->m_t1];
}
T& front()
{
cxAssert(first_);
cxAssert(first_->size() > 0);
return first_->m_buffer[first_->m_t1];
}
const T& back() const
{
cxAssert(last_);
cxAssert(last_->size() > 0);
return last_->m_buffer[last_->m_t2-1];
}
T& back()
{
cxAssert(last_);
cxAssert(last_->size() > 0);
return last_->m_buffer[last_->m_t2-1];
}
const T& operator[](ssize_t i) const
{
cxAssert(0 <= i && i < size_);
return *(begin() + i);
}
T& operator[](ssize_t i)
{
cxAssert(0 <= i && i < size_);
return *(begin() + i);
}
class IteratorPolicy
{
public:
IteratorPolicy() : m_page(nullptr), m_index(-1), m_overallIndex(0) {}
IteratorPolicy(Page* page, ssize_t index, ssize_t overallIndex) : m_page(page), m_index(index), m_overallIndex(overallIndex) {}
IteratorPolicy(const IteratorPolicy& rhs) : m_page(rhs.m_page),m_index(rhs.m_index),m_overallIndex(rhs.m_overallIndex) {}
typedef std::random_access_iterator_tag iterator_category;
typedef T value_type;
typedef std::ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
typedef const T* const_pointer;
typedef const T& const_reference;
bool operator==(const IteratorPolicy& rhs) const
{
return m_overallIndex == rhs.m_overallIndex;
}
bool operator<(const IteratorPolicy& rhs) const
{
return m_overallIndex < rhs.m_overallIndex;
}
void next()
{
cxAssert(m_page);
cxAssert(0 <= m_page->m_t1 && m_page->m_t1 < m_page->m_t2 && m_page->m_t2 <= pageSize);
cxAssert(m_page->m_t1 <= m_index && m_index < m_page->m_t2);
++m_overallIndex;
if (++m_index == m_page->m_t2)
{
// Only step onto next page if there is a next page, so that --end() is defined
if (m_page->next_)
{
m_page = m_page->next_;
m_index = m_page->m_t1;
}
}
}
void prev()
{
cxAssert(m_page);
cxAssert(0 <= m_page->m_t1 && m_page->m_t1 < m_page->m_t2 && m_page->m_t2 <= pageSize);
cxAssert(m_page->m_t1 <= m_index && m_index <= m_page->m_t2);
cxAssert(m_overallIndex > 0);
--m_overallIndex;
if (--m_index < m_page->m_t1)
{
m_page = m_page->prev_;
cxAssert(m_page);
m_index = m_page->m_t2-1;
cxAssert(0 <= m_index);
}
}
value_type& deref() const
{
cxAssert(m_page);
cxAssert(0 <= m_page->m_t1 && m_page->m_t1 < m_page->m_t2 && m_page->m_t2 <= pageSize);
cxAssert(m_page->m_t1 <= m_index && m_index < m_page->m_t2);
return m_page->m_buffer[m_index];
}
const value_type& const_deref() const
{
return deref();
}
difference_type operator-(const IteratorPolicy& rhs) const
{
return m_overallIndex - rhs.m_overallIndex;
}
IteratorPolicy operator+(difference_type d) const
{
if (d)
{
cxAssert(m_page);
cxAssert(0 <= m_page->m_t1 && m_page->m_t1 < m_page->m_t2 && m_page->m_t2 <= pageSize);
cxAssert(m_page->m_t1 <= m_index && m_index <= m_page->m_t2);
Page* p = m_page;
ssize_t i = m_index - m_page->m_t1 + d;
ssize_t oi = m_overallIndex + d;
cxAssert(oi >= 0);
if (d > 0)
{
while(1)
{
cxAssert(p);
cxAssert(i >= 0);
ssize_t s = p->size();
if (i < s || p->next_ == nullptr)
{
cxAssert(i <= s);
return IteratorPolicy(p,p->m_t1+i,oi);
}
i -= s;
p = p->next_;
}
}
else
{
while(1)
{
cxAssert(p);
ssize_t s = p->size();
cxAssert(i <= s);
if (i >= 0)
{
return IteratorPolicy(p,p->m_t1+i,oi);
}
i += s;
p = p->prev_;
}
}
}
else
{
return *this;
}
}
private:
/*
There are three cases
Case m_page m_index
-----------------------------------------------------------------------
1. queue is empty nullptr 0
2. queue non-empty last_ last_->m_count
iterator at end()
3. queue non-empty page with index position
iterator dereferencable element of element
Note that end() is represented so that --end() can be implemented.
*/
Page* m_page;
ssize_t m_index; // Index of element within the page
ssize_t m_overallIndex; // Index position within the overall xdeque
friend class xdeque;
};
typedef make_iterator<IteratorPolicy> iterator;
iterator begin() { return iterator(IteratorPolicy(first_,first_ ? first_->m_t1 : -1,0)); }
iterator end() { return iterator(last_ ? IteratorPolicy(last_,last_->m_t2,size_) : IteratorPolicy(nullptr,-1,0)); }
typedef make_const_iterator<IteratorPolicy> const_iterator;
const_iterator begin() const { return const_cast<xdeque*>(this)->begin(); }
const_iterator end() const { return const_cast<xdeque*>(this)->end(); }
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
typedef std::reverse_iterator<iterator> reverse_iterator;
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
/////////////// compare //////////////////
// Returns -1,0,1 for lexicographic compare
int compare(const xdeque& r) const
{
return LexicographicalCompareX(begin(), end(), r.begin(), r.end());
}
int compare(const T* p, ssize_t pn) const
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return LexicographicalCompareX(begin(), end(), p, p+pn);
}
int compare(ssize_t i, ssize_t n, const xdeque& r) const
{
cxAssert(0 <= i && 0 <= n && i+n <= size());
return LexicographicalCompareX(begin()+i, begin()+i+n, r.begin(), r.end());
}
int compare(ssize_t i, ssize_t n, const xdeque& r,ssize_t ri, ssize_t rn) const
{
cxAssert(0 <= i && 0 <= n && i+n <= size());
cxAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
return LexicographicalCompareX(begin()+i, begin()+i+n, r.begin()+ri, r.begin()+ri+rn);
}
int compare(ssize_t i, ssize_t n, const T* p, ssize_t pn) const
{
cxAssert(0 <= i && 0 <= n && i+n <= size());
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return LexicographicalCompareX(begin()+i, begin()+i+n, p, p+pn);
}
bool _Eq(const xdeque& r) const
{
return size() == r.size() && IsEqual(begin(), end(), r.begin());
}
bool _Lt(const xdeque& r) const
{
return compare(r) < 0;
}
/////////////// assign //////////////////
void assign(const xdeque& r)
{
assign(r.begin(),r.end());
}
void assign(const xdeque& r,ssize_t ri, ssize_t rn)
{
cxAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
assign(r.begin()+ri, r.begin()+ri+rn);
}
void assign(const T* p, ssize_t pn)
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
assign(p, p+pn);
}
void assign(ssize_t count, const T& x)
{
clear();
push_back(count,x);
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
void assign(It r1, It r2)
{
clear();
push_back(r1,r2);
}
/////////////// push_back //////////////////
void push_back(const T& t)
{
if (last_)
{
cxAssert(first_);
cxAssert(first_->prev_ == nullptr);
cxAssert(last_->next_ == nullptr);
// Allocate a new last page if necessary
if (last_->m_t2 == pageSize)
{
// Need to allocate a new page
Page* p = m_allocator.New();
p->m_t1 = p->m_t2 = 0;
last_->next_ = p;
p->prev_ = last_;
cxAssert(p->next_ == nullptr);
last_ = p;
}
}
else
{
// Allocate the first page
first_ = last_ = m_allocator.New();
last_->m_t1 = last_->m_t2 = 0;
cxAssert(last_->prev_ == nullptr);
cxAssert(last_->next_ == nullptr);
}
// Insert the element into the last page
last_->m_buffer[last_->m_t2++] = t;
++size_;
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
}
void push_back(const T* p, ssize_t pn)
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
iterator i = InsertSpace(end(),pn);
const T* pend = p + pn;
while(p != pend)
{
*i++ = *p++;
}
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
}
void push_back(ssize_t count,const T& t)
{
cxAssert(0 <= count);
iterator i = InsertSpace(end(),count);
assign_range(i,count,t);
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
}
// Inserts the range [i1,i2) into this xdeque
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
void push_back(It i1, It i2)
{
iterator i = InsertSpace(end(),i2-i1);
assign_it_range(i,i1,i2);
/*
while(i1 != i2)
{
*i++ = *i1++;
}
*/
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
void push_back(ssize_t count,It r1, It r2)
{
// todo : inefficient
cxAssert(0 <= count);
for (ssize_t c=0 ; c < count ; ++c)
{
push_back(r1,r2);
}
}
void push_back(const xdeque& r)
{
push_back(r.begin(), r.end());
}
// All elements of other are appended to 'this' and other is cleared.
// This is done very efficiently without any need to copy elements (even with memcpy)
// It is only necessary to merge the linked list of pages.
void move_back(xdeque& other)
{
if (other.size_ != 0)
{
cxAssert(other.first_);
cxAssert(other.first_->prev_ == nullptr);
cxAssert(other.last_);
cxAssert(other.last_->next_ == nullptr);
if (last_)
{
cxAssert(last_->next_ == nullptr);
cxAssert(first_);
cxAssert(first_->prev_ == nullptr);
last_->next_ = other.first_;
other.first_->prev_ = last_;
}
else
{
first_ = other.first_;
cxAssert(size_ == 0);
}
last_ = other.last_;
size_ += other.size_;
other.first_ = other.last_ = nullptr;
other.size_ = 0;
}
}
/////////////// push_front //////////////////
void push_front(const T& x)
{
/*
todo: This can be made much more efficient by introducing the concept of a
range [m_i1,m_i2) within a page's m_buffer that is filled with valued.
So push_front/pop_front can manipulate m_i1, whereas push_back/pop_back
manipulate m_i2.
*/
if (first_)
{
cxAssert(last_);
cxAssert(first_->prev_ == nullptr);
cxAssert(last_->next_ == nullptr);
// Allocate a new first page if necessary
if (first_->m_t1 == 0)
{
// Need to allocate a new page
Page* p = m_allocator.New();
p->m_t1 = p->m_t2 = pageSize;
first_->prev_ = p;
cxAssert(p->prev_ == nullptr);
p->next_ = first_;
first_ = p;
}
}
else
{
// Allocate the first page
first_ = last_ = m_allocator.New();
first_->m_t1 = first_->m_t2 = pageSize;
cxAssert(first_->prev_ == nullptr);
cxAssert(first_->next_ == nullptr);
}
// Insert the element into the last page
first_->m_buffer[--first_->m_t1] = x;
++size_;
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
void push_front(It r1, It r2)
{
// todo : inefficient
insert( begin(),r1,r2);
}
/////////////// += //////////////////
xdeque& operator+=(const xdeque& r)
{
push_back(r.begin(), r.end());
return *this;
}
xdeque& operator+=(const T& x)
{
push_back(x);
return *this;
}
const xdeque operator+(const xdeque& r) const
{
xdeque z(*this);
z.push_back(r);
return z;
}
const xdeque operator+(const T& x) const
{
xdeque z(*this);
z.push_back(x);
return z;
}
/////////////// *= //////////////////
xdeque& operator*=(ssize_t count)
{
cxAssert(0 <= count);
if (count == 0)
{
clear();
}
else
{
// This works because push_back doesn't invalidate existing iterators
push_back(count-1,begin(),end());
}
return *this;
}
/////////////// append //////////////////
xdeque& append(const xdeque& r)
{
push_back(r);
return *this;
}
xdeque& append(const xdeque& r,ssize_t ri, ssize_t rn)
{
cxAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
push_back(r.begin()+ri, r.begin()+ri+rn);
return *this;
}
xdeque& append(const T* p, ssize_t pn)
{
push_back(p, p+pn);
return *this;
}
xdeque& append(ssize_t count, const T& x)
{
cxAssert(0 <= count);
push_back(count,x);
return *this;
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
xdeque& append(It r1, It r2)
{
push_back(r1,r2);
return *this;
}
/////////////// move //////////////////
// Efficiently in-place moves n elements starting at position s to position d. s,d are zero
// based index positions. s is given in pre-insertion coordinates and d is in
// post-extraction coordinates.
//
// Eg 1 initially have '0123456789'. move(3,2,1) moves '34' to pos 1 to get '0341256789'
// Eg 2 initially have '0123456789'. move(4,3,5) moves '456' to pos 5 to get '0123745689'
//
// Constraints : 0 <= n
// 0 <= s
// s+n <= size()
// 0 <= d
// d+n <= size()
void move(ssize_t d, ssize_t s, ssize_t n)
{
// todo
cxAssert(0);
//m_buffer.move(d*sizeof(T), s*sizeof(T), n*sizeof(T));
}
/////////////// insert //////////////////
/*
// 2 args
void insert(ssize_t i,const xdeque& r) <-- STL string
void insert(ssize_t i, const T& x)
iterator insert(iterator it, const T& x) <-- STL string, vector
// 3 args
void insert(ssize_t i,const T* p, ssize_t pn) <-- STL string
void insert(ssize_t i, ssize_t count, const T& x) <-- STL string
template<typename It> void insert(ssize_t i,It r1, It r2)
template<typename It> iterator insert(iterator it,It r1, It r2) <-- STL string, vector ***
iterator insert(iterator i, ssize_t count, const T& x) <-- STL string, vector ***
// 4 args
void insert(ssize_t i,const xdeque& r, ssize_t ri, ssize_t rn) <-- STL string
-----------------------------------------
// STL vector
iterator insert ( iterator position, const T& x );
void insert ( iterator position, size_type n, const T& x );
template <typename InputIterator> void insert ( iterator position, InputIterator first, InputIterator last );
----------------------
// STL string
string& insert ( size_t pos1, const string& str );
iterator insert ( iterator p, char c );
---------- string& insert ( size_t pos1, const char* s );
string& insert ( size_t pos1, const char* s, size_t n);
string& insert ( size_t pos1, size_t n, char c );
void insert ( iterator p, size_t n, char c );
template<typename InputIterator> void insert ( iterator p, InputIterator first, InputIterator last );
string& insert ( size_t pos1, const string& str, size_t pos2, size_t n );
*/
// Insert range [r1,r2) at position i
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
void insert(ssize_t i,It r1, It r2)
{
cxAssert(0 <= i && i <= size());
insert(begin()+i,r1,r2);
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
iterator insert(iterator it,It r1, It r2)
{
if (ssize_t n = r2-r1)
{
it = InsertSpace(it,n);
iterator i = it;
do
{
*i++ = *r1++;
} while(r1 != r2);
}
#if CEDA_VALIDATE_XDEQUE
ValidateIterator(it);
Validate();
#endif
return it;
}
void insert(ssize_t i,const xdeque& r)
{
insert(i,r.begin(),r.end());
}
void insert(ssize_t i,const xdeque& r, ssize_t ri, ssize_t rn)
{
cxAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
insert(i, r.begin()+ri, r.begin()+ri+rn);
}
void insert(ssize_t i,const T* p, ssize_t pn)
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
insert(i, p, p+pn);
}
void insert(ssize_t i, const T& x)
{
cxAssert(0 <= i && i <= size());
insert(begin()+i,x);
}
iterator insert(iterator it, const T& x)
{
cxAssert(0 <= it.m_overallIndex && it.m_overallIndex <= size_);
Page* p = it.m_page;
ssize_t i = it.m_index;
if (p)
{
cxAssert(0 <= p->m_t1 && p->m_t1 < p->m_t2 && p->m_t2 <= pageSize);
cxAssert(p->m_t1 <= i && i <= p->m_t2);
if (i == p->m_t1)
{
if (i > 0)
{
it.m_index = p->m_t1 = --i;
p->m_buffer[i] = x;
}
else
{
// Insert new page to the left of p
p = InsertPage(p);
p->m_t1 = pageSize-1;
p->m_t2 = pageSize;
p->m_buffer[pageSize-1] = x;
it.m_page = p;
it.m_index = pageSize-1;
}
}
else if (i == p->m_t2)
{
if (i < pageSize)
{
p->m_buffer[i] = x;
++p->m_t2;
}
else
{
// Insert new page to the right of p
p = InsertPage(p->next_);
p->m_t1 = 0;
p->m_t2 = 1;
p->m_buffer[0] = x;
it.m_page = p;
it.m_index = 0;
}
}
else if (p->size() < pageSize)
{
// Insertion can be done on this page
it.m_index = p->InsertInPage(i,x);
}
else
{
cxAssert(p->m_t1 == 0);
cxAssert(p->m_t2 == pageSize);
cxAssert(i > 0);
cxAssert(i < pageSize);
// Split at i. Element is guaranteed to fit at i
SplitPage(p,i);
cxAssert(p->m_t2 == i);
cxAssert(p->m_t2 < pageSize);
p->m_buffer[p->m_t2++] = x;
}
}
else
{
cxAssert(i == -1);
cxAssert(it.m_overallIndex == 0);
cxAssert(size_ == 0);
cxAssert(first_ == nullptr);
cxAssert(last_ == nullptr);
first_ = last_ = m_allocator.New();
cxAssert(first_->prev_ == nullptr);
cxAssert(first_->next_ == nullptr);
const ssize_t index = pageSize/2;
last_->m_t1 = index;
last_->m_t2 = index + 1;
last_->m_buffer[index] = x;
it.m_page = last_;
it.m_index = index;
}
++size_;
#if CEDA_VALIDATE_XDEQUE
ValidateIterator(it);
Validate();
#endif
return it;
}
void insert(ssize_t i, ssize_t count, const T& x)
{
cxAssert(0 <= i && i <= size());
insert(begin()+i,count,x);
}
iterator insert(iterator i, ssize_t count, const T& x)
{
cxAssert(0 <= count);
i = InsertSpace(i,count);
assign_range(i, count, x);
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
return i;
}
/////////////// replace //////////////////
void replace(ssize_t i, ssize_t n, const xdeque& r)
{
erase(i,n);
insert(i,r);
}
void replace(ssize_t i,ssize_t n, const xdeque& r, ssize_t ri, ssize_t rn)
{
erase(i,n);
insert(i,r,ri,rn);
}
void replace(ssize_t i,ssize_t n, const T *p, ssize_t pn)
{
erase(i,n);
insert(i,p,pn);
}
void replace(ssize_t i,ssize_t n, ssize_t count, const T& x)
{
erase(i,n);
insert(i,count,x);
}
void replace(iterator i1, iterator i2, const xdeque& r)
{
insert(erase(i1,i2)-begin(),r);
}
void replace(iterator i1, iterator i2, const T *p,ssize_t pn)
{
insert(erase(i1,i2)-begin(),p,pn);
}
void replace(iterator i1, iterator i2,ssize_t count, const T& x)
{
insert(erase(i1,i2),count,x);
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
void replace(iterator i1, iterator i2,It r1, It r2)
{
insert(erase(i1,i2),r1,r2);
}
/////////////// erase //////////////////
iterator erase(iterator it1, iterator it2)
{
#if CEDA_VALIDATE_XDEQUE
Validate();
ValidateIterator(it1);
ValidateIterator(it2);
#endif
cxAssert(begin() <= it1 && it1 <= it2 && it2 <= end());
/*
Tracer() << "it1.m_page = " << it1.m_page
<< " it1.m_index = " << it1.m_index
<< " it1.m_overallIndex = " << it1.m_overallIndex
<< "\nit2.m_page = " << it2.m_page
<< " it2.m_index = " << it2.m_index
<< " it2.m_overallIndex = " << it2.m_overallIndex
<< '\n';
*/
if (Page* p1 = it1.m_page)
{
ssize_t n = it2-it1;
cxAssert(n >= 0);
size_ -= n;
cxAssert(size_ >= 0);
Page* p2 = it2.m_page;
cxAssert(p2);
ssize_t i1 = it1.m_index;
ssize_t i2 = it2.m_index;
cxAssert(p1->m_t1 <= i1 && i1 <= p1->m_t2);
cxAssert(p2->m_t1 <= i2 && i2 <= p2->m_t2);
if (p1 == p2)
{
// Same page
cxAssert(i1 <= i2);
it1.m_index = p1->EraseRange(i1,i2);
if (p1->size() == 0)
{
it1.m_page = ErasePage(p1);
if (it1.m_page)
{
it1.m_index = it1.m_page->m_t1;
}
else
{
it1 = end();
}
}
}
else
{
// Calculate range of pages to delete [d1,d2)
Page* d1;
Page* d2;
if (i1 > p1->m_t1)
{
p1->m_t2 = i1;
d1 = p1->next_;
}
else
{
d1 = p1;
}
if (i2 < p2->m_t2)
{
p2->EraseRange(p2->m_t1,i2);
d2 = p2;
}
else
{
d2 = p2->next_;
}
ErasePages(d1,d2);
it1.m_page = d2;
if (it1.m_page)
{
it1.m_index = it1.m_page->m_t1;
}
else
{
it1 = end();
}
}
}
else
{
cxAssert(size_ == 0);
cxAssert(first_ == nullptr);
cxAssert(last_ == nullptr);
cxAssert(it1.m_index == -1);
cxAssert(it2.m_page == nullptr);
cxAssert(it2.m_index == -1);
}
#if CEDA_VALIDATE_XDEQUE
ValidateIterator(it1);
Validate();
#endif
return it1;
}
iterator erase(iterator it)
{
#if CEDA_VALIDATE_XDEQUE
Validate();
ValidateIterator(it);
#endif
//Tracer() << "it.m_index = " << it.m_index
// << "it.m_overallIndex = " << it.m_overallIndex
// << '\n';
cxAssert(begin() <= it && it < end());
--size_;
Page* p = it.m_page;
cxAssert(p);
cxAssert(p->m_t1 <= it.m_index && it.m_index < p->m_t2);
if (p->size() == 1)
{
it.m_page = ErasePage(p);
if (it.m_page)
{
it.m_index = it.m_page->m_t1;
}
else
{
cxAssert(it.m_overallIndex == size_);
if (last_)
{
cxAssert(size_ > 0);
it.m_page = last_;
it.m_index = last_->m_t2;
}
else
{
cxAssert(size_ == 0);
it.m_index = -1;
}
}
}
else
{
if (it.m_index == p->m_t1)
{
p->m_t1 = ++it.m_index;
}
else if (it.m_index + 1 == p->m_t2)
{
p->m_t2 = it.m_index;
if (p->next_)
{
it.m_page = p->next_;
it.m_index = p->next_->m_t1;
}
}
else
{
// Move [it.m_index+1,p->m_t2) down to position it.m_index.
//Tracer() << "Here\n";
p->MoveDown(it.m_index,it.m_index+1,p->m_t2);
--p->m_t2;
}
}
#if CEDA_VALIDATE_XDEQUE
ValidateIterator(it);
Validate();
#endif
return it;
}
void erase()
{
Page* p = first_;
while(p)
{
Page* n = p->next_;
m_allocator.Delete(p);
p = n;
}
first_ = last_ = nullptr;
size_ = 0;
}
void erase(ssize_t i, ssize_t n)
{
cxAssert(0 <= i && 0 <= n && i+n <= size());
erase(begin()+i, begin()+i+n);
}
void erase_range(ssize_t i1, ssize_t i2)
{
cxAssert(0 <= i1 && i1 <= i2 && i2 <= size());
erase(begin()+i1, begin()+i2);
}
void erase_element(ssize_t i)
{
cxAssert(0 <= i && i < size());
erase(begin()+i);
}
void clear()
{
erase();
}
// Specialised version which doesn't delete the first page.
void clear2()
{
if (first_)
{
Page* p = first_->next_;
while(p)
{
Page* n = p->next_;
m_allocator.Delete(p);
p = n;
}
cxAssert(first_->prev_ == nullptr);
first_->m_t1 = pageSize/2;
first_->m_t2 = pageSize/2;
first_->next_ = nullptr;
last_ = first_;
size_ = 0;
}
else
{
cxAssert(last_ == nullptr);
cxAssert(size_ == 0);
}
}
// Must only be called if queue is non-empty.
void pop_front()
{
cxAssert(first_);
cxAssert(size_ > 0);
cxAssert(first_->size() > 0);
--size_;
if (++first_->m_t1 == first_->m_t2)
{
Page* p = first_->next_;
m_allocator.Delete(first_);
first_ = p;
if (first_)
{
cxAssert(first_->size() > 0);
first_->prev_ = nullptr;
}
else
{
last_ = nullptr;
cxAssert(size_ == 0);
}
}
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
}
// Must only be called if queue is non-empty.
void pop_back()
{
cxAssert(last_);
cxAssert(size_ > 0);
cxAssert(last_->size() > 0);
--size_;
if (--last_->m_t2 == last_->m_t1)
{
Page* p = last_->prev_;
m_allocator.Delete(last_);
last_ = p;
if (last_)
{
cxAssert(last_->size() > 0);
last_->next_ = nullptr;
}
else
{
first_ = nullptr;
cxAssert(size_ == 0);
}
}
#if CEDA_VALIDATE_XDEQUE
Validate();
#endif
}
/*
bool remove(const T& t)
{
Page* p = first_;
while(p)
{
T* i = p->m_buffer;
T* iend = i + p->m_count;
while (i != iend)
{
if (*i == t)
{
// Remove element, assuming the elements in the array are relocatable
// --------------xxx-------------
// ^ ^ ^
// i i+1 iend
void* dst = i;
const void* src = i+1;
ssize_t count = (iend-(i+1)) * sizeof(T);
cxAssert(count >= 0);
memmove(dst,src,count);
--p->m_count;
return true;
}
++i;
}
p = p->next_;
}
return false;
}
*/
// Find and erase all elements equal to x. Returns number erased
ssize_t FindAndErase(const T& x)
{
ssize_t count = 0;
for (ssize_t i=size()-1 ; i >= 0 ; --i)
{
if ((*this)[i] == x)
{
++count;
erase_element(i);
}
}
return count;
}
/////////////// prefix //////////////////
// Returns true if [r1,r2) appears as a substring at offset of *this
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
bool contains(It r1, It r2, ssize_t offset = 0) const
{
cxAssert(0 <= offset && offset <= size());
return IsPrefix(begin() + offset, end(), r1,r2);
}
/////////////// find //////////////////
/*
bool find(const T& t) const
{
const Page* p = first_;
while(p)
{
const T* i = p->m_buffer;
const T* iend = i + p->m_count;
while (i != iend)
{
if (*i == t) return true;
++i;
}
p = p->next_;
}
return false;
}
*/
enum { npos = -1 };
// Search forwards within *this, beginning at offset, for the first element equal to c.
ssize_t find(const T& c, ssize_t offset = 0) const
{
cxAssert(0 <= offset && offset <= size());
for (ssize_t i=offset ; i < size() ; ++i)
{
if ((*this)[i] == c) return i;
}
return npos;
}
// Search forwards within *this, beginning at offset, for the first subsequence that
// equals the sequence [r1,r2)
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
ssize_t find(It r1, It r2, ssize_t offset = 0) const
{
cxAssert(0 <= offset && offset <= size());
// YUK
// Needed for compatibility with the STL
if (r1 == r2) return offset;
const_iterator i = FindFirstSubSequence(begin()+offset,end(),r1,r2);
return i == end() ? npos : i-begin();
/*
const_iterator x1 = begin()+offset;
const_iterator x2 = end();
for(;;)
{
if (IsPrefix(x1,x2,r1,r2))
{
return x1-begin();
}
if (x1 == x2)
{
return npos;
}
++x1;
}
*/
/*
The above code returns success for finding an empty string within an empty string
whereas the code below returns failure.
It is unclear what the answer should be. The Microsoft STL returns success
const_iterator i = FindFirstSubSequence(begin()+offset,end(),r1,r2);
return i == end() ? npos : i-begin();
*/
}
// Search forwards within *this, beginning at offset, for the first subsequence that
// equals s
ssize_t find(const xdeque& r,ssize_t offset = 0) const
{
return find(r.begin(), r.end(), offset);
}
// Searches forwards within *this, beginning at offset, for the first subsequence that
// equals the sequence [p,p+pn)
ssize_t find(const T* p, ssize_t offset, ssize_t pn) const
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return find(p, p+pn, offset);
}
/////////////// rfind //////////////////
// Search backwards within *this, beginning at offset, for the first element equal to c.
ssize_t rfind(const T& c, ssize_t offset = npos) const
{
cxAssert(offset == npos || (0 <= offset && offset < size()));
for (ssize_t i = (offset == npos) ? size()-1 : offset ; i != -1 ; --i)
{
if ((*this)[i] == c) return i;
}
return npos;
}
// Search backwards within *this, beginning at offset, for the first subsequence that
// equals the sequence [r1,r2)
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
ssize_t rfind(It r1, It r2, ssize_t offset = npos) const
{
cxAssert(offset == npos || (0 <= offset && offset < size()));
// YUK
// Needed for compatibility with the STL
if (r1 == r2) return (offset == npos) ? size() : offset;
for (ssize_t i = (offset == npos) ? size()-1 : offset ; i != -1 ; --i)
{
if (contains(r1,r2,i)) return i;
}
return npos;
}
// Search backwards within *this, beginning at offset, for the first subsequence that
// equals s
ssize_t rfind(const xdeque& r,ssize_t offset = npos) const
{
return rfind(r.begin(), r.end(), offset);
}
// Search backwards within *this, beginning at offset, for the first subsequence that
// equals the sequence [p,p+pn)
ssize_t rfind(const T* p, ssize_t offset, ssize_t pn) const
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return rfind(p, p+pn, offset);
}
/////////////// find_first_of //////////////////
// Search forwards within *this, beginning at offset, for the first element equal to c.
ssize_t find_first_of(const T& c, ssize_t offset = 0) const
{
return find(c,offset);
}
// Search forwards within *this, beginning at offset, for the first element that is equal
// to any element within [r1,r2).
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
ssize_t find_first_of(It r1, It r2, ssize_t offset = 0) const
{
cxAssert(0 <= offset && offset <= size());
const_iterator i = FindFirstOf(begin()+offset,end(),r1,r2);
return i == end() ? npos : i-begin();
}
// Search forwards within *this, beginning at offset, for the first element that is equal
// to any element within r.
ssize_t find_first_of(const xdeque& r, ssize_t offset = 0)
{
return find_first_of(r.begin(), r.end(), offset);
}
// Search forwards within *this, beginning at offset, for the first element that is equal
// to any element within [p,p+pn).
ssize_t find_first_of(const T* p, ssize_t offset, ssize_t pn) const
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return find_first_of(p, p+pn, offset);
}
/////////////// find_first_not_of //////////////////
// Search forwards within *this, beginning at offset, for the first element not equal to c.
ssize_t find_first_not_of(const T& c, ssize_t offset = 0) const
{
cxAssert(0 <= offset && offset <= size());
for (ssize_t i=offset ; i < size() ; ++i)
{
if ((*this)[i] != c) return i;
}
return npos;
}
// Search forwards within *this, beginning at offset, for the first element that is not equal
// to any element within [r1,r2).
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
ssize_t find_first_not_of(It r1, It r2, ssize_t offset = 0) const
{
cxAssert(0 <= offset && offset <= size());
const_iterator i = FindFirstNotOf(begin()+offset,end(),r1,r2);
return i == end() ? npos : i-begin();
}
// Search forwards within *this, beginning at offset, for the first element that is not equal
// to any element within r.
ssize_t find_first_not_of(const xdeque& r, ssize_t offset = 0)
{
return find_first_not_of(r.begin(), r.end(), offset);
}
// Search forwards within *this, beginning at offset, for the first element that is not equal
// to any element within [p,p+pn).
ssize_t find_first_not_of(const T* p, ssize_t offset, ssize_t pn) const
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return find_first_not_of(p, p+pn, offset);
}
/////////////// find_last_of //////////////////
// Equivalent to rfind(c,offset)
ssize_t find_last_of(const T& c, ssize_t offset = npos) const
{
return rfind(c,offset);
}
// Search backwards within *this, beginning at offset, for the first element equal
// to any element within r.
ssize_t find_last_of(const xdeque& r, ssize_t offset = npos) const
{
return find_last_of(r.begin(), r.end(), offset);
}
// Search backwards within *this, beginning at offset, for the first element equal
// to any element within [r1,r2).
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
ssize_t find_last_of(It r1, It r2, ssize_t offset = npos) const
{
cxAssert(offset == npos || (0 <= offset && offset < size()));
for (ssize_t i = (offset == npos) ? size()-1 : offset ; i != -1 ; --i)
{
if (ceda::Find(r1,r2,(*this)[i]) != r2) return i;
}
return npos;
}
// Search backward within *this, beginning at offset, for the first element equal
// to any element within [p,p+pn).
ssize_t find_last_of(const T* p, ssize_t offset, ssize_t pn) const
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return find_last_of(p, p+pn, offset);
}
/////////////// find_last_not_of //////////////////
// Search backward within *this, beginning at offset, for the first element not equal
// to c.
ssize_t find_last_not_of(const T& c, ssize_t offset = npos) const
{
cxAssert(offset == npos || (0 <= offset && offset < size()));
for (ssize_t i = (offset == npos) ? size()-1 : offset ; i != -1 ; --i)
{
if ((*this)[i] != c) return i;
}
return npos;
}
// Search backward within *this, beginning at offset, for the first element not equal
// to any element within [r1,r2).
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
ssize_t find_last_not_of(It r1, It r2, ssize_t offset = npos) const
{
cxAssert(offset == npos || (0 <= offset && offset < size()));
for (ssize_t i = (offset == npos) ? size()-1 : offset ; i != -1 ; --i)
{
if (ceda::Find(r1,r2,(*this)[i]) == r2) return i;
}
return npos;
}
// Search backward within *this, beginning at offset, for the first element not equal
// to any element within r.
ssize_t find_last_not_of(const xdeque& r, ssize_t offset = npos) const
{
return find_last_not_of(r.begin(), r.end(), offset);
}
// Search backward within *this, beginning at offset, for the first element not equal
// to any element within [p,p+pn).
ssize_t find_last_not_of(const T* p, ssize_t offset, ssize_t pn) const
{
cxAssert(pn == 0 || (pn > 0 && p != nullptr));
return find_last_not_of(p, p+pn, offset);
}
/////////////// substr //////////////////
xdeque substr(ssize_t offset = 0, ssize_t count = npos) const
{
cxAssert(0 <= offset && offset <= size());
cxAssert(count == npos || (0 <= count && offset+count <= size()));
return xdeque(begin()+offset, (count == npos) ? end() : begin() + offset + count);
}
private:
// Insert pages for n elements to the left of p. Returns a pointer to the left-most
// created page.
// If p == nullptr then insert pages at the end
// todo: there are actually variations of this function depending on how we want to
// distribute partially full pages. The two important cases are where we make space on
// the left or on the right.
Page* InsertPagesForElements(Page* p, ssize_t n)
{
cxAssert(n >= 0);
// Insert full pages
ssize_t numFullPages = n / pageSize;
for (ssize_t c = 0 ; c < numFullPages ; ++c)
{
p = InsertPage(p);
p->m_t1 = 0;
p->m_t2 = pageSize;
}
// Insert another partially full page if there is a remainder
ssize_t remain = n - numFullPages * pageSize;
cxAssert(0 <= remain && remain < pageSize);
if (remain)
{
p = InsertPage(p);
p->m_t1 = 0;
p->m_t2 = remain;
}
return p;
}
// Insert n arbitrary elements at 'it'
//
// p
// [ [ ) )
// 0 t1 | t2 pageSize
// i
iterator InsertSpace(iterator it,ssize_t n)
{
#if CEDA_VALIDATE_XDEQUE
Validate();
ValidateIterator(it);
#endif
/*
Tracer() << "it.m_page = " << it.m_page
<< " it.m_index = " << it.m_index
<< " n = " << n
<< '\n';
*/
cxAssert(0 <= it.m_overallIndex && it.m_overallIndex <= size_);
cxAssert(0 <= n);
if (n > 0)
{
Page* p = it.m_page;
ssize_t i = it.m_index;
if (p)
{
//Tracer() << "prev = " << p->prev_ << " next = " << p->next_ << '\n';
//Tracer() << "t1 = " << p->m_t1 << " t2 = " << p->m_t2 << " n = " << n << " i = " << i << '\n';
cxAssert(p->size() > 0);
#if CEDA_VALIDATE_XDEQUE
p->Validate();
#endif
cxAssert(p->m_t1 <= i && i <= p->m_t2);
if (n <= p->m_t1)
{
//Tracer() << "move down\n";
// Shift left section [m_t1,i) downwards by n
p->MoveDown(p->m_t1-n, p->m_t1, i);
p->m_t1 = p->m_t1-n;
it.m_index = i-n;
}
else if (n <= pageSize-p->m_t2)
{
//Tracer() << "move up\n";
// Shift right section [i,m_t2) upwards by n
p->MoveUp(p->m_t2+n, i, p->m_t2);
p->m_t2 = p->m_t2+n;
}
else
{
// Page is too full. We choose to split at position i.
if (i == p->m_t1)
{
//Tracer() << "ins left\n";
// Insert new page to the left of p
p = InsertPagesForElements(p,n);
cxAssert(p);
cxAssert(p->m_t1 == 0);
it.m_page = p;
it.m_index = 0;
}
else if (i == p->m_t2)
{
//Tracer() << "ins right\n";
// Insert new page to the right of p
p = InsertPagesForElements(p->next_,n);
cxAssert(p);
cxAssert(p->m_t1 == 0);
it.m_page = p;
it.m_index = 0;
}
else
{
//Tracer() << "split\n";
// todo : not optimal use of pages
// Split at i.
p = SplitPage(p,i);
p = InsertPagesForElements(p,n);
cxAssert(p);
cxAssert(p->m_t1 == 0);
it.m_page = p;
it.m_index = 0;
}
}
}
else
{
cxAssert(i == -1);
cxAssert(it.m_overallIndex == 0);
cxAssert(size_ == 0);
cxAssert(first_ == nullptr);
cxAssert(last_ == nullptr);
InsertPagesForElements(nullptr,n);
it.m_page = first_;
it.m_index = first_->m_t1;
}
size_ += n;
}
#if CEDA_VALIDATE_XDEQUE
Validate();
ValidateIterator(it);
#endif
return it;
}
// assign [i,i+count) the value t.
void assign_range(iterator i, ssize_t count,const T& t)
{
cxAssert(0 <= count);
/*
while(count > 0)
{
*i++ = t;
--count;
}
*/
if (count > 0)
{
Page* p = i.m_page;
ssize_t i1 = i.m_index;
while(1)
{
cxAssert(p);
ssize_t avail = p->m_t2 - i1;
ssize_t nc = avail < count ? avail : count;
p_create(p->m_buffer+i1, p->m_buffer+i1+nc, t); // todo : should be p_assign
count -= nc;
if (count == 0) return;
p = p->next_;
cxAssert(p);
i1 = p->m_t1;
}
}
}
// assign [i,i+count) from [buf, buf+count)
void assign_range(iterator i, T* buf, ssize_t count)
{
if (count > 0)
{
Page* p = i.m_page;
ssize_t i1 = i.m_index;
while(1)
{
cxAssert(p);
ssize_t avail = p->m_t2 - i1;
ssize_t nc = avail < count ? avail : count;
p_copy(p->m_buffer+i1, buf, nc);
buf += nc;
count -= nc;
if (count == 0) return;
p = p->next_;
cxAssert(p);
i1 = p->m_t1;
}
}
}
template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
void assign_it_range(iterator i, It i1, It i2)
{
/*
while(i1 != i2)
{
*i++ = *i1++;
}
*/
ssize_t count = i2-i1;
if (count > 0)
{
Page* p = i.m_page;
ssize_t t1 = i.m_index;
while(1)
{
cxAssert(p);
ssize_t avail = p->m_t2 - t1;
ssize_t nc = avail < count ? avail : count;
p_copy(p->m_buffer+t1, i1, i1+nc);
i1 = i1+nc;
count -= nc;
if (count == 0)
{
cxAssert(i1 == i2);
return;
}
p = p->next_;
cxAssert(p);
t1 = p->m_t1;
}
}
}
#if CEDA_VALIDATE_XDEQUE
void ValidateIterator(iterator i)
{
iterator j = begin();
while(j != i)
{
++j;
}
cxAssert(j.m_overallIndex == i.m_overallIndex);
cxAssert(j.m_page == i.m_page);
cxAssert(j.m_index == i.m_index);
}
#endif
};
template<typename T, ssize_t pageSize> inline bool operator==(const xdeque<T,pageSize>& x, const xdeque<T,pageSize>& y) { return x._Eq(y); }
template<typename T, ssize_t pageSize> inline bool operator!=(const xdeque<T,pageSize>& x, const xdeque<T,pageSize>& y) { return !(x == y); }
template<typename T, ssize_t pageSize> inline bool operator<(const xdeque<T,pageSize>& x, const xdeque<T,pageSize>& y) { return x._Lt(y); }
template<typename T, ssize_t pageSize> inline bool operator>(const xdeque<T,pageSize>& x, const xdeque<T,pageSize>& y) { return y < x; }
template<typename T, ssize_t pageSize> inline bool operator<=(const xdeque<T,pageSize>& x, const xdeque<T,pageSize>& y) { return !(y < x); }
template<typename T, ssize_t pageSize> inline bool operator>=(const xdeque<T,pageSize>& x, const xdeque<T,pageSize>& y) { return !(x < y); }
template <typename T, ssize_t pageSize>
xdeque<T>& operator<<(xdeque<T,pageSize>& v, const T& x)
{
v.push_back(x);
return v;
}
template <typename T, ssize_t pageSize>
xostream& operator<<(xostream& os, const xdeque<T,pageSize>& v)
{
os << '[';
for (typename xdeque<T,pageSize>::const_iterator p = v.begin() ; p != v.end() ; ++p)
{
if (p != v.begin()) os << ',';
os << *p;
}
os << ']';
return os;
}
} // namespace ceda
#endif // include guard