// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

///////////////////////////////////////////////////////////////////////////
// LINK: Generic Graph Tool and Class Library
//
//      Function name: Collection methods
//
//      Synopsis: Contains the implementations of the Collection and 
//		  Iterator methods.  See the document on Collections
//		  in the doc directory for a thorough discussion.
//		  A significant amount of the set and sequence code
//		  is actually located in the header file Collection.h
//		  This is because set and sequence are largely just
//		  "empty shells" that parameterized by implementation 
//		  type and mainly call the methods of the implementation.
//		  This file contains mainly the code for copy constructors,
//		  assignment operators, and iterator methods.
//
//      Description: Collections may be thought of as abstract objects
//		     that may be any kind of set or sequence.  The 
//		     purpose of the grouping is to allow various types
//		     of sets and sequences to interact with each other.
//		     "Collection" is an abstract base class, meaning that
//		     no Collection objects may be declared.  Rather, a 
//		     Collection pointer may point to and access the methods
//		     of any set or sequence.  This feature simplifies the
//		     implementation of graph primitive routines by allowing
//		     all types of edges to be thought of simply as 
//		     Collections.  
//
//      Creation: 1993 July 30, Jonathan W. Berry, berryj@cs.rpi.edu
//
//      Routines used: None.
//
//      Related files: Collection.h, List.h (since List is the default
//                     implementation.  If the default changes, the included
//		       file must change.)
//
//      Test suite: 
//
//      User documentation: see doc
//
//      Testing History:
//
//      Code Review:
//
//      Bugs and Deficiencies:
//
//////////////////////////////////////////////////////////////////////////////
#ifndef Sequence_CC
#define Sequence_CC

#include<LINK/basic/Array.h>

template <class Item, class Impl>
SequenceBase<Item, Impl>::SequenceBase()
{
	if (store->sortedQ())
		error("Attempt to use SequenceBase or Sequence object \n"
		      "with a sorted Container as the implementation.");
}

template <class Item, class Impl>
SequenceBase<Item, Impl>::SequenceBase(const SequenceBase<Item, Impl> &s)
{
    if (store->sortedQ())
		error("Attempt to use SequenceBase or Sequence object \n"
		      "with a sorted Container as the implementation.");
    if (&s == this)
        return;

    //((Container<Item>*)store)->decrRefCount();
    //if (((Container<Item>*)store)->getRefCount() == 0)
    //    delete store;

    delete store;
    store = s.store;
    //store->ref_count++;
    ((Container<Item>*)store)->incrRefCount();
}


template <class Item, class Impl>
SequenceBase<Item, Impl>::SequenceBase(const Collection<Item> &col)
{
    if (store->sortedQ())
		error("Attempt to use SequenceBase or Sequence object \n"
		      "with a sorted Container as the implementation.");
    Iterator<Item> get_next(&col);
    Item item; 
    while (get_next(item))
	append(item);
}

template <class Item, class Impl>
SequenceBase<Item, Impl>::SequenceBase(const Container<Item> &con)
{
    if (store->sortedQ())
		error("Attempt to use SequenceBase or Sequence object \n"
		      "with a sorted Container as the implementation.");
    Iterator<Item> get_next(&con);
    Item item; 
    while (get_next(item))
	append(item);
}


template <class Item, class Impl>
SequenceBase<Item, Impl>&
SequenceBase<Item,Impl>::operator=(const SequenceBase<Item,Impl>& seq)
{
    if (&seq == this)
	return *this;
    ((Container<Item>*)store)->decrRefCount(); 
    if (((Container<Item>*)store)->getRefCount() == 0)
	delete store;
    store = seq.store;
    ((Container<Item>*)store)->incrRefCount();
    return *this;
}


template <class Item, class Impl>
SequenceBase<Item, Impl>&
SequenceBase<Item,Impl>::operator=(const Collection<Item>& col)
{
    Iterator<Item> get_next(&col);
    Item item; 
    newStore();
    while (get_next(item))
	append(item);
    return *this;
}

