Marsyas  0.6.0-alpha
/usr/src/RPM/BUILD/marsyas-0.6.0/src/marsyas/Heap.h
Go to the documentation of this file.
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 
00019 #define is_root(_ND) (_ND->m_id==1)
00020 #define odd_id(_ND) (_ND->m_id & 1)
00021 #define is_lchild(_ND) ((_ND!=NULL)&&!(is_root(_ND))&&(!odd_id(_ND)))
00022 #define is_rchild(_ND) ((_ND!=NULL)&&!(is_root(_ND))&&( odd_id(_ND)))
00023 
00024 //only  relevant for WIN32 MSVC (and ignored by all other platforms)
00025 //For more info about the reason for this #pragma consult:
00026 //http://msdn2.microsoft.com/en-us/library/sa28fef8.aspx
00027 
00028 
00029 /* This is heap is designed to sort pointers to objects.
00030    The heap template requires a Type, a Comparator object for determining Type
00031    ordering, and a Destructor object for destroying Type objects still in the
00032    heap once the program finishes.
00033 
00034    Examples of Comparator and Destructor objects for Heap declaration:
00035 
00036     Heap<Object, Comp, Destr> h;
00037 
00038     class Comp {
00039     public:
00040         bool operator()(Object* a, Object* b) { return (a->m_id()) < (b->m_id()); }
00041     };
00042     class Destr {
00043     public:
00044         void operator()(Object* a) { delete(a); }
00045     };
00046 */
00047 
00048 namespace Marsyas
00049 {
00056 template <typename Type, typename Comparator>
00057 class Heap {
00058 private:
00059   class Node {
00060   public:
00061     Node* parent; Node* lchild; Node* rchild; // tree pointers
00062     Node* prev; Node* next; // vector list pointers
00063     unsigned int m_id; // node id, for determining child type
00064     Type* data;
00065     Node(unsigned int node_id, Type* d) {
00066       parent=NULL; lchild=NULL; rchild=NULL;
00067       prev=NULL; next=NULL;
00068       data=d; m_id=node_id;
00069     }
00070     ~Node() { }
00071     friend std::ostream& operator<<(std::ostream& o, Node* s) {
00072       o << "<" << s->m_id << "," << s->data << ",(";
00073       if (s->parent==NULL) { o<<"0"; } else { o<<s->parent->m_id; } o << ",";
00074       if (s->lchild==NULL) { o<<"x"; } else { o<<s->lchild->m_id; } o << ",";
00075       if (s->rchild==NULL) { o<<"x"; } else { o<<s->rchild->m_id; } o << ")>";
00076       return o;
00077     };
00078   };
00079 
00080 public:
00081 
00082   Node* first; Node* last; // first and last pointers in heap
00083   // assigned to a node to identify root, l/r child.
00084   // An empty tree has a count of 0, while the root node is always 1.
00085   unsigned int node_count;
00086   // name declaration for required Comparator object
00087   Comparator cmp;
00088 
00089   Heap() { first=NULL; last=NULL; node_count=0; }
00090   virtual ~Heap() {
00091     while(first!=NULL) {
00092       last=first->next;
00093       // use the supplied Destructor object to delete the data
00094       delete(first->data); delete(first);
00095       first=last;
00096     }
00097   }
00098 
00099   bool empty() { return (node_count==0); };
00100 
00101   Type* top() {
00102     // on empty heap throw a const char* exception, specified in the contract
00103     if (first==NULL) { throw "Heap::top()  empty heap exception."; }
00104     else { return first->data; }
00105   };
00106   Type* pop() {
00107     // on empty heap throw a const char* exception, specified in the contract
00108     if (first==NULL) { throw "Heap::pop()  empty heap exception."; }
00109     // save top data
00110     Type* data = first->data;
00111     // if it's the root then clear the heap
00112     if (is_root(last)) {
00113       delete(last); first=NULL; last=NULL; node_count=0;
00114     }
00115     else {
00116       // swap last element data into top position
00117       first->data = last->data;
00118       // extricate the node from its parent
00119       if (is_lchild(last)) { last->parent->lchild=NULL; }
00120       else { last->parent->rchild=NULL; }
00121       // remove the last node and update the pointer to the new last
00122       last=last->prev; delete(last->next); last->next=NULL;
00123       // bubble down
00124       Node* f = first;
00125       while (1) {
00126         Node* c = f->lchild;
00127         // if lchild of c==NULL then c cannot be bubbled down further
00128         if (c==NULL) { break; }
00129         // make f point to the smallest of c's children
00130         if (f->rchild!=NULL && (cmp(f->rchild->data,c->data))) { c=f->rchild; }
00131         // use the template required Comparator to compare if the
00132         // smallest child of c is less, if not leave
00133         if (cmp(f->data,c->data)) { break; }
00134         // swap data
00135         Type* sw=c->data; c->data=f->data; f->data=sw;
00136         // track the bubbling node
00137         f=c;
00138       }
00139       // update node_count ensuring it never goes below 0
00140       node_count = (node_count>0) ? node_count-1 : 0;
00141     }
00142     return data;
00143   };
00144   // push
00145   void push(Type* data) {
00146     // could throw an exception here...hmm
00147     if (data==NULL) { return; }
00148     node_count++;
00149 
00150     Node* n = new Node(node_count,data);
00151     if (first==NULL) {
00152       first=n; last=n;
00153     }
00154     else {
00155       // add node to end of list
00156       last->next=n; n->prev=last;
00157       // insert node into tree and update parent and parent_children
00158       if (is_root(last)) {
00159         n->parent=last;
00160         last->lchild = n;
00161       }
00162       else if (is_lchild(last)) {
00163         n->parent=last->parent;
00164         last->parent->rchild=n;
00165       }
00166       else {
00167         n->parent=last->parent->next;
00168         last->parent->next->lchild=n;
00169       }
00170       last=n;
00171       // bubble up if needed
00172       while (!is_root(n) && cmp(n->data,n->parent->data)) {
00173         Type* sw=n->data; n->data=n->parent->data; n->parent->data=sw;
00174         n = n->parent;
00175       }
00176     }
00177   };
00178   friend std::ostream& operator<<(std::ostream& o, Heap& s) {
00179     Node* c = s.first;
00180     while (c!=NULL) { o << c; c = c->next; } o << "\n";
00181     return o;
00182   };
00183 };
00184 
00185 }//namespace Marsyas
00186 
00187 //only  relevant for WIN32 MSVC (and ignored by all other platforms)
00188 //For more info about the reason for this #pragma consult:
00189 //http://msdn2.microsoft.com/en-us/library/sa28fef8.aspx
00190