QGpCoreTools::SortedVector< Key, T > Class Template Reference

A vector of sorted elements. More...

#include <SortedVector.h>

Inheritance diagram for QGpCoreTools::SortedVector< Key, T >:

List of all members.

Public Member Functions
void	append (T *o)
T *	at (int index) const
void	clear ()
bool	contains (const Key &k) const
int	count () const
int	indexOf (const Key &k) const
void	insert (T *o)
bool	isEmpty () const
void	remove (int index)
void	reserve (int n)
void	sort ()
	SortedVector ()
const QVector< T * > &	vector () const

---

Detailed Description

template<class Key, class T>
class QGpCoreTools::SortedVector< Key, T >

A vector of sorted elements.

Provides fast lookup (equivalent to QMap) on vector based storage. Probably less memory consumption than a QMap but slower insertions.

---

Constructor & Destructor Documentation

template<class Key, class T>

QGpCoreTools::SortedVector< Key, T >::SortedVector

(

)

[inline]

{_n2=1;}

---

Member Function Documentation

template<class Key, class T>

void QGpCoreTools::SortedVector< Key, T >::append

(

T *

o

)

[inline]

Adds object o to the end of the vector. The vector is not automatically sorted and search functions cannot be used before a proper initialization of all object keys and a call to sort(). This function may be of interest if keys are not available at the time of insertion.

{QVector<T *>::append(o);}

template<class Key, class T>

T* QGpCoreTools::SortedVector< Key, T >::at

(

int

index

)

const [inline]

Referenced by GeopsyCore::MetaDataMap::add(), GeopsyCore::SharedMetaData::add(), GeopsyCore::Signal::xml_writeChildren(), GeopsyCore::SignalDB::xml_writeProperties(), and GeopsyCore::Signal::xml_writeProperties().

{return QVector<T *>::at(index);}

template<class Key , class T >

void QGpCoreTools::SortedVector< Key, T >::clear

(

)

Reimplemented in GeopsyCore::MetaDataMap.

{
  QVector<T *>::clear();
}

template<class Key, class T>

bool QGpCoreTools::SortedVector< Key, T >::contains

(

const Key &

k

)

const [inline]

{return indexOf(k)>-1;}

template<class Key, class T>

int QGpCoreTools::SortedVector< Key, T >::count

(

)

const [inline]

Reimplemented in GeopsyCore::MetaDataMap.

Referenced by GeopsyCore::SharedMetaData::add().

{return QVector<T *>::count();}

template<class Key, class T >

int QGpCoreTools::SortedVector< Key, T >::indexOf

(

const Key &

k

)

const

Returns the index of o or -1 if o does not exist

{
  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>

void QGpCoreTools::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>

bool QGpCoreTools::SortedVector< Key, T >::isEmpty

(

)

const [inline]

{return QVector<T *>::isEmpty();}

template<class Key , class T >

void QGpCoreTools::SortedVector< Key, T >::remove

(

int

index

)

Reimplemented in GeopsyCore::MetaDataMap.

{
  QVector<T *>::remove(index);
  int n2=_n2 >> 1;
  if(n2>0 && n2>=count()) {
    _n2=n2;
  }
}

template<class Key, class T>

void QGpCoreTools::SortedVector< Key, T >::reserve

(

int

n

)

[inline]

Reimplemented in GeopsyCore::MetaDataMap.

{QVector<T *>::reserve(n);}

template<class Key, class T>

void QGpCoreTools::SortedVector< Key, T >::sort

(

)

[inline]

Sort the obects. This function is required only when object are added using append(). On the contrary, insert() keeps the vector properly sorted.

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

template<class Key, class T>

const QVector<T *>& QGpCoreTools::SortedVector< Key, T >::vector

(

)

const [inline]

Reimplemented in GeopsyCore::MetaDataMap.

{return *this;}

---

The documentation for this class was generated from the following files:

• QGpCoreTools/SortedVector.h
• QGpCoreTools/SortedVector.cpp