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

KCal Library

sortablelist.h
Go to the documentation of this file.
00001 /*
00002     This file is part of the kcal library.
00003 
00004     Copyright (c) 2006 David Jarvie <software@astrojar.org.uk>
00005 
00006     This library is free software; you can redistribute it and/or
00007     modify it under the terms of the GNU Library General Public
00008     License as published by the Free Software Foundation; either
00009     version 2 of the License, or (at your option) any later version.
00010 
00011     This library is distributed in the hope that it will be useful,
00012     but WITHOUT ANY WARRANTY; without even the implied warranty of
00013     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014     Library General Public License for more details.
00015 
00016     You should have received a copy of the GNU Library General Public License
00017     along with this library; see the file COPYING.LIB.  If not, write to
00018     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019     Boston, MA 02110-1301, USA.
00020 */
00029 #ifndef KCAL_SORTABLELIST_H
00030 #define KCAL_SORTABLELIST_H
00031 
00032 #include <QtCore/QList>
00033 #include <QtCore/QtAlgorithms>
00034 
00035 namespace KCal {
00036 
00037 //@cond PRIVATE
00038 template <class T>
00039 void qSortUnique( QList<T> &list )
00040 {
00041   if ( list.count() <= 1 ) {
00042     return;
00043   }
00044   qSort( list );
00045   typename QList<T>::iterator prev = list.begin();
00046   for ( typename QList<T>::iterator it = prev + 1;  it != list.end();  ++it ) {
00047     if ( *it == *prev ) {
00048       // Found two equal values. Search for any further equal values and remove
00049       // them all together for efficiency.
00050       while ( ++it != list.end()  &&  *it == *prev ) ;
00051       prev = it = list.erase( prev + 1, it );
00052       if ( it == list.end() ) {
00053         break;
00054       }
00055     } else {
00056       prev = it;
00057     }
00058   }
00059 }
00060 //@endcond
00061 
00085 template <class T>
00086 class SortableList : public QList<T>
00087 {
00088   public:
00092     SortableList() {}
00093 
00099     SortableList( const QList<T> &list ) : QList<T>( list ) {}   // implicit conversion
00100 
00110     bool containsSorted( const T &value ) const  { return findSorted( value ) >= 0; }
00111 
00122     int findSorted( const T &value, int start = 0 ) const;
00123 
00132     int findLE( const T &value, int start = 0 ) const;
00133 
00142     int findLT( const T &value, int start = 0 ) const;
00143 
00152     int findGE( const T &value, int start = 0 ) const;
00153 
00162     int findGT( const T &value, int start = 0 ) const;
00163 
00175     int insertSorted( const T &value );
00176 
00186     int removeSorted( const T &value, int start = 0 );
00187 
00191     void sortUnique()  { qSortUnique( *this ); }
00192 };
00193 
00194 template <class T>
00195 int SortableList<T>::findSorted( const T &value, int start ) const
00196 {
00197   // Do a binary search to find the item == value
00198   int st = start - 1;
00199   int end = QList<T>::count();
00200   while ( end - st > 1 ) {
00201     int i = ( st + end ) / 2;
00202     if ( value < QList<T>::at(i) ) {
00203       end = i;
00204     } else {
00205       st = i;
00206     }
00207   }
00208   return ( end > start && value == QList<T>::at(st) ) ? st : -1;
00209 }
00210 
00211 template <class T>
00212 int SortableList<T>::findLE( const T &value, int start ) const
00213 {
00214   // Do a binary search to find the last item <= value
00215   int st = start - 1;
00216   int end = QList<T>::count();
00217   while ( end - st > 1 ) {
00218     int i = ( st + end ) / 2;
00219     if ( value < QList<T>::at(i) ) {
00220       end = i;
00221     } else {
00222       st = i;
00223     }
00224   }
00225   return ( end > start ) ? st : -1;
00226 }
00227 
00228 template <class T>
00229 int SortableList<T>::findLT( const T &value, int start ) const
00230 {
00231   // Do a binary search to find the last item < value
00232   int st = start - 1;
00233   int end = QList<T>::count();
00234   while ( end - st > 1 ) {
00235     int i = ( st + end ) / 2;
00236     if ( value <= QList<T>::at(i) ) {
00237       end = i;
00238     } else {
00239       st = i;
00240     }
00241   }
00242   return ( end > start ) ? st : -1;
00243 }
00244 
00245 template <class T>
00246 int SortableList<T>::findGE( const T &value, int start ) const
00247 {
00248   // Do a binary search to find the first item >= value
00249   int st = start - 1;
00250   int end = QList<T>::count();
00251   while ( end - st > 1 ) {
00252     int i = ( st + end ) / 2;
00253     if ( value <= QList<T>::at(i) ) {
00254       end = i;
00255     } else {
00256       st = i;
00257     }
00258   }
00259   ++st;
00260   return ( st == QList<T>::count() ) ? -1 : st;
00261 }
00262 
00263 template <class T>
00264 int SortableList<T>::findGT( const T &value, int start ) const
00265 {
00266   // Do a binary search to find the first item > value
00267   int st = start - 1;
00268   int end = QList<T>::count();
00269   while ( end - st > 1 ) {
00270     int i = ( st + end ) / 2;
00271     if ( value < QList<T>::at(i) ) {
00272       end = i;
00273     } else {
00274       st = i;
00275     }
00276   }
00277   ++st;
00278   return ( st == QList<T>::count() ) ? -1 : st;
00279 }
00280 
00281 template <class T>
00282 int SortableList<T>::insertSorted( const T &value )
00283 {
00284   int i = findLE( value );
00285   if ( i < 0  ||  QList<T>::at(i) != value ) {
00286     QList<T>::insert( ++i, value );
00287   }
00288   return i;
00289 }
00290 
00291 template <class T>
00292 int SortableList<T>::removeSorted( const T &value, int start )
00293 {
00294   int i = findSorted( value, start );
00295   if ( i >= 0 ) {
00296     QList<T>::removeAt( i );
00297   }
00298   return i;
00299 }
00300 
00301 } // namespace KCal
00302 
00303 #endif
This file is part of the KDE documentation.
Documentation copyright © 1996-2012 The KDE developers.
Generated on Mon Aug 27 2012 22:10:05 by doxygen 1.7.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
  • Related Pages

kdepimlibs-4.8.5 API Reference

Skip menu "kdepimlibs-4.8.5 API Reference"
  • akonadi
  •   contact
  •   kmime
  • kabc
  • kalarmcal
  • kblog
  • kcal
  • kcalcore
  • kcalutils
  • kholidays
  • kimap
  • kioslave
  •   imap4
  •   mbox
  •   nntp
  • kldap
  • kmbox
  • kmime
  • kontactinterface
  • kpimidentities
  • kpimtextedit
  •   richtextbuilders
  • 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