HeapTreeType.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_TYPE_H_
#define HEAP_TREE_TYPE_H_

#include <stdlib.h>
#include <iostream>
#include <math.h>

//#include "Array.H"
#include <vector>

using namespace std;

#include <assert.h>

class HeapTreeCell{
public:
    unsigned int level; 
    unsigned int child; 

//    /** Overloads the output operator.
//    This is usefull for debugging.
//    \param c The ostream to output to
//    \param cell The cell to put into the ostream
//    \return A reference to the ostream for further operations.
//    */
//    friend ostream& operator<<(ostream& c, const HeapTreeCell& cell);
};
//ostream& operator<<(ostream& c, const HeapTreeCell& cell){
//    c<<"("<<cell.level<<", "<<cell.child<<")";
//}

template<class HT_TYPE>
class HeapTreeType : protected vector<HT_TYPE> {
    float base;

    void swapIfBigger(unsigned int index){
        //this-> dump(); cout<<endl;
        HeapTreeCell childL, childR;
        findChildren(index, childL, childR);
        unsigned int indexL, indexR;
        indexL=findIndex(childL); indexR=findIndex(childR);
        int useIndexL=0, useIndexR=0;
        int res;
        if (indexL<unsortedCount)
                if ((*this)[index]<(*this)[indexL])
                    useIndexL=1;
        if (indexR<unsortedCount)
                if ((*this)[index]<(*this)[indexR])
                    useIndexR=1;
        if (useIndexR && useIndexL)
                if ((*this)[indexL]<(*this)[indexR])
                    useIndexL=0;
                else
                    useIndexR=0;
        if (useIndexL){
            swap(index,indexL);
            swapIfBigger(indexL);
        }
        if (useIndexR){
            swap(index,indexR);
            swapIfBigger(indexR);
        }
    }
protected:
    int unsortedCount;

    void swap(unsigned int one, unsigned int two){
        HT_TYPE temp=(*this)[one];
        (*this)[one]=(*this)[two];
        (*this)[two]=temp;
    }

public:
    HeapTreeType(int baseIn=2) {
        assert(baseIn==2);
        base=(float)baseIn; // binary tree
        deleteElements();
    }

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

    void findCell(unsigned int index, HeapTreeCell &cell){
        findCell(&(*this)[index], cell);
    }

    void findCell(HT_TYPE* index, HeapTreeCell &cell){
        HT_TYPE* root=&(*this)[0];
        //cout<<"index="<<index<<'\t'<<"root="<<root<<"\tsizeof(HT_TYPE)="<<sizeof(HT_TYPE)<<"index-root"<<index-root<<endl;
        int location = (int)(index-root); // no need to divide by sizeof here
        cell.level=0;
//        cout<<"pow = "<<base<<"^"<<cell.level<<" = "<<pow(base,(float)cell.level)<<endl;
        while ((location-=(int)pow(base,(float)cell.level))>=0)
            cell.level++;
        location+=(int)pow(base,(float)cell.level);
        cell.child=location;
        return;
    }

    unsigned int findIndex(HeapTreeCell &cell){
        if (!cell.level) return 0;
        return (unsigned int)(pow(base,(float)cell.level)+cell.child-base+1.0);
    }

    unsigned int findParent(unsigned int index){
        if (!index){
            cerr<<"error: the root parent has no parent"<<endl;
            exit(-1);
        }
        HeapTreeCell child, parent;
        findCell(index, child); // find the cell of the child
        parent.level=child.level-1;
        parent.child=(unsigned int)floor((float)child.child/base);
        return findIndex(parent);
    }

    void findChildren(unsigned int parent, HeapTreeCell& childL, HeapTreeCell& childR){
//        cout<<"findChildren"<<parent<<endl;
        HeapTreeCell cell;
        findCell(parent, cell);
        childL.level=cell.level+1; childR.level=cell.level+1;
        childL.child=cell.child*2; childR.child=cell.child*2+1;
    }

//    void parent(HT_TYPE* index, HeapTreeCell& cell){
//        HT_TYPE* root=&(*this)[0];
//        //cout<<"index="<<index<<'\t'<<"root="<<root<<"\tsizeof(HT_TYPE)="<<sizeof(HT_TYPE)<<"index-root"<<index-root<<endl;
//        unsigned int location = (int)(index-root); // no need to divide by sizeof here
//    }

    void dump(){
        for (int i=0;i<vector<HT_TYPE>::size();i++)
            cout<<(*this)[i]<<'\t';
    }

    void dumpDereference(){
        for (int i=0;i<vector<HT_TYPE>::size();i++)
            cout<<*((*this)[i])<<'\t';
    }

    void dumpLPR(HeapTreeCell& cell){
        HeapTreeCell childL, childR;
        unsigned int myIndex=findIndex(cell);
        findChildren(myIndex, childL, childR);
        if (findIndex(childL)<=unsortedCount)
            dumpLPR(childL);
        cout<<(*this)[myIndex]<<'\t';
        if (findIndex(childR)<=unsortedCount)
            dumpLPR(childR);
    }

    void sort(void){
                // store first and bubble up
        unsigned int unsortedCountOrig=unsortedCount;
        while (unsortedCount>0){
            unsigned int index=0;
            swap(index,unsortedCount);
            swapIfBigger(index);
            unsortedCount-=1;
            //this->dump();cout<<"\tsize="<<unsortedCount<<endl;
        }
    }

    void resize(size_t s, HT_TYPE c=HT_TYPE()){
        vector<HT_TYPE>::resize(s,c);
    }

    virtual void deleteElements(void){
        this->resize(0);
        unsortedCount=-1;
    }


//    HeapTreeType &operator<<=(HT_TYPE var){
//        add(var);
//        return *this;
//    }
//

//    HT_TYPE operator[](int i){
//        return vector<HT_TYPE>::operator[](i);
//    }
//
//    HT_TYPE operator[](int i){
//        if (i>unsortedCount){
//            cerr<<"ERROR: Current tree unsortedCount = "<<unsortedCount<<" you requested index = "<<i<<endl;
//            assert(-1);
//        }
//        return (*this)[i];
//    }
};
#endif //HEAP_TREE_TYPE_H_