AVL Array

Header <avl_array.hpp>

The header file avl_array.hpp is the only one that the user needs to include. It contains the declaration of the class avl_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.

Macros

`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, non-trivial 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_tagwill 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_tagis used. See rationale.

Classes

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 and list interface methods (this excludes, for instance, reserve() and capacity()).

The STL-style container avl_array, defined here, is intended to fill the gap between vector and list. 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* and binary_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.

Non-Proportional Sequence View

Additionally, an experimental feature, called "Non-Proportional 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 from int must be defined for the specified type/class. The conversion from int 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 non-proportional 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, non-proportional 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) of avl_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 the npsv_ 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 with

N: number of elements in the container

M: number of elements in the other container

t: 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 interval

to: 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 operation

dst: an iterator (straight/reverse) referring the destination position of an operation

sfrom: src from

sto: src to

other: another avl_array container of the same type

x: another avl_array container of the same type

cmp: a binary predicate functor for comparisons returning a boolean meaning "lesser than"

Revised 22 November, 2006