------------------------------------------------------------------------------
--                                                                          --
--		            GraphADT simulation program                     --
--                                                                          --
--                          AUTHOR: Robert Walsh                            --
--                          DATE:   November 14, 1995                       --
--                          CLASS:  CSCI 375 - Fall - SCSU                  --
--                                                                          --
------------------------------------------------------------------------------

with TEXT_IO;
package INTEGER_IO is new TEXT_IO.INTEGER_IO(INTEGER);

with TEXT_IO, INTEGER_IO;
use TEXT_IO, INTEGER_IO;

with Graph;

procedure Prog4 is
	--WHAT:	Allows user to perform operations on a graph.  The program
	--provides a menu in which the user may select these operations from.
	--IN:	None
	--OUT:	None

type EdgeData is record
	From, To, Weight : INTEGER;
	end record;
subtype NodeData is CHARACTER;
function Less(X1, X2 : EdgeData) return BOOLEAN;
function Equal(X1, X2 : EdgeData) return BOOLEAN;
procedure PEdge(X : EdgeData);
procedure Extract(Data : in EdgeData; From, To, Weight : out INTEGER);
procedure Insert(Data : out EdgeData; To, Weight : in INTEGER);
procedure Print(Data : in NodeData);
          
package NewGraph is new Graph(EdgeData, NodeData, Less, Equal, PEdge,
			      Extract, Insert, Print);
