From 210f77d2c32f14d2e99577fd3c9842bb19d47e50 Mon Sep 17 00:00:00 2001
From: Tuowen Zhao <ztuowen@gmail.com>
Date: Mon, 19 Sep 2016 21:14:58 +0000
Subject: Moved most modules into lib

---
 lib/omega/include/basic/Bag.h | 405 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 405 insertions(+)
 create mode 100644 lib/omega/include/basic/Bag.h

(limited to 'lib/omega/include/basic/Bag.h')

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
-- 
cgit v1.2.3-70-g09d2