sortablelist.h

Go to the documentation of this file.

/*
    This file is part of the kcal library.

    Copyright (c) 2006 David Jarvie <software@astrojar.org.uk>

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public License
    along with this library; see the file COPYING.LIB.  If not, write to
    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
    Boston, MA 02110-1301, USA.
*/
#ifndef KCAL_SORTABLELIST_H
#define KCAL_SORTABLELIST_H

#include <QtCore/QList>
#include <QtCore/QtAlgorithms>

namespace KCal {

//@cond PRIVATE
template <class T>
void qSortUnique( QList<T> &list )
{
  if ( list.count() <= 1 ) {
    return;
  }
  qSort( list );
  typename QList<T>::iterator prev = list.begin();
  for ( typename QList<T>::iterator it = prev + 1;  it != list.end();  ++it ) {
    if ( *it == *prev ) {
      // Found two equal values. Search for any further equal values and remove
      // them all together for efficiency.
      while ( ++it != list.end()  &&  *it == *prev ) ;
      prev = it = list.erase( prev + 1, it );
      if ( it == list.end() ) {
        break;
      }
    } else {
      prev = it;
    }
  }
}
//@endcond

template <class T>
class SortableList : public QList<T>
{
  public:
    SortableList() {}

    SortableList( const QList<T> &list ) : QList<T>( list ) {}   // implicit conversion

    bool containsSorted( const T &value ) const  { return findSorted( value ) >= 0; }

    int findSorted( const T &value, int start = 0 ) const;

    int findLE( const T &value, int start = 0 ) const;

    int findLT( const T &value, int start = 0 ) const;

    int findGE( const T &value, int start = 0 ) const;

    int findGT( const T &value, int start = 0 ) const;

    int insertSorted( const T &value );

    int removeSorted( const T &value, int start = 0 );

    void sortUnique()  { qSortUnique( *this ); }
};

template <class T>
int SortableList<T>::findSorted( const T &value, int start ) const
{
  // Do a binary search to find the item == value
  int st = start - 1;
  int end = QList<T>::count();
  while ( end - st > 1 ) {
    int i = ( st + end ) / 2;
    if ( value < QList<T>::at(i) ) {
      end = i;
    } else {
      st = i;
    }
  }
  return ( end > start && value == QList<T>::at(st) ) ? st : -1;
}

template <class T>
int SortableList<T>::findLE( const T &value, int start ) const
{
  // Do a binary search to find the last item <= value
  int st = start - 1;
  int end = QList<T>::count();
  while ( end - st > 1 ) {
    int i = ( st + end ) / 2;
    if ( value < QList<T>::at(i) ) {
      end = i;
    } else {
      st = i;
    }
  }
  return ( end > start ) ? st : -1;
}

template <class T>
int SortableList<T>::findLT( const T &value, int start ) const
{
  // Do a binary search to find the last item < value
  int st = start - 1;
  int end = QList<T>::count();
  while ( end - st > 1 ) {
    int i = ( st + end ) / 2;
    if ( value <= QList<T>::at(i) ) {
      end = i;
    } else {
      st = i;
    }
  }
  return ( end > start ) ? st : -1;
}

template <class T>
int SortableList<T>::findGE( const T &value, int start ) const
{
  // Do a binary search to find the first item >= value
  int st = start - 1;
  int end = QList<T>::count();
  while ( end - st > 1 ) {
    int i = ( st + end ) / 2;
    if ( value <= QList<T>::at(i) ) {
      end = i;
    } else {
      st = i;
    }
  }
  ++st;
  return ( st == QList<T>::count() ) ? -1 : st;
}

template <class T>
int SortableList<T>::findGT( const T &value, int start ) const
{
  // Do a binary search to find the first item > value
  int st = start - 1;
  int end = QList<T>::count();
  while ( end - st > 1 ) {
    int i = ( st + end ) / 2;
    if ( value < QList<T>::at(i) ) {
      end = i;
    } else {
      st = i;
    }
  }
  ++st;
  return ( st == QList<T>::count() ) ? -1 : st;
}

template <class T>
int SortableList<T>::insertSorted( const T &value )
{
  int i = findLE( value );
  if ( i < 0  ||  QList<T>::at(i) != value ) {
    QList<T>::insert( ++i, value );
  }
  return i;
}

template <class T>
int SortableList<T>::removeSorted( const T &value, int start )
{
  int i = findSorted( value, start );
  if ( i >= 0 ) {
    QList<T>::removeAt( i );
  }
  return i;
}

} // namespace KCal

#endif