/Users/ljp/code/gamma/trunk/Gamma/Containers.h

#ifndef GAMMA_CONTAINERS_H_INC
#define GAMMA_CONTAINERS_H_INC

/*  Gamma - Generic processing library
    See COPYRIGHT file for authors and license information

    File Description:
    Dynamically sizable generic containers.
*/

#include <stdlib.h>
#include <vector>
#include <map>

#include "Gamma/Allocator.h"
#include "Gamma/Conversion.h"
#include "Gamma/mem.h"
#include "Gamma/scl.h"

namespace gam{


struct SizeArrayPow2{
    SizeArrayPow2(uint32_t size){ (*this)(size); }
    uint32_t operator()() const { return (1<<mBitsI) & 0xfffffffe/*avoids 1*/; }
    void operator()(uint32_t v){ mBitsI = scl::log2(convert(v)); mBitsF = 32U - mBitsI; /*printf("%d %d\n", mBitsI, mBitsF);*/ }
    static uint32_t convert(uint32_t v){ v=scl::ceilPow2(v); return v!=1 ? v : 2; } // should return 0,2,4,8,16,...
    uint32_t mBitsI;    // integer portion # bits
    uint32_t mBitsF;    // fraction portion # bits
};


struct SizeArray{
    SizeArray(uint32_t size): mSize(size){}
    uint32_t operator()() const { return mSize; }
    void operator()(uint32_t v){ mSize = v; }
    static uint32_t convert(uint32_t v){ return v; }
    uint32_t mSize;
};



template <class T, class S, class A=gam::Allocator<T> >
class ArrayBase : private A{
public:

    ArrayBase();
    explicit ArrayBase(uint32_t size);
    ArrayBase(uint32_t size, const T& init);
    ArrayBase(T * src, uint32_t size);
    explicit ArrayBase(ArrayBase<T,S,A>& src);

    virtual ~ArrayBase();

    T& operator[](uint32_t i);
    
    const T& operator[](uint32_t i) const;
    
    ArrayBase& assign(const T& v);

    
    ArrayBase& assign(const T& v, uint32_t end, uint32_t stride=1, uint32_t start=0);

    T * elems();                    
    const T * elems() const;        
    uint32_t size() const;          

    void clear();

    
    void own();
    
    bool isSoleOwner() const;
    
    bool usingExternalSource() const;
    
    
    void resize(uint32_t newSize, const T& c=T());
    void source(ArrayBase<T,S,A>& src);     
    void source(T * src, uint32_t size);    

    virtual void onResize(){}

    static int references(T* m){
        typename RefCount::const_iterator it = refCount().find(m);
        return it != refCount().end() ? it->second : 0;
    }

protected:
    T * mElems;
    S mSize;

    typedef std::map<T *, int> RefCount;

    static RefCount& refCount(){
        static RefCount * o = new RefCount;
        return *o;
    }
    
    // is memory being managed automatically?
    static bool managing(T* m){ return references(m) != 0; }

private: ArrayBase& operator=(const ArrayBase& v);
};



template <class T, class A=gam::Allocator<T> >
class Array : public ArrayBase<T, SizeArray, A>{
public:
    typedef ArrayBase<T, SizeArray, A> Base;

    Array(): Base(){}
    explicit Array(uint32_t size): Base(size){}
    Array(uint32_t size, const T& init): Base(size, init){}
    Array(T * src, uint32_t size): Base(src, size){}
    Array(Array& src): Base(src){}

    virtual ~Array(){}

private: Array& operator=(const Array& v);
};



template <class T, class A=gam::Allocator<T> >
class ArrayPow2 : public ArrayBase<T, SizeArrayPow2, A>{
public:
    typedef ArrayBase<T, SizeArrayPow2, A> Base;

    ArrayPow2(): Base(){}
    explicit ArrayPow2(uint32_t size): Base(size){}
    ArrayPow2(uint32_t size, const T& initial): Base(size, initial){}
    ArrayPow2(T * src, uint32_t size): Base(src, size){}
    explicit ArrayPow2(const ArrayPow2& src): Base(src){}

    virtual ~ArrayPow2(){}

    uint32_t fracBits() const;              
    float fraction(uint32_t phase) const;   
    uint32_t index(uint32_t phase) const;   
    uint32_t log2Size() const;              
    uint32_t oneIndex() const;              

    const T& atPhase(uint32_t phase) const; 
    void putPhase(uint32_t phase, T v);     
    
private:
    using Base::mSize;
private: ArrayPow2& operator=(const ArrayPow2& v);
};



template <class T, class A=gam::Allocator<T> >
class Ring : public Array<T,A> {
public:

    typedef Array<T,A> Base; using Base::elems; using Base::size;

    explicit Ring(uint32_t size=0, const T& value=T());

    T& readBack(){ return (*this)[indexBack()]; }
    const T& readBack() const { return (*this)[indexBack()]; }
    
    T& readFront(){ return (*this)[indexFront()]; }
    const T& readFront() const { return (*this)[indexFront()]; }
    
    T& read(uint32_t ago){ return (*this)[indexPrev(ago)]; }
    const T& read(uint32_t ago) const { return (*this)[indexPrev(ago)]; }

