[Header]
let compare_key (a : key) (b : key) =
  let rec f (a : t) (b : t) =
    match (a, b) with
    | (Bar, Bar) -> 0
    | (Bar, _) -> -1
    | (_, Bar) -> 1
    | (Node (a1, a2), Node (b1, b2)) ->
        let c = f a1 b1 in
        if c <> 0 then c else f a2 b2
  in
  match (a, b) with
  | Silver a, Silver b -> f a b
  | Silver _, _ -> -1
  | _, Silver _ -> 1
  | Gold a, Gold b -> f a b

let sortedGetReady m =
  List.sort compare_key (getReady m)

let a : map = End (NameBox "a")
let b : map = End (NameBox "b")
let c : map = End (NameBox "c")
let d : map = End (NameBox "d")
let e : map = End (NameBox "e")
let f : map = End (NameBox "f")
let ga k : map = Guide ("a", k)
let gb k : map = Guide ("b", k)
let gc k : map = Guide ("c", k)
let gd k : map = Guide ("d", k)
let ge k : map = Guide ("e", k)
let gf k : map = Guide ("f", k)
let br k1 k2 : map = Branch (k1, k2)
let star : map = End StarBox

[Test]
(* 1 : base case *)
sortedGetReady star

[Value]
[Silver Bar]

[Test]
(* 2 : base case *)
sortedGetReady (ga a)

[Value]
[Silver Bar]

[Test]
(* 3 : base case *)
sortedGetReady ((gb (ga (br a b))))

[Value]
[Silver Bar; Silver (Node (Bar, Bar))]

[Test]
(* 4 : base case *)
sortedGetReady (br (ga a) star)

[Value]
[Silver Bar]

[Test]
(* 5 *)
getReady (br star star)

[Exception]
IMPOSSIBLE

[Test]
(* 6 *)
sortedGetReady (br (ga a) (gb b))

[Value]
[Silver Bar; Silver (Node (Bar, Bar))]

[Test]
(* 7 *)
getReady (br (gb (br b b)) star)

[Exception]
IMPOSSIBLE

[Test]
(* 8 *)
sortedGetReady
(ga (gb (gc (gd (ge (br (br (br (br a b) c) (br d e)) star))))))

[Value]
[Silver Bar; Silver (Node (Bar, Bar)); Silver (Node (Bar, Node (Bar, Node (Bar, Node (Bar, Bar)))))]

[Test]
(* 9 *)
getReady (gb (br (gc (br (br (ga (br a b)) (br b a)) c)) star))

[Exception]
IMPOSSIBLE

[Test]
(* 10 *)
sortedGetReady
(ga (gb (gc (gd (gf (br (br (br (br a b) c) (br (br d c) f)) (br b star)))))))

[Value]
[Silver Bar; Silver (Node (Bar, Bar)); Silver (Node (Bar, Node (Bar, Bar))); Silver (Node (Node (Bar, Bar), Node (Bar, Node (Bar, Node (Bar, Bar)))))]

[Test]
(* 11 *)
sortedGetReady (br (ga (br a a)) (gb (br b b)))

[Value]
[Gold Bar]

[Test]
(* 12 *)
sortedGetReady (br (ga (br a a)) (gb (gc (br (br b c) b))))

[Value]
[Gold Bar; Gold (Node (Bar, Node (Bar, Bar)))]