wenzelm@23427: (*  Title:      Pure/General/balanced_tree.ML
wenzelm@23427:     ID:         $Id$
wenzelm@23427:     Author:     Lawrence C Paulson and Makarius
wenzelm@23427: 
wenzelm@23427: Balanced binary trees.
wenzelm@23427: *)
wenzelm@23427: 
wenzelm@23427: signature BALANCED_TREE =
wenzelm@23427: sig
wenzelm@23427:   val make: ('a * 'a -> 'a) -> 'a list -> 'a
wenzelm@23427:   val dest: ('a -> 'a * 'a) -> int -> 'a -> 'a list
wenzelm@23427:   val access: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> int -> 'a
wenzelm@23427:   val accesses: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> 'a list
wenzelm@23427: end;
wenzelm@23427: 
wenzelm@23427: structure BalancedTree: BALANCED_TREE =
wenzelm@23427: struct
wenzelm@23427: 
wenzelm@23427: fun make _ [] = raise Empty
wenzelm@23427:   | make _ [x] = x
wenzelm@23427:   | make f xs =
wenzelm@23427:       let
wenzelm@23427:         val m = length xs div 2;
wenzelm@23427:         val (ps, qs) = chop m xs;
wenzelm@23427:       in f (make f ps, make f qs) end;
wenzelm@23427: 
wenzelm@23427: fun dest f n x =
wenzelm@23427:   if n <= 0 then raise Empty
wenzelm@23427:   else if n = 1 then [x]
wenzelm@23427:   else
wenzelm@23427:     let
wenzelm@23427:       val m = n div 2;
wenzelm@23427:       val (left, right) = f x;
wenzelm@23427:     in dest f m left @ dest f (n - m) right end;
wenzelm@23427: 
wenzelm@23427: (*construct something of the form f(...g(...(x)...)) for balanced access*)
wenzelm@23427: fun access {left = f, right = g, init = x} len i =
wenzelm@23427:   let
wenzelm@23427:     fun acc 1 _ = x
wenzelm@23427:       | acc n i =
wenzelm@23427:           let val m = n div 2 in
wenzelm@23427:             if i <= m then f (acc m i)
wenzelm@23427:             else g (acc (n - m) (i - m))
wenzelm@23427:           end;
wenzelm@23427:   in if 1 <= i andalso i <= len then acc len i else raise Subscript end;
wenzelm@23427: 
wenzelm@23427: (*construct ALL such accesses; could try harder to share recursive calls!*)
wenzelm@23427: fun accesses {left = f, right = g, init = x} len =
wenzelm@23427:   let
wenzelm@23427:     fun acc 1 = [x]
wenzelm@23427:       | acc n =
wenzelm@23427:           let
wenzelm@23427:             val m = n div 2;
wenzelm@23427:             val accs_left = acc m;
wenzelm@23427:             val accs_right =
wenzelm@23427:               if n - m = m then accs_left
wenzelm@23427:               else acc (n - m);
wenzelm@23427:           in map f accs_left @ map g accs_right end;
wenzelm@23427:   in if 1 <= len then acc len else raise Subscript end;
wenzelm@23427: 
wenzelm@23427: end;