Marsyas
0.6.0-alpha
|
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