ulcontainers.h

#ifndef ULCONTAINERS_H
#define ULCONTAINERS_H

#include "ultypes.h"
#include "ulassert.h"

// Forward declarations.
template <class T>
class ULList;
template <class K, class V>
class ULHashTable;


template <class T, class U>
class ULPair
{
    UL_TEST_FRIEND;

public:
    ULPair();
    ULPair(const T& firstItem, const U& secondItem);
    ULPair(const ULPair<T,U>& p);

    ULPair<T,U>& operator=(const ULPair<T,U>& p);

    bool operator==(const ULPair<T,U>& p) const;
    bool operator<(const ULPair<T,U>& p) const;
    bool operator!=(const ULPair<T,U>& p) const;
    
    const T& getFirst() const;
    const U& getSecond() const;
    void setFirst(const T& f);
    void setSecond(const U& s);

    T first;
    U second;
};

template <class T, class U>
ULPair<T,U>::ULPair()
{
}

template <class T, class U>
ULPair<T,U>::ULPair(const T& firstItem, const U& secondItem)
{
    this->first = firstItem;
    this->second = secondItem;
}

template <class T, class U>
ULPair<T,U>::ULPair(const ULPair<T,U>& p)
{
    *this = p;
}

template <class T, class U>
ULPair<T,U>& ULPair<T,U>::operator=(const ULPair<T,U>& p)
{
    if (this != &p) {
        this->first = p.first;
        this->second = p.second;
    }

    return *this;
}

template <class T, class U>
bool ULPair<T,U>::operator==(const ULPair<T,U>& p) const
{
    return (this->first == p.first && this->second == p.second);
}

template <class T, class U>
bool ULPair<T,U>::operator!=(const ULPair<T,U>& p) const
{
    return !(*this == p);
}


template <class T, class U>
bool ULPair<T,U>::operator<(const ULPair<T,U>& p) const
{
    if (!(this->first == p.first)) {
        return this->first < p.first;
    }

    return this->second < p.second;
}

template <class T, class U>
const T& ULPair<T,U>::getFirst() const
{
    return this->first;
}

template <class T, class U>
const U& ULPair<T,U>::getSecond() const
{
    return this->second;
}

template <class T, class U>
void ULPair<T,U>::setFirst(const T& f)
{
    this->first = f;
}

template <class T, class U>
void ULPair<T,U>::setSecond(const U& s)
{
    this->second = s;
}


template <class T>
struct ULListNode
{
    ULListNode();
    ULListNode(const T& data);
    ULListNode(const ULListNode<T>& node);

    ULListNode<T>& operator=(const ULListNode<T>& node);

    T data;
    ULListNode *next;
    ULListNode *previous;
};

template <class T>
ULListNode<T>::ULListNode()
{
    this->next = 0;
    this->previous = 0;
}

template <class T>
ULListNode<T>::ULListNode(const T& data)
{
    this->next = 0;
    this->previous = 0;
    this->data = data;
}

template <class T>
ULListNode<T>::ULListNode(const ULListNode<T>& node)
{
    *this = node;
}

template <class T>
ULListNode<T>& ULListNode<T>::operator=(const ULListNode<T>& node)
{
    if (this != &node) {
        this->data = node.data;
        this->next = node.next;
        this->previous = node.previous;
    }

    return *this;
}


template <class T>
class ULListIterator
{
    friend class ULList<T>;
    UL_TEST_FRIEND;

public:
    ULListIterator();
    ULListIterator(const ULListIterator<T>& it);

    void clear();
    ULListIterator<T>& operator=(const ULListIterator<T>& it);

    operator bool() const;
    bool operator==(const ULListIterator<T>& it) const;
    bool operator!=(const ULListIterator<T>& it) const;

    ULListIterator<T>& operator++();
    ULListIterator<T> operator++(int);
    ULListIterator<T>& operator--();
    ULListIterator<T> operator--(int);
    void increment(); // non-operator synonym for operator++(), to help SWIG
    void decrement(); // non-operator synonym for operator--(), to help SWIG

    T& operator*();
    T& getData(); // non-operator synonym for operator*, to help SWIG

    bool isAtEnd() const;
    bool isAtBeginning() const;
    int getIndex() const;

    ULList<T> *getList();

private:
    ULList<T> *list;
    ULListNode<T> *current;
};

template <class T>
ULListIterator<T>::ULListIterator()
{
    this->current = 0;
    this->list = 0;
}

template <class T>
ULListIterator<T>::ULListIterator(const ULListIterator<T>& it)
{
    *this = it;
}

template <class T>
void ULListIterator<T>::clear()
{
    this->current = 0;
    this->list = 0;
}

template <class T>
ULListIterator<T>& ULListIterator<T>::operator=(const ULListIterator<T>& it)
{
    if (this != &it) {
        this->current = it.current;
        this->list = it.list;
    }

    return *this;
}