template <class Item, class Impl>
void
SequenceBase<Item,Impl>::newStore()
{
    Impl* nstore = new Impl();
    ((Container<Item>*)nstore)->initRefCount(); 

    ((Container<Item>*)store)->decrRefCount(); 
    if (((Container<Item>*)store)->getRefCount() == 0)
	delete store;
    store = nstore;
    ((Container<Item>*)store)->initRefCount();
}

template <class Item, class Impl>
void
SequenceBase<Item,Impl>::newSequence(SequenceBase<Item,Impl> *seq)
{
    Item item;
    Impl* x = seq->store;
    Iterator<Item> get_next(x);

    if (((Container<Item>*)store)->getRefCount() > 1)  {
	newStore();
	while (get_next(item))
	    append(item);
    }
}


template <class Item, class Impl>
void
SequenceBase<Item,Impl>::insertBefore(Item e, Item after_item)
{
	ContainerNode *cn = store->search(after_item);
	if (cn != 0) {
		newSequence(this); 
		store->insertBefore(e, cn);
	}
}
	
template <class Item, class Impl>
void
SequenceBase<Item,Impl>::insertAfter(Item e, Item after_item)
{
	ContainerNode *cn = store->search(after_item);
	if (cn != 0) {
		newSequence(this); 
		store->insertAfter(e, cn);
	}
}

//template <class Item, class Impl>
//MSetBase<Item,DEFAULT_SET_IMPL<Item> >
//SequenceBase<Item,Impl>::unions(Collection<Item>& col)
//{
//    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
//    Iterator<Item> get_next1(this);
//    Iterator<Item> get_next2(&col);
//    Item item;
//    while (get_next1(item))
//      result.insert(item);
//    while (get_next2(item))
//      result.insert(item);
//    return result;
//}
//
//template <class Item, class Impl>
//MSetBase<Item,DEFAULT_SET_IMPL<Item> >
//SequenceBase<Item,Impl>::operator+(Collection<Item>& col)
//{
//    return unions(col);
//}
//
//template <class Item, class Impl>
//MSetBase<Item,DEFAULT_SET_IMPL<Item> >
//SequenceBase<Item,Impl>::intersection(Collection<Item>& col)
//{
//    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
//    Iterator<Item> get_next(this);
//    Item item;
//    int count, minFreq, temp;
//
//    while (get_next(item))
//       if (!result.memberQ(item)) {
//          minFreq = occurrences(item);
//          temp = col.occurrences(item);
//          if (minFreq > temp)
//            minFreq = temp;
//          for (count = 0; count < minFreq; count++)
//            result.insert(item);
//       }
//    return result;
//}
//
//
//template <class Item, class Impl>
//MSetBase<Item,DEFAULT_SET_IMPL<Item> >
//SequenceBase<Item,Impl>::operator^(Collection<Item>& col)
//{
//    return intersection(col);
//}
//
//template <class Item, class Impl>
//MSetBase<Item,DEFAULT_SET_IMPL<Item> >
//SequenceBase<Item,Impl>::difference(Collection<Item>& col)
//{
//    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
//    Iterator<Item> get_next(this);
//    Item item;
//    int count, monFreq;
//
//    while (get_next(item))
//      if (!result.memberQ(item))
//        {
//          monFreq = occurrences(item) - col.occurrences(item);
//          for (count = 1; count <= monFreq; count++)
//            result.insert(item);
//        };
//    return result;
//}
//
//
//template <class Item, class Impl>
//MSetBase<Item,DEFAULT_SET_IMPL<Item> >
//SequenceBase<Item,Impl>::operator-(Collection<Item>& col)
//{
//    return difference(col);
//}


template <class Item, class Impl>
ostream&
SequenceBase<Item,Impl>::display(ostream& os) const
{
    os << "<";
    Iterator<Item> get_next(this);
    Item i;
    Bool start = FALSE;
    while (get_next(i))
         if (!start) {
                ElementOps<Item>::displayItem(os, i);
                start = TRUE;
         } else {
                os << " ";
                ElementOps<Item>::displayItem(os, i);
        }
    os << ">";
    return os;
}


// Implemented by David Wagner


