<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
(*
 * Search: functorized code for BFS, DFS and IDS
 * Copyright (C) 2003 Jean-Christophe FILLIATRE
 * 
 * This software is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License version 2, as published by the Free Software Foundation.
 * 
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * 
 * See the GNU Library General Public License version 2 for more details
 * (enclosed in the file LGPL).
 *)

(*s Search algorithms, presented both functionally and imperatively. *)

(*s Functional search *)

module type FunctionalProblem = sig

  (* states *)
  type state
  val success : state -> bool

  (* moves *)
  type move
  val moves : state -> (move * state) list

  (* visited states are put in a hash table using function [mark] *)
  type marked_state
  val mark : state -> marked_state option

end

(* [search s] searches for a successful state starting from state [s];
   if there is such a state, it returns it, together with the path from [s];
   otherwise, it raises [Not_found]. *)

(* Depth-first search *)
module FunctionalDFS(P : FunctionalProblem) : sig
  val search : P.state -> P.state * P.move list
end

(* Breadth-first search *)
module FunctionalBFS(P : FunctionalProblem) : sig
  val search : P.state -> P.state * P.move list
end

(* Iterative deepening search *)
module FunctionalIDS(P : FunctionalProblem) : sig
  val search : P.state -> P.state * P.move list
end

(*s Imperative search *)

module type ImperativeProblem = sig

  (* the state is imperative *)
  val success : unit -> bool

  (* moves *)
  type move
  val moves : unit -> move list
  val do_move : move -> unit
  val undo_move : move -> unit

  (* visited states are put in a hash table using function [mark] *)
  type marked_state
  val mark : unit -> marked_state option

end

(* [search ()] searches for a successful state starting from the current state;
   if there is such a state, it returns the path from the initial state;
   otherwise, it raises [Not_found]. *)

(* Depth-first search *)
module ImperativeDFS(P : ImperativeProblem) : sig
  val search : unit -> P.move list
end

(* Breadth-first search *)
module ImperativeBFS(P : ImperativeProblem) : sig
  val search : unit -> P.move list
end

(* Iterative deepening search *)
module ImperativeIDS(P : ImperativeProblem) : sig
  val search : unit -> P.move list
end