|
1 /**************************************************************************** |
|
2 ** |
|
3 ** |
|
4 ** Definition of QGList and QGListIterator classes |
|
5 ** |
|
6 ** Created : 920624 |
|
7 ** |
|
8 ** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. |
|
9 ** |
|
10 ** This file is part of the tools module of the Qt GUI Toolkit. |
|
11 ** |
|
12 ** This file may be distributed under the terms of the Q Public License |
|
13 ** as defined by Trolltech AS of Norway and appearing in the file |
|
14 ** LICENSE.QPL included in the packaging of this file. |
|
15 ** |
|
16 ** This file may be distributed and/or modified under the terms of the |
|
17 ** GNU General Public License version 2 as published by the Free Software |
|
18 ** Foundation and appearing in the file LICENSE.GPL included in the |
|
19 ** packaging of this file. |
|
20 ** |
|
21 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition |
|
22 ** licenses may use this file in accordance with the Qt Commercial License |
|
23 ** Agreement provided with the Software. |
|
24 ** |
|
25 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE |
|
26 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. |
|
27 ** |
|
28 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for |
|
29 ** information about Qt Commercial License Agreements. |
|
30 ** See http://www.trolltech.com/qpl/ for QPL licensing information. |
|
31 ** See http://www.trolltech.com/gpl/ for GPL licensing information. |
|
32 ** |
|
33 ** Contact info@trolltech.com if any conditions of this licensing are |
|
34 ** not clear to you. |
|
35 ** |
|
36 **********************************************************************/ |
|
37 |
|
38 #ifndef QGLIST_H |
|
39 #define QGLIST_H |
|
40 |
|
41 #ifndef QT_H |
|
42 #include "qcollection.h" |
|
43 #endif // QT_H |
|
44 |
|
45 |
|
46 /***************************************************************************** |
|
47 QLNode class (internal doubly linked list node) |
|
48 *****************************************************************************/ |
|
49 |
|
50 class Q_EXPORT QLNode |
|
51 { |
|
52 friend class QGList; |
|
53 friend class QGListIterator; |
|
54 public: |
|
55 QCollection::Item getData() { return data; } |
|
56 private: |
|
57 QCollection::Item data; |
|
58 QLNode *prev; |
|
59 QLNode *next; |
|
60 QLNode( QCollection::Item d ) { data = d; } |
|
61 }; |
|
62 |
|
63 |
|
64 /***************************************************************************** |
|
65 QGList class |
|
66 *****************************************************************************/ |
|
67 |
|
68 class Q_EXPORT QGList : public QCollection // doubly linked generic list |
|
69 { |
|
70 friend class QGListIterator; |
|
71 friend class QGVector; // needed by QGVector::toList |
|
72 public: |
|
73 uint count() const; // return number of nodes |
|
74 |
|
75 #ifndef QT_NO_DATASTREAM |
|
76 QDataStream &read( QDataStream & ); // read list from stream |
|
77 QDataStream &write( QDataStream & ) const; // write list to stream |
|
78 #endif |
|
79 protected: |
|
80 QGList(); // create empty list |
|
81 QGList( const QGList & ); // make copy of other list |
|
82 virtual ~QGList(); |
|
83 |
|
84 QGList &operator=( const QGList & ); // assign from other list |
|
85 bool operator==( const QGList& ) const; |
|
86 |
|
87 void inSort( QCollection::Item ); // add item sorted in list |
|
88 void append( QCollection::Item ); // add item at end of list |
|
89 bool insertAt( uint index, QCollection::Item ); // add item at i'th position |
|
90 void relinkNode( QLNode * ); // relink as first item |
|
91 bool removeNode( QLNode * ); // remove node |
|
92 bool remove( QCollection::Item = 0 ); // remove item (0=current) |
|
93 bool removeRef( QCollection::Item = 0 ); // remove item (0=current) |
|
94 bool removeFirst(); // remove first item |
|
95 bool removeLast(); // remove last item |
|
96 bool removeAt( uint index ); // remove item at i'th position |
|
97 QCollection::Item takeNode( QLNode * ); // take out node |
|
98 QCollection::Item take(); // take out current item |
|
99 QCollection::Item takeAt( uint index ); // take out item at i'th pos |
|
100 QCollection::Item takeFirst(); // take out first item |
|
101 QCollection::Item takeLast(); // take out last item |
|
102 |
|
103 void sort(); // sort all items; |
|
104 void clear(); // remove all items |
|
105 |
|
106 int findRef( QCollection::Item, bool = TRUE ); // find exact item in list |
|
107 int find( QCollection::Item, bool = TRUE ); // find equal item in list |
|
108 |
|
109 uint containsRef( QCollection::Item ) const; // get number of exact matches |
|
110 uint contains( QCollection::Item ) const; // get number of equal matches |
|
111 |
|
112 QCollection::Item at( uint index ); // access item at i'th pos |
|
113 int at() const; // get current index |
|
114 QLNode *currentNode() const; // get current node |
|
115 |
|
116 QCollection::Item get() const; // get current item |
|
117 |
|
118 QCollection::Item cfirst() const; // get ptr to first list item |
|
119 QCollection::Item clast() const; // get ptr to last list item |
|
120 QCollection::Item first(); // set first item in list curr |
|
121 QCollection::Item last(); // set last item in list curr |
|
122 QCollection::Item next(); // set next item in list curr |
|
123 QCollection::Item prev(); // set prev item in list curr |
|
124 |
|
125 void toVector( QGVector * ) const; // put items in vector |
|
126 |
|
127 virtual int compareItems( QCollection::Item, QCollection::Item ); |
|
128 |
|
129 #ifndef QT_NO_DATASTREAM |
|
130 virtual QDataStream &read( QDataStream &, QCollection::Item & ); |
|
131 virtual QDataStream &write( QDataStream &, QCollection::Item ) const; |
|
132 #endif |
|
133 private: |
|
134 void prepend( QCollection::Item ); // add item at start of list |
|
135 |
|
136 void heapSortPushDown( QCollection::Item* heap, int first, int last ); |
|
137 |
|
138 QLNode *firstNode; // first node |
|
139 QLNode *lastNode; // last node |
|
140 QLNode *curNode; // current node |
|
141 int curIndex; // current index |
|
142 uint numNodes; // number of nodes |
|
143 QGList *iterators; // list of iterators |
|
144 |
|
145 QLNode *locate( uint ); // get node at i'th pos |
|
146 QLNode *unlink(); // unlink node |
|
147 }; |
|
148 |
|
149 |
|
150 inline uint QGList::count() const |
|
151 { |
|
152 return numNodes; |
|
153 } |
|
154 |
|
155 inline bool QGList::removeFirst() |
|
156 { |
|
157 first(); |
|
158 return remove(); |
|
159 } |
|
160 |
|
161 inline bool QGList::removeLast() |
|
162 { |
|
163 last(); |
|
164 return remove(); |
|
165 } |
|
166 |
|
167 inline int QGList::at() const |
|
168 { |
|
169 return curIndex; |
|
170 } |
|
171 |
|
172 inline QCollection::Item QGList::at( uint index ) |
|
173 { |
|
174 QLNode *n = locate( index ); |
|
175 return n ? n->data : 0; |
|
176 } |
|
177 |
|
178 inline QLNode *QGList::currentNode() const |
|
179 { |
|
180 return curNode; |
|
181 } |
|
182 |
|
183 inline QCollection::Item QGList::get() const |
|
184 { |
|
185 return curNode ? curNode->data : 0; |
|
186 } |
|
187 |
|
188 inline QCollection::Item QGList::cfirst() const |
|
189 { |
|
190 return firstNode ? firstNode->data : 0; |
|
191 } |
|
192 |
|
193 inline QCollection::Item QGList::clast() const |
|
194 { |
|
195 return lastNode ? lastNode->data : 0; |
|
196 } |
|
197 |
|
198 |
|
199 /***************************************************************************** |
|
200 QGList stream functions |
|
201 *****************************************************************************/ |
|
202 |
|
203 #ifndef QT_NO_DATASTREAM |
|
204 Q_EXPORT QDataStream &operator>>( QDataStream &, QGList & ); |
|
205 Q_EXPORT QDataStream &operator<<( QDataStream &, const QGList & ); |
|
206 #endif |
|
207 |
|
208 /***************************************************************************** |
|
209 QGListIterator class |
|
210 *****************************************************************************/ |
|
211 |
|
212 class Q_EXPORT QGListIterator // QGList iterator |
|
213 { |
|
214 friend class QGList; |
|
215 protected: |
|
216 QGListIterator( const QGList & ); |
|
217 QGListIterator( const QGListIterator & ); |
|
218 QGListIterator &operator=( const QGListIterator & ); |
|
219 ~QGListIterator(); |
|
220 |
|
221 bool atFirst() const; // test if at first item |
|
222 bool atLast() const; // test if at last item |
|
223 QCollection::Item toFirst(); // move to first item |
|
224 QCollection::Item toLast(); // move to last item |
|
225 |
|
226 QCollection::Item get() const; // get current item |
|
227 QCollection::Item operator()(); // get current and move to next |
|
228 QCollection::Item operator++(); // move to next item (prefix) |
|
229 QCollection::Item operator+=(uint); // move n positions forward |
|
230 QCollection::Item operator--(); // move to prev item (prefix) |
|
231 QCollection::Item operator-=(uint); // move n positions backward |
|
232 |
|
233 protected: |
|
234 QGList *list; // reference to list |
|
235 |
|
236 private: |
|
237 QLNode *curNode; // current node in list |
|
238 }; |
|
239 |
|
240 |
|
241 inline bool QGListIterator::atFirst() const |
|
242 { |
|
243 return curNode == list->firstNode; |
|
244 } |
|
245 |
|
246 inline bool QGListIterator::atLast() const |
|
247 { |
|
248 return curNode == list->lastNode; |
|
249 } |
|
250 |
|
251 inline QCollection::Item QGListIterator::get() const |
|
252 { |
|
253 return curNode ? curNode->data : 0; |
|
254 } |
|
255 |
|
256 |
|
257 #endif // QGLIST_H |