#ifndef ARRAY1_H

#define ARRAY1_H

#include <algorithm>

#include <cstring>

#include <cassert>

#include <climits>

#include <cstdlib>

#include <iostream>

#include <stdexcept>

#include <vector>

// In this file:

// Array1<T>: a dynamic 1D array for plain-old-data (not objects)

// WrapArray1<T>: a 1D array wrapper around an existing array (perhaps objects, perhaps data)

// For the most part std::vector operations are supported, though for the Wrap version

// note that memory is never allocated/deleted and constructor/destructors are never called

// from within the class, thus only shallow copies can be made and some operations such as

// resize() and push_back() are limited.

// Note: for the most part assertions are done with assert(), not exceptions...

// gross template hacking to determine if a type is integral or not

struct Array1True {};

struct Array1False {};

template<typename T> struct Array1IsIntegral{ typedef Array1False type; }; // default: no (specializations to yes follow)

template<> struct Array1IsIntegral<bool>{ typedef Array1True type; };

template<> struct Array1IsIntegral<char>{ typedef Array1True type; };

template<> struct Array1IsIntegral<signed char>{ typedef Array1True type; };

template<> struct Array1IsIntegral<unsigned char>{ typedef Array1True type; };

template<> struct Array1IsIntegral<short>{ typedef Array1True type; };

template<> struct Array1IsIntegral<unsigned short>{ typedef Array1True type; };

template<> struct Array1IsIntegral<int>{ typedef Array1True type; };

template<> struct Array1IsIntegral<unsigned int>{ typedef Array1True type; };

template<> struct Array1IsIntegral<long>{ typedef Array1True type; };

template<> struct Array1IsIntegral<unsigned long>{ typedef Array1True type; };

template<> struct Array1IsIntegral<long long>{ typedef Array1True type; };

template<> struct Array1IsIntegral<unsigned long long>{ typedef Array1True type; };

//============================================================================

template<typename T>

struct Array1

{

// STL-friendly typedefs

typedef T* iterator;

typedef const T* const_iterator;

typedef unsigned long size_type;

typedef long difference_type;

typedef T& reference;

typedef const T& const_reference;

typedef T value_type;

typedef T* pointer;

typedef const T* const_pointer;

typedef std::reverse_iterator<iterator> reverse_iterator;

typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

// the actual representation

unsigned long n;

unsigned long max_n;

T* data;

// STL vector's interface, with additions, but only valid when used with plain-old-data

Array1(void)

: n(0), max_n(0), data(0)

{}

// note: default initial values are zero

Array1(unsigned long n_)

: n(0), max_n(0), data(0)

{

if(n_>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

data=(T*)std::calloc(n_, sizeof(T));

if(!data) throw std::bad_alloc();

n=n_;

max_n=n_;

}

Array1(unsigned long n_, const T& value)

: n(0), max_n(0), data(0)

{

if(n_>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

data=(T*)std::calloc(n_, sizeof(T));

if(!data) throw std::bad_alloc();

n=n_;

max_n=n_;

for(unsigned long i=0; i<n; ++i) data[i]=value;

}

Array1(unsigned long n_, const T& value, unsigned long max_n_)

: n(0), max_n(0), data(0)

{

assert(n_<=max_n_);

if(max_n_>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

data=(T*)std::calloc(max_n_, sizeof(T));

if(!data) throw std::bad_alloc();

n=n_;

max_n=max_n_;

for(unsigned long i=0; i<n; ++i) data[i]=value;

}

Array1(unsigned long n_, const T* data_)

: n(0), max_n(0), data(0)

{

if(n_>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

data=(T*)std::calloc(n_, sizeof(T));

if(!data) throw std::bad_alloc();

n=n_;

max_n=n_;

assert(data_);

std::memcpy(data, data_, n*sizeof(T));

}

Array1(unsigned long n_, const T* data_, unsigned long max_n_)

: n(0), max_n(0), data(0)

{

assert(n_<=max_n_);

if(max_n_>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

data=(T*)std::calloc(max_n_, sizeof(T));

if(!data) throw std::bad_alloc();

max_n=max_n_;

n=n_;

assert(data_);

std::memcpy(data, data_, n*sizeof(T));

}

Array1(const Array1<T> &x)

: n(0), max_n(0), data(0)

{

data=(T*)std::malloc(x.n*sizeof(T));

if(!data) throw std::bad_alloc();

n=x.n;

max_n=x.n;

std::memcpy(data, x.data, n*sizeof(T));

}

~Array1(void)

{

std::free(data);

#ifndef NDEBUG

data=0;

n=max_n=0;

#endif

}

const T& operator[](unsigned long i) const

{ return data[i]; }

T& operator[](unsigned long i)

{ return data[i]; }

// these are range-checked (in debug mode) versions of operator[], like at()

const T& operator()(unsigned long i) const

{

assert(i<n);

return data[i];

}

T& operator()(unsigned long i)

{

assert(i<n);

return data[i];

}

Array1<T>& operator=(const Array1<T>& x)

{

if(max_n<x.n){

T* new_data=(T*)std::malloc(x.n*sizeof(T));

if(!new_data) throw std::bad_alloc();

std::free(data);

data=new_data;

max_n=x.n;

}

n=x.n;

std::memcpy(data, x.data, n*sizeof(T));

return *this;

}

bool operator==(const Array1<T>& x) const

{

if(n!=x.n) return false;

for(unsigned long i=0; i<n; ++i) if(!(data[i]==x.data[i])) return false;

return true;

}

bool operator!=(const Array1<T>& x) const

{

if(n!=x.n) return true;

for(unsigned long i=0; i<n; ++i) if(data[i]!=x.data[i]) return true;

return false;

}

bool operator<(const Array1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]<x[i]) return true;

else if(x[i]<data[i]) return false;

}

return n<x.n;

}

bool operator>(const Array1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]>x[i]) return true;

else if(x[i]>data[i]) return false;

}

return n>x.n;

}

