1 | /* |
2 | This file is part of the kcal 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 KCAL_SORTABLELIST_H |
30 | #define KCAL_SORTABLELIST_H |
31 | |
32 | #include <QtCore/QList> |
33 | #include <QtCore/QtAlgorithms> |
34 | |
35 | namespace KCal { |
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 { return findSorted( value ) >= 0; } |
111 | |
112 | /** |
113 | Search the list for the item equal to @p value. The list must be sorted; |
114 | if not, the result is undefined. |
115 | When the list is sorted, use this optimised method in preference to |
116 | QList<T>::indexOf(). |
117 | |
118 | @param value is the value to find. |
119 | @param start is the start index for search (default is from beginning). |
120 | @return index to item in list, or -1 if @p value not found in the list. |
121 | */ |
122 | int findSorted( const T &value, int start = 0 ) const; |
123 | |
124 | /** |
125 | Search the list for the last item <= @p value. The list must be sorted; |
126 | if not, the result is undefined. |
127 | |
128 | @param value is the value to find. |
129 | @param start is the start index for search (default is from beginning). |
130 | @return index to item in list, or -1 if @p value < first value in the list. |
131 | */ |
132 | int findLE( const T &value, int start = 0 ) const; |
133 | |
134 | /** |
135 | Search the list for the last item < @p value. The list must be sorted; |
136 | if not, the result is undefined. |
137 | |
138 | @param value is the value to find. |
139 | @param start is the start index for search (default is from beginning). |
140 | @return index to item in list, or -1 if @p value <= first value in the list. |
141 | */ |
142 | int findLT( const T &value, int start = 0 ) const; |
143 | |
144 | /** |
145 | Search the list for the first item >= @p value. The list must be sorted; |
146 | if not, the result is undefined. |
147 | |
148 | @param value is the value to find. |
149 | @param start is the start index for search (default is from beginning). |
150 | @return index to item in list, or -1 if @p value > last value in the list. |
151 | */ |
152 | int findGE( const T &value, int start = 0 ) const; |
153 | |
154 | /** |
155 | Search the list for the first item > @p value. The list must be sorted; |
156 | if not, the result is undefined. |
157 | |
158 | @param value is the value to find. |
159 | @param start is the start index for search (default is from beginning). |
160 | @return index to item in list, or -1 if @p value >= last value in the list. |
161 | */ |
162 | int findGT( const T &value, int start = 0 ) const; |
163 | |
164 | /** |
165 | Insert a value in the list, in correct sorted order. If the same value |
166 | is already in the list, no change is made. |
167 | |
168 | The list must already be sorted before calling this method; otherwise |
169 | the result is undefined. |
170 | |
171 | @param value is the value to insert. |
172 | @return index to inserted item in list, or to the pre-existing entry |
173 | equal to @p value. |
174 | */ |
175 | int insertSorted( const T &value ); |
176 | |
177 | /** |
178 | Remove value @p value from the list. The list must be sorted. |
179 | When the list is sorted, use this optimised method in preference to |
180 | QList<T>::removeAll(). |
181 | |
182 | @param value is the value to remove. |
183 | @param start is the start index for search (default is from beginning). |
184 | @return index to removed value, or -1 if not found. |
185 | */ |
186 | int removeSorted( const T &value, int start = 0 ); |
187 | |
188 | /** |
189 | Sort the list. Any duplicate values are removed. |
190 | */ |
191 | void sortUnique() { qSortUnique( *this ); } |
192 | }; |
193 | |
194 | template <class T> |
195 | int SortableList<T>::findSorted( const T &value, int start ) const |
196 | { |
197 | // Do a binary search to find the item == value |
198 | int st = start - 1; |
199 | int end = QList<T>::count(); |
200 | while ( end - st > 1 ) { |
201 | int i = ( st + end ) / 2; |
202 | if ( value < QList<T>::at(i) ) { |
203 | end = i; |
204 | } else { |
205 | st = i; |
206 | } |
207 | } |
208 | return ( end > start && value == QList<T>::at(st) ) ? st : -1; |
209 | } |
210 | |
211 | template <class T> |
212 | int SortableList<T>::findLE( const T &value, int start ) const |
213 | { |
214 | // Do a binary search to find the last item <= value |
215 | int st = start - 1; |
216 | int end = QList<T>::count(); |
217 | while ( end - st > 1 ) { |
218 | int i = ( st + end ) / 2; |
219 | if ( value < QList<T>::at(i) ) { |
220 | end = i; |
221 | } else { |
222 | st = i; |
223 | } |
224 | } |
225 | return ( end > start ) ? st : -1; |
226 | } |
227 | |
228 | template <class T> |
229 | int SortableList<T>::findLT( const T &value, int start ) const |
230 | { |
231 | // Do a binary search to find the last item < value |
232 | int st = start - 1; |
233 | int end = QList<T>::count(); |
234 | while ( end - st > 1 ) { |
235 | int i = ( st + end ) / 2; |
236 | if ( value <= QList<T>::at(i) ) { |
237 | end = i; |
238 | } else { |
239 | st = i; |
240 | } |
241 | } |
242 | return ( end > start ) ? st : -1; |
243 | } |
244 | |
245 | template <class T> |
246 | int SortableList<T>::findGE( const T &value, int start ) const |
247 | { |
248 | // Do a binary search to find the first item >= value |
249 | int st = start - 1; |
250 | int end = QList<T>::count(); |
251 | while ( end - st > 1 ) { |
252 | int i = ( st + end ) / 2; |
253 | if ( value <= QList<T>::at(i) ) { |
254 | end = i; |
255 | } else { |
256 | st = i; |
257 | } |
258 | } |
259 | ++st; |
260 | return ( st == QList<T>::count() ) ? -1 : st; |
261 | } |
262 | |
263 | template <class T> |
264 | int SortableList<T>::findGT( const T &value, int start ) const |
265 | { |
266 | // Do a binary search to find the first item > value |
267 | int st = start - 1; |
268 | int end = QList<T>::count(); |
269 | while ( end - st > 1 ) { |
270 | int i = ( st + end ) / 2; |
271 | if ( value < QList<T>::at(i) ) { |
272 | end = i; |
273 | } else { |
274 | st = i; |
275 | } |
276 | } |
277 | ++st; |
278 | return ( st == QList<T>::count() ) ? -1 : st; |
279 | } |
280 | |
281 | template <class T> |
282 | int SortableList<T>::insertSorted( const T &value ) |
283 | { |
284 | int i = findLE( value ); |
285 | if ( i < 0 || QList<T>::at(i) != value ) { |
286 | QList<T>::insert( ++i, value ); |
287 | } |
288 | return i; |
289 | } |
290 | |
291 | template <class T> |
292 | int SortableList<T>::removeSorted( const T &value, int start ) |
293 | { |
294 | int i = findSorted( value, start ); |
295 | if ( i >= 0 ) { |
296 | QList<T>::removeAt( i ); |
297 | } |
298 | return i; |
299 | } |
300 | |
301 | } // namespace KCal |
302 | |
303 | #endif |
304 | |