moved balanced tree operations to General/balanced_tree.ML;
authorwenzelm
Tue Jun 19 23:15:54 2007 +0200 (2007-06-19)
changeset 23424d0580634f128
parent 23423 b2d64f86d21b
child 23425 b74315510f85
moved balanced tree operations to General/balanced_tree.ML;
src/Pure/library.ML
     1.1 --- a/src/Pure/library.ML	Tue Jun 19 23:15:51 2007 +0200
     1.2 +++ b/src/Pure/library.ML	Tue Jun 19 23:15:54 2007 +0200
     1.3 @@ -4,7 +4,7 @@
     1.4      Author:     Markus Wenzel, TU Muenchen
     1.5  
     1.6  Basic library: functions, options, pairs, booleans, lists, integers,
     1.7 -strings, lists as sets, balanced trees, orders, current directory, misc.
     1.8 +strings, lists as sets, orders, current directory, misc.
     1.9  
    1.10  See also General/basics.ML for the most fundamental concepts.
    1.11  *)
    1.12 @@ -194,12 +194,6 @@
    1.13    val remove1: ('b * 'a -> bool) -> 'b -> 'a list -> 'a list
    1.14    val submultiset: ('a * 'b -> bool) -> 'a list * 'b list -> bool
    1.15  
    1.16 -  (*balanced trees*)
    1.17 -  exception Balance
    1.18 -  val fold_bal: ('a * 'a -> 'a) -> 'a list -> 'a
    1.19 -  val access_bal: ('a -> 'a) * ('a -> 'a) * 'a -> int -> int -> 'a
    1.20 -  val accesses_bal: ('a -> 'a) * ('a -> 'a) * 'a -> int -> 'a list
    1.21 -
    1.22    (*orders*)
    1.23    val is_equal: order -> bool
    1.24    val rev_order: order -> order
    1.25 @@ -920,39 +914,6 @@
    1.26  
    1.27  
    1.28  
    1.29 -(** balanced trees **)
    1.30 -
    1.31 -exception Balance;      (*indicates non-positive argument to balancing fun*)
    1.32 -
    1.33 -(*balanced folding; avoids deep nesting*)
    1.34 -fun fold_bal f [x] = x
    1.35 -  | fold_bal f [] = raise Balance
    1.36 -  | fold_bal f xs =
    1.37 -      let val (ps, qs) = chop (length xs div 2) xs
    1.38 -      in  f (fold_bal f ps, fold_bal f qs)  end;
    1.39 -
    1.40 -(*construct something of the form f(...g(...(x)...)) for balanced access*)
    1.41 -fun access_bal (f, g, x) n i =
    1.42 -  let fun acc n i =     (*1<=i<=n*)
    1.43 -          if n=1 then x else
    1.44 -          let val n2 = n div 2
    1.45 -          in  if i<=n2 then f (acc n2 i)
    1.46 -                       else g (acc (n-n2) (i-n2))
    1.47 -          end
    1.48 -  in  if 1<=i andalso i<=n then acc n i else raise Balance  end;
    1.49 -
    1.50 -(*construct ALL such accesses; could try harder to share recursive calls!*)
    1.51 -fun accesses_bal (f, g, x) n =
    1.52 -  let fun acc n =
    1.53 -          if n=1 then [x] else
    1.54 -          let val n2 = n div 2
    1.55 -              val acc2 = acc n2
    1.56 -          in  if n-n2=n2 then map f acc2 @ map g acc2
    1.57 -                         else map f acc2 @ map g (acc (n-n2)) end
    1.58 -  in  if 1<=n then acc n else raise Balance  end;
    1.59 -
    1.60 -
    1.61 -
    1.62  (** orders **)
    1.63  
    1.64  fun is_equal EQUAL = true