// DELList.H
// JR 9/23/95   members
//    9/27/95   merged with old (8/19/95) DEList.H which included DELinListIterator
//    10/16/95  Now derived from new LinList<T>.
//		Fixed "substitute" (list for list).
//		Tested all DELList functions.
//		Iterator and Browser still not checked thoroughly!
//    10/17/95	Browser tested.
//		Fixed problem in Iterator and Browser operator=
//		Iterator tested.
//	4/13/96	Deleted backtracks(). (Not used anywhere.)

#ifndef DELLIST_H
#define DELLIST_H

#include "DE.H"
#include "LinList.H"
#include "Boolean.H"
#include <assert.h>
//#include <iostream.h>
#include <iostream>
using namespace std;


// This is an LinList of DirectedEdges, with some special properties.
//	10/25/95  Added constructor
//		  DELList(DE first,const CircList<DE>& L).

class DELList: public LinList<DE>
{
//	friend ostream& operator << ( ostream& out, const LinList<DE>& L)

	public:
		DELList()
		: LinList<DE>()
		{}
		DELList(const DE& e1)
		: LinList<DE>(e1)
		{}
		DELList(const DE& e1,const DE& e2)
		: LinList<DE>(e1,e2)
		{}
		DELList(const DE& e1,const DE& e2,const DE& e3)
		: LinList<DE>(e1,e2,e3)
		{}
		DELList(const LinList<DE>& L)
		: LinList<DE>(L)
		{}
		DELList(const DE& first,const CircList<DE>& L)
		: LinList<DE>(first,L)
		{}
	        ~DELList()
		{}
		DELList& rename( DE deOld, DE deNew );
		DELList& substitute( DE e, const DELList& L );
		DELList& substitute( const DELList& oldL, const DELList& newL );
// (see LinList)	DELList commonLeadingSublist( const DELList& l1, const DELList& l2 );
		DELList bar() const;
		DELList& negate();
};


DELList& DELList::rename( DE deOld, DE deNew )
{	
	LinListIterator<DE> i(*this);
	for( i.init(); i.ok(); ++i )
	{   if(i.ahead()==deOld)
               i.replacef(deNew);
	    else if(i.ahead()==deOld.bar())
               i.replacef(deNew.bar());
  	}
	return *this;
}


ostream& operator << (ostream& out, const DELList& s)
{         out << "( ";
          LinListBrowser<DE> i(s);
	  for(i.init(); i.ok(); ++i )
                out << i.ahead() << " ";
          out << ") ";
	  return out;
}

///////////////////////////////////////////////////////////////////////

class DELListIterator
			// This has analogs of all the member functions
			// of LinListIterator<DE>, the difference being
			// that it will iterate over the negation of
			// an image when asked.
{
   private:
	Boolean positive;
	LinListIterator<DE> li;
	LinListReverseIterator<DE> rli;

   public:
	DELListIterator(LinList<DE>&);  	        // constructor
//	DELListIterator(LinList<DE>&,Boolean pos); // constructor
	DELListIterator::DELListIterator(LinList<DE>& s, char bORf);
       ~DELListIterator() {}                     // destructor
	void init();                            // initializer	 	       	
	DELListIterator& operator=(int n);     	// initialize with offset
	Boolean ok();                           // test for at end
        DELListIterator& operator++();         	// step forward over one node
        DELListIterator& operator--();         	// step backward over one node
        DE ahead() const;                       // data (not ref!) in node ahead
        DE behind() const;                   	// data (not ref!) in node behind
	void insertf(DE t);             	// insert new node ahead
	void insertb(DE t);          	// insert new node behind
	void replacef(DE t);         	// replace data in node ahead
	void replaceb(DE t);         	// replace data in node behind
	void deletef();                      	// delete node ahead
	void deleteb();                      	// delete node behind

   friend class DELListBrowser;
};



//==== DELListIterator implementation =======================================


