Marsyas  0.2
/home/gperciva/src/marsyas/src/marsyas/Heap.h
00001 /*
00002 ** Copyright (C) 1998-2006 George Tzanetakis <gtzan@cs.uvic.ca>
00003 **  
00004 ** This program is free software; you can redistribute it and/or modify
00005 ** it under the terms of the GNU General Public License as published by
00006 ** the Free Software Foundation; either version 2 of the License, or
00007 ** (at your option) any later version.
00008 ** 
00009 ** This program is distributed in the hope that it will be useful,
00010 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012 ** GNU General Public License for more details.
00013 ** 
00014 ** You should have received a copy of the GNU General Public License
00015 ** along with this program; if not, write to the Free Software 
00016 ** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00017 */
00018 
00027 #define is_root(_ND) (_ND->m_id==1)
00028 #define odd_id(_ND) (_ND->m_id & 1)
00029 #define is_lchild(_ND) ((_ND!=NULL)&&!(is_root(_ND))&&(!odd_id(_ND)))
00030 #define is_rchild(_ND) ((_ND!=NULL)&&!(is_root(_ND))&&( odd_id(_ND)))
00031 
00032 //only  relevant for WIN32 MSVC (and ignored by all other platforms)
00033 //For more info about the reason for this #pragma consult:
00034 //http://msdn2.microsoft.com/en-us/library/sa28fef8.aspx
00035 
00036 
00037 /* This is heap is designed to sort pointers to objects.
00038    The heap template requires a Type, a Comparator object for determining Type
00039    ordering, and a Destructor object for destroying Type objects still in the
00040    heap once the program finishes.
00041 
00042    Examples of Comparator and Destructor objects for Heap declaration:
00043 
00044     Heap<Object, Comp, Destr> h;
00045 
00046     class Comp {
00047     public:
00048         bool operator()(Object* a, Object* b) { return (a->m_id()) < (b->m_id()); }
00049     };
00050     class Destr {
00051     public:
00052         void operator()(Object* a) { delete(a); }
00053     };
00054 */
00055 
00056 namespace Marsyas
00057 {
00058 
00059 template <typename Type, typename Comparator>
00060 class Heap {
00061 private:
00062     class Node {
00063     public:
00064         Node* parent; Node* lchild; Node* rchild; // tree pointers
00065         Node* prev; Node* next; // vector list pointers
00066         unsigned int m_id; // node id, for determining child type
00067         Type* data;
00068         Node(unsigned int node_id, Type* d) {
00069             parent=NULL; lchild=NULL; rchild=NULL;
00070             prev=NULL; next=NULL;
00071             data=d; m_id=node_id;
00072         }
00073         ~Node() { }
00074         friend std::ostream& operator<<(std::ostream& o, Node* s) {
00075             o << "<" << s->m_id << "," << s->data << ",(";
00076             if (s->parent==NULL) { o<<"0"; } else { o<<s->parent->m_id; } o << ",";
00077             if (s->lchild==NULL) { o<<"x"; } else { o<<s->lchild->m_id; } o << ",";
00078             if (s->rchild==NULL) { o<<"x"; } else { o<<s->rchild->m_id; } o << ")>";
00079             return o;
00080         };
00081     };
00082 
00083 public:
00084 
00085     Node* first; Node* last; // first and last pointers in heap
00086     // assigned to a node to identify root, l/r child.
00087     // An empty tree has a count of 0, while the root node is always 1.
00088     unsigned int node_count;
00089     // name declaration for required Comparator object
00090     Comparator cmp;
00091 
00092     Heap() { first=NULL; last=NULL; node_count=0; }
00093     virtual ~Heap() {
00094         while(first!=NULL) {
00095             last=first->next;
00096             // use the supplied Destructor object to delete the data
00097             delete(first->data); delete(first);
00098             first=last;
00099         }
00100     }
00101 
00102     bool empty() { return (node_count==0); };
00103 
00104     Type* top() {
00105     // on empty heap throw a const char* exception, specified in the contract
00106         if (first==NULL) { throw "Heap::top()  empty heap exception."; }
00107         else { return first->data; }
00108     };
00109     Type* pop() {
00110     // on empty heap throw a const char* exception, specified in the contract
00111         if (first==NULL) { throw "Heap::pop()  empty heap exception."; }
00112         // save top data
00113         Type* data = first->data;
00114         // if it's the root then clear the heap
00115         if (is_root(last)) {
00116             delete(last); first=NULL; last=NULL; node_count=0;
00117         }
00118         else {
00119             // swap last element data into top position
00120             first->data = last->data;
00121             // extricate the node from its parent
00122             if (is_lchild(last)) { last->parent->lchild=NULL; }
00123             else { last->parent->rchild=NULL; }
00124             // remove the last node and update the pointer to the new last
00125             last=last->prev; delete(last->next); last->next=NULL;
00126             // bubble down
00127             Node* f = first;
00128             while (1) {
00129                 Node* c = f->lchild;
00130                 // if lchild of c==NULL then c cannot be bubbled down further
00131                 if (c==NULL) { break; }
00132                 // make f point to the smallest of c's children
00133                 if (f->rchild!=NULL && (cmp(f->rchild->data,c->data))) { c=f->rchild; }
00134                 // use the template required Comparator to compare if the
00135                 // smallest child of c is less, if not leave
00136                 if (cmp(f->data,c->data)) { break; }
00137                 // swap data
00138                 Type* sw=c->data; c->data=f->data; f->data=sw;
00139                 // track the bubbling node
00140                 f=c;
00141             }
00142             // update node_count ensuring it never goes below 0
00143             node_count = (node_count>0) ? node_count-1 : 0;
00144         }
00145         return data;
00146     };
00147     // push
00148     void push(Type* data) {
00149         // could throw an exception here...hmm
00150         if (data==NULL) { return; }
00151         node_count++;
00152 
00153         Node* n = new Node(node_count,data);
00154         if (first==NULL) {
00155             first=n; last=n;
00156         }
00157         else {
00158             // add node to end of list
00159             last->next=n; n->prev=last;
00160             // insert node into tree and update parent and parent_children
00161             if (is_root(last)) {
00162                 n->parent=last;
00163                 last->lchild = n;
00164             }
00165             else if (is_lchild(last)) {
00166                 n->parent=last->parent;
00167                 last->parent->rchild=n;
00168             }
00169             else {
00170                 n->parent=last->parent->next;
00171                 last->parent->next->lchild=n;
00172             }
00173             last=n;
00174             // bubble up if needed
00175             while (!is_root(n) && cmp(n->data,n->parent->data)) {
00176                 Type* sw=n->data; n->data=n->parent->data; n->parent->data=sw;
00177                 n = n->parent;
00178             }
00179         }
00180     };
00181     friend std::ostream& operator<<(std::ostream& o, Heap& s) {
00182         Node* c = s.first;
00183         while (c!=NULL) { o << c; c = c->next; } o << "\n";
00184         return o;
00185     };
00186 };
00187 
00188 }//namespace Marsyas
00189 
00190 //only  relevant for WIN32 MSVC (and ignored by all other platforms)
00191 //For more info about the reason for this #pragma consult:
00192 //http://msdn2.microsoft.com/en-us/library/sa28fef8.aspx
00193