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
35namespace KCalCore {
36
37//@cond PRIVATE
38template <class T>
39void 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*/
85template <class T>
86class SortableList : public QList<T>
87{
88public:
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
198template <class T>
199int 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
215template <class T>
216int 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
232template <class T>
233int 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
249template <class T>
250int 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
267template <class T>
268int 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
285template <class T>
286int 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
295template <class T>
296int 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