Algorithms : complete 02-data_structures 04-binary_search_trees

1 files changed, 159 insertions, 9 deletions

diff --git a/02-data_structures/04-binary_search_trees/03-rope/rope.cpp b/02-data_structures/04-binary_search_trees/03-rope/rope.cpp
index d5f5f35..2f2bb75 100644
--- a/02-data_structures/04-binary_search_trees/03-rope/rope.cpp
+++ b/02-data_structures/04-binary_search_trees/03-rope/rope.cpp
@@ -2,22 +2,170 @@
 #include <string>
 #include <iostream>
 
+/* static bool debug = false; */
+
+struct Vertex {
+  const char *s;
+  size_t weight;
+  Vertex* left;
+  Vertex* right;
+
+  Vertex(const char *s, size_t weight)
+  : s(s), weight(weight), left(NULL), right(NULL) {}
+
+  Vertex(Vertex* left, Vertex* right, size_t weight)
+  : s(NULL), weight(weight), left(left), right(right) {}
+};
 
 class Rope {
 	std::string s;
+    Vertex *root;
 public:
-	Rope(const std::string &s) : s(s) { 
+	Rope(const std::string &s) : s(s) {
+        root = new Vertex(&s[0], s.size());
 	}
 
-	void process( int i, int j, int k ) {
-                // Replace this code with a faster implementation
-                std::string t = s.substr(0, i) + s.substr(j + 1);
-                s = t.substr(0, k) + s.substr(i, j - i + 1) + t.substr(k);
+	void process( int i, int j, int k )
+    {
+        Vertex* left = NULL;
+        Vertex* right = NULL;
+        Vertex* out = NULL;
+        int len = weight(root);
+
+        /* if (debug) std::cout << std::endl << "PROCESS : " << i << " " << j << " " << k << std::endl; */
+
+        if (i > 0) {
+            split(root, i, out);
+            left = root;
+            /* if (debug) { */
+            /*     std::cout << "   left : " << print(left) << std::endl; */
+            /*     std::cout << "    out : " << print(out) << std::endl; */
+            /* } */
+        } else {
+            left = NULL;
+            out = root;
+        }
+
+        if (len > (j + 1)) {
+            split(out, (j - i + 1), right);
+            /* if (debug) { */
+            /*     std::cout << "   out  : " << print(out) << std::endl; */
+            /*     std::cout << "  right : " << print(right) << std::endl; */
+            /* } */
+        } else {
+            right = NULL;
+        }
+
+        /* if (debug) std::cout << "  concat left || right : "; */
+        root = concat(left, right);
+        /* if (debug) std::cout << print(root) << std::endl; */
+
+        left = NULL;
+        right = NULL;
+        if (k > 0) {
+            split(root, k, right);
+            left = root;
+            /* if (debug) { */
+            /*     std::cout << "   left : " << print(left) << std::endl; */
+            /*     std::cout << "  right : " << print(right) << std::endl; */
+            /* } */
+            root = concat(left, concat(out, right));
+            /* if (debug) std::cout << "   root : " << print(root) << std::endl; */
+        } else {
+            root = concat(out, root);
+            /* if (debug) std::cout << "   root : " << print(root) << std::endl; */
+        }
 	}
 
 	std::string result() {
-		return s;
+        return print(root);
 	}
+
+private:
+    std::string print(Vertex *v)
+    {
+        /* std::cout << weight(v) << std::endl; */
+        if (v == NULL) return "NULL";
+        std::string res;
+        in_order(v, res);
+		return res;
+    }
+
+    void in_order(Vertex *v, std::string &r) {
+        if (v == NULL) return;
+        /* if (debug) { */
+        /*     std::cout << v << "  " << v->weight << " "; */
+        /*     if (v->s != NULL) { */
+        /*         for (int i = 0; i < v->weight; i++) */
+        /*             std::cout << v->s[i]; */
+        /*     } */
+        /*     std::cout << std::endl << "   " << v->left<< std::endl; */
+        /*     std::cout << "   " << v->right << std::endl; */
+        /* } */
+
+        in_order(v->left, r);
+        if (v->s != NULL) {
+            for (int i = 0; i < v->weight; i++)
+                r.push_back(v->s[i]);
+        }
+        in_order(v->right, r);
+    }
+
+    size_t weight(Vertex *v) {
+        size_t w = 0;
+        while (v != NULL) {
+            w += v->weight;
+            v = v->right;
+        }
+        return w;
+    }
+
+    Vertex* concat(Vertex *left, Vertex *right) {
+        if (right == NULL)
+            return left;
+        if (left == NULL)
+            return right;
+        return new Vertex(left, right, weight(left));
+    }
+
+    // split into : [0 ; (key-1)] [key; ...]
+    void split(Vertex* v, int key, Vertex*& outer) {
+        /* if (debug) std::cout << " split  " << key  << " " << print(v) << std::endl; */
+        _split(v, key, outer);
+    }
+
+    int _split(Vertex* v, int key, Vertex*& outer) {
+        if (v == NULL) return 0;
+        if (key < v->weight) {
+            if (v->left == NULL) {
+                /* if (debug) std::cout << "      found : " << v->s[key] << std::endl; */
+                Vertex *tmp = new Vertex(&v->s[key], v->weight - key);
+                v->weight = key;
+                outer = concat(tmp, outer);
+                return v->weight;
+            } else {
+                outer = concat(v->right, outer);
+                v->right = NULL;
+                v->weight = _split(v->left, key, outer);
+                // compress
+                if (v->left != NULL && v->left->left != NULL && v->left->right == NULL) {
+                    Vertex *tmp = v->left;
+                    v->left = v->left->left;
+                    delete(tmp);
+                }
+                return v->weight;
+            }
+        } else {
+            key -= v->weight;
+            if (key == 0) {
+                outer = concat(v->right, outer);
+                v->right = NULL;
+                return v->weight;
+            } else {
+                return v->weight + _split(v->right, key, outer);
+            }
+        }
+    }
 };
 
 int main() {
@@ -26,11 +174,13 @@ int main() {
 	std::cin >> s;
 	Rope rope(s);
 	int actions;
+    /* if (debug) std::cout << rope.result() << std::endl; */
 	std::cin >> actions;
-        for (int action_index = 0; action_index < actions; ++action_index) {
-                int i, j, k;
+    for (int action_index = 0; action_index < actions; ++action_index) {
+        int i, j, k;
 		std::cin >> i >> j >> k;
 		rope.process(i, j, k);
+        /* if (debug) std::cout << rope.result() << std::endl; */
 	}
-	std::cout << rope.result() << std::endl;
+    std::cout << rope.result() << std::endl;
 }