AVL Array 
Get the latest

 Introduction
 Macros
AA_DEREF_NULL_ON_ASSERTION_FAILURE
AA_NO_SLOW_ASSERTS
AA_ASSERT_BEFORE_THROW
AA_USE_RANDOM_ACCESS_TAG
 Classes
 Class
avl_array
 NonProportional Sequence View
 Class
avl_array
synopsis
The header file
avl_array.hpp
is the only one that the user needs to include. It contains the declaration of the classavl_array
(which is the only one the user needs to know), and it includes all other necessary headers. Together with each include directive, a short comment explains the contents of the corresponding header.
AA_DEREF_NULL_ON_ASSERTION_FAILURE
If this macro is defined, any assertion failure will provoke a program crash by dereferencing NULL and trying to increase an integer at that address. This can be useful for debugging on some environments.
AA_NO_SLOW_ASSERTS
If this macro is defined, nontrivial assertions that take O(log N) time will be turned off.
AA_ASSERT_BEFORE_THROW
If this macro is defined, an assertion failure will precede every exception throw. This can be useful for debugging on some environments.
AA_USE_RANDOM_ACCESS_TAG
If this macro is defined,
random_access_iterator_tag
will be used for iterators instead ofbidirectional_iterator_tag
. This can be useful for checking random access concepts, but note that it will turn suboptimal the algorithms that assume O(1) random access whererandom_access_iterator_tag
is used. See rationale.
Class
avl_array
This class is the only one the user needs to know about in the library. It provides the counterparts of most
vector
andlist
interface methods (this excludes, for instance,reserve()
andcapacity()
).The STLstyle container
avl_array
, defined here, is intended to fill the gap betweenvector
andlist
. It provides a reasonably fast random access (logarithmic time) and a reasonably fast insert/erase (also logarithmic time).Additionally, it can be traversed as fast as a list (constant time per advance), and it provides algorithms like
swap
,reverse
,sort
,stable sort
,merge
*,unique
* andbinary_search
* (*: data must be previously in order).Last, but not least, all iterators defined here (yes: reverse iterators too) remain valid, following the referenced element, until it is erased. This holds true even when the referenced element is moved along the container or when it is moved from one container to another container.
NonProportional Sequence View
Additionally, an experimental feature, called "NonProportional Sequence View" (NPSV) is provided. It can be used by specifying a numeric type in the third operand of the template
avl_array<T,A,W>
. Operators=
,+
,
,+=
,=
,==
,!=
,>
,<
,<=
,>=
and a conversion fromint
must be defined for the specified type/class. The conversion fromint
will be used for values 0 and 1.The NPSV isn't at all related to the width of the tree as a data structure. It is a feature that supports random access (also with O(log n) time complexity) with index values different from the usual correlative natural numbers.
The point here is that these index values don't need to be proportional to their ordinal positions in the sequence. For every node in the sequence, its nonproportional position is defined as the sum of the 'widths' of all previous elements in the sequence. The 'width' of an element is a new field. It is 1 by default, leading to a classic index 0,1,2... Changing the 'width' of an element (which takes O(log n) time) automatically alters the position of all elements placed after it in the sequence.
The position of an element in this alternative view of the sequence can be retrieved in O(log n) time. The element of a given position in the alternative view of the sequence can be reached in O(log n) time.
The order in the alternative, nonproportional view of the sequence is, of course, the same as in the normal sequence. The only difference is that, in the alternative view of the sequence, the index of elements doesn't need to be proportional to their ordinal position.
When the width parameter (
W
) ofavl_array<T,A,W>
is not specified, an empty class is used by default, being all widths equivalent to 0.Iterators and operator
[]
remain unchanged (working with the traditional sequence of natural numbers). The only way to use this new feature is by calling thenpsv_
methods.See examples for more information.
Class
avl_array
synopsis
namespace mkr { class avl_array // (see legend) { public: // Constructors: avl_array (); // O(1) default avl_array (other); // O(N) copy avl_array (n, t); // O(N) n elements like t avl_array (n); // O(N) n default constructed elements avl_array (from, to); // O(N) copy interval [from,to) avl_array (from, n); // O(N) copy n starting at from ~avl_array (); // Destructor operator= (other); // O(M+N) whole container assignment swap (other); // O(1) whole container swap size_t size (); // O(1) get current size bool empty (); // O(1) true means size==0 size_t max_size (); // O(1) get estimated max size resize (n); // * change size resize (n, t); // * change size (append copies of t) // (*): O(min{N, n log N}) iterator begin (); // O(1) beginning (first) iterator end (); // O(1) end (after last) reverse_iterator rbegin (); // O(1) reverse beg. (last) reverse_iterator rend (); // O(1) reverse end (before first) bool operator== (other); // * (size==) && (all==) bool operator!= (other); // * not(==) bool operator< (other); // * (first!= is <)  (all== but size<) bool operator> (other); // * (first!= is >)  (all== but size>) bool operator<= (other); // * not(>) bool operator>= (other); // * not(<) // (*) O(min{M,N}) reference operator[] (size_t n); // O(log N) get n'th element reference operator() (size_t n); // O(log N) get n'th element reference at (size_t n); // O(log N) get n'th element // Insert... it insert (t); // O(log N) t anywhere (no rotations) it insert (it, t); // O(log N) t before *it insert (it, n, t); // * n copies of t before *it insert (it, from, to); // * [from,to) before *it // (*): O(min{N, n log N}) // Erase... it erase (it); // O(log N) *it it erase (it, n); // * [it, it+n) it erase (from, to); // * [from, to) clear (); // O(N) all // (*): O(min{N, n log N}) reference front (); // O(1) get first push_front (t); // O(log N) insert t before first pop_front (); // O(log N) erase first reference back (); // O(1) get last push_back (t); // O(log N) append t after last pop_back (); // O(log N) erase last swap (it1, it2); // O(1)* interchange *it1 with *it2 move (it, n); // O(log N) shift *it by n positions move (src, dst); // ** put *src before *dst move (sfrom, n, dst); // *** put [sfrom,sfrom+n) before dst move (sfrom, sto, dst); // *** put [sfrom,sto) before dst reverse (); // O(N) invert the sequence // (*): O(log N) with NPSV // (**): O(log M + log N) // (***): O(min{N, n log N} + min{M, n log M}) splice (dst, x); // move (x.begin(), x.end(), dst) splice (dst, x, src); // move (src, dst) splice (dst, x, sfrom, sto); // move (sfrom, sto, dst) // Look for t using cmp, bool binary_search (t, it, cmp); // it=position, true==found // defaults: [] [<] // O(log N) iterator insert_sorted (t, allow_duplicates, cmp); // O(log N) // defaults: [true] [<] sort (cmp); // O(N log N) impose order using cmp (or <) // [<] // same as sort(), but stable_sort (cmp); // O(N log N) respect current order // default: [<] // between equals merge (other, cmp); // O(M+N) mix with other (leave it empty) // default: [<] unique (cmp); // O(N) erase duplicates // [<] npsv_update_sums (); // O(1)/O(N)* update width sums W npsv_width (); // O(1)/O(N)* get total width W npsv_width (it); // O(1) get element's width npsv_set_width (it, w, update_sums); // set element's width // [true] // O(log N)/O(1)** W npsv_pos_of (it); // O(log N)/O(N)* get element's position iterator npsv_at_pos (pos, cmp); // get element from position // [<] // O(log N)/O(N)* // (*) width sums need to be updated // (**) don't update width sums (lazy mode) }; };Parameters and time complexity specifications legend:
n:
number of elements to operate withN:
number of elements in the containerM:
number of elements in the other containert:
a value of the payload type (value_type
)it:
an iterator (straight/reverse)it1:
an iterator (straight/reverse)it2:
an iterator (straight/reverse)from:
an iterator (straight/reverse) referring the beginning of a range or intervalto:
an iterator (straight/reverse) referring the end of a range or interval (*to
excluded)src:
an iterator (straight/reverse) referring the source element(s) of an operationdst:
an iterator (straight/reverse) referring the destination position of an operationsfrom: src from
sto: src to
other:
anotheravl_array
container of the same typex:
anotheravl_array
container of the same typecmp:
a binary predicate functor for comparisons returning a boolean meaning "lesser than"
Revised 19 May, 2010
Copyright © Universidad de Alcalá 2006. See accompanying license.