HeapTree.H

Go to the documentation of this file.

/* Copyright 2000-2018 Matt Flax <flatmax@flatmax.org>
   This file is part of GTK+ IOStream class set

   GTK+ IOStream is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   GTK+ IOStream is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You have received a copy of the GNU General Public License
   along with GTK+ IOStream
*/
#ifndef HEAP_TREE_H_
#define HEAP_TREE_H_

#include "HeapTreeType.H"
#include "LinkList.H"

template<class HT_TYPE>
class HeapTree : public HeapTreeType<HT_TYPE*> {
    typedef int(HT_TYPE::*HTCompareMethod)(const HT_TYPE&)const;

    void swapIfBigger(unsigned int index, HTCompareMethod compare){
        HeapTreeCell childL, childR;
        HeapTreeType<HT_TYPE*>::findChildren(index, childL, childR);
        unsigned int indexL=HeapTreeType<HT_TYPE*>::findIndex(childL);
        unsigned int indexR=HeapTreeType<HT_TYPE*>::findIndex(childR);
        //cout<<"indexL "<<indexL<<"indexR "<<indexR<<endl;
        int useIndexL=0, useIndexR=0;
        int res;
        if (indexL<HeapTreeType<HT_TYPE*>::unsortedCount){
            //    cout<<"indexL "<<(*(*this)[index])<<'\t'<<(*(*this)[indexL])<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexL])<<endl;
                if (((*(*this)[index]).*compare)(*(*this)[indexL])<0)
                    useIndexL=1;
        }
        if (indexR<HeapTreeType<HT_TYPE*>::unsortedCount){
          //      cout<<"indexR "<<*(*this)[index]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexR])<<endl;
                if (((*(*this)[index]).*compare)(*(*this)[indexR])<0)
                    useIndexR=1;
        }
        if (useIndexR && useIndexL){
        //        cout<<"indexLR "<<*(*this)[indexL]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[indexL].*compare)(*(*this)[indexR])<<endl;
                if (((*(*this)[indexL]).*compare)(*(*this)[indexR])<0)
                    useIndexL=0;
                else
                    useIndexR=0;
        }
        if (useIndexL){
//                cout<<"before index indexL "<<*(*this)[index]<<'\t'<<*(*this)[indexL]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexL])<<endl;
            HeapTreeType<HT_TYPE*>::swap(index,indexL);
  //              cout<<"after index indexL "<<*(*this)[index]<<'\t'<<*(*this)[indexL]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexL])<<endl;
            swapIfBigger(indexL, compare);
        }
        if (useIndexR){
    //            cout<<"before index indexR "<<*(*this)[index]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexR])<<endl;
            HeapTreeType<HT_TYPE*>::swap(index,indexR);
      //          cout<<"after index indexR "<<*(*this)[index]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexR])<<endl;
            swapIfBigger(indexR, compare);
        }
    }
public:

    HeapTree(int baseIn=2) : HeapTreeType<HT_TYPE*>(baseIn) {
    }


    void add(HT_TYPE *value, HTCompareMethod compare){
        HeapTreeType<HT_TYPE*>::unsortedCount+=1; // add
        if (HeapTreeType<HT_TYPE*>::unsortedCount+1>vector<HT_TYPE*>::size())
            vector<HT_TYPE*>::resize(HeapTreeType<HT_TYPE*>::unsortedCount+1);
        (*this)[HeapTreeType<HT_TYPE*>::unsortedCount]=value;
        // bubble up
        int index=HeapTreeType<HT_TYPE*>::unsortedCount;
            //this->dump(); cout<<endl;
        while (index>0){
            int parent=HeapTreeType<HT_TYPE*>::findParent(index);
            if ((*(*this)[parent].*compare)(*(*this)[index])<0){
                HeapTreeType<HT_TYPE*>::swap(parent, index);
                index=parent;
            //this->dump(); cout<<endl;
            } else
                break;
        }
            //this->dump(); cout<<endl;
    }

    void sort(HTCompareMethod compare){
                // store first and bubble up
        unsigned int sizeOrig=HeapTreeType<HT_TYPE*>::unsortedCount;
        while (HeapTreeType<HT_TYPE*>::unsortedCount>0){
            unsigned int index=0;
            HeapTreeType<HT_TYPE*>::swap(index,HeapTreeType<HT_TYPE*>::unsortedCount);
            swapIfBigger(index, compare);
            HeapTreeType<HT_TYPE*>::unsortedCount-=1;
            //this->dump();
//            cout<<"\tunsortedCount="<<HeapTreeType<HT_TYPE*>::unsortedCount<<endl;
        }
    }

    void sort(LinkList<HT_TYPE *> &ll, HTCompareMethod compare){
        if (vector<HT_TYPE*>::size()!=ll.getCount()) // ensure the vector size matches
            resize(ll.getCount());
        while (ll.getCount()) // load the vector
            add(ll.remove(),compare);
        sort(compare); // sort
        for (int i=0; i<vector<HT_TYPE*>::size(); i++) // unload the vector
            ll.add((*this)[i]);
        HeapTreeType<HT_TYPE*>::deleteElements();
    }

    void deleteElements(void){
        for (int i=0;i<HeapTreeType<HT_TYPE*>::unsortedCount; i++){
            delete (*this)[i];
            (*this)[i]=NULL;
        }
        HeapTreeType<HT_TYPE*>::deleteElements();
    }
//    /** Run through the vector and output (to cout) the HT_TYPE tree element.
//    */
//    void dump(){
//        for (int i=0;i<(HeapTreeType<HT_TYPE*>::vector<HT_TYPE>::size());i++)
//            cout<<*(HeapTreeType<HT_TYPE*>::vector<HT_TYPE>::operator[](i))<<'\t';
//    }

//    HT_TYPE operator[](int i){
//        return HeapTreeType<HT_TYPE*>::operator[](i);
//    }
};
#endif //HEAP_TREE_H_