1 files changed, 176 insertions, 0 deletions

diff --git a/src/list.h b/src/list.h
new file mode 100644
index 0000000..ec63496
--- /dev/null
+++ b/src/list.h
@@ -0,0 +1,176 @@
+#ifndef LIST_H
+#define LIST_H
+
+#include <memory>
+#include "bu/exceptionbase.h"
+
+namespace Bu
+{
+        template<typename value>
+        struct ListLink
+        {
+                value *pValue;
+                ListLink *pNext;
+                ListLink *pPrev;
+        };
+        template<typename value, typename valuealloc=std::allocator<value>, typename linkalloc=std::allocator<struct ListLink<value> > >
+        class List
+        {
+        private:
+                typedef struct ListLink<value> Link;
+                typedef class List<value, valuealloc, linkalloc> MyType;
+
+        public:
+                List() :
+                        pFirst( NULL ),
+                        pLast( NULL )
+                {
+                }
+
+                void append( value v )
+                {
+                        Link *pNew = la.allocate( sizeof( Link ) );
+                        pNew->pValue = va.allocate( sizeof( value ) );
+                        va.construct( pNew->pValue, v );
+                        if( pFirst == NULL )
+                        {
+                                // Empty list
+                                pFirst = pLast = pNew;
+                                pNew->pNext = pNew->pPrev = NULL;
+                        }
+                        else
+                        {
+                                pNew->pNext = NULL;
+                                pNew->pPrev = pLast;
+                                pLast->pNext = pNew;
+                                pLast = pNew;
+                        }
+                }
+
+                void prepend( value v )
+                {
+                        Link *pNew = la.allocate( sizeof( Link ) );
+                        pNew->pValue = va.allocate( sizeof( value ) );
+                        va.construct( pNew->pValue, v );
+                        if( pFirst == NULL )
+                        {
+                                // Empty list
+                                pFirst = pLast = pNew;
+                                pNew->pNext = pNew->pPrev = NULL;
+                        }
+                        else
+                        {
+                                pNew->pNext = pFirst;
+                                pNew->pPrev = NULL;
+                                pFirst->pPrev = pNew;
+                                pFirst = pNew;
+                        }
+                }
+
+                typedef struct iterator
+                {
+                        friend class List<value, valuealloc, linkalloc>;
+                private:
+                        Link *pLink;
+                        iterator() :
+                                pLink( NULL )
+                        {
+                        }
+
+                        iterator( Link *pLink ) :
+                                pLink( pLink )
+                        {
+                        }
+
+                public:
+                        bool operator==( const iterator &oth )
+                        {
+                                return ( pLink == oth.pLink );
+                        }
+
+                        bool operator==( const Link *pOth )
+                        {
+                                return ( pLink == pOth );
+                        }
+
+                        bool operator!=( const iterator &oth )
+                        {
+                                return ( pLink != oth.pLink );
+                        }
+
+                        bool operator!=( const Link *pOth )
+                        {
+                                return ( pLink != pOth );
+                        }
+
+                        value &operator*()
+                        {
+                                return *(pLink->pValue);
+                        }
+
+                        value *operator->()
+                        {
+                                return pLink->pValue();
+                        }
+
+                        iterator operator++()
+                        {
+                                if( pLink != NULL )
+                                        pLink = pLink->pNext;
+                                return *this;
+                        }
+
+                        iterator operator--()
+                        {
+                                if( pLink != NULL )
+                                        pLink = pLink->pPrev;
+                                return *this;
+                        }
+                        
+                        iterator operator++( int )
+                        {
+                                if( pLink != NULL )
+                                        pLink = pLink->pNext;
+                                return *this;
+                        }
+
+                        iterator operator--( int )
+                        {
+                                if( pLink != NULL )
+                                        pLink = pLink->pPrev;
+                                return *this;
+                        }
+
+                        iterator operator=( const iterator &oth )
+                        {
+                                pLink = oth.pLink;
+                        }
+                };
+
+                iterator begin()
+                {
+                        return iterator( pFirst );
+                }
+
+                const Link *end()
+                {
+                        return NULL;
+                }
+
+                int getSize()
+                {
+                        int j = 0;
+                        for( Link *pCur = pFirst; pCur; pCur = pCur->pNext )
+                                j++;
+                        return j;
+                }
+                
+        private:
+                Link *pFirst;
+                Link *pLast;
+                linkalloc la;
+                valuealloc va;
+        };
+}
+
+#endif