template <class T>
bool ULListIterator<T>::isAtEnd() const
{
    return (this->current == 0);
}

template <class T>
bool ULListIterator<T>::isAtBeginning() const
{
    return (this->list == 0 || this->current == this->list->frontNode);
}

template <class T>
int ULListIterator<T>::getIndex() const
{
    if (this->list == 0 || this->current == 0) {
        return -1;
    }

    int count = -1;
    const ULListNode<T> *nodePtr;
    for (nodePtr = this->current; nodePtr != 0; nodePtr = nodePtr->previous) {
        count++;
    }

    return count;
}

template <class T>
ULList<T> *ULListIterator<T>::getList()
{
    return this->list;
}

template <class T>
ULListIterator<T>::operator bool() const
{
    return !(this->isAtEnd());
}

template <class T>
bool ULListIterator<T>::operator==(const ULListIterator<T>& it) const
{
    return this->current == it.current && this->list == it.list;
}

template <class T>
bool ULListIterator<T>::operator!=(const ULListIterator<T>& it) const
{
    return !(*this == it);
}

template <class T>
ULListIterator<T>& ULListIterator<T>::operator++()
{
    if (this->current != 0) {
        this->current = this->current->next;
    }

    return *this;
}

template <class T>
ULListIterator<T> ULListIterator<T>::operator++(int)
{
    ULListIterator<T> tmp = *this;
    ++(*this);
    return tmp;
}

template <class T>
ULListIterator<T>& ULListIterator<T>::operator--()
{
    UL_ASSERT(this->list != 0);

    if (this->current == this->list->frontNode) {
    } else if (this->current != 0) {
        this->current = this->current->previous;
    } else if (this->list != 0) {
        this->current = this->list->backNode;
    }

    return *this;
}

template <class T>
ULListIterator<T> ULListIterator<T>::operator--(int)
{
    ULListIterator<T> tmp = *this;
    --(*this);
    return tmp;
}

template <class T>
void ULListIterator<T>::increment()
{
    ++(*this);
}

template <class T>
void ULListIterator<T>::decrement()
{
    --(*this);
}

template <class T>
T& ULListIterator<T>::operator*()
{
    UL_ASSERT(this->current != 0);
    return this->current->data;
}

template <class T>
T& ULListIterator<T>::getData()
{
    return *(*this);
}

template <class T>
class ULListConstIterator
{
    friend class ULList<T>;
    UL_TEST_FRIEND;

public:
    ULListConstIterator();
    ULListConstIterator(const ULListConstIterator<T>& it);

    void clear();
    ULListConstIterator<T>& operator=(const ULListConstIterator<T>& it);

    operator bool() const;
    bool operator==(const ULListConstIterator<T>& it) const;
    bool operator!=(const ULListConstIterator<T>& it) const;

    ULListConstIterator<T>& operator++();
    ULListConstIterator<T> operator++(int);
    ULListConstIterator<T>& operator--();
    ULListConstIterator<T> operator--(int);
    void increment(); // non-operator synonym for operator++(), to help SWIG
    void decrement(); // non-operator synonym for operator--(), to help SWIG

    const T& operator*() const;
    const T& getData(); // non-operator synonym for operator*, to help SWIG

    bool isAtEnd() const;
    bool isAtBeginning() const;
    int getIndex() const;

    const ULList<T> *getList() const;

private:
    const ULList<T> *list;
    const ULListNode<T> *current;
};

template <class T>
ULListConstIterator<T>::ULListConstIterator()
{
    this->current = 0;
    this->list = 0;
}

template <class T>
ULListConstIterator<T>::ULListConstIterator(const ULListConstIterator<T>& it)
{
    *this = it;
}

template <class T>
void ULListConstIterator<T>::clear()
{
    this->current = 0;
    this->list = 0;
}

template <class T>
ULListConstIterator<T>& ULListConstIterator<T>::operator=(const ULListConstIterator<T>& it)
{
    if (this != &it) {
        this->current = it.current;
        this->list = it.list;
    }

    return *this;
}

template <class T>
bool ULListConstIterator<T>::isAtEnd() const
{
    return (this->current == 0);
}

template <class T>
bool ULListConstIterator<T>::isAtBeginning() const
{
    return (this->list == 0 || this->current == this->list->frontNode);
}

template <class T>
int ULListConstIterator<T>::getIndex() const
{
    if (this->list == 0 || this->current == 0) {
        return -1;
    }

    int count = -1;
    const ULListNode<T> *nodePtr;
    for (nodePtr = this->current; nodePtr != 0; nodePtr = nodePtr->previous) {
        count++;
    }

    return count;
}

template <class T>
const ULList<T> *ULListConstIterator<T>::getList() const
{
    return this->list;
}

template <class T>
ULListConstIterator<T>::operator bool() const
{
    return !(this->isAtEnd());
}

template <class T>
bool ULListConstIterator<T>::operator==(const ULListConstIterator<T>& it) const
{
    return this->current == it.current && this->list == it.list;
}

