UTLists.h

Go to the documentation of this file.

//==================================================================================================
// Copyright (C) 2010  Brian Tietz    sdbtietz at yahoo dot com
//
// This program is free software; you can redistribute it and/or modify it under the terms of the
// GNU General Public License as published by the Free Software Foundation, version 2.0 of the
// License.
//
// This program 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
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License along with this program; if
// not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
// 02110-1301, USA.
//
// For commercial software, the copyright holder (Brian Tietz, email sdbtietz at yahoo dot com)
// reserves the right and is willing to waive the proprietary source code disclosure aspects of that
// license as applied to the UT library in exchange for either substantial contributions to the
// development of the UT library or other forms of compensation.  Any such waiver must be
// established in writing between the copyright holder and the commercial entity obtaining such a
// waiver.
//==================================================================================================


#ifndef _UT_LISTS_H_
#define _UT_LISTS_H_


//==================================================================================================
//=== Project headers
//==================================================================================================
#include "UT.h"


//==================================================================================================
template <class T>
class Array_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
                Array_t();

                Array_t( T* stack_buffer, int stack_buffer_num_items_allcoated );

                ~Array_t();

    void        InstallStackBuffer( T* stack_buffer, int stack_buffer_num_items_allcoated );

    T           AddHead(const T& item);

    T           AddTail(const T& item);

    T           AddItemAt( const T& item, int index );

    T           RemoveHead();

    T           RemoveTail();

    T           RemoveItemAt(int index);

    inline int  CountItems() const;

    inline int  AllocatedItems() const;

    inline void SetNumValidItems(int count);

    void        GrowIfNeeded( int min_allocated_items, bool expect_more_growth = false );

    inline T    Head() const;

    inline T    Tail() const;

    inline T    ItemAt(int index) const;

    inline T&   operator [](int index) const;

    inline void operator +=(const T& item);

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    T*          m_items;
    int         m_num_items;
    int         m_items_allocated;
    bool        m_items_allocated_on_stack;
    int         m_head_index;
};


//==================================================================================================
template <class T>
class List_t
//==================================================================================================
: public Array_t<T*>
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline      List_t();

    inline      List_t( T** stack_buffer, int stack_buffer_num_items_allcoated );

    T*          RemoveItem(T* item);

    int         IndexOfItem(T* item);

    inline T&   operator [](int index) const;

    inline void operator -=(T* item);
};


//==================================================================================================
template <class T>
class OwnedList_t
//==================================================================================================
: public List_t<T>
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline  OwnedList_t();

    inline  OwnedList_t( T** stack_buffer, int stack_buffer_num_items_allcoated );

            ~OwnedList_t();
};


//==================================================================================================
template <class T>
class LinkedList_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline          LinkedList_t();

    T*              AddHead(T* item);

    T*              AddTail(T* item);

    T*              AddItemBefore( T* new_item, T* after_item );

    T*              AddItemAfter( T* before_item, T* new_item );

    T*              RemoveHead();

    T*              RemoveTail();

    T*              RemoveItem(T* item);

    inline int      CountItems() const;

    inline T*       Head() const;

    inline T*       Tail() const;

    inline void     operator +=(T* item);

    inline void     operator -=(T* item);

    void            SortSmallOrSlow();

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    T*              m_head;
    T*              m_tail;
    int             m_num_items;
};


//==================================================================================================
template <class T>
class LinkedListNode_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    protected:
    //----------------------------------------------------------------------------------------------
    inline                  LinkedListNode_t();

    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline T*               Next() const;

    inline T*               Prev() const;

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    LinkedListNode_t<T>*    m_next;
    LinkedListNode_t<T>*    m_prev;

    friend class LinkedList_t<T>;
};


//==================================================================================================
template <class T>
class OwnedLinkedList_t
//==================================================================================================
: public LinkedList_t<T>
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
        ~OwnedLinkedList_t();
};


//==================================================================================================
template <class T, class K>
class BTree_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline      BTree_t();

    T*          FindItem(K key) const;

    T*          FindItemAtOrBefore(K key) const;

    T*          FindItemAtOrAfter(K key) const;

    T*          IsInTree(T* item) const;

    void        AddItem( T* new_item, bool balance_tree = true );

    T*          RemoveHead(bool balance_tree = true);

    T*          RemoveTail(bool balance_tree = true);

    T*          RemoveItem( T* item, bool balance_tree = true );

    inline int  CountItems() const;

    T*          Head() const;

    T*          Tail() const;

    inline T*   Root() const;

    inline void operator +=(T* new_item);

    inline void operator -=(T* item);

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    void        UpdateChildNodeCountsAndBalanceToRoot( T* node, bool balance_tree );
                    // Balances the tree from node back up to the root node, updating the child node
                    // counts all the way back up.

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    T*          m_root;
    int         m_num_items;
};


//==================================================================================================
template <class T, class K>
class BTreeNode_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    protected:
    //----------------------------------------------------------------------------------------------
    inline              BTreeNode_t();

    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    T*                  Next() const;

    T*                  Prev() const;

    inline bool         operator < (const T& other);

    inline bool         operator <= (const T& other);

    inline bool         operator > (const T& other);

    inline bool         operator >= (const T& other);

    inline bool         operator == (const T& other);

    inline bool         operator < (K key);

    inline bool         operator <= (K key);

    inline bool         operator > (K key);

    inline bool         operator >= (K key);

    inline bool         operator == (K key);

    inline int          ChildNodesDepth() const;

    void                ValidateChildNodeDepth() const;

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    BTreeNode_t<T,K>*   m_prev;                 // Down the tree and to a lower position
    BTreeNode_t<T,K>*   m_parent;               // Up the tree
    BTreeNode_t<T,K>*   m_next;                 // Down the tree and to a higher position
    int                 m_child_nodes_depth;

    friend class BTree_t<T,K>;
};


//==================================================================================================
template <class T, class K>
class OwnedBTree_t
//==================================================================================================
: public BTree_t<T,K>
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
        ~OwnedBTree_t();
};


//==================================================================================================
template <class T, class K>
class SortedList_t
//==================================================================================================
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
                SortedList_t();

                SortedList_t( T** stack_buffer, int stack_buffer_num_items_allcoated );

                ~SortedList_t();

    T*          FindItem( K key, out int* index = NULL ) const;

    T*          FindItemAtOrBefore( K key, out int* index = NULL ) const;

    T*          FindItemAtOrAfter( K key, out int* index = NULL ) const;

    T*          IsInList(T* item) const;

    void        AddItem(T* new_item);

    void        AddHead(T* item);

    void        AddTail( T* item, bool will_sort_later = false );

    void        Sort();

    T*          RemoveItem(T* item);

    T*          RemoveHead();

    inline T*   RemoveTail();

    T*          RemoveItemAt(int index);

    int         IndexOfItem(T* item);

    inline int  CountItems() const;

    inline T*   Head() const;

    inline T*   Tail() const;

    inline T*   ItemAt(int index) const;

    inline T&   operator [](int index) const;

    inline void operator +=(T* new_item);

    inline void operator -=(T* item);

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    int         FindItemIndex( K key, bool at_or_before, bool at_or_after ) const;
    int         FindItemIndex( T* item, bool adding ) const;
    static bool MergeSort( T** from, T** to, int num_items );
                    // Returns true if the sorted items actually end up in the to buffer.

    //----------------------------------------------------------------------------------------------
    private:
    //----------------------------------------------------------------------------------------------
    T**         m_items;
    int         m_num_items;
    int         m_items_allocated;
    bool        m_items_allocated_on_stack;
};


//==================================================================================================
template <class T, class K>
class OwnedSortedList_t
//==================================================================================================
: public SortedList_t<T,K>
{
    //----------------------------------------------------------------------------------------------
    public:
    //----------------------------------------------------------------------------------------------
    inline  OwnedSortedList_t();

    inline  OwnedSortedList_t( T** stack_buffer, int stack_buffer_num_items_allcoated );

            ~OwnedSortedList_t();
};




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class Array_t
//===
//==================================================================================================
//==================================================================================================
template <class T>
Array_t<T>::Array_t()
{
    m_items = NULL;
    m_num_items = 0;
    m_items_allocated = 0;
    m_items_allocated_on_stack = false;
    m_head_index = 0;
}


template <class T>
Array_t<T>::Array_t( T* stack_buffer, int stack_buffer_num_items_allcoated )
{
    m_items = stack_buffer;
    m_num_items = 0;
    m_items_allocated = stack_buffer_num_items_allcoated;
    m_items_allocated_on_stack = true;
    m_head_index = 0;
}


template <class T>
Array_t<T>::~Array_t()
{
    if(m_items && !m_items_allocated_on_stack)
        delete[] m_items;
}


template <class T>
void    
Array_t<T>::InstallStackBuffer( T* stack_buffer, int stack_buffer_num_items_allcoated )
{
    assert(m_items == NULL);
    m_items = stack_buffer;
    m_items_allocated = stack_buffer_num_items_allcoated;
    m_items_allocated_on_stack = true;
}


template <class T>
T
Array_t<T>::AddHead(const T& item)
{
    assert(m_head_index < m_items_allocated || !m_items_allocated);
    assert(m_items_allocated >= m_num_items);

    if(m_num_items == m_items_allocated)
    {
        // Need to make room for the item: figure out how big to make the new list
        int new_items_allocated = m_items_allocated;
        if(new_items_allocated == 0)
            new_items_allocated = 16;
        else if(new_items_allocated < 128)
            new_items_allocated *= 2;
        else
            new_items_allocated += new_items_allocated / 2;

        // Allocate the new list
        T* new_list = new T[new_items_allocated];

        // Insert the new item as the head
        new_list[0] = item;

        // Copy the existing items
        int copy_items_from_head_index = m_num_items;
        if(copy_items_from_head_index > m_items_allocated - m_head_index)
            copy_items_from_head_index = m_items_allocated - m_head_index;
        memcpy( new_list+1, m_items+m_head_index, copy_items_from_head_index * sizeof(T) );
        memcpy( new_list+1+copy_items_from_head_index,
                m_items,
                (m_num_items - copy_items_from_head_index) * sizeof(T) );

        // Increment the item count
        m_num_items++;

        // Install the new list
        if(m_items && !m_items_allocated_on_stack)
            delete[] m_items;
        m_items = new_list;
        m_items_allocated = new_items_allocated;
        m_items_allocated_on_stack = false;
        m_head_index = 0;
        return item;
    }

    m_head_index--;
    if(m_head_index <= -1)
    {
        assert(m_head_index == -1);
        m_head_index = m_items_allocated-1;
    }
    m_items[m_head_index] = item;
    m_num_items++;
    return item;
}


