1 | /****************************************************************************
|
---|
2 | **
|
---|
3 | ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
|
---|
4 | ** All rights reserved.
|
---|
5 | ** Contact: Nokia Corporation ([email protected])
|
---|
6 | **
|
---|
7 | ** This file is part of the qt3to4 porting application of the Qt Toolkit.
|
---|
8 | **
|
---|
9 | ** $QT_BEGIN_LICENSE:LGPL$
|
---|
10 | ** Commercial Usage
|
---|
11 | ** Licensees holding valid Qt Commercial licenses may use this file in
|
---|
12 | ** accordance with the Qt Commercial License Agreement provided with the
|
---|
13 | ** Software or, alternatively, in accordance with the terms contained in
|
---|
14 | ** a written agreement between you and Nokia.
|
---|
15 | **
|
---|
16 | ** GNU Lesser General Public License Usage
|
---|
17 | ** Alternatively, this file may be used under the terms of the GNU Lesser
|
---|
18 | ** General Public License version 2.1 as published by the Free Software
|
---|
19 | ** Foundation and appearing in the file LICENSE.LGPL included in the
|
---|
20 | ** packaging of this file. Please review the following information to
|
---|
21 | ** ensure the GNU Lesser General Public License version 2.1 requirements
|
---|
22 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
|
---|
23 | **
|
---|
24 | ** In addition, as a special exception, Nokia gives you certain additional
|
---|
25 | ** rights. These rights are described in the Nokia Qt LGPL Exception
|
---|
26 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
|
---|
27 | **
|
---|
28 | ** GNU General Public License Usage
|
---|
29 | ** Alternatively, this file may be used under the terms of the GNU
|
---|
30 | ** General Public License version 3.0 as published by the Free Software
|
---|
31 | ** Foundation and appearing in the file LICENSE.GPL included in the
|
---|
32 | ** packaging of this file. Please review the following information to
|
---|
33 | ** ensure the GNU General Public License version 3.0 requirements will be
|
---|
34 | ** met: http://www.gnu.org/copyleft/gpl.html.
|
---|
35 | **
|
---|
36 | ** If you have questions regarding the use of this file, please contact
|
---|
37 | ** Nokia at [email protected].
|
---|
38 | ** $QT_END_LICENSE$
|
---|
39 | **
|
---|
40 | ****************************************************************************/
|
---|
41 |
|
---|
42 | #ifndef LIST_H
|
---|
43 | #define LIST_H
|
---|
44 |
|
---|
45 | #include "smallobject.h"
|
---|
46 | #include <QtGlobal>
|
---|
47 |
|
---|
48 | QT_BEGIN_NAMESPACE
|
---|
49 |
|
---|
50 | template <typename T>
|
---|
51 | class List
|
---|
52 | {
|
---|
53 | struct Data
|
---|
54 | {
|
---|
55 | int alloc, size;
|
---|
56 | T array[1];
|
---|
57 | };
|
---|
58 | pool *p;
|
---|
59 | Data *d;
|
---|
60 |
|
---|
61 | public:
|
---|
62 | inline List(pool *_pool) : p(_pool), d(0) { d = malloc(16); d->size = 0; d->alloc = 16; }
|
---|
63 |
|
---|
64 | inline List(const List &v) : d(0) { operator=(v); }
|
---|
65 | inline ~List() { d = 0; }
|
---|
66 | List &operator=(const List &v);
|
---|
67 |
|
---|
68 | bool operator==(const List &v) const;
|
---|
69 | inline bool operator!=(const List &v) const { return !(*this == v); }
|
---|
70 |
|
---|
71 | inline int size() const { return d->size; }
|
---|
72 | inline bool isEmpty() const { return d->size == 0; }
|
---|
73 |
|
---|
74 | inline int capacity() const { return d->alloc; }
|
---|
75 | void reserve(int alloc);
|
---|
76 |
|
---|
77 | inline T* data() { return d->array; }
|
---|
78 | inline const T* data() const { return d->array; }
|
---|
79 | void clear();
|
---|
80 |
|
---|
81 | const T &at(int i) const;
|
---|
82 | T &operator[](int i);
|
---|
83 | const T &operator[](int i) const;
|
---|
84 | void append(const T &t);
|
---|
85 | void prepend(const T &t);
|
---|
86 | void insert(int i, const T &t);
|
---|
87 | void insert(int i, int n, const T &t);
|
---|
88 | void replace(int i, const T &t);
|
---|
89 | void remove(int i);
|
---|
90 | void remove(int i, int n);
|
---|
91 |
|
---|
92 | List &fill(const T &t, int size = -1);
|
---|
93 |
|
---|
94 | int indexOf(const T &t, int from = 0) const;
|
---|
95 | int lastIndexOf(const T &t, int from = -1) const;
|
---|
96 | bool contains(const T &t) const;
|
---|
97 | int count(const T &t) const;
|
---|
98 |
|
---|
99 | // STL-style
|
---|
100 | typedef T* iterator;
|
---|
101 | typedef const T* const_iterator;
|
---|
102 | inline iterator begin() { return d->array; }
|
---|
103 | inline const_iterator begin() const { return d->array; }
|
---|
104 | inline iterator end() { return d->array + d->size; }
|
---|
105 | inline const_iterator end() const { return d->array + d->size; }
|
---|
106 | iterator insert(iterator before, int n, const T &x);
|
---|
107 | inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
|
---|
108 | iterator erase(iterator begin, iterator end);
|
---|
109 | inline iterator erase(iterator pos) { return erase(pos, pos+1); }
|
---|
110 |
|
---|
111 | // more Qt
|
---|
112 | inline int count() const { return d->size; }
|
---|
113 | inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
|
---|
114 | inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }
|
---|
115 | inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }
|
---|
116 | inline const T& last() const { Q_ASSERT(!isEmpty()); return *(end()-1); }
|
---|
117 |
|
---|
118 | T value(int i) const;
|
---|
119 | T value(int i, const T &defaultValue) const;
|
---|
120 |
|
---|
121 | // STL compatibility
|
---|
122 | typedef T value_type;
|
---|
123 | typedef value_type* pointer;
|
---|
124 | typedef const value_type* const_pointer;
|
---|
125 | typedef value_type& reference;
|
---|
126 | typedef const value_type& const_reference;
|
---|
127 | #ifndef QT_NO_STL
|
---|
128 | typedef ptrdiff_t difference_type;
|
---|
129 | #else
|
---|
130 | typedef int difference_type;
|
---|
131 | #endif
|
---|
132 | typedef iterator Iterator;
|
---|
133 | typedef const_iterator ConstIterator;
|
---|
134 | typedef int size_type;
|
---|
135 | inline void push_back(const T &t) { append(t); }
|
---|
136 | inline void push_front(const T &t) { prepend(t); }
|
---|
137 | void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); }
|
---|
138 | void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); }
|
---|
139 | inline bool empty() const
|
---|
140 | { return d->size == 0; }
|
---|
141 | inline T& front() { return first(); }
|
---|
142 | inline const_reference front() const { return first(); }
|
---|
143 | inline reference back() { return last(); }
|
---|
144 | inline const_reference back() const { return last(); }
|
---|
145 |
|
---|
146 | //comfort
|
---|
147 | List &operator+=(const List &l);
|
---|
148 | inline List operator+(const List &l) const
|
---|
149 | { List n = *this; n += l; return n; }
|
---|
150 | inline void operator+=(const T &t)
|
---|
151 | { append(t); }
|
---|
152 | inline List &operator<< (const T &t)
|
---|
153 | { append(t); return *this; }
|
---|
154 |
|
---|
155 | private:
|
---|
156 | Data *malloc(int alloc);
|
---|
157 | };
|
---|
158 |
|
---|
159 | template <typename T>
|
---|
160 | inline void List<T>::clear()
|
---|
161 | { d->size = 0; }
|
---|
162 |
|
---|
163 | template <typename T>
|
---|
164 | inline const T &List<T>::at(int i) const
|
---|
165 | { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::at", "index out of range");
|
---|
166 | return d->array[i]; }
|
---|
167 | template <typename T>
|
---|
168 | inline const T &List<T>::operator[](int i) const
|
---|
169 | { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::operator[]", "index out of range");
|
---|
170 | return d->array[i]; }
|
---|
171 | template <typename T>
|
---|
172 | inline T &List<T>::operator[](int i)
|
---|
173 | { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::operator[]", "index out of range");
|
---|
174 | return d->array[i]; }
|
---|
175 | template <typename T>
|
---|
176 | inline void List<T>::insert(int i, const T &t)
|
---|
177 | { Q_ASSERT_X(i >= 0 && i <= d->size, "List<T>::insert", "index out of range");
|
---|
178 | insert(begin()+i, 1, t); }
|
---|
179 | template <typename T>
|
---|
180 | inline void List<T>::insert(int i, int n, const T &t)
|
---|
181 | { Q_ASSERT_X(i >= 0 && i <= d->size, "List<T>::insert", "index out of range");
|
---|
182 | insert(begin() + i, n, t); }
|
---|
183 | template <typename T>
|
---|
184 | inline void List<T>::remove(int i, int n)
|
---|
185 | { Q_ASSERT_X(i >= 0 && i + n <= d->size, "List<T>::remove", "index out of range");
|
---|
186 | erase(begin() + i, begin() + i + n); }
|
---|
187 | template <typename T>
|
---|
188 | inline void List<T>::remove(int i)
|
---|
189 | { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::remove", "index out of range");
|
---|
190 | erase(begin() + i, begin() + i + 1); }
|
---|
191 | template <typename T>
|
---|
192 | inline void List<T>::prepend(const T &t)
|
---|
193 | { insert(begin(), 1, t); }
|
---|
194 | template <typename T>
|
---|
195 | inline void List<T>::replace(int i, const T &t)
|
---|
196 | { Q_ASSERT_X(i >= 0 && i < d->size, "List<T>::replace", "index out of range");
|
---|
197 | data()[i] = t; }
|
---|
198 |
|
---|
199 | template <typename T>
|
---|
200 | List<T> &List<T>::operator=(const List<T> &v)
|
---|
201 | {
|
---|
202 | p = v.p;
|
---|
203 | d = malloc(v.d->alloc);
|
---|
204 | memcpy(d, v.d, sizeof(Data) + (v.d->size - 1) * sizeof(T));
|
---|
205 | return *this;
|
---|
206 | }
|
---|
207 |
|
---|
208 | template <typename T>
|
---|
209 | inline typename List<T>::Data *List<T>::malloc(int alloc)
|
---|
210 | {
|
---|
211 | return static_cast<Data *>(p->allocate(sizeof(Data) + (alloc - 1) * sizeof(T)));
|
---|
212 | }
|
---|
213 |
|
---|
214 | template <typename T>
|
---|
215 | void List<T>::reserve(int alloc)
|
---|
216 | {
|
---|
217 | if (alloc <= d->alloc)
|
---|
218 | return;
|
---|
219 | alloc <<= 2;
|
---|
220 | d = static_cast<Data *>(p->reallocate(d, sizeof(Data) + d->alloc * sizeof(T),
|
---|
221 | sizeof(Data) + (alloc - 1) * sizeof(T)));
|
---|
222 | d->alloc = alloc;
|
---|
223 | }
|
---|
224 |
|
---|
225 | template<typename T>
|
---|
226 | T List<T>::value(int i) const
|
---|
227 | {
|
---|
228 | if(i < 0 || i >= d->size) {
|
---|
229 | return T();
|
---|
230 | }
|
---|
231 | return d->array[i];
|
---|
232 | }
|
---|
233 | template<typename T>
|
---|
234 | T List<T>::value(int i, const T& defaultValue) const
|
---|
235 | {
|
---|
236 | return ((i < 0 || i >= d->size) ? defaultValue : d->array[i]);
|
---|
237 | }
|
---|
238 |
|
---|
239 | template <typename T>
|
---|
240 | void List<T>::append(const T &t)
|
---|
241 | {
|
---|
242 | reserve(d->size + 1);
|
---|
243 | d->array[d->size++] = t;
|
---|
244 | }
|
---|
245 |
|
---|
246 |
|
---|
247 | template <typename T>
|
---|
248 | typename List<T>::iterator List<T>::insert(iterator before, size_type n, const T& t)
|
---|
249 | {
|
---|
250 | int p = before - d->array;
|
---|
251 | if (n != 0) {
|
---|
252 | reserve(d->size + n);
|
---|
253 | T *b = d->array+p;
|
---|
254 | T *i = b+n;
|
---|
255 | memmove(i, b, (d->size-p)*sizeof(T));
|
---|
256 | while (i != b)
|
---|
257 | *(--i) = t;
|
---|
258 | }
|
---|
259 | d->size += n;
|
---|
260 | return d->array+p;
|
---|
261 | }
|
---|
262 |
|
---|
263 | template <typename T>
|
---|
264 | typename List<T>::iterator List<T>::erase(iterator begin, iterator end)
|
---|
265 | {
|
---|
266 | int f = begin - d->array;
|
---|
267 | int l = end - d->array;
|
---|
268 | int n = l - f;
|
---|
269 | memmove(d->array + f, d->array + l, (d->size-l)*sizeof(T));
|
---|
270 | d->size -= n;
|
---|
271 | return d->array + f;
|
---|
272 | }
|
---|
273 |
|
---|
274 | template <typename T>
|
---|
275 | bool List<T>::operator==(const List<T> &v) const
|
---|
276 | {
|
---|
277 | if (d->size != v.d->size)
|
---|
278 | return false;
|
---|
279 | T* b = d->array;
|
---|
280 | T* i = b + d->size;
|
---|
281 | T* j = v.d->array + d->size;
|
---|
282 | while (i != b)
|
---|
283 | if (!(*--i == *--j))
|
---|
284 | return false;
|
---|
285 | return true;
|
---|
286 | }
|
---|
287 |
|
---|
288 | template <typename T>
|
---|
289 | List<T> &List<T>::fill(const T &t, int size)
|
---|
290 | {
|
---|
291 | resize(size < 0 ? d->size : size);
|
---|
292 | if (d->size) {
|
---|
293 | T* i = d->array + d->size;
|
---|
294 | T* b = d->array;
|
---|
295 | while (i != b)
|
---|
296 | *--i = t;
|
---|
297 | }
|
---|
298 | return *this;
|
---|
299 | }
|
---|
300 |
|
---|
301 | template <typename T>
|
---|
302 | List<T> &List<T>::operator+=(const List &l)
|
---|
303 | {
|
---|
304 | int newSize = d->size + l.d->size;
|
---|
305 | reserve(newSize);
|
---|
306 |
|
---|
307 | T *w = d->array + newSize;
|
---|
308 | T *i = l.d->array + l.d->size;
|
---|
309 | T *b = l.d->array;
|
---|
310 | while (i != b)
|
---|
311 | *--w = *--i;
|
---|
312 | d->size = newSize;
|
---|
313 | return *this;
|
---|
314 | }
|
---|
315 |
|
---|
316 | template <typename T>
|
---|
317 | int List<T>::indexOf(const T &t, int from) const
|
---|
318 | {
|
---|
319 | if (from < 0)
|
---|
320 | from = qMax(from + d->size, 0);
|
---|
321 | if (from < d->size) {
|
---|
322 | T* n = d->array + from - 1;
|
---|
323 | T* e = d->array + d->size;
|
---|
324 | while (++n != e)
|
---|
325 | if (*n == t)
|
---|
326 | return n - d->array;
|
---|
327 | }
|
---|
328 | return -1;
|
---|
329 | }
|
---|
330 |
|
---|
331 | template <typename T>
|
---|
332 | int List<T>::lastIndexOf(const T &t, int from) const
|
---|
333 | {
|
---|
334 | if (from < 0)
|
---|
335 | from += d->size;
|
---|
336 | else if (from >= d->size)
|
---|
337 | from = d->size-1;
|
---|
338 | if (from >= 0) {
|
---|
339 | T* b = d->array;
|
---|
340 | T* n = d->array + from + 1;
|
---|
341 | while (n != b) {
|
---|
342 | if (*--n == t)
|
---|
343 | return n - b;
|
---|
344 | }
|
---|
345 | }
|
---|
346 | return -1;
|
---|
347 | }
|
---|
348 |
|
---|
349 | template <typename T>
|
---|
350 | bool List<T>::contains(const T &t) const
|
---|
351 | {
|
---|
352 | T* b = d->array;
|
---|
353 | T* i = d->array + d->size;
|
---|
354 | while (i != b)
|
---|
355 | if (*--i == t)
|
---|
356 | return true;
|
---|
357 | return false;
|
---|
358 | }
|
---|
359 |
|
---|
360 | template <typename T>
|
---|
361 | int List<T>::count(const T &t) const
|
---|
362 | {
|
---|
363 | int c = 0;
|
---|
364 | T* b = d->array;
|
---|
365 | T* i = d->array + d->size;
|
---|
366 | while (i != b)
|
---|
367 | if (*--i == t)
|
---|
368 | ++c;
|
---|
369 | return c;
|
---|
370 | }
|
---|
371 |
|
---|
372 | QT_END_NAMESPACE
|
---|
373 |
|
---|
374 | #endif // LIST_H
|
---|