template <class T>
bool ULListConstIterator<T>::operator!=(const ULListConstIterator<T>& it) const
{
    return !(*this == it);
}

template <class T>
ULListConstIterator<T>& ULListConstIterator<T>::operator++()
{
    if (this->current != 0) {
        this->current = this->current->next;
    }

    return *this;
}

template <class T>
ULListConstIterator<T> ULListConstIterator<T>::operator++(int)
{
    ULListConstIterator<T> tmp = *this;
    ++(*this);
    return tmp;
}

template <class T>
ULListConstIterator<T>& ULListConstIterator<T>::operator--()
{
    UL_ASSERT(this->list != 0);

    if (this->current == this->list->frontNode) {
    } else if (this->current != 0) {
        this->current = this->current->previous;
    } else if (this->list != 0) {
        this->current = this->list->backNode;
    }

    return *this;
}

template <class T>
ULListConstIterator<T> ULListConstIterator<T>::operator--(int)
{
    ULListConstIterator<T> tmp = *this;
    --(*this);
    return tmp;
}

template <class T>
void ULListConstIterator<T>::increment()
{
    ++(*this);
}

template <class T>
void ULListConstIterator<T>::decrement()
{
    --(*this);
}

template <class T>
const T& ULListConstIterator<T>::operator*() const
{
    UL_ASSERT(this->current != 0);
    return this->current->data;
}

template <class T>
const T& ULListConstIterator<T>::getData()
{
    return *(*this);
}

template <class T>
class ULList
{
    friend class ULListIterator<T>;
    friend class ULListConstIterator<T>;
    UL_TEST_FRIEND;

public:
    ULList();
    ULList(const ULList<T>& list);
    ~ULList();

    void clear();
    ULList<T>& operator=(const ULList<T>& list);
    bool operator==(const ULList<T>& list) const;

    T& operator[](uluint32 n) const;
    T& getAtIndex(uluint32 n) const; // non-operator synonym for operator[], to help SWIG
    
    ULListConstIterator<T> find(const T& data) const;

    void erase(uluint32 n);
    void erase(ULListIterator<T>& it);
    void erase(ULListIterator<T>& start, ULListIterator<T>& stop);

    bool empty() const;
    uluint32 size() const;
    uluint32 length() const; // synonym for size

    void push_front(const T& data);
    void push_back(const T& data);
    void append(const T& data); // synonym for push_back
    void prepend(const T& data); // synonym for push_front
    void add(const T& data);
    void insert(ULListIterator<T>& it, const T& data);
    void insert(const T& data);

    void pop();
    T& top();

    ULListIterator<T> begin();
    ULListConstIterator<T> cbegin() const;
    ULListIterator<T> end();
    ULListConstIterator<T> cend() const;
    ULListIterator<T> back();
    ULListConstIterator<T> cback() const;

    // Node-based operations to allow rearrangement of the list
    // without lots of copying when T is large.
    ULListNode<T> *removeNode(ULListIterator<T>& it);
    ULListNode<T> *removeFrontNode();
    void insertNode(ULListIterator<T>& it, ULListNode<T> *node);

    void splice(ULList<T>& tail);
    void sort(int (*func)(T&, T&, void *), void *context);
    void mergeSort(int (*func)(T&, T&, void *), void *context);

private:
    uluint32 listLength;
    ULListNode<T> *frontNode;
    ULListNode<T> *backNode;

    void destroy();
};

template <class T>
ULList<T>::ULList()
{
    this->listLength = 0;
    this->frontNode = 0;
    this->backNode = 0;
}

template <class T>
ULList<T>::ULList(const ULList<T>& list)
{
    this->listLength = 0;
    this->frontNode = 0;
    this->backNode = 0;
    *this = list;
}

template <class T>
ULList<T>::~ULList()
{
    this->destroy();
}

template <class T>
void ULList<T>::destroy()
{
    ULListNode<T> *tmp;
    ULListNode<T> *current = this->frontNode;

    while (current != 0) {
        tmp = current;
        current = current->next;
        delete tmp;
    }

    this->listLength = 0;
}

template <class T>
ULList<T>& ULList<T>::operator=(const ULList<T>& list)
{
    if (this == &list) {
        return *this;
    }

    ULListNode<T> *current, *tmp;
    this->destroy();
    this->frontNode = this->backNode = 0;
    this->listLength = 0;
    for (current=list.frontNode; current != 0; current = current->next) {
        tmp = new ULListNode<T>(current->data); // sets next = previous = 0
        if (tmp == 0) {
            return *this;
        }

        tmp->previous = this->backNode;
        if (this->backNode == 0) {
            this->frontNode = tmp;
        } else {
            this->backNode->next = tmp;
        }
        this->backNode = tmp;
        (this->listLength)++;
    }

    return *this;
}