template <class T>
T
Array_t<T>::AddTail(const T& item)
{
    assert(m_head_index < m_items_allocated || !m_items_allocated);
    assert(m_items_allocated >= m_num_items);

    if(m_num_items == m_items_allocated)
    {
        // Need to make room for the item: figure out how big to make the new list
        int new_items_allocated = m_items_allocated;
        if(new_items_allocated == 0)
            new_items_allocated = 16;
        else if(new_items_allocated < 128)
            new_items_allocated *= 2;
        else
            new_items_allocated += new_items_allocated / 2;

        // Allocate the new list
        T* new_list = new T[new_items_allocated];

        // Copy the existing items
        int copy_items_from_head_index = m_num_items;
        if(copy_items_from_head_index > m_items_allocated - m_head_index)
            copy_items_from_head_index = m_items_allocated - m_head_index;
        memcpy( new_list, m_items+m_head_index, copy_items_from_head_index * sizeof(T) );
        memcpy( new_list+copy_items_from_head_index,
                m_items,
                (m_num_items - copy_items_from_head_index) * sizeof(T) );

        // Add the new item as the tail
        new_list[m_num_items] = item;

        // Increment the item count
        m_num_items++;

        // Install the new list
        if(m_items && !m_items_allocated_on_stack)
            delete[] m_items;
        m_items = new_list;
        m_items_allocated = new_items_allocated;
        m_items_allocated_on_stack = false;
        m_head_index = 0;
        return item;
    }

    int add_index;
    #if TARGET_CPU_FAST_INTEGER_MOD
        add_index = (m_head_index + m_num_items) % m_items_allocated;
    #else
        add_index = m_head_index + m_num_items;
        if(add_index >= m_items_allocated)
            add_index -= m_items_allocated;
    #endif

    m_items[add_index] = item;
    m_num_items++;
    return item;
}


template <class T>
T
Array_t<T>::AddItemAt( const T& item, int index )
{
    int head_segment_count;
    int tail_segment_count;

    if(index == -1)
        index = m_num_items;
    assert(m_head_index < m_items_allocated || !m_items_allocated);
    assert(m_items_allocated >= m_num_items);
    assert(index >= 0 && index <= m_num_items);

    if(m_num_items == m_items_allocated)
    {
        // Need to make room for the item: figure out how big to make the new list
        int new_items_allocated = m_items_allocated;
        if(new_items_allocated == 0)
            new_items_allocated = 16;
        else if(new_items_allocated < 128)
            new_items_allocated *= 2;
        else
            new_items_allocated += new_items_allocated / 2;

        // Allocate the new list
        T* new_list = new T[new_items_allocated];

        // Assemble the new list
        head_segment_count = m_items_allocated - m_head_index;
        tail_segment_count = m_num_items - head_segment_count;
        if(index <= head_segment_count)
        {
            // Item insertion will occur in the segment starting with the head index and extending
            // to the end of the allocated item list
            memcpy( new_list, m_items+m_head_index, index * sizeof(T) );
            new_list[index] = item;
            memcpy( new_list+index+1,
                    m_items+m_head_index+index,
                    (head_segment_count-index) * sizeof(T) );
            memcpy( new_list+head_segment_count+1, m_items, tail_segment_count * sizeof(T) );
        }
        else
        {
            // Item insertion will occur in the segment starting with the beginning of the allocated
            // item list and extending to the tail item
            memcpy( new_list, m_items+m_head_index, head_segment_count * sizeof(T) );
            memcpy( new_list+head_segment_count, m_items, (index-head_segment_count) * sizeof(T) );
            new_list[index] = item;
            memcpy( new_list+index+1,
                    m_items+index-head_segment_count,
                    (m_num_items-index) * sizeof(T) );
        }

        // Increment the item count
        m_num_items++;

        // Install the new list
        if(m_items && !m_items_allocated_on_stack)
            delete[] m_items;
        m_items = new_list;
        m_items_allocated = new_items_allocated;
        m_items_allocated_on_stack = false;
        m_head_index = 0;
        return item;
    }

    if(index == 0)
        return AddHead(item);
    if(index == m_num_items)
        return AddTail(item);

    int array_index;

    // Shifting the head, the number of items to be moved is index
    // Shifting the tail, the number of items to be moved is m_num_items - index
    if(index < m_num_items - index)
    {
        // It is more efficient to shift the head back one to make room

        // Possible scenarios:
        // H****I******T-------
        // -H****I******T------
        // ----H****I******T---
        // ------H****I******T-
        // -------H****I******T
        // T-------H****I******
        // *T-------H****I*****
        // **T-------H****I****
        // *****T-------H****I*
        // ******T-------H****I
        // I******T-------H****
        // *I******T-------H***
        // ***I******T-------H*
        // ****I******T-------H

        #if TARGET_CPU_FAST_INTEGER_MOD
            array_index = (m_head_index + index - 1) % m_items_allocated;
        #else
            array_index = m_head_index + index - 1;
            if(array_index >= m_items_allocated)
                array_index -= m_items_allocated;
        #endif

        if(m_head_index == 0)
        {
            // 00000000001111111111
            // 01234567890123456789
            // H****I******T-------
            // H1234z******T------- m_head_index = 0, index = 5, array_index = 4
            // 1234Iz******T------H
            m_head_index = m_items_allocated-1;
            m_items[m_head_index] = m_items[0];
            memmove( m_items, m_items+1, array_index * sizeof(T) );
            m_items[array_index] = item;
            m_num_items++;
            return item;
        }

        else if(m_head_index <= array_index)
        {
            // 00000000001111111111
            // 01234567890123456789
            // -H****I******T------
            // -H1234z******T------ m_head_index = 1, index = 5, array_index = 5
            // H1234Iz******T------

            // ----H****I******T---
            // ----H1234z******T--- m_head_index = 4, index = 5, array_index = 8
            // ---H1234Iz******T---

            // ------H****I******T-
            // ------H1234z******T- m_head_index = 6, index = 5, array_index = 10
            // -----H1234Iz******T-

            // -------H****I******T
            // -------H1234z******T m_head_index = 7, index = 5, array_index = 11
            // ------H1234Iz******T

            // T-------H****I******
            // T-------H1234z****** m_head_index = 8, index = 5, array_index = 12
            // T------H1234iz******

            // *T-------H****I*****
            // *T-------H1234z***** m_head_index = 9, index = 5, array_index = 13
            // *T------H1234iz*****

            // **T-------H****I****
            // **T-------H1234z**** m_head_index = 10, index = 5, array_index = 14
            // **T------H1234Iz****

            // *****T-------H****I*
            // *****T-------H1234z* m_head_index = 13, index = 5, array_index = 17
            // *****T------H1234Iz*

            // ******T-------H****I
            // ******T-------H1234z m_head_index = 14, index = 5, array_index = 18
            // ******T------H1234Iz

            // I******T-------H****
            // z******T-------H1234 m_head_index = 15, index = 5, array_index = 19
            // z******T------H1234I
            memmove( m_items+m_head_index-1, m_items+m_head_index, index * sizeof(T) );
            m_head_index--;
            m_items[array_index] = item;
            m_num_items++;
            return item;
        }

        else
        {
            // 00000000001111111111
            // 01234567890123456789
            // *I******T-------H***
            // 4z******T-------H123 m_head_index = 16, index = 5, array_index = 0
            // Iz******T------H1234

            // ***I******T-------H*
            // 234z******T-------H1 m_head_index = 18, index = 5, array_index = 2
            // 34Iz******T------H12

            // ****I******T-------H
            // 1234z******T-------H m_head_index = 19, index = 5, array_index = 3
            // 234Iz******T------H1
            memmove(    m_items+m_head_index-1,
                        m_items+m_head_index,
                        (m_items_allocated-m_head_index) * sizeof(T) );
            m_head_index--;
            m_items[m_items_allocated-1] = m_items[0];
            memmove(    m_items,
                        m_items+1,
                        array_index * sizeof(T) );
            m_items[array_index] = item;
            m_num_items++;
            return item;
        }
    }
    else
    {
        // It is more efficient to shift the tail forward one to make room

        // Possible scenarios:
        // H******I****T-------
        // -H******I****T------
        // ----H******I****T---
        // ------H******I****T-
        // -------H******I****T
        // T-------H******I****
        // *T-------H******I***
        // **T-------H******I**
        // ***T-------H******I*
        // ****T-------H******I
        // I****T-------H******
        // *I****T-------H*****
        // *****I****T-------H*
        // ******I****T-------H

        #if TARGET_CPU_FAST_INTEGER_MOD
            array_index = (m_head_index + index) % m_items_allocated;
        #else
            array_index = m_head_index + index;
            if(array_index >= m_items_allocated)
                array_index -= m_items_allocated;
        #endif

        if(m_head_index + m_num_items < m_items_allocated)
        {
            // 00000000001111111111
            // 01234567890123456789
            // H******I****T-------
            // H123456z****T------- m_head_index = 0, index = 7, array_index = 7
            // H123456Iz****T------

            // -H******I****T------
            // -H123456z****T------ m_head_index = 1, index = 7, array_index = 8
            // -H123456Iz****T-----

            // ----H******I****T---
            // ----H123456z****T--- m_head_index = 4, index = 7, array_index = 11
            // ----H123456Iz****T--

            // ------H******I****T-
            // ------H123456z****T- m_head_index = 6, index = 7, array_index = 13
            // ------H123456Iz****T
            memmove(    m_items+array_index+1,
                        m_items+array_index,
                        (m_num_items-index) * sizeof(T) );
            m_items[array_index] = item;
            m_num_items++;
            return item;
        }

        else if(array_index > m_head_index)
        {
            // 00000000001111111111
            // 01234567890123456789
            // -------H******I****T
            // -------H123456z****T m_head_index = 7, index = 7, array_index = 14
            // T------H123456Iz****

            // T-------H******I****
            // T-------H123456z**** m_head_index = 8, index = 7, array_index = 15
            // *T------H123456Iz***

            // *T-------H******I***
            // *T-------H123456z*** m_head_index = 9, index = 7, array_index = 16
            // **T------H123456Iz**

            // **T-------H******I**
            // **T-------H123456z** m_head_index = 10, index = 7, array_index = 17
            // ***T------H123456Iz*

            // ***T-------H******I*
            // ***T-------H123456z* m_head_index = 11, index = 7, array_index = 18
            // ****T------H123456Iz

            // ****T-------H******I
            // ****T-------H123456z m_head_index = 12, index = 7, array_index = 19
            // z****T------H123456I
            memmove(    m_items+1,
                        m_items,
                        (m_head_index + m_num_items - m_items_allocated) * sizeof(T) );
            m_items[0] = m_items[m_items_allocated-1];
            memmove(    m_items+array_index+1,
                        m_items+array_index,
                        ( m_items_allocated - (array_index+1) ) * sizeof(T) );
            m_items[array_index] = item;
            m_num_items++;
            return item;
        }

        else
        {
            // 00000000001111111111
            // 01234567890123456789
            // I****T-------H******
            // z****T-------H123456 m_head_index = 13, index = 7, array_index = 0
            // Iz****T------H123456

            // *I****T-------H*****
            // 6z****T-------H12345 m_head_index = 14, index = 7, array_index = 1
            // 6Iz****T------H12345

            // *****I****T-------H*
            // 23456z****T-------H1 m_head_index = 18, index = 7, array_index = 5
            // 23456Iz****T------H1

            // ******I****T-------H
            // 123456z****T-------H m_head_index = 19, index = 7, array_index = 6
            // 123456Iz****T------H
            memmove(    m_items+array_index+1,
                        m_items+array_index,
                        (m_num_items-index) * sizeof(T) );
            m_items[array_index] = item;
            m_num_items++;
            return item;
        }
    }
}


