xvecarray.h

// xvecarray.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2008

#pragma once
#ifndef Ceda_cxUtils_xvecarray_H
#define Ceda_cxUtils_xvecarray_H

#include "MakeIterator.h"
#include "xvector.h"
#include <algorithm>
#include <iterator>
#include <cstddef>
#include <initializer_list>

namespace ceda
{

/*
Dynamic like an xvector, except has a fixed capacity defined at compile time.
Like an xvector it is assumed that the elements can be relocated using memmove.
*/

template <typename T, ssize_t N>
class xvecarray
{
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;

    ~xvecarray() { p_del(data(), data_end()); }

    /////////////// constructors //////////////////

    xvecarray() :
        size_(0)
    {
    }

    xvecarray(const xvecarray& r, ssize_t ri, ssize_t rn)
    {
        cxAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
        assign(r.begin()+ri, r.begin()+ri+rn);
    }

    xvecarray(const T* p, ssize_t pn) 
    { 
        cxAssert(pn == 0 || pn > 0 && p != nullptr);
        assign(p,pn); 
    }

    explicit xvecarray(ssize_t count, const T& x = T()) : size_(count)
    {
        cxAssert(0 <= count && count <= N);
        p_create(data(), data_end(), x);
    }

    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    xvecarray(It r1, It r2) { assign(r1,r2); }
    
    xvecarray(const T* r1, const T* r2)
    { 
        /*
        todo: It is possible that p_copy is fundamentally broken as far as exception safety
        is concerned.
        
        The problem is when p_copy fails part way.  This causes this xvecarray to fail
        construction so its destructor will never run.  In that case it is necessary to 
        run all the relevant destructors to avoid resource leaks
        */
        size_ = r2-r1;
        cxAssert(0 <= size_ && size_ <= N);
        p_copy(data(), r1, r2);
    }

    xvecarray(const xvecarray& r) :
        size_(r.size_)
    {
        cxAssert(size_ <= N);
        p_copy(data(), r.begin(), r.end());
    }

    xvecarray(std::initializer_list<T> r)
    {
        cxAssert(r.size() <= N);
        p_copy(data(), r.begin(), r.end());
    }

    xvecarray& operator=(xvecarray rhs)
    { 
        swap(rhs);        // must be no throw 
        return *this; 
    } 
    
    void swap(xvecarray& rhs)
    {
        using std::swap;
        swap(size_, rhs.size_);
        std::swap_ranges( m_buffer, m_buffer+N*sizeof(T), rhs.m_buffer ); 
    }
    
    ssize_t size() const { return size_; }
    bool empty() const { return size_ == 0; }
    static ssize_t capacity() { return N; }
    
    void reserve(ssize_t n)
    {
        cxAssert(n <= N);
    }

    void resize(ssize_t newSize, const T& x = T()) 
    { 
        cxAssert(0 <= newSize && newSize <= N);
        ssize_t oldSize = size();
        p_del(data()+newSize, data()+oldSize);         // Destruct elements if shrinking
        p_create(data()+oldSize, data()+newSize, x);   // Construct elements if growing
        size_ = newSize;
    }

    /////////////// access elements //////////////////

    const T* data() const { return reinterpret_cast<const T*>(m_buffer); }
    T* data() { return reinterpret_cast<T*>(m_buffer); }

    const T* data_end() const { return data() + size_; }
    T* data_end() { return data() + size_; }
    
    const T& operator[](ssize_t i) const
    {
        cxAssert(0 <= i && i < size());
        return * (data() + i);
    }
    T& operator[](ssize_t i)
    {
        cxAssert(0 <= i && i < size());
        return * (data() + i);
    }

    const T& front() const { cxAssert(size() > 0); return *begin(); }
    T& front() { cxAssert(size() > 0); return *begin(); }

    const T& back() const { cxAssert(size() > 0); return *(begin() + size() - 1); }
    T& back() { cxAssert(size() > 0); return *(begin() + size() - 1); }

    /////////////// forward iterators //////////////////

    class IteratorPolicy
    {
    public:
        IteratorPolicy() : m_ptr(nullptr) {}
        explicit IteratorPolicy(T* ptr) : m_ptr(ptr) {}
        IteratorPolicy(const IteratorPolicy& rhs) : m_ptr(rhs.m_ptr) {}
    
        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_ptr == rhs.m_ptr; }
        void next() { ++m_ptr; }
        void prev() { --m_ptr; }
        value_type& deref() const { return *m_ptr; }
        const value_type& const_deref() const { return *m_ptr; }

        std::ptrdiff_t operator-(const IteratorPolicy& rhs) const { return m_ptr - rhs.m_ptr; }
        IteratorPolicy operator+(std::ptrdiff_t x) const { return IteratorPolicy(m_ptr + x); }
        