template <class T>
bool ULList<T>::operator==(const ULList<T>& other) const
{
    if (this == &other) {
        return true;
    }
    
    if (this->length() != other.length()) {
        return false;
    }
    
    ULListNode<T> *current = this->frontNode;
    ULListNode<T> *otherCurrent = other.frontNode;
    while (current != 0 && otherCurrent != 0) {
        if (!(current->data == otherCurrent->data)) {
            return false;
        }
        current = current->next;
        otherCurrent = otherCurrent->next;
    }

    return current == 0 && otherCurrent == 0;
}

template <class T>
T& ULList<T>::operator[](uluint32 n) const
{
    UL_ASSERT(n < this->listLength);
    ULListNode<T> *current = this->frontNode;
    for (uluint32 k=0; current != 0 && k < n; k++) {
        current = current->next;
    }
    
    UL_ASSERT(current != 0);
    return current->data;
}

template <class T>
T& ULList<T>::getAtIndex(uluint32 n) const
{
    UL_ASSERT(n < this->listLength);
    ULListNode<T> *current = this->frontNode;
    for (uluint32 k=0; current != 0 && k < n; k++) {
        current = current->next;
    }
    
    UL_ASSERT(current != 0);
    return current->data;
}

template <class T>
uluint32 ULList<T>::size() const
{
    return this->listLength;
}

template <class T>
uluint32 ULList<T>::length() const
{
    return this->listLength;
}

template <class T>
void ULList<T>::clear()
{
    this->destroy();
    this->frontNode = this->backNode = 0;
    this->listLength = 0;
}

template <class T>
ULListConstIterator<T> ULList<T>::find(const T& data) const
{
    ULListConstIterator<T> it = cbegin();
    while (!it.isAtEnd()) {
        if (data == *it) {
            break;
        }

        ++it;
    }

    return it;
}

template <class T>
bool ULList<T>::empty() const
{
    return this->frontNode == 0;
}

template <class T>
void ULList<T>::erase(uluint32 n)
{
    ULListNode<T> *current = this->frontNode;
    for (uluint32 k=0; current != 0 && k < n; k++) {
        current = current->next;
    }

    UL_ASSERT(current != 0);

    ULListIterator<T> it;
    it.list = this;
    it.current = current;
    erase(it);
}

template <class T>
void ULList<T>::erase(ULListIterator<T>& it)
{
    if (!it.isAtEnd()) {
        ULListNode<T> *node = removeNode(it);
        delete node;
    }
}

template <class T>
void ULList<T>::erase(ULListIterator<T>& start, ULListIterator<T>& stop)
{
    if (start.isAtBeginning()) {
        ULListIterator<T> it;
        while (!empty()) {
            it = begin();
            if (it.current == stop.current) {
                break;
            }
            erase(it);
        }
    } else {
        ULListIterator<T> previous = start;
        --previous;

        ULListIterator<T> it = start;
        while (!it.isAtEnd() && it.current != stop.current) {
            ULListNode<T> *node = removeNode(it);
            delete node;
            it = previous;
            ++it;
        }
    }
}

template <class T>
void ULList<T>::push_front(const T& data)
{
    ULListNode<T> *newNode = new ULListNode<T>;
    if (newNode == 0) {
        return;
    }

    newNode->data = data;
    newNode->next = this->frontNode;
    newNode->previous = 0;
    if (this->frontNode == 0) {
        this->backNode = newNode;
    } else {
        this->frontNode->previous = newNode;
    }
    this->frontNode = newNode;
    (this->listLength)++;
}

template <class T>
void ULList<T>::push_back(const T& data)
{
    ULListNode<T> *newNode = new ULListNode<T>;
    if (newNode == 0) {
        return;
    }

    newNode->data = data;
    newNode->next = 0;
    newNode->previous = this->backNode;

    if (this->backNode == 0) {
        this->frontNode = newNode;
    } else {
        this->backNode->next = newNode;
    }

    this->backNode = newNode;
    (this->listLength)++;
}

template <class T>
void ULList<T>::append(const T& data)
{
    this->push_back(data);
}

template <class T>
void ULList<T>::prepend(const T& data)
{
    this->push_front(data);
}

template <class T>
void ULList<T>::add(const T& data)
{
    ULListIterator<T> it = begin();
    while (!it.isAtEnd()) {
        if (data == *it) {
            break;
        }
        ++it;
    }

    if (it.isAtEnd()) {
        push_back(data);
    }
}

template <class T>
void ULList<T>::insert(ULListIterator<T>& it, const T& data)
{
    ULListNode<T> *node = new ULListNode<T>(data);
    if (node != 0) {
        this->insertNode(it, node);
    }
}

template <class T>
void ULList<T>::insert(const T& data)
{
    ULListIterator<T> it = begin();
    while (!it.isAtEnd() && *it < data) {
        ++it;
    }

    if (it.isAtEnd() || !(*it == data)) {
        insert(it, data);
    }
}

