wb-vector.h

Go to the documentation of this file.

// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2014-2015 Tsinghua University
// Author: wb.th08@gmail.com (Bin Wang), ozj@tsinghua.edu.cn (Zhijian Ou)
//
// All h, cpp, cc, and script files (e.g. bat, sh, pl, py) should include the above
// license declaration. Different coding language may use different comment styles.




#ifndef _WB_VECTOR_H_
#define _WB_VECTOR_H_
//#include <conio.h>
#include <iostream>
#include <cmath>
#include <cstring>
#include <stdlib.h>
using namespace std;

#define POINT_TEST(p) { if ((p)==NULL) {cout<<#p<<"[New Memory Error]"<<endl; exit(0);} }
#define SAFE_NEW(p, Type) {p = new Type; POINT_TEST(p)}
#define SAFE_DNEW(PType, p, Type) { PType p = new Type; POINT_TEST(p) }
#define SAFE_NEW_ARRAY(p, Type, n) { p = new Type[n]; POINT_TEST(p) }
#define SAFE_NEW_DARRAY(p, Type, n, m) { p=new Type*[n]; for(int i=0; i<n; i++){p[i]=new Type[m];}; POINT_TEST(p) }


#define SAFE_DELETE(p) {if (p) delete (p); (p)=NULL;}
#define SAFE_DELETE_ARRAY(p) {if(p) delete [](p); (p)=NULL;}
#define SAFE_DELETE_DARRAY(p, n) { if(p){ for(int i=0; i<n; i++){delete [](p)[i];} delete [](p); (p)=NULL; } }
#define SAFE_DEL_POINTER_ARRAY(a) for (int i=0; i<a.GetNum(); i++) { SAFE_DELETE(a[i]); } a.Clean();


namespace wb
{
#define DEFAULE_VECTOR_SIZE 16
#define VECTOR_bits2Size(n) (1<<n)

    template <typename T>
    class Vector
    {
    protected:
        T *m_pBuffer; 
        int m_nBits;  
    public:
        Vector(int size = DEFAULE_VECTOR_SIZE)
        {
            m_pBuffer = NULL;
            m_nBits = Size2Bits(size);
            m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
        }
        ~Vector()
        {
            if (m_pBuffer != NULL)
                delete[]m_pBuffer;
            m_pBuffer = NULL;
            m_nBits = 0;
        }
        int Size() const { return VECTOR_bits2Size(m_nBits); }
        inline T* GetBuffer(int i = 0) const { return m_pBuffer + i; }
        inline T& Get(int i)
        {

            if (i<0) {
                i = 0;
            }

            int nSize = VECTOR_bits2Size(m_nBits);

            if (i >= nSize)
            {
                int nNewBits = Size2Bits(i + 1);

                T *pNew = new T[VECTOR_bits2Size(nNewBits)];
                //memset(pNew+m_nBufferSize, 0, sizeof(T)*nStepNum*m_nBufferStep);


                for (int n = 0; n<nSize; n++)
                    pNew[n] = m_pBuffer[n];

                delete[] m_pBuffer;
                m_pBuffer = pNew;
                m_nBits = nNewBits;
            }

            return m_pBuffer[i];
        }

        inline int Size2Bits(int size)
        {
            for (int n = 1;; ++n) {
                if (VECTOR_bits2Size(n) >= size)
                    return n;
            }
            return 0;
        }


        void Fill(T m)
        {
            for (int i = 0; i<VECTOR_bits2Size(m_nBits); i++)
                m_pBuffer[i] = m;
        }
        void Zero()
        {
            memset(m_pBuffer, 0, sizeof(T)*VECTOR_bits2Size(m_nBits));
        }

