summaryrefslogtreecommitdiff
path: root/omegalib/omega/include/basic/Bag.h
diff options
context:
space:
mode:
Diffstat (limited to 'omegalib/omega/include/basic/Bag.h')
-rw-r--r--omegalib/omega/include/basic/Bag.h405
1 files changed, 0 insertions, 405 deletions
diff --git a/omegalib/omega/include/basic/Bag.h b/omegalib/omega/include/basic/Bag.h
deleted file mode 100644
index a3d07a0..0000000
--- a/omegalib/omega/include/basic/Bag.h
+++ /dev/null
@@ -1,405 +0,0 @@
-#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
generated by cgit v1.2.3-70-g09d2 (git 2.48.1) at 2025-02-09 00:33:27 +0000