diff options
Diffstat (limited to '02-data_structures/04-binary_search_trees/03-rope')
| -rw-r--r-- | 02-data_structures/04-binary_search_trees/03-rope/rope.cpp | 168 |
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; } |