bool operator<=(const Array1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]<x[i]) return true;

else if(x[i]<data[i]) return false;

}

return n<=x.n;

}

bool operator>=(const Array1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]>x[i]) return true;

else if(x[i]>data[i]) return false;

}

return n>=x.n;

}

void add_unique(const T& value)

{

for(unsigned long i=0; i<n; ++i) if(data[i]==value) return;

if(n==max_n) grow();

data[n++]=value;

}

void assign(const T& value)

{ for(unsigned long i=0; i<n; ++i) data[i]=value; }

void assign(unsigned long num, const T& value)

{ fill(num, value); }

// note: copydata may not alias this array's data, and this should not be

// used when T is a full object (which defines its own copying operation)

void assign(unsigned long num, const T* copydata)

{

assert(num==0 || copydata);

if(num>max_n){

if(num>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

std::free(data);

data=(T*)std::malloc(num*sizeof(T));

if(!data) throw std::bad_alloc();

max_n=num;

}

n=num;

std::memcpy(data, copydata, n*sizeof(T));

}

template<typename InputIterator>

void assign(InputIterator first, InputIterator last)

{ assign_(first, last, typename Array1IsIntegral<InputIterator>::type()); }

template<typename InputIterator>

void assign_(InputIterator first, InputIterator last, Array1True check)

{ fill(first, last); }

template<typename InputIterator>

void assign_(InputIterator first, InputIterator last, Array1False check)

{

unsigned long i=0;

InputIterator p=first;

for(; p!=last; ++p, ++i){

if(i==max_n) grow();

data[i]=*p;

}

n=i;

}

const T& at(unsigned long i) const

{

assert(i<n);

return data[i];

}

T& at(unsigned long i)

{

assert(i<n);

return data[i];

}

const T& back(void) const

{

assert(data && n>0);

return data[n-1];

}

T& back(void)

{

assert(data && n>0);

return data[n-1];

}

const T* begin(void) const

{ return data; }

T* begin(void)

{ return data; }

unsigned long capacity(void) const

{ return max_n; }

void clear(void)

{

std::free(data);

data=0;

max_n=0;

n=0;

}

bool empty(void) const

{ return n==0; }

const T* end(void) const

{ return data+n; }

T* end(void)

{ return data+n; }

void erase(unsigned long index)

{

assert(index<n);

for(unsigned long i=index; i<n-1; ++i)

data[i]=data[i-1];

pop_back();

}

void fill(unsigned long num, const T& value)

{

if(num>max_n){

if(num>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

std::free(data);

data=(T*)std::malloc(num*sizeof(T));

if(!data) throw std::bad_alloc();

max_n=num;

}

n=num;

for(unsigned long i=0; i<n; ++i) data[i]=value;

}

const T& front(void) const

{

assert(n>0);

return *data;

}

T& front(void)

{

assert(n>0);

return *data;

}

void grow(void)

{

unsigned long new_size=(max_n*sizeof(T)<ULONG_MAX/2 ? 2*max_n+1 : ULONG_MAX/sizeof(T));

T *new_data=(T*)std::realloc(data, new_size*sizeof(T));

if(!new_data) throw std::bad_alloc();

data=new_data;

max_n=new_size;

}

void insert(unsigned long index, const T& entry)

{

assert(index<=n);

push_back(back());

for(unsigned long i=n-1; i>index; --i)

data[i]=data[i-1];

data[index]=entry;

}

unsigned long max_size(void) const

{ return ULONG_MAX/sizeof(T); }

void pop_back(void)

{

assert(n>0);

--n;

}

void push_back(const T& value)

{

if(n==max_n) grow();

data[n++]=value;

}

reverse_iterator rbegin(void)

{ return reverse_iterator(end()); }

const_reverse_iterator rbegin(void) const

{ return const_reverse_iterator(end()); }

reverse_iterator rend(void)

{ return reverse_iterator(begin()); }

const_reverse_iterator rend(void) const

{ return const_reverse_iterator(begin()); }

void reserve(unsigned long r)

{

if(r>ULONG_MAX/sizeof(T)) throw std::bad_alloc();

T *new_data=(T*)std::realloc(data, r*sizeof(T));

if(!new_data) throw std::bad_alloc();

data=new_data;

max_n=r;

}

void resize(unsigned long n_)

{

if(n_>max_n) reserve(n_);

n=n_;

}

void resize(unsigned long n_, const T& value)

{

if(n_>max_n) reserve(n_);

if(n<n_) for(unsigned long i=n; i<n_; ++i) data[i]=value;

n=n_;

}

void set_zero(void)

{ std::memset(data, 0, n*sizeof(T)); }

unsigned long size(void) const

{ return n; }

void swap(Array1<T>& x)

{

std::swap(n, x.n);

std::swap(max_n, x.max_n);

std::swap(data, x.data);

}

// resize the array to avoid wasted space, without changing contents

// (Note: realloc, at least on some platforms, will not do the trick)

void trim(void)

{

if(n==max_n) return;

T *new_data=(T*)std::malloc(n*sizeof(T));

if(!new_data) return;

std::memcpy(new_data, data, n*sizeof(T));

std::free(data);

data=new_data;

max_n=n;

}

};

// some common arrays

typedef Array1<double> Array1d;

typedef Array1<float> Array1f;

typedef Array1<long long> Array1ll;

typedef Array1<unsigned long long> Array1ull;

typedef Array1<int> Array1i;

typedef Array1<unsigned int> Array1ui;

typedef Array1<short> Array1s;

typedef Array1<unsigned short> Array1us;

typedef Array1<char> Array1c;

typedef Array1<unsigned char> Array1uc;

//============================================================================

template<typename T>

struct WrapArray1

{

// STL-friendly typedefs

typedef T* iterator;

typedef const T* const_iterator;

typedef unsigned long size_type;

typedef long difference_type;

typedef T& reference;

typedef const T& const_reference;

typedef T value_type;

typedef T* pointer;

typedef const T* const_pointer;

typedef std::reverse_iterator<iterator> reverse_iterator;

typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

// the actual representation

unsigned long n;

unsigned long max_n;

T* data;

// most of STL vector's interface, with a few changes

WrapArray1(void)

: n(0), max_n(0), data(0)

{}

WrapArray1(unsigned long n_, T* data_)

: n(n_), max_n(n_), data(data_)

{ assert(data || max_n==0); }

WrapArray1(unsigned long n_, T* data_, unsigned long max_n_)

: n(n_), max_n(max_n_), data(data_)

{

assert(n<=max_n);

assert(data || max_n==0);

}

// Allow for simple shallow copies of existing arrays

// Note that if the underlying arrays change where their data is, the WrapArray may be screwed up

WrapArray1(Array1<T>& a)

: n(a.n), max_n(a.max_n), data(a.data)

{}

WrapArray1(std::vector<T>& a)

: n(a.size()), max_n(a.capacity()), data(&a[0])

{}

void init(unsigned long n_, T* data_, unsigned long max_n_)

{

assert(n_<=max_n_);

assert(data_ || max_n_==0);

n=n_;

max_n=max_n_;

data=data_;

}

const T& operator[](unsigned long i) const

{ return data[i]; }

T& operator[](unsigned long i)

{ return data[i]; }

// these are range-checked (in debug mode) versions of operator[], like at()

const T& operator()(unsigned long i) const

{

assert(i<n);

return data[i];

}

T& operator()(unsigned long i)

{

assert(i<n);

return data[i];

}

bool operator==(const WrapArray1<T>& x) const

{

if(n!=x.n) return false;

for(unsigned long i=0; i<n; ++i) if(!(data[i]==x.data[i])) return false;

return true;

}

bool operator!=(const WrapArray1<T>& x) const

{

if(n!=x.n) return true;

for(unsigned long i=0; i<n; ++i) if(data[i]!=x.data[i]) return true;

return false;

}

bool operator<(const WrapArray1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]<x[i]) return true;

else if(x[i]<data[i]) return false;

}

