diff options
Diffstat (limited to 'src/sat/glucose2/Heap.h')
| -rw-r--r-- | src/sat/glucose2/Heap.h | 163 |
1 files changed, 163 insertions, 0 deletions
diff --git a/src/sat/glucose2/Heap.h b/src/sat/glucose2/Heap.h new file mode 100644 index 00000000..d68229f6 --- /dev/null +++ b/src/sat/glucose2/Heap.h @@ -0,0 +1,163 @@ +/******************************************************************************************[Heap.h] +Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson +Copyright (c) 2007-2010, 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. +**************************************************************************************************/ + +#ifndef Glucose_Heap_h +#define Glucose_Heap_h + +#include "sat/glucose2/Vec.h" + +ABC_NAMESPACE_CXX_HEADER_START + +namespace Gluco2 { + +//================================================================================================= +// A heap implementation with support for decrease/increase key. + + +template<class Comp> +class Heap { + Comp lt; // The heap is a minimum-heap with respect to this comparator + vec<int> heap; // Heap of integers + vec<int> indices; // Each integers position (index) in the 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; } + + + void percolateUp(int i) + { + int x = heap[i]; + int p = parent(i); + + while (i != 0 && lt(x, heap[p])){ + heap[i] = heap[p]; + indices[heap[p]] = i; + i = p; + p = parent(p); + } + heap [i] = x; + indices[x] = i; + } + + + 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; + } + + + 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]); } + void increase (int n) { assert(inHeap(n)); percolateDown(indices[n]); } + void prelocate (int ext_cap){ indices.prelocate(ext_cap); } + + // Safe variant of insert/decrease/increase: + void update(int n) + { + if (!inHeap(n)) + insert(n); + else { + percolateUp(indices[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; + } + + + // Rebuild the heap from scratch, using the elements in 'ns': + void build(vec<int>& ns) { + int i; + for (i = 0; i < heap.size(); i++) + indices[heap[i]] = -1; + heap.clear(); + + for (i = 0; i < ns.size(); i++){ + indices[ns[i]] = i; + heap.push(ns[i]); } + + for (i = heap.size() / 2 - 1; i >= 0; i--) + percolateDown(i); + } + + void clear(bool dealloc = false) + { + int i; + for (i = 0; i < heap.size(); i++) + indices[heap[i]] = -1; + heap.clear(dealloc); + } + void clear_(bool dealloc = false) + { + int i; + for (i = 0; i < heap.size(); i++) + indices[heap[i]] = -1; + + if( ! dealloc ) heap.shrink_( heap.size() ); + else heap.clear(true); + } +}; + + +//================================================================================================= +} + +ABC_NAMESPACE_CXX_HEADER_END + +#endif |