INTERFACE GDHistory;

(* History of solutions found by heuristic methods. *)

IMPORT Wr;

IMPORT CPUTime;

TYPE
  T = REF RECORD           (* Family history of a solution. *)
      prev: T;             (* History of its parent. *)
      inst: Instruction;   (* Instruction that created it from the parent. *)
      cost: Cost;          (* Cost of this instruction. *)
    END;
    (*
      The history of a drawing is a currently a directed tree, where
      each node points to a single parent (or NIL).  The edge
      represents the derivation of the current drawing from the
      parent by application of some instruction "inst".
      
      [Support should eventually be added for multiple-parent
      solutions, as required by genetic algorithms.] *)
      
TYPE
  Cost = CPUTime.T;  (* Cost of an operation or solution, in CPU seconds. *)

  Instruction = OBJECT
    METHODS
      toText(): TEXT;
        (*
          Returns a readable description of the instruction. *)
    END;

PROCEDURE Append(hs: T; inst: Instruction; cost: CPUTime.T): T;
  (*
    Appends a new instruction to the end of "hs", and returns
    the result. *)

PROCEDURE Write(wr: Wr.T; hs: T);

PROCEDURE CostToText(cost: Cost): TEXT;

END GDHistory.
(* Last edited on 2000-01-12 06:35:42 by stolfi *)