return n<x.n;

}

bool operator>(const WrapArray1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]>x[i]) return true;

else if(x[i]>data[i]) return false;

}

return n>x.n;

}

bool operator<=(const WrapArray1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]<x[i]) return true;

else if(x[i]<data[i]) return false;

}

return n<=x.n;

}

bool operator>=(const WrapArray1<T>& x) const

{

for(unsigned long i=0; i<n && i<x.n; ++i){

if(data[i]>x[i]) return true;

else if(x[i]>data[i]) return false;

}

return n>=x.n;

}

void add_unique(const T& value)

{

for(unsigned long i=0; i<n; ++i) if(data[i]==value) return;

assert(n<max_n);

data[n++]=value;

}

void assign(const T& value)

{ for(unsigned long i=0; i<n; ++i) data[i]=value; }

void assign(unsigned long num, const T& value)

{ fill(num, value); }

// note: copydata may not alias this array's data, and this should not be

// used when T is a full object (which defines its own copying operation)

void assign(unsigned long num, const T* copydata)

{

assert(num==0 || copydata);

assert(num<=max_n);

n=num;

std::memcpy(data, copydata, n*sizeof(T));

}

template<typename InputIterator>

void assign(InputIterator first, InputIterator last)

{ assign_(first, last, typename Array1IsIntegral<InputIterator>::type()); }

