← Back to branch summary

~ubuntu-branches/ubuntu/breezy/kdemultimedia/breezy

« back to all changes in this revision

Viewing changes to juk/sortedstringlist.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Jonathan Riddell
  • Date: 2005-03-24 04:48:58 UTC
  • mfrom: (1.2.1 upstream) (2.1.1 sarge)
  • Revision ID: james.westby@ubuntu.com-20050324044858-8ff88o9jxej6ii3d
Tags: 4:3.4.0-0ubuntu3
Add kubuntu_02_hide_arts_menu_entries.diff to hide artsbuilder and artscontrol k-menu entries

Show diffs side-by-side

added added

removed removed

Lines of Context:
juk/sortedstringlist.cpp
 
1
/***************************************************************************
 
2
    begin                : Wed Jan 29 2003
 
3
    copyright            : (C) 2003 - 2004 by Scott Wheeler
 
4
    email                : wheeler@kde.org
 
5
 ***************************************************************************/
 
6
 
 
7
/***************************************************************************
 
8
 *                                                                         *
 
9
 *   This program is free software; you can redistribute it and/or modify  *
 
10
 *   it under the terms of the GNU General Public License as published by  *
 
11
 *   the Free Software Foundation; either version 2 of the License, or     *
 
12
 *   (at your option) any later version.                                   *
 
13
 *                                                                         *
 
14
 ***************************************************************************/
 
15
 
 
16
#include <kdebug.h>
 
17
 
 
18
#include "sortedstringlist.h"
 
19
 
 
20
class SortedStringList::Node 
 
21
{
 
22
public:
 
23
    Node(const QString &value) : key(value), parent(0), left(0), right(0) {}
 
24
    ~Node() {}
 
25
    
 
26
    QString key;
 
27
    Node *parent;
 
28
    Node *left;
 
29
    Node *right;
 
30
};
 
31
 
 
32
SortedStringList::SortedStringList() : m_root(0)
 
33
{
 
34
    
 
35
}
 
36
 
 
37
SortedStringList::~SortedStringList()
 
38
{
 
39
    
 
40
}
 
41
 
 
42
bool SortedStringList::insert(const QString &value)
 
43
{
 
44
    return BSTInsert(value);
 
45
}
 
46
 
 
47
bool SortedStringList::contains(const QString &value) const
 
48
{
 
49
    return find(value);
 
50
}
 
51
 
 
52
SortedStringList::Node *SortedStringList::treeMinimum(Node *n) const
 
53
{
 
54
    while(n->left)
 
55
        n = n->left;
 
56
    return n;
 
57
}
 
58
 
 
59
SortedStringList::Node *SortedStringList::treeSuccessor(Node *n) const
 
60
{
 
61
    if(n->right)
 
62
        return treeMinimum(n->right);
 
63
    
 
64
    Node *p = n->parent;
 
65
    
 
66
    while(p && n == p->right) {
 
67
        n = p;
 
68
        p = p->parent;
 
69
    }
 
70
    
 
71
    return p;
 
72
}
 
73
 
 
74
bool SortedStringList::remove(const QString &value)
 
75
{
 
76
    Node *n = find(value);
 
77
 
 
78
    if(!n)
 
79
        return false;
 
80
    
 
81
    Node *y;
 
82
    Node *x;
 
83
 
 
84
    if(!n->left || !n->right)
 
85
        y = n;
 
86
    else
 
87
        y = treeSuccessor(n);
 
88
 
 
89
    if(y->left)
 
90
        x = y->left;
 
91
    else
 
92
        x = y->right;
 
93
 
 
94
    if(x)
 
95
        x->parent = y->parent;
 
96
    
 
97
    if(!y->parent)
 
98
        m_root = x;
 
99
    else {
 
100
        if(y == y->parent->left)
 
101
            y->parent->left = x;
 
102
        else
 
103
            y->parent->right = x;
 
104
    }
 
105
    
 
106
    if(y != x)
 
107
        n->key = y->key;
 
108
    
 
109
    delete y;
 
110
 
 
111
    return true;
 
112
}
 
113
 
 
114
QStringList SortedStringList::values() const
 
115
{
 
116
    QStringList l;
 
117
    traverse(m_root, l);
 
118
    return l;
 
119
}
 
120
 
 
121
////////////////////////////////////////////////////////////////////////////////
 
122
// private methods
 
123
////////////////////////////////////////////////////////////////////////////////
 
124
 
 
125
SortedStringList::Node *SortedStringList::find(const QString &value) const
 
126
{
 
127
    Node *n = m_root;
 
128
    while(n && value != n->key) {
 
129
        if(value < n->key)
 
130
            n = n->left;
 
131
        else
 
132
            n = n->right;
 
133
    }
 
134
 
 
135
    return n;
 
136
}
 
137
 
 
138
bool SortedStringList::BSTInsert(const QString &value)
 
139
{
 
140
    Node *previousNode = 0;
 
141
    Node *node = m_root;
 
142
    
 
143
    while(node) {
 
144
        previousNode = node;
 
145
        if(value == node->key)
 
146
            return true;
 
147
        else if(value < node->key)
 
148
            node = node->left;
 
149
        else
 
150
            node = node->right;
 
151
    }
 
152
    
 
153
    if(previousNode && value == previousNode->key)
 
154
        return true;
 
155
 
 
156
    Node *n = new Node(value);
 
157
 
 
158
    n->parent = previousNode;
 
159
 
 
160
    if(!m_root)
 
161
        m_root = n;
 
162
    else {
 
163
        if(value < previousNode->key)
 
164
            previousNode->left = n;
 
165
        else
 
166
            previousNode->right = n;
 
167
    }
 
168
    
 
169
    return false;
 
170
}
 
171
 
 
172
void SortedStringList::traverse(const Node *n, QStringList &list) const
 
173
{
 
174
    if(!n)
 
175
        return;
 
176
 
 
177
    traverse(n->left, list);
 
178
    list.append(n->key);
 
179
    traverse(n->right, list);
 
180
}