template <class T>
T
Array_t<T>::RemoveHead()
{
    assert(m_num_items);
    assert(m_head_index >= 0 && m_head_index < m_items_allocated);

    T* item = &m_items[m_head_index];
    m_num_items--;
    #if TARGET_CPU_FAST_INTEGER_MOD
        m_head_index = (m_head_index + 1) % m_items_allocated;
    #else
        m_head_index++;
        if(m_head_index == m_items_allocated)
            m_head_index = 0;
    #endif

    return *item;
}


template <class T>
T
Array_t<T>::RemoveTail()
{
    assert(m_num_items);
    assert(m_head_index >= 0 && m_head_index < m_items_allocated);

    m_num_items--;
    int tail_index;
    #if TARGET_CPU_FAST_INTEGER_MOD
        tail_index = (m_head_index + m_num_items) % m_items_allocated;
    #else
        tail_index = m_head_index + m_num_items;
        if(tail_index >= m_items_allocated)
            tail_index -= m_items_allocated;
    #endif
    return m_items[tail_index];
}


template <class T>
T
Array_t<T>::RemoveItemAt(int index)
{
    assert(index >= 0 && index < m_num_items);
    assert(m_head_index >= 0 && m_head_index < m_items_allocated);

    int array_index;
    #if TARGET_CPU_FAST_INTEGER_MOD
        array_index = (m_head_index + index) % m_items_allocated;
    #else
        array_index = m_head_index + index;
        if(array_index >= m_items_allocated)
            array_index -= m_items_allocated;
    #endif
    T item = m_items[array_index];

    // Shifting the head, the number of items to be moved is index
    // Shifting the tail, the number of items to be moved is m_num_items - (index+1)

    if (index < m_num_items - (index+1) )
    {
        // It is more efficient to shift the head forward one

        // Possible scenarios:
        // H****R******T-------
        // ----H****R******T---
        // -------H****R******T
        // T-------H****R******
        // *****T-------H****R*
        // ******T-------H****R
        // R******T-------H****
        // *R******T-------H***
        // ***R******T-------H*
        // ****R******T-------H

        if(m_head_index <= array_index)
        {
            // H****R******T-------
            // ----H****R******T---
            // -------H****R******T
            // T-------H****R******
            // *****T-------H****R*
            // ******T-------H****R
            memmove( m_items+m_head_index+1, m_items+m_head_index, index * sizeof(T) );
            #if TARGET_CPU_FAST_INTEGER_MOD
                m_head_index = (m_head_index + 1) % m_items_allocated;
            #else
                m_head_index++;
                if(m_head_index == m_items_allocated)
                    m_head_index = 0;
            #endif
            m_num_items--;
            return item;
        }

        else
        {
            // R******T-------H****
            // *R******T-------H***
            // ***R******T-------H*
            // ****R******T-------H
            memmove( m_items+1, m_items, array_index * sizeof(T) );
            m_items[0] = m_items[m_items_allocated-1];
            memmove(    m_items+m_head_index+1,
                        m_items+m_head_index,
                        ( m_items_allocated-(m_head_index+1) ) * sizeof(T) );
            #if TARGET_CPU_FAST_INTEGER_MOD
                m_head_index = (m_head_index + 1) % m_items_allocated;
            #else
                m_head_index++;
                if(m_head_index == m_items_allocated)
                    m_head_index = 0;
            #endif
            m_num_items--;
            return item;
        }
    }
    else
    {
        // It is more efficient to shift the tail back one

        // Possible scenarios:
        // H******R****T-------
        // ----H******R****T---
        // -------H******R****T
        // T-------H******R****
        // *T-------H******R***
        // ***T-------H******R*
        // ****T-------H******R
        // R****T-------H******
        // *R****T-------H*****
        // ******R****T-------H

        int tail_array_index;
        #if TARGET_CPU_FAST_INTEGER_MOD
            tail_array_index = (m_head_index + m_num_items - 1) % m_items_allocated;
        #else
            tail_array_index = m_head_index + m_num_items - 1;
            if(tail_array_index >= m_items_allocated)
                tail_array_index -= m_items_allocated;
        #endif
        if(tail_array_index >= array_index)
        {
            // H******R****T-------
            // ----H******R****T---
            // -------H******R****T
            // R****T-------H******
            // *R****T-------H*****
            // ******R****T-------H
            memmove(    m_items+array_index,
                        m_items+array_index+1,
                        ( m_num_items - (index+1) ) * sizeof(T) );
            m_num_items--;
            return item;
        }

        else
        {
            // T-------H******R****
            // *T-------H******R***
            // ***T-------H******R*
            // ****T-------H******R
            memmove(    m_items+array_index,
                        m_items+array_index+1,
                        ( m_items_allocated - (array_index+1) ) * sizeof(T) );
            m_items[m_items_allocated-1] = m_items[0];
            memmove( m_items, m_items+1, tail_array_index * sizeof(T) );
            m_num_items--;
            return item;
        }
    }
}


template <class T>
inline int
Array_t<T>::CountItems() const
{
    return m_num_items;
}


template <class T>
inline int
Array_t<T>::AllocatedItems() const
{
    return m_items_allocated;
}


template <class T>
inline void
Array_t<T>::SetNumValidItems(int count)
{
    assert(count <= m_num_items);
    m_num_items = count;
}


template <class T>
void
Array_t<T>::GrowIfNeeded( int min_allocated_items, bool expect_more_growth )
{
    if(m_items_allocated >= min_allocated_items)
        return;

    // Figure out how many items to allocate
    int new_items_allocated = min_allocated_items;
    if(expect_more_growth)
    {
        if(new_items_allocated == 0)
            new_items_allocated = 16;
        else if(new_items_allocated < 128)
            new_items_allocated *= 2;
        else
            new_items_allocated += new_items_allocated / 2;
    }

    // Allocate the new list
    T* new_list = new T[new_items_allocated];

    // Copy the existing items
    int copy_items_from_head_index = m_num_items;
    if(copy_items_from_head_index > m_items_allocated - m_head_index)
        copy_items_from_head_index = m_items_allocated - m_head_index;
    memcpy( new_list, m_items+m_head_index, copy_items_from_head_index * sizeof(T) );
    memcpy( new_list+copy_items_from_head_index,
            m_items,
            (m_num_items - copy_items_from_head_index) * sizeof(T) );

    // Install the new list
    if(m_items && !m_items_allocated_on_stack)
        delete[] m_items;
    m_items = new_list;
    m_items_allocated = new_items_allocated;
    m_items_allocated_on_stack = false;
    m_head_index = 0;
}



template <class T>
inline T
Array_t<T>::Head() const
{
    if(m_num_items == 0)
        return NULL;
    return m_items[m_head_index];
}


template <class T>
inline T
Array_t<T>::Tail() const
{
    if(m_num_items == 0)
        return NULL;
    int tail_array_index;
    #if TARGET_CPU_FAST_INTEGER_MOD
        tail_array_index = (m_head_index + m_num_items - 1) % m_items_allocated;
    #else
        tail_array_index = m_head_index + m_num_items - 1;
        if(tail_array_index >= m_items_allocated)
            tail_array_index -= m_items_allocated;
    #endif
    return m_items[tail_array_index];
}


template <class T>
inline T
Array_t<T>::ItemAt(int index) const
{
    assert(index >= 0 && index < m_num_items);
    int array_index;
    #if TARGET_CPU_FAST_INTEGER_MOD
        array_index = (m_head_index + index) % m_items_allocated;
    #else
        array_index = m_head_index + index;
        if(array_index >= m_items_allocated)
            array_index -= m_items_allocated;
    #endif
    return m_items[array_index];
}


template <class T>
inline T&
Array_t<T>::operator [](int index) const
{
    assert(index >= 0 && index <= m_num_items);
    if(index == m_num_items)
        const_cast<Array_t<T>*>(this)->GrowIfNeeded( m_num_items+1, true );

    int array_index;
    #if TARGET_CPU_FAST_INTEGER_MOD
        array_index = (m_head_index + index) % m_items_allocated;
    #else
        array_index = m_head_index + index;
        if(array_index >= m_items_allocated)
            array_index -= m_items_allocated;
    #endif
    return m_items[array_index];
}