//    DELListIterator::DELListIterator(LinList<DE>& s, Boolean pos)
//       : positive(pos),  li(s), rli(s)
//    {}

      DELListIterator::DELListIterator(LinList<DE>& s, char bORf)
         : positive(bORf=='f' ? 1 : 0),  li(s), rli(s)
      {}

      DELListIterator::DELListIterator(LinList<DE>& s)   // constructor
         : positive(1), li(s), rli(s)
      {}


      void DELListIterator::init()          // initialization
      {                                    // Can also use  =0
	if(positive) li.init();
	else         rli.init();
      }

      DELListIterator& DELListIterator::operator=(int n)
      {                                       // offset initialization
	assert(n>=0);
	if(positive)
	{
		li.init();
		while(n) {assert(li.ok());++li; n--;}
	}
	else
	{
		rli.init();
		while(n) {assert(rli.ok());++rli; n--;}
	}
        return *this;
      }


      DELListIterator& DELListIterator::operator++()
      {
	  if(positive) ++li;
	  else	       ++rli;
          return *this;
      }


      DELListIterator& DELListIterator::operator--()
      {
	  if(positive) --li;
	  else	       --rli;
          return *this;
      }


      Boolean DELListIterator::ok()
      {
		if(positive) return li.ok();
		else         return rli.ok();
      }


      DE DELListIterator::ahead() const       	// JR 8/26/95
						// Return type changed to DE
						// from DE& because in case
						// not positive, we'd be
						// returning a ref to a
						// temporary object.
      {
 		if(positive) return li.ahead();
	        else         return rli.ahead().bar();
      }


      DE DELListIterator::behind() const
      {
 		if(positive) return li.behind();
		else         return rli.behind().bar();
      }


      void DELListIterator::replacef(DE t)
      {
 		if(positive) li.replacef(t);
	        else	     rli.replacef(t.bar());
      }


      void DELListIterator::replaceb(DE t)
      {
 		if(positive) li.replaceb(t);
	        else	     rli.replaceb(t.bar());
      }

      void DELListIterator::insertf(DE t)
      {
          if(positive) li.insertf(t);
	  else         rli.insertf(t.bar());
      }


      void DELListIterator::insertb(DE t)
      {
          if(positive) li.insertb(t);
	  else         rli.insertb(t.bar());
      }

      void DELListIterator::deletef()
      {
          if(positive) {  li.deletef(); }
	  else         { rli.deletef(); }
      }

      void DELListIterator::deleteb()
      {

          if(positive) li.deleteb();
	  else         rli.deleteb();
      }


///////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////

class DELListBrowser
			// This has analogs of all the member functions
			// of LinListBrowser<DE>, the difference being
			// that it will browse over the negation of
			// an image when asked.
{
   private:
	int positive;
	LinListBrowser<DE> li;
	LinListReverseBrowser<DE> rli;

   public:
	DELListBrowser(const LinList<DE>&);  	        // constructor
	DELListBrowser(const LinList<DE>&,Boolean pos);   // constructor
	DELListBrowser(const DELListBrowser& b);     	// copy constructor
	DELListBrowser(const DELListIterator& i);       // copy constructor
       ~DELListBrowser() {}                     // destructor
	void init();                            // initializer	 	       	
	DELListBrowser& operator=(int n);     	// initialize with offset
	Boolean ok();                           // test for at end
        DELListBrowser& operator++();         	// step forward over one node
        DELListBrowser& operator--();         	// step backward over one node
        DE ahead() const;                       // ref to data in node ahead
        DE behind() const;                   	// ref to data in node behind

};



