// file: $isip/doc/examples/class/search/search_example_00/example.cc
// version: $Id: example.cc 7869 2002-03-09 21:48:58Z wang $
//

// isip include files
//
#include <Trace.h>
#include <DiGraph.h>

// this example generates a word graph like this:
//
/*                                   */
/*        /-> boy  -> runs  ->\      */
/*  START                     TERM   */
/*        \-> girl -> swims ->/      */
/*                                   */
//
// and it finds all paths throug this graph


// main program starts here
//
int main(int argc, const char** argv) {

  // generate word symbols
  //
  Vector<SearchSymbol> word_syms(4);
  word_syms(0).assign(L"boy");
  word_syms(1).assign(L"runs");
  word_syms(2).assign(L"girl");
  word_syms(3).assign(L"swims");

  // assing a search level to each symobl
  //
  SearchLevel slev;
  slev.setSymbolTable(word_syms);

  Vector<SearchNode> search_nodes(4);
  for(long i = 0; i<4; i++) {
    search_nodes(i).setSearchLevel(&slev);
    search_nodes(i).setSymbol(word_syms(i));
  }

  // generate a graph
  //
  DiGraph<SearchNode> graph;

  // START->boy->runs>TERM
  //
  GraphVertex<SearchNode>* vertex_0 = graph.insertVertex(&search_nodes(0));
  graph.insertArc(graph.getStart(), vertex_0);
  GraphVertex<SearchNode>* vertex_1 = graph.insertVertex(&search_nodes(1));
  graph.insertArc(vertex_0, vertex_1);
  graph.insertArc(vertex_1, graph.getTerm());
  
  // START->girl->swims->TERM
  //
  GraphVertex<SearchNode>* vertex_2 = graph.insertVertex(&search_nodes(2));
  graph.insertArc(graph.getStart(), vertex_2);
  GraphVertex<SearchNode>* vertex_3 = graph.insertVertex(&search_nodes(3));
  graph.insertArc(vertex_2, vertex_3);
  graph.insertArc(vertex_3, graph.getTerm());

  // create the start trace
  //
  Trace* tmp_trace = new Trace();
  tmp_trace->setBackPointer((Trace*)NULL);
  tmp_trace->getHistory()->setAllocationMode(DstrBase::USER);
  tmp_trace->getHistory()->push((Context*)graph.getStart());

  // add the start trace to the list
  //
  DoubleLinkedList<Trace> trace_list;
  trace_list.setAllocationMode(DstrBase::USER);
  trace_list.insertLast(tmp_trace);

  // declare the list of the final hypotheses
  //
  DoubleLinkedList<Trace> final_hypotheses_list;

  // declare useful variables
  //
  GraphVertex<SearchNode>* curr_vert;
  Trace* curr_trace;
  Trace* next_trace;
  History* curr_hist;

  // loop over list of traces (paths) until it is not empty
  //
  trace_list.gotoFirst();
  while(!(trace_list.length() < 1)) {

    // get next trace off of the list
    //
    curr_trace = trace_list.getCurr();
    
    // get the vertex of the trace
    //
    curr_hist = curr_trace->getHistory();
    curr_vert = (GraphVertex<SearchNode>*)curr_hist->peek();

    if (curr_vert->getItem() == &DiGraph<SearchNode>::TERM_OBJ) {

      // if the trace reached end of the graph, remove it
      //
      trace_list.removeFirst(curr_trace);
    }
    else {

      // get the children of that trace
      //
      for (boolean more_paths = curr_vert->gotoFirst(); more_paths;
	   more_paths = curr_vert->gotoNext()) {

	// create a new traces
	//
	next_trace = new Trace(*curr_trace);

	GraphArc<SearchNode>* tmp_arc = curr_vert->getCurr();
      
	// update the history of each child
	//
	next_trace->getHistory()->setAllocationMode(DstrBase::USER);
	next_trace->getHistory()->push((Context*)tmp_arc->getVertex());
	
	// add each child to the back of the list
	//
	trace_list.insertLast(next_trace);

	// print the message
	//
	String message(L"trace generated from: ");
	SearchSymbol sym;
	if(curr_vert->getItem() == &DiGraph<SearchNode>::START_OBJ) {
	  sym.assign(L"START");
	}
	else {
	  curr_vert->getItem()->getSymbol(sym);
	}
	message.concat(sym);
	message.concat(L" to: ");
	if(tmp_arc->getVertex()->getItem() == &DiGraph<SearchNode>::TERM_OBJ) {
	  sym.assign(L"TERM");

	  // store this trace in the final hypotheses list
	  //
	  final_hypotheses_list.insertLast(next_trace);
	}
	else {
	  tmp_arc->getVertex()->getItem()->getSymbol(sym);
	}
	message.concat(sym);
	Console::put(message);
      }

      // remove the trace
      //
      trace_list.removeFirst(curr_trace);
    }

    // move to the first trace
    //
    trace_list.gotoFirst();
  }
  
  // print the final hypotheses
  //
  Console::put(L"\nThe final paths through the graph are:");
  
  for(boolean more_paths = final_hypotheses_list.gotoFirst();
      more_paths; more_paths = final_hypotheses_list.gotoNext()) {
    
    // reverse the history of the current trace (path)
    //
    curr_trace = final_hypotheses_list.getCurr();
    curr_trace->getHistory()->reverse();

    // loop through the history of trace end print it
    //
    String output;
    while (!curr_trace->getHistory()->isEmpty()) {
      SearchSymbol sym;
      GraphVertex<SearchNode>* temp = (GraphVertex<SearchNode>*)curr_trace->getHistory()->pop();
      if(temp->getItem() == &DiGraph<SearchNode>::START_OBJ) {
	    sym.assign(L"START");
	  }
      else if(temp->getItem() == &DiGraph<SearchNode>::TERM_OBJ) {
	    sym.assign(L"TERM");
      }
      else {
	temp->getItem()->getSymbol(sym);
	output.concat(L" ");
	output.concat(sym);
      }
    }
    Console::put(output);
  }
}