source: Deliverables/D4.1/Matita/BitVectorTrie.ma @ 419

include "BitVector.ma".
include "Bool.ma".
include "Maybe.ma".

ninductive BitVectorTrie (A: Type[0]): Nat → Type[0] ≝
  Leaf: A → BitVectorTrie A Z
| Node: ∀n: Nat. BitVectorTrie A n → BitVectorTrie A n → BitVectorTrie A (S n)
| Stub: ∀n: Nat. BitVectorTrie A n.

nlet rec lookup (A: Type[0]) (n: Nat)
                (b: BitVector n) (t: BitVectorTrie A n) (a: A) on b
       : A ≝
  (match b return λx.λ_. x = n → A with
    [ VEmpty ⇒ 
      (match t return λx.λ_. Z = x → A with
        [ Leaf l ⇒ λ_.l
        | Node h l r ⇒ λK.⊥
        | Stub s ⇒ λ_.a
        ])
    | VCons o hd tl ⇒
      match t return λx.λ_. (S o) = x → A with
        [ Leaf l ⇒ λK.⊥
        | Node h l r ⇒
           match hd with
             [ true ⇒ λK. lookup A h (tl⌈o ↦ h⌉) r a
             | false ⇒ λK. lookup A h (tl⌈o ↦ h⌉) l a
             ]
        | Stub s ⇒ λ_. a
        ]
    ]) (refl ? n).
 ##[##1,2: ndestruct |##*: napply S_inj; //]
nqed.

nlet rec prepare_trie_for_insertion (A: Type[0]) (n: Nat)
                                    (b: BitVector n) (a:A) on b
       : BitVectorTrie A n ≝
   match b with
    [ VEmpty ⇒ Leaf A a
    | VCons o hd tl ⇒
      match hd with
        [ true ⇒  Node A o (Stub A o) (prepare_trie_for_insertion A o tl a)
        | false ⇒ Node A o (prepare_trie_for_insertion A o tl a) (Stub A o)
        ]
    ].

nlet rec insert (A: Type[0]) (n: Nat)
                (b: BitVector n) (a: A) on b:
                 BitVectorTrie A n → BitVectorTrie A n ≝
  (match b with
    [ VEmpty ⇒ λ_. Leaf A a
    | VCons o hd tl ⇒ λt.
          match t return λy.λ_. S o = y → BitVectorTrie A (S o) with
            [ Leaf l ⇒ λprf.⊥
            | Node p l r ⇒ λprf.
               match hd with
                [ true ⇒  Node A o (l⌈p ↦ o⌉) (insert A o tl a (r⌈p ↦ o⌉))
                | false ⇒ Node A o (insert A o tl a (l⌈p ↦ o⌉)) (r⌈p ↦ o⌉)
                ]
            | Stub p ⇒ λprf. (prepare_trie_for_insertion A ? (hd:::tl) a)
            ] (refl ? (S o))
    ]).
    ##[ ndestruct;
    ##|##*: napply S_inj; // ]
nqed.

(*
nlemma insert_lookup_stub:
  ∀A: Type[0].
  ∀n: Nat.
  ∀b: BitVector n.
  ∀t: BitVectorTrie A n.
  ∀a, c: A.
    (lookup A n b (insert A n b a (Stub A n)) a) = a.
  #A n b t a c.
  nelim b.
  //.
  #N H V H2.
  nnormalize.
  @.
nqed.
*)
(*
nlemma test:
  ∀n: Nat.
  ∀b: BitVector n.
    length n b = n.
  #n b.
  nelim b.
  //.
  #N H V IH.
  ncases H.

nlemma insert_lookup_leaf:
  ∀A: Type[0].
  ∀n: Nat.
  ∀b: BitVector n.
  ∀a, c: A.
  ∀t: BitVectorTrie A n.
    lookup A ? b (insert A ? b a t) c = a.
  #A n b a c t.
  nelim b.
  nnormalize.
  @.
  #N H V IH.
*)