summaryrefslogtreecommitdiff
path: root/extractor/veb_tree.cc
diff options
context:
space:
mode:
authorPaul Baltescu <pauldb89@gmail.com>2013-01-28 11:56:31 +0000
committerPaul Baltescu <pauldb89@gmail.com>2013-01-28 11:56:31 +0000
commit5530575ae0ad939e17f08d6bd49978acea388ab7 (patch)
tree4620a276c1c827d824e285148f4f4a5bf781ebfe /extractor/veb_tree.cc
parentce6937f136a38af93d9a5cd9628acc712da95543 (diff)
Initial working commit.
Diffstat (limited to 'extractor/veb_tree.cc')
-rw-r--r--extractor/veb_tree.cc71
1 files changed, 71 insertions, 0 deletions
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());
+ }
+}