xvector.h

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

#pragma once
#ifndef Ceda_cxUtils_xvector_H
#define Ceda_cxUtils_xvector_H

#include "CedaAssert.h"
#include "VectorOfByte.h"
#include "xostream.h"
#include "MakeIterator.h"
#include "Detect.h"
#include <new>
#include <initializer_list>
#include <string.h>
#include <cstring>

// It was found that using a class to implement an iterator leads to dramatically less 
// performance, perhaps because it prevents the specialisations of p_create, p_del, p_copy.
//#define CEDA_USE_CLASS_ITERATOR

#define cxXvectorAssert(c)  cxAssert(c)
//#define cxXvectorAssert(c)

namespace ceda
{
// default construct elements in [r1,r2).
template <typename T>
inline void DefaultConstructRange(T* r1, T* r2)
{
    cxXvectorAssert(r1 <= r2);
    cxXvectorAssert(implies(r1 < r2, r1 != nullptr));

    if constexpr (std::is_scalar_v<T>)
    {
		// std::is_integral:        bool, char, char8_t, char16_t, char32_t, wchar_t, short, int, long, long long (including any signed, unsigned, and cv-qualified variants)
        // std::is_floating_point   float, double, long double, including any cv-qualified variants
        // std::is_enum
        // std::is_pointer
        // std::is_member_pointer
        // std::is_null_pointer
        
        std::memset(r1, 0, (r2-r1)*sizeof(T));
    }
    else
    {
        while(r1 != r2)
        {
            new(r1) T();
            ++r1;
        }
    }
}

// construct elements in [r1,r2) with value x.
// This function can safely be called with r1 >= r2 (it's a no-op in that case)
template <typename T>
inline void p_create(T* r1, T* r2, const T& x)
{
    // r1 < r2  =>   r1 != nullptr
    cxXvectorAssert(r1 >= r2 || r1 != nullptr);

    if constexpr (std::is_trivially_assignable_v<T,T>)
    {
        if constexpr (sizeof(T) == 1 && std::is_scalar_v<T>)
        {
	        if (r2 > r1)
	        {
		        std::memset(r1,x,r2-r1);
	        }
        }
        else
        {
            while(r1 < r2)
            {
                *r1++ = x;
            }
        }
    }
    else
    {
        while(r1 < r2)
        {
            new(r1) T(x);
            ++r1;
        }
    }
}

// Destruct elements in [r1,r2).
// This function can safely be called with r1 >= r2 (it's a no-op in that case)
template <typename T>
inline void p_del(T* r1, T* r2)
{
    // r1 < r2  =>   r1 != nullptr
    cxXvectorAssert(r1 >= r2 || r1 != nullptr);

    if constexpr (std::is_trivially_destructible_v<T>)
    {
        (void) r1;
        (void) r2;
    }
    else 
    {
        while(r1 < r2)
        {
            r1->~T();
            ++r1;
        }
    }
}

// Copy construct elements in [dst,dst+n) from elements in [src1,src2) where n = src2-src1;
template <typename T, typename It>
inline void p_copy(T* dst, It src1, It src2)
{
    cxXvectorAssert(src1 <= src2);
    if constexpr (std::is_same_v<It, const T*> && std::is_trivially_copyable_v<T>)
    {
        // src1 != src2  =>  (src1 < src2 && src1 != nullptr && dst != nullptr)
        cxXvectorAssert(src1 == src2 || (src1 < src2 && src1 != nullptr && dst != nullptr));

        std::memcpy(dst, src1, (src2-src1)*sizeof(T));
    }
    else
    {
        // src1 != src2  =>  dst != nullptr
        cxXvectorAssert(src1 == src2 || dst != nullptr);
        while(src1 != src2)
        {
            new(dst) T(*src1);
            ++dst;
            ++src1;
        }
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// xvector<T>

// Assumes that elements T are relocateable

template <typename T>
class xvector
{
public:
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    //using size_type = size_t;
    //using difference_type = ptrdiff_t;
    using size_type = ssize_t;
    using difference_type = ssize_t;

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

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

    xvector() {}

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

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

    explicit xvector(ssize_t count)
    {
        cxXvectorAssert(count >= 0);
        m_buffer.growbytes(count * sizeof(T));
        DefaultConstructRange(data(), data_end());
    }

    xvector(ssize_t count, const T& x)
    {
        cxXvectorAssert(count >= 0);
        m_buffer.growbytes(count * sizeof(T));
        p_create(data(), data_end(), x);
    }
        
    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    xvector(It r1, It r2) { assign(r1,r2); }
    
    xvector(const T* r1, const T* r2) 
    { 
        cxXvectorAssert(r1 <= r2);
        assign(r1,r2); 
    }

    xvector(const xvector& r)
    {
        assign(r.begin(), r.end());
    }

    xvector(std::initializer_list<T> r)
    {
        assign(r.begin(), r.end());
    }

    /////////////// assignment //////////////////
    
    xvector& operator=(const xvector& r)
    {
        if (this != &r) assign(r);
        return *this;
    }
    /*
    xvector& operator=(const T& x)
    {
        assign(1,x);
        return *this;
    }
    */
    
    /////////////// swap //////////////////

    void swap(xvector& r)
    {
        m_buffer.swap(r.m_buffer);    
    }

    /////////////// size //////////////////
    
    void reserve(ssize_t size) const 
    { 
        cxXvectorAssert(size >= 0);
        m_buffer.reserve(size * sizeof(T)); 
    }
    ssize_t capacity() const { return m_buffer.capacity() / sizeof(T); }

    void resize(ssize_t newSize, const T& x = T()) 
    { 
        cxXvectorAssert(newSize >= 0);
        ssize_t oldSize = size();
        p_del(data()+newSize, data()+oldSize);         // Destruct elements if shrinking
        m_buffer.resize(newSize * sizeof(T));
        p_create(data()+oldSize, data()+newSize, x);   // Construct elements if growing
    }

    bool empty() const { return m_buffer.empty(); }
    ssize_t size() const { return m_buffer.size() / sizeof(T); }
    ssize_t length() const { return m_buffer.size() / sizeof(T); }

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

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

    const T* data_end() const { return reinterpret_cast<const T*>(m_buffer.end()); }
    T* data_end() { return reinterpret_cast<T*>(m_buffer.end()); }

    const T& operator[](ssize_t i) const 
    { 
        cxXvectorAssert(0 <= i && i < size());
        return *(begin() + i);
    }
    T& operator[](ssize_t i) 
    { 
        cxXvectorAssert(0 <= i && i < size());
        return *(begin() + i); 
    }
    
    const T& front() const { cxXvectorAssert(size() > 0); return *begin(); }
    T& front() { cxXvectorAssert(size() > 0); return *begin(); }

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

    #ifdef CEDA_USE_CLASS_ITERATOR
        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(reinterpret_cast<T*>(m_buffer.begin()))); }
        iterator end() { return iterator(IteratorPolicy(reinterpret_cast<T*>(m_buffer.end()))); }

        typedef make_const_iterator<IteratorPolicy> const_iterator;
        const_iterator begin() const { return const_cast<xvector*>(this)->begin(); }
        const_iterator end() const { return const_cast<xvector*>(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()); }
    #else
        /////////////// forward iterators //////////////////

        typedef const T* const_iterator;
        const_iterator begin() const { return reinterpret_cast<const T*>(m_buffer.begin()); }
        const_iterator end() const { return reinterpret_cast<const T*>(m_buffer.end()); }

        typedef T* iterator;
        iterator begin() { return reinterpret_cast<T*>(m_buffer.begin()); }
        iterator end() { return reinterpret_cast<T*>(m_buffer.end()); }

        /////////////// reverse iterators //////////////////
        class const_reverse_iterator
        {
        public:
            explicit const_reverse_iterator(const T* _p = 0) : p(_p) {}
            
            // todo: This allow two iterators to be differenced.  Unfortunately it means
            // we have implicit conversions between reverse and forward iterators which can hide
            // programming errors.
            operator const T*() const { return p; }
            
            const T& operator*() const { cxXvectorAssert(p); return *(p-1); }
            const T* operator->() const { cxXvectorAssert(p); return p-1; }

            const_reverse_iterator& operator++() { cxXvectorAssert(p); --p; return *this; }
            const const_reverse_iterator operator++(int) { const_reverse_iterator it = *this; ++(*this); return it; }

            const_reverse_iterator& operator--() { cxXvectorAssert(p); ++p; return *this; }
            const const_reverse_iterator operator--(int) { const_reverse_iterator it = *this; --(*this); return it; }

            bool operator==(const const_reverse_iterator& rhs) const { return p == rhs.p; }
            bool operator!=(const const_reverse_iterator& rhs) const { return p != rhs.p; }
        
        protected:
            const T* p;
        };
        const_reverse_iterator rbegin() const { return const_reverse_iterator(reinterpret_cast<const T*>(m_buffer.end())); }
        const_reverse_iterator rend() const { return const_reverse_iterator(reinterpret_cast<const T*>(m_buffer.begin())); }
        
        
        // Note : there needs to be an implicit conversion from iterator to const_iterator, and
        // reverse_iterator to const_reverse_iterator.
        class reverse_iterator : public const_reverse_iterator
        {
            using const_reverse_iterator::p;
        public:
            explicit reverse_iterator(T* _p) : const_reverse_iterator(_p) {}

            operator T*() const { return (T*) p; }

            T& operator*() const { cxXvectorAssert(p); return * (T*) (p-1); }
            T* operator->() const { cxXvectorAssert(p); return (T*) (p-1); }

            reverse_iterator& operator++() { cxXvectorAssert(p); --p; return *this; }
            const reverse_iterator operator++(int) { reverse_iterator it = *this; ++(*this); return it; }

            reverse_iterator& operator--() { cxXvectorAssert(p); ++p; return *this; }
            const reverse_iterator operator--(int) { reverse_iterator it = *this; --(*this); return it; }
        };
        
        reverse_iterator rbegin() { return reverse_iterator(reinterpret_cast<T*>(m_buffer.end())); }
        reverse_iterator rend() { return reverse_iterator(reinterpret_cast<T*>(m_buffer.begin())); }
    #endif

    /////////////// compare //////////////////

	// Returns -1,0,1 for lexicographic compare
	int compare(const xvector& r) const
	{ 
	    return LexicographicalCompareX(begin(), end(), r.begin(), r.end());
	}
	int compare(const T* p, ssize_t pn) const
	{ 
	    cxXvectorAssert(pn == 0 || (pn > 0 && p != nullptr));
	    return LexicographicalCompareX(begin(), end(), p, p+pn);
	}
	int compare(ssize_t i, ssize_t n, const xvector& r) const
	{ 
	    cxXvectorAssert(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 xvector& r,ssize_t ri, ssize_t rn) const
	{ 
	    cxXvectorAssert(0 <= i && 0 <= n && i+n <= size());
	    cxXvectorAssert(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
	{ 
	    cxXvectorAssert(0 <= i && 0 <= n && i+n <= size());
	    cxXvectorAssert(pn == 0 || (pn > 0 && p != nullptr));
	    return LexicographicalCompareX(begin()+i, begin()+i+n, p, p+pn);
	}
    bool _Eq(const xvector& r) const
    {
        return size() == r.size() && IsEqual(begin(), end(), r.begin());
    }
    bool _Lt(const xvector& r) const
    {
        return compare(r) < 0;
    }

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

    // Assign from range [r1,r2)
    /*
    void assign(const T* r1, const T* r2)
    {
        cxXvectorAssert(r1 <= r2);
        clear();
        m_buffer.insertbytes(0,(r2-r1)*sizeof(T));
        p_copy(data(), r1, r2);
    }
    */
    void assign(const xvector& r) 
    { 
        assign(r.begin(),r.end());
    }
    void assign(const xvector& r,ssize_t ri, ssize_t rn)
    {
        cxXvectorAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
        assign(r.begin()+ri, r.begin()+ri+rn);
    }
    void assign(const T* p, ssize_t pn) 
    { 
        cxXvectorAssert(pn == 0 || (pn > 0 && p != nullptr));
        assign(p, p+pn); 
    }
    void assign(ssize_t count, const T& x) 
    { 
        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();
        m_buffer.insertbytes(0,(r2-r1)*sizeof(T));
        p_copy(data(), r1, r2);
    }

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

    void push_back(const T& x)
    {
        m_buffer.push_back(x);
    }

    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    void push_back(It r1, It r2)
    {
        cxAssert(r1 <= r2);
        ssize_t n = m_buffer.size();
        m_buffer.insertbytes(n, (r2-r1) * sizeof(T));
        p_copy((T*) &m_buffer[n], r1, r2);
    }

    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    void push_back(ssize_t count,It r1, It r2)
    {
        cxXvectorAssert(0 <= count);
        ssize_t n = m_buffer.size();
        m_buffer.insertbytes(n, count * (r2-r1) * sizeof(T));
        T* p = (T*) &m_buffer[n];
        for (ssize_t c=0 ; c < count ; ++c) 
        {
            p_copy(p,r1,r2);
            p += (r2-r1);
        }
    }

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

    void push_front(const T& x)
    {
        // Cast is need to avoid ambiguity when iterator = T* and ssize_t is 64 bit
        insert( (ssize_t)0,x);
    }

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

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

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

    const xvector operator+(const xvector& r) const
    {
        xvector z;
        z.reserve(size()+r.size());
        z = *this;
        z.append(r);
        return z;
    }

    const xvector operator+(const T& x) const
    {
        xvector z;
        z.reserve(size()+1);
        z = *this;
        z.push_back(x);
        return z;
    }

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

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

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

    xvector& append(const xvector& r) 
    { 
        push_back(r.begin(), r.end()); 
        return *this; 
    }
    xvector& append(const xvector& r,ssize_t ri, ssize_t rn)
    {
        cxXvectorAssert(0 <= ri && 0 <= rn && ri+rn <= r.size());
        push_back(r.begin()+ri, r.begin()+ri+rn);
        return *this;
    }
    xvector& append(const T* p, ssize_t pn) 
    { 
        cxXvectorAssert(pn == 0 || (pn > 0 && p != nullptr));
        push_back(p, p+pn);
        return *this; 
    }
    xvector& append(ssize_t count, const T& x) 
    { 
        cxXvectorAssert(0 <= count);
        insert(end(),count,x);
        return *this; 
    }
    /*
    xvector& append(const T* p1, const T* p2) 
    { 
        push_back(p1,p2);
        return *this; 
    }
    */
	
    template <class It, std::enable_if_t<is_iterator_v<It>, int> = 0>
    xvector& 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)
	{
        cxXvectorAssert(0 <= i && i <= size());
        m_buffer.insertbytes(i*sizeof(T), (r2-r1)*sizeof(T));
        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 xvector& r) 
    { 
        insert(i,r.begin(),r.end());
    }
   
    void insert(ssize_t i,const xvector& r, ssize_t ri, ssize_t rn)
    {
        cxXvectorAssert(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)
    {
        cxXvectorAssert(pn == 0 || (pn > 0 && p != nullptr));
        insert(i, p, p+pn);
    }
    void insert(ssize_t i, const T& x)
    {
        cxXvectorAssert(0 <= i && i <= size());
        m_buffer.insertbytes(i*sizeof(T), sizeof(T));
        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)
    {
        cxXvectorAssert(0 <= i && i <= size());
        m_buffer.insertbytes(i*sizeof(T),count*sizeof(T));
        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 xvector& r)
	{
	    erase(i,n);
	    insert(i,r);
	}
	void replace(ssize_t i,ssize_t n, const xvector& 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 xvector& 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)
    {
        cxXvectorAssert(begin() <= i1 && i1 <= i2 && i2 <= end());
        p_del(&*i1,&*i2);
        m_buffer.erase((unsigned char*) &*i1,(unsigned char*) &*i2);
    }
    iterator erase(iterator i)
    {
        cxXvectorAssert(begin() <= i && i < end());
        ssize_t pos = i - begin();
        (&*i)->~T();
        m_buffer.erase( (unsigned char*) &*i, (unsigned char*) &*(i+1));
        return begin() + pos;
    }
    void erase()
    { 
        p_del(data(), data_end());
        m_buffer.clear(); 
    }
    void erase(ssize_t i, ssize_t n)
    {
        cxXvectorAssert(0 <= i && 0 <= n && i+n <= size());
        erase(begin()+i, begin()+i+n);
    }
    void erase_range(ssize_t i1, ssize_t i2)
    {
        cxXvectorAssert(0 <= i1 && i1 <= i2 && i2 <= size());
        erase(begin()+i1, begin()+i2);
    }
    void erase_element(ssize_t i)
    {
        cxXvectorAssert(0 <= i && i < size());
        erase(begin()+i);
    }
    
    void clear()
    {
        erase();
    }
    void pop_front()
    { 
        cxXvectorAssert(size() > 0);
        erase_element(0);
    }
    void pop_back()
    {
        cxXvectorAssert(size() > 0);
        back().~T();
        m_buffer.pop_back(sizeof(T));
    }

    // 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;
    }

    ssize_t FindAndEraseFirst(const T& x)
    {
        for (ssize_t i=size()-1 ; i >= 0 ; --i)
        {
            if ((*this)[i] == x)
            {
                erase_element(i);
                return true;
            }
        }
        return false;
    }

    /////////////// 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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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 xvector& 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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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 xvector& 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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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 xvector& 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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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 xvector& 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
    {
        cxXvectorAssert(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 xvector& 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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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
    {
        cxXvectorAssert(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 xvector& 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
    {
        cxXvectorAssert(pn == 0 || (pn > 0 && p != nullptr));
        return find_last_not_of(p, p+pn, offset);
    }


    /////////////// substr //////////////////

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

private:
    VectorOfByte m_buffer;
};

template<typename T, std::enable_if_t<has_compare_equal<T>::value, int> = 0>
inline bool operator==(const xvector<T>& x, const xvector<T>& y) { return x._Eq(y); }

template<typename T, std::enable_if_t<has_compare_equal<T>::value, int> = 0>
inline bool operator!=(const xvector<T>& x, const xvector<T>& y) { return !(x == y); }

template<typename T, std::enable_if_t<has_compare_less<T>::value, int> = 0>
inline bool operator<(const xvector<T>& x, const xvector<T>& y) { return x._Lt(y); }

template<typename T, std::enable_if_t<has_compare_less<T>::value, int> = 0>
inline bool operator>(const xvector<T>& x, const xvector<T>& y) { return y < x; }

template<typename T, std::enable_if_t<has_compare_less<T>::value, int> = 0>
inline bool operator<=(const xvector<T>& x, const xvector<T>& y) { return !(y < x); }

template<typename T, std::enable_if_t<has_compare_less<T>::value, int> = 0>
inline bool operator>=(const xvector<T>& x, const xvector<T>& y) { return !(x < y); }

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

template <typename T, std::enable_if_t<has_xostream_insertion<T>::value, int> = 0> 
xostream& operator<<(xostream& os, const xvector<T>& v)
{
    os << '[';
    for (typename xvector<T>::const_iterator p = v.begin() ; p != v.end() ; ++p)
    {
        if (p != v.begin()) os << ',';
        os << *p;
    }
    os << ']';
    return os;
}

} // namespace ceda

#endif // include guard