template <class T>
void ULList<T>::pop()
{
    if (!empty()) {
        ULListIterator<T> it = end();
        --it;
        erase(it);
    }
}

template <class T>
T& ULList<T>::top()
{
    UL_ASSERT(!empty());
    return this->backNode->data;
}

template <class T>
ULListIterator<T> ULList<T>::begin()
{
    ULListIterator<T> it;
    it.list = this;
    it.current = this->frontNode;
    return it;
}

template <class T>
ULListConstIterator<T> ULList<T>::cbegin() const
{
    ULListConstIterator<T> it;
    it.list = this;
    it.current = this->frontNode;
    return it;
}

template <class T>
ULListIterator<T> ULList<T>::end()
{
    ULListIterator<T> it;
    it.list = this;
    it.current = 0;
    return it;
}

template <class T>
ULListConstIterator<T> ULList<T>::cend() const
{
    ULListConstIterator<T> it;
    it.list = this;
    it.current = 0;
    return it;
}

template <class T>
ULListIterator<T> ULList<T>::back()
{
    ULListIterator<T> it;
    it.list = this;
    it.current = this->backNode;
    return it;
}

template <class T>
ULListConstIterator<T> ULList<T>::cback() const
{
    ULListConstIterator<T> it;
    it.list = this;
    it.current = this->backNode;
    return it;
}

template <class T>
ULListNode<T> *ULList<T>::removeNode(ULListIterator<T>& it)
{
    ULListNode<T> *node = it.current;

    UL_ASSERT(it.list == this);
    if (it.current != 0 && it.list == this) {
        if (it.current == this->frontNode) {
            this->frontNode = this->frontNode->next;
        }

        if (it.current == this->backNode) {
            this->backNode = this->backNode->previous;
        }

        if (it.current->next != 0) {
            it.current->next->previous = it.current->previous;
        }

        if (it.current->previous != 0) {
            it.current->previous->next = it.current->next;
        }

        // This enables you to iterate through a list and safely remove nodes
        // based on some criterion without corrupting the iterator in the process.
        it.current = it.current->next;
    }

    (this->listLength)--;
    return node;
}

template <class T>
ULListNode<T> *ULList<T>::removeFrontNode()
{
    ULListIterator<T> it = this->begin();
    return removeNode(it);
}

template <class T>
void ULList<T>::insertNode(ULListIterator<T>& it, ULListNode<T> *node)
{
    UL_ASSERT(node != 0);
    UL_ASSERT(it.list == this);
    if (node == 0 || it.list != this) {
        return;
    }

    node->next = it.current;
    if (it.current == 0) {
        node->previous = this->backNode;
        if (this->backNode != 0) {
            this->backNode->next = node;
        }
        this->backNode = node;
    } else {
        node->previous = it.current->previous;
        if (it.current->previous != 0) {
            it.current->previous->next = node;
        }

        it.current->previous = node;
    }

    if (it.current == this->frontNode) {
        this->frontNode = node;
    }

    this->listLength++;
    it.current = node;
}

template <class T>
void ULList<T>::splice(ULList<T>& tail)
{
    // Adjust this list.
    if (this->listLength == 0) {
        this->frontNode = tail.frontNode;
    } else {
        this->backNode->next = tail.frontNode;
    }

    if (tail.frontNode != 0) {
        tail.frontNode->previous = this->backNode;
    }

    this->listLength += tail.listLength;
    if (tail.listLength != 0) {
        this->backNode = tail.backNode;
    }

    // Remove spliced nodes from tail list so they don't get deleted when tail gets deleted.
    tail.listLength = 0;
    tail.frontNode = 0;
    tail.backNode = 0;
}

template <class T>
void ULList<T>::sort(int (*func)(T&, T&, void *), void *context)
{
    // this function implements a qsort algorithm with func() as the
    // comparison function
    
    // it relies on the internal structure of ULList, and tries to perform
    // an efficient sort. No objects are copied, just nodes rearranged and some
    // temporary ULList instances created on the stack
    
    if (this->frontNode == this->backNode) { // this is a fast way to see if size() is 0 or 1
        return; // a list of 0 or 1 elements is always sorted
    }
    
    // take the first node in the list as the pivot
    ULListNode<T> *pivot = this->removeFrontNode();
    
    ULList<T> lteqList, gtList; // our two sublists
    
    // iterate the list, removing elements and adding them to the sublists
    while (!empty()) {
        ULListNode<T> *cur = this->removeFrontNode();
        ULList<T>& list =
            func(cur->data, pivot->data, context) <= 0
            ? lteqList
            : gtList;

        ULListIterator<T> it = list.begin();
        list.insertNode(it, cur);
    }
    
    // the list is divided, now recurse!
    lteqList.sort(func, context);
    gtList.sort(func, context);
    
    // now we rebuild our own list from the pivot and the two others
    
    // add the <= list
    while (!lteqList.empty()) {
        ULListNode<T> *node = lteqList.removeFrontNode();
        ULListIterator<T> it = this->end();
        this->insertNode(it, node);
    }
    
    // add the pivot
    ULListIterator<T> it = this->end();
    this->insertNode(it, pivot);
    
    // add the > list
    while (!gtList.empty()) {
        ULListNode<T> *node = gtList.removeFrontNode();
        ULListIterator<T> it = this->end();
        this->insertNode(it, node);
    }
    
    // the list is now sorted, and there's no cleanup
}