template <class T>
inline void
Array_t<T>::operator +=(const T& item)
{
    AddTail(item);
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class List_t
//===
//==================================================================================================
//==================================================================================================
template <class T>
inline
List_t<T>::List_t()
{ }


template <class T>
inline
List_t<T>::List_t( T** stack_buffer, int stack_buffer_num_items_allcoated )
: Array_t<T*>( stack_buffer, stack_buffer_num_items_allcoated )
{ }


template <class T>
T*
List_t<T>::RemoveItem(T* item)
{
    for(int i = 0; i < Array_t<T*>::CountItems(); i++)
    {
        if(Array_t<T*>::ItemAt(i) == item)
        {
            Array_t<T*>::RemoveItemAt(i);
            return item;
        }
    }
    debug_error("The specified item was not found");
    return NULL;
}


template <class T>
int
List_t<T>::IndexOfItem(T* item)
{
    for(int i = 0; i < Array_t<T*>::CountItems(); i++)
        if(Array_t<T*>::ItemAt(i) == item)
            return i;
    return -1;
}


template <class T>
inline T&
List_t<T>::operator [](int index) const
{
    return *Array_t<T*>::ItemAt(index);
}


template <class T>
inline void
List_t<T>::operator -=(T* item)
{
    RemoveItem(item);
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class OwnedList_t
//===
//==================================================================================================
//==================================================================================================
template <class T>
inline
OwnedList_t<T>::OwnedList_t()
{ }


template <class T>
inline
OwnedList_t<T>::OwnedList_t( T** stack_buffer, int stack_buffer_num_items_allcoated )
: List_t<T*>( stack_buffer, stack_buffer_num_items_allcoated )
{ }


template <class T>
OwnedList_t<T>::~OwnedList_t()
{
    for(int i=0; i<List_t<T>::CountItems(); i++)
        delete List_t<T>::ItemAt(i);
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class LinkedList_t
//===
//==================================================================================================
//==================================================================================================
template <class T>
inline
LinkedList_t<T>::LinkedList_t()
{
    m_head = NULL;
    m_tail = NULL;
    m_num_items = 0;
}


template <class T>
T*
LinkedList_t<T>::AddHead(T* item)
{
    assert(!item->m_next);
    assert(!item->m_prev);
    if(m_num_items == 0)
    {
        m_head = item;
        m_tail = item;
        m_num_items = 1;
        return item;
    }
    assert(!static_cast<LinkedListNode_t<T>*>(m_head)->m_prev);
    assert(static_cast<LinkedListNode_t<T>*>(m_head) != item);
    m_head->m_prev = item;
    item->m_next = m_head;
    m_head = item;
    m_num_items++;
    return item;
}


template <class T>
T*
LinkedList_t<T>::AddTail(T* item)
{
    assert(!static_cast<LinkedListNode_t<T>*>(item)->m_next);
    assert(!static_cast<LinkedListNode_t<T>*>(item)->m_prev);
    if(m_num_items == 0)
    {
        m_head = item;
        m_tail = item;
        m_num_items = 1;
        return item;
    }
    assert(!static_cast<LinkedListNode_t<T>*>(m_tail)->m_next);
    assert(static_cast<LinkedListNode_t<T>*>(m_tail) != item);
    static_cast<LinkedListNode_t<T>*>(m_tail)->m_next = item;
    static_cast<LinkedListNode_t<T>*>(item)->m_prev = m_tail;
    m_tail = item;
    m_num_items++;
    return item;
}


template <class T>
T*
LinkedList_t<T>::AddItemBefore( T* new_item, T* after_item )
{
    assert(new_item && after_item);
    if(after_item == m_head)
    {
        AddHead(new_item);
        return new_item;
    }
    assert(!static_cast<LinkedListNode_t<T>*>(new_item)->m_next);
    assert(!static_cast<LinkedListNode_t<T>*>(new_item)->m_prev);
    assert(m_num_items);
    static_cast<LinkedListNode_t<T>*>(new_item)->m_prev =
                                            static_cast<LinkedListNode_t<T>*>(after_item)->m_prev;
    static_cast<LinkedListNode_t<T>*>(new_item)->m_next = after_item;
    static_cast<LinkedListNode_t<T>*>(new_item)->m_prev->m_next = new_item;
    after_item->m_prev = new_item;
    m_num_items++;
    return new_item;
}


template <class T>
T*
LinkedList_t<T>::AddItemAfter( T* before_item, T* new_item )
{
    assert(before_item && new_item);
    if(before_item == m_tail)
    {
        AddTail(new_item);
        return new_item;
    }
    assert(!new_item->m_next);
    assert(!new_item->m_prev);
    assert(m_num_items);
    new_item->m_prev = before_item;
    new_item->m_next = before_item->m_next;
    before_item->m_next = new_item;
    new_item->m_next->m_prev = new_item;
    m_num_items++;
    return new_item;
}


template <class T>
T*
LinkedList_t<T>::RemoveHead()
{
    assert(m_num_items && m_head);
    LinkedListNode_t<T>* item = m_head;
    assert(!item->m_prev);
    if(m_num_items == 1)
    {
        assert(m_head == m_tail);
        assert(!item->m_next);
        assert(!item->m_prev);
        m_head = NULL;
        m_tail = NULL;
        m_num_items = 0;
        return static_cast<T*>(item);
    }
    m_head = static_cast<T*>(item->m_next);
    static_cast<LinkedListNode_t<T>*>(m_head)->m_prev = NULL;
    item->m_next = NULL;
    m_num_items--;
    return static_cast<T*>(item);
}


template <class T>
T*
LinkedList_t<T>::RemoveTail()
{
    assert(m_num_items && m_tail);
    LinkedListNode_t<T>* item = m_tail;
    assert(!item->m_next);
    if(m_num_items == 1)
    {
        assert(m_head == m_tail);
        assert(!item->m_prev);
        m_head = NULL;
        m_tail = NULL;
        m_num_items = 0;
        return static_cast<T*>(item);
    }
    m_tail = static_cast<T*>(item->m_prev);
    static_cast<LinkedListNode_t<T>*>(m_tail)->m_next = NULL;
    item->m_prev = NULL;
    m_num_items--;
    return static_cast<T*>(item);
}


template <class T>
T*
LinkedList_t<T>::RemoveItem(T* item)
{
    assert(m_num_items);
    if(item == m_head)
        return RemoveHead();
    if(item == m_tail)
        return RemoveTail();
    assert(m_head && (m_head != m_tail) && m_tail);
    assert(     static_cast<LinkedListNode_t<T>*>(item)->m_prev
            &&  static_cast<LinkedListNode_t<T>*>(item)->m_next);
    #if DEBUG
        LinkedListNode_t<T>* check_item_fwd = static_cast<LinkedListNode_t<T>*>(m_head)->m_next;
        LinkedListNode_t<T>* check_item_back = static_cast<LinkedListNode_t<T>*>(m_tail)->m_prev;
        while(check_item_fwd)
        {
            assert(check_item_back);
            if(check_item_fwd == item)
                break;
            if(check_item_fwd == check_item_back)
                break;
            if(check_item_back == item)
                break;

            check_item_fwd = check_item_fwd->m_next;
            if(check_item_fwd == check_item_back)
                break;
            check_item_back = check_item_back->m_prev;
        }

        assert(check_item_fwd == item || check_item_back == item);
        // Otherwise, the item was not in the list
    #endif
    static_cast<LinkedListNode_t<T>*>(static_cast<LinkedListNode_t<T>*>(item)->m_prev)->m_next =
                                                    static_cast<LinkedListNode_t<T>*>(item)->m_next;
    static_cast<LinkedListNode_t<T>*>(static_cast<LinkedListNode_t<T>*>(item)->m_next)->m_prev =
                                                    static_cast<LinkedListNode_t<T>*>(item)->m_prev;
    static_cast<LinkedListNode_t<T>*>(item)->m_prev = NULL;
    static_cast<LinkedListNode_t<T>*>(item)->m_next = NULL;
    m_num_items--;
    return item;
}


template <class T>
inline int
LinkedList_t<T>::CountItems() const
{
    return m_num_items;
}


template <class T>
inline T*
LinkedList_t<T>::Head() const
{
    return m_head;
}


template <class T>
inline T*
LinkedList_t<T>::Tail() const
{
    return m_tail;
}


template <class T>
inline void
LinkedList_t<T>::operator +=(T* item)
{
    AddTail(item);
}


template <class T>
inline void
LinkedList_t<T>::operator -=(T* item)
{
    RemoveItem(item);
}


template <class T>
void
LinkedList_t<T>::SortSmallOrSlow()
{
    if(m_num_items < 2)
        return;

    T* first_unsorted = static_cast<T*>(m_head->m_next);
    while(first_unsorted)
    {
        if( (*first_unsorted) < *( static_cast<T*>(first_unsorted->m_prev) ) )
        {
            T* reposition_item = first_unsorted;
            T* check_pos = static_cast<T*>(first_unsorted->m_prev->m_prev);
            // first_unsorted->m_prev cannot be NULL, but check_pos could be NULL
            first_unsorted = static_cast<T*>(first_unsorted->m_next);
            RemoveItem(reposition_item);

            // Find where to reposition the item to
            while(check_pos)
            {
                if( (*reposition_item) < (*check_pos) )
                    check_pos = static_cast<T*>(check_pos->m_prev);
                else
                {
                    AddItemAfter( check_pos, reposition_item );
                    break;
                }
            }
            if(!check_pos)
                AddHead(reposition_item);
        }
        else
            first_unsorted = static_cast<T*>(first_unsorted->m_next);
    }
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class LinkedListNode_t
//===
//==================================================================================================
//==================================================================================================
template <class T>
inline
LinkedListNode_t<T>::LinkedListNode_t()
{
    m_next = NULL;
    m_prev = NULL;
}


template <class T>
inline T*
LinkedListNode_t<T>::Next() const
{
    assert( (!m_next) || m_next->m_prev == this );
    return static_cast<T*>(m_next);
}


template <class T>
inline T*
LinkedListNode_t<T>::Prev() const
{
    assert( (!m_prev) || m_prev->m_next == this );
    return static_cast<T*>(m_prev);
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class OwnedLinkedList_t
//===
//==================================================================================================
//==================================================================================================
template <class T>
OwnedLinkedList_t<T>::~OwnedLinkedList_t()
{
    while( LinkedList_t<T>::Tail() )
        delete LinkedList_t<T>::RemoveTail();
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class BTree_t
//===
//==================================================================================================
//==================================================================================================
template <class T, class K>
inline
BTree_t<T,K>::BTree_t()
{
    m_root = NULL;
    m_num_items = 0;
}


template <class T, class K>
T*
BTree_t<T,K>::FindItem(K key) const
{
    BTreeNode_t<T,K>* node = static_cast<BTreeNode_t<T,K>*>( const_cast<T*>(m_root) );
    for(;;)
    {
        if(!node)
            return NULL;

        int compare = static_cast<T*>(node)->Compare(key);

        if(compare < 0)
            node = node->m_next;    // node comes before key
        else if(compare > 0)
            node = node->m_prev;    // node comes after key
        else
        {
            // Found a matching item.  Return the one closest to the head with a matching key.
            for(;;)
            {
                BTreeNode_t<T,K>* prev = node->Prev();
                if(prev && static_cast<T*>(prev)->Compare(key) == 0)
                    node = prev;
                else
                    return static_cast<T*>(node);
            }
        }
    }
}


template <class T, class K>
T*
BTree_t<T,K>::FindItemAtOrBefore(K key) const
{
    BTreeNode_t<T,K>* node = m_root;
    BTreeNode_t<T,K>* last_before_node = NULL;
    for(;;)
    {
        if(!node)
            return static_cast<T*>(last_before_node);

        int compare = static_cast<T*>(node)->Compare(key);

        if(compare < 0)
        {
            last_before_node = node;    // node comes before key
            node = node->m_next;
        }
        else if(compare > 0)
            node = node->m_prev;        // node comes after key
        else
        {
            // Found a matching item.  Return the one closest to the tail with a matching key.
            for(;;)
            {
                BTreeNode_t<T,K>* next = node->Next();
                if(next && static_cast<T*>(next)->Compare(key) == 0)
                    node = next;
                else
                    return static_cast<T*>(node);
            }
        }
    }
}


template <class T, class K>
T*
BTree_t<T,K>::FindItemAtOrAfter(K key) const
{
    BTreeNode_t<T,K>* node = m_root;
    BTreeNode_t<T,K>* last_after_node = NULL;
    for(;;)
    {
        if(!node)
            return static_cast<T*>(last_after_node);

        int compare = static_cast<T*>(node)->Compare(key);

        if(compare < 0)
            node = node->m_next;        // node comes before key
        else if(compare > 0)
        {
            last_after_node = node;     // node comes after key
            node = node->m_prev;
        }
        else
        {
            // Found a matching item.  Return the one closest to the head with a matching key.
            for(;;)
            {
                BTreeNode_t<T,K>* prev = node->Prev();
                if(prev && static_cast<T*>(prev)->Compare(key) == 0)
                    node = prev;
                else
                    return static_cast<T*>(node);
            }
        }
    }
}


template <class T, class K>
void
BTree_t<T,K>::AddItem( T* new_item, bool balance_tree )
{
    assert(new_item);
    assert( (static_cast<BTreeNode_t<T,K>*>(new_item) )->m_prev == NULL);
    assert( (static_cast<BTreeNode_t<T,K>*>(new_item) )->m_next == NULL);
    assert( (static_cast<BTreeNode_t<T,K>*>(new_item) )->m_parent == NULL);
    assert( (static_cast<BTreeNode_t<T,K>*>(new_item) )->m_child_nodes_depth == 0);

    if(!m_root)
    {
        assert(m_num_items == 0);
        m_root = new_item;
        m_num_items = 1;
        return;
    }

    BTreeNode_t<T,K>* node = m_root;
    m_num_items++;
    for(;;)
    {
        int compare = static_cast<T*>(node)->Compare( static_cast<K>(*new_item) );

        if(compare <= 0)
        {
            // node comes before new_item
            if(node->m_next)
                node = node->m_next;
            else
            {
                node->m_next = new_item;
                static_cast<BTreeNode_t<T,K>*>(new_item)->m_parent = node;
                UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(node), balance_tree );
                return;
            }
        }
        else if(compare > 0)
        {
            // node comes after new_item
            if(node->m_prev)
                node = node->m_prev;
            else
            {
                node->m_prev = new_item;
                static_cast<BTreeNode_t<T,K>*>(new_item)->m_parent = node;
                UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(node), balance_tree );
                return;
            }
        }
    }
}


template <class T, class K>
void
BTree_t<T,K>::UpdateChildNodeCountsAndBalanceToRoot( T* a_node, bool balance_tree )
{
    assert(a_node);
    BTreeNode_t<T,K>* node = a_node;
    BTreeNode_t<T,K>* parent;
    BTreeNode_t<T,K>* a;
    BTreeNode_t<T,K>* b;
    BTreeNode_t<T,K>* c;
    BTreeNode_t<T,K>* d;

    while(node)
    {
        int left_child_nodes_depth = 0;
        int right_child_nodes_depth = 0;
        if(node->m_prev)
            left_child_nodes_depth = node->m_prev->m_child_nodes_depth + 1;
        if(node->m_next)
            right_child_nodes_depth = node->m_next->m_child_nodes_depth + 1;

        if(!balance_tree)
            node->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );
        else if(left_child_nodes_depth >= right_child_nodes_depth + 2)
        {
            // The left is too deep compared with the right; balance it
            //  parent          parent     (parent might not exist)
            //   node             b        (node then b could be m_next or m_prev in parent)
            //  b    d    ->     a node    (d might not exist)
            // a c                 c  d    (either a or c might not exist)
            parent = node->m_parent;
            b = node->m_prev;
            d = node->m_next;
            a = b->m_prev;
            c = b->m_next;

            // Shifting won't reduce the depth if c is the limiting factor
            if(c && c->m_child_nodes_depth == left_child_nodes_depth - 2)
            {
                // c is the limiting factor; do nothing
                node->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );
            }
            else
            {
                // Reestablish all connections
                if(parent)
                {
                    if(parent->m_prev == node)
                        parent->m_prev = b;
                    else
                    {
                        assert(parent->m_next == node);
                        parent->m_next = b;
                    }
                }
                else
                    m_root = static_cast<T*>(b);
                b->m_parent = parent;
                b->m_prev = a;
                if(a)
                    a->m_parent = b;
                b->m_next = node;
                node->m_parent = b;
                node->m_prev = c;
                if(c)
                    c->m_parent = node;

                // Reevaluate node depths for node, b, parent

                // node
                left_child_nodes_depth = 0;
                if(c)
                    left_child_nodes_depth = c->m_child_nodes_depth + 1;
                right_child_nodes_depth = 0;
                if(d)
                    right_child_nodes_depth = d->m_child_nodes_depth + 1;
                node->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );

                // b
                left_child_nodes_depth = 0;
                if(a)
                    left_child_nodes_depth = a->m_child_nodes_depth + 1;
                right_child_nodes_depth = node->m_child_nodes_depth + 1;
                b->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );

                // parent
                if(parent)
                {
                    left_child_nodes_depth = 0;
                    if(parent->m_prev)
                        left_child_nodes_depth = parent->m_prev->m_child_nodes_depth + 1;
                    right_child_nodes_depth = 0;
                    if(parent->m_next)
                        right_child_nodes_depth = parent->m_next->m_child_nodes_depth + 1;
                    parent->m_child_nodes_depth = max(  left_child_nodes_depth,
                                                        right_child_nodes_depth );
                }
            }
        }
        else if(right_child_nodes_depth >= left_child_nodes_depth + 2)
        {
            // The right is too deep compared with the left; balance it
            //  parent             parent   (parent might not exist)
            //   node                c      (node then b could be m_next or m_prev in parent)
            //  a    c     ->    node d     (d might not exist)
            //      b d          a  b       (either a or c might not exist)
            parent = node->m_parent;
            a = node->m_prev;
            c = node->m_next;
            b = c->m_prev;
            d = c->m_next;

            // Shifting won't reduce the depth if b is the limiting factor
            if(b && b->m_child_nodes_depth == right_child_nodes_depth - 2)
            {
                // c is the limiting factor; do nothing
                node->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );
            }
            else
            {
                // Reestablish all connections
                if(parent)
                {
                    if(parent->m_prev == node)
                        parent->m_prev = c;
                    else
                    {
                        assert(parent->m_next == node);
                        parent->m_next = c;
                    }
                }
                else
                    m_root = static_cast<T*>(c);
                c->m_parent = parent;
                c->m_prev = node;
                c->m_next = d;
                if(d)
                    d->m_parent = c;
                node->m_parent = c;
                node->m_next = b;
                if(b)
                    b->m_parent = node;

                // Reevaluate node depths for node, c, parent

                // node
                left_child_nodes_depth = 0;
                if(a)
                    left_child_nodes_depth = a->m_child_nodes_depth + 1;
                right_child_nodes_depth = 0;
                if(b)
                    right_child_nodes_depth = b->m_child_nodes_depth + 1;
                node->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );

                // c
                left_child_nodes_depth = node->m_child_nodes_depth + 1;
                right_child_nodes_depth = 0;
                if(d)
                    right_child_nodes_depth = d->m_child_nodes_depth + 1;
                c->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );

                // parent
                if(parent)
                {
                    left_child_nodes_depth = 0;
                    if(parent->m_prev)
                        left_child_nodes_depth = parent->m_prev->m_child_nodes_depth + 1;
                    right_child_nodes_depth = 0;
                    if(parent->m_next)
                        right_child_nodes_depth = parent->m_next->m_child_nodes_depth + 1;
                    parent->m_child_nodes_depth = max(  left_child_nodes_depth,
                                                        right_child_nodes_depth );
                }
            }
        }
        else
            node->m_child_nodes_depth = max( left_child_nodes_depth, right_child_nodes_depth );

        node = node->m_parent;
    }
}


