// JR    9/27/95
// 		  Mods by Qi.
// JR	10/18/95  Mods for new list classes, and testing.
//      10/19/95  Tested.
//		  The testing revealed a nastiness in CircListIterator::insert
//		  I worked around it in Vertex::replaceDE, but should consider
//		  changing CircListIterator.
//	10/25/95  Had to make const version of originOf.
//	10/26/95  Added member touching(const Set<Name>& s).
//      12/21/95  Added numberOfComponents(const Set<DE>& s).
//	 3/28/96  Added int nComponentsOf(Set<Name> S),
//	          and   Boolean edgeIncidentOnSet( Name n, Set<Name> S ).
//		  Didn't remember I already had numberOfComponents!
//	4/2/96	  Added and tested members leftTurn and rightTurn, which return
//		  the DE that constitutes a hard left or right turn at the 
//		  terminus of the given DE.
//	4/8/96	  Added Lk.
//	4/9/96	  Fixed bug in Lk.


#ifndef GRAPH_H
#define GRAPH_H

#include "Set.H"
#include "Vertex.H"
//#include <iostream.h>
#include <iostream>
using namespace std;
#include <assert.h>

class Graph: public Set<Vertex>
{
   public:
	Graph()
	: Set<Vertex>()
	{}
        ~Graph()
	{}
	void mergeAlong(DE e);
	Vertex& originOf(const DE& e);
	const Vertex& originOf(const DE& e) const;
	Set<Name> touching(const Set<Name>& s);

	int numberOfComponents(const Set<DE>& s);
	Boolean edgesMutuallyIncident(Name e,Name f) const;
	Boolean edgeIncidentOnSubgraph(Name e,const Set<Name>& s) const;

	LinList< Set<Name> > componentsOf(Set<Name> S) const;      // generateG0.c
	int nComponentsOf(Set<Name> S) const;		           // generateG0.c
	Boolean edgeIncidentOnSet( Name n, Set<Name> S ) const;    // generateG0.c
	void findFrontier( DE a, int depth, 
		DE e, const Set<Name>& G0i, CircList<DE>& Ai);	// frontier.c
	DE leftTurn(DE e);
	DE rightTurn(DE e);
	Set<DE> Lk(const Set<Name>& S) const;
//2002_12_27	friend ostream& operator << ( ostream& out, const Set<Vertex>& g);
//2002_12_27	friend istream& operator >> ( istream&  in,       Set<Vertex>& g);

   private:

};

DE Graph::leftTurn(DE e)
{
	DE ebar=e.bar();
	CircListBrowser<DE> i(originOf(ebar));
	i.init();
	while(i.ahead()!=ebar) ++i;
	++i;
	return i.ahead();	
}

DE Graph::rightTurn(DE e)
{
	DE ebar=e.bar();
	CircListBrowser<DE> i(originOf(ebar));
	i.init();
	while(i.ahead()!=ebar) ++i;
	return i.behind();	
}

void Graph::mergeAlong(DE e)
{
  assert(&originOf(e)!=&originOf(e.bar()));
  Vertex v1(originOf(e)), v2(originOf(e.bar()));
  remove(v1);
  remove(v2);
  v2.rotateToJustBeforeThe(e.bar());
  v2.popf();
  v1.replaceDE(e,v2);
  add(v1);
}
	
Vertex& Graph::originOf(const DE& e)
{
  SetIterator<Vertex> i(*this);
  for( i.init(); i.ok(); i.advance() )
  {
	if(i.current().isOriginOf(e))
      	{
		return i.current();
	}
  }
  cout << "No origin found in Graph for edge " << e << endl;
  int no_origin_of_edge_found_in_graph=0;
  assert(no_origin_of_edge_found_in_graph);
}

const Vertex& Graph::originOf(const DE& e) const
{
  SetBrowser<Vertex> i(*this);
  for( i.init(); i.ok(); i.advance() )
  {
//cout << "Looking for " << e << " in vertex " << i.current() << endl;
	if(i.current().isOriginOf(e))
      	{
		return i.current();
	}
  }
  Boolean No_vertex_found_that_is_origin_of_given_DE=0;
  assert(No_vertex_found_that_is_origin_of_given_DE);
}

Set<Name> Graph::touching(const Set<Name>& s)
{
	// Return the set of edges that are either
	//	either in s
	//	or are in a link that contains an element of s.
	
	Set<Name> tmp;
	SetBrowser<Name> i(s);
	for(i.init();i.ok();i.advance())
	{
		CircListBrowser<DE> j(originOf(DE(i.current(),0)));
		for(j.init();j.ok();++j) tmp.add(j.ahead().name());
		CircListBrowser<DE> k(originOf(DE(i.current(),1)));
		for(k.init();k.ok();++k) tmp.add(k.ahead().name());
	}
	return tmp;
}

int Graph::numberOfComponents(const Set<DE>& s)
{
	// Make a list of the edges
	LinList<DE> L;
	SetBrowser<DE> k(s);
	for(k.init();k.ok();k.advance()) L.append(k.current());
	
	int n=s.cardinality();
	int *comp=new int[n];		// component # of edge
	for(int ci=0;ci<n;ci++) comp[ci]=ci;

	LinListBrowser<DE> ie(L);
	LinListBrowser<DE> je(L);
	int i;
	int j;
	for(ie.init(),i=0;ie.ok();++ie,i++)
	{	for(je.init(),j=0;je.ok();++je,j++)
		{	if(edgesMutuallyIncident(
				ie.ahead().name(),je.ahead().name()))
			{
				// change all comp[j]'s to comp[i]'s
				int compi=comp[i];
				int compj=comp[j];
				for(int m=0;m<n;m++)
					if(comp[m]=compj) comp[j]=compi;
			}
		}
	}
	
	// count the components
	int ncomp=0;
	int highestyet=-1;
	for(int m=0;m<n;m++)
	{	if(comp[m]>highestyet)
		{	ncomp++;
			highestyet=comp[m];
		}
	}
	delete[] comp;
	return ncomp;
}

Boolean Graph::edgesMutuallyIncident(Name e,Name f) const
{
	CircListBrowser<DE> i(originOf(DE(e,0)));
	for(i.init();i.ok();++i)
		if(i.ahead().name()==f) return 1;
	CircListBrowser<DE> j(originOf(DE(e,1)));
	for(i.init();i.ok();++i)
		if(i.ahead().name()==f) return 1;
	return 0;
}

Boolean Graph::edgeIncidentOnSubgraph(Name e,const Set<Name>& s) const
{
	CircListBrowser<DE> i(originOf(DE(e,0)));
	SetBrowser<Name> is(s);
	for(is.init();is.ok();is.advance())
	{	
		Name n=is.current();
		for(i.init();i.ok();++i)
			if(i.ahead().name()==n) return 1;
	}
	return 0;
}

Set<DE> Graph::Lk(const Set<Name>& S) const 
{
			// Generate and return Lk( S, (*this) ).

			// First generate the set of vertices "in S".
	Set<DE> L;
	SetBrowser<Name> i(S);
	for(i.init();i.ok();i.advance())
	{
					// edges touching start of current
		CircListBrowser<DE> j(originOf(DE(i.current(),0)));
		for(j.init();j.ok();++j)
		{
			if(!S.has(j.ahead().name()))
				L.add(j.ahead());
		}
					// edges touching end of current
		CircListBrowser<DE> k(originOf(DE(i.current(),1)));
		for(k.init();k.ok();++k)
		{
			if(!S.has(k.ahead().name()))
				L.add(k.ahead());
		}
	}
	return L;
}



#endif