        bool operator<(const IteratorPolicy& rhs) const { return m_ptr < rhs.m_ptr; }

    private:
        T* m_ptr;
    };

    typedef make_iterator<IteratorPolicy> iterator;
    iterator begin() { return iterator(IteratorPolicy(data())); }
    iterator end() { return iterator(IteratorPolicy(data_end())); }

    typedef make_const_iterator<IteratorPolicy> const_iterator;
    const_iterator begin() const { return const_cast<xvecarray*>(this)->begin(); }
    const_iterator end() const { return const_cast<xvecarray*>(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 xvecarray& 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 xvecarray& 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 xvecarray& 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 xvecarray& r) const
    {
        return size() == r.size() && IsEqual(begin(), end(), r.begin());
    }
    bool _Lt(const xvecarray& r) const
    {
        return compare(r) < 0;
    }

    /////////////// assign //////////////////

    // Assign from range [r1,r2)
    /*
    void assign(const T* r1, const T* r2)
    {
        clear();
        size_ = r2-r1;
        cxAssert(0 <= size_ && size_ <= N);
        p_copy(data(), r1, r2);
    }
    */
    void assign(const xvecarray& r) 
    { 
        assign(r.begin(),r.end());
    }
    void assign(const xvecarray& 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) 
    { 
        cxAssert(count <= N);
        clear();
        insert(end(),count,x);
    }
    
    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    void assign(It r1, It r2)
    {
        clear();
        size_ = r2-r1;
        cxAssert(0 <= size_ && size_ <= N);
        p_copy(data(), r1, r2);
    }

    /////////////// push_back //////////////////

    void push_back(const T& x)
    {
        cxAssert(size_ < N);
        new(data() + size_) T(x);
        ++size_;
    }
    
    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    void push_back(It r1, It r2)
    {
        cxAssert(r1 <= r2);
        cxAssert(size_+(r2-r1) <= N);
        p_copy(data()+size_, r1, r2);
        size_ += r2-r1;
    }

    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    void push_back(ssize_t count,It r1, It r2)
    {
        cxAssert(0 <= count);
        cxAssert(size_+count*(r2-r1) <= N);
        T* p = data() + size_;
        for (ssize_t c=0 ; c < count ; ++c) 
        {
            p_copy(p,r1,r2);
            p += (r2-r1);
        }
    }

    /////////////// push_front //////////////////

    void push_front(const T& x)
    {
        insert(0,x);
    }
    
    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    void push_front(It r1, It r2)
    {
        insert(0,r1,r2);
    }

    /////////////// += //////////////////

    xvecarray& operator+=(const xvecarray& r) 
    { 
        push_back(r.begin(), r.end()); 
        return *this; 
    }
    xvecarray& operator+=(const T& x) 
    { 
        push_back(x); 
        return *this; 
    }

    const xvecarray operator+(const xvecarray& r) const
    {
        xvecarray z(*this);
        z.append(r);
        return z;
    }

    const xvecarray operator+(const T& x) const
    {
        xvecarray z(*this);
        z.push_back(x);
        return z;
    }

    /////////////// *= //////////////////

    xvecarray& operator*=(ssize_t count) 
    { 
        cxAssert(0 <= count);
        xvecarray copy;
        copy.swap(*this);
        push_back(count,copy.begin(),copy.end());
        return *this; 
    }

    /////////////// append //////////////////

    xvecarray& append(const xvecarray& r) 
    { 
        push_back(r.begin(), r.end()); 
        return *this; 
    }
    xvecarray& append(const xvecarray& 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;
    }
    xvecarray& append(const T* p, ssize_t pn) 
    { 
        cxAssert(pn == 0 || pn > 0 && p != nullptr);
        push_back(p, p+pn);
        return *this; 
    }
    xvecarray& append(ssize_t count, const T& x) 
    { 
        cxAssert(0 <= count);
        insert(end(),count,x);
        return *this; 
    }
	
    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    xvecarray& 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)
    {
        m_buffer.move(d*sizeof(T), s*sizeof(T), n*sizeof(T));
    }
    */
    
    /////////////// insert //////////////////

