Array.h

Go to the documentation of this file.

/*
 * $Revision: 2047 $
 * 
 * last checkin:
 *   $Author: klein $ 
 *   $Date: 2010-10-13 17:12:21 +0200 (Wed, 13 Oct 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_ARRAY_H
#define OGDF_ARRAY_H


#include <ogdf/basic/basic.h>


namespace ogdf {

const size_t maxSizeInsertionSort = 40;



#define forall_arrayindices(i, A) \
   for(i = (A).low(); i<=(A).high(); ++i)


#define forall_rev_arrayindices(i, A) \
   for(i = (A).high(); i>=(A).low(); --i)




template<class E, class INDEX = int> class Array {
public:
    Array() { construct(0,-1); }

    explicit Array(INDEX s) {
        construct(0,s-1); initialize();
    }

    Array(INDEX a, INDEX b) {
        construct(a,b); initialize();
    }

    Array(INDEX a, INDEX b, const E &x) {
        construct(a,b); initialize(x);
    }

    Array(const Array<E> &A) {
        copy(A);
    }

    // destruction
    ~Array() {
        deconstruct();
    }

    INDEX low() const { return m_low; }

    INDEX high() const { return m_high; }

    INDEX size() const { return m_high - m_low + 1; }

    E *begin() { return m_pStart; }

    const E *begin() const { return m_pStart; }

    E *end() { return m_pStop; }

    const E *end() const { return m_pStop; }

    E *rbegin() { return m_pStop-1; }

    const E *rbegin() const { return m_pStop-1; }

    E *rend() { return m_pStart-1; }

    const E *rend() const { return m_pStart-1; }

    const E &operator[](INDEX i) const {
        OGDF_ASSERT(m_low <= i && i <= m_high)
        return m_vpStart[i];
    }

    E &operator[](INDEX i) {
        OGDF_ASSERT(m_low <= i && i <= m_high)
        return m_vpStart[i];
    }

    void swap(INDEX i, INDEX j) {
        OGDF_ASSERT(m_low <= i && i <= m_high)
        OGDF_ASSERT(m_low <= j && j <= m_high)

        std::swap(m_vpStart[i], m_vpStart[j]);
    }

    void init() { init(0,-1); }
    

    void init(INDEX s) { init(0,s-1); }


    void init(INDEX a, INDEX b) {
        deconstruct();
        construct(a,b);
        initialize();
    }

    void init(INDEX a, INDEX b, const E &x) {
        deconstruct();
        construct(a,b);
        initialize(x);
    }

    Array<E,INDEX> &operator=(const Array<E,INDEX> &array2) {
        deconstruct();
        copy(array2);
        return *this;
    }

    void fill(const E &x) {
        E *pDest = m_pStop;
        while(pDest > m_pStart)
            *--pDest = x;
    }

    void fill(INDEX i, INDEX j, const E &x) {
        OGDF_ASSERT(m_low <= i && i <= m_high)
        OGDF_ASSERT(m_low <= j && j <= m_high)

        E *pI = m_vpStart + i, *pJ = m_vpStart + j+1;
        while(pJ > pI)
            *--pJ = x;
    }


    void grow(INDEX add, const E &x);


    void grow(INDEX add);

    void permute (INDEX l, INDEX r);

    void permute() {
        permute(low(), high());
    }
    

    inline int binarySearch (const E& x) const {
        return binarySearch(x, StdComparer<E>());
    }


    template<class COMPARER>
    int binarySearch(const E& e, const COMPARER &comp) const {
        if(size() < 2) {
            if(size() == 1 && comp.equal(e, m_vpStart[low()]))
                return low();
            return low()-1;
        }
        int l = low();
        int r = high();
        do {
            int m = (r + l)/2;
            if(comp.greater(e, m_vpStart[m]))
                l = m+1;
            else
                r = m;
        } while(r>l);
        return comp.equal(e, m_vpStart[l]) ? l : low()-1;
    }


    inline int linearSearch (const E& e) const {
        int i;
        for(i = size(); i-->0;)
            if(e == m_pStart[i]) break;
        return i+low(); }


    template<class COMPARER>
    int linearSearch(const E& e, const COMPARER &comp) const {
        int i;
        for(i = size(); i-->0;)
            if(comp.equal(e, m_pStart[i])) break;
        return i+low();
    }

    inline void quicksort() {
        quicksort(StdComparer<E>());
    }

    inline void quicksort(INDEX l, INDEX r) {
        quicksort(l, r, StdComparer<E>());
    }


    template<class COMPARER>
    inline void quicksort(const COMPARER &comp) {
        if(low() < high())
            quicksortInt(m_pStart,m_pStop-1,comp);
    }


    template<class COMPARER>
    void quicksort(INDEX l, INDEX r, const COMPARER &comp) {
        OGDF_ASSERT(low() <= l && l <= high())
        OGDF_ASSERT(low() <= r && r <= high())      
        if(l < r)
            quicksortInt(m_vpStart+l,m_vpStart+r,comp);
    }

    template<class F, class I> friend class ArrayBuffer; // for efficient ArrayBuffer::compact-method

private:
    E *m_vpStart; 
    E *m_pStart;  
    E *m_pStop;   
    INDEX m_low;    
    INDEX m_high;   

    void construct(INDEX a, INDEX b);

    void initialize();

    void initialize(const E &x);

    void deconstruct();

    void copy(const Array<E,INDEX> &A);

    template<class COMPARER>
    static void quicksortInt(E *pL, E *pR, const COMPARER &comp) {
        size_t s = pR-pL;

        // use insertion sort for small instances
        if (s < maxSizeInsertionSort) {
            for (E *pI = pL+1; pI <= pR; pI++) {
                E v = *pI; 
                E *pJ = pI;
                while (--pJ >= pL && comp.less(v,*pJ)) {
                    *(pJ+1) = *pJ;
                }
                *(pJ+1) = v;
            }
            return;
        }

        E *pI = pL, *pJ = pR;
        E x = *(pL+(s>>1));

        do {
            while (comp.less(*pI,x)) pI++;
            while (comp.less(x,*pJ)) pJ--;
            if (pI <= pJ) std::swap(*pI++,*pJ--);
        } while (pI <= pJ);

        if (pL < pJ) quicksortInt(pL,pJ,comp);
        if (pI < pR) quicksortInt(pI,pR,comp);
    }

    OGDF_NEW_DELETE
}; // class Array




// enlarges array by add elements and sets new elements to x
template<class E, class INDEX>
void Array<E,INDEX>::grow(INDEX add, const E &x)
{
    INDEX sOld = size(), sNew = sOld + add;

    // expand allocated memory block
    if(m_pStart != 0) {
        E *p = (E *)realloc(m_pStart, sNew*sizeof(E));
        if(p == 0) OGDF_THROW(InsufficientMemoryException);
        m_pStart = p;
    } else {
        m_pStart = (E *)malloc(sNew*sizeof(E));
        if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
    }

    m_vpStart = m_pStart-m_low;
    m_pStop   = m_pStart+sNew;
    m_high   += add;

    // initialize new array entries
    for (E *pDest = m_pStart+sOld; pDest < m_pStop; pDest++)
        new (pDest) E(x);
}

// enlarges array by add elements (initialized with default constructor)
template<class E, class INDEX>
void Array<E,INDEX>::grow(INDEX add)
{
    INDEX sOld = size(), sNew = sOld + add;

    // expand allocated memory block
    if(m_pStart != 0) {
        E *p = (E *)realloc(m_pStart, sNew*sizeof(E));
        if(p == 0) OGDF_THROW(InsufficientMemoryException);
        m_pStart = p;
    } else {
        m_pStart = (E *)malloc(sNew*sizeof(E));
        if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
    }

    m_vpStart = m_pStart-m_low;
    m_pStop   = m_pStart+sNew;
    m_high   += add;

    // initialize new array entries
    for (E *pDest = m_pStart+sOld; pDest < m_pStop; pDest++)
        new (pDest) E;
}

template<class E, class INDEX>
void Array<E,INDEX>::construct(INDEX a, INDEX b)
{
    m_low = a; m_high = b;
    INDEX s = b-a+1;
    
    if (s < 1) {
        m_pStart = m_vpStart = m_pStop = 0;

    } else {
        m_pStart = (E *)malloc(s*sizeof(E));
        if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);

        m_vpStart = m_pStart - a;
        m_pStop = m_pStart + s;
    }
}


template<class E, class INDEX>
void Array<E,INDEX>::initialize()
{
    E *pDest = m_pStart;
    try {
        for (; pDest < m_pStop; pDest++)
            new(pDest) E;
    } catch (...) {
        while(--pDest >= m_pStart)
            pDest->~E();
        free(m_pStart);
        throw;
    }
}


template<class E, class INDEX>
void Array<E,INDEX>::initialize(const E &x)
{
    E *pDest = m_pStart;
    try {
        for (; pDest < m_pStop; pDest++)
            new(pDest) E(x);
    } catch (...) {
        while(--pDest >= m_pStart)
            pDest->~E();
        free(m_pStart);
        throw;
    }
}


template<class E, class INDEX>
void Array<E,INDEX>::deconstruct()
{
    if (doDestruction((E*)0)) {
        for (E *pDest = m_pStart; pDest < m_pStop; pDest++)
            pDest->~E();
    }
    free(m_pStart);
}


template<class E, class INDEX>
void Array<E,INDEX>::copy(const Array<E,INDEX> &array2)
{
    construct(array2.m_low, array2.m_high);

    if (m_pStart != 0) {
        E *pSrc = array2.m_pStop;
        E *pDest = m_pStop;
        while(pDest > m_pStart)
            //*--pDest = *--pSrc;
            new (--pDest) E(*--pSrc);
    }
}


// permutes array a from a[l] to a[r] randomly
template<class E, class INDEX>
void Array<E,INDEX>::permute (INDEX l, INDEX r)
{
    OGDF_ASSERT(low() <= l && l <= high())
    OGDF_ASSERT(low() <= r && r <= high())

    E *pI = m_vpStart+l, *pStart = m_vpStart+l, *pStop = m_vpStart+r;
    while(pI <= pStop)
        std::swap(*pI++,*(pStart+randomNumber(0,r-l)));
}


// prints array a to output stream os using delimiter delim
template<class E, class INDEX>
void print(ostream &os, const Array<E,INDEX> &a, char delim = ' ')
{
    for (int i = a.low(); i <= a.high(); i++) {
        if (i > a.low()) os << delim;
        os << a[i];
    }
}


// output operator
template<class E, class INDEX>
ostream &operator<<(ostream &os, const ogdf::Array<E,INDEX> &a)
{
    print(os,a);
    return os;
}

} // end namespace ogdf


#endif