Algorithms : add 02-data_structures 04-binary_search_trees

5 files changed, 46 insertions, 0 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
new file mode 100644
index 0000000..d5f5f35
--- /dev/null
+++ b/02-data_structures/04-binary_search_trees/03-rope/rope.cpp
@@ -0,0 +1,36 @@
+#include <cstdio>
+#include <string>
+#include <iostream>
+
+
+class Rope {
+	std::string s;
+public:
+	Rope(const std::string &s) : s(s) { 
+	}
+
+	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);
+	}
+
+	std::string result() {
+		return s;
+	}
+};
+
+int main() {
+	std::ios_base::sync_with_stdio(0);
+	std::string s;
+	std::cin >> s;
+	Rope rope(s);
+	int actions;
+	std::cin >> actions;
+        for (int action_index = 0; action_index < actions; ++action_index) {
+                int i, j, k;
+		std::cin >> i >> j >> k;
+		rope.process(i, j, k);
+	}
+	std::cout << rope.result() << std::endl;
+}
diff --git a/02-data_structures/04-binary_search_trees/03-rope/tests/01 b/02-data_structures/04-binary_search_trees/03-rope/tests/01
new file mode 100644
index 0000000..8ecb9b9
--- /dev/null
+++ b/02-data_structures/04-binary_search_trees/03-rope/tests/01
@@ -0,0 +1,4 @@
+hlelowrold
+2
+1 1 2
+6 6 7
diff --git a/02-data_structures/04-binary_search_trees/03-rope/tests/01.a b/02-data_structures/04-binary_search_trees/03-rope/tests/01.a
new file mode 100644
index 0000000..31e0fce
--- /dev/null
+++ b/02-data_structures/04-binary_search_trees/03-rope/tests/01.a
@@ -0,0 +1 @@
+helloworld
diff --git a/02-data_structures/04-binary_search_trees/03-rope/tests/02 b/02-data_structures/04-binary_search_trees/03-rope/tests/02
new file mode 100644
index 0000000..b7d407d
--- /dev/null
+++ b/02-data_structures/04-binary_search_trees/03-rope/tests/02
@@ -0,0 +1,4 @@
+abcdef
+2
+0 1 1
+4 5 0
diff --git a/02-data_structures/04-binary_search_trees/03-rope/tests/02.a b/02-data_structures/04-binary_search_trees/03-rope/tests/02.a
new file mode 100644
index 0000000..a02a180
--- /dev/null
+++ b/02-data_structures/04-binary_search_trees/03-rope/tests/02.a
@@ -0,0 +1 @@
+efcabd