    void copy(T * dst, uint32_t len, uint32_t delay) const;
    
    void copyUnwrap(T * dst, uint32_t len) const;
    
    uint32_t pos() const;           
    bool reachedEnd() const;        
    uint32_t indexBack() const;     
    uint32_t indexFront() const;    
    uint32_t indexPrev(uint32_t ago) const; 

    void operator()(const T& v);    
    void pos(uint32_t index);       
    void reset();                   
    void writeClip(const T& v);     
    
protected:
    uint32_t mPos;
    void incPos();
};


template <class T, class A=gam::Allocator<T> >
class RingFill : public Ring<T,A> {
public:
    typedef Ring<T,A> Base;
    
    explicit RingFill(uint32_t size=0, const T& value=T())
    :   Base(size, value), mFill(0)
    {}

    void operator()(const T& v){
        this->Base::operator()(v);
        if(mFill < Base::size()) ++mFill;
    }
    
    void reset(){ mFill=0; Base::reset(); }
    
    
    uint32_t fill() const { return mFill; }
    
protected:
    uint32_t mFill;
    virtual void onResize(){ reset(); }
};




template <class T, class A=gam::Allocator<T> >
class DoubleRing : public Ring<T,A>{
public:
    explicit DoubleRing(uint32_t size=0, const T& value=T())
    :   Ring<T>(size, value), mRead(size)
    {}

    const Array<T,A>& readBuf() const { return mRead; }

    
    T * copyUnwrap(){ Ring<T,A>::copyUnwrap(mRead.elems(), mRead.size()); return mRead.elems(); }
    
    
    T * copy(){
        mem::deepCopy(mRead.elems(), Ring<T,A>::elems(), mRead.size());
        //for(uint32_t i=0; i<read.size(); ++i) construct(read.elems()+i, (*this)[i]);
        return mRead.elems();
    }

    void resize(int n){ Ring<T,A>::resize(n); mRead.resize(n); }

protected:  
    Array<T,A> mRead;
};




template <class T, class A=gam::Allocator<T> >
struct DelayN: public Ring<T,A>{
    using Ring<T,A>::incPos; using Ring<T,A>::pos;

    explicit DelayN(uint32_t size, const T& value=T())
    :   Ring<T,A>(size, value)
    {}