use NewGraph;

  Graph : GraphADT;
  Quit : BOOLEAN := FALSE;
  Item : INTEGER;

  function Less(X1, X2 : EdgeData) return BOOLEAN is
	--WHAT:	Determines if the first number [X1] is less than the second [X2]. 
	--IN:	X1 [INTEGER] : The first number to be compared with X2.
	--	X2 [INTEGER] : The second number to be compared with X1.
	--OUT:	[BOOLEAN] : TRUE if X1<X2 otherwise FALSE.

  begin
    if (X1.To<X2.To) then return TRUE;
    else return FALSE;
    end if;
  end Less;

  function Equal(X1, X2 : EdgeData) return BOOLEAN is
	--WHAT:	Determines if the first number [X1] is equal to the second [X2].
	--IN:	X1 [INTEGER] : The first number to compare with X2.
	--	X2 [INTEGER] : The second number to compare with X1.
	--OUT:	[BOOLEAN] : TRUE is X1=X2 otherwise FALSE.

  begin
    if (X1.To=X2.To) then return TRUE;
    else return FALSE;
    end if;
  end Equal;

  procedure PEdge(X : EdgeData) is
 	--WHAT:	The linked list demands this procedure but I don't need it so I	
	--made it a null procedure to satisfy the compiler.
	--IN:	X [EdgeData] : The record which holds the data to be printed.
	--OUT:	None

  begin
    null;    -- LList package needs this function but I don't. So....
  end PEdge;

  procedure Extract(Data : in EdgeData; From, To, Weight : out INTEGER) is
	--WHAT: Extracts the To & Weight data from the EdgeData record and
	--puts them in their own separate variables.  This enables the graph to
	--use data which is hidden inside the EdgeData record.
	--IN:	Data [EdgeData] : The edge from which the To & Weight need to be known.
        --OUT:	To [INTEGER] : The node which the edge is entering.
	--	Weight [INTEGER] : The weight of the node.

  begin
    From := Data.From;
    To := Data.To;
    Weight := Data.Weight;
  end Extract;

  procedure Insert(Data : out EdgeData; To, Weight : in INTEGER) is
	--WHAT: Inserts the To & Weight data into the EdgeData record. This
	--enables the graph to use data which is hidden inside the EdgeData record.
	--IN:	Data [EdgeData] : The edge from which the To & Weight need to be known.
        --OUT:	To [INTEGER] : The node which the edge is entering.
	--	Weight [INTEGER] : The weight of the node.

  begin
    Data.To := To;
    Data.Weight := Weight;
  end Insert;

  procedure Print(Data : in NodeData) is
	--WHAT: Prints the data in type NodeData to the screen.
	--IN:	Data [NodeData] : The Data to be printed.
	--OUT:  None
  begin
    PUT(Data);
  end Print;
  
  procedure Title is
	--WHAT: Prints the programs title to the screen.
	--IN:	None
	--OUT:  None
  begin
    NEW_LINE(2);
    PUT_LINE("*****  ****   ***  ****  *   *");
    PUT_LINE("*      *   * *   * *   * *   *");
    PUT_LINE("*  *** ****  ***** ****  *****");
    PUT_LINE("*   *  *   * *   * *     *   *");
    PUT_LINE("*****  *   * *   * *     *   *");
    PUT_LINE("A Graph ADT simulation program");
    NEW_LINE(2);    
  end Title;

  procedure PrintMenu is
  	--WHAT:	Prints the programs menu to the screen.
	--IN: 	None
	--OUT:  None
  begin
    NEW_LINE;
    PUT_LINE("***************************");
    PUT_LINE("1. Add a node              ");
    PUT_LINE("2. Add an edge             ");
    PUT_LINE("3. Remove an edge          ");
    PUT_LINE("4. Breadth first search    ");
    PUT_LINE("5. Create min spanning tree");
    PUT_LINE("6. Quit                    ");
    PUT_LINE("***************************");
    NEW_LINE(2);
  end PrintMenu;

  procedure AddNode(G : in out GraphADT) is
	--WHAT:	Prompts user for node data and waits for input.  After user
	--inputs data a node is added to the graph which contains the user
	--inputed data. 
	--IN:	G [GraphADT] : A graph which will have a node added to it.
	--OUT:	G [GraphADT] : The graph with the node (with data) added.

  Success : BOOLEAN;
  Data : NodeData;

  begin
    PUT("What is the data [CHARACTER] for this node:");
    GET(Data);
    AddNode(G, Data, Success);
    if not Success then 
      PUT_LINE("Operation failed -- Graph is full"); 
      NEW_LINE(2);
    end if;
  NEW_LINE(2);
  end AddNode;

  procedure AddEdge(G : in out GraphADT) is
	--WHAT:	Adds an edge to the graph.  First it prompts the user for the
	--endpoints (From & To nodes) and the edge weight. Then, the data is 
	--assigned appropriately and the coresponding edge is added to the
	--graph.
	--IN:	G [GraphADT] : A graph which will have an edge added.
	--OUT:	G [GraphADT] : The graph with the edge added.

  Success : BOOLEAN := FALSE;
  Data : EdgeData;

  begin
    PUT("From:");   GET(Data.From);
    PUT("To:");     GET(Data.To);
    PUT("Weight:"); GET(Data.Weight);
    AddEdge(G, Data.From, Data.To, Data, Success);
    if Success then
      PUT_LINE("The edge was added successfully");
    else
      PUT_LINE("The edge failed to be added");
    end if; 
    NEW_LINE(2);
  end AddEdge;

  procedure RemEdge(G : in out GraphADT) is
	--WHAT: Removes an edge from the graph.  The endpoints (From and To nodes)
	--will be requested first.  Then, the coresponding edge will be removed.
	--IN:	G [GraphADT] : A graph which needs an edge removed.
	--OUT:	G [GraphADT] : The graph with the edge removed.

  Success : BOOLEAN := FALSE;
  Data : EdgeData;
  begin
    PUT("From:");
    GET(Data.From);
    PUT("To:");
    GET(Data.To);
    RemEdge(G, Data.From, Data.To, Data, Success);
    if Success then
      PUT_LINE("The edge was deleted successfully");
    else
      PUT_LINE("The edge failed to be deleted");
    end if; 
    NEW_LINE(2);
  end RemEdge;

  procedure MSTree(G : in GraphADT) is
	--WHAT: Creates a minimm spanning tree.  Then, it calls BFS (which will
	--give a print out of the data in the BFS order).
	--IN:	G [GraphADT] : A graph to make a MST of.
	--OUT:	None

  MSTG : GraphADT;
  begin
    Create(MSTG);
    MST(G, MSTG);
    BFS(MSTG);
  end MSTree;

begin
  Create(Graph);
  Title;
  while (Quit=FALSE) loop  
    PrintMenu;
    Get(Item);
    case Item is
      when 1	  => AddNode(Graph);
      when 2	  => AddEdge(Graph);
      when 3 	  => RemEdge(Graph);
      when 4	  => BFS(Graph);
      when 5 	  => MSTree(Graph);
      when 6      => Quit:=TRUE;
      when others => PUT_LINE("That is not a valid menu item.");
    end case;
  end loop;
end Prog4;