(********************************************************************)
(*  OCaml code from the book ``Learn Programming with OCaml''       *)
(*  See https://usr.lmf.cnrs.fr/lpo/                                *)
(*                                                                  *)
(*  Sylvain Conchon and Jean-Christophe Filliâtre                   *)
(*  Copyright 2025 Université Paris-Saclay and CNRS                 *)
(*                                                                  *)
(*  Openly licensed via CC BY SA 4.0                                *)
(*  See https://creativecommons.org/licenses/by-sa/4.0/deed.en      *)
(********************************************************************)

(* Program 56 on page 259
   Union of Two Patricia Trees *)

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 && p1 = p2 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