summaryrefslogtreecommitdiffstats
path: root/juk/sortedstringlist.h
blob: 108a16c6f3834bc6b6a7ec87915e18e908b8751f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/***************************************************************************
    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.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef SORTEDSTRINGLIST_H
#define SORTEDSTRINGLIST_H

#include <qstringlist.h>

class SortedStringList 
{
public: 
    SortedStringList();
    ~SortedStringList();

    /**
     * Insert the value.  Returns true if the item was already in the list
     * or false otherwise.
     */
    bool insert(const QString &value);
    bool contains(const QString &value) const;
    bool remove(const QString &value);

    /**
     * Returns a sorted list of the values.
     * Warning, this method is expensive and shouldn't be used except when 
     * necessary.
     */
    QStringList values() const;

private:
    class Node;

    Node *find(const QString &value) const;
    /**
     * The insertion implementation.  Returns true if the item was already 
     * present in the list.
     */
    bool BSTInsert(const QString &value);
    void traverse(const Node *n, QStringList &list) const;

    Node *treeMinimum(Node *n) const;
    Node *treeSuccessor(Node *n) const;

    Node *m_root;
};

#endif