VectorOfByte.h

// VectorOfByte.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2006

#pragma once
#ifndef Ceda_cxUtils_VectorOfByte_H
#define Ceda_cxUtils_VectorOfByte_H

#include "cxUtils.h"
#include "CedaAssert.h"
#include <new>
#include <wchar.h>
#include <initializer_list>
#include <string.h>

namespace ceda
{
class xostream;

///////////////////////////////////////////////////////////////////////////////////////////////////

template <typename It1, typename It2>
int LexicographicalCompareX(It1 x1, It1 x2, It2 y1, It2 y2)
{
    while (x1 != x2 && y1 != y2) 
    {
        if (*x1 < *y1) return -1;
        if (*y1 < *x1) return 1;
        ++x1; ++y1;
    }
    return (x1 == x2) ? ((y1 == y2) ? 0 : -1) : 1;
}

inline int LexicographicalCompareX(const unsigned char* x1, const unsigned char* x2, const unsigned char* y1, const unsigned char* y2)
{
    ssize_t n1 = x2-x1;
    ssize_t n2 = y2-y1;
    int result = memcmp(x1, y1, n1<n2 ? n1 : n2);
    if (result == 0)
    {
        //Upsets unit test which compares ceda and stl return values
        //return (int) (n1-n2);
        
        if (n1 < n2) return -1;
        else if (n1 == n2) return 0;
        else return 1;
    }
    else
    {
        return result;
    }
}

inline int LexicographicalCompareX(const char* x1, const char* x2, const char* y1, const char* y2)
{
    return LexicographicalCompareX(
        (const unsigned char*) x1, 
        (const unsigned char*) x2, 
        (const unsigned char*) y1, 
        (const unsigned char*) y2);
}

#ifdef _WIN32   // wchar_t is 16 bit
inline int LexicographicalCompareX(ConstString16Z x1, ConstString16Z x2, ConstString16Z y1, ConstString16Z y2)
{
    static_assert( sizeof(wchar_t) == sizeof(char16), "wchar_t is 16 bit" );
    
    ssize_t n1 = x2-x1;
    ssize_t n2 = y2-y1;
    int result = wmemcmp( (const wchar_t*) x1, (const wchar_t*) y1, n1<n2 ? n1 : n2);
    if (result == 0)
    {
        //Upsets unit test which compares ceda and stl return values
        //return (int) (n1-n2);
        
        if (n1 < n2) return -1;
        else if (n1 == n2) return 0;
        else return 1;
    }
    else
    {
        return result;
    }
}
#endif // defined(_WIN32)

template <typename It1, typename It2>
bool IsEqual(It1 x1, It1 x2, It2 y1)
{
    while (x1 != x2)
    {
        if (!(*x1 == *y1)) return false;
        ++x1; ++y1;
    }
    return true;
}

#define CEDA_USE_MEMCMP_IS_EQUAL(T) \
    inline bool IsEqual(const T* x1, const T* x2, const T* y1) \
        { return memcmp(x1,y1,(x2-x1)*sizeof(T)) == 0; }

CEDA_USE_MEMCMP_IS_EQUAL(bool)
CEDA_USE_MEMCMP_IS_EQUAL(int8)
CEDA_USE_MEMCMP_IS_EQUAL(uint8)
CEDA_USE_MEMCMP_IS_EQUAL(char8)
CEDA_USE_MEMCMP_IS_EQUAL(char16)
CEDA_USE_MEMCMP_IS_EQUAL(int16)
CEDA_USE_MEMCMP_IS_EQUAL(uint16)
CEDA_USE_MEMCMP_IS_EQUAL(int32)
CEDA_USE_MEMCMP_IS_EQUAL(uint32)
CEDA_USE_MEMCMP_IS_EQUAL(int64)
CEDA_USE_MEMCMP_IS_EQUAL(uint64)
CEDA_USE_MEMCMP_IS_EQUAL(float32)
CEDA_USE_MEMCMP_IS_EQUAL(float64)

// Returns true if [y1,y2) is a prefix of [x1,x2)
template <typename It1, typename It2>
bool IsPrefix(It1 x1, It1 x2, It2 y1, It2 y2)
{
    while (y1 != y2)
    {
        if (x1 == x2 || *x1 != *y1) return false;
        ++x1; ++y1;
    }
    return true;
}

// Returns position of [y1,y2) in [x1,x2) or x2 if not found
template <typename It1, typename It2>
It1 FindFirstSubSequence(It1 x1, It1 x2, It2 y1, It2 y2)
{
    while (x1 != x2)
    {
        if (IsPrefix(x1,x2,y1,y2)) break;
        ++x1;
    }
    return x1;
}

template <typename It, typename T>
It Find(It i1, It i2, const T& v)
{
    while (i1 != i2)
    {
        if (v == *i1) return i1;
        ++i1;
    }
    return i1;
}

// Returns position of first element in [x1,x2) that exists in [y1,y2), or x2 if not found
template <typename It1, typename It2>
It1 FindFirstOf(It1 x1, It1 x2, It2 y1, It2 y2)
{
    while (x1 != x2)
    {
        if (Find(y1,y2,*x1) != y2) return x1;
        ++x1;
    }
    return x1;
}

// Returns position of first element in [x1,x2) that doesn't exist in [y1,y2), or x2 if not
// found
template <typename It1, typename It2>
It1 FindFirstNotOf(It1 x1, It1 x2, It2 y1, It2 y2)
{
    while (x1 != x2)
    {
        if (Find(y1,y2,*x1) == y2) return x1;
        ++x1;
    }
    return x1;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
// VectorOfByte

class cxUtils_API VectorOfByte
{
public:
    VectorOfByte();
    ~VectorOfByte();
    
    typedef uint8 value_type;

    VectorOfByte(const value_type* r1, const value_type* r2);
    explicit VectorOfByte(ssize_t size, value_type x = 0);

    VectorOfByte(std::initializer_list<value_type> r) :
        m_buffer(nullptr), 
        size_(0),
        m_capacity(0) 
    {
        assign(r.begin(), r.end());
    }

    VectorOfByte(const VectorOfByte& rhs);
    VectorOfByte& operator=(const VectorOfByte& rhs);

	// Returns -1,0,1 for lexicographic compare
	int compare(const VectorOfByte& r) const;
	int compare(ssize_t i, ssize_t n, const VectorOfByte& r) const;
	int compare(ssize_t i, ssize_t n, const VectorOfByte& r,ssize_t ri, ssize_t rn) const;
	int compare(ssize_t i, ssize_t n, const value_type* p, ssize_t pn) const;

    bool operator==(const VectorOfByte& rhs) const;
    bool operator!=(const VectorOfByte& rhs) const { return !operator==(rhs); }
    bool operator<(const VectorOfByte& rhs) const { return compare(rhs) < 0; }
    bool operator<=(const VectorOfByte& rhs) const { return compare(rhs) <= 0; }
    bool operator>(const VectorOfByte& rhs) const { return compare(rhs) > 0; }
    bool operator>=(const VectorOfByte& rhs) const { return compare(rhs) >= 0; }
    
    VectorOfByte& operator+=(const VectorOfByte& rhs)
    {
        push_back(rhs.begin(), rhs.end());
        return *this;
    }

    // Assign from octet_t range [r1,r2)
    void assign(const value_type* r1, const value_type* r2);

    template <typename It> void assign(It r1, It r2)
    {
        resize(r2-r1);
        value_type* p = data();
        while(r1 != r2)
        {
            *p++ = *r1++;
        }
    }

    void clear();
    void reserve(ssize_t size) const;
    ssize_t capacity() const { return m_capacity; }
    void resize(ssize_t newSize);

    bool empty() const { return size_ == 0; }
    ssize_t size() const { return size_; }

    value_type operator[](ssize_t i) const { return m_buffer[i]; }
    value_type& operator[](ssize_t i) { return m_buffer[i]; }

    const value_type* data() const { return m_buffer; }
    value_type* data() { return m_buffer; }

    const value_type* data_end() const { return m_buffer + size_; }
    value_type* data_end() { return m_buffer + size_; }

    typedef const value_type* const_iterator;
    const value_type* begin() const { return m_buffer; }
    const value_type* end() const { return m_buffer + size_; }

    typedef value_type* iterator;
    value_type* begin() { return m_buffer; }
    value_type* end() { return m_buffer + size_; }

    value_type front() const { cxAssert(size_ > 0); return *m_buffer; }
    value_type& front() { cxAssert(size_ > 0); return *m_buffer; }

    value_type back() const { cxAssert(size_ > 0); return *(m_buffer+size_-1); }
    value_type& back() { cxAssert(size_ > 0); return *(m_buffer+size_-1); }
    //void pop_back() { cxAssert(size_ > 0); erase_element(size_-1); }
    void pop_back(ssize_t count = 1)
    {
        size_ -= count;
        cxAssert(size_ >= 0);
    }

    // Efficiently in-place moves n bytes 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);

    // Insert count (uninitialised) bytes at position i
    void insertbytes(ssize_t i, ssize_t count);
    void growbytes(ssize_t count) { insertbytes(size(),count); } 
    
    // Insert range [r1,r2) at position i
    void insert(ssize_t i, const value_type* r1, const value_type* r2);

    void insert(ssize_t i, ssize_t count, value_type x)
    {
        insertbytes(i,count);
        memset(m_buffer+i,x,count);
    }

    void insert(iterator i, const value_type* r1, const value_type* r2)
    {
        insert(i-m_buffer,r1,r2);
    }
    void insert(iterator i, ssize_t count, value_type x) 
    { 
        insert(i-m_buffer,count,x); 
    }
    void insert(ssize_t i, value_type x)
    {
        insertbytes(i,1);
        m_buffer[i] = x;
    }
    void insert(iterator i, value_type x)
    {
        insert(i-m_buffer,x);
    }
    
    template<typename T>
    void push_back(const T& x)
    {
        ssize_t n = size_ + sizeof(T);
        if (m_capacity < n)
        {
            reserve(n + m_capacity);
        }                
        new(m_buffer + size_) T(x);
        size_ = n;
    }
    
    // Push range [r1,r2) onto the back of the vector
    void push_back(const value_type* r1, const value_type* r2);

    void swap(VectorOfByte& rhs);

    void erase(iterator i1, iterator i2);
    void erase(iterator i);
    void erase(ssize_t i, ssize_t n);
    void erase_element(ssize_t i);

//private:
    value_type* m_buffer;
    ssize_t size_;
    ssize_t m_capacity;
    //template <typename T> friend class xvector; 
};

cxUtils_API xostream& operator<<(xostream& os, const VectorOfByte& v);

} // namespace ceda

#endif // include guard