• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdepimlibs-4.14.10 API Reference
  • KDE Home
  • Contact Us
 

KCal Library

  • kcal
sortablelist.h
Go to the documentation of this file.
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*/
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
85template <class T>
86class SortableList : public QList<T>
87{
88 public:
92 SortableList() {}
93
99 SortableList( const QList<T> &list ) : QList<T>( list ) {} // implicit conversion
100
110 bool containsSorted( const T &value ) const { return findSorted( value ) >= 0; }
111
122 int findSorted( const T &value, int start = 0 ) const;
123
132 int findLE( const T &value, int start = 0 ) const;
133
142 int findLT( const T &value, int start = 0 ) const;
143
152 int findGE( const T &value, int start = 0 ) const;
153
162 int findGT( const T &value, int start = 0 ) const;
163
175 int insertSorted( const T &value );
176
186 int removeSorted( const T &value, int start = 0 );
187
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
KCal::SortableList
A QList which can be sorted.
Definition: sortablelist.h:87
KCal::SortableList::findLE
int findLE(const T &value, int start=0) const
Search the list for the last item <= value.
Definition: sortablelist.h:212
KCal::SortableList::findLT
int findLT(const T &value, int start=0) const
Search the list for the last item < value.
Definition: sortablelist.h:229
KCal::SortableList::findGT
int findGT(const T &value, int start=0) const
Search the list for the first item > value.
Definition: sortablelist.h:264
KCal::SortableList::insertSorted
int insertSorted(const T &value)
Insert a value in the list, in correct sorted order.
Definition: sortablelist.h:282
KCal::SortableList::findGE
int findGE(const T &value, int start=0) const
Search the list for the first item >= value.
Definition: sortablelist.h:246
KCal::SortableList::findSorted
int findSorted(const T &value, int start=0) const
Search the list for the item equal to value.
Definition: sortablelist.h:195
KCal::SortableList::removeSorted
int removeSorted(const T &value, int start=0)
Remove value value from the list.
Definition: sortablelist.h:292
KCal::SortableList::SortableList
SortableList(const QList< T > &list)
Constructs a sortable list by copying another one.
Definition: sortablelist.h:99
KCal::SortableList::SortableList
SortableList()
Constructs an empty sortable list.
Definition: sortablelist.h:92
KCal::SortableList::containsSorted
bool containsSorted(const T &value) const
Return whether the list contains value value.
Definition: sortablelist.h:110
KCal::SortableList::sortUnique
void sortUnique()
Sort the list.
Definition: sortablelist.h:191
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Thu Jul 21 2022 00:00:00 by doxygen 1.9.5 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

KCal Library

Skip menu "KCal Library"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Related Pages

kdepimlibs-4.14.10 API Reference

Skip menu "kdepimlibs-4.14.10 API Reference"
  • akonadi
  •   contact
  •   kmime
  •   socialutils
  • kabc
  • kalarmcal
  • kblog
  • kcal
  • kcalcore
  • kcalutils
  • kholidays
  • kimap
  • kioslave
  •   imap4
  •   mbox
  •   nntp
  • kldap
  • kmbox
  • kmime
  • kontactinterface
  • kpimidentities
  • kpimtextedit
  • kpimutils
  • kresources
  • ktnef
  • kxmlrpcclient
  • mailtransport
  • microblog
  • qgpgme
  • syndication
  •   atom
  •   rdf
  •   rss2
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal