TLSortedArray< T, _OP > Class Template Reference

Standard sorted array template. More...

#include <tlsortedarray.h>

Inheritance diagram for TLSortedArray< T, _OP >:

[legend]Collaboration diagram for TLSortedArray< T, _OP >:

[legend]List of all members.

Public Member Functions
	TLSortedArray (const _OP &op=_OP())
	Create empty heap.
	~TLSortedArray ()
	Destroy heap clearing it.
T *	last ()
	Clear the whole array.
const T *	last () const
template<typename K> ssize_t	GetInsertIdx (const K &ent, int allow_dup)
	Get interstion index.
int	insert (const T &ent, int allow_dup, ssize_t *ret_idx=NULL)
	Add element to the array.
ssize_t	ReOrder (size_t idx, int allow_dup)
	Bring element at correct position in array.
void	ReOrder ()
	Sort the array.
template<typename K> ssize_t	search (const K &key)
	Search an element in the array.
template<typename K> ssize_t	remove (const K &key)
	Remove element from array. Remove passed element.
size_t	CheckOrder ()
	Debugging: check ordering condition for all entries.
Private Member Functions
	TLSortedArray (const TLSortedArray &)
	Do not use these:.
void	operator= (const TLSortedArray &)

---

Detailed Description

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
class TLSortedArray< T, _OP >

Standard sorted array template.

Author:

Wolfgang Wieser ] wwieser (a) gmx <*> de [

Implements standard sorted array template.

Sorted arrays allow to insert() and remove() in O(n), and search operations in O(log(n)) (binary search). Of course, the smallest and largest elements are accessible O(1). Removing the largest is O(1) as well.

WHAT TO USE FOR <T>: (Standard text from tlbtree.h:) This class is probably most useful for T being a simple type (integer, unique pointers to a class or small data-only structures). You may use any POD type or any struct/class which is a "plain data type" (PDT; see defop.h) and even for "complex data types" as long as you can provide the required operator plugin OP and it has a working default constructor and a working copy constructor (both for temporaries).

Thread safety: The complete array must be protected by a mutex for all "write" operations.

This class is NOT "C++-safe", i.e. do not use the assignment operator or the copy constructor (these are private).

Definition at line 60 of file tlsortedarray.h.

---

Constructor & Destructor Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> TLSortedArray< T, _OP >::TLSortedArray (  const TLSortedArray< T, _OP > &   )  [private]

Do not use these:.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> TLSortedArray< T, _OP >::TLSortedArray (  const _OP &  op = _OP()  )  [inline]

Create empty heap. Definition at line 78 of file tlsortedarray.h.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> TLSortedArray< T, _OP >::~TLSortedArray (   )  [inline]

Destroy heap clearing it. Definition at line 80 of file tlsortedarray.h.

---

Member Function Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> size_t TLSortedArray< T, _OP >::CheckOrder (   )  [inline]

Debugging: check ordering condition for all entries. Returns: number of errors Definition at line 264 of file tlsortedarray.h. References TLArray< T, _OP >::array().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> template<typename K> ssize_t TLSortedArray< T, _OP >::GetInsertIdx (  const K &  ent, int  allow_dup )  [inline]

Get interstion index. This returns the index where to add the passed element. Returned index is -1 if you shall not add the passed elem (allow_dup==0). Index i means that you should add ent at array[i] thus moving array[i] to array[i+1] etc. before doing so. For the allow_dup parameter, see insert(). Runtime is O(log(n)). Definition at line 112 of file tlsortedarray.h. References TLArray< T, _OP >::array(), and ssize_t. Referenced by TLSortedArray< T, _OP >::insert(), and TLSortedArray< T, _OP >::ReOrder().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> int TLSortedArray< T, _OP >::insert (  const T &  ent, int  allow_dup, ssize_t *  ret_idx = NULL )  [inline]

Add element to the array. If allow_dup is set, add element even if it is already in the array. If allow_dup is <0, add as the first elem of the equal ones, if >0 as the last. E.g. for a case insensitive match, adding "b" to "AAABBBCC" will yield: allow_dup=-1 -> "AAAbBBBCC" return 0 allow_dup=0 -> "AAABBBCC" return 1 allow_dup=+1 -> "AAABBBbCC" return 0 Runtime is O(log(n)) for the search and O(n) for the move. Returns: 0 -> ok, added, index stores in *ret_idx if non-NULL. 1 -> already in list and allow_dup not set Definition at line 147 of file tlsortedarray.h. References TLSortedArray< T, _OP >::GetInsertIdx(), TLArray< T, _OP >::insert(), and ssize_t.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> const T* TLSortedArray< T, _OP >::last (   )  const [inline]

Definition at line 96 of file tlsortedarray.h. References TLArray< T, _OP >::arrayP().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> T* TLSortedArray< T, _OP >::last (   )  [inline]

Clear the whole array. Get last (=largest) element in the array (or NULL): Runtime is O(1). Definition at line 95 of file tlsortedarray.h. References TLArray< T, _OP >::arrayP().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLSortedArray< T, _OP >::operator= (  const TLSortedArray< T, _OP > &   )  [private]

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> template<typename K> ssize_t TLSortedArray< T, _OP >::remove (  const K &  key  )  [inline]

Remove element from array. Remove passed element. Runtime is O(log(n)) for the search and O(n) for the move. In case several elements matching key exist, all of them are removed. Returns number of removed elements. Definition at line 240 of file tlsortedarray.h. References TLArray< T, _OP >::_downsize(), TLArray< T, _OP >::array(), TLArray< T, _OP >::arrayP(), and ssize_t.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> void TLSortedArray< T, _OP >::ReOrder (   )  [inline]

Sort the array. Reorder complete list; may be used if several elements were modified. This uses "insertion sort" to sort the list; hence runtime is O(m*n) with m being the number of elements which are not in the correct position. Hence, it is nearly O(n) as long as m << n. In the worst case (list not ordered), runtime is O(n^2). Todo: Could use binary search for insert position but ONLY for elems which are out of order! (Otherwise no longer O(m*n)). Definition at line 197 of file tlsortedarray.h. References TLArray< T, _OP >::array().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> ssize_t TLSortedArray< T, _OP >::ReOrder (  size_t  idx, int  allow_dup )  [inline]

Bring element at correct position in array. In case the array element with index idx was modified, call this function to have it put into the correct position in the array so that the array stays sorted. For the allow_dup parameter, see insert(). Runtime is O(log(n)) for the search and O(n) for the move. Returns: >=0 -> new index of the element -2 -> idx is out of range -3 -> removed because elem would be duplicate and allow_dup=0 Definition at line 171 of file tlsortedarray.h. References TLArray< T, _OP >::array(), TLSortedArray< T, _OP >::GetInsertIdx(), and ssize_t.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>> template<typename K> ssize_t TLSortedArray< T, _OP >::search (  const K &  key  )  [inline]

Search an element in the array. This uses binary search and is hence O(log(n)). Returns: Index of first occurence element or -1 if not found. Definition at line 224 of file tlsortedarray.h. References ssize_t, and TLBinarySearch().

---

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

• /ray/src/lib/tl/tlsortedarray.h

---