summaryrefslogtreecommitdiffstats
path: root/juk/sortedstringlist.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'juk/sortedstringlist.cpp')
-rw-r--r--juk/sortedstringlist.cpp180
1 files changed, 180 insertions, 0 deletions
diff --git a/juk/sortedstringlist.cpp b/juk/sortedstringlist.cpp
new file mode 100644
index 00000000..87f2938d
--- /dev/null
+++ b/juk/sortedstringlist.cpp
@@ -0,0 +1,180 @@
+/***************************************************************************
+ begin : Wed Jan 29 2003
+ copyright : (C) 2003 - 2004 by Scott Wheeler
+ email : wheeler@kde.org
+ ***************************************************************************/
+
+/***************************************************************************
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU General Public License as published by *
+ * the Free Software Foundation; either version 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ ***************************************************************************/
+
+#include <kdebug.h>
+
+#include "sortedstringlist.h"
+
+class SortedStringList::Node
+{
+public:
+ Node(const QString &value) : key(value), parent(0), left(0), right(0) {}
+ ~Node() {}
+
+ QString key;
+ Node *parent;
+ Node *left;
+ Node *right;
+};
+
+SortedStringList::SortedStringList() : m_root(0)
+{
+
+}
+
+SortedStringList::~SortedStringList()
+{
+
+}
+
+bool SortedStringList::insert(const QString &value)
+{
+ return BSTInsert(value);
+}
+
+bool SortedStringList::contains(const QString &value) const
+{
+ return find(value);
+}
+
+SortedStringList::Node *SortedStringList::treeMinimum(Node *n) const
+{
+ while(n->left)
+ n = n->left;
+ return n;
+}
+
+SortedStringList::Node *SortedStringList::treeSuccessor(Node *n) const
+{
+ if(n->right)
+ return treeMinimum(n->right);
+
+ Node *p = n->parent;
+
+ while(p && n == p->right) {
+ n = p;
+ p = p->parent;
+ }
+
+ return p;
+}
+
+bool SortedStringList::remove(const QString &value)
+{
+ Node *n = find(value);
+
+ if(!n)
+ return false;
+
+ Node *y;
+ Node *x;
+
+ if(!n->left || !n->right)
+ y = n;
+ else
+ y = treeSuccessor(n);
+
+ if(y->left)
+ x = y->left;
+ else
+ x = y->right;
+
+ if(x)
+ x->parent = y->parent;
+
+ if(!y->parent)
+ m_root = x;
+ else {
+ if(y == y->parent->left)
+ y->parent->left = x;
+ else
+ y->parent->right = x;
+ }
+
+ if(y != x)
+ n->key = y->key;
+
+ delete y;
+
+ return true;
+}
+
+QStringList SortedStringList::values() const
+{
+ QStringList l;
+ traverse(m_root, l);
+ return l;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// private methods
+////////////////////////////////////////////////////////////////////////////////
+
+SortedStringList::Node *SortedStringList::find(const QString &value) const
+{
+ Node *n = m_root;
+ while(n && value != n->key) {
+ if(value < n->key)
+ n = n->left;
+ else
+ n = n->right;
+ }
+
+ return n;
+}
+
+bool SortedStringList::BSTInsert(const QString &value)
+{
+ Node *previousNode = 0;
+ Node *node = m_root;
+
+ while(node) {
+ previousNode = node;
+ if(value == node->key)
+ return true;
+ else if(value < node->key)
+ node = node->left;
+ else
+ node = node->right;
+ }
+
+ if(previousNode && value == previousNode->key)
+ return true;
+
+ Node *n = new Node(value);
+
+ n->parent = previousNode;
+
+ if(!m_root)
+ m_root = n;
+ else {
+ if(value < previousNode->key)
+ previousNode->left = n;
+ else
+ previousNode->right = n;
+ }
+
+ return false;
+}
+
+void SortedStringList::traverse(const Node *n, QStringList &list) const
+{
+ if(!n)
+ return;
+
+ traverse(n->left, list);
+ list.append(n->key);
+ traverse(n->right, list);
+}