// Step6.C
// Bestvina-Handel Step 6, p 126.
//      JR
//      12/8/95 Begun.
//      3/4/96  Rewritten.
//              Getting nonsensical error messages from compiler.
//	3/5/96  Was referencing the superseded CList instead of CircList.
//		Compiled. Ran on homeo2.dat, where it does nothing.
//              Ran on homeo4.dat, which does not satisfy Lemma 4.1.2(2),
//		so P gets altered and the safety check causes exit.
//		Need valid example for proper testing.
//	4/22/96 Flaw in BH algorithm identified? ( -1 -1 3 2 )
//		A folding in step 6 can cause Lemma 4.2.1 to fail
//		to be satisfied.
//		Will fix by popping out and going back to the top
//		of the main loop if and when a single folding is done
//		here.

#include "Set.H"

Boolean Homeo::step6()
{
cout << "  In step 6," << endl;

        Set<Name> P(theNameManager.periphery());

        // Search them all in turn for the common derivative of
        // a pair of edges E0,E1 incident on the same vertex.

	// IMPORTANT: Needs to be called as 
	//					while(step6());


        Set<Name> PeeI(P);             // Start with PeeI=P
        Boolean somethingHappened=0;
	int icounter=0;

        while(!(PeeI.isEmpty()))
        {
cout << "    P_" << icounter << " is " << PeeI << "." << endl;
                // Search for a pair of edges E0,E1 with common derivative in PeeI
                // fold them as much as possible.
                // Note that (by Lemma 4.2.1(2) neither E0 nor E1 is in PeeI

		// If Step6 is used appropriately, the peripheral subgraph
		// should not be altered by it. Let's put in a (temporary)
		// safety check:

		Set<Name> currentP(theNameManager.periphery());
cout << "       P=" << P;
cout << "currentP=" << currentP;
		assert(P==currentP);

                Boolean didFolding=0;
cout << "Top of main loop in Step6" << endl;
cout << PeeI << endl;
cout << (*this) << endl;

                SetBrowser<Vertex> iv(theGraph);
                for(iv.init();iv.ok();iv.advance())
                {
cout << "  Top of vertex loop" << endl;
cout << "  " << iv.current() << endl;

                       CircListBrowser<DE> ie(iv.current());
                       for(ie.init();ie.ok();++ie)
                       {
                            DE E0=ie.behind();
                            DE E1=ie.ahead();
                            DE dgE0=theMap.derivative(E0);
cout << "    Looking at derivatives of edges " << E0 << ", " << E1 << endl;
                            if(dgE0==theMap.derivative(E1))
                            {
cout << "      ... equal" << endl;
                                  if(PeeI.has(dgE0.name()))
                                  {
                                       // I2 is not satisfied.
                                       // Fold E0,E1 as much as possible.
                                       DE newEdge=foldMany(E0,E1);
cout << "      Folding edges " << E0 << ", " << E1 << 
	", creating new edge " << newEdge << "," << endl;                                                        
                                       somethingHappened=1;
                                       didFolding=1;
                                  
                                       break;      // (out of for loop)
                                  }
                            }
	
                       }
		       if(didFolding) break;
                }

                if(!didFolding)
                {
                     // Increment i, i.e.,
                     // add to PeeIPlus1 all the edges in pre-P that get mapped to PeeI
cout << "  Incrementing i" << endl;
		     icounter++;
                     Set<Name> PeeIPlus1;
		     Set<Name> notP(theNameManager.edges());
		     notP -= P;
                     SetBrowser<Name> i(notP);
                     for(i.init();i.ok();i.advance())
                     {
			     Set<Name> S=theMap.namesInImageOf(DE(i.current(),0));
                             if(PeeI.contains(S))
                                     PeeIPlus1.add(i.current());
                     }
                     PeeI = PeeIPlus1;
                }
		else return 1;	// Added 4/22/96 to fix problem in algorithm.
        }
cout << "    P_" << icounter << " is " << PeeI << "." << endl;
if(!somethingHappened) cout << "    No folding was done." << endl;
        return somethingHappened;
}