#include <fstream.h>
#include "graph.h"



Graph::Graph()
{
 // out = new ofstream( "graph", ios::app );
}

void Graph::append( Line* nl )
{
  lineList.append( nl );
}

void Graph::remove( Line* nl )
{
  for( lineList.first(); !lineList.isLast(); lineList.next() )
  {
    if( nl == lineList.retrieve() )
      lineList.remove();
  }
}

int  Graph::isEuler( void )
{
   if( isZusammenhaengend() )
     return _makePositionList();
   else
   {
     return NICHTZUSAMMENHAENGEND;
   }
}

int  Graph::isZusammenhaengend( void )
{
  int ret = 1;
  int cont = 1;
  LineList ll1 = lineList;
  LineList ll2;

  // es wird solange ein Linie an ll angehaengt, bis keine Line mehr uebrig ist
  // Bedingung: Linie hat einen gemeinsamen Punkt mit den schon eingefuegten
  //            ( und ist noch nicht marked() )

  for( ll1.first(); !ll1.isLast(); ll1.next() )
  {
    ll1.retrieve()->unmark();
  }

  // mit einer Line beginnen
  if( ll1.isEmpty() )
    return 0;

  ll1.first();
  Line* l = ll1.retrieve();
  ll2.append( l );
  ll1.remove();

  while( !ll1.isEmpty() && cont ) // solange noch Linien zur Verfuegung stehen
  {                               // bzw. eine passende gefunden wurde
    cont = 0; // die Linie kann nicht angefuegt werden, so dass
              // der Graph zusammenhaenged bleibt!

    for( ll1.first(); !ll1.isLast(); ll1.next() )
    {
      // alle Linien durchgehen und angfuegen, so dass
      // der Graph zusammenhaengend bleibt.
      Line* l1 = ll1.retrieve();
      CPosition sp1( l1->getX(), l1->getY() );
      CPosition ep1( l1->getX1(), l1->getY1() );

      for( ll2.first(); !ll2.isLast(); ll2.next() )
      { // jede schon eingefuegte Linie testen
        Line* l2 = ll2.retrieve();
        CPosition sp2( l2->getX(), l2->getY() );
        CPosition ep2( l2->getX1(), l2->getY1() );

        if( (sp1 == sp2 ) || ( sp1 == ep2 )
         || ( ep1 == sp2 ) || ( ep1 == ep2 ) )
        {
          ll1.remove();
          ll2.append( l1 );
          cont = 1;
          break;
        }
      }
    }
    if( cont == 0 )
      break;
  }
  // checken ob alle Linien eingefuegt wurden
  if( ll1.isEmpty() )
    ret = 1; // graph ist zusammenhaengend
  else
    ret = 0; // graph ist nicht zusammenhaengend

  return ret;
}

// gibt die noch nicht gekennzeichneten angrenzenden Kanten des Punktes zurueck
LineList* Graph::_getSuccessors( Position cp )
{
  LineList *ll = new LineList;

  for( lineList.first(); !lineList.isLast(); lineList.next() )
  {
    Line* l=lineList.retrieve();

    if( l->isMarked() )
      continue;

    Position sp( l->getX(), l->getY() );
    Position ep( l->getX1(), l->getY1() );

    if( sp == cp )
    {
      ll->append(l);
    }
    else if( ep == cp )
    {
      l->mirror();
      ll->append(l);
    }
  }
  return ll;
}

// sortiert die Linien so, dass sie in einem Zug gemalt werden koennen
// Rueckgabe: 0 wenn es geht, sonst 1
int Graph::sort( Position cp )
{
  switch( isEuler() )
  {
    case EULERKREIS:
      break;
    case EULERWEG:
      break;
    default: // Figure ist nicht in einem Zug malbar, also nicht abspeichern
      return 1;
  }

  for( lineList.first(); !lineList.isLast(); lineList.next() )
  {
    lineList.retrieve()->unmark();
  }

  sortList.empty();

  if( _sort( cp ) == READY )
  {
    lineList = sortList;
    return 0;
  }
  return 1;
}

int Graph::_sort( Position cp )
{
  LineList* ll = _getSuccessors( cp );
  ll->last();

  if( ll->isEmpty() )
  { // keine Nachfolger mehr da -> entweder ist der Graph ganz durchlaufen
    // worden ( alle Linien sind marked() ), oder nicht
    // falls nicht: muss weiter versucht werden einen zusammenhaengenden
    // Weg zu finden
    //*out << "ll->isEmpty()" << endl;
    for( lineList.first(); !lineList.isLast(); lineList.next() )
    {
      if( !( lineList.retrieve()->isMarked() ) )
      {
        return NOTREADY;
      }
    }
    return READY;
  }

  ll->last();

  // eine Kante auswaehlen und weiter suchen
  for( ll->first(); !ll->isLast(); ll->next() )
  {
    Line* l = ll->retrieve();
    Position cp( l->getX1(), l->getY1() );
    l->mark();
    sortList.append(l);
    if( _sort( cp ) == READY )
    {
      l->unmark();
      delete ll;
      return READY;
    }
    sortList.remove(l);
    l->unmark();
  }
  delete ll;
  return NOTREADY;
}
/*
// prueft ob der Punkt mehr als eine abgehende nicht markierte
// Kante hat
// Ruckgabewert 0, wenn <=1,
// Anzahl der moeglichen Kanten-1  sonst.
int Graph::_checkPosition( CPosition& cp )
{
  int ret = 0;
  for( cpList.first(); !cpList.isLast(); cpList.next() )
  {
    CPosition* ncp = cpList.retrieve();
    if( cp == *ncp )
    { // Position in Liste vorhanden
      ret = ncp->getCount();
      break;
    }
  }
  return ret;
}
*/
int  Graph::_makePositionList( void )
{
  cpList.emptyWithElementDelete();

  for( lineList.first(); !lineList.isLast(); lineList.next() )
  {
    Line* line = lineList.retrieve();
    CPosition *startPosition = new CPosition( line->getX(), line->getY() );
    CPosition *endPosition   = new CPosition( line->getX1(), line->getY1() );
    cpList.append( startPosition );
    cpList.append( endPosition );
  }
  return cpList.istEuler();
}