template <class T, class K>
T*
BTree_t<T,K>::RemoveHead(bool balance_tree)
{
    assert(m_root);

    BTreeNode_t<T,K>* node = m_root;
    while(node->m_prev)
        node = node->m_prev;

    if(node->m_parent)
    {
        node->m_parent->m_prev = node->m_next;
        if(node->m_next)
            node->m_next->m_parent = node->m_parent;
    }
    else
    {
        m_root = static_cast<T*>(node->m_next);
        if(node->m_next)
            node->m_next->m_parent = NULL;
    }

    if(node->m_parent)
        UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(node->m_parent), balance_tree );

    m_num_items--;

    node->m_next = NULL;
    node->m_parent = NULL;
    node->m_child_nodes_depth = 0;

    #if DEBUG
        if(m_num_items)
            assert(m_root);
        else
            assert(!m_root);
    #endif

    return static_cast<T*>(node);
}


template <class T, class K>
T*
BTree_t<T,K>::RemoveTail(bool balance_tree)
{
    assert(m_root);

    BTreeNode_t<T,K>* node = m_root;
    while(node->m_next)
        node = node->m_next;

    if(node->m_parent)
    {
        node->m_parent->m_next = node->m_prev;
        if(node->m_prev)
            node->m_prev->m_parent = node->m_parent;
    }
    else
    {
        m_root = static_cast<T*>(node->m_prev);
        if(node->m_prev)
            node->m_prev->m_parent = NULL;
    }

    if(node->m_parent)
        UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(node->m_parent), balance_tree );

    m_num_items--;

    node->m_prev = NULL;
    node->m_parent = NULL;
    node->m_child_nodes_depth = 0;

    #if DEBUG
        if(m_num_items)
            assert(m_root);
        else
            assert(!m_root);
    #endif

    return static_cast<T*>(node);
}


