#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