diff options
Diffstat (limited to 'src/prop/minisat/mtl/Heap.h')
| -rw-r--r-- | src/prop/minisat/mtl/Heap.h | 179 |
1 files changed, 0 insertions, 179 deletions
diff --git a/src/prop/minisat/mtl/Heap.h b/src/prop/minisat/mtl/Heap.h deleted file mode 100644 index 20d379b1d..000000000 --- a/src/prop/minisat/mtl/Heap.h +++ /dev/null @@ -1,179 +0,0 @@ -/******************************************************************************************[Heap.h] -MiniSat -- Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and -associated documentation files (the "Software"), to deal in the Software without restriction, -including without limitation the rights to use, copy, modify, merge, publish, distribute, -sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or -substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT -NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, -DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT -OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -**************************************************************************************************/ - -#include "cvc4_private.h" - -#ifndef CVC4_MiniSat_Heap_h -#define CVC4_MiniSat_Heap_h - -#include "Vec.h" -#include <cassert> - -namespace CVC4 { -namespace prop { -namespace minisat { - -//================================================================================================= -// A heap implementation with support for decrease/increase key. - - -template<class Comp> -class Heap { - Comp lt; - vec<int> heap; // heap of ints - vec<int> indices; // int -> index in heap - - // Index "traversal" functions - static inline int left (int i) { return i*2+1; } - static inline int right (int i) { return (i+1)*2; } - static inline int parent(int i) { return (i-1) >> 1; } - - - inline void percolateUp(int i) - { - int x = heap[i]; - while (i != 0 && lt(x, heap[parent(i)])){ - heap[i] = heap[parent(i)]; - indices[heap[i]] = i; - i = parent(i); - } - heap [i] = x; - indices[x] = i; - } - - - inline void percolateDown(int i) - { - int x = heap[i]; - while (left(i) < heap.size()){ - int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i); - if (!lt(heap[child], x)) break; - heap[i] = heap[child]; - indices[heap[i]] = i; - i = child; - } - heap [i] = x; - indices[x] = i; - } - - - bool heapProperty (int i) const { - return i >= heap.size() - || ((i == 0 || !lt(heap[i], heap[parent(i)])) && heapProperty(left(i)) && heapProperty(right(i))); } - - - public: - Heap(const Comp& c) : lt(c) { } - - int size () const { return heap.size(); } - bool empty () const { return heap.size() == 0; } - bool inHeap (int n) const { return n < indices.size() && indices[n] >= 0; } - int operator[](int index) const { assert(index < heap.size()); return heap[index]; } - - void decrease (int n) { assert(inHeap(n)); percolateUp(indices[n]); } - - // RENAME WHEN THE DEPRECATED INCREASE IS REMOVED. - void increase_ (int n) { assert(inHeap(n)); percolateDown(indices[n]); } - - - void insert(int n) - { - indices.growTo(n+1, -1); - assert(!inHeap(n)); - - indices[n] = heap.size(); - heap.push(n); - percolateUp(indices[n]); - } - - - int removeMin() - { - int x = heap[0]; - heap[0] = heap.last(); - indices[heap[0]] = 0; - indices[x] = -1; - heap.pop(); - if (heap.size() > 1) percolateDown(0); - return x; - } - - - void clear(bool dealloc = false) - { - for (int i = 0; i < heap.size(); i++) - indices[heap[i]] = -1; -#ifdef NDEBUG - for (int i = 0; i < indices.size(); i++) - assert(indices[i] == -1); -#endif - heap.clear(dealloc); - } - - - // Fool proof variant of insert/decrease/increase - void update (int n) - { - if (!inHeap(n)) - insert(n); - else { - percolateUp(indices[n]); - percolateDown(indices[n]); - } - } - - - // Delete elements from the heap using a given filter function (-object). - // *** this could probaly be replaced with a more general "buildHeap(vec<int>&)" method *** - template <class F> - void filter(const F& filt) { - int i,j; - for (i = j = 0; i < heap.size(); i++) - if (filt(heap[i])){ - heap[j] = heap[i]; - indices[heap[i]] = j++; - }else - indices[heap[i]] = -1; - - heap.shrink(i - j); - for (int i = heap.size() / 2 - 1; i >= 0; i--) - percolateDown(i); - - assert(heapProperty()); - } - - - // DEBUG: consistency checking - bool heapProperty() const { - return heapProperty(1); } - - - // COMPAT: should be removed - void setBounds (int n) { } - void increase (int n) { decrease(n); } - int getmin () { return removeMin(); } - -}; - -}/* CVC4::prop::minisat namespace */ -}/* CVC4::prop namespace */ -}/* CVC4 namespace */ - -//================================================================================================= -#endif /* CVC4_MiniSat_Heap_h */ |