• 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 
35 namespace KCalCore {
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 
85 template <class T>
86 class 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 {
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 
198 template <class T>
199 int 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 
215 template <class T>
216 int 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 
232 template <class T>
233 int 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 
249 template <class T>
250 int 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 
267 template <class T>
268 int 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 
285 template <class T>
286 int 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 
295 template <class T>
296 int 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
TODO: KDE5:
Definition: alarm.h:47
KCalCore::SortableList::sortUnique
void sortUnique()
Sort the list.
Definition: sortablelist.h:193
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::findLE
int findLE(const T &value, int start=0) const
Search the list for the last item <= value.
Definition: sortablelist.h:216
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::removeSorted
int removeSorted(const T &value, int start=0)
Remove value value from the list.
Definition: sortablelist.h:296
KCalCore::SortableList::SortableList
SortableList(const QList< T > &list)
Constructs a sortable list by copying another one.
Definition: sortablelist.h:99
KCalCore::SortableList
A QList which can be sorted.
Definition: sortablelist.h:86
KCalCore::SortableList::SortableList
SortableList()
Constructs an empty sortable list.
Definition: sortablelist.h:92
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::insertSorted
int insertSorted(const T &value)
Insert a value in the list, in correct sorted order.
Definition: sortablelist.h:286
KCalCore::SortableList::containsSorted
bool containsSorted(const T &value) const
Return whether the list contains value value.
Definition: sortablelist.h:110
KCalCore::SortableList::findGT
int findGT(const T &value, int start=0) const
Search the list for the first item > value.
Definition: sortablelist.h:268
This file is part of the KDE documentation.
Documentation copyright © 1996-2019 The KDE developers.
Generated on Thu Jul 25 2019 00:00:00 by doxygen 1.8.15 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