template <class Item, class Impl>
Item
SequenceBase<Item,Impl>::element (int i)
{
   Iterator<Item> iter (this);
   Item x;

   for (int j=0; j<i; j++)
   {
     iter(x);
   }

   return (x);
}
   
template <class Item, class Impl>
SequenceBase<Item,Impl>
SequenceBase<Item,Impl>::subsequence(int i, int j)
{	
   //SequenceBase<Item,Impl>* seq = new(SequenceBase<Item,Impl>);
   SequenceBase<Item,Impl> seq;

   if (j<i) return seq;

   for(int k=i; k<j; k++)
   {
      seq.append(this->element(k));
// old line was this->     seq->insert(this->element(k),k-i);
   }

   return(seq);
}

template <class Item, class Impl>
int
SequenceBase<Item,Impl>::search(SequenceBase<Item,Impl>* str)
{
  int len = str->size();
  int mylen= this->size();

  for(int i=0;i<mylen;i++)
  {
     if (this->subsequence(i,i+len)==*str) return (i);
  }

  return(-1);
}

/*
template <class Item, class Impl>
SequenceBase<Item,Impl>& 
SequenceBase<Item,Impl>::insert(Item char, int pos)
{
  if (pos > size()) { warning("Insert Location past end of Sequence");
                      return;}
  Impl * temp;
  temp = new (Impl);
  Iterator<Item> get_next(store);
  Item elt;
  for(int i=0;i<pos && get_next(elt);i++) {
     temp->insert(elt);
    }
  temp->insert(char);
  for(i=pos;get_next(elt);i++) {
     temp->insert(elt);
    }
  Iterator<Item> get_temp(temp);
  for(int j=0;get_temp(elt);j++) {
     store->insert(elt);
    }
  delete temp;  
  return this;
}    

template <class Item, class Impl>
SequenceBase<Item,Impl>&
SequenceBase<Item,Impl>::insert(SequenceBase<Item,Impl2> str, int pos)
{
  if (pos > size()) { warning("Insert Location past end of Sequence");
                      return;}
  Impl * temp;
  temp = new (Impl);
  Iterator<Item> get_next(store);
  Item elt;
  for(int i=0;i<pos && get_next(elt);i++) {
     temp->insert(elt);
    }
  Iterator<Item> get_str(str);
  Item * strchar;
  while( get_str(strchar) ) {  
    temp->insert(strchar);  }
  for(i=pos;get_next(elt);i++) {
     temp->insert(elt);
    }
  Iterator<Item> get_temp(temp);
  for(int j=0;get_next(elt);j++) {
     store->insert(elt);
    }
  delete temp;
  return this;
}    

template <class Item, class Impl>
SequenceBase<Item,Impl>&
SequenceBase<Item,Impl>::replace(Item char, int pos)
{
  if (pos > size()) { warning("Replace Location past end of Sequence");
                      return;}
  Impl * temp;
  temp = new (Impl);
  Iterator<Item> get_next(store);
  Item elt;
  for(int i=0;i<pos && get_next(elt);i++) {
     temp->insert(elt);
    }
  temp->insert(char);
  get_next(elt);
  for(i=pos;get_next(elt);i++) {
     temp->insert(elt);
    }
  Iterator<Item> get_temp(temp);
  for(int j=0;get_temp(elt);j++) {
     store->insert(elt);
    }
  delete temp;
  return this;
}

template <class Item, class Impl>
SequenceBase<Item,Impl>&
SequenceBase<Item,Impl>::(SequenceBase<Item,Impl2> str, int pos)
{
  if (pos > size()) { warning("Replace Location past end of Sequence");
                      return;}
  Impl * temp;
  temp = new (Impl);
  Iterator<Item> get_next(store);
  Item elt;
  for(int i=0;i<pos && get_next(elt);i++) {
     temp->insert(elt);
    }
  Iterator<Item> get_str(str);
  Item * strchar;
  while( get_str(strchar) ) {
    get_next(elt);
    temp->insert(strchar);  }
  for(i=pos;get_next(elt);i++) {
     temp->insert(elt);
    }
  Iterator<Item> get_temp(temp);
  for(int j=0;get_next(elt);j++) {
     store->insert(elt);
    }
  delete temp;
  return this;
}

template <class Item, class Impl> 
SequenceBase<Item,Impl>& 
SequenceBase<Item,Impl>::remove(int i) 
{ 
  if (pos > size()) { warning("Remove Location past end of Sequence"); 
                      return;} 
  Impl * temp;   
  temp = new (Impl); 
  Iterator<Item> get_next(store); 
  Item elt; 
  for(int i=0;i<pos && get_next(elt);i++) { 
     temp->insert(elt); 
    } 
  temp->insert(char); 
  get_next(elt); 
  for(i=pos;get_next(elt);i++) { 
     temp->insert(elt); 
    } 
  Iterator<Item> get_temp(temp); 
  for(int j=0;get_temp(elt);j++) { 
     store->insert(elt); 
    } 
  delete temp;   
  return this;
} 
 
template <class Item, class Impl> 
SequenceBase<Item,Impl>& 
SequenceBase<Item,Impl>::remove(int i,int j) 
{ 
  if (pos > size()) { warning("Remove Location past end of Sequence"); 
                      return;} 
  Impl * temp;   
  temp = new (Impl); 
  Iterator<Item> get_next(store);
  Item elt;
  for(int a=0;a<i && get_next(elt);a++) {
     temp->insert(elt);
    }
  Iterator<Item> get_str(str);
  Item * strchar;
  for(a=i;a<j;a++){
    get_next(elt); 
  }
  for(a=j;a<count() && get_next(elt);a++) {
     temp->insert(elt);
    }
  Iterator<Item> get_temp(temp); 
  for(int b=0;get_next(elt);b++) {
     store->insert(elt);
    }
  delete temp;
  return this;
}   

template <class Item, class Impl>
SequenceBase<Item,Impl>&
SequenceBase<Item,Impl>::union(Sequence<Item>& str) 
{
  Impl * temp;
  Iterator<Item> get_str(str);
  Iterator<Item> get_store(store);

  while(get_str(char)) temp->insert(char);
  while(get_store(char)) temp->insert(char);
  
  return temp;
}
  
*/