template <class T>
void ULList<T>::mergeSort(int (*func)(T&, T&, void*), void *context)
{
    // this function implements an in-place mergesort using
    // func() as the comparison function

    // it relies on the internal structure of ULList and
    // avoids copying any objects

    if (this->frontNode == this->backNode) {
        return; // a list of 0 or 1 elements is always sorted
    }

    // first, split ourselves into two sublists
    // we go even/odd so we don't have to iterate twice
    ULList<T> evenList, oddList;
    for (bool odd = false; !this->empty(); odd = !odd) {
        ULListNode<T> *front = this->removeFrontNode();
        ULList<T>& list = odd ? oddList : evenList;
        ULListIterator<T> it = list.begin();
        list.insertNode(it, front);
    }

    // recurse on the sublists
    evenList.mergeSort(func, context);
    oddList.mergeSort(func, context);

    // now merge
    while (!evenList.empty() && !oddList.empty()) {
        ULList<T>& list =
            func(evenList.frontNode->data, oddList.frontNode->data, context) <= 0
              ? evenList
              : oddList;
        ULListIterator<T> it = this->end();
        this->insertNode(it, list.removeFrontNode());
    }

    // scoop up stragglers from whichever list has stuff left
    while (!evenList.empty()) {
        ULListIterator<T> it = this->end();
        this->insertNode(it, evenList.removeFrontNode());
    }
    while (!oddList.empty()) {
        ULListIterator<T> it = this->end();
        this->insertNode(it, oddList.removeFrontNode());
    }

    // all done!
}


template <class K, class V>
class ULHashTableIterator
{
    friend class ULHashTable<K,V>;
    UL_TEST_FRIEND;

public:
    ULHashTableIterator();
    ULHashTableIterator(const ULHashTableIterator& it);
    ~ULHashTableIterator();

    const ULHashTableIterator& operator=(const ULHashTableIterator& it);
    const ULPair<K,V>& operator*() const;
    void operator++();
    void operator++(int);
    operator bool() const;

    bool isAtEnd() const;
    uluint32 getHashIndex() const;

private:
    const ULHashTable<K,V> *hashTable;
    uluint32 hashIndex;
    ULListConstIterator< ULPair<K,V> > listIterator;
};

template <class K, class V>
ULHashTableIterator<K,V>::ULHashTableIterator()
    : hashTable(0), hashIndex(0)
{
}

template <class K, class V>
ULHashTableIterator<K,V>::ULHashTableIterator(const ULHashTableIterator& it)
    : hashTable(0), hashIndex(0)
{
    *this = it;
}

template <class K, class V>
ULHashTableIterator<K,V>::~ULHashTableIterator()
{
}

template <class K, class V>
const ULHashTableIterator<K,V>& ULHashTableIterator<K,V>::operator=(const ULHashTableIterator& it)
{
    if (&it != this) {
        this->hashTable = it.hashTable;
        this->hashIndex = it.hashIndex;
        this->listIterator = it.listIterator;
    }

    return *this;
}

template <class K, class V>
const ULPair<K,V>& ULHashTableIterator<K,V>::operator*() const
{
    UL_ASSERT(!isAtEnd());
    return *(this->listIterator);
}

template <class K, class V>
void ULHashTableIterator<K,V>::operator++()
{
    if (this->hashTable == 0) {
        return;
    }

    ++(this->listIterator);
    if (this->listIterator.isAtEnd()) {
        this->hashIndex++;
        this->listIterator = this->hashTable->table[this->hashIndex].cbegin();
        while (this->hashIndex < this->hashTable->tableSize && this->listIterator.isAtEnd()) {
            this->hashIndex++;
            this->listIterator = this->hashTable->table[this->hashIndex].cbegin();
        }
    }
}

template <class K, class V>
void ULHashTableIterator<K,V>::operator++(int)
{
    ++(*this);
}

template <class K, class V>
ULHashTableIterator<K,V>::operator bool() const
{
    return !(this->isAtEnd());
}

template <class K, class V>
bool ULHashTableIterator<K,V>::isAtEnd() const
{
    return this->hashTable == 0 || this->hashIndex >= this->hashTable->tableSize;
}

template <class K, class V>
uluint32 ULHashTableIterator<K,V>::getHashIndex() const
{
    return this->hashIndex;
}

template <class K, class V>
class ULHashTable
{
    friend class ULHashTableIterator<K,V>;
    UL_TEST_FRIEND;

public:
    ULHashTable();
    ULHashTable(uluint32 tableSize);
    ~ULHashTable();

