1 | /* |
2 | This file is part of the kcalcore library. |
3 | |
4 | Copyright (c) 2006 David Jarvie <software@astrojar.org.uk> |
5 | |
6 | This library is free software; you can redistribute it and/or |
7 | modify it under the terms of the GNU Library General Public |
8 | License as published by the Free Software Foundation; either |
9 | version 2 of the License, or (at your option) any later version. |
10 | |
11 | This library is distributed in the hope that it will be useful, |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | Library General Public License for more details. |
15 | |
16 | You should have received a copy of the GNU Library General Public License |
17 | along with this library; see the file COPYING.LIB. If not, write to |
18 | the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
19 | Boston, MA 02110-1301, USA. |
20 | */ |
21 | /** |
22 | @file |
23 | This file is part of the API for handling calendar data and |
24 | defines the Sortable List class. |
25 | |
26 | @author David Jarvie \<software@astrojar.org.uk\>. |
27 | */ |
28 | |
29 | #ifndef KCALCORE_SORTABLELIST_H |
30 | #define KCALCORE_SORTABLELIST_H |
31 | |
32 | #include <QtCore/QList> |
33 | #include <QtCore/QtAlgorithms> |
34 | |
35 | namespace KCalCore { |
36 | |
37 | //@cond PRIVATE |
38 | template <class T> |
39 | void qSortUnique(QList<T> &list) |
40 | { |
41 | if (list.count() <= 1) { |
42 | return; |
43 | } |
44 | qSort(list); |
45 | typename QList<T>::iterator prev = list.begin(); |
46 | for (typename QList<T>::iterator it = prev + 1; it != list.end(); ++it) { |
47 | if (*it == *prev) { |
48 | // Found two equal values. Search for any further equal values and remove |
49 | // them all together for efficiency. |
50 | while (++it != list.end() && *it == *prev) ; |
51 | prev = it = list.erase(prev + 1, it); |
52 | if (it == list.end()) { |
53 | break; |
54 | } |
55 | } else { |
56 | prev = it; |
57 | } |
58 | } |
59 | } |
60 | //@endcond |
61 | |
62 | /** |
63 | @brief A QList which can be sorted |
64 | |
65 | For a QList is capable of being sorted, SortedList provides additional |
66 | optimized methods which can be used when the list is sorted and has no |
67 | duplicate entries. |
68 | |
69 | Because SortableList has no data members, an object may be referred to |
70 | interchangeably as either a QList or SortableList. Just bear in mind that |
71 | the results of the SortableList methods are undefined when the list is |
72 | unsorted or contains duplicate entries. |
73 | |
74 | To sort the list and remove duplicate entries, thereby allowing use of |
75 | other SortableList methods, use sortUnique(). Once sortUnique() has been |
76 | called, use findSorted(), containsSorted() and removeSorted() in preference |
77 | to QList::indexOf(), QList::contains() and QList::removeAll(). Use findLE(), |
78 | findLT(), findGE(), findGT() to find the index to the nearest value in the |
79 | list which is <=, <, >= or > a given value. To add a value to the list, |
80 | use insertSorted() in preference to insert(), append(), prepend(), |
81 | operator<<() or operator+=(). |
82 | |
83 | @author David Jarvie \<software@astrojar.org.uk\>. |
84 | */ |
85 | template <class T> |
86 | class SortableList : public QList<T> |
87 | { |
88 | public: |
89 | /** |
90 | Constructs an empty sortable list. |
91 | */ |
92 | SortableList() {} |
93 | |
94 | /** |
95 | Constructs a sortable list by copying another one. |
96 | |
97 | @param list is the list to copy. |
98 | */ |
99 | SortableList(const QList<T> &list) : QList<T>(list) {} // implicit conversion |
100 | |
101 | /** |
102 | Return whether the list contains value @p value. The list must be sorted; |
103 | if not, the result is undefined. |
104 | When the list is sorted, use this optimised method in preference to |
105 | QList<T>::contains(). |
106 | |
107 | @param value is the value to find. |
108 | @return true if list contains @p value; false otherwise. |
109 | */ |
110 | bool containsSorted(const T &value) const { |
111 | return findSorted(value) >= 0; |
112 | } |
113 | |
114 | /** |
115 | Search the list for the item equal to @p value. The list must be sorted; |
116 | if not, the result is undefined. |
117 | When the list is sorted, use this optimised method in preference to |
118 | QList<T>::indexOf(). |
119 | |
120 | @param value is the value to find. |
121 | @param start is the start index for search (default is from beginning). |
122 | @return index to item in list, or -1 if @p value not found in the list. |
123 | */ |
124 | int findSorted(const T &value, int start = 0) const; |
125 | |
126 | /** |
127 | Search the list for the last item <= @p value. The list must be sorted; |
128 | if not, the result is undefined. |
129 | |
130 | @param value is the value to find. |
131 | @param start is the start index for search (default is from beginning). |
132 | @return index to item in list, or -1 if @p value < first value in the list. |
133 | */ |
134 | int findLE(const T &value, int start = 0) const; |
135 | |
136 | /** |
137 | Search the list for the last item < @p value. The list must be sorted; |
138 | if not, the result is undefined. |
139 | |
140 | @param value is the value to find. |
141 | @param start is the start index for search (default is from beginning). |
142 | @return index to item in list, or -1 if @p value <= first value in the list. |
143 | */ |
144 | int findLT(const T &value, int start = 0) const; |
145 | |
146 | /** |
147 | Search the list for the first item >= @p value. The list must be sorted; |
148 | if not, the result is undefined. |
149 | |
150 | @param value is the value to find. |
151 | @param start is the start index for search (default is from beginning). |
152 | @return index to item in list, or -1 if @p value > last value in the list. |
153 | */ |
154 | int findGE(const T &value, int start = 0) const; |
155 | |
156 | /** |
157 | Search the list for the first item > @p value. The list must be sorted; |
158 | if not, the result is undefined. |
159 | |
160 | @param value is the value to find. |
161 | @param start is the start index for search (default is from beginning). |
162 | @return index to item in list, or -1 if @p value >= last value in the list. |
163 | */ |
164 | int findGT(const T &value, int start = 0) const; |
165 | |
166 | /** |
167 | Insert a value in the list, in correct sorted order. If the same value |
168 | is already in the list, no change is made. |
169 | |
170 | The list must already be sorted before calling this method; otherwise |
171 | the result is undefined. |
172 | |
173 | @param value is the value to insert. |
174 | @return index to inserted item in list, or to the pre-existing entry |
175 | equal to @p value. |
176 | */ |
177 | int insertSorted(const T &value); |
178 | |
179 | /** |
180 | Remove value @p value from the list. The list must be sorted. |
181 | When the list is sorted, use this optimised method in preference to |
182 | QList<T>::removeAll(). |
183 | |
184 | @param value is the value to remove. |
185 | @param start is the start index for search (default is from beginning). |
186 | @return index to removed value, or -1 if not found. |
187 | */ |
188 | int removeSorted(const T &value, int start = 0); |
189 | |
190 | /** |
191 | Sort the list. Any duplicate values are removed. |
192 | */ |
193 | void sortUnique() { |
194 | qSortUnique(*this); |
195 | } |
196 | }; |
197 | |
198 | template <class T> |
199 | int SortableList<T>::findSorted(const T &value, int start) const |
200 | { |
201 | // Do a binary search to find the item == value |
202 | int st = start - 1; |
203 | int end = QList<T>::count(); |
204 | while (end - st > 1) { |
205 | int i = (st + end) / 2; |
206 | if (value < QList<T>::at(i)) { |
207 | end = i; |
208 | } else { |
209 | st = i; |
210 | } |
211 | } |
212 | return (end > start && value == QList<T>::at(st)) ? st : -1; |
213 | } |
214 | |
215 | template <class T> |
216 | int SortableList<T>::findLE(const T &value, int start) const |
217 | { |
218 | // Do a binary search to find the last item <= value |
219 | int st = start - 1; |
220 | int end = QList<T>::count(); |
221 | while (end - st > 1) { |
222 | int i = (st + end) / 2; |
223 | if (value < QList<T>::at(i)) { |
224 | end = i; |
225 | } else { |
226 | st = i; |
227 | } |
228 | } |
229 | return (end > start) ? st : -1; |
230 | } |
231 | |
232 | template <class T> |
233 | int SortableList<T>::findLT(const T &value, int start) const |
234 | { |
235 | // Do a binary search to find the last item < value |
236 | int st = start - 1; |
237 | int end = QList<T>::count(); |
238 | while (end - st > 1) { |
239 | int i = (st + end) / 2; |
240 | if (value <= QList<T>::at(i)) { |
241 | end = i; |
242 | } else { |
243 | st = i; |
244 | } |
245 | } |
246 | return (end > start) ? st : -1; |
247 | } |
248 | |
249 | template <class T> |
250 | int SortableList<T>::findGE(const T &value, int start) const |
251 | { |
252 | // Do a binary search to find the first item >= value |
253 | int st = start - 1; |
254 | int end = QList<T>::count(); |
255 | while (end - st > 1) { |
256 | int i = (st + end) / 2; |
257 | if (value <= QList<T>::at(i)) { |
258 | end = i; |
259 | } else { |
260 | st = i; |
261 | } |
262 | } |
263 | ++st; |
264 | return (st == QList<T>::count()) ? -1 : st; |
265 | } |
266 | |
267 | template <class T> |
268 | int SortableList<T>::findGT(const T &value, int start) const |
269 | { |
270 | // Do a binary search to find the first item > value |
271 | int st = start - 1; |
272 | int end = QList<T>::count(); |
273 | while (end - st > 1) { |
274 | int i = (st + end) / 2; |
275 | if (value < QList<T>::at(i)) { |
276 | end = i; |
277 | } else { |
278 | st = i; |
279 | } |
280 | } |
281 | ++st; |
282 | return (st == QList<T>::count()) ? -1 : st; |
283 | } |
284 | |
285 | template <class T> |
286 | int SortableList<T>::insertSorted(const T &value) |
287 | { |
288 | int i = findLE(value); |
289 | if (i < 0 || QList<T>::at(i) != value) { |
290 | QList<T>::insert(++i, value); |
291 | } |
292 | return i; |
293 | } |
294 | |
295 | template <class T> |
296 | int SortableList<T>::removeSorted(const T &value, int start) |
297 | { |
298 | int i = findSorted(value, start); |
299 | if (i >= 0) { |
300 | QList<T>::removeAt(i); |
301 | } |
302 | return i; |
303 | } |
304 | |
305 | } // namespace KCalCore |
306 | |
307 | #endif |
308 | |