//==== DELListBrowser implementation =======================================


      DELListBrowser::DELListBrowser(const LinList<DE>& s, Boolean pos)
         : positive(pos),  li(s), rli(s)
      {}

      DELListBrowser::DELListBrowser(const LinList<DE>& s)   // constructor
         : positive(1), li(s), rli(s)
      {}

      DELListBrowser::DELListBrowser(const DELListBrowser& b)   // copy constructor
         : positive(b.positive),li(b.li),rli(b.rli)
      {}
      DELListBrowser::DELListBrowser(const DELListIterator& i)   // copy constructor
         : positive(i.positive),li(i.li),rli(i.rli)
      {}


      void DELListBrowser::init()          // initialization
      {                                    // Can also use  =0
	if(positive) li.init();
 	else	     rli.init();
      }

      DELListBrowser& DELListBrowser::operator=(int n)
      {                                       // offset initialization
	assert(n>=0);
	if(positive)
	{
		li.init();
		while(n) {assert(li.ok());++li; n--;}
	}
	else
	{
		rli.init();
		while(n) {assert(rli.ok());++rli; n--;}
	}
        return *this;
       }


      DELListBrowser& DELListBrowser::operator++()
      {
	  if(positive) ++li;
	  else	       ++rli;
          return *this;
      }


      DELListBrowser& DELListBrowser::operator--()
      {
	  if(positive) --li;
	  else	       --rli;
          return *this;
      }


      Boolean DELListBrowser::ok()
      {
		if(positive) return li.ok();
		else	     return rli.ok();
      }


      DE DELListBrowser::ahead() const       	// JR 8/26/95
						// Return type changed to DE
						// from DE& because in case
						// not positive, we'd be
						// returning a ref to a
						// temporary object.
      {
 		if(positive) return li.ahead();
	        else         return rli.ahead().bar();
      }


      DE DELListBrowser::behind() const
      {
 		if(positive) return li.behind();
		else         return rli.behind().bar();
      }










// 9/23/95 Functions requested by Qi:

DELList& DELList::substitute( DE e, const DELList& L )
{
        // Substitute L for each occurrence of e
        //     and Lbar for each occurrence of ebar

        DELList Lbar(L.bar());
        DE      ebar=e.bar();
        LinListBrowser<DE> iL(L);
        LinListBrowser<DE> iLb(Lbar);

        LinListIterator<DE> i(*this);
        for( i.init(); i.ok(); )
        {
                if( i.ahead()==e )
                {
                        i.deletef();
                        i.insertb(L);
                }
                else if( i.ahead()==ebar )
                {
                        i.deletef();
                        i.insertb(Lbar);
                }
                else
                {
                        ++i;
                }
        }
	return *this;
}

DELList& DELList::substitute( const DELList& oldL, const DELList& newL )
{
        // Substitute newL for each occurrence of oldL
        //     and newLbar for each occurrence of oldLbar

        DELList orig(*this);

        DELList oldLbar=oldL.bar();
        DELList newLbar=newL.bar();

        assert( (oldLbar!=oldL) || (newL==newLbar) );
        //  the substitution is not unique otherwise.

        LinListBrowser<DE> o(oldL);
        LinListBrowser<DE> n(newL);

        LinListBrowser<DE> ob(oldLbar);
        LinListBrowser<DE> nb(newLbar);

        int olen=oldL.length();
        int nlen=newL.length();

        LinListIterator<DE> i(*this);
        for( i.init(); i.ok(); )
        {
                LinListIterator<DE> scout(i);
                int match=1;
                for( o.init(); o.ok(); ++o,++scout )
                {
                        if( (!scout.ok()) || o.ahead()!=scout.ahead() )
                        {       match=0;
                                break;
                        }
                }
                if(match)
                {
                        for(o.init();o.ok();++o)
                        {
                                i.deletef();
                        }
			i.insertb(newL);
                }
                else
                {
                        match=1;
                        LinListIterator<DE> scout2(i);
                        for( ob.init(); ob.ok(); ++ob,++scout2 )
                        {
                                if( (!scout2.ok()) || ob.ahead()!=scout2.ahead() )
                                {       match=0;
                                        break;
                                }
                        }
                        if(match)
                        {
                                for(ob.init();ob.ok();++ob)
                                {
                                        i.deletef();
                                }
				i.insertb(newLbar);
                        }
                        else
                        {
                                ++i;
                        }
                }
        }
	return *this;
}


DELList DELList::bar()	const		// create the negative of a DELList
{
	DELList tmp;
	LinListBrowser<DE> i(*this);
	for(i.init();i.ok();++i) tmp.prepend(i.ahead().bar());
	return tmp;
}

#endif