template <class T, class K>
T*
BTree_t<T,K>::IsInTree(T* item) const
{
    BTreeNode_t<T,K>* check_root = item;
    while(check_root && check_root->m_parent)
        check_root = check_root->m_parent;
    if(check_root == m_root)
        return item;
    return NULL;
}


template <class T, class K>
T*
BTree_t<T,K>::RemoveItem( T* item, bool balance_tree )
{
    BTreeNode_t<T,K>* prev = static_cast<BTreeNode_t<T,K>*>(item)->m_prev;
    BTreeNode_t<T,K>* next = static_cast<BTreeNode_t<T,K>*>(item)->m_next;
    BTreeNode_t<T,K>* parent = static_cast<BTreeNode_t<T,K>*>(item)->m_parent;

    #if DEBUG
        BTreeNode_t<T,K>* check_root = item;
        while(check_root->m_parent)
            check_root = check_root->m_parent;
        assert(check_root == m_root);
    #endif

    if(prev && !next)
    {
        //     parent       parent   (parent might not exist)
        //      node     ->  prev
        //  prev    NULL
        if(parent)
        {
            if(parent->m_prev == item)
                parent->m_prev = prev;
            else
            {
                assert(parent->m_next == item);
                parent->m_next = prev;
            }
            prev->m_parent = parent;
            UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(parent), balance_tree );
        }
        else
        {
            m_root = static_cast<T*>(prev);
            prev->m_parent = NULL;
        }
    }
    else if(next && !prev)
    {
        //     parent       parent   (parent might not exist)
        //      node     ->  next
        //  NULL    next
        if(parent)
        {
            if(parent->m_prev == item)
                parent->m_prev = next;
            else
            {
                assert(parent->m_next == item);
                parent->m_next = next;
            }
            next->m_parent = parent;
            UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(parent), balance_tree );
        }
        else
        {
            m_root = static_cast<T*>(next);
            next->m_parent = NULL;
        }
    }
    else if( !(prev || next) )
    {
        //     parent       parent   (parent might not exist)
        //      node     ->  NULL
        //  NULL    NULL
        if(parent)
        {
            if(parent->m_prev == item)
                parent->m_prev = NULL;
            else
            {
                assert(parent->m_next == item);
                parent->m_next = NULL;
            }
            UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(parent), balance_tree );
        }
        else
            m_root = NULL;
    }
    else
    {
        //     parent                parent    parent         (parent might not exist)
        //      node        ->     prev     or     prev
        //  prev    next           a  b            a  b       (a, b, c, d might not exist)
        //  a  b    c  d               next            next
        //                             c  d            c  d
        // If next had a deeper child tree than prev, this wouldn't be the ideal arrangement, but
        // tree balancing will take care of that
        if(parent)
        {
            if(parent->m_prev == item)
                parent->m_prev = prev;
            else
            {
                assert(parent->m_next == item);
                parent->m_next = prev;
            }
            prev->m_parent = parent;
        }
        else
        {
            m_root = static_cast<T*>(prev);
            prev->m_parent = NULL;
        }

        // The diagram above is actually simplified; where next is chained off of b, there could
        // be any number of layers below b, with next belonging after b->m_next->m_next, etc
        while(prev->m_next)
            prev = prev->m_next;

        prev->m_next = next;
        next->m_parent = prev;
        UpdateChildNodeCountsAndBalanceToRoot( static_cast<T*>(prev), balance_tree );
    }

    m_num_items--;

    static_cast<BTreeNode_t<T,K>*>(item)->m_prev = NULL;
    static_cast<BTreeNode_t<T,K>*>(item)->m_parent = NULL;
    static_cast<BTreeNode_t<T,K>*>(item)->m_next = NULL;
    static_cast<BTreeNode_t<T,K>*>(item)->m_child_nodes_depth = 0;

    #if DEBUG
        if(m_num_items)
            assert(m_root);
        else
            assert(!m_root);
    #endif

    return item;
}


template <class T, class K>
inline int
BTree_t<T,K>::CountItems() const
{
    return m_num_items;
}


template <class T, class K>
T*
BTree_t<T,K>::Head() const
{
    BTreeNode_t<T,K>* node = m_root;
    if(!node)
        return NULL;
    while(node->m_prev)
        node = node->m_prev;
    return static_cast<T*>(node);
}


template <class T, class K>
T*
BTree_t<T,K>::Tail() const
{
    BTreeNode_t<T,K>* node = m_root;
    if(!node)
        return NULL;
    while(node->m_next)
        node = node->m_next;
    return static_cast<T*>(node);
}


template <class T, class K>
inline T*
BTree_t<T,K>::Root() const
{
    return m_root;
}


template <class T, class K>
inline void
BTree_t<T,K>::operator +=(T* item)
{
    AddItem(item);
}