        /*
            As sometimes using memcpy may cause error.
            Such as copying a string vector.
        */
        void Copy(const Vector<T> &vector)
        {
            if (m_pBuffer == NULL) {
                m_nBits = vector.m_nBits;
                m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
            }
            else if (m_nBits < vector.m_nBits) {
                delete[] m_pBuffer;
                m_nBits = vector.m_nBits;
                m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
            }

            for (int i = 0; i<VECTOR_bits2Size(vector.m_nBits); i++)
                m_pBuffer[i] = vector.m_pBuffer[i];
        }
        void MemCopy(Vector<T> &vector)
        {
            if (m_pBuffer == NULL) {
                m_nBits = vector.m_nBits;
                m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
            }
            else if (m_nBits < vector.m_nBits) {
                delete[] m_pBuffer;
                m_nBits = vector.m_nBits;
                m_pBuffer = new T[VECTOR_bits2Size(m_nBits)];
            }

            memcpy(m_pBuffer, vector.m_pBuffer, sizeof(T)*VECTOR_bits2Size(m_nBits));
        }
        void BufferOutside(T* &p_pt)
        {
            p_pt = m_pBuffer;
            m_pBuffer = NULL;
            new (this) Vector();
        }
    };

    template <typename T>
    class Array : public Vector<T>
    {
    public:
        int m_nTop; 
    public:
        Array(int size = DEFAULE_VECTOR_SIZE) : Vector<T>(size)
        {
            m_nTop = -1;
        }
        Array(Array &array) { Copy(array); }
        Array(T* pbuf, int n) { Copy(pbuf, n); }
        ~Array() { m_nTop = -1; }
        T& operator [](int i)
        {
            if (i < 0) {
                cout << "[warning] the index less than 0: i=" << i << endl;
                /*#ifdef _DEBUG*/
                //getch();
                /*#endif*/
                i = 0;
            }

            if (i > m_nTop)
                m_nTop = i;

            return this->Get(i);
        }
        void SetNum(int n) { this->Get(n - 1); m_nTop = n - 1; }
        int GetNum() const { return m_nTop + 1; }
        void Add(T t) { (*this)[m_nTop + 1] = t; }
        T& Add() { return (*this)[m_nTop + 1]; }
        void Add(Array<T> &a) { for (int i = 0; i < a.GetNum(); i++) { Add(a[i]); } }
        int Find(T t) {
            for (int i = 0; i < GetNum(); i++) {
                if ((*this)[i] == t)
                    return i;
            }
            return -1;
        }
        T& End() { return (*this)[m_nTop]; }
        void Clean() { m_nTop = -1; }
        void Copy(const Array<T> &array)
        {
            Vector<T>::Copy(array);
            m_nTop = array.m_nTop;
        }
        void Copy(const T* pbuf, int n)
        {
            Clean();
            for (int i = 0; i < n; i++)
                (*this)[i] = pbuf[i];
        }
        void MemCopy(Array<T> &array)
        {
            Vector<T>::MemCopy(array);
            m_nTop = array.m_nTop;
        }
        void operator = (const Array<T> &array) { Copy(array); }
        operator T* () { return this->GetBuffer(); }
        void Output(ostream &os)
        {
            for (int i = 0; i < GetNum(); i++) {
                os << this->Get(i) << " ";
            }
        }
        void Input(istream &is)
        {
            T t;
            while (is >> t) {
                Add(t);
            }
        }
        void Insert(T t)
        {
            for (int i = 0; i < GetNum(); i++) {
                if ((*this)[i] == t) {
                    return;
                }
            }
            Add(t);
        }
        T Sum()
        {
            T sum = 0;
            for (int i = 0; i < GetNum(); i++) {
                sum += (*this)[i];
            }
            return sum;
        }
        T Max(int &idx) {
            if (GetNum() == 0) {
                idx = -1;
                return 0;
            }

            idx = 0;
            for (int i = 1; i < GetNum(); i++) {
                if (this->Get(i) > this->Get(idx)) {
                    idx = i;
                }
            }
            return this->Get(idx);
        }
        T Min(int &idx)
        {
            if (GetNum() == 0) {
                idx = -1;
                return 0;
            }

            idx = 0;
            for (int i = 1; i < GetNum(); i++) {
                if (this->Get(i) < this->Get(idx)) {
                    idx = i;
                }
            }
            return this->Get(idx);
        }
    };

