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 May 14 2012 05:05:30 by doxygen 1.7.5 written by Dimitri van Heesch, © 1997-2006
Documentation copyright © 1996-2012 The KDE developers.
Generated on Mon May 14 2012 05:05:30 by doxygen 1.7.5 written by Dimitri van Heesch, © 1997-2006
KDE's Doxygen guidelines are available online.