1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the test suite of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:GPL-EXCEPT$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT |
21 | ** included in the packaging of this file. Please review the following |
22 | ** information to ensure the GNU General Public License requirements will |
23 | ** be met: https://www.gnu.org/licenses/gpl-3.0.html. |
24 | ** |
25 | ** $QT_END_LICENSE$ |
26 | ** |
27 | ****************************************************************************/ |
28 | |
29 | |
30 | #ifndef QARRAY_TEST_SIMPLE_VECTOR_H |
31 | #define QARRAY_TEST_SIMPLE_VECTOR_H |
32 | |
33 | #include <QtCore/qarraydata.h> |
34 | #include <QtCore/qarraydatapointer.h> |
35 | |
36 | #include <algorithm> |
37 | |
38 | template <class T> |
39 | struct SimpleVector |
40 | { |
41 | private: |
42 | typedef QTypedArrayData<T> Data; |
43 | |
44 | public: |
45 | typedef T value_type; |
46 | typedef typename Data::iterator iterator; |
47 | typedef typename Data::const_iterator const_iterator; |
48 | |
49 | SimpleVector() |
50 | { |
51 | } |
52 | |
53 | explicit SimpleVector(size_t n) |
54 | : d(Data::allocate(n)) |
55 | { |
56 | if (n) |
57 | d->appendInitialize(n); |
58 | } |
59 | |
60 | SimpleVector(size_t n, const T &t) |
61 | : d(Data::allocate(n)) |
62 | { |
63 | if (n) |
64 | d->copyAppend(n, t); |
65 | } |
66 | |
67 | SimpleVector(const T *begin, const T *end) |
68 | : d(Data::allocate(end - begin)) |
69 | { |
70 | if (end - begin) |
71 | d->copyAppend(begin, end); |
72 | } |
73 | |
74 | SimpleVector(QArrayDataPointerRef<T> ptr) |
75 | : d(ptr) |
76 | { |
77 | } |
78 | |
79 | explicit SimpleVector(Data *ptr) |
80 | : d(ptr) |
81 | { |
82 | } |
83 | |
84 | bool empty() const { return d->size == 0; } |
85 | bool isNull() const { return d.isNull(); } |
86 | bool isEmpty() const { return this->empty(); } |
87 | |
88 | bool isStatic() const { return d->ref.isStatic(); } |
89 | bool isShared() const { return d->ref.isShared(); } |
90 | bool isSharedWith(const SimpleVector &other) const { return d == other.d; } |
91 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
92 | bool isSharable() const { return d->ref.isSharable(); } |
93 | void setSharable(bool sharable) { d.setSharable(sharable); } |
94 | #endif |
95 | |
96 | size_t size() const { return d->size; } |
97 | size_t capacity() const { return d->alloc; } |
98 | |
99 | iterator begin() { detach(); return d->begin(); } |
100 | iterator end() { detach(); return d->end(); } |
101 | |
102 | const_iterator begin() const { return d->constBegin(); } |
103 | const_iterator end() const { return d->constEnd(); } |
104 | |
105 | const_iterator constBegin() const { return begin(); } |
106 | const_iterator constEnd() const { return end(); } |
107 | |
108 | T &operator[](size_t i) { Q_ASSERT(i < size_t(d->size)); detach(); return begin()[i]; } |
109 | T &at(size_t i) { Q_ASSERT(i < size_t(d->size)); detach(); return begin()[i]; } |
110 | |
111 | const T &operator[](size_t i) const { Q_ASSERT(i < size_t(d->size)); return begin()[i]; } |
112 | const T &at(size_t i) const { Q_ASSERT(i < size_t(d->size)); return begin()[i]; } |
113 | |
114 | T &front() |
115 | { |
116 | Q_ASSERT(!isEmpty()); |
117 | detach(); |
118 | return *begin(); |
119 | } |
120 | |
121 | T &back() |
122 | { |
123 | Q_ASSERT(!isEmpty()); |
124 | detach(); |
125 | return *(end() - 1); |
126 | } |
127 | |
128 | const T &front() const |
129 | { |
130 | Q_ASSERT(!isEmpty()); |
131 | return *begin(); |
132 | } |
133 | |
134 | const T &back() const |
135 | { |
136 | Q_ASSERT(!isEmpty()); |
137 | return *(end() - 1); |
138 | } |
139 | |
140 | void reserve(size_t n) |
141 | { |
142 | if (n == 0) |
143 | return; |
144 | |
145 | if (n <= capacity()) { |
146 | if (d->capacityReserved) |
147 | return; |
148 | if (!d->ref.isShared()) { |
149 | d->capacityReserved = 1; |
150 | return; |
151 | } |
152 | } |
153 | |
154 | SimpleVector detached(Data::allocate(qMax(n, size()), |
155 | d->detachFlags() | Data::CapacityReserved)); |
156 | if (size()) |
157 | detached.d->copyAppend(constBegin(), constEnd()); |
158 | detached.swap(*this); |
159 | } |
160 | |
161 | void resize(size_t newSize) |
162 | { |
163 | if (size() == newSize) |
164 | return; |
165 | |
166 | if (d.needsDetach() || newSize > capacity()) { |
167 | SimpleVector detached(Data::allocate( |
168 | d->detachCapacity(newSize), d->detachFlags())); |
169 | if (newSize) { |
170 | if (newSize < size()) { |
171 | const T *const begin = constBegin(); |
172 | detached.d->copyAppend(begin, begin + newSize); |
173 | } else { |
174 | if (size()) { |
175 | const T *const begin = constBegin(); |
176 | detached.d->copyAppend(begin, begin + size()); |
177 | } |
178 | detached.d->appendInitialize(newSize); |
179 | } |
180 | } |
181 | detached.swap(*this); |
182 | return; |
183 | } |
184 | |
185 | if (newSize > size()) |
186 | d->appendInitialize(newSize); |
187 | else |
188 | d->truncate(newSize); |
189 | } |
190 | |
191 | void prepend(const_iterator first, const_iterator last) |
192 | { |
193 | if (!d->size) { |
194 | append(first, last); |
195 | return; |
196 | } |
197 | |
198 | if (first == last) |
199 | return; |
200 | |
201 | T *const begin = d->begin(); |
202 | if (d.needsDetach() |
203 | || capacity() - size() < size_t(last - first)) { |
204 | SimpleVector detached(Data::allocate( |
205 | d->detachCapacity(size() + (last - first)), |
206 | d->detachFlags() | Data::Grow)); |
207 | |
208 | detached.d->copyAppend(first, last); |
209 | detached.d->copyAppend(begin, begin + d->size); |
210 | detached.swap(*this); |
211 | |
212 | return; |
213 | } |
214 | |
215 | d->insert(begin, first, last); |
216 | } |
217 | |
218 | void append(const_iterator first, const_iterator last) |
219 | { |
220 | if (first == last) |
221 | return; |
222 | |
223 | if (d.needsDetach() |
224 | || capacity() - size() < size_t(last - first)) { |
225 | SimpleVector detached(Data::allocate( |
226 | d->detachCapacity(size() + (last - first)), |
227 | d->detachFlags() | Data::Grow)); |
228 | |
229 | if (d->size) { |
230 | const T *const begin = constBegin(); |
231 | detached.d->copyAppend(begin, begin + d->size); |
232 | } |
233 | detached.d->copyAppend(first, last); |
234 | detached.swap(*this); |
235 | |
236 | return; |
237 | } |
238 | |
239 | d->copyAppend(first, last); |
240 | } |
241 | |
242 | void insert(int position, const_iterator first, const_iterator last) |
243 | { |
244 | if (position < 0) |
245 | position += d->size + 1; |
246 | |
247 | if (position <= 0) { |
248 | prepend(first, last); |
249 | return; |
250 | } |
251 | |
252 | if (size_t(position) >= size()) { |
253 | append(first, last); |
254 | return; |
255 | } |
256 | |
257 | if (first == last) |
258 | return; |
259 | |
260 | const iterator begin = d->begin(); |
261 | const iterator where = begin + position; |
262 | const iterator end = begin + d->size; |
263 | if (d.needsDetach() |
264 | || capacity() - size() < size_t(last - first)) { |
265 | SimpleVector detached(Data::allocate( |
266 | d->detachCapacity(size() + (last - first)), |
267 | d->detachFlags() | Data::Grow)); |
268 | |
269 | if (position) |
270 | detached.d->copyAppend(begin, where); |
271 | detached.d->copyAppend(first, last); |
272 | detached.d->copyAppend(where, end); |
273 | detached.swap(*this); |
274 | |
275 | return; |
276 | } |
277 | |
278 | if ((first >= where && first < end) |
279 | || (last > where && last <= end)) { |
280 | // Copy overlapping data first and only then shuffle it into place |
281 | iterator start = d->begin() + position; |
282 | iterator middle = d->end(); |
283 | |
284 | d->copyAppend(first, last); |
285 | std::rotate(start, middle, d->end()); |
286 | |
287 | return; |
288 | } |
289 | |
290 | d->insert(where, first, last); |
291 | } |
292 | |
293 | void erase(iterator first, iterator last) |
294 | { |
295 | if (first == last) |
296 | return; |
297 | |
298 | const T *const begin = d->begin(); |
299 | const T *const end = begin + d->size; |
300 | |
301 | if (d.needsDetach()) { |
302 | SimpleVector detached(Data::allocate( |
303 | d->detachCapacity(size() - (last - first)), |
304 | d->detachFlags())); |
305 | if (first != begin) |
306 | detached.d->copyAppend(begin, first); |
307 | detached.d->copyAppend(last, end); |
308 | detached.swap(*this); |
309 | |
310 | return; |
311 | } |
312 | |
313 | if (last == end) |
314 | d->truncate(end - first); |
315 | else |
316 | d->erase(first, last); |
317 | } |
318 | |
319 | void swap(SimpleVector &other) |
320 | { |
321 | qSwap(d, other.d); |
322 | } |
323 | |
324 | void clear() |
325 | { |
326 | d.clear(); |
327 | } |
328 | |
329 | void detach() |
330 | { |
331 | d.detach(); |
332 | } |
333 | |
334 | static SimpleVector fromRawData(const T *data, size_t size, |
335 | QArrayData::AllocationOptions options = Data::Default) |
336 | { |
337 | return SimpleVector(Data::fromRawData(data, size, options)); |
338 | } |
339 | |
340 | private: |
341 | QArrayDataPointer<T> d; |
342 | }; |
343 | |
344 | template <class T> |
345 | bool operator==(const SimpleVector<T> &lhs, const SimpleVector<T> &rhs) |
346 | { |
347 | if (lhs.isSharedWith(rhs)) |
348 | return true; |
349 | if (lhs.size() != rhs.size()) |
350 | return false; |
351 | return std::equal(lhs.begin(), lhs.end(), rhs.begin()); |
352 | } |
353 | |
354 | template <class T> |
355 | bool operator!=(const SimpleVector<T> &lhs, const SimpleVector<T> &rhs) |
356 | { |
357 | return !(lhs == rhs); |
358 | } |
359 | |
360 | template <class T> |
361 | bool operator<(const SimpleVector<T> &lhs, const SimpleVector<T> &rhs) |
362 | { |
363 | return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); |
364 | } |
365 | |
366 | template <class T> |
367 | bool operator>(const SimpleVector<T> &lhs, const SimpleVector<T> &rhs) |
368 | { |
369 | return rhs < lhs; |
370 | } |
371 | |
372 | template <class T> |
373 | bool operator<=(const SimpleVector<T> &lhs, const SimpleVector<T> &rhs) |
374 | { |
375 | return !(rhs < lhs); |
376 | } |
377 | |
378 | template <class T> |
379 | bool operator>=(const SimpleVector<T> &lhs, const SimpleVector<T> &rhs) |
380 | { |
381 | return !(lhs < rhs); |
382 | } |
383 | |
384 | namespace std { |
385 | template <class T> |
386 | void swap(SimpleVector<T> &v1, SimpleVector<T> &v2) |
387 | { |
388 | v1.swap(v2); |
389 | } |
390 | } |
391 | |
392 | #endif // include guard |
393 | |