    // 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());
        ssize_t n = r2-r1;
        cxAssert(size_ + n <= N);
        memmove(data()+i+n, data()+i, (size_ - i) * sizeof(T));
        size_ += n;
        p_copy(data()+i,r1,r2);
	}

    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
	void insert(iterator i,It r1, It r2)
	{
        insert(i - begin(),r1,r2);
	}
    void insert(ssize_t i,const xvecarray& r) 
    { 
        insert(i,r.begin(),r.end());
    }
   
    void insert(ssize_t i,const xvecarray& 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());
        cxAssert(size_ < N);
        
        // Move bytes to right to make room for the insertion
        memmove(data()+i+1, data()+i, (size_ - i) * sizeof(T));
        ++size_;
        new(data()+i) T(x);
    }
    iterator insert(iterator i, const T& x)
    {
        ssize_t n = i-begin();
        insert(n,x);
        return begin() + n;
    }
    void insert(ssize_t i, ssize_t count, const T& x)
    {
        cxAssert(0 <= i && i <= size());
        cxAssert(size_+count <= N);

        memmove(data()+i+count, data()+i, (size_ - i) * sizeof(T));
        size_ += count;
        p_create(data()+i,data()+i+count,x);
    }
    void insert(iterator i, ssize_t count, const T& x)
    {
        insert(i-begin(),count,x);
    }

    /////////////// replace //////////////////

	void replace(ssize_t i, ssize_t n, const xvecarray& r)
	{
	    erase(i,n);
	    insert(i,r);
	}
	void replace(ssize_t i,ssize_t n, const xvecarray& 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 xvecarray& r)
	{
        ssize_t i = i1-begin();
	    erase(i1,i2);
	    insert(i,r);
	}
	void replace(iterator i1, iterator i2, const T *p,ssize_t pn)
	{
        ssize_t i = i1-begin();
	    erase(i1,i2);
	    insert(i,p,pn);
	}
	void replace(iterator i1, iterator i2,ssize_t count, const T& x)
	{
        ssize_t i = i1-begin();
	    erase(i1,i2);
	    insert(i,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)
	{
        ssize_t i = i1-begin();
	    erase(i1,i2);
	    insert(i,r1,r2);
	}

    /////////////// erase //////////////////

    void erase(iterator i1, iterator i2)
    {
        cxAssert(begin() <= i1 && i1 <= i2 && i2 <= end());
        erase( i1-begin(), i2-i1 );
    }
    iterator erase(iterator i)
    {
        cxAssert(begin() <= i && i < end());
        ssize_t pos = i-begin();
        erase_element( pos );
        return begin() + pos;
    }
    void erase()
    { 
        p_del(data(), data_end());
        size_ = 0;
    }
    void erase(ssize_t i, ssize_t n)
    {
        cxAssert(0 <= i && 0 <= n && i+n <= size());
        p_del(data()+i,data()+i+n);
        size_ -= n;
        memmove( data()+i, data()+i+n, (size_-i)*sizeof(T) );
    }
    void erase_element(ssize_t i)
    {
        cxAssert(0 <= i && i < size());
        (data() + i)->~T();
        --size_;
        memmove( data()+i, data()+i+1, (size_-i)*sizeof(T) );
    }
    
    void clear()
    {
        erase();
    }
    void pop_front()
    { 
        cxAssert(size() > 0);
        erase_element(0);
    }
    void pop_back()
    {
        cxAssert(size() > 0);
        erase_element(size()-1);
    }

    // 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 //////////////////
    
    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 xvecarray& 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 xvecarray& 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 xvecarray& 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 xvecarray& 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 xvecarray& 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 xvecarray& 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 //////////////////

    xvecarray substr(ssize_t offset = 0, ssize_t count = npos) const
    {
        cxAssert(0 <= offset && offset <= size());
        cxAssert(count == npos || 0 <= count && offset+count <= size());
        return xvecarray(begin()+offset, (count == npos) ? end() : begin() + offset + count);
    }

private:
    // Must be in [0,N]
    ssize_t size_;
    
    octet_t m_buffer[N*sizeof(T)];
};

template<typename T,ssize_t N> inline bool operator==(const xvecarray<T,N>& x, const xvecarray<T,N>& y) { return x._Eq(y); }
template<typename T,ssize_t N> inline bool operator!=(const xvecarray<T,N>& x, const xvecarray<T,N>& y) { return !(x == y); }
template<typename T,ssize_t N> inline bool operator<(const xvecarray<T,N>& x, const xvecarray<T,N>& y) { return x._Lt(y); }
template<typename T,ssize_t N> inline bool operator>(const xvecarray<T,N>& x, const xvecarray<T,N>& y) { return y < x; }
template<typename T,ssize_t N> inline bool operator<=(const xvecarray<T,N>& x, const xvecarray<T,N>& y) { return !(y < x); }
template<typename T,ssize_t N> inline bool operator>=(const xvecarray<T,N>& x, const xvecarray<T,N>& y) { return !(x < y); }

template <typename T,ssize_t N> 
xvecarray<T,N>& operator<<(xvecarray<T,N>& v, const T& x)
{
    v.push_back(x);
    return v;
}

template <typename T,ssize_t N> 
xostream& operator<<(xostream& os, const xvecarray<T,N>& v)
{
    os << '[';
    for (typename xvecarray<T,N>::const_iterator p = v.begin() ; p != v.end() ; ++p)
    {
        if (p != v.begin()) os << ',';
        os << *p;
    }
    os << ']';
    return os;
}

} // namespace ceda

#endif // include guard