OCaml Radix tree implementation

radix_tree.ml

type 'a t = {
        key: string option;
        child_id: char array;
        depth: int;
        mutable value: 'a option;
        mutable nodes: 'a t list
      }

let create v = { key = Some "";
                 child_id = [||];
                 depth = 0;
                 value = v;
                 nodes = []
               }

let array_of_string s =
  let len = String.length s in
  if len > 0 then Array.init (String.length s) (fun i -> String.get s i) else [||];;

type inclusion_result = Full_inclusion
                      | Partial_inclusion of { mutable pos: int;
                                               mutable root_new_child_id: char array
                                             } (* Partial inclusion also means full mismatch of symbols*)

let (=~) a b =
  let repeat = ref true in
  let pos = ref 0 in
  let len_a = Array.length a in
  let len_b = Array.length b in
  let root_new_child_id = ref [||] in

  if len_a > 0 && len_b > 0 then
    while !repeat do
      if (Array.get a !pos) = (Array.get b !pos) then
        pos := !pos + 1
      else
        let len = !pos in
        root_new_child_id := Array.init len (fun i -> Array.get a i);
        repeat := false;
    done;

  if len_a = len_b && !pos = len_a - 1 then Full_inclusion
  else Partial_inclusion { pos = !pos; root_new_child_id = !root_new_child_id };;

exception Key_already_exists of string

let rec __add t k child_id d v =
  match t.child_id =~ child_id with
  | Partial_inclusion { pos; root_new_child_id } ->
    if (Array.length root_new_child_id) = 0 then
      let depth = d + 1 in
      let len = Array.length child_id - pos in
      let child_id = Array.sub child_id pos len in
      if len > 0 then
        List.iter (fun n -> __add n k child_id depth v) t.nodes
      else

    else
     () (* remake the tree *)
  | Full_inclusion -> match t.value with
                      | None -> t.value <- v
                      | Some _ -> raise (Key_already_exists "Given key already exists in the tree!");;

let add t k v =
  let child_id = array_of_string k in
  __add t k child_id 0 v;;


(*
  1 - Если совпадает первый символ ключа, то:
  1.1 - Если совпадают все символы ключей, то копируем значение в текущую ноду
  1.2 - Если совпадают только несколько первых символов, то перестраиваем поддерево.
  2 - Если не совпадает первый символ ключа, то:
  2.1 - Переходим к следующей ноде и проверяем ее.
  3 - Если нет совпадений по всем нодам - создаем новую - их sibling'а.

  Перестраивание дерева:
  - а: нужно получить root-элемент поддерева для перерисовки и
    b: нужно получить не сходящийся целиком ключ ноды
  - нужно высчитать новый префикс (он должен быть короче)
  - нужно переписать вложенные ноды по принципу как выше (ключи могут стать чуть длиннее)
  - нужно подменить одигинальную ноду вновь созданной
*)