1 /******************************************************************************************[Heap.h] 2 MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson 3 4 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and 5 associated documentation files (the "Software"), to deal in the Software without restriction, 6 including without limitation the rights to use, copy, modify, merge, publish, distribute, 7 sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is 8 furnished to do so, subject to the following conditions: 9 10 The above copyright notice and this permission notice shall be included in all copies or 11 substantial portions of the Software. 12 13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT 14 NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 15 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 16 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT 17 OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 18 **************************************************************************************************/ 19 20 #ifndef heap_h 21 #define heap_h 22 23 #include <chuffed/support/vec.h> 24 25 //================================================================================================= 26 // A heap implementation with support for decrease/increase key. 27 28 29 template<class Comp> 30 class Heap { 31 Comp lt; 32 vec<int> heap; // heap of ints 33 vec<int> indices; // int -> index in heap 34 35 // Index "traversal" functions left(int i)36 static inline int left (int i) { return i*2+1; } right(int i)37 static inline int right (int i) { return (i+1)*2; } parent(int i)38 static inline int parent(int i) { return (i-1) >> 1; } 39 40 percolateUp(int i)41 inline void percolateUp(int i) 42 { 43 int x = heap[i]; 44 while (i != 0 && lt(x, heap[parent(i)])){ 45 heap[i] = heap[parent(i)]; 46 indices[heap[i]] = i; 47 i = parent(i); 48 } 49 heap [i] = x; 50 indices[x] = i; 51 } 52 53 percolateDown(int i)54 inline void percolateDown(int i) 55 { 56 int x = heap[i]; 57 while (left(i) < heap.size()){ 58 int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i); 59 if (!lt(heap[child], x)) break; 60 heap[i] = heap[child]; 61 indices[heap[i]] = i; 62 i = child; 63 } 64 heap [i] = x; 65 indices[x] = i; 66 } 67 68 heapProperty(int i)69 bool heapProperty (int i) const { 70 return i >= heap.size() 71 || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); } 72 73 74 public: Heap(const Comp & c)75 Heap(const Comp& c) : lt(c) { } 76 size()77 int size () const { return heap.size(); } empty()78 bool empty () const { return heap.size() == 0; } inHeap(int n)79 bool inHeap (int n) const { return n < indices.size() && indices[n] >= 0; } 80 int operator[](int index) const { assert(index < heap.size()); return heap[index]; } 81 decrease(int n)82 void decrease (int n) { assert(inHeap(n)); percolateUp(indices[n]); } 83 84 // RENAME WHEN THE DEPRECATED INCREASE IS REMOVED. increase_(int n)85 void increase_ (int n) { assert(inHeap(n)); percolateDown(indices[n]); } 86 87 insert(int n)88 void insert(int n) 89 { 90 indices.growTo(n+1, -1); 91 assert(!inHeap(n)); 92 93 indices[n] = heap.size(); 94 heap.push(n); 95 percolateUp(indices[n]); 96 } 97 98 removeMin()99 int removeMin() 100 { 101 int x = heap[0]; 102 heap[0] = heap.last(); 103 indices[heap[0]] = 0; 104 indices[x] = -1; 105 heap.pop(); 106 if (heap.size() > 1) percolateDown(0); 107 return x; 108 } 109 110 111 void clear(bool dealloc = false) 112 { 113 for (int i = 0; i < heap.size(); i++) 114 indices[heap[i]] = -1; 115 #ifdef NDEBUG 116 for (int i = 0; i < indices.size(); i++) 117 assert(indices[i] == -1); 118 #endif 119 heap.clear(dealloc); 120 } 121 122 123 // Fool proof variant of insert/decrease/increase update(int n)124 void update (int n) 125 { 126 if (!inHeap(n)) 127 insert(n); 128 else { 129 percolateUp(indices[n]); 130 percolateDown(indices[n]); 131 } 132 } 133 134 135 // Delete elements from the heap using a given filter function (-object). 136 // *** this could probaly be replaced with a more general "buildHeap(vec<int>&)" method *** 137 template <class F> filter(const F & filt)138 void filter(const F& filt) { 139 int i,j; 140 for (i = j = 0; i < heap.size(); i++) 141 if (filt(heap[i])){ 142 heap[j] = heap[i]; 143 indices[heap[i]] = j++; 144 }else 145 indices[heap[i]] = -1; 146 147 heap.shrink(i - j); 148 for (int i = heap.size() / 2 - 1; i >= 0; i--) 149 percolateDown(i); 150 151 assert(heapProperty()); 152 } 153 154 155 // DEBUG: consistency checking heapProperty()156 bool heapProperty() const { 157 return heapProperty(1); } 158 159 160 // COMPAT: should be removed setBounds(int n)161 void setBounds (int n) { } increase(int n)162 void increase (int n) { decrease(n); } getmin()163 int getmin () { return removeMin(); } 164 165 }; 166 167 168 //================================================================================================= 169 #endif 170