1 files changed, 233 insertions, 0 deletions
diff --git a/lib/omega/include/basic/List.h b/lib/omega/include/basic/List.h
new file mode 100644
index 0000000..28ab1d5
--- /dev/null
+++ b/lib/omega/include/basic/List.h
@@ -0,0 +1,233 @@
+#if ! defined _List_h
+#define _List_h 1
+
+/*
+ *  Linked lists with an interface like a bit of libg++'s SLList class
+ */
+#include <stdio.h>  // for NULL
+#include <basic/Iterator.h>
+#include <basic/Collection.h>
+#include <basic/Link.h>
+#include <assert.h>
+
+namespace omega {
+  
+template<class T> class List_Iterator;
+
+//
+// indexing of Lists starts at 1, index == 0 means not there
+//
+
+template<class T> class List : public Sequence<T> {
+public:
+    List(const List<T> &l)
+    { contents = l.contents ? new List_Element<T>(*l.contents) : 0; }
+    List() { contents = 0; }
+    virtual ~List() { delete contents; }
+
+    Iterator<T> *new_iterator();
+    const T &operator[](int) const;
+          T &operator[](int);
+
+         int index(const T &) const;
+    
+         int size() const;
+         int length() const { return size(); }
+	 bool empty() const { return size() == 0; }
+
+           T &front() const;
+
+// insertion/deletion on a list invalidates any iterators
+// that are on/after the element added/removed
+
+           T remove_front();	       
+
+        void prepend(const T &item);
+        void append(const T &item);
+        void ins_after(List_Iterator<T> i, const T &item);
+
+        void del_front();
+        void del_after(List_Iterator<T> i);
+        void clear();
+
+        void join(List<T> &consumed);
+
+private:
+    friend class List_Iterator<T>;
+    List_Element<T> **end()
+    {
+    List_Element<T> **e = &contents;
+    while (*e)
+	e = &((*e)->tail);
+    return e;
+    }
+
+    List_Element<T> *contents;
+};
+
+
+template<class T> class List_Iterator : public List_Element_Iterator<T> {
+public:
+    List_Iterator(List<T> &l);
+    List_Iterator(const List<T> &l);
+    List_Iterator();
+private:
+    List_Element<T> &element() { return *List_Element_Iterator<T>::i; } ;
+    friend class List<T>;
+};
+
+} // namespace
+
+#define instantiate_List(T)	template class List<T>; \
+				template class List_Iterator<T>; \
+				instantiate_Only_List_Element(T) \
+				instantiate_Sequence(T)
+
+namespace omega {
+  
+template<class T> List_Iterator<T>::List_Iterator(List<T> &l) 
+: List_Element_Iterator<T>(l.contents) {}
+
+template<class T> List_Iterator<T>::List_Iterator(const List<T> &l) 
+: List_Element_Iterator<T>(l.contents) {}
+
+template<class T> List_Iterator<T>::List_Iterator()
+: List_Element_Iterator<T>(0) {}
+
+template<class T> Iterator<T> *List<T>::new_iterator()
+{
+    return new List_Iterator<T>(*this);
+}
+
+template<class T> const T &List<T>::operator[](int i) const
+{
+    assert(i > 0 && "Subscript out of bounds");
+    List_Iterator<T> p(*this);
+
+    while(--i > 0 && p)
+	p++;
+
+    if (p)
+	return *p;
+    else
+	return *((T *)0);
+}
+
+template<class T>       T &List<T>::operator[](int i)
+{
+    assert(i > 0 && "Subscript out of bounds");
+    List_Iterator<T> p(*this);
+
+    while(--i > 0 && p)
+	p++;
+
+    if (p)
+	return *p;
+    else
+	return *((T *)0);
+}
+
+template<class T>      int List<T>::index(const T &item) const
+{
+    List_Iterator<T> p(*this);
+    int i = 1;
+
+    while(p && *p != item)
+    {
+	p++;
+	i++;
+    }
+
+    if (p)
+	return i;
+    else
+	return 0;
+}
+
+template<class T> int List<T>::size() const
+    {
+    int i = 0;
+    List_Element<T> * p = contents;
+    while (p)
+	{
+	p = p->tail;
+	i++;
+	}
+    return i;
+    }
+
+template<class T> T &List<T>::front() const
+    {
+    return contents->head;
+    }
+
+template<class T> T List<T>::remove_front()
+    {
+    List_Element<T> *frunt = contents;
+    contents = contents->tail;
+    T fruntT = frunt->head;
+    frunt->tail = 0;
+    delete frunt;
+    return fruntT;
+    }
+
+template<class T> void List<T>::prepend(const T &item)
+    {
+    contents = new List_Element<T>(item, contents);
+    }
+
+
+template<class T> void List<T>::append(const T &item)
+    {
+    *(end()) = new List_Element<T>(item, 0);
+    }
+
+template<class T> void List<T>::ins_after(List_Iterator<T> i,
+					     const T &item)
+    {
+#if ! defined NDEBUG
+    for (List_Element<T> *e = contents; e != &(i.element()); e=e->tail)
+	{
+	assert(e);
+	}
+#endif
+    i.element().tail = new List_Element<T>(item, i.element().tail);
+    }
+
+template<class T> void List<T>::del_front()
+    {
+    List_Element<T> *e = contents;
+    contents = contents->tail;
+    e->tail = 0;
+    delete e;
+    }
+
+template<class T> void List<T>::del_after(List_Iterator<T> i)
+    {
+#if ! defined NDEBUG
+    for (List_Element<T> *e0 = contents; e0 != &(i.element()); e0=e0->tail)
+	{
+	assert(e0);
+	}
+#endif
+    List_Element<T> *e = i.element().tail;
+    i.element().tail = e->tail;
+    e->tail = 0;
+    delete e;
+    }
+
+template<class T> void List<T>::clear()
+    {
+    delete contents;
+    contents = 0;
+    }
+
+template<class T> void List<T>::join(List<T> &consumed)
+    {
+    List_Element<T> *e = consumed.contents;
+    consumed.contents = 0;
+    *(end()) = e;
+    }
+
+} // namespace
+#endif