    template <typename T>
    class DArray : public Vector<T>
    {
    public:
        int m_nXDim; 
        int m_nYDim; 
        DArray(int x_size = DEFAULE_VECTOR_SIZE, int y_size = DEFAULE_VECTOR_SIZE) : Vector<T>(x_size*y_size)
        {
            m_nXDim = x_size;
            m_nYDim = y_size;
        }
        T& Get(int i, int j)
        {
            return Vector<T>::Get(i*m_nYDim + j);
        }
    };

    template <typename T>
    class Stack : public Vector<T>
    {
    public:
        int m_nTop; 
        Stack(int size = DEFAULE_VECTOR_SIZE) : Vector<T>(size)
        {
            m_nTop = 0;
        }
        void Clean() { m_nTop = 0; }
        void Push(T p_t)
        {
            this->Get(m_nTop) = p_t;
            m_nTop++;
        }
        bool Pop(T *p_pT)
        {
            if (m_nTop == 0)
                return false;

            if (p_pT != NULL)
                *p_pT = this->Get(m_nTop - 1);

            m_nTop--;
            return true;
        }
        T Top()
        {
            if (m_nTop == 0)
                return this->Get(0);
            return this->Get(m_nTop - 1);
        }
        int GetNum() const { return m_nTop; }
    };

    template <typename T>
    class Queue : public Vector<T>
    {
    public:
        int m_nTop; 
        int m_nBottom; 
        Queue(int size = DEFAULE_VECTOR_SIZE) : Vector<T>(size)
        {
            m_nTop = 0;
            m_nBottom = 0;
        }
        void Clean() { m_nTop = 0; m_nBottom = 0; }
        void In(T p_t)
        {
            this->Get(m_nTop) = p_t;
            m_nTop++;
        }
        bool Out(T *p_pT)
        {
            if (m_nBottom == m_nTop)
                return false;
            if (p_pT)
                *p_pT = this->Get(m_nBottom);
            m_nBottom++;
            return true;
        }
        bool IsEmpty()
        {
            return m_nBottom == m_nTop;
        }
        int GetNum() { return m_nTop - m_nBottom; }
    };


    template <typename T>
    class CirQueue : Vector<T>
    {
    private:
        int nSize; 
        bool bFull; 
    public:
        int nHead; 
        int nTail; 
    public:
        CirQueue(int size = 10) :Vector<T>(size)
        {
            nHead = 0;
            nTail = 0;
            bFull = false;
            nSize = size;
        }
        void Init(int size)
        {
            Clean();
            this->Get(size);
            nSize = size;
        }
        void Clean()
        {
            nHead = 0;
            nTail = 0;
            bFull = false;
        }
        void In(T t)
        {
            if (!bFull) {
                this->Get(nTail) = t;
                nTail = (nTail + 1) % nSize;
                if (nTail == nHead)
                    bFull = true;
            }
            else {
                Out();
                In(t);
            }
        }
        bool Out(T *t = NULL)
        {
            if (!bFull) {
                if (nHead == nTail) {
                    // empty
                    return false;
                }
                else {
                    if (t) *t = this->Get(nHead);
                    nHead = (nHead + 1) % nSize;
                    return true;
                }
            }
            else {
                if (t) *t = this->Get(nHead);
                nHead = (nHead + 1) % nSize;
                bFull = false;
                return true;
            }
        }
        bool IsEmpty() { return (!bFull) && nHead == nTail; }
        bool IsFull() { return bFull; }
        int GetNum() { return (bFull) ? nSize : max(nTail - nHead, nTail + nSize - nHead); }
        int GetSize() { return nSize; }
        T GetSum()
        {
            T sum = 0;
            if (bFull) {
                for (int i = 0; i < nSize; i++)
                    sum += this->Get(i);
            }
            else {
                for (int i = nHead; i != nTail; i = (i + 1) % nSize)
                    sum += this->Get(i);
            }
            return sum;
        }
    };

