src/Pure/General/balanced_tree.ML
author wenzelm
Thu Jul 19 23:18:48 2007 +0200 (2007-07-19)
changeset 23863 8f3099589cfa
parent 23427 26202f4e663d
child 29606 fedb8be05f24
permissions -rw-r--r--
tuned signature;
wenzelm@23427
     1
(*  Title:      Pure/General/balanced_tree.ML
wenzelm@23427
     2
    ID:         $Id$
wenzelm@23427
     3
    Author:     Lawrence C Paulson and Makarius
wenzelm@23427
     4
wenzelm@23427
     5
Balanced binary trees.
wenzelm@23427
     6
*)
wenzelm@23427
     7
wenzelm@23427
     8
signature BALANCED_TREE =
wenzelm@23427
     9
sig
wenzelm@23427
    10
  val make: ('a * 'a -> 'a) -> 'a list -> 'a
wenzelm@23427
    11
  val dest: ('a -> 'a * 'a) -> int -> 'a -> 'a list
wenzelm@23427
    12
  val access: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> int -> 'a
wenzelm@23427
    13
  val accesses: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> 'a list
wenzelm@23427
    14
end;
wenzelm@23427
    15
wenzelm@23427
    16
structure BalancedTree: BALANCED_TREE =
wenzelm@23427
    17
struct
wenzelm@23427
    18
wenzelm@23427
    19
fun make _ [] = raise Empty
wenzelm@23427
    20
  | make _ [x] = x
wenzelm@23427
    21
  | make f xs =
wenzelm@23427
    22
      let
wenzelm@23427
    23
        val m = length xs div 2;
wenzelm@23427
    24
        val (ps, qs) = chop m xs;
wenzelm@23427
    25
      in f (make f ps, make f qs) end;
wenzelm@23427
    26
wenzelm@23427
    27
fun dest f n x =
wenzelm@23427
    28
  if n <= 0 then raise Empty
wenzelm@23427
    29
  else if n = 1 then [x]
wenzelm@23427
    30
  else
wenzelm@23427
    31
    let
wenzelm@23427
    32
      val m = n div 2;
wenzelm@23427
    33
      val (left, right) = f x;
wenzelm@23427
    34
    in dest f m left @ dest f (n - m) right end;
wenzelm@23427
    35
wenzelm@23427
    36
(*construct something of the form f(...g(...(x)...)) for balanced access*)
wenzelm@23427
    37
fun access {left = f, right = g, init = x} len i =
wenzelm@23427
    38
  let
wenzelm@23427
    39
    fun acc 1 _ = x
wenzelm@23427
    40
      | acc n i =
wenzelm@23427
    41
          let val m = n div 2 in
wenzelm@23427
    42
            if i <= m then f (acc m i)
wenzelm@23427
    43
            else g (acc (n - m) (i - m))
wenzelm@23427
    44
          end;
wenzelm@23427
    45
  in if 1 <= i andalso i <= len then acc len i else raise Subscript end;
wenzelm@23427
    46
wenzelm@23427
    47
(*construct ALL such accesses; could try harder to share recursive calls!*)
wenzelm@23427
    48
fun accesses {left = f, right = g, init = x} len =
wenzelm@23427
    49
  let
wenzelm@23427
    50
    fun acc 1 = [x]
wenzelm@23427
    51
      | acc n =
wenzelm@23427
    52
          let
wenzelm@23427
    53
            val m = n div 2;
wenzelm@23427
    54
            val accs_left = acc m;
wenzelm@23427
    55
            val accs_right =
wenzelm@23427
    56
              if n - m = m then accs_left
wenzelm@23427
    57
              else acc (n - m);
wenzelm@23427
    58
          in map f accs_left @ map g accs_right end;
wenzelm@23427
    59
  in if 1 <= len then acc len else raise Subscript end;
wenzelm@23427
    60
wenzelm@23427
    61
end;