(***********************************************************************)
(*                                                                     *)
(*  OCaml library from the book ``Apprendre à programmer avec OCaml''  *)
(*                                                                     *)
(*  Sylvain Conchon and Jean-Christophe Filliâtre                      *)
(*  Université Paris Sud                                               *)
(*                                                                     *)
(*  Copyright 2014 Université Paris Sud.  All rights reserved. This    *)
(*  file is distributed under the terms of the GNU Library General     *)
(*  Public License, with the same special exception on linking as the  *)
(*  OCaml library. See http://caml.inria.fr/ocaml/license.fr.html      *)
(*                                                                     *)
(***********************************************************************)

(* Programme 56 page 244
   Union de deux arbres de Patricia *)

let rec union t1 t2 = match t1, t2 with
  | Empty, t | t, Empty  ->
      t
  | Leaf x, t | t, Leaf x ->
      add x t
  | Node (p1, b1, l1, r1), Node (p2, b2, l2, r2) ->
      if b1 == b2 && matches_prefix p2 p1 b1 then
        Node (p1, b1, union l1 l2, union r1 r2)
      else if b1 < b2 && matches_prefix p2 p1 b1 then
        if zero_bit p2 b1 then
          Node (p1, b1, union l1 t2, r1)
        else
          Node (p1, b1, l1, union r1 t2)
      else if b1 > b2 && matches_prefix p1 p2 b2 then
        if zero_bit p1 b2 then
          Node (p2, b2, union t1 l2, r2)
        else
          Node (p2, b2, l2, union t1 r2)
      else
        branch p1 t1 p2 t2

This document was generated using caml2html