--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/deps/Platinum/ThirdParty/Neptune/Source/Core/NptList.h	Mon Jul 06 08:06:28 2009 -0700
@@ -0,0 +1,605 @@
+/*****************************************************************
+|
+|   Neptune - Lists
+|
+| Copyright (c) 2002-2008, Axiomatic Systems, LLC.
+| All rights reserved.
+|
+| Redistribution and use in source and binary forms, with or without
+| modification, are permitted provided that the following conditions are met:
+|     * Redistributions of source code must retain the above copyright
+|       notice, this list of conditions and the following disclaimer.
+|     * Redistributions in binary form must reproduce the above copyright
+|       notice, this list of conditions and the following disclaimer in the
+|       documentation and/or other materials provided with the distribution.
+|     * Neither the name of Axiomatic Systems nor the
+|       names of its contributors may be used to endorse or promote products
+|       derived from this software without specific prior written permission.
+|
+| THIS SOFTWARE IS PROVIDED BY AXIOMATIC SYSTEMS ''AS IS'' AND ANY
+| EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+| WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+| DISCLAIMED. IN NO EVENT SHALL AXIOMATIC SYSTEMS BE LIABLE FOR ANY
+| DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+| (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+| LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+| ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+| (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+| SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+|
+ ****************************************************************/
+
+#ifndef _NPT_LIST_H_
+#define _NPT_LIST_H_
+
+/*----------------------------------------------------------------------
+|   includes
++---------------------------------------------------------------------*/
+#include "NptResults.h"
+#include "NptTypes.h"
+#include "NptConstants.h"
+#include "NptCommon.h"
+
+/*----------------------------------------------------------------------
+|   constants
++---------------------------------------------------------------------*/
+const int NPT_ERROR_LIST_EMPTY              = NPT_ERROR_BASE_LIST - 0;
+const int NPT_ERROR_LIST_OPERATION_ABORTED  = NPT_ERROR_BASE_LIST - 1;
+const int NPT_ERROR_LIST_OPERATION_CONTINUE = NPT_ERROR_BASE_LIST - 2;
+
+/*----------------------------------------------------------------------
+|   NPT_List
++---------------------------------------------------------------------*/
+template <typename T> 
+class NPT_List 
+{
+protected:
+    class Item;
+
+public:
+    // types
+    typedef T Element;
+
+    class Iterator {
+    public:
+        Iterator() : m_Item(NULL) {}
+        explicit Iterator(Item* item) : m_Item(item) {}
+        Iterator(const Iterator& copy) : m_Item(copy.m_Item) {}
+        T&  operator*()  const { return m_Item->m_Data; }
+        T*  operator->() const { return &m_Item->m_Data;}
+        Iterator& operator++()  { // prefix
+            m_Item = m_Item->m_Next;
+            return (*this); 
+        }
+        Iterator operator++(int) { // postfix
+            Iterator saved_this = *this;
+            m_Item = m_Item->m_Next;
+            return saved_this;
+        }
+        Iterator& operator--() { // prefix
+            m_Item = m_Item->m_Prev;
+            return (*this); 
+        }
+        Iterator operator--(int) { // postfix
+            Iterator saved_this = *this;
+            m_Item = m_Item->m_Prev;
+            return saved_this;
+        }
+        operator bool() const {
+            return m_Item != NULL;
+        }
+        bool operator==(const Iterator& other) const {
+            return m_Item == other.m_Item;
+        }
+        bool operator!=(const Iterator& other) const {
+            return m_Item != other.m_Item;
+        }
+        void operator=(const Iterator& other) {
+            m_Item = other.m_Item;
+        }
+        void operator=(Item* item) {
+            m_Item = item;
+        }
+
+    private:
+        Item* m_Item;
+
+        // friends
+        friend class NPT_List<T>;
+    };
+
+    // methods
+                 NPT_List<T>();
+                 NPT_List<T>(const NPT_List<T>& list);
+                ~NPT_List<T>();
+    NPT_Result   Add(const T& data);
+    NPT_Result   Insert(const Iterator where, const T& data);
+    NPT_Result   Remove(const T& data, bool all=false);
+    NPT_Result   Erase(const Iterator position);
+    NPT_Result   PopHead(T& data);
+    bool         Contains(const T& data) const;
+    NPT_Result   Clear();
+    NPT_Result   Get(NPT_Ordinal index, T& data) const;
+    NPT_Result   Get(NPT_Ordinal index, T*& data) const;
+    NPT_Cardinal GetItemCount() const { return m_ItemCount; }
+    Iterator     GetFirstItem() const { return Iterator(m_Head); }
+    Iterator     GetLastItem() const  { return Iterator(m_Tail); }
+    Iterator     GetItem(NPT_Ordinal index) const;
+
+    // list manipulation
+    NPT_Result   Add(NPT_List<T>& list);
+    NPT_Result   Remove(const NPT_List<T>& list, bool all=false);
+
+    // item manipulation
+    NPT_Result   Add(Item& item);
+    NPT_Result   Detach(Item& item);
+    NPT_Result   Insert(const Iterator where, Item& item);
+
+    // list operations
+    // keep these template members defined here because MSV6 does not let
+    // us define them later
+    template <typename X> 
+    NPT_Result Apply(const X& function) const
+    {                          
+        Item* item = m_Head;
+        while (item) {
+            function(item->m_Data);
+            item = item->m_Next;
+        }
+
+        return NPT_SUCCESS;
+    }
+
+    template <typename X, typename P> 
+    NPT_Result ApplyUntil(const X& function, const P& predicate, bool* match = NULL) const
+    {                          
+        Item* item = m_Head;
+        while (item) {
+            NPT_Result return_value;
+            if (predicate(function(item->m_Data), return_value)) {
+                if (match) *match = true;
+                return return_value;
+            }
+            item = item->m_Next;
+        }
+        
+        if (match) *match = false;
+        return NPT_SUCCESS;
+    }
+
+    template <typename P> 
+    Iterator Find(const P& predicate, NPT_Ordinal n=0) const
+    {
+        Item* item = m_Head;
+        while (item) {
+            if (predicate(item->m_Data)) {
+                if (n == 0) {
+                    return Iterator(item);
+                }
+                --n;
+            }
+            item = item->m_Next;
+        }
+
+        return Iterator(NULL);
+    }
+
+    // operators
+    void operator=(const NPT_List<T>& other);
+    bool operator==(const NPT_List<T>& other) const;
+    bool operator!=(const NPT_List<T>& other) const;
+
+protected:
+    // types
+    class Item 
+    {
+    public:
+        // methods
+        Item(const T& data) : m_Next(0), m_Prev(0), m_Data(data) {}
+
+        // members
+        Item* m_Next;
+        Item* m_Prev;
+        T     m_Data;
+
+        // friends
+        //friend class NPT_List<T>;
+        //friend class NPT_List<T>::Iterator;
+    };
+
+    // members
+    NPT_Cardinal m_ItemCount;
+    Item*        m_Head;
+    Item*        m_Tail;
+};
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::NPT_List
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_List<T>::NPT_List() : m_ItemCount(0), m_Head(0), m_Tail(0) 
+{
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::NPT_List
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_List<T>::NPT_List(const NPT_List<T>& list) : m_ItemCount(0), m_Head(0), m_Tail(0) 
+{
+    *this = list;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::~NPT_List<T>
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_List<T>::~NPT_List()
+{
+    Clear();
+}
+ 
+/*----------------------------------------------------------------------
+|   NPT_List<T>::operator=
++---------------------------------------------------------------------*/
+template <typename T>
+void
+NPT_List<T>::operator=(const NPT_List<T>& list)
+{
+    // cleanup
+    Clear();
+
+    // copy the new list
+    Item* item = list.m_Head;
+    while (item) {
+        Add(item->m_Data);
+        item = item->m_Next;
+    }
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::operator==
++---------------------------------------------------------------------*/
+template <typename T>
+bool
+NPT_List<T>::operator==(const NPT_List<T>& other) const
+{
+    // quick test
+    if (m_ItemCount != other.m_ItemCount) return false;
+
+    // compare all elements one by one
+    Item* our_item = m_Head;
+    Item* their_item = other.m_Head;
+    while (our_item && their_item) {
+        if (our_item->m_Data != their_item->m_Data) return false;
+        our_item   = our_item->m_Next;
+        their_item = their_item->m_Next;
+    }
+    
+    return our_item == NULL && their_item == NULL;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::operator!=
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+bool
+NPT_List<T>::operator!=(const NPT_List<T>& other) const
+{
+    return !(*this == other);
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Clear
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Clear()
+{
+    // delete all items
+    Item* item = m_Head;
+    while (item) {
+        Item* next = item->m_Next;
+        delete item;
+        item = next;
+    }
+
+    m_ItemCount = 0;
+    m_Head      = NULL;
+    m_Tail      = NULL;
+
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Add
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Add(Item& item)
+{
+    // add element at the tail
+    if (m_Tail) {
+        item.m_Prev = m_Tail;
+        item.m_Next = NULL;
+        m_Tail->m_Next = &item;
+        m_Tail = &item;
+    } else {
+        m_Head = &item;
+        m_Tail = &item;
+        item.m_Next = NULL;
+        item.m_Prev = NULL;
+    }
+
+    // one more item in the list now
+    ++m_ItemCount;
+ 
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Add
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Add(NPT_List<T>& list)
+{
+    // copy the new list
+    Item* item = list.m_Head;
+    while (item) {
+        Add(item->m_Data);
+        item = item->m_Next;
+    }
+
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Add
++---------------------------------------------------------------------*/
+template <typename T>
+inline
+NPT_Result
+NPT_List<T>::Add(const T& data)
+{
+    return Add(*new Item(data));
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::GetItem
++---------------------------------------------------------------------*/
+template <typename T>
+typename NPT_List<T>::Iterator
+NPT_List<T>::GetItem(NPT_Ordinal n) const
+{
+    Iterator result;
+    if (n >= m_ItemCount) return result;
+    
+    result = m_Head;
+    for (unsigned int i=0; i<n; i++) {
+        ++result;
+    }
+
+    return result;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Insert
++---------------------------------------------------------------------*/
+template <typename T>
+inline NPT_Result
+NPT_List<T>::Insert(Iterator where, const T&data)
+{
+    return Insert(where, *new Item(data));
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Insert
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Insert(Iterator where, Item& item)
+{
+    // insert the item in the list
+    Item* position = where.m_Item;
+    if (position) {
+        // insert at position
+        item.m_Next = position;
+        item.m_Prev = position->m_Prev;
+        position->m_Prev = &item;
+        if (item.m_Prev) {
+            item.m_Prev->m_Next = &item;
+        } else {
+            // this is the new head
+            m_Head = &item;
+        }
+
+        // one more item in the list now
+        ++m_ItemCount;
+    } else {
+        // insert at tail
+        return Add(item);
+    }
+ 
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Erase
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Erase(Iterator position) 
+{
+    if (!position) return NPT_ERROR_NO_SUCH_ITEM;
+    Detach(*position.m_Item);
+    delete position.m_Item;
+
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Remove
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Remove(const T& data, bool all)
+{
+    Item* item = m_Head;
+    NPT_Cardinal matches = 0;
+
+    while (item) {
+        Item* next = item->m_Next;
+        if (item->m_Data == data) {
+            // we found a match
+            ++matches;
+
+            // detach item
+            Detach(*item);
+            
+            // destroy the item
+            delete item;
+
+            if (!all) return NPT_SUCCESS;
+        }
+        item = next;
+    }
+ 
+    return matches?NPT_SUCCESS:NPT_ERROR_NO_SUCH_ITEM;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Remove
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Remove(const NPT_List<T>& list, bool all)
+{
+    Item* item = list.m_Head;
+    while (item) {
+        Remove(item->m_Data, all);
+        item = item->m_Next;
+    }
+
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Detach
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Detach(Item& item)
+{
+    // remove item
+    if (item.m_Prev) {
+        // item is not the head
+        if (item.m_Next) {
+            // item is not the tail
+            item.m_Next->m_Prev = item.m_Prev;
+            item.m_Prev->m_Next = item.m_Next;
+        } else {
+            // item is the tail
+            m_Tail = item.m_Prev;
+            m_Tail->m_Next = NULL;
+        }
+    } else {
+        // item is the head
+        m_Head = item.m_Next;
+        if (m_Head) {
+            // item is not the tail
+            m_Head->m_Prev = NULL;
+        } else {
+            // item is also the tail
+            m_Tail = NULL;
+        }
+    }
+
+    // one less item in the list now
+    --m_ItemCount;
+
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Get
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Get(NPT_Ordinal index, T& data) const
+{
+    T* data_pointer;
+    NPT_CHECK(Get(index, data_pointer));
+    data = *data_pointer;
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Get
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::Get(NPT_Ordinal index, T*& data) const
+{
+    Item* item = m_Head;
+
+    if (index < m_ItemCount) {
+        while (index--) item = item->m_Next;
+        data = &item->m_Data;
+        return NPT_SUCCESS;
+    } else {
+        data = NULL;
+        return NPT_ERROR_NO_SUCH_ITEM;
+    }
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::PopHead
++---------------------------------------------------------------------*/
+template <typename T>
+NPT_Result
+NPT_List<T>::PopHead(T& data)
+{
+    // check that we have an element
+    if (m_Head == NULL) return NPT_ERROR_LIST_EMPTY;
+
+    // copy the head item's data
+    data = m_Head->m_Data;
+
+    // discard the head item
+    Item* head = m_Head;
+    m_Head = m_Head->m_Next;
+    if (m_Head) {
+        m_Head->m_Prev = NULL;
+    } else {
+        m_Tail = NULL;
+    }
+    delete head;
+
+    // update the count
+    --m_ItemCount;
+
+    return NPT_SUCCESS;
+}
+
+/*----------------------------------------------------------------------
+|   NPT_List<T>::Contains
++---------------------------------------------------------------------*/
+template <typename T>
+bool
+NPT_List<T>::Contains(const T& data) const
+{
+    Item* item = m_Head;
+    while (item) {
+        if (item->m_Data == data) return true;
+        item = item->m_Next;
+    }
+
+    return false;
+}
+
+#endif // _NPT_LIST_H_