KCal Library
sortablelist.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
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
00049
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
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 ) {}
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
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
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
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
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
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 }
00302
00303 #endif