    void clear();
    ULHashTable<K,V>& operator=(const ULHashTable<K,V>& table);

    uluint32 getTableSize() const;
    uluint32 getKeyCount() const;
    bool resize(uluint32 tableSize);

    void add(const K& key, const V& value);
    void add(const ULPair<K,V>& keyValuePair);

    bool find(const K& key, V& value) const;
    bool find(const K& key) const;

    ULHashTableIterator<K,V> end() const;
    ULHashTableIterator<K,V> begin() const;

    void getStats(double& avgListLength, uluint32& maxListLength);

private:
    ULList< ULPair<K,V> > *table;
    uluint32 tableSize;
    uluint32 keyCount;
};

template <class K, class V>
ULHashTable<K,V>::ULHashTable()
    : table(0), tableSize(0), keyCount(0)
{
}

template <class K, class V>
ULHashTable<K,V>::ULHashTable(uluint32 initialTableSize)
{
    this->table = 0;
    this->tableSize = 0;
    this->keyCount = 0;
    if (initialTableSize > 0) {
        this->table = new ULList< ULPair<K,V> >[initialTableSize];
        if (this->table != 0) {
            this->tableSize = initialTableSize;
        }
    }
}

template <class K, class V>
ULHashTable<K,V>::~ULHashTable()
{
    delete [] this->table;
}

template <class K, class V>
void ULHashTable<K,V>::clear()
{
    if (this->table != 0) {
        for (uluint32 k=0; k < this->tableSize; k++) {
            this->table[k].clear();
        }
        this->keyCount = 0;
    }
}

template <class K, class V>
ULHashTable<K,V>& ULHashTable<K,V>::operator=(const ULHashTable<K,V>& otherTable)
{
    delete [] this->table;
    this->table = 0;
    this->tableSize = 0;
    this->keyCount = 0;
    if (otherTable.tableSize > 0) {
        this->table = new ULList< ULPair<K,V> >[otherTable.tableSize];
    }

    if (this->table != 0) {
        this->tableSize = otherTable.tableSize;
        for (uluint32 k=0; k < this->tableSize; k++) {
            this->table[k] = otherTable.table[k];
        }
        this->keyCount = otherTable.keyCount;
    }

    return *this;
}

template <class K, class V>
uluint32 ULHashTable<K,V>::getTableSize() const
{
    return this->tableSize;
}

template <class K, class V>
uluint32 ULHashTable<K,V>::getKeyCount() const
{
    return this->keyCount;
}

template <class K, class V>
bool ULHashTable<K,V>::resize(uluint32 tableSize)
{
    if (tableSize == 0 || tableSize == this->tableSize) {
        return true;
    }

    ULList< ULPair<K,V> > *newTable = new ULList< ULPair<K,V> >[tableSize];
    if (newTable == 0) {
        return false;
    }

    if (this->tableSize != 0) {
        uluint32 hashValue;
        ULListConstIterator< ULPair<K,V> > it;
        this->keyCount = 0;
        for (uluint32 k=0; k < this->tableSize; k++) {
            for (it = this->table[k].cbegin(); it; ++it) {
                hashValue = (*it).getFirst().hash(tableSize);
                UL_ASSERT(hashValue < tableSize);
                newTable[hashValue].push_back(*it);
                this->keyCount++;
            }
        }
    }

    delete [] this->table;
    this->table = newTable;
    this->tableSize = tableSize;

    return true;
}

template <class K, class V>
void ULHashTable<K,V>::add(const K& key, const V& value)
{
    ULPair<K,V> keyValuePair;
    keyValuePair.setFirst(key);
    keyValuePair.setSecond(value);
    this->add(keyValuePair);
}

template <class K, class V>
void ULHashTable<K,V>::add(const ULPair<K,V>& keyValuePair)
{
    uluint32 hashValue = keyValuePair.getFirst().hash(this->tableSize);
    UL_ASSERT(hashValue < this->tableSize);
    if (hashValue < this->tableSize) {
        ULListIterator< ULPair<K,V> > it;
        for (it = this->table[hashValue].begin(); it; ++it) {
            if (keyValuePair.getFirst() == (*it).getFirst()) {
                (*it).setSecond(keyValuePair.getSecond());
                return;
            }
        }

        this->table[hashValue].push_back(keyValuePair);
        this->keyCount++;
    }
}

template <class K, class V>
bool ULHashTable<K,V>::find(const K& key, V& value) const
{
    uluint32 hashValue = key.hash(this->tableSize);
    UL_ASSERT(hashValue < this->tableSize);
    if (hashValue < this->tableSize) {
        ULListConstIterator< ULPair<K,V> > it;
        for (it = this->table[hashValue].cbegin(); it; ++it) {
            if (key == (*it).getFirst()) {
                value = (*it).getSecond();
                return true;
            }
        }
    }

    return false;
}