    T operator()(const T& input){
        incPos();               // inc write pos
        T dly = (*this)[pos()]; // read oldest element
        (*this)[pos()] = input; // write new element
        return dly;             //  ... write pos left at last written element
    }
};






// Implementation_______________________________________________________________


// ArrayBase

#define TEM3 template <class T, class S, class A>
#define ARRAYBASE_INIT mElems(0), mSize(0)

TEM3 ArrayBase<T,S,A>::ArrayBase()
:   ARRAYBASE_INIT{}

TEM3 ArrayBase<T,S,A>::ArrayBase(uint32_t sz)
:   ARRAYBASE_INIT
{   resize(sz); }

TEM3 ArrayBase<T,S,A>::ArrayBase(uint32_t sz, const T& initial)
:   ARRAYBASE_INIT
{   resize(sz); for(uint32_t i=0;i<this->size();++i) (*this)[i] = initial; }

TEM3 ArrayBase<T,S,A>::ArrayBase(T * src, uint32_t sz)
:   ARRAYBASE_INIT
{   source(src, sz); }

TEM3 ArrayBase<T,S,A>::ArrayBase(ArrayBase<T,S,A>& src)
:   ARRAYBASE_INIT
{   source(src); }

#undef ARRAYBASE_INIT

TEM3 ArrayBase<T,S,A>::~ArrayBase(){ clear(); }

TEM3 inline ArrayBase<T,S,A>& ArrayBase<T,S,A>::assign(const T& v){
    return assign(v, size());
}

TEM3 inline ArrayBase<T,S,A>& ArrayBase<T,S,A>::assign(
    const T& v, uint32_t end, uint32_t stride, uint32_t start
){
    for(uint32_t i=start; i<end; i+=stride) A::construct(mElems+i, v);
    return *this;
}

TEM3 inline T& ArrayBase<T,S,A>::operator[](uint32_t i){ return elems()[i]; }
TEM3 inline const T& ArrayBase<T,S,A>::operator[](uint32_t i) const { return elems()[i]; }

TEM3 inline T * ArrayBase<T,S,A>::elems(){ return mElems; }
TEM3 inline const T * ArrayBase<T,S,A>::elems() const { return mElems; }

TEM3 void ArrayBase<T,S,A>::clear(){ //printf("ArrayBase::clear(): mElems=%p\n", mElems);
    
    // We will only attempt to deallocate the data if it exists and is being 
    // managed (reference counted) by ArrayBase.
    if(mElems && managing(mElems)){
        int& c = refCount()[mElems];
        --c;
        if(0 == c){
            refCount().erase(mElems);
            for(uint32_t i=0; i<size(); ++i) A::destroy(mElems+i);
            A::deallocate(mElems, size());
        }
        mElems=0; mSize(0);
    }
}

TEM3 void ArrayBase<T,S,A>::own(){  
    T * oldElems = elems();
    
    // If we are not the sole owner, do nothing...
    if(!isSoleOwner()){
        uint32_t oldSize = size();
        clear();
        resize(oldSize);
        for(uint32_t i=0; i<size(); ++i) A::construct(mElems+i, oldElems[i]);
    }
}

TEM3 bool ArrayBase<T,S,A>::isSoleOwner() const {
    return references((T*)elems()) == 1;
}

TEM3 bool ArrayBase<T,S,A>::usingExternalSource() const {
    return elems() && !managing((T*)elems());
}

TEM3 void ArrayBase<T,S,A>::resize(uint32_t newSize, const T& c){
//printf("ArrayBase::resize() %p\n", this);
    newSize = mSize.convert(newSize);

    if(0 == newSize){
        clear();
    }

    if(newSize != size()){
        
        T * newElems = A::allocate(newSize);

        // If successful allocation...
        if(newElems){

            uint32_t nOldToCopy = newSize<size() ? newSize : size();
        
            // Copy over old elements
            for(uint32_t i=0; i<nOldToCopy; ++i){
                A::construct(newElems+i, (*this)[i]);
            }
            
            // Copy argument into any additional elements
            for(uint32_t i=nOldToCopy; i<newSize; ++i){
                A::construct(newElems+i, c);
            }
        
            clear();
            mElems = newElems;
        
            refCount()[mElems] = 1;
            mSize(newSize);
            onResize();
        }
    }
    //printf("ArrayBase::resize(): mElems=%p, size=%d\n", mElems, size());
}

TEM3 inline uint32_t ArrayBase<T,S,A>::size() const { return mSize(); }

TEM3 void ArrayBase<T,S,A>::source(ArrayBase<T,S,A>& src){
    source(src.elems(), src.size());
}

TEM3 void ArrayBase<T,S,A>::source(T * src, uint32_t size){
    clear();
    if(managing(src)){
        ++refCount()[src];
    }
    mElems = src;
    mSize(size);
    onResize();
}

#undef TEM3


#define TEM template<class T, class A>

// ArrayPow2

TEM inline uint32_t ArrayPow2<T,A>::oneIndex() const { return 1<<fracBits(); }
TEM inline uint32_t ArrayPow2<T,A>::log2Size() const { return mSize.mBitsI; }
TEM inline uint32_t ArrayPow2<T,A>::fracBits() const { return mSize.mBitsF; }
TEM inline uint32_t ArrayPow2<T,A>::index(uint32_t phase) const { return phase >> fracBits(); }

TEM inline const T& ArrayPow2<T,A>::atPhase(uint32_t phase) const { return (*this)[index(phase)]; }
TEM inline void ArrayPow2<T,A>::putPhase(uint32_t phase, T v){ (*this)[index(phase)] = v; }

TEM inline float ArrayPow2<T,A>::fraction(uint32_t phase) const{        
    return gam::fraction(log2Size(), phase);
}



//---- Ring

TEM Ring<T,A>::Ring(uint32_t size, const T& v) : Array<T,A>(size,v), mPos(size-1){}

TEM inline void Ring<T,A>::operator()(const T& v){
    incPos();               // inc write pos; do first to avoid out-of-bounds access
    (*this)[pos()] = v;     // write new element
}

TEM void Ring<T,A>::copy(T * dst, uint32_t len, uint32_t delay) const{
    // pos() points to most recently written slot
    //uint32_t tap = (pos() - delay) % size();
    uint32_t tap = (uint32_t)scl::wrap((int32_t)pos() - (int32_t)delay, (int32_t)size());

    // this ensures that we don't copy across the ring tap boundary
    // we add one to maxLen because of a fence post anomaly
    uint32_t maxLen = (tap < pos() ? (pos() - tap) : (pos() + (size() - tap))) + 1;
    len = scl::min(len, maxLen);
    
    mem::copyFromRing(elems(), size(), tap, dst, len);
}

TEM void Ring<T,A>::copyUnwrap(T * dst, uint32_t len) const { copy(dst, len, size() - 1); }

TEM inline uint32_t Ring<T,A>::indexBack() const {
    uint32_t i = pos() + 1;
    return (i != size()) ? i : 0;
}

TEM inline uint32_t Ring<T,A>::indexFront() const { return pos(); }

TEM inline uint32_t Ring<T,A>::indexPrev(uint32_t v) const {
    return scl::wrapOnce<int>(pos() - v, size());
}

TEM inline uint32_t Ring<T,A>::pos() const { return mPos; }
TEM inline bool Ring<T,A>::reachedEnd() const { return pos() == (size()-1); }

TEM inline void Ring<T,A>::incPos(){ if(++mPos >= size()) mPos = 0; }
TEM void Ring<T,A>::pos(uint32_t index){ mPos = index; }

TEM void Ring<T,A>::reset(){ pos(size()-1); }

TEM inline void Ring<T,A>::writeClip(const T& v){
    if(mPos < size()){
        (*this)[mPos] = v;
        mPos++;
    }
}

#undef TEM
} // gam::
#endif