summaryrefslogtreecommitdiff
path: root/lib/omega/include/basic
diff options
context:
space:
mode:
Diffstat (limited to 'lib/omega/include/basic')
-rw-r--r--lib/omega/include/basic/Bag.h405
-rwxr-xr-xlib/omega/include/basic/BoolSet.h641
-rw-r--r--lib/omega/include/basic/Collection.h43
-rw-r--r--lib/omega/include/basic/Collections.h12
-rw-r--r--lib/omega/include/basic/ConstString.h57
-rw-r--r--lib/omega/include/basic/DynamicArray.h318
-rw-r--r--lib/omega/include/basic/Iterator.h129
-rw-r--r--lib/omega/include/basic/Link.h97
-rw-r--r--lib/omega/include/basic/List.h233
-rw-r--r--lib/omega/include/basic/Map.h127
-rw-r--r--lib/omega/include/basic/Section.h138
-rw-r--r--lib/omega/include/basic/SimpleList.h194
-rw-r--r--lib/omega/include/basic/Tuple.h336
-rw-r--r--lib/omega/include/basic/omega_error.h14
-rw-r--r--lib/omega/include/basic/util.h263
15 files changed, 3007 insertions, 0 deletions
diff --git a/lib/omega/include/basic/Bag.h b/lib/omega/include/basic/Bag.h
new file mode 100644
index 0000000..a3d07a0
--- /dev/null
+++ b/lib/omega/include/basic/Bag.h
@@ -0,0 +1,405 @@
+#if ! defined _Bag_h
+#define _Bag_h 1
+
+#include <stdio.h>
+#include <basic/Iterator.h>
+#include <basic/Collection.h>
+#include <basic/Link.h>
+#include <assert.h>
+
+namespace omega {
+
+template<class T> class Bag : public Collection<T> {
+public:
+virtual ~Bag();
+ Bag();
+ Bag(const Bag<T>&);
+ Bag & operator=(const Bag<T>&);
+ //! add elements in b
+ virtual void operator |= (const Bag<T> & b);
+ Iterator<T> *new_iterator();
+ bool empty() const;
+ void remove(T);
+ virtual void insert(T);
+ void clear();
+ virtual bool contains(T) const;
+ int size() const;
+ T extract();
+// protected: breaks g++ 261
+ List_Element<T>* contents;
+};
+
+
+template<class T> class Ordered_Bag : public Bag<T> {
+public:
+ Ordered_Bag();
+ Ordered_Bag(const Ordered_Bag<T>& B) : Bag<T>(B) {}
+ void insert(T);
+ //! add elements in b
+ virtual void operator |= (const Ordered_Bag<T> & b);
+ //! add elements in b
+ void operator |= (const Bag<T> & b);
+ bool contains(T) const;
+ bool operator == (const Ordered_Bag<T>&) const;
+ bool operator != (const Ordered_Bag<T>&) const;
+ bool operator < (const Ordered_Bag<T>&) const;
+};
+
+template <class T> class Set : public Ordered_Bag <T> {
+public:
+ Set();
+ Set(T);
+ Set(const Set<T>& S) : Ordered_Bag<T>(S) {}
+
+ bool contains (const Set<T>& b) const;
+ bool contains (T t) const { return Ordered_Bag<T>::contains(t); }
+ // the above makes "standard" C++ happy
+
+ //! add elements in b
+ virtual void operator |= (const Set<T> & b);
+ //! add elements in b
+ void operator |= (const Ordered_Bag<T> & b);
+ //! add elements in b
+ void operator |= (const Bag<T> & b);
+
+ //! delete items also in b
+ void operator -= (const Set<T> & b);
+ //! delete items not in b
+ void operator &= (const Set<T> & b);
+ //! check for elements in common
+ bool operator & (const Set<T> &) const;
+};
+
+} // namespace
+
+#define instantiate_Bag(T) template class Bag<T>; \
+ instantiate_List_Element(T);
+#define instantiate_Ordered_Bag(T) template class Ordered_Bag<T>; \
+ instantiate_Bag(T)
+#define instantiate_Set(T) template class Set<T>; \
+ instantiate_Ordered_Bag(T)
+
+
+namespace omega {
+
+template<class T> Bag<T>::Bag() {
+ contents = new List_Element <T>;
+ contents->tail = 0;
+ }
+template<class T> Bag<T>::~Bag() {
+ delete contents;
+ }
+
+template<class T> Ordered_Bag<T>::Ordered_Bag() {}
+
+template<class T> Set<T>::Set() {}
+
+template<class T> Bag<T>::Bag(const Bag<T> &L) {
+ contents = new List_Element<T>(*L.contents);
+ }
+
+template<class T> Bag<T> & Bag<T>::operator=(const Bag<T> &L) {
+ if (this != &L) {
+ delete contents;
+ contents = new List_Element<T>(*L.contents);
+ }
+ return *this;
+ }
+
+
+
+template<class T> Set<T>::Set(T e) {
+ assert(this->contents);
+ this->contents->tail = new List_Element<T>(e, 0);
+ }
+
+
+/****************************************************************
+ * *
+ * Misc. simple Collection operations *
+ * *
+ ****************************************************************/
+
+template<class T> bool Bag<T>::empty() const {
+ return contents->tail == 0;
+ }
+
+template<class T> Iterator<T> *Bag<T>::new_iterator()
+ {
+ return new List_Element_Iterator<T>(contents->tail);
+ }
+
+
+template<class T> void Bag<T>::clear() {
+ if (contents->tail) delete contents->tail;
+ contents->tail = 0;
+ }
+
+template<class T> int Bag<T>::size() const {
+ int i = 0;
+ List_Element<T> * p = contents->tail;
+ while (p) {
+ p = p->tail;
+ i++;
+ };
+ return i;
+ }
+
+
+/****************************************************************
+ * *
+ * Collection/Element operations (e.g. insert, contains) *
+ * *
+ ****************************************************************/
+
+template<class T> void Bag<T>::remove(T e) {
+ List_Element<T> * p = contents;
+ while (p->tail && p->tail->head != e) p = p->tail;
+ if (p->tail && p->tail->head == e) {
+ List_Element<T> * q = p->tail;
+ p->tail = q->tail;
+ q->tail = 0;
+ delete q;
+ }
+ }
+
+template<class T> T Bag<T>::extract() {
+ List_Element<T> * p = contents->tail;
+ T e = p->head;
+ contents->tail = p->tail;
+ p->tail = 0;
+ delete p;
+ return e;
+ }
+
+
+template<class T> void Bag<T>::insert(T e) {
+ List_Element<T> * q = new List_Element<T>(e,contents->tail);
+ contents->tail = q;
+ }
+
+template<class T> void Ordered_Bag<T>::insert(T e) {
+ List_Element<T> * p = this->contents;
+ while (p->tail && p->tail->head < e) p = p->tail;
+ if (!p->tail || p->tail->head != e) {
+ List_Element<T> * q = new List_Element<T>(e,p->tail);
+ p->tail = q;
+ }
+ }
+
+
+template<class T> bool Bag<T>::contains(T e) const {
+ List_Element<T> * p = contents;
+ while (p->tail && p->tail->head != e) p = p->tail;
+ return (p->tail && p->tail->head == e);
+ }
+
+template<class T> bool Ordered_Bag<T>::contains(T e) const {
+ List_Element<T> * p = this->contents;
+ while (p->tail && p->tail->head < e) p = p->tail;
+ return (p->tail && p->tail->head == e);
+ }
+
+
+template<class T> bool Set<T>::contains (const Set<T>& b) const {
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents;
+ do {
+ /* consume matched elements in p and q */
+ p = p->tail;
+ q = q->tail;
+ if (!q) return 1; /* no more elements to match */
+ if (!p) return 0; /* nothing left in p to match with */
+ if (q->head < p->head) {
+ /* nothing smaller than
+ p->head left in p, so q->head
+ can't be matched */
+ return 0;
+ };
+ while (p && p->head < q->head) {
+ /* toss away some elements from p */
+ p = p->tail;
+ }
+ if (!p || q->head < p->head) return 0;
+ } while (q);
+
+ return 1;
+ }
+
+
+
+/****************************************************************
+ * *
+ * Collection/Collection operations (e.g. |=) *
+ * *
+ ****************************************************************/
+
+template<class T> void Bag<T>::operator |= (const Bag<T> & b) {
+ assert(this != &b);
+ List_Element<T> * q = b.contents->tail;
+
+ while (q) {
+ List_Element<T> * r = new List_Element<T>(q->head,contents->tail);
+ contents->tail = r;
+ q = q->tail;
+ }
+ }
+
+template<class T> void Ordered_Bag<T>::operator |= (const Ordered_Bag<T> & b) {
+ if (this == &b) return;
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents->tail;
+
+ while (q) {
+ while (p->tail && p->tail->head < q->head) p = p->tail;
+ List_Element<T> * r = new List_Element<T>(q->head,p->tail);
+ p->tail = r;
+ q = q->tail;
+ }
+ }
+
+template<class T> void Ordered_Bag<T>::operator |= (const Bag<T> & b) {
+ Ordered_Bag<T> tmp;
+ for (List_Element<T> *p = b.contents; p; p=p->tail) {
+ tmp.insert(p->head);
+ }
+ *this |= tmp;
+}
+
+template<class T> void Set<T>::operator |= (const Set<T> & b) {
+ if (this == &b) return;
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents->tail;
+
+ while (q) {
+ while (p->tail && p->tail->head < q->head) p = p->tail;
+ if (!p->tail || p->tail->head != q->head) {
+ List_Element<T> * r = new List_Element<T>(q->head,p->tail);
+ p->tail = r;
+ }
+ q = q->tail;
+ }
+ }
+
+template<class T> void Set<T>::operator |= (const Ordered_Bag<T> & b) {
+ Set<T> tmp;
+ for (List_Element<T> *p = b.contents; p; p=p->tail) {
+ tmp.insert(p->head);
+ }
+ *this |= tmp;
+}
+
+template<class T> void Set<T>::operator |= (const Bag<T> & b) {
+ Set<T> tmp;
+ for (List_Element<T> *p = b.contents; p; p=p->tail) {
+ tmp.insert(p->head);
+ }
+ *this |= tmp;
+}
+
+
+
+// delete items also in b
+template<class T> void Set<T>::operator -= (const Set<T> & b) {
+ if (this == &b) {
+ this->clear();
+ return;
+ }
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents->tail;
+
+ while (q) {
+ while (p->tail && p->tail->head < q->head) p = p->tail;
+ if (p->tail && p->tail->head == q->head) {
+ List_Element<T> * r = p->tail;
+ p->tail = r->tail;
+ r->tail = 0;
+ delete r;
+ }
+ q = q->tail;
+ }
+ }
+
+
+// delete items not in b
+template<class T> void Set<T>::operator &= (const Set<T> & b)
+ {
+ if (this == &b) return;
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents->tail;
+
+ while (q) {
+ while (p->tail && p->tail->head < q->head) {
+ List_Element<T> * r = p->tail;
+ p->tail = r->tail;
+ r->tail = 0;
+ delete r;
+ };
+ if (p->tail && p->tail->head == q->head) {
+ /* allow p->tail->head into the result */
+ p = p->tail;
+ }
+ /* q->head has matched anything it is going to match */
+ q = q->tail;
+ }
+ if (p->tail) {
+ delete p->tail;
+ p->tail = 0;
+ };
+
+ }
+
+
+template<class T> bool Set<T>::operator & (const Set<T>& b) const {
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents;
+ do {
+ p = p->tail;
+ q = q->tail;
+ while (p && q && p->head != q->head) {
+ while (p && p->head < q->head) p = p->tail;
+ while (p && q && q->head < p->head) q = q->tail;
+ };
+ if (p && q && p->head == q->head) return 1;
+ } while (p && q);
+
+ return 0;
+ }
+
+
+template<class T> bool Ordered_Bag<T>::operator == (const Ordered_Bag<T>& b) const {
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents;
+ while (1) {
+ p = p->tail;
+ q = q->tail;
+ if (!p && !q) return 1;
+ if (!p || !q) return 0;
+ if (p->head != q->head) return 0;
+ };
+
+ }
+
+template<class T> bool Ordered_Bag<T>::operator != (const Ordered_Bag<T>& b) const {
+ return !(*this == b);
+ }
+
+template<class T> bool Ordered_Bag<T>::operator < (const Ordered_Bag<T>& b) const {
+ List_Element<T> * p = this->contents;
+ List_Element<T> * q = b.contents;
+ while (1) {
+ p = p->tail;
+ q = q->tail;
+ if (!p && !q) return 0;
+ if (!p) return 1;
+ if (!q) return 0;
+ if (p->head < q->head) return 1;
+ if (q->head < p->head) return 0;
+ };
+
+ return 1;
+ }
+
+} // namespace
+
+#endif
diff --git a/lib/omega/include/basic/BoolSet.h b/lib/omega/include/basic/BoolSet.h
new file mode 100755
index 0000000..a78af2e
--- /dev/null
+++ b/lib/omega/include/basic/BoolSet.h
@@ -0,0 +1,641 @@
+/*****************************************************************************
+ Copyright (C) 2009-2011 Chun Chen
+ All Rights Reserved.
+
+ Purpose:
+ BoolSet class, used as a set of integers from 0..n-1 where n is a very
+ small integer.
+
+ Notes:
+ Set operands of binary operations can be of different sizes, missing
+ elements are treated as false.
+
+ History:
+ 03/30/09 Created by Chun Chen.
+ 03/26/11 iterator added, -chun
+*****************************************************************************/
+
+#ifndef _BOOLSET_H
+#define _BOOLSET_H
+
+#include <vector>
+#include <iostream>
+#include <assert.h>
+#include <stdexcept>
+#include <iterator>
+
+namespace omega {
+
+ //! BoolSet class, used as a set of integers from 0 to n-1 where n is a very small integer.
+template<typename T = unsigned int>
+class BoolSet {
+protected:
+ unsigned int size_;
+ std::vector<T> set_;
+
+public:
+ BoolSet(unsigned int size = 0);
+ ~BoolSet() {}
+
+ void set(unsigned int);
+ void unset(unsigned int);
+ void set_all();
+ void unset_all();
+ bool get(unsigned int) const;
+ unsigned int size() const {return size_;}
+ unsigned int num_elem() const;
+ bool imply(const BoolSet<T> &) const;
+ bool empty() const;
+ void dump() const;
+
+ BoolSet<T> &operator|=(const BoolSet<T> &);
+ BoolSet<T> &operator&=(const BoolSet<T> &);
+ BoolSet<T> &operator-=(const BoolSet<T> &);
+
+ //! union
+ template<typename TT> friend BoolSet<TT> operator|(const BoolSet<TT> &, const BoolSet<TT> &);
+ //! intersection
+ template<typename TT> friend BoolSet<TT> operator&(const BoolSet<TT> &, const BoolSet<TT> &);
+ //! difference
+ template<typename TT> friend BoolSet<TT> operator-(const BoolSet<TT> &, const BoolSet<TT> &);
+ //! complement
+ template<typename TT> friend BoolSet<TT> operator~(const BoolSet<TT> &);
+ template<typename TT> friend bool operator==(const BoolSet<TT> &, const BoolSet<TT> &);
+ template<typename TT> friend bool operator!=(const BoolSet<TT> &, const BoolSet<TT> &);
+ template<typename TT> friend std::ostream& operator<<(std::ostream &, const BoolSet<TT> &);
+ template<typename TT> friend bool operator<(const BoolSet<TT> &, const BoolSet<TT> &);
+
+public:
+ class iterator;
+ class const_iterator;
+ iterator begin();
+ iterator end();
+ const_iterator begin() const;
+ const_iterator end() const;
+};
+
+
+template<typename T>
+BoolSet<T>::BoolSet(unsigned int size) {
+ assert(size >= 0);
+ size_ = size;
+ unsigned int n = size / (sizeof(T)*8);
+ unsigned int r = size % (sizeof(T)*8);
+ if (r != 0)
+ n++;
+ set_ = std::vector<T>(n, static_cast<T>(0));
+}
+
+
+template<typename T>
+void BoolSet<T>::set(unsigned int i) {
+ assert(i < size_ && i >= 0);
+ unsigned int n = i / (sizeof(T)*8);
+ unsigned int r = i % (sizeof(T)*8);
+
+ T t = static_cast<T>(1) << r;
+ set_[n] |= t;
+}
+
+
+template<typename T>
+void BoolSet<T>::unset(unsigned int i) {
+ assert(i < size_ && i >= 0);
+ unsigned int n = i / (sizeof(T)*8);
+ unsigned int r = i % (sizeof(T)*8);
+
+ T t = static_cast<T>(1) << r;
+ t = ~t;
+ set_[n] &= t;
+}
+
+
+template<typename T>
+void BoolSet<T>::set_all() {
+ unsigned int r = size_ % (sizeof(T)*8);
+ if (r == 0) {
+ for (unsigned int i = 0; i < set_.size(); i++)
+ set_[i] = ~static_cast<T>(0);
+ }
+ else {
+ for (unsigned int i = 0; i < set_.size()-1; i++)
+ set_[i] = ~static_cast<T>(0);
+ set_[set_.size()-1] = static_cast<T>(0);
+ T t = static_cast<T>(1);
+ for (unsigned int i = 0; i < r; i++) {
+ set_[set_.size()-1] |= t;
+ t = t<<1;
+ }
+ }
+}
+
+
+template<typename T>
+void BoolSet<T>::unset_all() {
+ for (unsigned int i = 0; i < set_.size(); i++)
+ set_[i] = static_cast<T>(0);
+}
+
+
+template<typename T>
+bool BoolSet<T>::get(unsigned int i) const {
+ assert(i < size_ && i >= 0);
+ unsigned int n = i / (sizeof(T)*8);
+ unsigned int r = i % (sizeof(T)*8);
+
+ T t = static_cast<T>(1) << r;
+ t = set_[n] & t;
+ if (t)
+ return true;
+ else
+ return false;
+}
+
+
+template<typename T>
+unsigned int BoolSet<T>::num_elem() const {
+ unsigned int n = size_;
+ unsigned int c = 0;
+ unsigned int p = 0;
+ while (n != 0) {
+ unsigned int m;
+ if (n >= sizeof(T)*8) {
+ m = sizeof(T)*8;
+ n -= sizeof(T)*8;
+ }
+ else {
+ m = n;
+ n = 0;
+ }
+
+ T v = set_[p++];
+ if (v != static_cast<T>(0)) {
+ for (unsigned int i = 0; i < m; i++) {
+ if (v & static_cast<T>(1))
+ c++;
+ v >>= 1;
+ }
+ }
+ }
+
+ return c;
+}
+
+
+template<typename T>
+bool BoolSet<T>::imply(const BoolSet<T> &b) const {
+ if (size_ >= b.size_) {
+ for (unsigned int i = 0; i < b.set_.size(); i++)
+ if ((set_[i] & b.set_[i]) != b.set_[i])
+ return false;
+ }
+ else {
+ for (unsigned int i = 0; i < set_.size(); i++)
+ if ((set_[i] & b.set_[i]) != b.set_[i])
+ return false;
+ for (unsigned int i = set_.size(); i < b.set_.size(); i++)
+ if (b.set_[i] != static_cast<T>(0))
+ return false;
+ }
+
+ return true;
+}
+
+
+template<typename T>
+bool BoolSet<T>::empty() const {
+ for (int i = 0; i < set_.size(); i++)
+ if (set_[i] != static_cast<T>(0))
+ return false;
+
+ return true;
+}
+
+
+template<typename T>
+void BoolSet<T>::dump() const {
+ int j = 1;
+ for (unsigned int i = 0; i < size(); i++) {
+ if (get(i))
+ std::cout << '1';
+ else
+ std::cout << '0';
+ if (j%10 == 0 && i != size() - 1) {
+ std::cout << ' ';
+ j = 1;
+ }
+ else
+ j++;
+ }
+ std::cout << std::endl;
+ std::cout.flush();
+}
+
+
+template<typename T>
+BoolSet<T> operator|(const BoolSet<T> &a, const BoolSet<T> &b) {
+ if (a.size_ >= b.size_) {
+ BoolSet<T> c = a;
+ for (unsigned int i = 0; i < b.set_.size(); i++)
+ c.set_[i] |= b.set_[i];
+ return c;
+ }
+ else {
+ BoolSet<T> c = b;
+ for (unsigned int i = 0; i < a.set_.size(); i++)
+ c.set_[i] |= a.set_[i];
+ return c;
+ }
+}
+
+
+template<typename T>
+BoolSet<T> operator&(const BoolSet<T> &a, const BoolSet<T> &b) {
+ if (a.size_ >= b.size_) {
+ BoolSet<T> c = a;
+ for (unsigned int i = 0; i < b.set_.size(); i++)
+ c.set_[i] &= b.set_[i];
+ for (unsigned int i = b.set_.size(); i < a.set_.size(); i++)
+ c.set_[i] = static_cast<T>(0);
+ return c;
+ }
+ else {
+ BoolSet<T> c = b;
+ for (unsigned int i = 0; i < a.set_.size(); i++)
+ c.set_[i] &= a.set_[i];
+ for (unsigned int i = a.set_.size(); i < b.set_.size(); i++)
+ c.set_[i] = static_cast<T>(0);
+ return c;
+ }
+}
+
+
+template<typename T>
+BoolSet<T> operator-(const BoolSet<T> &a, const BoolSet<T> &b) {
+ BoolSet<T> c(a.size_);
+
+ int sz = a.set_.size();
+ if (sz > b.set_.size())
+ sz = b.set_.size();
+ for (int i = 0; i < sz; i++)
+ c.set_[i] = a.set_[i] ^ (a.set_[i] & b.set_[i]);
+ for (int i = sz; i < a.set_.size(); i++)
+ c.set_[i] = a.set_[i];
+
+ return c;
+}
+
+
+template<typename T>
+BoolSet<T> operator~(const BoolSet<T> &b) {
+ unsigned int r = b.size_ % (sizeof(T)*8);
+ BoolSet<T> a(b.size_);
+ for (unsigned int i = 0; i < b.set_.size(); i++)
+ a.set_[i] = ~b.set_[i];
+
+ if (r != 0) {
+ T t = static_cast<T>(1);
+ for (unsigned int i = 1; i < r; i++)
+ t = (t << 1) | static_cast<T>(1);
+ a.set_[a.set_.size()-1] &= t;
+ }
+ return a;
+}
+
+
+template<typename T>
+bool operator==(const BoolSet<T> &a, const BoolSet<T> &b) {
+ return (a.size_ == b.size_) && (a.set_ == b.set_);
+}
+
+
+template<typename T>
+bool operator!=(const BoolSet<T> &a, const BoolSet<T> &b) {
+ return !(a == b);
+}
+
+
+
+template<typename T>
+BoolSet<T> & BoolSet<T>::operator|=(const BoolSet<T> &b) {
+ *this = *this | b;
+ return *this;
+}
+
+
+template<typename T>
+BoolSet<T> & BoolSet<T>::operator&=(const BoolSet<T> &b) {
+ *this = *this & b;
+ return *this;
+}
+
+
+template<typename T>
+BoolSet<T> & BoolSet<T>::operator-=(const BoolSet<T> &b) {
+ *this = *this - b;
+ return *this;
+}
+
+
+template<typename T>
+std::ostream& operator<<(std::ostream &os, const BoolSet<T> &b) {
+ os << '{';
+ for (typename BoolSet<T>::const_iterator i = b.begin(); i != b.end(); i++) {
+ os << *i;
+ if (i+1 != b.end())
+ os << ',';
+ }
+ os << '}';
+
+ return os;
+}
+
+
+template<typename T>
+bool operator<(const BoolSet<T> &a, const BoolSet<T> &b) {
+ unsigned int t1, t2;
+ t1 = a.num_elem();
+ t2 = b.num_elem();
+ if (t1 < t2)
+ return true;
+ else if (t1 > t2)
+ return false;
+ else {
+ t1 = a.size();
+ t2 = b.size();
+ if (t1 < t2)
+ return true;
+ else if (t1 > t2)
+ return false;
+ else
+ for (unsigned int i = 0; i < a.set_.size(); i++)
+ if (a.set_[i] < b.set_[i])
+ return true;
+ }
+ return false;
+}
+
+
+//
+// iterator for BoolSet
+//
+
+template<typename T>
+typename BoolSet<T>::iterator BoolSet<T>::begin() {
+ typename BoolSet<T>::iterator it(this, 0);
+ if (size_ == 0)
+ return it;
+ else if (set_[0] & static_cast<T>(1))
+ return it;
+ else
+ return ++it;
+}
+
+
+template<typename T>
+typename BoolSet<T>::iterator BoolSet<T>::end() {
+ return typename BoolSet<T>::iterator(this, size_);
+}
+
+
+template<typename T>
+typename BoolSet<T>::const_iterator BoolSet<T>::begin() const {
+ typename BoolSet<T>::const_iterator it(this, 0);
+ if (size_ == 0)
+ return it;
+ else if (set_[0] & static_cast<T>(1))
+ return it;
+ else
+ return ++it;
+}
+
+
+template<typename T>
+typename BoolSet<T>::const_iterator BoolSet<T>::end() const {
+ return typename BoolSet<T>::const_iterator(this, size_);
+}
+
+
+template<typename T>
+class BoolSet<T>::iterator: public std::iterator<std::forward_iterator_tag, T> {
+protected:
+ BoolSet<T> *s_;
+ unsigned int pos_;
+
+protected:
+ iterator(BoolSet<T> *s, unsigned int pos) { s_ = s; pos_ = pos; }
+
+public:
+ ~iterator() {}
+
+ typename BoolSet<T>::iterator &operator++();
+ typename BoolSet<T>::iterator operator++(int);
+ typename BoolSet<T>::iterator operator+(int) const;
+ unsigned int operator*() const;
+ bool operator==(const BoolSet<T>::iterator &) const;
+ bool operator!=(const BoolSet<T>::iterator &) const;
+ operator typename BoolSet<T>::const_iterator();
+
+ friend class BoolSet<T>;
+};
+
+
+template<typename T>
+typename BoolSet<T>::iterator &BoolSet<T>::iterator::operator++() {
+ assert(pos_ < s_->size_);
+
+ pos_++;
+ unsigned int n = pos_ / (sizeof(T)*8);
+ unsigned int r = pos_ % (sizeof(T)*8);
+ while (pos_ < s_->size_) {
+ if (s_->set_[n] == static_cast<T>(0)) {
+ pos_ += sizeof(T)*8-r;
+ n++;
+ r = 0;
+ if (pos_ >= s_->size_)
+ break;
+ }
+
+ if (r == 0) {
+ while (pos_ < s_->size_) {
+ if (s_->set_[n] == static_cast<T>(0)) {
+ pos_ += sizeof(T)*8;
+ n++;
+ }
+ else
+ break;
+ }
+ if (pos_ >= s_->size_)
+ break;
+ }
+
+ for (unsigned int i = r; i < sizeof(T)*8; i++)
+ if (s_->set_[n] & static_cast<T>(1) << i) {
+ pos_ = pos_+i-r;
+ return *this;
+ }
+
+ pos_ += sizeof(T)*8-r;
+ n++;
+ r = 0;
+ }
+
+ pos_ = s_->size_;
+ return *this;
+}
+
+
+template<typename T>
+typename BoolSet<T>::iterator BoolSet<T>::iterator::operator++(int) {
+ typename BoolSet<T>::iterator it(*this);
+ ++(*this);
+ return it;
+}
+
+
+template<typename T>
+typename BoolSet<T>::iterator BoolSet<T>::iterator::operator+(int n) const {
+ assert(n >= 0);
+ typename BoolSet<T>::iterator it(*this);
+ while (n > 0) {
+ ++it;
+ --n;
+ }
+ return it;
+}
+
+
+template<typename T>
+unsigned int BoolSet<T>::iterator::operator*() const {
+ assert(pos_ < s_->size_);
+ return pos_;
+}
+
+
+template<typename T>
+bool BoolSet<T>::iterator::operator==(const BoolSet<T>::iterator &other) const {
+ return s_ == other.s_ && pos_ == other.pos_;
+}
+
+
+template<typename T>
+bool BoolSet<T>::iterator::operator!=(const BoolSet<T>::iterator &other) const {
+ return !((*this) == other);
+}
+
+
+template<typename T>
+BoolSet<T>::iterator::operator typename BoolSet<T>::const_iterator() {
+ return BoolSet<T>::const_iterator(s_, pos_);
+}
+
+
+template<typename T>
+class BoolSet<T>::const_iterator: public std::iterator<std::forward_iterator_tag, T> {
+protected:
+ const BoolSet<T> *s_;
+ unsigned int pos_;
+
+protected:
+ const_iterator(const BoolSet<T> *s, unsigned int pos) { s_ = s; pos_ = pos; }
+
+public:
+ ~const_iterator() {}
+
+ typename BoolSet<T>::const_iterator &operator++();
+ typename BoolSet<T>::const_iterator operator++(int);
+ typename BoolSet<T>::const_iterator operator+(int) const;
+ unsigned int operator*() const;
+ bool operator==(const BoolSet<T>::const_iterator &) const;
+ bool operator!=(const BoolSet<T>::const_iterator &) const;
+
+ friend class BoolSet<T>;
+};
+
+
+template<typename T>
+typename BoolSet<T>::const_iterator &BoolSet<T>::const_iterator::operator++() {
+ assert(pos_ < s_->size_);
+
+ pos_++;
+ unsigned int n = pos_ / (sizeof(T)*8);
+ unsigned int r = pos_ % (sizeof(T)*8);
+ while (pos_ < s_->size_) {
+ if (s_->set_[n] == static_cast<T>(0)) {
+ pos_ += sizeof(T)*8-r;
+ n++;
+ r = 0;
+ if (pos_ >= s_->size_)
+ break;
+ }
+
+ if (r == 0) {
+ while (pos_ < s_->size_) {
+ if (s_->set_[n] == static_cast<T>(0)) {
+ pos_ += sizeof(T)*8;
+ n++;
+ }
+ else
+ break;
+ }
+ if (pos_ >= s_->size_)
+ break;
+ }
+
+ for (unsigned int i = r; i < sizeof(T)*8; i++)
+ if (s_->set_[n] & static_cast<T>(1) << i) {
+ pos_ = pos_+i-r;
+ return *this;
+ }
+
+ pos_ += sizeof(T)*8-r;
+ n++;
+ r = 0;
+ }
+
+ pos_ = s_->size_;
+ return *this;
+}
+
+
+template<typename T>
+typename BoolSet<T>::const_iterator BoolSet<T>::const_iterator::operator++(int) {
+ typename BoolSet<T>::const_iterator it(*this);
+ ++(*this);
+ return it;
+}
+
+
+template<typename T>
+typename BoolSet<T>::const_iterator BoolSet<T>::const_iterator::operator+(int n) const {
+ assert(n >= 0);
+ typename BoolSet<T>::const_iterator it(*this);
+ while (n > 0) {
+ ++it;
+ --n;
+ }
+ return it;
+}
+
+
+template<typename T>
+unsigned int BoolSet<T>::const_iterator::operator*() const {
+ assert(pos_ < s_->size_);
+ return pos_;
+}
+
+
+template<typename T>
+bool BoolSet<T>::const_iterator::operator==(const BoolSet<T>::const_iterator &other) const {
+ return s_ == other.s_ && pos_ == other.pos_;
+}
+
+
+template<typename T>
+bool BoolSet<T>::const_iterator::operator!=(const BoolSet<T>::const_iterator &other) const {
+ return !((*this) == other);
+}
+
+}
+
+#endif
diff --git a/lib/omega/include/basic/Collection.h b/lib/omega/include/basic/Collection.h
new file mode 100644
index 0000000..80ddf48
--- /dev/null
+++ b/lib/omega/include/basic/Collection.h
@@ -0,0 +1,43 @@
+#if !defined Already_Included_Collection
+#define Already_Included_Collection
+
+namespace omega {
+
+template<class T> class Iterator;
+template<class T> class Any_Iterator;
+
+
+//! protocol for any kind of collection
+template<class T> class Collection {
+public:
+ virtual Iterator<T> *new_iterator() = 0;
+ virtual Any_Iterator<T> any_iterator() { return Any_Iterator<T>(new_iterator()); }
+
+ virtual int size() const = 0;
+};
+
+
+/*!
+ * protocol for collections whose elements are ordered
+ * by the way they are entered into the collection, and
+ * whose elements can be accessed by "index"
+ *
+ * note that the implementation need not be a linked list
+ */
+template<class T> class Sequence : public Collection<T> {
+public:
+ virtual const T &operator[](int) const = 0;
+ virtual T &operator[](int) = 0;
+
+ /*! Y in X --> X[X.index(Y)] == Y */
+ virtual int index(const T &) const = 0; };
+
+} // namespace
+
+#define instantiate_Collection(T) template class Collection<T>; \
+ instantiate_Any_Iterator(T)
+#define instantiate_Sequence(T) template class Sequence<T>; \
+ instantiate_Collection(T)
+
+#endif
+
diff --git a/lib/omega/include/basic/Collections.h b/lib/omega/include/basic/Collections.h
new file mode 100644
index 0000000..1e68031
--- /dev/null
+++ b/lib/omega/include/basic/Collections.h
@@ -0,0 +1,12 @@
+#if !defined Already_Included_Collections
+#define Already_Included_Collections
+
+#include <stdio.h>
+#include <basic/Collection.h>
+#include <basic/Iterator.h>
+#include <basic/List.h>
+#include <basic/Bag.h>
+#include <basic/Map.h>
+
+#endif
+
diff --git a/lib/omega/include/basic/ConstString.h b/lib/omega/include/basic/ConstString.h
new file mode 100644
index 0000000..f149c9d
--- /dev/null
+++ b/lib/omega/include/basic/ConstString.h
@@ -0,0 +1,57 @@
+#if ! defined _Const_String_h
+#define _Const_String_h 1
+
+#include <string>
+
+namespace omega {
+
+// should be inside Const_String, but I can't get it to
+// compile the hashTable when it is: hashTable can't be
+// global, but if it and its size are static to Const_String,
+// the compiler still doesn't seem to like the definition,
+// or the declaration either for that matter.
+class ConstStringRep {
+public:
+ const char *name;
+ int count;
+ ConstStringRep *nextInBucket;
+ ConstStringRep(const char *t);
+};
+
+class Const_String {
+private:
+ ConstStringRep *rep;
+ void buildRep(const char *t);
+
+public:
+ Const_String();
+ Const_String(const char* t);
+ Const_String(const std::string &s);
+ Const_String(const Const_String & t) {rep = t.rep;}
+
+ operator int() const;
+ int null() const;
+
+ operator const char*() const;
+ operator std::string() const;
+ int operator++(int);
+ int operator++();
+ int operator--(int);
+ int operator--();
+ friend int operator==(const Const_String &x, const Const_String &y);
+ friend int operator!=(const Const_String &x, const Const_String &y);
+ friend int operator<(const Const_String &x, const Const_String &y);
+ friend int operator >(const Const_String &x, const Const_String &y);
+
+};
+
+#if defined SCREWED_UP_CASTING_RULES
+static int operator==(const Const_String &x, const char *y)
+{ return x == (Const_String) y; }
+static int operator!=(const Const_String &x, const char *y)
+{ return x != (Const_String) y; }
+#endif
+
+} // namespace
+
+#endif
diff --git a/lib/omega/include/basic/DynamicArray.h b/lib/omega/include/basic/DynamicArray.h
new file mode 100644
index 0000000..08f8b91
--- /dev/null
+++ b/lib/omega/include/basic/DynamicArray.h
@@ -0,0 +1,318 @@
+#ifndef Already_Included_DynamicArray
+#define Already_Included_DynamicArray
+
+#include <assert.h>
+
+namespace omega {
+
+template <class T> class DynamicArray2;
+template <class T> class DynamicArray3;
+template <class T> class DynamicArray4;
+
+template <class T, int d> class DynamicArray
+ {
+ public:
+ DynamicArray(DynamicArray<T,d> &D);
+ ~DynamicArray();
+
+ protected:
+ DynamicArray();
+ bool partial;
+ int *bounds;
+ T *elements;
+
+ void do_constr();
+ void do_destruct();
+ };
+
+
+template <class T> class DynamicArray1 : public DynamicArray<T,1>
+ {
+ public:
+ DynamicArray1(const char *s0 = 0);
+ DynamicArray1(int d0);
+ void resize(int d0);
+ T& operator[](int d);
+
+ friend class DynamicArray2<T>;
+
+ private:
+ void do_construct(int d0);
+ };
+
+
+template <class T> class DynamicArray2 : public DynamicArray<T,2>
+ {
+ public:
+ DynamicArray2(const char *s0 = 0, const char *s1 = 0);
+ DynamicArray2(int d0, int d1);
+ void resize(int d0, int d1);
+ DynamicArray1<T> operator[](int d);
+
+ friend class DynamicArray3<T>;
+
+ private:
+ void do_construct(int d0, int d1);
+ };
+
+
+template <class T> class DynamicArray3 : public DynamicArray<T,3>
+ {
+ public:
+ DynamicArray3(const char *s0 = 0, const char *s1 = 0, const char *s2 = 0);
+ DynamicArray3(int d0, int d1, int d2);
+ void resize(int d0, int d1, int d2);
+ DynamicArray2<T> operator[](int d);
+
+ friend class DynamicArray4<T>;
+
+ private:
+ void do_construct(int d0, int d1, int d2);
+ };
+
+template <class T> class DynamicArray4 : public DynamicArray<T,4>
+ {
+ public:
+ DynamicArray4(const char *s0 = 0, const char *s1 = 0, const char *s2 = 0, const char *s3 = 0);
+ DynamicArray4(int d0, int d1, int d2, int d3);
+ void resize(int d0, int d1, int d2, int d3);
+ DynamicArray3<T> operator[](int d);
+
+ private:
+ void do_construct(int d0, int d1, int d2, int d3);
+ };
+
+} // namespace
+
+#define instantiate_DynamicArray1(T) template class DynamicArray1<T>; \
+ template class DynamicArray<T,1>;
+
+#define instantiate_DynamicArray2(T) template class DynamicArray2<T>; \
+ template class DynamicArray<T,2>; \
+ instantiate_DynamicArray1(T);
+
+#define instantiate_DynamicArray3(T) template class DynamicArray3<T>; \
+ template class DynamicArray<T,3>; \
+ instantiate_DynamicArray2(T);
+
+#define instantiate_DynamicArray4(T) template class DynamicArray4<T>; \
+ template class DynamicArray<T,4>; \
+ instantiate_DynamicArray3(T);
+
+namespace omega {
+
+template<class T, int d> void DynamicArray<T,d>::do_constr()
+ {
+// #if ! defined SHUT_UP_ABOUT_STATEMENT_WITH_NO_EFFECT_IN_DYNAMIC_ARRAY_CREATION
+// assert(d > 0);
+// #endif
+ bounds = 0;
+ elements = 0;
+ partial = false;
+ }
+
+
+template<class T> void DynamicArray1<T>::do_construct(int d0)
+ {
+ this->bounds = new int[1];
+ this->bounds[0] = d0;
+ this->elements = new T [d0];
+ this->partial = false;
+ }
+
+template<class T> void DynamicArray2<T>::do_construct(int d0, int d1)
+ {
+ this->bounds = new int[2];
+ this->bounds[0] = d0;
+ this->bounds[1] = d1;
+ this->elements = new T [d0 * d1];
+ this->partial = false;
+ }
+
+template<class T> void DynamicArray3<T>::do_construct(int d0,int d1,int d2)
+ {
+ this->bounds = new int[3];
+ this->bounds[0] = d0;
+ this->bounds[1] = d1;
+ this->bounds[2] = d2;
+ this->elements = new T [d0 * d1 * d2];
+ this->partial = false;
+ }
+
+template<class T> void DynamicArray4<T>::do_construct(int d0,int d1,int d2,int d3)
+ {
+ this->bounds = new int[4];
+ this->bounds[0] = d0;
+ this->bounds[1] = d1;
+ this->bounds[2] = d2;
+ this->bounds[3] = d3;
+ this->elements = new T [d0 * d1 * d2 * d3];
+ this->partial = false;
+ }
+
+template<class T, int d> DynamicArray<T,d>::DynamicArray()
+ {
+ do_constr();
+ }
+
+template<class T> DynamicArray1<T>::DynamicArray1(const char *)
+ {
+ this->do_constr();
+ }
+
+template<class T> DynamicArray2<T>::DynamicArray2(const char *,const char *)
+ {
+ this->do_constr();
+ }
+
+template<class T> DynamicArray3<T>::DynamicArray3(const char *,const char *,const char *)
+ {
+ this->do_constr();
+ }
+
+template<class T> DynamicArray4<T>::DynamicArray4(const char *,const char *,const char *,const char *)
+ {
+ this->do_constr();
+ }
+
+template<class T> DynamicArray1<T>::DynamicArray1(int d0)
+ {
+ do_construct(d0);
+ }
+
+template<class T> DynamicArray2<T>::DynamicArray2(int d0, int d1)
+ {
+ do_construct(d0, d1);
+ }
+
+template<class T> DynamicArray3<T>::DynamicArray3(int d0,int d1,int d2)
+ {
+ do_construct(d0, d1, d2);
+ }
+
+template<class T> DynamicArray4<T>::DynamicArray4(int d0,int d1,int d2,int d3)
+ {
+ do_construct(d0, d1, d2, d3);
+ }
+
+
+template<class T, int d> void DynamicArray<T,d>::do_destruct()
+ {
+ if (! partial)
+ {
+ delete [] bounds;
+ delete [] elements;
+ }
+ }
+
+
+template<class T, int d> DynamicArray<T,d>::~DynamicArray()
+ {
+ do_destruct();
+ }
+
+
+template<class T> void DynamicArray1<T>::resize(int d0)
+ {
+ assert(!this->partial);
+ this->do_destruct();
+ if (d0 == 0)
+ this->do_constr();
+ else
+ do_construct(d0);
+ }
+
+template<class T> void DynamicArray2<T>::resize(int d0, int d1)
+ {
+ assert(!this->partial);
+ this->do_destruct();
+ if (d0 == 0 && d1 == 0)
+ this->do_constr();
+ else
+ do_construct(d0, d1);
+ }
+
+template<class T> void DynamicArray3<T>::resize(int d0, int d1, int d2)
+ {
+ assert(!this->partial);
+ this->do_destruct();
+ if (d0 == 0 && d1 == 0 && d2 == 0)
+ this->do_constr();
+ else
+ do_construct(d0, d1, d2);
+ }
+
+template<class T> void DynamicArray4<T>::resize(int d0, int d1, int d2, int d3)
+ {
+ assert(!this->partial);
+ this->do_destruct();
+ if (d0 == 0 && d1 == 0 && d2 == 0 && d3 == 0)
+ this->do_constr();
+ else
+ do_construct(d0, d1, d2, d3);
+ }
+
+
+template<class T> T& DynamicArray1<T>::operator[](int d0)
+ {
+#if !defined (NDEBUG)
+ assert(this->elements != 0 && "Trying to dereference undefined array");
+ assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds");
+#endif
+
+ return this->elements[d0];
+ }
+
+template<class T> DynamicArray1<T> DynamicArray2<T>::operator[](int d0)
+ {
+#if !defined (NDEBUG)
+ assert(this->elements != 0 && "Trying to dereference undefined array");
+ assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds");
+#endif
+
+ DynamicArray1<T> result;
+ result.bounds = this->bounds+1;
+ result.elements = this->elements + this->bounds[1] * d0;
+ result.partial = true;
+ return result;
+ }
+
+template<class T> DynamicArray2<T> DynamicArray3<T>::operator[](int d0)
+ {
+#if !defined (NDEBUG)
+ assert(this->elements != 0 && "Trying to dereference undefined array");
+ assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds");
+#endif
+ DynamicArray2<T> result;
+ result.bounds = this->bounds+1;
+ result.elements = this->elements + this->bounds[1] * this->bounds[2] * d0;
+ result.partial = true;
+ return result;
+ }
+
+template<class T> DynamicArray3<T> DynamicArray4<T>::operator[](int d0)
+ {
+#if !defined (NDEBUG)
+ assert(this->elements != 0 && "Trying to dereference undefined array");
+ assert(0 <= d0 && d0 < this->bounds[0] && "Array subscript out of bounds");
+#endif
+
+ DynamicArray3<T> result;
+ result.bounds = this->bounds+1;
+ result.elements = this->elements + this->bounds[1] * this->bounds[2] * this->bounds[3] * d0;
+ result.partial = true;
+ return result;
+ }
+
+
+template<class T, int d>
+ DynamicArray<T,d>::DynamicArray(DynamicArray<T,d> &D)
+ {
+ assert(D.elements != 0 && "Trying to copy an undefined array");
+ partial = true;
+ bounds = D.bounds;
+ elements = D.elements;
+ }
+
+} // namespace
+#endif
diff --git a/lib/omega/include/basic/Iterator.h b/lib/omega/include/basic/Iterator.h
new file mode 100644
index 0000000..f62874c
--- /dev/null
+++ b/lib/omega/include/basic/Iterator.h
@@ -0,0 +1,129 @@
+/*
+ * Base classes for iterators, generators
+ *
+ * These don't really work yet for constant collections.
+ * I'm not sure how to make that happen.
+ */
+
+#if ! defined _Iterator_h
+#define _Iterator_h 1
+
+#include <basic/Collection.h>
+
+namespace omega {
+
+#define foreach(x,T,S,A) do {for (omega::Any_Iterator<T> __P_##x = (S).any_iterator();__P_##x;__P_##x++) {T & x = *__P_##x; A;}} while (0)
+
+#define foreachSeparated(x,T,S,A,B) do {for (omega::Any_Iterator<T> __P_##x = (S).any_iterator();__P_##x;) {T & x = *__P_##x; A; __P_##x++; if (__P_##x) B;}} while (0)
+
+/*!
+ * \brief Abstract base class Iterator<type>
+ *
+ * Supports two styles of iteration:
+ * ~~~
+ * for ( ... initialize i (typically i = collection) ... ; i ; i++ )
+ * operate_on(*i)
+ * ~~~
+ * or
+ * ~~~
+ * for ( ... initialize i ... ; i.live() ; i.next() )
+ * operate_on(i.curr())
+ * ~~~
+ * **IF THE COLLECTION IS CHANGED, THE ITERATOR IS NO LONGER VALID**
+ *
+ * For collections that are not "Sequence"s, the order in
+ * which the elements are returned may not be consistent.
+ */
+template<class T> class Iterator {
+public:
+ virtual const T & operator*() const = 0;
+ virtual T & operator*() = 0;
+
+ virtual void operator++(int) = 0;
+ virtual void operator++() = 0;
+
+ virtual bool live() const = 0;
+ operator bool() const { return live(); }
+
+ const T & curr() const { return *(*this); }
+ T & curr() { return *(*this); }
+ void next() { (*this)++; }
+
+ virtual Iterator<T> *new_copy() const = 0;
+ virtual ~Iterator() {}
+};
+
+
+//! A generator is like an iterator but it gives out values
+/*! Values may or may not exist in some writable collection */
+template<class T> class Generator {
+public:
+ virtual T operator*() const = 0;
+
+ virtual void operator++(int) = 0;
+ virtual void operator++() = 0;
+
+ virtual int live() const = 0;
+ operator int() const { return live(); }
+
+ const T curr() const { return *(*this); }
+ T curr() { return *(*this); }
+ void next() { (*this)++; }
+};
+
+
+
+//! Delegate to any kind of iterator (on the heap)
+/*!
+ * * If created via a reference, become a copy of the iterator
+ * * If created via a pointer, manipulate that pointer and free *p when this dies
+ *
+ * Mostly useful for Collection::iterator `Iterator::Iterator(Collection)`
+ */
+template<class T> class Any_Iterator : public Iterator<T> {
+public:
+ Any_Iterator(Collection<T> &c);
+ Any_Iterator(const Iterator<T> &i); // copy of i
+
+ virtual ~Any_Iterator() { delete me; }
+
+ Any_Iterator<T> &operator=(const Any_Iterator<T> &rhs)
+ { delete me; me = rhs.me->new_copy(); return *this; }
+
+ const T & operator*() const { return *(*me); }
+ T & operator*() { return *(*me); }
+ void operator++(int) { (*me)++; }
+ void operator++() { ++(*me); }
+ bool live() const { return (*me).live(); }
+
+ Iterator<T> *new_copy() const { return new Any_Iterator<T>((*me).new_copy()); }
+
+private:
+ //! take over *p, *p MUST BE ON THE HEAP
+ Any_Iterator(Iterator<T> *p) { me = p; }
+ friend class Collection<T>;
+/*
+ * // Couldn't make this work with g++258
+ * friend Any_Iterator<T> Collection<T>::any_iterator();
+ */
+ Iterator<T> *me;
+};
+
+template <class T> inline Any_Iterator<T>::Any_Iterator(Collection<T> &c)
+ {
+ me = c.new_iterator();
+ }
+
+template <class T> inline Any_Iterator<T>::Any_Iterator(const Iterator<T> &i)
+ {
+ me = i.new_copy();
+ }
+
+} // namespace
+
+#define instantiate_Iterator(T) template class Iterator<T>;
+#define instantiate_Generator(T) template class Generator<T>;
+#define instantiate_Any_Iterator(T) template class Any_Iterator<T>; \
+ instantiate_Iterator(T)
+
+#endif
diff --git a/lib/omega/include/basic/Link.h b/lib/omega/include/basic/Link.h
new file mode 100644
index 0000000..bdf169c
--- /dev/null
+++ b/lib/omega/include/basic/Link.h
@@ -0,0 +1,97 @@
+#if ! defined _Link_h
+#define _Link_h 1
+
+#include <basic/Iterator.h>
+#include <stddef.h>
+
+namespace omega {
+
+// By default, if ndebug is not set, do not do free list
+
+#if ! defined ListElementFreeList
+#if ! defined NDEBUG || defined ASSERTIONS_ANYWAY
+#define ListElementFreeList 0
+#else
+#define ListElementFreeList 1
+#endif
+#endif
+
+#if ListElementFreeList
+ // g++ 2.5.8 does not allow static data in template classes, so...
+ extern void *kludgy_List_Element_new(size_t size);
+ extern void kludgy_List_Element_delete(void *ptr, size_t size);
+#endif
+/*!
+ * \brief List_Element: one item in a list and the pointer to the next.
+ *
+ * Each such object should be pointed to by either exactly one
+ * other List_Element or by some other pointer(s), exactly one
+ * of which will delete the List_Element.
+ * ListElements should ONLY be allocated on the heap.
+ */
+template <class T> class List_Element {
+public:
+#if ListElementFreeList
+ void *operator new(size_t size)
+ {
+ return kludgy_List_Element_new(size);
+ }
+ void operator delete(void *ptr, size_t size)
+ {
+ kludgy_List_Element_delete(ptr, size);
+ }
+#endif
+
+ T head;
+ List_Element<T> *tail;
+
+ List_Element() {
+ tail = 0;
+ }
+ List_Element(T h, List_Element<T> * t) {
+ head = h;
+ tail = t;
+ }
+ List_Element(const List_Element<T> & L) {
+ head = L.head;
+ if (L.tail) tail = new List_Element<T>(*L.tail);
+ else tail = 0;
+ }
+ List_Element & operator=(const List_Element<T> &L) {
+ if (this != &L) {
+ head = L.head;
+ if (tail) delete tail;
+ if (L.tail) tail = new List_Element<T>(*L.tail);
+ else tail = 0;
+ }
+ return *this;
+ }
+ virtual ~List_Element() { // virtual ensures 2nd arg of delete is right
+ delete tail;
+ }
+};
+
+
+
+template<class T> class List_Element_Iterator : public Iterator<T> {
+public:
+ List_Element_Iterator(List_Element<T>* j) { i = j; }
+ virtual const T & operator*() const { return i->head; }
+ virtual T & operator*() { return i->head; }
+ virtual void operator++(int) { i = i->tail; }
+ virtual void operator++() { i = i->tail; }
+ virtual bool live() const { return i != 0; }
+ Iterator<T> * new_copy() const { return new List_Element_Iterator<T>(i);}
+
+protected:
+ List_Element<T> *i;
+};
+
+} // namespace
+
+#define instantiate_Only_List_Element(T) template class List_Element<T>; \
+ template class List_Element_Iterator<T>;
+#define instantiate_List_Element(T) instantiate_Only_List_Element(T)\
+ instantiate_Collection(T)
+
+#endif
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
diff --git a/lib/omega/include/basic/Map.h b/lib/omega/include/basic/Map.h
new file mode 100644
index 0000000..25a116d
--- /dev/null
+++ b/lib/omega/include/basic/Map.h
@@ -0,0 +1,127 @@
+#if ! defined _Map_h
+#define _Map_h 1
+
+#include <basic/Link.h>
+#include <stdio.h> // for NULL
+
+namespace omega {
+
+#define foreach_map(k,K,v,V,M,A) {for (omega::MapElementIterator<K,V> __M_##k = (M).iterator();__M_##k;__M_##k++) {K & k = *__M_##k; V & v = __M_##k.value(); A;}}
+
+template <class K, class V> class MapElement {
+public:
+ K k;
+ V v;
+ MapElement<K,V> *tail;
+ MapElement(const MapElement<K,V>&);
+ MapElement() {}
+ MapElement & operator=(const MapElement<K,V>&);
+ ~MapElement() { delete tail; }
+};
+
+template<class K, class V> class MapElementIterator {
+public:
+ MapElementIterator(MapElement<K,V>* j) { i = j;}
+ virtual const K & operator*() const { return i->k; }
+ virtual K & operator*() { return i->k;}
+ virtual const V & value() const { return i->v; }
+ virtual V & value() { return i->v; }
+ virtual void operator++(int) { i = i->tail; }
+ virtual void operator++() { i = i->tail; }
+ virtual bool live() const { return i != NULL; }
+ operator bool() const { return live(); }
+protected:
+MapElement<K,V> *i;
+};
+
+template <class K, class V> class Map {
+public:
+#if ! defined linux
+ Map(const V &default_value);
+#else
+ // work around for '386 g++ on Linux
+ Map(V default_value);
+#endif
+ ~Map();
+ MapElementIterator<K,V> iterator()
+ {return MapElementIterator<K,V>(contents);}
+ int empty() const {return contents == NULL;}
+ V operator()(K) const;
+ V& operator[](K);
+private:
+ MapElement<K,V> * contents;
+ V _default_value;
+};
+
+} // namespace
+
+#define instantiate_Map(T1,T2) template class Map<T1,T2>; \
+ template class MapElement<T1,T2>; \
+ template class MapElementIterator<T1,T2>;
+#define instantiate_MapElement(T1,T2) instantiate_Map(T1,T2)
+#define instantiate_MapElementIterator(T1,T2) instantiate_Map(T1,T2)
+
+namespace omega {
+
+template<class K, class V> MapElement<K,V>:: MapElement(const MapElement<K,V>& M) {
+ if (M.tail) tail = new MapElement<K,V>(*M.tail);
+ else tail = 0;
+ k = M.k;
+ v = M.v;
+ }
+
+template<class K, class V> MapElement<K,V> &
+ MapElement<K,V>:: operator=(const MapElement<K,V>& M) {
+ if (this != &M) {
+ if (tail) delete tail;
+ if (M.tail) tail = new MapElement<K,V>(*M.tail);
+ else tail = 0;
+ k = M.k;
+ v = M.v;
+ }
+ return *this;
+ }
+
+
+
+
+#if ! defined linux
+template <class K, class V> Map <K,V>::Map(const V &default_value)
+#else
+template <class K, class V> Map <K,V>::Map(V default_value)
+#endif
+ : _default_value(default_value)
+ {
+ contents = 0;
+ }
+
+template <class K, class V> Map <K,V>::~Map()
+ {
+ delete contents;
+ }
+
+template <class K, class V> V Map<K,V>::operator()(K k) const {
+ MapElement <K,V> * P = contents;
+ while (P) {
+ if (P->k == k) return P->v;
+ P = P->tail;
+ };
+ return _default_value;
+ }
+
+template <class K, class V> V & Map<K,V>::operator[](K k) {
+ MapElement <K,V> * P = contents;
+ while (P) {
+ if (P->k == k) return P->v;
+ P = P->tail;
+ };
+ P = new MapElement <K,V>;
+ P->k = k;
+ P->v = _default_value;
+ P->tail = contents;
+ contents = P;
+ return P->v;
+ }
+
+} // namespace
+#endif
diff --git a/lib/omega/include/basic/Section.h b/lib/omega/include/basic/Section.h
new file mode 100644
index 0000000..7a4d241
--- /dev/null
+++ b/lib/omega/include/basic/Section.h
@@ -0,0 +1,138 @@
+#if ! defined _Section_h
+#define _Section_h 1
+/*
+ Section of an existing collection viewed as a collection
+ */
+
+#include <basic/Collection.h>
+#include <assert.h>
+
+namespace omega {
+
+template<class T> class Section_Iterator;
+
+template <class T> class Section : public Sequence<T> {
+public:
+ Section(Sequence<T> *, int start, int length);
+
+ Iterator<T> *new_iterator();
+
+ const T &operator[](int) const;
+ T &operator[](int);
+
+ int index(const T &) const;
+ int size() const;
+
+ friend class Section_Iterator<T>;
+
+private:
+ Sequence<T> *it;
+ int _start, _length;
+};
+
+template <class T> class Section_Iterator : public Iterator<T> {
+public:
+ Section_Iterator(Section<T> &sec);
+ virtual ~Section_Iterator() { delete it; }
+
+ const T & operator*() const { return *(*it); }
+ T & operator*() { return *(*it); }
+
+ void operator++(int);
+ void operator++();
+
+ bool live() const;
+ Iterator<T> *new_copy() const;
+
+private:
+ Section_Iterator(const Section_Iterator<T> &si);
+ Iterator<T> *it;
+ int remaining;
+};
+
+} // namespace
+
+#define instantiate_Section(T) template class Section<T>; \
+ template class Section_Iterator<T>; \
+ instantiate_Sequence(T)
+#define instantiate_Section_Iterator(T) instantiate_Section(T)
+
+
+namespace omega {
+
+template <class T> Section<T>::Section(Sequence<T> *s, int start, int length)
+ {
+ assert(s->size() >= start-1 + length);
+ it = s;
+ _start = start;
+ _length = length;
+ }
+
+template <class T> Iterator<T> *Section<T>::new_iterator()
+ {
+ return new Section_Iterator<T>(*this);
+ }
+
+template <class T> const T &Section<T>::operator[](int i) const
+ {
+ assert(1 <= i && i <= size());
+ return (*it)[i+(_start-1)];
+ }
+
+template <class T> T &Section<T>::operator[](int i)
+ {
+ assert(1 <= i && i <= size());
+ return (*it)[i+(_start-1)];
+ }
+
+template <class T> int Section<T>::index(const T &var) const
+ {
+ int i;
+ for (i=1; i<=size(); i++)
+ if ((*this)[i] == var)
+ return i;
+ return 0;
+ }
+
+template <class T> int Section<T>::size() const
+ {
+ return _length;
+ }
+
+
+template <class T> Section_Iterator<T>::Section_Iterator(Section<T> &sec)
+ {
+ it = sec.it->new_iterator();
+ for (int i = 1; i < sec._start; i++)
+ (*it)++;
+ remaining = sec.size();
+ }
+
+
+template <class T> Section_Iterator<T>::Section_Iterator(const Section_Iterator<T> &si) : it(si.it), remaining(si.remaining) {}
+
+
+template <class T> void Section_Iterator<T>::operator++()
+ { this->operator++(0); }
+
+template <class T> void Section_Iterator<T>::operator++(int)
+ {
+ if (remaining > 0)
+ {
+ (*it)++;
+ remaining--;
+ }
+ }
+
+template <class T> bool Section_Iterator<T>::live() const
+ {
+ return (remaining > 0);
+ }
+
+template <class T> Iterator<T> *Section_Iterator<T>::new_copy() const
+ {
+ return new Section_Iterator<T>(*this);
+ }
+
+} // namespace
+#endif
diff --git a/lib/omega/include/basic/SimpleList.h b/lib/omega/include/basic/SimpleList.h
new file mode 100644
index 0000000..104390d
--- /dev/null
+++ b/lib/omega/include/basic/SimpleList.h
@@ -0,0 +1,194 @@
+#if ! defined _Simple_List_h
+#define _Simple_List_h 1
+
+/*
+ * Linked lists with an interface like a bit of libg++'s SLSimple_List class
+ */
+
+#include <assert.h>
+#include <basic/Iterator.h>
+#include <basic/Collection.h>
+#include <basic/Link.h>
+
+namespace omega {
+
+#define Simple_List Omega_Simple_List
+#define Simple_List_Iterator Omega_Simple_List_Iterator
+
+template<class T> class Simple_List_Iterator;
+
+// A TEMPORARY HACK - ERROR IF YOU TRY TO USE "INDEX" - FERD
+
+template<class T> class Simple_List : public Sequence<T> {
+public:
+ Simple_List(const Simple_List<T> &l)
+ { contents = l.contents ? new List_Element<T>(*l.contents) : 0; }
+ Simple_List() { contents = 0; }
+ virtual ~Simple_List() { delete contents; }
+
+ Iterator<T> *new_iterator();
+ const T &operator[](int) const;
+ T &operator[](int);
+
+
+ int size() const;
+ int length() const { return size(); }
+ int 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 del_front();
+ void clear();
+
+ void join(Simple_List<T> &consumed);
+
+ int index(const T &) const {
+ assert(0&&"ILLEGAL SimpleList operation\n");
+ return -1;
+ }
+
+private:
+ friend class Simple_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 Simple_List_Iterator : public List_Element_Iterator<T> {
+public:
+ Simple_List_Iterator(Simple_List<T> &l);
+ Simple_List_Iterator(const Simple_List<T> &l);
+ Simple_List_Iterator();
+private:
+ List_Element<T> &element() { return *this->i; } ;
+ friend class Simple_List<T>;
+};
+
+} // namespace
+
+#define instantiate_Simple_List(T) template class Simple_List<T>; \
+ template class Simple_List_Iterator<T>; \
+ instantiate_Only_List_Element(T) \
+ instantiate_Sequence(T)
+
+namespace omega {
+
+template<class T> Simple_List_Iterator<T>::Simple_List_Iterator(Simple_List<T> &l)
+: List_Element_Iterator<T>(l.contents) {}
+
+template<class T> Simple_List_Iterator<T>::Simple_List_Iterator(const Simple_List<T> &l)
+: List_Element_Iterator<T>(l.contents) {}
+
+template<class T> Simple_List_Iterator<T>::Simple_List_Iterator()
+: List_Element_Iterator<T>(0) {}
+
+template<class T> Iterator<T> *Simple_List<T>::new_iterator()
+{
+ return new Simple_List_Iterator<T>(*this);
+}
+
+template<class T> const T &Simple_List<T>::operator[](int i) const
+{
+ Simple_List_Iterator<T> p(*this);
+
+ while(--i > 0 && p)
+ p++;
+
+ if (p)
+ return *p;
+ else
+ return *((T *)0);
+}
+
+template<class T> T &Simple_List<T>::operator[](int i)
+{
+ Simple_List_Iterator<T> p(*this);
+
+ while(--i > 0 && p)
+ p++;
+
+ if (p)
+ return *p;
+ else
+ return *((T *)0);
+}
+
+
+template<class T> int Simple_List<T>::size() const
+ {
+ int i = 0;
+ List_Element<T> * p = contents;
+ while (p)
+ {
+ p = p->tail;
+ i++;
+ }
+ return i;
+ }
+
+template<class T> T &Simple_List<T>::front() const
+ {
+ return contents->head;
+ }
+
+template<class T> T Simple_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 Simple_List<T>::prepend(const T &item)
+ {
+ contents = new List_Element<T>(item, contents);
+ }
+
+
+template<class T> void Simple_List<T>::append(const T &item)
+ {
+ *(end()) = new List_Element<T>(item, 0);
+ }
+
+
+template<class T> void Simple_List<T>::del_front()
+ {
+ List_Element<T> *e = contents;
+ contents = contents->tail;
+ e->tail = 0;
+ delete e;
+ }
+
+
+template<class T> void Simple_List<T>::clear()
+ {
+ delete contents;
+ contents = 0;
+ }
+
+template<class T> void Simple_List<T>::join(Simple_List<T> &consumed)
+ {
+ List_Element<T> *e = consumed.contents;
+ consumed.contents = 0;
+ *(end()) = e;
+ }
+
+} // namespace
+#endif
diff --git a/lib/omega/include/basic/Tuple.h b/lib/omega/include/basic/Tuple.h
new file mode 100644
index 0000000..e9aae84
--- /dev/null
+++ b/lib/omega/include/basic/Tuple.h
@@ -0,0 +1,336 @@
+#if !defined _Already_defined_tuple
+#define _Already_defined_tuple
+
+#include <stdio.h>
+
+#include <basic/Collection.h>
+#include <basic/Iterator.h>
+#include <basic/util.h>
+
+namespace omega {
+
+template<class T> class Tuple_Iterator;
+
+// TUPLES ARE INDEXED STARTING AT 1
+// index\(i\) == 0 MEANS i IS NOT IN THE TUPLE
+
+template <class T> class Tuple : public Sequence<T> {
+public:
+ Tuple();
+ Tuple(int size);
+ Tuple (const Tuple<T>& tpl);
+ virtual ~Tuple();
+ Tuple<T>& operator=(const Tuple<T>& tpl);
+ int size() const { return sz; }
+ int length() const { return sz; }
+ bool operator==(const Tuple<T> &b) const;
+ void reallocate(const int);
+ void delete_last();
+ void append(const Tuple<T> &v);
+ void append(const T &v);
+ void join(Tuple<T> &v);
+ void clear();
+ int empty() const;
+
+ Iterator<T> *new_iterator();
+
+ virtual T &operator[](int index);
+ virtual const T &operator[](int index) const;
+
+ int index(const T &) const;
+
+ friend class Tuple_Iterator<T>;
+
+private:
+ int prealloc_size(const int req_size)
+ { return max(req_size+prealloc_pad,prealloc_min); }
+ int realloc_size(const int oldsize) { return 2*oldsize; }
+
+
+ int sz, alloc_sz; // Number of elements, size of allocated array
+ int prealloc_min,prealloc_pad; // These should be static, but that
+ // causes portability prob. for initialization
+
+protected:
+ T * data;
+};
+
+template <class T> class Tuple_Iterator : public Iterator <T> {
+public:
+ Tuple_Iterator(const Tuple<T> &tpl);
+ const T & operator*() const;
+ T & operator*();
+ void set_position(const int req_pos);
+ void operator++(int);
+ void operator++();
+ void operator--(int);
+ void operator--();
+ void set_to_last();
+ void set_to_first();
+// void set_position(const int req_pos); Don't do this, compiler bug
+ bool live() const;
+ Iterator<T> *new_copy() const;
+
+private:
+ Tuple_Iterator(T * cr, T * frst, T *lst, int insz);
+ T * current, * lastptr, *firstptr;
+ int sz;
+};
+
+} // namespace
+
+#define instantiate_Tuple(T) template class Tuple<T>; \
+ template class Tuple_Iterator<T>; \
+ instantiate_Sequence(T)
+
+namespace omega {
+
+template<class T> T &Tuple<T>::operator[](int index)
+ {
+ assert(1 <= index && index <= sz); return data[index-1];
+ }
+
+template<class T> const T &Tuple<T>::operator[](int index) const
+ {
+ assert(1 <= index && index <= sz); return data[index-1];
+ }
+
+
+template<class T> Tuple<T>::~Tuple()
+ {
+ if (data)
+ delete [] data;
+ }
+
+template<class T> Tuple<T>::Tuple() : sz(0), alloc_sz(0),
+ prealloc_min(20),prealloc_pad(5), data(0)
+{
+ // nothing needs be done
+ }
+
+template<class T> Tuple<T>::Tuple(int size) : sz(size),
+ prealloc_min(20),prealloc_pad(5)
+{
+ if (sz > 0)
+ {
+ alloc_sz = prealloc_size(sz);
+ data = new T[alloc_sz];
+ assert(alloc_sz >= sz);
+ //Need some handling for out of memory.
+ assert (data!=0);
+ }
+ else {
+ alloc_sz = 0;
+ data = 0;
+ }
+}
+
+
+template<class T> Tuple<T>::Tuple(const Tuple<T>& t)
+ : sz(t.sz), alloc_sz(t.alloc_sz), prealloc_min(20),prealloc_pad(5)
+{
+ if (sz > 0) {
+ data = new T[alloc_sz];
+ assert (data!=0);
+ assert (alloc_sz >= sz);
+ for (int i=0; i<sz; i++)
+ data[i] = t.data[i];
+ } else {
+ data = 0;
+ alloc_sz = 0; // THis might not be 0 if it was a "clear"ed Tuple
+// assert(alloc_sz == 0);
+ }
+}
+
+
+template<class T> Tuple<T>& Tuple<T>::operator=(const Tuple<T>& t)
+{
+ if (this != &t) { // Delete this
+ if (data)
+ delete [] data;
+ sz = t.sz;
+ alloc_sz = t.alloc_sz;
+ assert(alloc_sz >= sz);
+ if (sz > 0) { // Copy old
+ data = new T[alloc_sz];
+ assert (data!=0);
+ for (int i=0; i<sz; i++)
+ data[i] = t.data[i];
+ } else {
+ data=0;
+ alloc_sz = 0; // THis might not be 0 if it was a "clear"ed Tuple
+// assert(alloc_sz == 0);
+ }
+ }
+ return *this;
+}
+
+
+template<class T> void Tuple<T>::reallocate(const int req_size)
+{
+ if (alloc_sz >= req_size) { // if (sz >= req_size), does this.
+ sz = req_size;
+ return;
+ }
+ alloc_sz = prealloc_size(req_size);
+ T* tmp_data = new T[alloc_sz];
+ for(int i=0;i<sz;i++)
+ tmp_data[i] = data[i];
+ delete [] data;
+ data = tmp_data;
+ sz = req_size;
+ assert(alloc_sz >= req_size);
+}
+
+template<class T> void Tuple<T>::delete_last()
+{
+assert(sz > 0);
+sz --;
+}
+
+template<class T> void Tuple<T>::append(const T &v)
+{
+ // Check if reallocation is necessary.
+ if (sz == 0) { // Empty Tuple
+ assert(alloc_sz >= 0); // May be nonzero for cleared tuple
+
+ if(alloc_sz == 0) { // If it's > 1 no allocation is necessary
+ alloc_sz = prealloc_size(1);
+ data = new T[alloc_sz];
+ }
+ assert (alloc_sz > 0 && data != 0);
+ } else {
+ if(sz == alloc_sz) { // Requires new allocation
+ alloc_sz = realloc_size(alloc_sz);
+ T * data_tmp = new T[alloc_sz];
+ assert (data_tmp!=0);
+ assert (alloc_sz > sz);
+ for (int i=0; i<sz; i++)
+ data_tmp[i] = data[i];
+ delete [] data;
+ data=data_tmp;
+ } // Otherwise big enough, no reallocation necessary
+ }
+ // Make assignment
+ assert(alloc_sz >= sz);
+ data[sz++] = v;
+}
+
+template<class T> void Tuple<T>::append(const Tuple<T>& t) {
+ int old_sz = sz;
+ reallocate(t.size()+size());
+ assert(alloc_sz >= sz);
+ for(int i=0; i<t.sz; i++)
+ data[i+old_sz] = t.data[i];
+}
+
+template<class T> void Tuple<T>::join(Tuple<T>& t) {
+ int old_sz = sz;
+ reallocate(t.size()+size());
+ assert(alloc_sz >= sz);
+ for(int i=0; i<t.sz; i++)
+ data[i+old_sz] = t.data[i];
+ t.clear();
+}
+
+template<class T> void Tuple<T>::clear() { if (sz) delete [] data; data = 0; alloc_sz = 0; sz = 0; }
+
+template<class T> int Tuple<T>::empty() const { return (sz == 0); }
+
+template<class T> Iterator<T> *Tuple<T>::new_iterator()
+{
+ return new Tuple_Iterator<T>(*this);
+}
+
+template<class T> int Tuple<T>::index(const T & var) const
+/* returns index or 0 if var isn't in the tuple */
+{
+ int i;
+ for (i=0; i<sz; i++)
+ if (data[i]== var)
+ return i+1;
+ return 0;
+}
+
+template<class T> bool Tuple<T>::operator == (const Tuple<T>& b) const
+{
+ int i;
+ if (sz != b.size()) return false;
+ for (i=0; i<sz; i++)
+ if (!(data[i] == b[i+1])) return false;
+ return true;
+}
+
+/* class Tuple_Iterator */
+
+template<class T> Tuple_Iterator<T>::Tuple_Iterator(const Tuple<T> &tpl) :
+current(tpl.data), lastptr(tpl.data+tpl.sz-1), firstptr(tpl.data), sz(tpl.sz)
+{
+}
+
+template<class T> Tuple_Iterator<T>::Tuple_Iterator(T * cr, T *frst, T * lst,
+ int insz)
+ : current(cr), lastptr(lst), firstptr(frst), sz(insz)
+{
+}
+
+template<class T> const T & Tuple_Iterator<T>::operator*() const
+{
+ assert (current<=lastptr && current>=firstptr);
+ return *current;
+}
+
+template<class T> T & Tuple_Iterator<T>::operator*()
+{
+ assert (current<=lastptr && current >=firstptr);
+ return *current;
+}
+
+template<class T> void Tuple_Iterator<T>::operator++(int)
+{
+ current++;
+}
+
+template<class T> void Tuple_Iterator<T>::operator++()
+{
+ current++;
+}
+
+template<class T> void Tuple_Iterator<T>::operator--(int)
+{
+ current--;
+}
+
+template<class T> void Tuple_Iterator<T>::operator--()
+{
+ current--;
+}
+
+template<class T> void Tuple_Iterator<T>::set_to_last()
+{
+ current = lastptr;
+}
+
+template<class T> void Tuple_Iterator<T>::set_to_first()
+{
+ current = firstptr;
+}
+
+template<class T> void Tuple_Iterator<T>::set_position(const int req_pos)
+{
+ assert(req_pos <= sz && 1 <= req_pos);
+ current = firstptr + (req_pos - 1);
+}
+
+
+template<class T> bool Tuple_Iterator<T>::live() const
+{
+ return (current !=0 && current<=lastptr && current >= firstptr);
+}
+
+template<class T> Iterator<T> *Tuple_Iterator<T>::new_copy() const {
+ return new Tuple_Iterator<T>(current, firstptr, lastptr, sz);
+}
+
+} // namespace
+#endif
diff --git a/lib/omega/include/basic/omega_error.h b/lib/omega/include/basic/omega_error.h
new file mode 100644
index 0000000..e342efb
--- /dev/null
+++ b/lib/omega/include/basic/omega_error.h
@@ -0,0 +1,14 @@
+#ifndef OMEGA_ERROR_H
+#define OMEGA_ERROR_H
+
+namespace omega {
+
+struct presburger_error: public std::runtime_error {
+ presburger_error(const std::string &msg): std::runtime_error("presburger error: " + msg) {}
+};
+
+
+
+}
+#endif
+
diff --git a/lib/omega/include/basic/util.h b/lib/omega/include/basic/util.h
new file mode 100644
index 0000000..4e807cd
--- /dev/null
+++ b/lib/omega/include/basic/util.h
@@ -0,0 +1,263 @@
+#if ! defined Already_Included_Util
+#define Already_Included_Util
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string>
+#include <sstream>
+#include <stdexcept>
+
+namespace omega {
+
+#define LONG_LONG_COEF 1
+
+#if LONG_LONG_COEF
+#if defined BOGUS_LONG_DOUBLE_COEF
+typedef long double coef_t; // type of coefficients
+#define coef_fmt "%llf"
+#define posInfinity (1e+24)
+#define negInfinity (-1e+24)
+#else
+#ifdef WIN32
+typedef _int64 coef_t; // type of coefficients
+#else
+typedef long long coef_t;
+#endif
+#define coef_fmt "%lld"
+#define posInfinity (0x7ffffffffffffffLL)
+#define negInfinity (-0x7ffffffffffffffLL)
+#endif
+#else
+typedef int coef_t; // type of coefficients
+#define coef_fmt "%d"
+#define posInfinity (0x7ffffff)
+#define negInfinity (-0x7ffffff)
+#endif
+
+
+template<typename T> inline const T& max(const T &x, const T &y) {
+ if (x >= y) return x; else return y;
+}
+
+
+template<typename T> inline const T& max(const T &x, const T &y, const T &z) {
+ return max(x, max(y, z));
+}
+
+template<typename T> inline const T& min(const T &x, const T &y) {
+ if (x <= y) return x; else return y;
+}
+
+template<typename T> inline const T& min(const T &x, const T &y, const T &z) {
+ return min(x, min(y, z));
+}
+
+template<class T> inline void set_max(T &m, const T &x) {
+ if (m < x) m = x;
+}
+
+template<class T> inline void set_min(T &m, const T &x) {
+ if (m > x) m = x;
+}
+
+/* template<class T> inline void swap(T &i, T &j) { */
+/* T tmp; */
+/* tmp = i; */
+/* i = j; */
+/* j = tmp; */
+/* } */
+
+/* template<class T> inline T copy(const T &t) { return t; } */
+
+
+/* inline coef_t check_pos_mul(coef_t x, coef_t y) { */
+/* if (y >= 48051280 && y < posInfinity) */
+/* fprintf(stderr, "%d %d\n", x, y); */
+/* /\* #if !defined NDEBUG *\/ */
+/* /\* if (x != 0) *\/ */
+/* /\* assert(((MAXINT)/4) / x > y); *\/ */
+/* /\* #elif defined STILL_CHECK_MULT *\/ */
+/* /\* if (x != 0 && !(((MAXINT)/4) / x > y)) { *\/ */
+/* /\* assert(0&&"Integer overflow during multiplication (util.h)"); *\/ */
+/* /\* } *\/ */
+/* /\* #endif *\/ */
+/* #if !defined NDEBUG */
+/* if (x != 0 && y != 0) */
+/* assert(x*y > 0); */
+/* #elif defined STILL_CHECK_MULT */
+/* if (x != 0 && y != 0 && x*y < 0) */
+/* assert(0&&"Integer overflow during multiplication (util.h)"); */
+/* #endif */
+/* return x * y; */
+/* } */
+
+
+/* inline int */
+/* check_pos_mul(int x, int y) { */
+/* #if !defined NDEBUG */
+/* if (x != 0) */
+/* assert(((posInfinity)/4) / x > y); */
+/* #elif defined STILL_CHECK_MULT */
+/* if (x != 0 && !(((posInfinity)/4) / x > y)) { */
+/* assert(0&&"Integer overflow during multiplication (util.h)"); */
+/* } */
+/* #endif */
+/* return x * y; */
+/* } */
+
+/* inline LONGLONG */
+/* check_pos_mul(LONGLONG x, LONGLONG y) { */
+/* #if !defined NDEBUG */
+/* if (x != 0) */
+/* assert(((posInfinity)/4) / x > y); */
+/* #elif defined STILL_CHECK_MULT */
+/* if (x != 0 && !(((posInfinity)/4) / x > y)) { */
+/* assert(0&&"Integer overflow during multiplication (util.h)"); */
+/* } */
+/* #endif */
+/* return x * y; */
+/* } */
+
+/* inline LONGLONG abs(LONGLONG c) { return (c>=0?c:(-c)); } */
+
+template<typename T> inline T check_mul(const T &x, const T &y) {
+#if defined NDEBUG && ! defined STILL_CHECK_MULT
+ return x*y;
+#else
+ if (x == 0 || y == 0)
+ return 0;
+
+ T z = x*y;
+ int sign_x = (x>0)?1:-1;
+ int sign_y = (y>0)?1:-1;
+ int sign_z = (z>0)?1:-1;
+
+ if (sign_x * sign_y != sign_z)
+ throw std::overflow_error("coefficient multiply overflow");
+
+ return z;
+
+ /* if (x > 0) { */
+ /* if (y > 0) { */
+ /* assert(x*y > 0); */
+ /* } */
+ /* else */
+ /* assert(x*y < 0); */
+ /* } */
+ /* else { */
+ /* if (y > 0) */
+ /* assert(x*y < 0); */
+ /* else */
+ /* assert(x*y > 0); */
+ /* } */
+ /* return x*y; */
+#endif
+}
+
+template<typename T> inline T abs(const T &v) {
+ return (v >= static_cast<T>(0))?v:-v;
+}
+
+template<class T> inline T int_div(const T &a, const T &b) {
+ T result;
+ assert(b > 0);
+ if (a>0) result = a/b;
+ else result = -((-a+b-1)/b);
+ return result;
+}
+
+template<class T> inline T int_mod(const T &a, const T &b) {
+ return a-b*int_div(a,b);
+}
+
+template<class T> inline T int_mod_hat(const T &a, const T &b) {
+ T r;
+ assert(b > 0);
+ r = a-b*int_div(a,b);
+ if (r > -(r-b)) r -= b;
+ return r;
+}
+
+template<typename T> inline T gcd(T b, T a) {/* First argument is non-negative */
+ assert(a >= 0);
+ assert(b >= 0);
+ if (b == 1)
+ return (1);
+ while (b != 0) {
+ T t = b;
+ b = a % b;
+ a = t;
+ }
+ return (a);
+}
+
+template<typename T> inline T lcm(T b, T a) { /* First argument is non-negative */
+ assert(a >= 0);
+ assert(b >= 0);
+ return check_mul(a/gcd(a,b), b);
+}
+
+template<typename T> T square_root(const T &n, T precision = 1) {
+ T guess = 1;
+
+ while (true) {
+ T next_guess = 0.5*(guess+n/guess);
+ if (abs(next_guess-guess) <= precision)
+ return next_guess;
+ else
+ guess = next_guess;
+ }
+}
+
+template<typename T> T factor(const T &n) {
+ assert(n >= 0);
+ if (n == 1) return 1;
+
+ static int prime[30] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113};
+
+ if (n <= 113*113) {
+ for (int i = 0; i < 30; i++)
+ if (n % static_cast<T>(prime[i]) == 0)
+ return static_cast<T>(prime[i]);
+
+ return n;
+ }
+
+ T i = 1;
+ T k = 2;
+ T x = static_cast<T>(rand())%n;
+ T y = x;
+ while(i < square_root<float>(n, 1)) {
+ i++;
+ x = (x*x-1) % n;
+ T d = gcd(abs(y-x), n);
+ if(d != 1 && d != n)
+ return factor(d);
+ if(i == k) {
+ y = x;
+ k *= 2;
+ }
+ }
+ return n;
+}
+
+/* #define implies(A,B) (A==(A&B)) */
+
+template<typename T> std::string to_string(const T &t) {
+ std::ostringstream ss;
+ ss << t;
+ return ss.str();
+}
+
+template<typename T> T from_string(const std::string &s) {
+ std::istringstream ss(s);
+ ss.exceptions(std::ios::failbit);
+ T t;
+ ss >> t;
+ return t;
+}
+
+} // namespace
+
+#endif
generated by cgit v1.2.3-70-g09d2 (git 2.48.1) at 2025-10-30 18:02:23 +0000