QGpCoreTools/SortedVector.h

Go to the documentation of this file.

/***************************************************************************
**
**  This file is part of QGpCoreTools.
**
**  This library is free software; you can redistribute it and/or
**  modify it under the terms of the GNU Lesser General Public
**  License as published by the Free Software Foundation; either
**  version 2.1 of the License, or (at your option) any later version.
**
**  This file 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 Lesser General Public
**  License for more details.
**
**  You should have received a copy of the GNU Lesser General Public
**  License along with this library; if not, write to the Free Software
**  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
**
**  See http://www.geopsy.org for more information.
**
**  Created: 2010-07-27
**  Authors:
**    Marc Wathelet (LGIT, Grenoble, France)
**
***************************************************************************/

#ifndef SORTEDVECTOR_H
#define SORTEDVECTOR_H

#include <QtCore>

#include "QGpCoreToolsDLLExport.h"

namespace QGpCoreTools {

template <class Key, class T>
class QGPCORETOOLS_EXPORT SortedVector : private QVector<T *>
{
public:
  SortedVector() {_n2=1;}

  bool isEmpty() const {return QVector<T *>::isEmpty();}
  int count() const {return QVector<T *>::count();}
  T * at(int index) const {return QVector<T *>::at(index);}

  void insert(T * o);
  void remove(int index);
  void clear();
  void reserve(int n) {QVector<T *>::reserve(n);}

  void append(T * o) {QVector<T *>::append(o);}
  void sort() {qSort(QVector<T *>::begin(), QVector<T *>::end(), lessThan);}

  bool contains(const Key& k) const {return indexOf(k)>-1;}
  int indexOf(const Key& k) const;
  const QVector<T *>& vector() const {return *this;}
private:
  static bool lessThan(const T * o1, const T * o2) {return o1->key()<o2->key();}
  int indexAfter(const Key& k) const;

  int _n2;
};

template<class Key, class T>
int SortedVector<Key, T>::indexOf(const Key& k) const
{
  if(count()<12) { /* For few elements, faster to check systematically
                      n integer comparisons
                      n increments
                      n object comparisons
                   */
    for(int i=count()-1; i>=0; i--) {
      if(k==at(i)->key()) return i;
    }
    return -1;
  } else {        /*
                    4+2*l object comparisons
                    2*l   integer comparisons
                    3*l   increments (including bit shifts)
                    With l=ceil(log2(n)), e.g. n=12, l=4: 12 oc  8 ic  12 i
                                                  7, l=3: 10 oc  6 ic   9 i
                                                 20, l=5: 14 oc 10 ic  15 i
                                                100, l=7: 16 oc 14 ic  21 i
                  */
    if(k<at(0)->key()) return -1;
    if(k==at(0)->key()) return 0;
    int lasti=count()-1;
    if(k>at(lasti)->key()) return -1;
    int i=_n2;
    int step2=_n2 >> 1;
    while(step2>0) {
      if(i>lasti) {
        i-=step2;
      } else {
        const Key& ki=at(i)->key();
        if(k<ki) {
          i-=step2;
        } else if(k>ki) {
          i+=step2;
        } else {
          return i;
        }
      }
      step2=step2 >> 1;
    }
    if(k==at(i)->key()) {
      return i;
    } else {
      return -1;
    }
  }
}

template<class Key, class T>
int SortedVector<Key, T>::indexAfter(const Key& k) const
{
  if(isEmpty() || k<at(0)->key()) return 0;
  int lasti=count()-1;
  if(k>=at(lasti)->key()) return count();
  int i=_n2;
  int step2=_n2 >> 1;
  while(step2>0) {
    if(i>lasti) {
      i-=step2;
    } else if(k<=at(i)->key()) {
      if(k>at(i-1)->key()) break;
      i-=step2;
    } else {
      i+=step2;
    }
    step2=step2 >> 1;
  }
  return i;
}

template<class Key, class T>
void SortedVector<Key, T>::insert(T * o)
{
  int i=indexAfter(o->key());
  QVector<T *>::insert(i, o);
  while(_n2<count()) _n2=_n2 << 1;
}

template<class Key, class T>
void SortedVector<Key, T>::remove(int index)
{
  QVector<T *>::remove(index);
  int n2=_n2 >> 1;
  if(n2>0 && n2>=count()) {
    _n2=n2;
  }
}

template<class Key, class T>
void SortedVector<Key, T>::clear()
{
  QVector<T *>::clear();
}

} // namespace QGpCoreTools

#endif // SORTEDVECTOR_H