//**************************************************************
//
//  CS 240C   : Spring 2003 Ohio University Travis Dillon
//  Project 1 : A Templated Set Class
//  file      : bag.template
//  started   : 04-07-03
//
//**************************************************************
#include "bag.h"
#include "main.h"

template <typename T>
Bag<T>::Bag()
{
   first = NULL;
   count = 0;
}

template <typename T>
Bag<T>::Bag(const Bag<T>& in)
{
   if(in.first == NULL)
   {
      first = NULL;
      count = 0;
      return;
   }
   Node<T>* iterr = in.first;
   first = new Node<T>(*iterr);
   Node<T>* iterl = first;
   while(iterr -> fore != NULL)
   {
      iterr = iterr -> fore;
      iterl -> fore = new Node<T>(*iterr);
      iterl = iterl -> fore;
   }
   iterl -> fore = NULL;
   count = in.count;
}

template <typename T>
Bag<T>& Bag<T>::operator =(const Bag<T>& rop)
{
   if(this == &rop) return *this;  //self assignment
   strip();
   
   if(rop.first == NULL)  //assignment of empty bag
   {
      first = NULL;
      count = 0;
      return *this;
   }
   Node<T>* iterr = rop.first;
   first = new Node<T>(*iterr);
   Node<T>* iterl = first;
   
   while(iterr -> fore != NULL)
   {
      iterr = iterr -> fore;
      iterl -> fore = new Node<T>(*iterr);
      iterl = iterl -> fore;
   }
   iterl -> fore = NULL;
   count = rop.count;
   return *this;
}

template <typename T>
Bag<T>::~Bag()
{
   strip();  //delete all nodes
}

template <typename T>
bool Bag<T>::iselement(T ele)const
{
   if(first == NULL) return false;  //not element if empty
   Node<T>* iter;
   for(iter = first; iter != NULL; iter = iter -> fore)
   {
      if(ele == iter -> data) return true;
   }
   return false;
}

template <typename T>
bool Bag<T>::issubset(const Bag<T>& in)const
{
   if(first == NULL && in.first == NULL) return true;
   if(first == NULL) return true;
   if(in.first == NULL) return false;
   Node<T>* iter = first;
   while(iter != NULL)
   {
      if(!in.iselement(iter -> data)) return false;
      iter = iter -> fore;
      if(iter == NULL) return true;
   }
   return true;
}

template <typename T>
ostream& operator <<(ostream& os, const Bag<T>& rop)
{
   os <<"\nBag : ";
   if(rop.first == NULL){os <<"empty\n"; return os;}
   os << '{';
   for(Node<T>* iter = rop.first; iter != NULL; iter = iter -> fore)
   {
      os << iter -> data;
      if(iter -> fore != NULL) os << ", ";
   }
   
   os << '}' << endl;
   return os;
}

template <typename T>
Bag<T> operator +(const Bag<T>& lop, const Bag<T>& rop)
{  //union of two sets
   Bag<T> ans;
   if(lop.count == 0 && rop.count == 0) return ans;
   if(lop.count == 0)
   {
      ans = rop;
      return ans;
   }
   ans = lop;
   Node<T>* iter = rop.first;
   for(; iter != NULL; iter = iter -> fore)
      if(!ans.iselement(iter -> data)) ans.insert(iter -> data);
   return ans;
}

template <typename T>
Bag<T> operator *(const Bag<T>& lop, const Bag<T>& rop)
{  //intersection of two sets
   Bag<T> ans;
   if(lop.count == 0) return ans;
   if(rop.count == 0) return ans;
   Node<T>* iter = lop.first;
   for(; iter != NULL; iter = iter -> fore)
      if(rop.iselement(iter -> data)) ans.insert(iter -> data);
   return ans;
}

template <typename T>
Bag<T> operator -(const Bag<T>& lop, const Bag<T>& rop)
{  //difference of two sets
   Bag<T> ans;
   Node<T>* iter = lop.first;
   for(; iter != NULL; iter = iter -> fore)
      if(!rop.iselement(iter -> data)) ans.insert(iter -> data);
   return ans;
}


template <typename T>
void Bag<T>::insert(T in_data)
{  //insert into bag, check for douplicates
   if(first == NULL)
   {
      first = new Node<T>(in_data);
      first -> fore = NULL;
      count++;
      return;
   }
   if(!iselement(in_data))
   {
      Node<T>* iter = first;
      first = new Node<T>(in_data);
      first -> fore = iter;
      count++;
   }
}

template <typename T>
void Bag<T>::strip()
{  //delete all nodes in list
   Node<T>* iter1 = first;
   Node<T>* iter2;
   while(iter1 != NULL)
   {
      iter2 = iter1;
      iter1 = iter1 -> fore;
      delete iter2;
   }
   first = NULL;
   count = 0;
}

template <typename T>
T Bag<T>::grab()
{  //return random item from bag
   if(count == 0) return T();
   int temp = rand() % count;
   Node<T>* iter = first;
   for(int i(0); i < temp; i++) iter = iter -> fore;
   return (iter -> data);
}