diff options
author | barras <barras@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2004-09-06 22:54:50 +0000 |
---|---|---|
committer | barras <barras@85f007b7-540e-0410-9357-904b9bb8a0f7> | 2004-09-06 22:54:50 +0000 |
commit | 82dfc9804315d0acac61f2fa603d7f181ed9dd44 (patch) | |
tree | 4573d0b0f6577abcadba92057287176f1f11e090 /lib/explore.ml | |
parent | 2a405677a527d71c403a173615bd9e2a0cd9c90b (diff) |
optimized the non-backtracking case
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@6066 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'lib/explore.ml')
-rw-r--r-- | lib/explore.ml | 18 |
1 files changed, 7 insertions, 11 deletions
diff --git a/lib/explore.ml b/lib/explore.ml index 9b0e0816c..51ff79e32 100644 --- a/lib/explore.ml +++ b/lib/explore.ml @@ -37,6 +37,7 @@ module Make = functor(S : SearchProblem) -> struct if S.success s then s else depth_first_many (S.branching s) and depth_first_many = function | [] -> raise Not_found + | [s] -> depth_first s | s :: l -> try depth_first s with Not_found -> depth_first_many l let debug_depth_first s = @@ -44,8 +45,8 @@ module Make = functor(S : SearchProblem) -> struct pp_position p; S.pp s; if S.success s then s else explore_many 1 p (S.branching s) and explore_many i p = function - | [] -> - raise Not_found + | [] -> raise Not_found + | [s] -> explore (i::p) s | s :: l -> try explore (i::p) s with Not_found -> explore_many (succ i) p l in @@ -67,10 +68,8 @@ module Make = functor(S : SearchProblem) -> struct let breadth_first s = let rec explore q = - try - let (s, q') = pop q in enqueue q' (S.branching s) - with Empty -> - raise Not_found + let (s, q') = try pop q with Empty -> raise Not_found in + enqueue q' (S.branching s) and enqueue q = function | [] -> explore q | s :: l -> if S.success s then s else enqueue (push s q) l @@ -79,11 +78,8 @@ module Make = functor(S : SearchProblem) -> struct let debug_breadth_first s = let rec explore q = - try - let ((p,s), q') = pop q in - enqueue 1 p q' (S.branching s) - with Empty -> - raise Not_found + let ((p,s), q') = try pop q with Empty -> raise Not_found in + enqueue 1 p q' (S.branching s) and enqueue i p q = function | [] -> explore q |