src/Pure/General/balanced_tree.ML
author wenzelm
Wed, 21 Mar 2012 11:00:34 +0100
changeset 47060 e2741ec9ae36
parent 32765 3032c0308019
permissions -rw-r--r--
prefer explicitly qualified exception List.Empty;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
23427
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     1
(*  Title:      Pure/General/balanced_tree.ML
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     2
    Author:     Lawrence C Paulson and Makarius
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     3
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     4
Balanced binary trees.
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     5
*)
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     6
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     7
signature BALANCED_TREE =
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     8
sig
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
     9
  val make: ('a * 'a -> 'a) -> 'a list -> 'a
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    10
  val dest: ('a -> 'a * 'a) -> int -> 'a -> 'a list
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    11
  val access: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> int -> 'a
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    12
  val accesses: {left: 'a -> 'a, right: 'a -> 'a, init: 'a} -> int -> 'a list
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    13
end;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    14
32765
3032c0308019 modernized Balanced_Tree;
wenzelm
parents: 29606
diff changeset
    15
structure Balanced_Tree: BALANCED_TREE =
23427
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    16
struct
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    17
47060
e2741ec9ae36 prefer explicitly qualified exception List.Empty;
wenzelm
parents: 32765
diff changeset
    18
fun make _ [] = raise List.Empty
23427
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    19
  | make _ [x] = x
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    20
  | make f xs =
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    21
      let
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    22
        val m = length xs div 2;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    23
        val (ps, qs) = chop m xs;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    24
      in f (make f ps, make f qs) end;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    25
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    26
fun dest f n x =
47060
e2741ec9ae36 prefer explicitly qualified exception List.Empty;
wenzelm
parents: 32765
diff changeset
    27
  if n <= 0 then raise List.Empty
23427
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    28
  else if n = 1 then [x]
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    29
  else
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    30
    let
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    31
      val m = n div 2;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    32
      val (left, right) = f x;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    33
    in dest f m left @ dest f (n - m) right end;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    34
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    35
(*construct something of the form f(...g(...(x)...)) for balanced access*)
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    36
fun access {left = f, right = g, init = x} len i =
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    37
  let
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    38
    fun acc 1 _ = x
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    39
      | acc n i =
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    40
          let val m = n div 2 in
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    41
            if i <= m then f (acc m i)
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    42
            else g (acc (n - m) (i - m))
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    43
          end;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    44
  in if 1 <= i andalso i <= len then acc len i else raise Subscript end;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    45
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    46
(*construct ALL such accesses; could try harder to share recursive calls!*)
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    47
fun accesses {left = f, right = g, init = x} len =
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    48
  let
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    49
    fun acc 1 = [x]
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    50
      | acc n =
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    51
          let
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    52
            val m = n div 2;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    53
            val accs_left = acc m;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    54
            val accs_right =
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    55
              if n - m = m then accs_left
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    56
              else acc (n - m);
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    57
          in map f accs_left @ map g accs_right end;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    58
  in if 1 <= len then acc len else raise Subscript end;
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    59
26202f4e663d Balanced binary trees (material from library.ML);
wenzelm
parents:
diff changeset
    60
end;