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
35namespace KCal {
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{
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
194template <class T>
195int 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
211template <class T>
212int 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
228template <class T>
229int 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
245template <class T>
246int 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
263template <class T>
264int 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
281template <class T>
282int 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
291template <class T>
292int 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