summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.settings/language.settings.xml4
-rw-r--r--Sources/DataStructure.cpp289
2 files changed, 196 insertions, 97 deletions
diff --git a/.settings/language.settings.xml b/.settings/language.settings.xml
index 4e9d73d..e532fea 100644
--- a/.settings/language.settings.xml
+++ b/.settings/language.settings.xml
@@ -5,7 +5,7 @@
<provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/>
<provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/>
<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
- <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+ <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-938732924838427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
<language-scope id="org.eclipse.cdt.core.gcc"/>
<language-scope id="org.eclipse.cdt.core.g++"/>
</provider>
@@ -16,7 +16,7 @@
<provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/>
<provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/>
<provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/>
- <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
+ <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-938732924838427581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD &quot;${INPUTS}&quot;" prefer-non-shared="true">
<language-scope id="org.eclipse.cdt.core.gcc"/>
<language-scope id="org.eclipse.cdt.core.g++"/>
</provider>
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 5cfb53c..4c0379b 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,117 +1,216 @@
#include <iostream>
-#include <string>
#include <vector>
+#include <algorithm>
+#include <stack>
+#include <queue>
+#include <unordered_set>
//#include <gtest/gtest.h>
+//#if defined(__unix__) || defined(__APPLE__)
+//#include <sys/resource.h>
+//#endif
-using std::string;
-typedef unsigned long long ull;
+using std::vector;
+using std::ios_base;
+using std::cin;
+using std::cout;
-struct Data {
- string pattern, text;
-};
-
-Data read_input() {
- Data data;
- std::cin >> data.pattern >> data.text;
- return data;
-}
-
-void print_occurrences(const std::vector<int>& output) {
- for (size_t i = 0; i < output.size(); ++i)
- std::cout << output[i] << " ";
- std::cout << "\n";
-}
-
-std::vector<int> get_occurrences(const Data& input) {
- const string& s = input.pattern, t = input.text;
- std::vector<int> ans;
- for (size_t i = 0; i + s.size() <= t.size(); ++i)
- if (t.substr(i, s.size()) == s)
- ans.push_back(i);
- return ans;
-}
+class TreeOrders {
+public:
+ int n;
+ vector<int> key;
+ vector<int> left;
+ vector<int> right;
-ull poly_hash(string& S, int p, int x) {
- ull hash = 0;
+ void read() {
+ cin >> n;
+ key.resize(n);
+ left.resize(n);
+ right.resize(n);
+ for (int i = 0; i < n; i++) {
+ cin >> key[i] >> left[i] >> right[i];
+ }
+ }
- for (int i = S.size() - 1; i >= 0; --i)
- hash = (hash * x + S[i]) % p;
- return hash;
-}
+ vector<int> in_order() {
+ std::stack<int> keyIndexStack;
+ vector<int> result;
+ bool walkLeft = true;
+ int currentIndex = 0;
+ keyIndexStack.push(currentIndex);
+ while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+ if (walkLeft) {
+ if (left[currentIndex] != -1) {
+ currentIndex = left[currentIndex];
+ keyIndexStack.push(currentIndex);
+ } else {
+ result.push_back(key[keyIndexStack.top()]);
+ keyIndexStack.pop();
+ walkLeft = false;
+ }
+ } else {
+ if (right[currentIndex] != -1) {
+ currentIndex = right[currentIndex];
+ keyIndexStack.push(currentIndex);
+ walkLeft = true;
+ } else {
+ if (!keyIndexStack.empty()) {
+ currentIndex = keyIndexStack.top();
+ keyIndexStack.pop();
+ result.push_back(key[currentIndex]);
+ }
+ }
+ }
+ }
+ return result;
+ }
-std::vector<ull> pre_compute_hashes(string& T, int pattenLength, int p, int x) {
- std::vector<ull> H(T.size() - pattenLength + 1);
- string S = T.substr(T.size() - pattenLength);
- H[T.size() - pattenLength] = poly_hash(S, p, x);
- ull y = 1;
- for (int i = 0; i < pattenLength; i++) {
- y = (y * x) % p;
+ vector<int> pre_order() {
+ vector<int> result;
+ std::stack<int> keyIndexStack;
+ std::queue<int> keyIndexQueue;
+ bool walkLeft = true;
+ int currentIndex = 0;
+ keyIndexStack.push(currentIndex);
+ keyIndexQueue.push(currentIndex);
+ while (!keyIndexStack.empty() || right[currentIndex] != -1) {
+ if (walkLeft) {
+ if (left[currentIndex] != -1) {
+ currentIndex = left[currentIndex];
+ keyIndexQueue.push(currentIndex);
+ keyIndexStack.push(currentIndex);
+ } else {
+ keyIndexStack.pop();
+ walkLeft = false;
+ result.push_back(key[keyIndexQueue.front()]);
+ keyIndexQueue.pop();
+ }
+ } else {
+ if (right[currentIndex] != -1) {
+ currentIndex = right[currentIndex];
+ keyIndexQueue.push(currentIndex);
+ keyIndexStack.push(currentIndex);
+ walkLeft = true;
+ } else {
+ if (!keyIndexStack.empty()) {
+ currentIndex = keyIndexStack.top();
+ keyIndexStack.pop();
+ result.push_back(key[keyIndexQueue.front()]);
+ keyIndexQueue.pop();
+ }
+ }
+ }
+ }
+ return result;
}
- for (int i = T.size() - pattenLength - 1; i >= 0; --i) {
- H[i] = (x * H[i + 1] + T[i] - y * T[i + pattenLength]) % p;
+
+ vector<int> post_order() {
+ vector<int> result;
+ std::stack<int> keyIndexStack;
+ std::unordered_set<int> peekedSet;
+ bool walkLeft = true;
+ int currentIndex = 0;
+ keyIndexStack.push(currentIndex);
+ while (!keyIndexStack.empty()) {
+ auto search = peekedSet.find(currentIndex);
+ if (search != peekedSet.end()) {
+ result.push_back(key[currentIndex]);
+ peekedSet.erase(currentIndex);
+ keyIndexStack.pop();
+ if (keyIndexStack.empty())
+ break;
+ currentIndex = keyIndexStack.top();
+ continue;
+ }
+ if (walkLeft) {
+ if (left[currentIndex] != -1) {
+ currentIndex = left[currentIndex];
+ keyIndexStack.push(currentIndex);
+ } else {
+ if (right[currentIndex] == -1) {
+ result.push_back(key[currentIndex]);
+ walkLeft = false;
+ keyIndexStack.pop();
+ currentIndex = keyIndexStack.top();
+ } else {
+ peekedSet.insert(currentIndex);
+ currentIndex = right[currentIndex];
+ keyIndexStack.push(currentIndex);
+ }
+ }
+ } else {
+ if (right[currentIndex] != -1) {
+ peekedSet.insert(currentIndex);
+ currentIndex = right[currentIndex];
+ keyIndexStack.push(currentIndex);
+ walkLeft = true;
+ } else {
+ result.push_back(key[currentIndex]);
+ int i = keyIndexStack.top();
+ keyIndexStack.pop();
+ if (i != currentIndex)
+ result.push_back(key[i]);
+ if (keyIndexStack.empty())
+ break;
+ currentIndex = keyIndexStack.top();
+ }
+ }
+ }
+ return result;
}
- return H;
-}
+};
-std::vector<int> rabin_karp(const Data& input) {
- string T = input.text;
- string P = input.pattern;
- int p = 1000000007;
- int x = 1 + (rand() % static_cast<int>(1000000006));
- std::vector<int> positions;
- ull pHash = poly_hash(P, p, x);
- std::vector<ull> H = pre_compute_hashes(T, P.size(), p, x);
- for (size_t i = 0; i < T.size() - P.size() + 1; i++) {
- if (pHash != H[i]) {
- continue;
+void print(vector<int> a) {
+ for (size_t i = 0; i < a.size(); i++) {
+ if (i > 0) {
+ cout << ' ';
}
- if (T.compare(i, P.size(), P) == 0)
- positions.push_back(i);
+ cout << a[i];
}
- return positions;
+ cout << '\n';
}
-//TEST(RabinKarp, t) {
-// Data data;
-// data.pattern = "a";
-// data.text = "ab";
-// std::vector<int> results = rabin_karp(data);
-//
-// ASSERT_EQ(1, results.size());
-// ASSERT_EQ(0, results[0]);
-//
-// data.pattern = "aba";
-// data.text = "abacaba";
-// results = rabin_karp(data);
-//
-// ASSERT_EQ(2, results.size());
-// ASSERT_EQ(0, results[0]);
-// ASSERT_EQ(4, results[1]);
-//}
+
+//TEST(TreeTraversal, t) {
+// TreeOrders t;
+// t.key = {4, 2, 5, 1, 3};
+// t.left = {1, 3, -1, -1, -1};
+// t.right = {2, 4, -1, -1, -1};
//
-//TEST(RabinKarp, t1) {
-// Data data;
-// data.pattern = "Test";
-// data.text = "testTesttesT";
-// std::vector<int> results = rabin_karp(data);
+// vector<int> results = t.in_order();
+// ASSERT_EQ(5, results.size());
+// ASSERT_EQ(1, results[0]);
+// ASSERT_EQ(2, results[1]);
+// ASSERT_EQ(3, results[2]);
+// ASSERT_EQ(4, results[3]);
+// ASSERT_EQ(5, results[4]);
//
-// ASSERT_EQ(1, results.size());
+// results = t.pre_order();
+// ASSERT_EQ(5, results.size());
// ASSERT_EQ(4, results[0]);
-//}
-//
-//TEST(RabinKarp, t2) {
-// Data data;
-// data.pattern = "aaaaa";
-// data.text = "baaaaaaa";
-// std::vector<int> results = rabin_karp(data);
+// ASSERT_EQ(2, results[1]);
+// ASSERT_EQ(1, results[2]);
+// ASSERT_EQ(3, results[3]);
+// ASSERT_EQ(5, results[4]);
//
-// ASSERT_EQ(3, results.size());
+// results = t.post_order();
+// ASSERT_EQ(5, results.size());
// ASSERT_EQ(1, results[0]);
-// ASSERT_EQ(2, results[1]);
-// ASSERT_EQ(3, results[2]);
+// ASSERT_EQ(3, results[1]);
+// ASSERT_EQ(2, results[2]);
+// ASSERT_EQ(5, results[3]);
+// ASSERT_EQ(4, results[4]);
//}
-int main() {
- std::ios_base::sync_with_stdio(false);
- print_occurrences(rabin_karp(read_input()));
- return 0;
+int main_with_large_stack_space() {
+ ios_base::sync_with_stdio(0);
+ TreeOrders t;
+ t.read();
+ print(t.in_order());
+ print(t.pre_order());
+ print(t.post_order());
+ return 0;
+}
+
+int main (int argc, char **argv)
+{
+ return main_with_large_stack_space();
}