template<typename InputIterator>

void assign_(InputIterator first, InputIterator last, Array1True check)

{ fill(first, last); }

template<typename InputIterator>

void assign_(InputIterator first, InputIterator last, Array1False check)

{

unsigned long i=0;

InputIterator p=first;

for(; p!=last; ++p, ++i){

assert(i<max_n);

data[i]=*p;

}

n=i;

}

const T& at(unsigned long i) const

{

assert(i<n);

return data[i];

}

T& at(unsigned long i)

{

assert(i<n);

return data[i];

}

const T& back(void) const

{

assert(data && n>0);

return data[n-1];

}

T& back(void)

{

assert(data && n>0);

return data[n-1];

}

const T* begin(void) const

{ return data; }

T* begin(void)

{ return data; }

unsigned long capacity(void) const

{ return max_n; }

void clear(void)

{ n=0; }

bool empty(void) const

{ return n==0; }

const T* end(void) const

{ return data+n; }

T* end(void)

{ return data+n; }

void erase(unsigned long index)

{

assert(index<n);

for(unsigned long i=index; i<n-1; ++i)

data[i]=data[i-1];

pop_back();

}

void fill(unsigned long num, const T& value)

{

assert(num<=max_n);

n=num;

for(unsigned long i=0; i<n; ++i) data[i]=value;

}

const T& front(void) const

{

assert(n>0);

return *data;

}

T& front(void)

{

assert(n>0);

return *data;

}

void insert(unsigned long index, const T& entry)

{

assert(index<=n);

push_back(back());

for(unsigned long i=n-1; i>index; --i)

data[i]=data[i-1];

data[index]=entry;

}

unsigned long max_size(void) const

{ return max_n; }

void pop_back(void)

{

assert(n>0);

--n;

}

void push_back(const T& value)

{

assert(n<max_n);

data[n++]=value;

}

reverse_iterator rbegin(void)

{ return reverse_iterator(end()); }

const_reverse_iterator rbegin(void) const

{ return const_reverse_iterator(end()); }

reverse_iterator rend(void)

{ return reverse_iterator(begin()); }

const_reverse_iterator rend(void) const

{ return const_reverse_iterator(begin()); }

void reserve(unsigned long r)

{ assert(r<=max_n); }

void resize(unsigned long n_)

{

assert(n_<=max_n);

n=n_;

}

void resize(unsigned long n_, const T& value)

{

assert(n_<=max_n);

if(n<n_) for(unsigned long i=n; i<n_; ++i) data[i]=value;

n=n_;

}

// note: shouldn't be used when T is a full object (setting to zero may not make sense)

void set_zero(void)

{ std::memset(data, 0, n*sizeof(T)); }

unsigned long size(void) const

{ return n; }

void swap(WrapArray1<T>& x)

{

std::swap(n, x.n);

std::swap(max_n, x.max_n);

std::swap(data, x.data);

}

};

// some common arrays

typedef WrapArray1<double> WrapArray1d;

typedef WrapArray1<float> WrapArray1f;

typedef WrapArray1<long long> WrapArray1ll;

typedef WrapArray1<unsigned long long> WrapArray1ull;

typedef WrapArray1<int> WrapArray1i;

typedef WrapArray1<unsigned int> WrapArray1ui;

typedef WrapArray1<short> WrapArray1s;

typedef WrapArray1<unsigned short> WrapArray1us;

typedef WrapArray1<char> WrapArray1c;

typedef WrapArray1<unsigned char> WrapArray1uc;

#endif