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

KCalCore Library

  • kcalcore
sortablelist.h
Go to the documentation of this file.
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*/
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
85template <class T>
86class SortableList : public QList<T>
87{
88public:
92 SortableList() {}
93
99 SortableList(const QList<T> &list) : QList<T>(list) {} // implicit conversion
100
110 bool containsSorted(const T &value) const {
111 return findSorted(value) >= 0;
112 }
113
124 int findSorted(const T &value, int start = 0) const;
125
134 int findLE(const T &value, int start = 0) const;
135
144 int findLT(const T &value, int start = 0) const;
145
154 int findGE(const T &value, int start = 0) const;
155
164 int findGT(const T &value, int start = 0) const;
165
177 int insertSorted(const T &value);
178
188 int removeSorted(const T &value, int start = 0);
189
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
KCalCore::SortableList
A QList which can be sorted.
Definition sortablelist.h:87
KCalCore::SortableList::findGE
int findGE(const T &value, int start=0) const
Search the list for the first item >= value.
Definition sortablelist.h:250
KCalCore::SortableList::findLT
int findLT(const T &value, int start=0) const
Search the list for the last item < value.
Definition sortablelist.h:233
KCalCore::SortableList::insertSorted
int insertSorted(const T &value)
Insert a value in the list, in correct sorted order.
Definition sortablelist.h:286
KCalCore::SortableList::sortUnique
void sortUnique()
Sort the list.
Definition sortablelist.h:193
KCalCore::SortableList::findGT
int findGT(const T &value, int start=0) const
Search the list for the first item > value.
Definition sortablelist.h:268
KCalCore::SortableList::SortableList
SortableList()
Constructs an empty sortable list.
Definition sortablelist.h:92
KCalCore::SortableList::removeSorted
int removeSorted(const T &value, int start=0)
Remove value value from the list.
Definition sortablelist.h:296
KCalCore::SortableList::findSorted
int findSorted(const T &value, int start=0) const
Search the list for the item equal to value.
Definition sortablelist.h:199
KCalCore::SortableList::containsSorted
bool containsSorted(const T &value) const
Return whether the list contains value value.
Definition sortablelist.h:110
KCalCore::SortableList::SortableList
SortableList(const QList< T > &list)
Constructs a sortable list by copying another one.
Definition sortablelist.h:99
KCalCore::SortableList::findLE
int findLE(const T &value, int start=0) const
Search the list for the last item <= value.
Definition sortablelist.h:216
KCalCore
TODO: KDE5:
Definition alarm.h:47
qHash
static uint qHash(const KDateTime &dt)
Private class that helps to provide binary compatibility between releases.
Definition occurrenceiterator.cpp:157
This file is part of the KDE documentation.
Documentation copyright © 1996-2024 The KDE developers.
Generated on Wed Jan 24 2024 00:00:00 by doxygen 1.10.0 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

KCalCore Library

Skip menu "KCalCore 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