template <class K, class V>
bool ULHashTable<K,V>::find(const K& key) const
{
    uluint32 hashValue = key.hash(this->tableSize);
    UL_ASSERT(hashValue < this->tableSize);
    ULListConstIterator< ULPair<K,V> > it;
    for (it = this->table[hashValue].cbegin(); it; ++it) {
        if (key == (*it).getFirst()) {
            return true;
        }
    }

    return false;
}

template <class K, class V>
ULHashTableIterator<K,V> ULHashTable<K,V>::end() const
{
    ULHashTableIterator<K,V> it;
    it.hashTable = this;
    it.hashIndex = this->tableSize;
    return it;
}

template <class K, class V>
ULHashTableIterator<K,V> ULHashTable<K,V>::begin() const
{
    ULHashTableIterator<K,V> it;
    it.hashTable = this;
    it.hashIndex = 0;
    it.listIterator = this->table[it.hashIndex].cbegin();
    while (it.hashIndex < this->tableSize && it.listIterator.isAtEnd()) {
        it.hashIndex++;
        it.listIterator = this->table[it.hashIndex].cbegin();
    }

    return it;
}

template <class K, class V>
void ULHashTable<K,V>::getStats(double& avgChainLength, uluint32& maxChainLength)
{
    maxChainLength = 0;
    uluint32 chainLengthTotal = 0;
    uluint32 nNonemptyChains = 0;
    for (uluint32 k=0; k < this->tableSize; k++) {
        uluint32 chainLength = this->table[k].size();
        chainLengthTotal += chainLength;
        if (chainLength > maxChainLength) {
            maxChainLength = chainLength;
        }
        if (chainLength > 0) {
            nNonemptyChains++;
        }
    }

    if (nNonemptyChains > 0) {
        avgChainLength = double(chainLengthTotal) / double(nNonemptyChains);
    } else {
        avgChainLength = 0;
    }
}


template <class T>
class ULVector
{
    UL_TEST_FRIEND;

public:
    ULVector();
    ULVector(uluint32 newSize);
    ULVector(const ULVector<T>& v);
    ~ULVector();

    ULVector<T>& operator=(const ULVector<T>& v);
    void clear();
    T& operator[](uluint32 n);
    uluint32 size() const;
    void resize(uluint32 newSize);
    void append(const T& item);

private:
    T **vector;
    uluint32 vectorSize;
};

template <class T>
ULVector<T>::ULVector()
{
    this->vector = 0;
    this->vectorSize = 0;
}

template <class T>
ULVector<T>::ULVector(uluint32 newSize)
{
    this->vector = 0;
    this->vectorSize = 0;
    resize(newSize);
}

template <class T>
ULVector<T>::ULVector(const ULVector<T>& v)
{
    this->vector = 0;
    this->vectorSize = 0;
    *this = v;
}

template <class T>
ULVector<T>::~ULVector()
{
    this->clear();
}

template <class T>
void ULVector<T>::clear()
{
    if (this->vector != 0) {
        for (uluint32 k=0; k < this->vectorSize; k++) {
            delete this->vector[k];
        }
        delete [] this->vector;
    }

    this->vector = 0;
    this->vectorSize = 0;
}

template <class T>
ULVector<T>& ULVector<T>::operator=(const ULVector<T>& v)
{
    if (this == &v) {
        return *this;
    }

    this->clear();
    this->resize(v.size());
    if(this->vector != 0) {
        for (uluint32 k=0; k < this->vectorSize; k++) {
            (*this)[k] = v[k];
        }
    }

    return *this;
}

template <class T>
T& ULVector<T>::operator[](uluint32 n)
{
    UL_ASSERT(n < (1 << 30));
    if (n >= this->vectorSize) {
        uluint32 newSize = (this->vectorSize == 0 ? 16 : 2 * this->vectorSize);
        while (newSize <= n) {
            newSize *= 2;
        }
        UL_ASSERT(newSize <= (1 << 30));

        this->resize(newSize);
    }

    UL_ASSERT(n < this->vectorSize);
    if (this->vector[n] == 0) {
        this->vector[n] = new T;
    }

    return *(this->vector[n]);
}

template <class T>
uluint32 ULVector<T>::size() const
{
    return this->vectorSize;
}

template <class T>
void ULVector<T>::resize(uluint32 newSize)
{
    if (newSize != this->vectorSize) {
        if (newSize == 0) {
            clear();
        } else {
            typedef T *TPtr;
            T **newVector = new TPtr[newSize];
            if (newVector != 0) {
                uluint32 k;
                for (k=0; k < newSize && k < this->vectorSize; k++) {
                    newVector[k] = this->vector[k];
                    this->vector[k] = 0;
                }

                for ( ; k < newSize; k++) {
                    newVector[k] = 0;
                }

                this->clear();
                this->vector = newVector;
                this->vectorSize = newSize;
            }
        }
    }
}

template <class T>
void ULVector<T>::append(const T& item)
{
}

#endif