template <class T, class K>
inline void
BTree_t<T,K>::operator -=(T* item)
{
    RemoveItem(item);
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class BTreeNode_t
//===
//==================================================================================================
//==================================================================================================
template <class T, class K>
inline
BTreeNode_t<T,K>::BTreeNode_t()
{
    m_prev = NULL;
    m_next = NULL;
    m_parent = NULL;
    m_child_nodes_depth = 0;
}


template <class T, class K>
T*
BTreeNode_t<T,K>::Next() const
{
    BTreeNode_t<T,K>* node;
    if(m_next)
    {
        node = m_next;
        while(node && node->m_prev)
            node = node->m_prev;
        return static_cast<T*>(node);
    }

    node = const_cast<T*>( static_cast<const T*>(this) );
    for(;;)
    {
        if(!node->m_parent)
            return NULL;
        if(node->m_parent->m_prev == node)
            return static_cast<T*>(node->m_parent);
        node = node->m_parent;
    }
}


template <class T, class K>
T*
BTreeNode_t<T,K>::Prev() const
{
    BTreeNode_t<T,K>* node;
    if(m_prev)
    {
        node = m_prev;
        while(node && node->m_next)
            node = node->m_next;
        return static_cast<T*>(node);
    }

    node = const_cast<T*>( static_cast<const T*>(this) );
    for(;;)
    {
        if(!node->m_parent)
            return NULL;
        if(node->m_parent->m_next == node)
            return static_cast<T*>(node->m_parent);
        node = node->m_parent;
    }
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator < (const T& other)
{
    return (static_cast<T*>(this)->Compare( static_cast<K>(other) ) < 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator <= (const T& other)
{
    return (static_cast<T*>(this)->Compare( static_cast<K>(other) ) <= 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator > (const T& other)
{
    return (static_cast<T*>(this)->Compare( static_cast<K>(other) ) > 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator >= (const T& other)
{
    return (static_cast<T*>(this)->Compare( static_cast<K>(other) ) >= 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator == (const T& other)
{
    return (static_cast<T*>(this)->Compare( static_cast<K>(other) ) == 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator < (K key)
{
    return (static_cast<T*>(this)->Compare(key) < 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator <= (K key)
{
    return (static_cast<T*>(this)->Compare(key) <= 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator > (K key)
{
    return (static_cast<T*>(this)->Compare(key) > 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator >= (K key)
{
    return (static_cast<T*>(this)->Compare(key) >= 0);
}


template <class T, class K>
inline bool
BTreeNode_t<T,K>::operator == (K key)
{
    return (static_cast<T*>(this)->Compare(key) == 0);
}


template <class T, class K>
inline int
BTreeNode_t<T,K>::ChildNodesDepth() const
{
    return m_child_nodes_depth;
}


template <class T, class K>
void
BTreeNode_t<T,K>::ValidateChildNodeDepth() const
{
    assert(     (m_next && m_child_nodes_depth == m_next->m_child_nodes_depth + 1)
            ||  (m_prev && m_child_nodes_depth == m_prev->m_child_nodes_depth + 1)
            ||  (m_child_nodes_depth == 0) );
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class OwnedBTree_t
//===
//==================================================================================================
//==================================================================================================
template <class T, class K>
OwnedBTree_t<T,K>::~OwnedBTree_t()
{
    while( BTree_t<T,K>::CountItems() )
        delete BTree_t<T,K>::RemoveHead(false);
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class SortedList_t
//===
//==================================================================================================
//==================================================================================================
template <class T, class K>
SortedList_t<T,K>::SortedList_t()
{
    m_items = NULL;
    m_num_items = 0;
    m_items_allocated = 0;
    m_items_allocated_on_stack = false;
}


template <class T, class K>
SortedList_t<T,K>::SortedList_t( T** stack_buffer, int stack_buffer_num_items_allcoated )
{
    m_items = stack_buffer;
    m_num_items = 0;
    m_items_allocated = stack_buffer_num_items_allcoated;
    m_items_allocated_on_stack = true;
}

template <class T, class K>
SortedList_t<T,K>::~SortedList_t()
{
    if(m_items && !m_items_allocated_on_stack)
        delete[] m_items;
}


template <class T, class K>
int
SortedList_t<T,K>::FindItemIndex( K key, bool at_or_before, bool at_or_after ) const
{
    if(m_num_items == 0)
        return -1;

    int first_unchecked = 0;
    int last_unchecked = m_num_items-1;
    for(;;)
    {
        int mid = (first_unchecked + last_unchecked) / 2;
        assert(mid >= 0 && mid < m_num_items);
        int result = m_items[mid]->Compare(key);
        if(result == 0)
        {
            // The item at mid has a matching key.
            if(at_or_before)
            {
                // Go towards the tail.
                for(;;)
                {
                    int next = mid+1;
                    if(next < m_num_items && m_items[next]->Compare(key) == 0)
                        mid = next;
                    else
                        return mid;
                }
            }
            else
            {
                // Go towards the head.
                for(;;)
                {
                    int prev = mid-1;
                    if(prev >= 0 && m_items[prev]->Compare(key) == 0)
                        mid = prev;
                    else
                        return mid;
                }
            }
        }
        else if(result < 0)
        {
            // this comes before key: mid comes before key
            first_unchecked = mid+1;
            if(last_unchecked < first_unchecked)
            {
                // For at_or_before or at_or_after evaluation, mid is before key, mid+1 must be
                // after (if it exists).
                if(at_or_before)
                {
                    #if DEBUG
                        if(mid+1 < m_num_items)
                            assert(m_items[mid+1]->Compare(key) > 0);
                    #endif
                    return mid;
                }
                else if(at_or_after)
                {
                    // Item at mid+1 (if it exists) is after key
                    if(mid+1 == m_num_items)
                        return -1;
                    assert(m_items[mid+1]->Compare(key) > 0);
                    return mid+1;
                }
                return -1;
            }
        }
        else // result > 0
        {
            // this comes after key: mid comes after key
            last_unchecked = mid-1;
            if(last_unchecked < first_unchecked)
            {
                // For at_or_before or at_or_after evaluation, mid is after key, mid-1 must be
                // before (if it exists).
                if(at_or_before)
                {
                    if(mid-1 < 0)
                        return -1;
                    assert(m_items[mid-1]->Compare(key) < 0);
                    return mid-1;
                }
                else if(at_or_after)
                {
                    #if DEBUG
                        if(mid-1 >= 0)
                            assert(m_items[mid-1]->Compare(key) < 0);
                    #endif
                    return mid;
                }
                return -1;
            }
        }
    }
}


template <class T, class K>
int
SortedList_t<T,K>::FindItemIndex( T* item, bool adding ) const
{
    if(m_num_items == 0)
        return -1;

    int first_unchecked = 0;
    int last_unchecked = m_num_items-1;
    for(;;)
    {
        int mid = (first_unchecked + last_unchecked) / 2;
        assert(mid >= 0 && mid < m_num_items);
        int result = m_items[mid]->Compare( static_cast<K>(*item) );
        if(result == 0)
        {
            // Found a matching key. 
            if(adding)
            {
                // The item at mid has a matching key.  Go towards the head.
                for(;;)
                {
                    int next = mid+1;
                    if(     next < m_num_items
                        &&  m_items[next]->Compare( static_cast<K>(*item) ) == 0 )
                    {
                        mid = next;
                    }
                    else
                        return mid;
                }
            }
            else
            {
                // Searching for the item
                if(m_items[mid] == item)
                    return mid;

                // See if one of the adjacent items with the same key is an exact match for the item.
                int sibling = mid-1;
                while(sibling >= 0)
                {
                    if(m_items[sibling]->Compare( static_cast<K>(*item) ) != 0)
                        break;
                    if(m_items[sibling] == item)
                        return sibling;
                    sibling--;
                }
                sibling = mid+1;
                while(sibling < m_num_items)
                {
                    if(m_items[sibling]->Compare( static_cast<K>(*item) ) != 0)
                        break;
                    if(m_items[sibling] == item)
                        return sibling;
                    sibling++;
                }
                return -1;
            }
        }
        else if(result < 0)
        {
            // this comes before item: mid comes before item
            first_unchecked = mid+1;
            if(last_unchecked < first_unchecked)
            {
                // mid is before item, mid+1 must be after (if it exists).
                if(adding)
                {
                    // Item at mid+1 (if it exists) is after item
                    return mid;
                }
                return -1;
            }
        }
        else // result > 0
        {
            // this comes after item: mid comes after item
            last_unchecked = mid-1;
            if(last_unchecked < first_unchecked)
            {
                // mid is after item, mid-1 must be before (if it exists).
                if(adding)
                {
                    return mid-1;
                }
                return -1;
            }
        }
    }
}


template <class T, class K>
T*
SortedList_t<T,K>::FindItem( K key, out int* a_index ) const
{
    int index = FindItemIndex( key, false, false );
    if(index == -1)
    {
        if(a_index)
            *a_index = -1;
        return NULL;
    }
    if(a_index)
        *a_index = index;
    return m_items[index];
}


template <class T, class K>
T*
SortedList_t<T,K>::FindItemAtOrBefore( K key, out int* a_index ) const
{
    int index = FindItemIndex( key, true, false );
    if(index == -1)
    {
        if(a_index)
            *a_index = -1;
        return NULL;
    }
    if(a_index)
        *a_index = index;
    return m_items[index];
}


template <class T, class K>
T*
SortedList_t<T,K>::FindItemAtOrAfter( K key, out int* a_index ) const
{
    int index = FindItemIndex( key, false, true );
    if(index == -1)
    {
        if(a_index)
            *a_index = -1;
        return NULL;
    }
    if(a_index)
        *a_index = index;
    return m_items[index];
}


template <class T, class K>
void
SortedList_t<T,K>::AddItem(T* item)
{
    assert(item);
    if(     m_num_items == 0
        ||  m_items[m_num_items-1]->Compare( static_cast<K>(*item) ) <= 0 )
    {
        AddTail(item);
        return;
    }
    int result = m_items[0]->Compare( static_cast<K>(*item) );
    if(result > 0)
    {
        AddHead(item);
        return;
    }

    // FindItemIndex will return the index of the item before where the new one should be inserted
    int index = FindItemIndex( item, true ) + 1;

    if(m_num_items < m_items_allocated)
    {
        // Insert at index
        memmove( m_items+index+1, m_items+index, (m_num_items-index) * sizeof(T*) );
        m_items[index] = item;
    }
    else
    {
        // Need to make room for the item: figure out how big to make the new list
        int new_items_allocated = m_items_allocated;
        if(new_items_allocated == 0)
            new_items_allocated = 16;
        else if(new_items_allocated < 128)
            new_items_allocated *= 2;
        else
            new_items_allocated += new_items_allocated / 2;

        // Allocate the new list
        T** new_list = new T*[new_items_allocated];

        // Copy the existing items before index
        memcpy( new_list, m_items, index * sizeof(T*) );
        new_list[index] = item;
        memcpy( new_list+index+1, m_items+index, (m_num_items-index) * sizeof(T*) );
        if(m_items && !m_items_allocated_on_stack)
            delete[] m_items;
        m_items = new_list;
        m_items_allocated = new_items_allocated;
        m_items_allocated_on_stack = false;
    }
    m_num_items++;
}


template <class T, class K>
void
SortedList_t<T,K>::AddHead(T* item)
{
    if(m_num_items == 0)
    {
        if(!m_items)
        {   
            assert(m_items_allocated == 0);
            m_items_allocated = 16;
            m_items = new T*[m_items_allocated];
        }
        m_items[0] = item;
        m_num_items = 1;
        return;
    }

    // Make sure the item to be added comes before the existing head
    assert(item->Compare( static_cast<K>(*m_items[0]) ) <= 0);

    if(m_num_items < m_items_allocated)
    {
        // Insert at index 0
        memmove( m_items+1, m_items, (m_num_items) * sizeof(T*) );
        m_items[0] = item;
    }
    else
    {
        // Need to make room for the item: figure out how big to make the new list
        int new_items_allocated = m_items_allocated;
        if(new_items_allocated == 0)
            new_items_allocated = 16;
        else if(new_items_allocated < 128)
            new_items_allocated *= 2;
        else
            new_items_allocated += new_items_allocated / 2;

        // Allocate the new list
        T** new_list = new T*[new_items_allocated];
        new_list[0] = item;

        // Copy the existing items before index
        memcpy( new_list+1, m_items, m_num_items * sizeof(T*) );
        if(m_items && !m_items_allocated_on_stack)
            delete[] m_items;
        m_items = new_list;
        m_items_allocated = new_items_allocated;
        m_items_allocated_on_stack = false;
    }
    m_num_items++;
}


template <class T, class K>
void
SortedList_t<T,K>::AddTail( T* item, bool will_sort_later )
{
    if(m_num_items == 0)
    {
        if(!m_items)
        {   
            assert(m_items_allocated == 0);
            m_items_allocated = 16;
            m_items = new T*[m_items_allocated];
        }
        m_items[0] = item;
        m_num_items = 1;
        return;
    }

    // Make sure the item to be added comes after the existing tail
    assert(will_sort_later || item->Compare( static_cast<K>(*m_items[m_num_items-1]) ) >= 0);

    if(m_num_items == m_items_allocated)
    {
        // Need to make room for the item: figure out how big to make the new list
        int new_items_allocated = m_items_allocated;
        if(new_items_allocated == 0)
            new_items_allocated = 16;
        else if(new_items_allocated < 128)
            new_items_allocated *= 2;
        else
            new_items_allocated += new_items_allocated / 2;

        // Allocate the new list
        T** new_list = new T*[new_items_allocated];

        // Copy the existing items
        memcpy( new_list, m_items, m_num_items * sizeof(T*) );

        if(m_items && !m_items_allocated_on_stack)
            delete[] m_items;
        m_items = new_list;
        m_items_allocated = new_items_allocated;
        m_items_allocated_on_stack = false;
    }
    m_items[m_num_items] = item;
    m_num_items++;
}


template <class T, class K>
void
SortedList_t<T,K>::Sort()
{
    if(m_num_items < 2)
        return;

    T** alt_buf;
    T* stack_buf[c_max_stack_buf/sizeof(T*)];
    if( m_num_items > static_cast<int>( c_max_stack_buf/sizeof(T*) ) )
        alt_buf = new T*[m_num_items];
    else
        alt_buf = stack_buf;

    bool sorted_items_in_alt_buf = MergeSort( m_items, alt_buf, m_num_items );

    // Use the target platform's reasonable stack buffer size as a guage for what is reasonable to
    // waste in terms of heap space.  Waste up to 1/32 of the max stack buffer.  If the max stack
    // buffer is 8192 with 32-bit pointers, that's 1/32 of 2048 item pointers, or 64 pointers, or
    // 256 bytes.
    int max_waste_heap_items = ( c_max_stack_buf/sizeof(T*) ) / 32;

    if(alt_buf == stack_buf)
    {
        // The items must end up back in the m_items buffer, which might be reallocated to optimize
        // its memory usage.
        if(m_items_allocated_on_stack)
        {
            // There is no reason to reallocate m_items since it's already a stack buffer.
            if(sorted_items_in_alt_buf)
            {
                // The sorted items are in alt_buf, so copy back to m_items.
                memcpy( m_items, alt_buf, m_num_items*sizeof(T*) );
            }
        }
        else
        {
            // m_items is a heap buffer, so we might want to compact it.
            if(m_num_items < m_items_allocated - max_waste_heap_items)
            {
                // Do reallocate the m_items buffer
                T** new_items = new T*[m_num_items];
                if(sorted_items_in_alt_buf)
                    memcpy( new_items, alt_buf, m_num_items*sizeof(T*) );
                else
                    memcpy( new_items, m_items, m_num_items*sizeof(T*) );
                delete[] m_items;
                m_items = new_items;
                m_items_allocated = m_num_items;
            }
            else
            {
                // Don't bother reallocating the m_items buffer.
                if(sorted_items_in_alt_buf)
                {
                    // The sorted items are in alt_buf, so copy back to m_items.
                    memcpy( m_items, alt_buf, m_num_items*sizeof(T*) );
                }
            }
        }
    }
    else
    {
        // alt_buf is a heap buffer.  If it would optimize memory usage, m_items will be freed and
        // alt_buf will be installed in its place.
        if(m_items_allocated_on_stack)
        {
            // There is no reason to reallocate m_items since it's already a stack buffer.
            if(sorted_items_in_alt_buf)
            {
                // The sorted items are in alt_buf, so copy back to m_items.
                memcpy( m_items, alt_buf, m_num_items*sizeof(T*) );
            }
            delete[] alt_buf;
        }
        else
        {
            if(sorted_items_in_alt_buf)
            {
                // The sorted items are in alt_buf, so install it in place of m_items
                delete[] m_items;
                m_items = alt_buf;
                m_items_allocated = m_num_items;
            }
            else
            {
                // The sorted items are in m_items.  If that buffer is oversized, use alt_buf
                // instead.
                if(m_num_items < m_items_allocated - max_waste_heap_items)
                {
                    // Switch to using alt_buf
                    memcpy( alt_buf, m_items, m_num_items*sizeof(T*) );
                    delete[] m_items;
                    m_items = alt_buf;
                    m_items_allocated = m_num_items;
                }
                else
                {
                    // Don't bother reallocating the m_items buffer.
                    delete[] alt_buf;
                }
            }
        }
    }
}


template <class T, class K>
bool
SortedList_t<T,K>::MergeSort( T** from, T** to, int num_items )
{
    int first_half_num_items = num_items/2;
    assert(first_half_num_items >= 1);
    int second_half_num_items = num_items - first_half_num_items;
    assert(second_half_num_items >= 1);
    T* temp;

    // Force the first half to be a sorted list
    bool first_half_in_to;
    if(first_half_num_items == 1)
        first_half_in_to = false;
    else if(first_half_num_items == 2)
    {
        if(from[0]->Compare( static_cast<K>(*from[1]) ) > 0)
        {
            // from[0] is after from[1]
            temp = from[0];
            from[0] = from[1];
            from[1] = temp;
        }
        first_half_in_to = false;
    }
    else
    {
        first_half_in_to = MergeSort( from, to, first_half_num_items );
    }

    // Force the second half to be a sorted list
    bool second_half_in_to;
    if(second_half_num_items == 1)
        second_half_in_to = false;
    else if(second_half_num_items == 2)
    {
        if(from[first_half_num_items]->Compare( static_cast<K>(*from[first_half_num_items+1]) ) > 0)
        {
            // from[0] is after from[1]
            temp = from[first_half_num_items];
            from[first_half_num_items] = from[first_half_num_items+1];
            from[first_half_num_items+1] = temp;
        }
        second_half_in_to = false;
    }
    else
    {
        second_half_in_to = MergeSort(  from+first_half_num_items,
                                        to+first_half_num_items,
                                        second_half_num_items );
    }

    // At this point, both halves are sorted, but not necessarily in the same buffer.  They need to
    // be in the same buffer before merging.
    bool result_in_caller_to;
    if(first_half_in_to && !second_half_in_to)
    {
        // Move the first half to the "from" buffer, then merge into the caller's "to" buffer
        result_in_caller_to = true;
        memcpy( from, to, first_half_num_items*sizeof(T*) );
    }
    else if(second_half_in_to && !first_half_in_to)
    {
        // Move the second half to the "from" buffer, then merge into the caller's "to" buffer
        result_in_caller_to = true;
        memcpy( from + first_half_num_items,
                to + first_half_num_items,
                second_half_num_items * sizeof(T*) );
    }
    else if(first_half_in_to)
    {
        // Both halves must already be in the caller's "to" buffer, so we'll merge into the caller's
        // "from" buffer.  That being the case, swap the from/to relationship for the merge.
        assert(second_half_in_to);
        T** temp_buf = from;
        from = to;
        to = temp_buf;
        result_in_caller_to = false;
    }
    else
    {
        // Both halves must already be in the caller's "from" buffer, so we'll merge into the "to"
        // buffer.
        assert(!second_half_in_to);
        result_in_caller_to = true;
    }

    // Perform the merge of the two halves from "from" into a sorted list in "to"
    int first_half_index = 0;
    int second_half_index = 0;
    int to_index = 0;
    T** from_second_half = from + first_half_num_items;
    for(;;)
    {
        assert(first_half_index < first_half_num_items);
        assert(second_half_index < second_half_num_items);
        if(     from[first_half_index]->Compare(
                                            static_cast<K>(*from_second_half[second_half_index]) )
            <= 0 )
        {
            // The next first half item comes before or is equal to the next second half item
            to[to_index++] = from[first_half_index++];
            if(first_half_index == first_half_num_items)
            {
                // Out of items in the first half, so insert everything from the second half
                while(second_half_index < second_half_num_items)
                    to[to_index++] = from_second_half[second_half_index++];
                break;
            }
        }
        else
        {
            // The next first half item comes after the next second half item
            to[to_index++] = from_second_half[second_half_index++];
            if(second_half_index == second_half_num_items)
            {
                // Out of items in the second half, so insert everything from the first half
                while(first_half_index < first_half_num_items)
                    to[to_index++] = from[first_half_index++];
                break;
            }
        }
    }

    // All items must have been merged
    assert(first_half_index == first_half_num_items);
    assert(second_half_index == second_half_num_items);
    assert(to_index == num_items);

    return result_in_caller_to;
}


template <class T, class K>
T*
SortedList_t<T,K>::IsInList(T* item) const
{
    if(item == NULL)
        return NULL;
    int index = FindItemIndex( item, false );
    if(index == -1)
        return NULL;
    return item;
}


template <class T, class K>
T*
SortedList_t<T,K>::RemoveItem(T* item)
{
    int index = FindItemIndex( item, false );
    if(index == -1)
    {
        debug_error("The specified item was not found");
        return NULL;
    }

    // Found it.
    m_num_items--;
    assert(m_items[index] == item);
    memmove( m_items+index, m_items+index+1, (m_num_items-index) * sizeof(T*) );
    return item;
}


template <class T, class K>
T*
SortedList_t<T,K>::RemoveHead()
{
    assert(m_num_items);
    T* head = m_items[0];
    m_num_items--;
    memmove( m_items, m_items+1, m_num_items * sizeof(T*) );
    return head;
}


template <class T, class K>
inline T*
SortedList_t<T,K>::RemoveTail()
{
    assert(m_num_items);
    m_num_items--;
    return m_items[m_num_items];
}


template <class T, class K>
T*
SortedList_t<T,K>::RemoveItemAt(int index)
{
    m_num_items--;
    assert(m_num_items > index);
    T* item = m_items[index];
    memmove( m_items+index, m_items+index+1, (m_num_items-index) * sizeof(T*) );
    return item;
}


template <class T, class K>
int
SortedList_t<T,K>::IndexOfItem(T* item)
{
    return FindItemIndex( item, false );
}


template <class T, class K>
inline int
SortedList_t<T,K>::CountItems() const
{
    return m_num_items;
}


template <class T, class K>
inline T*
SortedList_t<T,K>::Head() const
{
    if(m_num_items == 0)
        return NULL;
    return m_items[0];
}


template <class T, class K>
inline T*
SortedList_t<T,K>::Tail() const
{
    if(m_num_items == 0)
        return NULL;
    return m_items[m_num_items-1];
}


template <class T, class K>
inline T*
SortedList_t<T,K>::ItemAt(int index) const
{
    assert(m_num_items > index);
    return m_items[index];
}


template <class T, class K>
inline T&
SortedList_t<T,K>::operator [](int index) const
{
    assert(m_num_items > index);
    return *m_items[index];
}


template <class T, class K>
inline void
SortedList_t<T,K>::operator +=(T* item)
{
    AddItem(item);
}


template <class T, class K>
inline void
SortedList_t<T,K>::operator -=(T* item)
{
    RemoveItem(item);
}




//==================================================================================================
//==================================================================================================
//===
//=== Template function implementations: class OwnedSortedList_t
//===
//==================================================================================================
//==================================================================================================
template <class T, class K>
inline
OwnedSortedList_t<T,K>::OwnedSortedList_t()
{ }


template <class T, class K>
inline
OwnedSortedList_t<T,K>::OwnedSortedList_t( T** stack_buffer, int stack_buffer_num_items_allcoated )
: List_t<T*>( stack_buffer, stack_buffer_num_items_allcoated )
{ }


template <class T, class K>
OwnedSortedList_t<T,K>::~OwnedSortedList_t()
{
    for(int i=0; i<SortedList_t<T,K>::CountItems(); i++)
        delete SortedList_t<T,K>::ItemAt(i);
}


#endif // _UT_LISTS_H_