Add the source files for the swift library.

[swifty.git] / src / libswift / binheap.cpp

diff --git a/src/libswift/binheap.cpp b/src/libswift/binheap.cpp
new file mode 100644 (file)
index 0000000..58054d4
--- /dev/null
+++ b/src/libswift/binheap.cpp
@@ -0,0 +1,71 @@
+/*
+ *  sbit.cpp
+ *  serp++
+ *
+ *  Created by Victor Grishchenko on 4/1/09.
+ *  Copyright 2009 Delft University of Technology. All rights reserved.
+ *
+ */
+
+#include <algorithm>
+#include <cstdlib>
+
+#include "binheap.h"
+
+
+binheap::binheap() {
+    size_ = 32;
+    heap_ = (bin_t*) malloc(size_*sizeof(bin_t));
+    filled_ = 0;
+}
+
+bool bincomp (const bin_t& a, const bin_t& b) {
+    register uint64_t ab = a.base_offset(), bb = b.base_offset();
+    if (ab==bb)
+        return a.layer_bits() < b.layer_bits();
+    else
+        return ab > bb;
+}
+
+bool bincomp_rev (const bin_t& a, const bin_t& b) {
+    register uint64_t ab = a.base_offset(), bb = b.base_offset();
+    if (ab==bb)
+        return a.layer_bits() > b.layer_bits();
+    else
+        return ab < bb;
+}
+
+bin_t binheap::pop() {
+    if (!filled_)
+        return bin_t::NONE;
+    bin_t ret = heap_[0];
+    std::pop_heap(heap_, heap_+filled_--,bincomp);
+    while (filled_ && ret.contains(heap_[0]))
+        std::pop_heap(heap_, heap_+filled_--,bincomp);
+    return ret;
+}
+
+void    binheap::extend() {
+    std::sort(heap_,heap_+filled_,bincomp_rev);
+    int solid = 0;
+    for(int i=1; i<filled_; i++)
+        if (!heap_[solid].contains(heap_[i]))
+            heap_[++solid] = heap_[i];
+    filled_ = solid+1;
+    if (2*filled_>size_) {
+        size_ <<= 1;
+        heap_ = (bin_t*) realloc(heap_,size_*sizeof(bin_t));
+    }
+}
+
+void    binheap::push(bin_t val) {
+    if (filled_==size_)
+        extend();
+    heap_[filled_++] = val;
+    std::push_heap(heap_, heap_+filled_,bincomp);
+}
+
+binheap::~binheap() {
+    free(heap_);
+}
+