//
// constructors for an implementation of Sequence
//
//template <class Item>
//Sequence<Item>::Sequence(const Sequence<Item>& s)
//{
//    if (&s == this)
//        return;
//    store = s.store;
//    store->ref_count++;
//}
//
//
//template <class Item>
//Sequence<Item>::Sequence(const Collection<Item>& col)
//{
//    Iterator<Item> get_next(&col);
//    Item item;
//    while (get_next(item))
//        insert(item);
//}

//template <class Item>
//Sequence<Item>::Sequence(const Sequence<Item> &s)
//{
//    if (&s == this)
//        return;
//
//    //delete store;
//    ((Container<Item>*)store)->decrRefCount();
//    if (((Container<Item>*)store)->getRefCount() == 0)
//        delete store;
//
//    store = s.store;
//    //store->ref_count++;
//    ((Container<Item>*)store)->incrRefCount();
//}


//template <class Item>
//Sequence<Item>::Sequence(const Collection<Item> &col)
//{
//    Iterator<Item> get_next(&col);
//    Item item; 
//    while (get_next(item))
//	append(item);
//}

template <class Item>
Sequence<Item>&
Sequence<Item>::operator=(const Sequence<Item>& seq)
{
    if (&seq == this)
	return *this;
    ((Container<Item>*)store)->decrRefCount(); 
    if (((Container<Item>*)store)->getRefCount() == 0)
	delete store;
    //if (--store->ref_count == 0)
    //	delete store;
    store = seq.store;
    //store->ref_count++;
    ((Container<Item>*)store)->incrRefCount();
    return *this;
}


template <class Item>
Sequence<Item>&
Sequence<Item>::operator=(const Collection<Item>& col)
{
    Iterator<Item> get_next(&col);
    Item item; 
    newStore();
    while (get_next(item))
	append(item);
    return *this;
}
#endif