    template <typename T>
    double VecNorm(T *pVec, int len)
    {
        double sum = 0;
        for (int i = 0; i < len; i++) {
            sum += pVec[i] * pVec[i];
        }
        return sqrt(sum);
    }
    template <typename T>
    double VecDot(T *pVec1, T *pVec2, int len)
    {
        double sum = 0;
        for (int i = 0; i < len; i++) {
            sum += pVec1[i] * pVec2[i];
        }
        return sum;
    }
    template <typename T>
    double VecDiff(T *pVec1, T*pVec2, int len)
    {
        double sum = 0;
        for (int i = 0; i < len; i++) {
            sum += pow(pVec1[i] - pVec2[i], 2);
        }
        return sqrt(sum);
    }
    template <typename T>
    double VecAngle(T *pVec1, T* pVec2, int len)
    {
        double sum = Dot(pVec1, pVec2, len);
        return sum / Norm(pVec1, len) / Norm(pVec2, len);
    }
    template <typename T>
    void VecUnfold(const char *pStr, Array<T> &a)
    {
        a.Clean();

        if (pStr == NULL)
            return;

        Array<char*> aStr;
        char *pStrDup = strdup(pStr);
        char *p = strtok(pStrDup, "[], ");
        while (p) {
            aStr.Add() = strdup(p);
            p = strtok(NULL, "[], ");
        }
        free(pStrDup);

        for (int i = 0; i < aStr.GetNum(); i++) {
            Array<double> d;
            char *p = strtok(aStr[i], ": ");
            while (p) {
                d.Add((T)atof(p));
                p = strtok(NULL, ": ");
            }

            double t = 0;
            switch (d.GetNum()) {
            case 1: a.Add(d[0]); break;
            case 2:
                for (t = d[0]; t <= d[1]; t += 1)
                    a.Add(t);
                break;
            case 3:
                for (t = d[0]; t <= d[2]; t += d[1])
                    a.Add(t);
                break;
            default:
                cout << "Error vector expression!! =>" << pStr << endl;
                exit(1);
            }

        }

        for (int i = 0; i < aStr.GetNum(); i++) {
            free(aStr[i]);
        }
    }

    template <typename T>
    int  Compar_Inc(const T& a, const T& b)
    {
        if (a > b) return 1;
        else return -1;
    }
    template <typename T>
    int Compar_Dec(const T& a, const T& b)
    {
        if (a > b) return -1;
        else return 1;
    }

    /*
        \param [in] p the input array
        \param [in] low the smallest index needed to be sorted, (commonly = 0)
        \param [in] high the largest index needed to be sorted, (commonly = the length - 1)
        \param [in] compar the compar function. Set to 'Compar_Inc' for increase and 'Compar_Dec' for decrease
    */
    template <typename T>
    void Qsort(T *p, int low, int high, int(*compar)(const T&, const T&) = Compar_Inc)
    {
        if (low >= high)
        {
            return;
        }
        int first = low;
        int last = high;
        T key = p[first];

        while (first < last)
        {
            while (first < last && compar(p[last], key) >= 0)
            {
                --last;
            }

            p[first] = p[last];

            while (first < last && compar(p[first], key) <= 0)
            {
                ++first;
            }

            p[last] = p[first];

        }
        p[first] = key;
        Qsort(p, low, first - 1, compar);
        Qsort(p, first + 1, high, compar);
    }
    template <typename T>
    void Qsort(Array<T> &a, int(*compar)(const T&, const T&) = Compar_Inc)
    {
        Qsort(a.GetBuffer(), 0, a.GetNum() - 1, compar);
    }


}

#endif