00001 /******************************************************************************************[Heap.h] 00002 MiniSat -- Copyright (c) 2003-2005, Niklas Een, Niklas Sorensson 00003 00004 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and 00005 associated documentation files (the "Software"), to deal in the Software without restriction, 00006 including without limitation the rights to use, copy, modify, merge, publish, distribute, 00007 sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is 00008 furnished to do so, subject to the following conditions: 00009 00010 The above copyright notice and this permission notice shall be included in all copies or 00011 substantial portions of the Software. 00012 00013 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT 00014 NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00015 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 00016 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT 00017 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00018 **************************************************************************************************/ 00019 #include <vector> 00020 #include <iostream> 00021 //================================================================================================= 00022 00023 00024 static inline int left (int i) { return i+i; } 00025 static inline int right (int i) { return i+i + 1; } 00026 static inline int parent(int i) { return i >> 1; } 00027 00028 using namespace std; 00029 00030 template<class C> 00031 class Heap { 00032 typedef vector<int> vectint; 00033 private : 00034 C* comp; 00035 public : 00036 vectint heap; // heap of ints 00037 vectint indices; // int -> index in heap 00038 Heap() { 00039 heap.push_back(-1); 00040 } 00041 00042 Heap(C* co) { 00043 comp=co; 00044 heap.push_back(-1); 00045 } 00046 00047 void initcomp(C* co) { 00048 comp=co; 00049 } 00050 00051 inline void percolateUp(int i) 00052 { 00053 int x = heap[i]; 00054 while (parent(i) != 0 && (*comp)(x,heap[parent(i)])) { 00055 heap[i] = heap[parent(i)]; 00056 indices[heap[i]] = i; 00057 i = parent(i); 00058 } 00059 heap [i] = x; 00060 indices[x] = i; 00061 } 00062 00063 inline void percolateDown(int i) 00064 { 00065 int x = heap[i]; 00066 while (left(i) < heap.size()){ 00067 int child = right(i) < heap.size() && (*comp)(heap[right(i)],heap[left(i)]) ? right(i) : left(i); 00068 if (!(*comp)(heap[child],x)) break; 00069 heap[i] = heap[child]; 00070 indices[heap[i]] = i; 00071 i = child; 00072 } 00073 heap [i] = x; 00074 indices[x] = i; 00075 } 00076 00077 bool ok(int n) { 00078 return n >= 0 && n < indices.size(); 00079 } 00080 00081 public: 00082 00083 int size() { 00084 return heap.size()-1; 00085 } 00086 00087 void setBounds (int size) { /*assert(size >= 0);*/ 00088 for (int i=indices.size();i<=size;i++) { 00089 indices.push_back(0); 00090 } 00091 } 00092 00093 bool inHeap (int n) { 00094 /*assert(ok(n));*/ 00095 return indices[n] != 0; 00096 } 00097 00098 void increase (int n) { 00099 /*assert(ok(n));*/ 00100 /*assert(inHeap(n));*/ 00101 percolateUp(indices[n]); 00102 } 00103 00104 void decrease (int n) { 00105 /*assert(ok(n));*/ 00106 /*assert(inHeap(n));*/ 00107 percolateDown(indices[n]); 00108 } 00109 00110 bool empty () { 00111 return heap.size() == 1; 00112 } 00113 00114 void insert(int n) { 00115 // cout<<"Insertion de "<<n<<endl; 00116 /*assert(ok(n));*/ 00117 if (inHeap(n)) return; 00118 indices[n] = heap.size(); 00119 heap.push_back(n); 00120 percolateUp(indices[n]); } 00121 00122 int getminwopop() { 00123 return heap[1]; 00124 } 00125 00126 int getmin() { 00127 int r = heap[1]; 00128 heap[1] = heap.back(); 00129 indices[heap[1]] = 1; 00130 indices[r] = 0; 00131 heap.pop_back(); 00132 if (heap.size() > 1) 00133 percolateDown(1); 00134 return r; } 00135 00136 bool heapProperty() { 00137 return heapProperty(1); } 00138 00139 bool heapProperty(int i) { 00140 return (size_t)i >= heap.size() 00141 || ((parent(i) == 0 || !(*comp)(heap[i],heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); } 00142 00143 void print() { 00144 cout<<"heap: "; 00145 for (int i=0;i<heap.size();i++) cout<<"-"<<heap[i]; 00146 cout<<"-"<<endl; 00147 cout<<"indices: "; 00148 for (int i=0;i<indices.size();i++) cout<<"-"<<indices[i]; 00149 cout<<"-"<<endl; 00150 } 00151 };