/**  Copyright Mikael Högdahl - triyana@users.sourceforge.net
*
*  This source is distributed under the terms of the Q Public License version 1.0,
*  created by Trolltech (www.trolltech.com).
*/

#ifndef MHVECTOR_H
#define MHVECTOR_H

#include "MH.h"
#include "MHString.h"




/**
*  A simple vector class, inherit stored objects from MH interface which
*  describes the compare mthod for sorting
*/
class MHVector : public MH {
public:
    enum {
                        FIND_EXACT = 0,
                        FIND_BEFORE,
                        FIND_AFTER,
                        SEARCH_ALL
    };

                        MHVector () {create(10);}
                        MHVector (int n) {create(n);}
    virtual             ~MHVector () {Empty();}

    MH*                 operator[](int i) {return aVector[i];}

    int                 Capacity () {return aCapacity;}
    const char*         Class () {return "MHVector";}
    int                 Compare (const MH* o, int type);
    void                Empty ();
    void                Empty (int index) {Pop (index);}
    void                Erase ();
    void                Erase (int index);
    void                Erase (MH* o);
    MH*                 Find (const MH* o, int exact, int type = 0, int* mid = 0);
    MH*                 Find (const char* key) {MHString s(key); return Find(&s, FIND_EXACT);}
    MH*                 First() {if (aSize > 0) return aVector[0]; else return 0;}
    MH*                 Get (int i) {if (i >= 0 && i < aSize) return aVector[i]; else return 0;}
    int                 GetSortType () {return aSortType;}
    void                HeapSort (int type = 0) {aSortType = type; MHVector::heapSort (aVector, aSize);}
    void                Insert (MH* node, int pos = 0);
    void                InsertSorted (MH* node, int type = 0);
    MH*                 Last() {if (aSize > 0) return aVector[aSize - 1]; else return 0;}
    void                Push (MH* node);
    MH*                 Pop ();
    MH*                 Pop (int index);
    MH*                 Pop (MH* o);
    void                Resize(int size);
    void                Reverse ();
    MH*                 Search (const MH* o, int exact, int type = 0, int* mid = 0);
    MH*                 Search (const char* key) {MHString s(key); return Search(&s, SEARCH_ALL);}
    MH*                 Set (int i, MH* o) {if (i >= 0 && i < aSize) {MH* o2 = aVector[i]; aVector[i] = o; return o2;} else return 0;}
    void                SetSortType (int type) {aSortType = type;}
    int                 Size() {return aSize;}
    void                Sort (int type = 0) {MHVector::QuickSort (type);}
    void                Sort (int type, int col) {aaSortVectorCol = col; MHVector::QuickSort (type);}
    void                QuickSort (int type = 0) {aSortType = type; MHVector::quickSort (aSortType, aVector, 0, aSize - 1); insertionSort(aVector, 0, aSize - 1);}

private:
    int                 aSize;
    int                 aCapacity;
    int                 aSortType;
    MH**                aVector;
    static int          aaSortVectorCol;

    void                create (int capacity);
    void                heapSort (MH** ve, int size);
    void                insertionSort (MH** ve, int lo0, int hi0);
    static void         swap (MH** ve, int a, int b);
    static void         siftDown (int type, MH** ve, int root, int bottom);
    static void         quickSort (int type, MH** ve, int left, int right);
};

#endif