From 5530575ae0ad939e17f08d6bd49978acea388ab7 Mon Sep 17 00:00:00 2001
From: Paul Baltescu <pauldb89@gmail.com>
Date: Mon, 28 Jan 2013 11:56:31 +0000
Subject: Initial working commit.

---
 extractor/veb_tree.cc | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 71 insertions(+)
 create mode 100644 extractor/veb_tree.cc

(limited to 'extractor/veb_tree.cc')

diff --git a/extractor/veb_tree.cc b/extractor/veb_tree.cc
new file mode 100644
index 00000000..f8945445
--- /dev/null
+++ b/extractor/veb_tree.cc
@@ -0,0 +1,71 @@
+#include <cmath>
+
+#include "veb_tree.h"
+
+VEBTree::VEBTree(int size) {
+  int num_bits = ceil(log2(size));
+
+  lower_bits = num_bits >> 1;
+  upper_size = (size >> lower_bits) + 1;
+
+  clusters.reserve(upper_size);
+  clusters.resize(upper_size);
+}
+
+int VEBTree::GetNextValue(int value) {
+  return value & ((1 << lower_bits) - 1);
+}
+
+int VEBTree::GetCluster(int value) {
+  return value >> lower_bits;
+}
+
+int VEBTree::Compose(int cluster, int value) {
+  return (cluster << lower_bits) + value;
+}
+
+void VEBTree::Insert(int value) {
+  if (min == -1 && max == -1) {
+    min = max = value;
+    return;
+  }
+
+  if (value < min) {
+    swap(min, value);
+  }
+
+  int cluster = GetCluster(value), next_value = GetNextValue(value);
+  if (clusters[cluster] == NULL) {
+    clusters[cluster] = VEB::Create(1 << lower_bits);
+    if (summary == NULL) {
+      summary = VEB::Create(upper_size);
+    }
+    summary->Insert(cluster);
+  }
+  clusters[cluster]->Insert(next_value);
+
+  if (value > max) {
+    max = value;
+  }
+}
+
+int VEBTree::GetSuccessor(int value) {
+  if (value >= max) {
+    return -1;
+  }
+  if (value < min) {
+    return min;
+  }
+
+  int cluster = GetCluster(value), next_value = GetNextValue(value);
+  if (clusters[cluster] != NULL &&
+      next_value < clusters[cluster]->GetMaximum()) {
+    return Compose(cluster, clusters[cluster]->GetSuccessor(next_value));
+  } else {
+    int next_cluster = summary->GetSuccessor(cluster);
+    if (next_cluster == -1) {
+      return -1;
+    }
+    return Compose(next_cluster, clusters[next_cluster]->GetMinimum());
+  }
+}
-- 
cgit v1.2.3