Mercurial > hg > Gears > GearsAgda
changeset 950:5c75fc6dfe59
...
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 13 Aug 2024 23:03:40 +0900 |
parents | 057d3309ed9d |
children | ccdcf5572a54 |
files | RBTree.agda logic.agda |
diffstat | 2 files changed, 675 insertions(+), 1148 deletions(-) [+] |
line wrap: on
line diff
--- a/RBTree.agda Sun Aug 04 13:05:12 2024 +0900 +++ b/RBTree.agda Tue Aug 13 23:03:40 2024 +0900 @@ -1,6 +1,6 @@ -{-# OPTIONS cubical-compatible --allow-unsolved-metas #-} --- {-# OPTIONS --cubical-compatible --safe #-} --- {-# OPTIONS --cubical-compatible #-} +{-# OPTIONS --cubical-compatible --allow-unsolved-metas #-} +-- {-# OPTIONS --cubical-compatible --safe #-} + module RBTree where open import Level hiding (suc ; zero ; _⊔_ ) @@ -13,12 +13,16 @@ open import Data.List open import Data.Product +open import Data.Maybe.Properties +open import Data.List.Properties + open import Function as F hiding (const) open import Relation.Binary open import Relation.Binary.PropositionalEquality open import Relation.Nullary open import logic +open import nat -- @@ -102,17 +106,6 @@ suc i ≤⟨ m≤m+n (suc i) j ⟩ suc i + j ∎ where open ≤-Reasoning -nat-≤> : { x y : ℕ } → x ≤ y → y < x → ⊥ -nat-≤> (s≤s x<y) (s≤s y<x) = nat-≤> x<y y<x -nat-<> : { x y : ℕ } → x < y → y < x → ⊥ -nat-<> (s≤s x<y) (s≤s y<x) = nat-<> x<y y<x - -nat-<≡ : { x : ℕ } → x < x → ⊥ -nat-<≡ (s≤s lt) = nat-<≡ lt - -nat-≡< : { x y : ℕ } → x ≡ y → x < y → ⊥ -nat-≡< refl lt = nat-<≡ lt - treeTest1 : bt ℕ treeTest1 = node 0 0 leaf (node 3 1 (node 2 5 (node 1 7 leaf leaf ) leaf) (node 5 5 leaf leaf)) treeTest2 : bt ℕ @@ -140,72 +133,223 @@ si-property0 (s-right _ _ _ x si) () si-property0 (s-left _ _ _ x si) () + si-property1 : {n : Level} {A : Set n} {key : ℕ} {tree tree0 tree1 : bt A} → {stack : List (bt A)} → stackInvariant key tree tree0 (tree1 ∷ stack) → tree1 ≡ tree -si-property1 (s-nil ) = refl -si-property1 (s-right _ _ _ _ si) = refl -si-property1 (s-left _ _ _ _ si) = refl +si-property1 {n} {A} {key} {tree} {tree0} {tree1} {stack} si = lem00 tree tree0 tree1 _ (tree1 ∷ stack) refl si where + lem00 : (tree tree0 tree1 : bt A) → (stack stack1 : List (bt A)) → tree1 ∷ stack ≡ stack1 → stackInvariant key tree tree0 stack1 → tree1 ≡ tree + lem00 tree .tree tree1 stack .(tree ∷ []) eq s-nil = ∷-injectiveˡ eq + lem00 tree tree0 tree1 stack .(tree ∷ _) eq (s-right .tree .tree0 tree₁ x si) = ∷-injectiveˡ eq + lem00 tree tree0 tree1 stack .(tree ∷ _) eq (s-left .tree .tree0 tree₁ x si) = ∷-injectiveˡ eq si-property2 : {n : Level} {A : Set n} {key : ℕ} {tree tree0 tree1 : bt A} → (stack : List (bt A)) → stackInvariant key tree tree0 (tree1 ∷ stack) → ¬ ( just leaf ≡ stack-last stack ) -si-property2 (.leaf ∷ []) (s-right _ _ tree₁ x ()) refl -si-property2 (x₁ ∷ x₂ ∷ stack) (s-right _ _ tree₁ x si) eq = si-property2 (x₂ ∷ stack) si eq -si-property2 (.leaf ∷ []) (s-left _ _ tree₁ x ()) refl -si-property2 (x₁ ∷ x₂ ∷ stack) (s-left _ _ tree₁ x si) eq = si-property2 (x₂ ∷ stack) si eq +si-property2 {n} {A} {key} {tree} {tree0} {tree1} [] si () +si-property2 {n} {A} {key} {tree} {tree0} {tree1} (x ∷ []) si eq with just-injective eq +... | refl = lem00 (tree1 ∷ leaf ∷ []) refl si where + lem00 : (t : List (bt A)) → (tree1 ∷ leaf ∷ []) ≡ t → stackInvariant key tree tree0 t → ⊥ + lem00 .(tree ∷ []) () s-nil + lem00 (tree ∷ _) () (s-right .tree .(node _ _ tree₁ tree) tree₁ x s-nil) + lem00 (tree ∷ _) () (s-right .tree .tree0 tree₁ x (s-right .(node _ _ tree₁ tree) .tree0 tree₂ x₁ si2)) + lem00 (tree ∷ _) () (s-right .tree .tree0 tree₁ x (s-left .(node _ _ tree₁ tree) .tree0 tree₂ x₁ si2)) + lem00 (tree₁ ∷ _) () (s-left .tree₁ .(node _ _ tree₁ tree) tree x s-nil) + lem00 (tree₁ ∷ _) () (s-left .tree₁ .tree0 tree x (s-right .(node _ _ tree₁ tree) .tree0 tree₂ x₁ si2)) + lem00 (tree₁ ∷ _) () (s-left .tree₁ .tree0 tree x (s-left .(node _ _ tree₁ tree) .tree0 tree₂ x₁ si2)) +si-property2 {n} {A} {key} {tree} {tree0} {tree1} (x ∷ x₁ ∷ stack) si = lem00 (tree1 ∷ x ∷ x₁ ∷ stack) refl si where + lem00 : (t : List (bt A)) → (tree1 ∷ x ∷ x₁ ∷ stack) ≡ t → stackInvariant key tree tree0 t → ¬ just leaf ≡ stack-last (x₁ ∷ stack) + lem00 .(tree ∷ []) () s-nil + lem00 (tree ∷ []) () (s-right .tree .tree0 tree₁ x si) + lem00 (tree ∷ x₁ ∷ st) eq (s-right .tree .tree0 tree₁ x si) eq1 = si-property2 st si + (subst (λ k → just leaf ≡ stack-last k ) (∷-injectiveʳ (∷-injectiveʳ eq)) eq1 ) + lem00 (tree ∷ []) () (s-left .tree .tree0 tree₁ x si) + lem00 (tree₁ ∷ x₁ ∷ st) eq (s-left .tree₁ .tree0 tree x si) eq1 = si-property2 st si + (subst (λ k → just leaf ≡ stack-last k ) (∷-injectiveʳ (∷-injectiveʳ eq)) eq1 ) + + +-- We cannot avoid warning: -W[no]UnsupportedIndexedMatcin tree-inject +-- open import Function.Base using (_∋_; id; _∘_; _∘′_) +-- just-injective1 : {n : Level } {A : Set n} {x y : A } → (Maybe A ∋ just x) ≡ just y → x ≡ y +-- just-injective1 refl = refl + +node-left : {n : Level} {A : Set n} → bt A → Maybe (bt A) +node-left (node _ _ left _) = just left +node-left _ = nothing + +node-right : {n : Level} {A : Set n} → bt A → Maybe (bt A) +node-right (node _ _ _ right) = just right +node-right _ = nothing + +-- lem00 = just-injective (cong node-key eq) + +tree-injective-key : {n : Level} {A : Set n} + → (tr0 tr1 : bt A) → tr0 ≡ tr1 → node-key tr0 ≡ node-key tr1 +tree-injective-key {n} {A} tr0 tr1 eq = cong node-key eq + +ti-property2 : {n : Level} {A : Set n} {key : ℕ} {value : A} {tree1 left right : bt A} + → tree1 ≡ node key value left right + → left ≡ right + → ( ¬ left ≡ leaf ) ∨ ( ¬ right ≡ leaf ) + → ¬ treeInvariant tree1 +ti-property2 {n} {A} {key} {value} {leaf} {left} {right} () eq1 x ti +ti-property2 {n} {A} {key} {value} {node key₁ value₁ leaf t₁} {left} {right} eq eq1 (case1 eq2) _ + = ⊥-elim ( eq2 (just-injective ( cong node-left (sym eq) ))) +ti-property2 {n} {A} {key} {value} {node key₁ value₁ leaf t₁} {left} {right} eq eq1 (case2 eq2) _ + = ⊥-elim ( eq2 (just-injective (trans (cong just (sym eq1)) ( cong node-left (sym eq) ) ) )) +ti-property2 {n} {A} {key} {value} {node key₁ value₁ (node key₂ value₂ t t₂) leaf} {left} {right} eq eq1 (case1 eq2) _ + = ⊥-elim ( eq2 (just-injective (trans (cong just eq1) ( cong node-right (sym eq) ) ) )) +ti-property2 {n} {A} {key} {value} {node key₁ value₁ (node key₂ value₂ t t₂) leaf} {left} {right} eq eq1 (case2 eq2) _ + = ⊥-elim ( eq2 (just-injective ( cong node-right (sym eq) ))) +ti-property2 {n} {A} {key} {value} {node key₂ value₂ (node key₁ value₁ t₁ t₂) (node key₃ value₃ t₃ t₄)} {left} {right} eq eq1 eq2 ti + = ⊥-elim ( nat-≡< lem00 (lem03 _ _ _ refl lem01 lem02 ti) ) where + lem01 : node key₁ value₁ t₁ t₂ ≡ left + lem01 = just-injective ( cong node-left eq ) + lem02 : node key₃ value₃ t₃ t₄ ≡ right + lem02 = just-injective ( cong node-right eq ) + lem00 : key₁ ≡ key₃ + lem00 = begin + key₁ ≡⟨ just-injective ( begin + just key₁ ≡⟨ cong node-key lem01 ⟩ + node-key left ≡⟨ cong node-key eq1 ⟩ + node-key right ≡⟨ cong node-key (sym lem02) ⟩ + just key₃ ∎ ) ⟩ + key₃ ∎ where open ≡-Reasoning + lem03 : (key₁ key₃ : ℕ) → (tr : bt A) → tr ≡ node key₂ value₂ (node key₁ value₁ t₁ t₂) (node key₃ value₃ t₃ t₄) + → node key₁ value₁ t₁ t₂ ≡ left + → node key₃ value₃ t₃ t₄ ≡ right + → treeInvariant tr → key₁ < key₃ + lem03 _ _ .leaf () _ _ t-leaf + lem03 _ _ .(node _ _ leaf leaf) () _ _ (t-single _ _) + lem03 _ _ .(node _ _ (node _ _ _ _) leaf) () _ _ (t-left _ _ _ _ _ _) + lem03 _ _ .(node _ _ leaf (node _ _ _ _)) () _ _ (t-right _ _ _ _ _ _) + lem03 key₁ key₃ (node key _ (node _ _ _ _) (node _ _ _ _)) eq3 el er (t-node key₄ key₅ key₂ x x₁ x₂ x₃ x₄ x₅ ti ti₁) = lem04 where + lem04 : key₁ < key₃ + lem04 = begin + suc key₁ ≡⟨ cong suc ( just-injective (cong node-key (just-injective (cong node-left (sym eq3)) ) ) ) ⟩ + suc key₄ ≤⟨ <-trans x x₁ ⟩ + key₂ ≡⟨ just-injective (cong node-key (just-injective (cong node-right eq3) ) ) ⟩ + key₃ ∎ where open ≤-Reasoning si-property-< : {n : Level} {A : Set n} {key kp : ℕ} {value₂ : A} {tree orig tree₃ : bt A} → {stack : List (bt A)} → ¬ ( tree ≡ leaf ) → treeInvariant (node kp value₂ tree tree₃ ) → stackInvariant key tree orig (tree ∷ node kp value₂ tree tree₃ ∷ stack) → key < kp -si-property-< ne (t-node _ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (s-right (node _ _ _ _) _ (node _ _ _ _) x s-nil) = ⊥-elim (nat-<> x₁ x₂) -si-property-< ne (t-node _ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (s-right .(node _ _ _ _) _ .(node _ _ _ _) x (s-right .(node _ _ (node _ _ _ _) (node _ _ _ _)) _ tree₁ x₇ si)) = ⊥-elim (nat-<> x₁ x₂) -si-property-< ne (t-node _ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (s-right .(node _ _ _ _) _ .(node _ _ _ _) x (s-left .(node _ _ (node _ _ _ _) (node _ _ _ _)) _ tree x₇ si)) = ⊥-elim (nat-<> x₁ x₂) -si-property-< ne ti (s-left _ _ _ x (s-right .(node _ _ _ _) _ tree₁ x₁ si)) = x -si-property-< ne ti (s-left _ _ _ x (s-left .(node _ _ _ _) _ tree₁ x₁ si)) = x -si-property-< ne ti (s-left _ _ _ x s-nil) = x -si-property-< ne (t-single _ _) (s-right _ _ tree₁ x si) = ⊥-elim ( ne refl ) +si-property-< {n} {A} {key} {kp} {value₂} {tree} {orig} {tree₃} {stack} ne ti si = + lem00 (node kp value₂ tree tree₃ ) (tree ∷ node kp value₂ tree tree₃ ∷ stack) refl refl ti si where + lem00 : (tree1 : bt A) → (st : List (bt A)) → (tree1 ≡ (node kp value₂ tree tree₃ )) → (st ≡ tree ∷ node kp value₂ tree tree₃ ∷ stack) + → treeInvariant tree1 → stackInvariant key tree orig st → key < kp + lem00 tree1 .(tree ∷ []) teq () ti s-nil + lem00 tree1 .(tree ∷ node key₁ v1 tree₁ tree ∷ []) teq seq ti₁ (s-right .tree .(node key₁ v1 tree₁ tree) tree₁ {key₁} {v1} x s-nil) = lem01 where + lem02 : node key₁ v1 tree₁ tree ≡ node kp value₂ tree tree₃ + lem02 = ∷-injectiveˡ ( ∷-injectiveʳ seq ) + lem03 : tree₁ ≡ tree + lem03 = just-injective (cong node-left lem02) + lem01 : key < kp + lem01 = ⊥-elim ( ti-property2 (sym lem02) lem03 (case2 ne) ti ) + lem00 tree1 .(tree ∷ node key₁ v1 tree₁ tree ∷ _) teq seq ti₁ (s-right .tree .orig tree₁ {key₁} {v1} x (s-right .(node _ _ tree₁ tree) .orig tree₂ {key₂} {v2} x₁ si)) = lem01 where + lem02 : node key₁ v1 tree₁ tree ≡ node kp value₂ tree tree₃ + lem02 = ∷-injectiveˡ ( ∷-injectiveʳ seq ) + lem03 : tree₁ ≡ tree + lem03 = just-injective (cong node-left lem02) + lem01 : key < kp + lem01 = ⊥-elim ( ti-property2 (sym lem02) lem03 (case2 ne) ti ) + lem00 tree1 (tree₂ ∷ node key₁ v1 tree₁ tree₂ ∷ _) teq seq ti₁ (s-right .tree₂ .orig tree₁ {key₁} {v1} x (s-left .(node _ _ tree₁ tree₂) .orig tree x₁ si)) = lem01 where + lem02 : node key₁ v1 tree₁ tree₂ ≡ node kp value₂ tree₂ tree₃ + lem02 = ∷-injectiveˡ ( ∷-injectiveʳ seq ) + lem03 : tree₁ ≡ tree₂ + lem03 = just-injective (cong node-left lem02 ) + lem01 : key < kp + lem01 = ⊥-elim ( ti-property2 (sym lem02) lem03 (case2 ne) ti ) + lem00 tree1 (tree₁ ∷ _) teq seq ti₁ (s-left .tree₁ .(node _ _ tree₁ tree) tree {key₁} {v1} x s-nil) = subst( λ k → key < k ) lem03 x where + lem03 : key₁ ≡ kp + lem03 = just-injective (cong node-key (∷-injectiveˡ ( ∷-injectiveʳ seq ))) + lem00 tree1 (tree₁ ∷ _) teq seq ti₁ (s-left .tree₁ .orig tree {key₁} {v1} x (s-right .(node _ _ tree₁ tree) .orig tree₂ x₁ si)) = subst( λ k → key < k ) lem03 x where + lem03 : key₁ ≡ kp + lem03 = just-injective (cong node-key (∷-injectiveˡ ( ∷-injectiveʳ seq ))) + lem00 tree1 (tree₁ ∷ _) teq seq ti₁ (s-left .tree₁ .orig tree {key₁} {v1} x (s-left .(node _ _ tree₁ tree) .orig tree₂ x₁ si)) = subst( λ k → key < k ) lem03 x where + lem03 : key₁ ≡ kp + lem03 = just-injective (cong node-key (∷-injectiveˡ ( ∷-injectiveʳ seq ))) si-property-> : {n : Level} {A : Set n} {key kp : ℕ} {value₂ : A} {tree orig tree₃ : bt A} → {stack : List (bt A)} → ¬ ( tree ≡ leaf ) → treeInvariant (node kp value₂ tree₃ tree ) → stackInvariant key tree orig (tree ∷ node kp value₂ tree₃ tree ∷ stack) → kp < key -si-property-> ne ti (s-right _ _ tree₁ x s-nil) = x -si-property-> ne ti (s-right _ _ tree₁ x (s-right .(node _ _ tree₁ _) _ tree₂ x₁ si)) = x -si-property-> ne ti (s-right _ _ tree₁ x (s-left .(node _ _ tree₁ _) _ tree x₁ si)) = x -si-property-> ne (t-node _ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (s-left _ _ _ x s-nil) = ⊥-elim (nat-<> x₁ x₂) -si-property-> ne (t-node _ _ _ x₂ x₃ x₄ x₅ x₆ x₇ ti ti₁) (s-left _ _ _ x (s-right .(node _ _ _ _) _ tree₁ x₁ si)) = ⊥-elim (nat-<> x₂ x₃) -si-property-> ne (t-node _ _ _ x₂ x₃ x₄ x₅ x₆ x₇ ti ti₁) (s-left _ _ _ x (s-left .(node _ _ _ _) _ tree x₁ si)) = ⊥-elim (nat-<> x₂ x₃) -si-property-> ne (t-single _ _) (s-left _ _ _ x s-nil) = ⊥-elim ( ne refl ) -si-property-> ne (t-single _ _) (s-left _ _ _ x (s-right .(node _ _ leaf leaf) _ tree₁ x₁ si)) = ⊥-elim ( ne refl ) -si-property-> ne (t-single _ _) (s-left _ _ _ x (s-left .(node _ _ leaf leaf) _ tree x₁ si)) = ⊥-elim ( ne refl ) +si-property-> {n} {A} {key} {kp} {value₂} {tree} {orig} {tree₃} {stack} ne ti si = + lem00 (node kp value₂ tree₃ tree ) (tree ∷ node kp value₂ tree₃ tree ∷ stack) refl refl ti si where + lem00 : (tree1 : bt A) → (st : List (bt A)) → (tree1 ≡ (node kp value₂ tree₃ tree )) → (st ≡ tree ∷ node kp value₂ tree₃ tree ∷ stack) + → treeInvariant tree1 → stackInvariant key tree orig st → kp < key + lem00 tree1 .(tree ∷ []) teq () ti s-nil + lem00 tree1 .(tree ∷ node key₁ v1 tree tree₁ ∷ []) teq seq ti₁ (s-left .tree .(node key₁ v1 tree tree₁) tree₁ {key₁} {v1} x s-nil) = lem01 where + lem02 : node key₁ v1 tree tree₁ ≡ node kp value₂ tree₃ tree + lem02 = ∷-injectiveˡ ( ∷-injectiveʳ seq ) + lem03 : tree₁ ≡ tree + lem03 = just-injective (cong node-right lem02) + lem01 : kp < key + lem01 = ⊥-elim ( ti-property2 (sym lem02) (sym lem03) (case1 ne) ti ) + lem00 tree1 .(tree ∷ node key₁ v1 tree tree₁ ∷ _) teq seq ti₁ (s-left .tree .orig tree₁ {key₁} {v1} x (s-left .(node _ _ tree tree₁) .orig tree₂ {key₂} {v2} x₁ si)) = lem01 where + lem02 : node key₁ v1 tree tree₁ ≡ node kp value₂ tree₃ tree + lem02 = ∷-injectiveˡ ( ∷-injectiveʳ seq ) + lem03 : tree₁ ≡ tree + lem03 = just-injective (cong node-right lem02) + lem01 : kp < key + lem01 = ⊥-elim ( ti-property2 (sym lem02) (sym lem03) (case1 ne) ti ) + lem00 tree1 (tree₂ ∷ node key₁ v1 tree₂ tree₁ ∷ _) teq seq ti₁ (s-left .tree₂ .orig tree₁ {key₁} {v1} x (s-right .(node _ _ tree₂ tree₁) .orig tree x₁ si)) = lem01 where + lem02 : node key₁ v1 tree₂ tree₁ ≡ node kp value₂ tree₃ tree₂ + lem02 = ∷-injectiveˡ ( ∷-injectiveʳ seq ) + lem03 : tree₁ ≡ tree₂ + lem03 = just-injective (cong node-right lem02) + lem01 : kp < key + lem01 = ⊥-elim ( ti-property2 (sym lem02) (sym lem03) (case1 ne) ti ) + lem00 tree1 (tree₁ ∷ _) teq seq ti₁ (s-right .tree₁ .(node _ _ tree tree₁) tree {key₁} {v1} x s-nil) = subst( λ k → k < key ) lem03 x where + lem03 : key₁ ≡ kp + lem03 = just-injective (cong node-key (∷-injectiveˡ ( ∷-injectiveʳ seq ))) + lem00 tree1 (tree₁ ∷ _) teq seq ti₁ (s-right .tree₁ .orig tree {key₁} {v1} x (s-left .(node _ _ tree tree₁) .orig tree₂ x₁ si)) = subst( λ k → k < key ) lem03 x where + lem03 : key₁ ≡ kp + lem03 = just-injective (cong node-key (∷-injectiveˡ ( ∷-injectiveʳ seq ))) + lem00 tree1 (tree₁ ∷ _) teq seq ti₁ (s-right .tree₁ .orig tree {key₁} {v1} x (s-right .(node _ _ tree tree₁) .orig tree₂ x₁ si)) = subst( λ k → k < key ) lem03 x where + lem03 : key₁ ≡ kp + lem03 = just-injective (cong node-key (∷-injectiveˡ ( ∷-injectiveʳ seq ))) + si-property-last : {n : Level} {A : Set n} (key : ℕ) (tree tree0 : bt A) → (stack : List (bt A)) → stackInvariant key tree tree0 stack → stack-last stack ≡ just tree0 -si-property-last key t t0 (t ∷ []) (s-nil ) = refl -si-property-last key t t0 (.t ∷ x ∷ st) (s-right _ _ _ _ si ) with si-property1 si -... | refl = si-property-last key x t0 (x ∷ st) si -si-property-last key t t0 (.t ∷ x ∷ st) (s-left _ _ _ _ si ) with si-property1 si -... | refl = si-property-last key x t0 (x ∷ st) si +si-property-last {n} {A} key tree .tree .(tree ∷ []) s-nil = refl +si-property-last {n} {A} key tree tree0 (tree ∷ []) (s-right .tree .tree0 tree₁ x si) = ⊥-elim ( si-property0 si refl ) +si-property-last {n} {A} key tree tree0 (tree ∷ x₁ ∷ st) (s-right .tree .tree0 tree₁ x si) = + si-property-last key _ tree0 (x₁ ∷ st) si +si-property-last {n} {A} key tree tree0 (tree ∷ []) (s-left .tree .tree0 tree₁ x si) = ⊥-elim ( si-property0 si refl ) +si-property-last {n} {A} key tree tree0 (tree ∷ x₁ ∷ st) (s-left .tree .tree0 tree₁ x si) = + si-property-last key _ tree0 (x₁ ∷ st) si si-property-pne : {n : Level} {A : Set n} {key key₁ : ℕ} {value₁ : A} (tree orig : bt A) → {left right x : bt A} → (stack : List (bt A)) {rest : List (bt A)} → stack ≡ x ∷ node key₁ value₁ left right ∷ rest → stackInvariant key tree orig stack → ¬ ( key ≡ key₁ ) -si-property-pne tree orig .(tree ∷ node _ _ _ _ ∷ _) refl (s-right .tree .orig tree₁ x si) eq with si-property1 si -... | refl = ⊥-elim ( nat-≡< (sym eq) x) -si-property-pne tree orig .(tree ∷ node _ _ _ _ ∷ _) refl (s-left .tree .orig tree₁ x si) eq with si-property1 si -... | refl = ⊥-elim ( nat-≡< eq x) +si-property-pne {_} {_} {key} {key₁} {value₁} tree orig {left} {right} (tree ∷ tree1 ∷ st) seq (s-right .tree .orig tree₁ {key₂} {v₂} x si) eq + = ⊥-elim ( nat-≡< lem00 x ) where + lem01 : tree1 ≡ node key₂ v₂ tree₁ tree + lem01 = si-property1 si + lem02 : node key₁ value₁ left right ≡ node key₂ v₂ tree₁ tree + lem02 = trans ( ∷-injectiveˡ (∷-injectiveʳ (sym seq) ) ) lem01 + lem00 : key₂ ≡ key + lem00 = trans (just-injective (cong node-key (sym lem02))) (sym eq) +si-property-pne {_} {_} {key} {key₁} {value₁} tree orig {left} {right} (tree ∷ tree1 ∷ st) seq (s-left tree orig tree₁ {key₂} {v₂} x si) eq + = ⊥-elim ( nat-≡< (sym lem00) x ) where + lem01 : tree1 ≡ node key₂ v₂ tree tree₁ + lem01 = si-property1 si + lem02 : node key₁ value₁ left right ≡ node key₂ v₂ tree tree₁ + lem02 = trans ( ∷-injectiveˡ (∷-injectiveʳ (sym seq) ) ) lem01 + lem00 : key₂ ≡ key + lem00 = trans (just-injective (cong node-key (sym lem02))) (sym eq) +si-property-pne {_} {_} {key} {key₁} {value₁} tree .tree {left} {right} .(tree ∷ []) () s-nil eq -si-property-parent-node : {n : Level} {A : Set n} {key : ℕ} (tree orig : bt A) {x : bt A} - → (stack : List (bt A)) {rest : List (bt A)} - → stackInvariant key tree orig stack - → ¬ ( stack ≡ x ∷ leaf ∷ rest ) -si-property-parent-node {n} {A} tree orig .(tree ∷ leaf ∷ _) (s-right .tree .orig tree₁ x si) refl with si-property1 si -... | () -si-property-parent-node {n} {A} tree orig .(tree ∷ leaf ∷ _) (s-left .tree .orig tree₁ x si) refl with si-property1 si -... | () + +-- si-property-parent-node : {n : Level} {A : Set n} {key : ℕ} (tree orig : bt A) {x : bt A} +-- → (stack : List (bt A)) {rest : List (bt A)} +-- → stackInvariant key tree orig stack +-- → ¬ ( stack ≡ x ∷ leaf ∷ rest ) +-- si-property-parent-node {n} {A} tree orig = ? rt-property1 : {n : Level} {A : Set n} (key : ℕ) (value : A) (tree tree1 : bt A ) → replacedTree key value tree tree1 → ¬ ( tree1 ≡ leaf ) @@ -215,16 +359,25 @@ rt-property1 {n} {A} key value .(node _ _ _ _) _ (r-left x rt) = λ () rt-property-leaf : {n : Level} {A : Set n} {key : ℕ} {value : A} {repl : bt A} → replacedTree key value leaf repl → repl ≡ node key value leaf leaf -rt-property-leaf r-leaf = refl +rt-property-leaf {n} {A} {key} {value} {repl} rt = lem00 leaf refl rt where + lem00 : (tree : bt A) → tree ≡ leaf → replacedTree key value tree repl → repl ≡ node key value leaf leaf + lem00 leaf eq r-leaf = refl + lem00 .(node key _ _ _) () r-node + lem00 .(node _ _ _ _) () (r-right x rt) + lem00 .(node _ _ _ _) () (r-left x rt) rt-property-¬leaf : {n : Level} {A : Set n} {key : ℕ} {value : A} {tree : bt A} → ¬ replacedTree key value tree leaf rt-property-¬leaf () rt-property-key : {n : Level} {A : Set n} {key key₂ key₃ : ℕ} {value value₂ value₃ : A} {left left₁ right₂ right₃ : bt A} → replacedTree key value (node key₂ value₂ left right₂) (node key₃ value₃ left₁ right₃) → key₂ ≡ key₃ -rt-property-key r-node = refl -rt-property-key (r-right x ri) = refl -rt-property-key (r-left x ri) = refl +rt-property-key {n} {A} {key} {key₂} {key₃} {value} {value₂} {value₃} {left} {left₁} {right₂} {right₃} rt + = lem00 (node key₂ value₂ left right₂) (node key₃ value₃ left₁ right₃) refl refl rt where + lem00 : (tree tree1 : bt A) → tree ≡ node key₂ value₂ left right₂ → tree1 ≡ node key₃ value₃ left₁ right₃ → replacedTree key value tree tree1 → key₂ ≡ key₃ + lem00 _ _ () eq2 r-leaf + lem00 _ _ eq1 eq2 r-node = trans (just-injective (cong node-key (sym eq1))) (just-injective (cong node-key eq2)) + lem00 _ _ eq1 eq2 (r-right x rt1) = trans (just-injective (cong node-key (sym eq1))) (just-injective (cong node-key eq2)) + lem00 _ _ eq1 eq2 (r-left x rt1) = trans (just-injective (cong node-key (sym eq1))) (just-injective (cong node-key eq2)) open _∧_ @@ -244,25 +397,64 @@ treeLeftDown : {n : Level} {A : Set n} {k : ℕ} {v1 : A} → (tree tree₁ : bt A ) → treeInvariant (node k v1 tree tree₁) → treeInvariant tree -treeLeftDown {n} {A} {_} {v1} leaf leaf (t-single k1 v1) = t-leaf -treeLeftDown {n} {A} {_} {v1} .leaf .(node _ _ _ _) (t-right _ _ x _ _ ti) = t-leaf -treeLeftDown {n} {A} {_} {v1} .(node _ _ _ _) .leaf (t-left _ _ x _ _ ti) = ti -treeLeftDown {n} {A} {_} {v1} .(node _ _ _ _) .(node _ _ _ _) (t-node _ _ _ x x₁ _ _ _ _ ti ti₁) = ti +treeLeftDown {n} {A} {k} {v1} tree tree₁ ti = lem00 (node k v1 tree tree₁) refl ti where + lem00 : ( tr : bt A ) → tr ≡ node k v1 tree tree₁ → treeInvariant tr → treeInvariant tree + lem00 .leaf () t-leaf + lem00 .(node key value leaf leaf) eq (t-single key value) = subst (λ k → treeInvariant k ) (just-injective (cong node-left eq)) t-leaf + lem00 .(node key _ leaf (node key₁ _ _ _)) eq (t-right key key₁ x x₁ x₂ ti) = subst (λ k → treeInvariant k ) (just-injective (cong node-left eq)) t-leaf + lem00 .(node key₁ _ (node key _ _ _) leaf) eq (t-left key key₁ x x₁ x₂ ti) = subst (λ k → treeInvariant k ) (just-injective (cong node-left eq)) ti + lem00 .(node key₁ _ (node key _ _ _) (node key₂ _ _ _)) eq (t-node key key₁ key₂ x x₁ x₂ x₃ x₄ x₅ ti ti₁) = subst (λ k → treeInvariant k ) (just-injective (cong node-left eq)) ti treeRightDown : {n : Level} {A : Set n} {k : ℕ} {v1 : A} → (tree tree₁ : bt A ) → treeInvariant (node k v1 tree tree₁) → treeInvariant tree₁ -treeRightDown {n} {A} {_} {v1} .leaf .leaf (t-single _ .v1) = t-leaf -treeRightDown {n} {A} {_} {v1} .leaf .(node _ _ _ _) (t-right _ _ x _ _ ti) = ti -treeRightDown {n} {A} {_} {v1} .(node _ _ _ _) .leaf (t-left _ _ x _ _ ti) = t-leaf -treeRightDown {n} {A} {_} {v1} .(node _ _ _ _) .(node _ _ _ _) (t-node _ _ _ x x₁ _ _ _ _ ti ti₁) = ti₁ +treeRightDown {n} {A} {k} {v1} tree tree₁ ti = lem00 (node k v1 tree tree₁) refl ti where + lem00 : ( tr : bt A ) → tr ≡ node k v1 tree tree₁ → treeInvariant tr → treeInvariant tree₁ + lem00 .leaf () t-leaf + lem00 .(node key value leaf leaf) eq (t-single key value) = subst (λ k → treeInvariant k ) (just-injective (cong node-right eq)) t-leaf + lem00 .(node key _ leaf (node key₁ _ _ _)) eq (t-right key key₁ x x₁ x₂ ti) = subst (λ k → treeInvariant k ) (just-injective (cong node-right eq)) ti + lem00 .(node key₁ _ (node key _ _ _) leaf) eq (t-left key key₁ x x₁ x₂ ti) = subst (λ k → treeInvariant k ) (just-injective (cong node-right eq)) t-leaf + lem00 .(node key₁ _ (node key _ _ _) (node key₂ _ _ _)) eq (t-node key key₁ key₂ x x₁ x₂ x₃ x₄ x₅ ti ti₁) = subst (λ k → treeInvariant k ) (just-injective (cong node-right eq)) ti₁ + ti-property1 : {n : Level} {A : Set n} {key₁ : ℕ} {value₂ : A} {left right : bt A} → treeInvariant (node key₁ value₂ left right ) → tr< key₁ left ∧ tr> key₁ right -ti-property1 {n} {A} {key₁} {value₂} {.leaf} {.leaf} (t-single .key₁ .value₂) = ⟪ tt , tt ⟫ -ti-property1 {n} {A} {key₁} {value₂} {.leaf} {.(node key₂ _ _ _)} (t-right .key₁ key₂ x x₁ x₂ t) = ⟪ tt , ⟪ x , ⟪ x₁ , x₂ ⟫ ⟫ ⟫ -ti-property1 {n} {A} {key₁} {value₂} {.(node key _ _ _)} {.leaf} (t-left key .key₁ x x₁ x₂ t) = ⟪ ⟪ x , ⟪ x₁ , x₂ ⟫ ⟫ , tt ⟫ -ti-property1 {n} {A} {key₁} {value₂} {.(node key _ _ _)} {.(node key₂ _ _ _)} (t-node key .key₁ key₂ x x₁ x₂ x₃ x₄ x₅ t t₁) - = ⟪ ⟪ x , ⟪ x₂ , x₃ ⟫ ⟫ , ⟪ x₁ , ⟪ x₄ , x₅ ⟫ ⟫ ⟫ +ti-property1 {n} {A} {key₁} {value₂} {left} {right} ti = lem00 key₁ (node key₁ value₂ left right) refl ti where + lem00 : (key₁ : ℕ) → ( tree : bt A ) → tree ≡ node key₁ value₂ left right → treeInvariant tree → tr< key₁ left ∧ tr> key₁ right + lem00 - .leaf () t-leaf + lem00 key₁ .(node key value leaf leaf) eq (t-single key value) = subst₂ (λ j k → tr< key₁ j ∧ tr> key₁ k ) lem01 lem02 ⟪ tt , tt ⟫ where + lem01 : leaf ≡ left + lem01 = just-injective (cong node-left eq) + lem02 : leaf ≡ right + lem02 = just-injective (cong node-right eq) + lem00 key₂ .(node key _ leaf (node key₁ _ _ _)) eq (t-right key key₁ {value} {value₁} {t₁} {t₂} x x₁ x₂ ti) + = subst₂ (λ j k → tr< key₂ j ∧ tr> key₂ k ) lem01 lem02 ⟪ tt , ⟪ subst (λ k → k < key₁) lem04 x , + ⟪ subst (λ k → tr> k t₁) lem04 x₁ , subst (λ k → tr> k t₂) lem04 x₂ ⟫ ⟫ ⟫ where + lem01 : leaf ≡ left + lem01 = just-injective (cong node-left eq) + lem02 : node key₁ value₁ t₁ t₂ ≡ right + lem02 = just-injective (cong node-right eq) + lem04 : key ≡ key₂ + lem04 = just-injective (cong node-key eq) + lem00 key₂ .(node key₁ _ (node key _ _ _) leaf) eq (t-left key key₁ {value} {value₁} {t₁} {t₂} x x₁ x₂ ti) + = subst₂ (λ j k → tr< key₂ j ∧ tr> key₂ k ) lem02 lem01 ⟪ ⟪ subst (λ k → key < k) lem04 x , + ⟪ subst (λ k → tr< k t₁) lem04 x₁ , subst (λ k → tr< k t₂) lem04 x₂ ⟫ ⟫ , tt ⟫ where + lem01 : leaf ≡ right + lem01 = just-injective (cong node-right eq) + lem02 : node key value t₁ t₂ ≡ left + lem02 = just-injective (cong node-left eq) + lem04 : key₁ ≡ key₂ + lem04 = just-injective (cong node-key eq) + lem00 key₂ .(node key₁ _ (node key _ _ _) (node key₃ _ _ _)) eq (t-node key key₁ key₃ {value} {value₁} {value₂} + {t₁} {t₂} {t₃} {t₄} x x₁ x₂ x₃ x₄ x₅ ti ti₁) + = subst₂ (λ j k → tr< key₂ j ∧ tr> key₂ k ) lem01 lem02 ⟪ ⟪ subst (λ k → key < k) lem04 x , + ⟪ subst (λ k → tr< k t₁) lem04 x₂ , subst (λ k → tr< k t₂) lem04 x₃ ⟫ ⟫ + , ⟪ subst (λ k → k < key₃) lem04 x₁ , ⟪ subst (λ k → tr> k t₃) lem04 x₄ , subst (λ k → tr> k t₄) lem04 x₅ ⟫ ⟫ ⟫ where + lem01 : node key value t₁ t₂ ≡ left + lem01 = just-injective (cong node-left eq) + lem02 : node key₃ value₂ t₃ t₄ ≡ right + lem02 = just-injective (cong node-right eq) + lem04 : key₁ ≡ key₂ + lem04 = just-injective (cong node-key eq) findP : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree tree0 : bt A ) → (stack : List (bt A)) @@ -276,24 +468,14 @@ findP {n} {_} {A} key (node key₁ v1 tree tree₁) tree0 st Pre next _ | tri< a ¬b ¬c = next tree (tree ∷ st) ⟪ treeLeftDown tree tree₁ (proj1 Pre) , findP1 a st (proj2 Pre) ⟫ depth-1< where findP1 : key < key₁ → (st : List (bt A)) → stackInvariant key (node key₁ v1 tree tree₁) tree0 st → stackInvariant key tree tree0 (tree ∷ st) - findP1 a (x ∷ st) si = s-left _ _ _ a si + findP1 = ? -- a (x ∷ st) si = s-left _ _ _ a si findP key n@(node key₁ v1 tree tree₁) tree0 st Pre next _ | tri> ¬a ¬b c = next tree₁ (tree₁ ∷ st) ⟪ treeRightDown tree tree₁ (proj1 Pre) , s-right _ _ _ c (proj2 Pre) ⟫ depth-2< replaceTree1 : {n : Level} {A : Set n} {t t₁ : bt A } → ( k : ℕ ) → (v1 value : A ) → treeInvariant (node k v1 t t₁) → treeInvariant (node k value t t₁) -replaceTree1 k v1 value (t-single .k .v1) = t-single k value -replaceTree1 k v1 value (t-right _ _ x a b t) = t-right _ _ x a b t -replaceTree1 k v1 value (t-left _ _ x a b t) = t-left _ _ x a b t -replaceTree1 k v1 value (t-node _ _ _ x x₁ a b c d t t₁) = t-node _ _ _ x x₁ a b c d t t₁ +replaceTree1 k v1 value = ? open import Relation.Binary.Definitions -lemma3 : {i j : ℕ} → 0 ≡ i → j < i → ⊥ -lemma3 refl () -lemma5 : {i j : ℕ} → i < 1 → j < i → ⊥ -lemma5 (s≤s z≤n) () -¬x<x : {x : ℕ} → ¬ (x < x) -¬x<x (s≤s lt) = ¬x<x lt - child-replaced : {n : Level} {A : Set n} (key : ℕ) (tree : bt A) → bt A child-replaced key leaf = leaf child-replaced key (node key₁ value left right) with <-cmp key key₁ @@ -306,30 +488,27 @@ → child-replaced key (node key₁ value left right) ≡ left child-replaced-left {n} {A} {key} {key₁} {value} {left} {right} lt = ch00 (node key₁ value left right) refl lt where ch00 : (tree : bt A) → tree ≡ node key₁ value left right → key < key₁ → child-replaced key tree ≡ left - ch00 (node key₁ value tree tree₁) refl lt1 with <-cmp key key₁ - ... | tri< a ¬b ¬c = refl - ... | tri≈ ¬a b ¬c = ⊥-elim (¬a lt1) - ... | tri> ¬a ¬b c = ⊥-elim (¬a lt1) + ch00 = ? child-replaced-right : {n : Level} {A : Set n} {key key₁ : ℕ} {value : A} {left right : bt A} → key₁ < key → child-replaced key (node key₁ value left right) ≡ right child-replaced-right {n} {A} {key} {key₁} {value} {left} {right} lt = ch00 (node key₁ value left right) refl lt where ch00 : (tree : bt A) → tree ≡ node key₁ value left right → key₁ < key → child-replaced key tree ≡ right - ch00 (node key₁ value tree tree₁) refl lt1 with <-cmp key key₁ - ... | tri< a ¬b ¬c = ⊥-elim (¬c lt1) - ... | tri≈ ¬a b ¬c = ⊥-elim (¬c lt1) - ... | tri> ¬a ¬b c = refl + ch00 tree eq lt1 with <-cmp key key₁ + ... | tri< a ¬b ¬c = ⊥-elim (¬c ?) + ... | tri≈ ¬a b ¬c = ⊥-elim (¬c ?) + ... | tri> ¬a ¬b c = ? child-replaced-eq : {n : Level} {A : Set n} {key key₁ : ℕ} {value : A} {left right : bt A} → key₁ ≡ key → child-replaced key (node key₁ value left right) ≡ node key₁ value left right child-replaced-eq {n} {A} {key} {key₁} {value} {left} {right} lt = ch00 (node key₁ value left right) refl lt where ch00 : (tree : bt A) → tree ≡ node key₁ value left right → key₁ ≡ key → child-replaced key tree ≡ node key₁ value left right - ch00 (node key₁ value tree tree₁) refl lt1 with <-cmp key key₁ - ... | tri< a ¬b ¬c = ⊥-elim (¬b (sym lt1)) - ... | tri≈ ¬a b ¬c = refl - ... | tri> ¬a ¬b c = ⊥-elim (¬b (sym lt1)) + ch00 tree eq lt1 with <-cmp key key₁ + ... | tri< a ¬b ¬c = ⊥-elim (¬b (sym ?)) + ... | tri≈ ¬a b ¬c = ? + ... | tri> ¬a ¬b c = ⊥-elim (¬b (sym ?)) open _∧_ @@ -357,62 +536,47 @@ RTtoTI0 : {n : Level} {A : Set n} → (tree repl : bt A) → (key : ℕ) → (value : A) → treeInvariant tree → replacedTree key value tree repl → treeInvariant repl -RTtoTI0 .leaf .(node key value leaf leaf) key value ti r-leaf = t-single key value -RTtoTI0 .(node key _ leaf leaf) .(node key value leaf leaf) key value (t-single .key _) r-node = t-single key value -RTtoTI0 .(node key _ leaf (node _ _ _ _)) .(node key value leaf (node _ _ _ _)) key value (t-right _ _ x a b ti) r-node = t-right _ _ x a b ti -RTtoTI0 .(node key _ (node _ _ _ _) leaf) .(node key value (node _ _ _ _) leaf) key value (t-left _ _ x a b ti) r-node = t-left _ _ x a b ti -RTtoTI0 .(node key _ (node _ _ _ _) (node _ _ _ _)) .(node key value (node _ _ _ _) (node _ _ _ _)) key value (t-node _ _ _ x x₁ a b c d ti ti₁) r-node = t-node _ _ _ x x₁ a b c d ti ti₁ --- r-right case -RTtoTI0 (node _ _ leaf leaf) (node _ _ leaf .(node key value leaf leaf)) key value (t-single _ _) (r-right x r-leaf) = t-right _ _ x _ _ (t-single key value) -RTtoTI0 (node _ _ leaf right@(node _ _ _ _)) (node key₁ value₁ leaf leaf) key value (t-right _ _ x₁ a b ti) (r-right x ri) = t-single key₁ value₁ -RTtoTI0 (node key₁ _ leaf right@(node key₂ _ left₁ right₁)) (node key₁ value₁ leaf right₃@(node key₃ _ left₂ right₂)) key value (t-right key₄ key₅ x₁ a b ti) (r-right x ri) = - t-right _ _ (subst (λ k → key₁ < k ) (rt-property-key ri) x₁) (rr00 ri a ) (rr02 ri b) (RTtoTI0 right right₃ key value ti ri) where - rr00 : replacedTree key value (node key₂ _ left₁ right₁) (node key₃ _ left₂ right₂) → tr> key₁ left₁ → tr> key₁ left₂ - rr00 r-node tb = tb - rr00 (r-right x ri) tb = tb - rr00 (r-left x₂ ri) tb = ri-tr> _ _ _ _ _ ri x tb - rr02 : replacedTree key value (node key₂ _ left₁ right₁) (node key₃ _ left₂ right₂) → tr> key₁ right₁ → tr> key₁ right₂ - rr02 r-node tb = tb - rr02 (r-right x₂ ri) tb = ri-tr> _ _ _ _ _ ri x tb - rr02 (r-left x ri) tb = tb -RTtoTI0 (node key₁ _ (node _ _ _ _) leaf) (node key₁ _ (node key₃ value left right) leaf) key value₁ (t-left _ _ x₁ a b ti) (r-right x ()) -RTtoTI0 (node key₁ _ (node key₃ _ _ _) leaf) (node key₁ _ (node key₃ value₃ _ _) (node key value leaf leaf)) key value (t-left _ _ x₁ a b ti) (r-right x r-leaf) = - t-node _ _ _ x₁ x a b tt tt ti (t-single key value) -RTtoTI0 (node key₁ _ (node _ _ left₀ right₀) (node key₂ _ left₁ right₁)) (node key₁ _ (node _ _ left₂ right₂) (node key₃ _ left₃ right₃)) key value (t-node _ _ _ x₁ x₂ a b c d ti ti₁) (r-right x ri) = - t-node _ _ _ x₁ (subst (λ k → key₁ < k ) (rt-property-key ri) x₂) a b (rr00 ri c) (rr02 ri d) ti (RTtoTI0 _ _ key value ti₁ ri) where - rr00 : replacedTree key value (node key₂ _ _ _) (node key₃ _ _ _) → tr> key₁ left₁ → tr> key₁ left₃ - rr00 r-node tb = tb - rr00 (r-right x₃ ri) tb = tb - rr00 (r-left x₃ ri) tb = ri-tr> _ _ _ _ _ ri x tb - rr02 : replacedTree key value (node key₂ _ _ _) (node key₃ _ _ _) → tr> key₁ right₁ → tr> key₁ right₃ - rr02 r-node tb = tb - rr02 (r-right x₃ ri) tb = ri-tr> _ _ _ _ _ ri x tb - rr02 (r-left x₃ ri) tb = tb --- r-left case -RTtoTI0 .(node _ _ leaf leaf) .(node _ _ (node key value leaf leaf) leaf) key value (t-single _ _) (r-left x r-leaf) = t-left _ _ x tt tt (t-single _ _ ) -RTtoTI0 .(node _ _ leaf (node _ _ _ _)) (node key₁ value₁ (node key value leaf leaf) (node _ _ _ _)) key value (t-right _ _ x₁ a b ti) (r-left x r-leaf) = - t-node _ _ _ x x₁ tt tt a b (t-single key value) ti -RTtoTI0 (node key₃ _ (node key₂ _ left₁ right₁) leaf) (node key₃ _ (node key₁ value₁ left₂ right₂) leaf) key value (t-left _ _ x₁ a b ti) (r-left x ri) = - t-left _ _ (subst (λ k → k < key₃ ) (rt-property-key ri) x₁) (rr00 ri a) (rr02 ri b) (RTtoTI0 _ _ key value ti ri) where -- key₁ < key₃ - rr00 : replacedTree key value (node key₂ _ left₁ right₁) (node key₁ _ left₂ right₂) → tr< key₃ left₁ → tr< key₃ left₂ - rr00 r-node tb = tb - rr00 (r-right x₂ ri) tb = tb - rr00 (r-left x₂ ri) tb = ri-tr< _ _ _ _ _ ri x tb - rr02 : replacedTree key value (node key₂ _ left₁ right₁) (node key₁ _ left₂ right₂) → tr< key₃ right₁ → tr< key₃ right₂ - rr02 r-node tb = tb - rr02 (r-right x₃ ri) tb = ri-tr< _ _ _ _ _ ri x tb - rr02 (r-left x₃ ri) tb = tb -RTtoTI0 (node key₁ _ (node key₂ _ left₂ right₂) (node key₃ _ left₃ right₃)) (node key₁ _ (node key₄ _ left₄ right₄) (node key₅ _ left₅ right₅)) key value (t-node _ _ _ x₁ x₂ a b c d ti ti₁) (r-left x ri) = - t-node _ _ _ (subst (λ k → k < key₁ ) (rt-property-key ri) x₁) x₂ (rr00 ri a) (rr02 ri b) c d (RTtoTI0 _ _ key value ti ri) ti₁ where - rr00 : replacedTree key value (node key₂ _ left₂ right₂) (node key₄ _ left₄ right₄) → tr< key₁ left₂ → tr< key₁ left₄ - rr00 r-node tb = tb - rr00 (r-right x₃ ri) tb = tb - rr00 (r-left x₃ ri) tb = ri-tr< _ _ _ _ _ ri x tb - rr02 : replacedTree key value (node key₂ _ left₂ right₂) (node key₄ _ left₄ right₄) → tr< key₁ right₂ → tr< key₁ right₄ - rr02 r-node tb = tb - rr02 (r-right x₃ ri) tb = ri-tr< _ _ _ _ _ ri x tb - rr02 (r-left x₃ ri) tb = tb +RTtoTI0 = ? +-- RTtoTI0 .(node key _ leaf leaf) .(node key value leaf leaf) key value = ? +-- RTtoTI0 .(node key _ leaf (node _ _ _ _)) .(node key value leaf (node _ _ _ _)) key value (t-right _ _ x a b ti) r-node = t-right _ _ x a b ti +-- RTtoTI0 .(node key _ (node _ _ _ _) leaf) .(node key value (node _ _ _ _) leaf) key value (t-left _ _ x a b ti) r-node = t-left _ _ x a b ti +-- RTtoTI0 .(node key _ (node _ _ _ _) (node _ _ _ _)) .(node key value (node _ _ _ _) (node _ _ _ _)) key value (t-node _ _ _ x x₁ a b c d ti ti₁) r-node = t-node _ _ _ x x₁ a b c d ti ti₁ +-- -- r-right case +-- RTtoTI0 (node _ _ leaf leaf) (node _ _ leaf .(node key value leaf leaf)) key value (t-single _ _) (r-right x r-leaf) = t-right _ _ x _ _ (t-single key value) +-- RTtoTI0 (node _ _ leaf right@(node _ _ _ _)) (node key₁ value₁ leaf leaf) key value (t-right _ _ x₁ a b ti) (r-right x ri) = t-single key₁ value₁ +-- RTtoTI0 (node key₁ _ leaf right@(node key₂ _ left₁ right₁)) (node key₁ value₁ leaf right₃@(node key₃ _ left₂ right₂)) key value (t-right key₄ key₅ x₁ a b ti) (r-right x ri) = +-- t-right _ _ (subst (λ k → key₁ < k ) (rt-property-key ri) x₁) (rr00 ri a ) (rr02 ri b) (RTtoTI0 right right₃ key value ti ri) where +-- rr00 : replacedTree key value (node key₂ _ left₁ right₁) (node key₃ _ left₂ right₂) → tr> key₁ left₁ → tr> key₁ left₂ +-- rr00 = ? +-- rr02 : replacedTree key value (node key₂ _ left₁ right₁) (node key₃ _ left₂ right₂) → tr> key₁ right₁ → tr> key₁ right₂ +-- rr02 = ? +-- RTtoTI0 (node key₁ _ (node _ _ _ _) leaf) (node key₁ _ (node key₃ value left right) leaf) key value₁ (t-left _ _ x₁ a b ti) (r-right x ()) +-- RTtoTI0 (node key₁ _ (node key₃ _ _ _) leaf) (node key₁ _ (node key₃ value₃ _ _) (node key value leaf leaf)) key value (t-left _ _ x₁ a b ti) (r-right x r-leaf) = +-- t-node _ _ _ x₁ x a b tt tt ti (t-single key value) +-- RTtoTI0 (node key₁ _ (node _ _ left₀ right₀) (node key₂ _ left₁ right₁)) (node key₁ _ (node _ _ left₂ right₂) (node key₃ _ left₃ right₃)) key value (t-node _ _ _ x₁ x₂ a b c d ti ti₁) (r-right x ri) = +-- t-node _ _ _ x₁ (subst (λ k → key₁ < k ) (rt-property-key ri) x₂) a b (rr00 ri c) (rr02 ri d) ti (RTtoTI0 _ _ key value ti₁ ri) where +-- rr00 : replacedTree key value (node key₂ _ _ _) (node key₃ _ _ _) → tr> key₁ left₁ → tr> key₁ left₃ +-- rr00 = ? +-- rr02 : replacedTree key value (node key₂ _ _ _) (node key₃ _ _ _) → tr> key₁ right₁ → tr> key₁ right₃ +-- rr02 = ? +-- -- r-left case +-- RTtoTI0 .(node _ _ leaf leaf) .(node _ _ (node key value leaf leaf) leaf) key value (t-single _ _) (r-left x r-leaf) = t-left _ _ x tt tt (t-single _ _ ) +-- RTtoTI0 .(node _ _ leaf (node _ _ _ _)) (node key₁ value₁ (node key value leaf leaf) (node _ _ _ _)) key value (t-right _ _ x₁ a b ti) (r-left x r-leaf) = +-- t-node _ _ _ x x₁ tt tt a b (t-single key value) ti +-- RTtoTI0 (node key₃ _ (node key₂ _ left₁ right₁) leaf) (node key₃ _ (node key₁ value₁ left₂ right₂) leaf) key value (t-left _ _ x₁ a b ti) (r-left x ri) = +-- t-left _ _ (subst (λ k → k < key₃ ) (rt-property-key ri) x₁) (rr00 ri a) (rr02 ri b) (RTtoTI0 _ _ key value ti ri) where -- key₁ < key₃ +-- rr00 : replacedTree key value (node key₂ _ left₁ right₁) (node key₁ _ left₂ right₂) → tr< key₃ left₁ → tr< key₃ left₂ +-- rr00 = ? +-- rr02 : replacedTree key value (node key₂ _ left₁ right₁) (node key₁ _ left₂ right₂) → tr< key₃ right₁ → tr< key₃ right₂ +-- rr02 = ? +-- RTtoTI0 (node key₁ _ (node key₂ _ left₂ right₂) (node key₃ _ left₃ right₃)) (node key₁ _ (node key₄ _ left₄ right₄) (node key₅ _ left₅ right₅)) key value (t-node _ _ _ x₁ x₂ a b c d ti ti₁) (r-left x ri) = +-- t-node _ _ _ (subst (λ k → k < key₁ ) (rt-property-key ri) x₁) x₂ (rr00 ri a) (rr02 ri b) c d (RTtoTI0 _ _ key value ti ri) ti₁ where +-- rr00 : replacedTree key value (node key₂ _ left₂ right₂) (node key₄ _ left₄ right₄) → tr< key₁ left₂ → tr< key₁ left₄ +-- rr00 = ? +-- rr02 : replacedTree key value (node key₂ _ left₂ right₂) (node key₄ _ left₄ right₄) → tr< key₁ right₂ → tr< key₁ right₄ +-- rr02 = ? +-- -- RTtoTI1 : {n : Level} {A : Set n} → (tree repl : bt A) → (key : ℕ) → (value : A) → treeInvariant repl -- → replacedTree key value tree repl → treeInvariant tree -- RTtoTI1 .leaf .(node key value leaf leaf) key value ti r-leaf = t-leaf @@ -439,50 +603,14 @@ → ( tree parent orig : bt A) → (key : ℕ) → stackInvariant key tree orig ( tree ∷ parent ∷ rest ) → stackInvariant key parent orig (parent ∷ rest ) -popStackInvariant rest tree parent orig key (s-right .tree .orig tree₁ x si) = sc00 where - sc00 : stackInvariant key parent orig (parent ∷ rest ) - sc00 with si-property1 si - ... | refl = si -popStackInvariant rest tree parent orig key (s-left .tree .orig tree₁ x si) = sc00 where - sc00 : stackInvariant key parent orig (parent ∷ rest ) - sc00 with si-property1 si - ... | refl = si - +popStackInvariant rest tree parent orig key = ? siToTreeinvariant : {n : Level} {A : Set n} → (rest : List ( bt A)) → ( tree orig : bt A) → (key : ℕ) → treeInvariant orig → stackInvariant key tree orig ( tree ∷ rest ) → treeInvariant tree -siToTreeinvariant .[] tree .tree key ti s-nil = ti -siToTreeinvariant .(node _ _ leaf leaf ∷ []) .leaf .(node _ _ leaf leaf) key (t-single _ _) (s-right .leaf .(node _ _ leaf leaf) .leaf x s-nil) = t-leaf -siToTreeinvariant .(node _ _ leaf (node key₁ _ _ _) ∷ []) .(node key₁ _ _ _) .(node _ _ leaf (node key₁ _ _ _)) key (t-right _ key₁ x₁ x₂ x₃ ti) (s-right .(node key₁ _ _ _) .(node _ _ leaf (node key₁ _ _ _)) .leaf x s-nil) = ti -siToTreeinvariant .(node _ _ (node key₁ _ _ _) leaf ∷ []) .leaf .(node _ _ (node key₁ _ _ _) leaf) key (t-left key₁ _ x₁ x₂ x₃ ti) (s-right .leaf .(node _ _ (node key₁ _ _ _) leaf) .(node key₁ _ _ _) x s-nil) = t-leaf -siToTreeinvariant .(node _ _ (node key₁ _ _ _) (node key₂ _ _ _) ∷ []) .(node key₂ _ _ _) .(node _ _ (node key₁ _ _ _) (node key₂ _ _ _)) key (t-node key₁ _ key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (s-right .(node key₂ _ _ _) .(node _ _ (node key₁ _ _ _) (node key₂ _ _ _)) .(node key₁ _ _ _) x s-nil) = ti₁ -siToTreeinvariant .(node _ _ tree₁ tree ∷ _) tree orig key ti (s-right .tree .orig tree₁ x si2@(s-right .(node _ _ tree₁ tree) .orig tree₂ x₁ si)) with siToTreeinvariant _ _ _ _ ti si2 -... | t-single _ _ = t-leaf -... | t-right _ key₁ x₂ x₃ x₄ ti₁ = ti₁ -... | t-left key₁ _ x₂ x₃ x₄ ti₁ = t-leaf -... | t-node key₁ _ key₂ x₂ x₃ x₄ x₅ x₆ x₇ ti₁ ti₂ = ti₂ -siToTreeinvariant .(node _ _ tree₁ tree ∷ _) tree orig key ti (s-right .tree .orig tree₁ x si2@(s-left .(node _ _ tree₁ tree) .orig tree₂ x₁ si)) with siToTreeinvariant _ _ _ _ ti si2 -... | t-single _ _ = t-leaf -... | t-right _ key₁ x₂ x₃ x₄ ti₁ = ti₁ -... | t-left key₁ _ x₂ x₃ x₄ ti₁ = t-leaf -... | t-node key₁ _ key₂ x₂ x₃ x₄ x₅ x₆ x₇ ti₁ ti₂ = ti₂ -siToTreeinvariant .(node _ _ leaf leaf ∷ []) .leaf .(node _ _ leaf leaf) key (t-single _ _) (s-left .leaf .(node _ _ leaf leaf) .leaf x s-nil) = t-leaf -siToTreeinvariant .(node _ _ leaf (node key₁ _ _ _) ∷ []) .leaf .(node _ _ leaf (node key₁ _ _ _)) key (t-right _ key₁ x₁ x₂ x₃ ti) (s-left .leaf .(node _ _ leaf (node key₁ _ _ _)) .(node key₁ _ _ _) x s-nil) = t-leaf -siToTreeinvariant .(node _ _ (node key₁ _ _ _) leaf ∷ []) .(node key₁ _ _ _) .(node _ _ (node key₁ _ _ _) leaf) key (t-left key₁ _ x₁ x₂ x₃ ti) (s-left .(node key₁ _ _ _) .(node _ _ (node key₁ _ _ _) leaf) .leaf x s-nil) = ti -siToTreeinvariant .(node _ _ (node key₁ _ _ _) (node key₂ _ _ _) ∷ []) .(node key₁ _ _ _) .(node _ _ (node key₁ _ _ _) (node key₂ _ _ _)) key (t-node key₁ _ key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (s-left .(node key₁ _ _ _) .(node _ _ (node key₁ _ _ _) (node key₂ _ _ _)) .(node key₂ _ _ _) x s-nil) = ti -siToTreeinvariant .(node _ _ tree tree₁ ∷ _) tree orig key ti (s-left .tree .orig tree₁ x si2@(s-right .(node _ _ tree tree₁) .orig tree₂ x₁ si)) with siToTreeinvariant _ _ _ _ ti si2 -... | t-single _ _ = t-leaf -... | t-right _ key₁ x₂ x₃ x₄ t = t-leaf -... | t-left key₁ _ x₂ x₃ x₄ t = t -... | t-node key₁ _ key₂ x₂ x₃ x₄ x₅ x₆ x₇ t t₁ = t -siToTreeinvariant .(node _ _ tree tree₁ ∷ _) tree orig key ti (s-left .tree .orig tree₁ x si2@(s-left .(node _ _ tree tree₁) .orig tree₂ x₁ si)) with siToTreeinvariant _ _ _ _ ti si2 -... | t-single _ _ = t-leaf -... | t-right _ key₁ x₂ x₃ x₄ t = t-leaf -... | t-left key₁ _ x₂ x₃ x₄ t = t -... | t-node key₁ _ key₂ x₂ x₃ x₄ x₅ x₆ x₇ t t₁ = t +siToTreeinvariant = ? record replacePR {n : Level} {A : Set n} (key : ℕ) (value : A) (tree repl : bt A ) (stack : List (bt A)) (C : bt A → bt A → List (bt A) → Set n) : Set n where field @@ -496,15 +624,16 @@ replaceNodeP : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (value : A) → (tree : bt A) → (tree ≡ leaf ) ∨ ( node-key tree ≡ just key ) → (treeInvariant tree ) → ((tree1 : bt A) → treeInvariant tree1 → replacedTree key value (child-replaced key tree) tree1 → t) → t -replaceNodeP k v1 leaf C P next = next (node k v1 leaf leaf) (t-single k v1 ) r-leaf -replaceNodeP k v1 (node .k value t t₁) (case2 refl) P next = next (node k v1 t t₁) (replaceTree1 k value v1 P) - (subst (λ j → replacedTree k v1 j (node k v1 t t₁) ) repl00 r-node) where - repl00 : node k value t t₁ ≡ child-replaced k (node k value t t₁) - repl00 with <-cmp k k - ... | tri< a ¬b ¬c = ⊥-elim (¬b refl) - ... | tri≈ ¬a b ¬c = refl - ... | tri> ¬a ¬b c = ⊥-elim (¬b refl) - +replaceNodeP = ? +-- replaceNodeP k v1 leaf C P next = next (node k v1 leaf leaf) (t-single k v1 ) r-leaf +-- replaceNodeP k v1 (node .k value t t₁) (case2 refl) P next = next (node k v1 t t₁) (replaceTree1 k value v1 P) +-- (subst (λ j → replacedTree k v1 j (node k v1 t t₁) ) repl00 r-node) where +-- repl00 : node k value t t₁ ≡ child-replaced k (node k value t t₁) +-- repl00 with <-cmp k k +-- ... | tri< a ¬b ¬c = ⊥-elim (¬b refl) +-- ... | tri≈ ¬a b ¬c = refl +-- ... | tri> ¬a ¬b c = ⊥-elim (¬b refl) +-- replaceP : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (value : A) → {tree : bt A} ( repl : bt A) @@ -514,15 +643,16 @@ → (exit : (tree1 repl : bt A) → treeInvariant repl ∧ replacedTree key value tree1 repl → t) → t replaceP key value {tree} repl [] Pre next exit = ⊥-elim ( si-property0 (replacePR.si Pre) refl ) -- can't happen replaceP key value {tree} repl (leaf ∷ []) Pre next exit with si-property-last _ _ _ _ (replacePR.si Pre)-- tree0 ≡ leaf -... | refl = exit (replacePR.tree0 Pre) (node key value leaf leaf) ⟪ t-single _ _ , r-leaf ⟫ +... | eq = exit (replacePR.tree0 Pre) (node key value leaf leaf) ⟪ t-single _ _ , ? ⟫ replaceP key value {tree} repl (node key₁ value₁ left right ∷ []) Pre next exit with <-cmp key key₁ ... | tri< a ¬b ¬c = exit (replacePR.tree0 Pre) (node key₁ value₁ repl right ) ⟪ RTtoTI0 _ _ _ _ (replacePR.ti Pre) repl01 , repl01 ⟫ where repl01 : replacedTree key value (replacePR.tree0 Pre) (node key₁ value₁ repl right ) - repl01 with si-property1 (replacePR.si Pre) | si-property-last _ _ _ _ (replacePR.si Pre) - repl01 | refl | refl = subst (λ k → replacedTree key value (node key₁ value₁ k right ) (node key₁ value₁ repl right )) repl02 (r-left a repl03) where + -- repl01 = ? --with si-property1 (replacePR.si Pre) | si-property-last _ _ _ _ (replacePR.si Pre) + repl01 = ? where + -- | refl | refl = subst (λ k → replacedTree key value (node key₁ value₁ k right ) (node key₁ value₁ repl right )) repl02 (r-left a repl03) where repl03 : replacedTree key value ( child-replaced key (node key₁ value₁ left right)) repl - repl03 = replacePR.ri Pre + repl03 = replacePR.ri ? repl02 : child-replaced key (node key₁ value₁ left right) ≡ left repl02 with <-cmp key key₁ ... | tri< a ¬b ¬c = refl @@ -530,8 +660,9 @@ ... | tri> ¬a ¬b c = ⊥-elim ( ¬a a) ... | tri≈ ¬a b ¬c = exit (replacePR.tree0 Pre) repl ⟪ RTtoTI0 _ _ _ _ (replacePR.ti Pre) repl01 , repl01 ⟫ where repl01 : replacedTree key value (replacePR.tree0 Pre) repl - repl01 with si-property1 (replacePR.si Pre) | si-property-last _ _ _ _ (replacePR.si Pre) - repl01 | refl | refl = subst (λ k → replacedTree key value k repl) repl02 (replacePR.ri Pre) where + --repl01 with si-property1 (replacePR.si Pre) | si-property-last _ _ _ _ (replacePR.si Pre) + repl01 = ? where + --repl01 | refl | refl = subst (λ k → replacedTree key value k repl) repl02 (replacePR.ri Pre) where repl02 : child-replaced key (node key₁ value₁ left right) ≡ node key₁ value₁ left right repl02 with <-cmp key key₁ ... | tri< a ¬b ¬c = ⊥-elim ( ¬b b) @@ -539,10 +670,11 @@ ... | tri> ¬a ¬b c = ⊥-elim ( ¬b b) ... | tri> ¬a ¬b c = exit (replacePR.tree0 Pre) (node key₁ value₁ left repl ) ⟪ RTtoTI0 _ _ _ _ (replacePR.ti Pre) repl01 , repl01 ⟫ where repl01 : replacedTree key value (replacePR.tree0 Pre) (node key₁ value₁ left repl ) - repl01 with si-property1 (replacePR.si Pre) | si-property-last _ _ _ _ (replacePR.si Pre) - repl01 | refl | refl = subst (λ k → replacedTree key value (node key₁ value₁ left k ) (node key₁ value₁ left repl )) repl02 (r-right c repl03) where + -- repl01 with si-property1 (replacePR.si Pre) | si-property-last _ _ _ _ (replacePR.si Pre) + repl01 = ? where + -- repl01 | refl | refl = subst (λ k → replacedTree key value (node key₁ value₁ left k ) (node key₁ value₁ left repl )) repl02 (r-right c repl03) where repl03 : replacedTree key value ( child-replaced key (node key₁ value₁ left right)) repl - repl03 = replacePR.ri Pre + repl03 = replacePR.ri ? repl02 : child-replaced key (node key₁ value₁ left right) ≡ right repl02 with <-cmp key key₁ ... | tri< a ¬b ¬c = ⊥-elim ( ¬c c) @@ -550,216 +682,218 @@ ... | tri> ¬a ¬b c = refl replaceP {n} {_} {A} key value {tree} repl (leaf ∷ st@(tree1 ∷ st1)) Pre next exit = next key value repl st Post ≤-refl where Post : replacePR key value tree1 repl (tree1 ∷ st1) (λ _ _ _ → Lift n ⊤) - Post with replacePR.si Pre - ... | s-right _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; ri = repl12 ; - rti = replacePR.rti Pre ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 tree₁ leaf - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl07 : child-replaced key (node key₂ v1 tree₁ leaf) ≡ leaf - repl07 with <-cmp key key₂ - ... | tri< a ¬b ¬c = ⊥-elim (¬c x) - ... | tri≈ ¬a b ¬c = ⊥-elim (¬c x) - ... | tri> ¬a ¬b c = refl - repl12 : replacedTree key value (child-replaced key tree1 ) repl - repl12 = subst₂ (λ j k → replacedTree key value j k ) (sym (subst (λ k → child-replaced key k ≡ leaf) (sym repl09) repl07 ) ) (sym (rt-property-leaf (replacePR.ri Pre))) r-leaf - ... | s-left _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = replacePR.rti Pre ; ri = repl12 ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 leaf tree₁ - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl07 : child-replaced key (node key₂ v1 leaf tree₁ ) ≡ leaf - repl07 with <-cmp key key₂ - ... | tri< a ¬b ¬c = refl - ... | tri≈ ¬a b ¬c = ⊥-elim (¬a x) - ... | tri> ¬a ¬b c = ⊥-elim (¬a x) - repl12 : replacedTree key value (child-replaced key tree1 ) repl - repl12 = subst₂ (λ j k → replacedTree key value j k ) (sym (subst (λ k → child-replaced key k ≡ leaf) (sym repl09) repl07) ) (sym (rt-property-leaf (replacePR.ri Pre ))) r-leaf + Post = ? -- where with replacePR.si Pre +-- -- ... | s-right _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; ri = repl12 ; +-- rti = replacePR.rti Pre ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 tree₁ leaf +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl07 : child-replaced key (node key₂ v1 tree₁ leaf) ≡ leaf +-- repl07 with <-cmp key key₂ +-- ... | tri< a ¬b ¬c = ⊥-elim (¬c x) +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬c x) +-- ... | tri> ¬a ¬b c = refl +-- repl12 : replacedTree key value (child-replaced key tree1 ) repl +-- repl12 = subst₂ (λ j k → replacedTree key value j k ) (sym (subst (λ k → child-replaced key k ≡ leaf) (sym repl09) repl07 ) ) (sym (rt-property-leaf (replacePR.ri Pre))) r-leaf +-- ... | s-left _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = replacePR.rti Pre ; ri = repl12 ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 leaf tree₁ +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl07 : child-replaced key (node key₂ v1 leaf tree₁ ) ≡ leaf +-- repl07 with <-cmp key key₂ +-- ... | tri< a ¬b ¬c = refl +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬a x) +-- ... | tri> ¬a ¬b c = ⊥-elim (¬a x) +-- repl12 : replacedTree key value (child-replaced key tree1 ) repl +-- repl12 = subst₂ (λ j k → replacedTree key value j k ) (sym (subst (λ k → child-replaced key k ≡ leaf) (sym repl09) repl07) ) (sym (rt-property-leaf (replacePR.ri Pre ))) r-leaf replaceP {n} {_} {A} key value {tree} repl (node key₁ value₁ left right ∷ st@(tree1 ∷ st1)) Pre next exit with <-cmp key key₁ ... | tri< a ¬b ¬c = next key value (node key₁ value₁ repl right ) st Post ≤-refl where Post : replacePR key value tree1 (node key₁ value₁ repl right ) st (λ _ _ _ → Lift n ⊤) - Post with replacePR.si Pre - ... | s-right _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 - ; rti = repl13 - ; ri = repl12 ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 tree₁ (node key₁ value₁ left right) - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl11 : stackInvariant key (node key₂ v1 tree₁ (node key₁ value₁ left right)) (replacePR.tree0 Pre) (node key₂ v1 tree₁ (node key₁ value₁ left right)∷ st1) - repl11 = subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10 - repl03 : child-replaced key (node key₁ value₁ left right) ≡ left - repl03 with <-cmp key key₁ - ... | tri< a1 ¬b ¬c = refl - ... | tri≈ ¬a b ¬c = ⊥-elim (¬a a) - ... | tri> ¬a ¬b c = ⊥-elim (¬a a) - repl02 : child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡ node key₁ value₁ left right - repl02 with repl09 | <-cmp key key₂ - ... | refl | tri< a ¬b ¬c = ⊥-elim (¬c lt) - ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬c lt) - ... | refl | tri> ¬a ¬b c = refl - repl04 : node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡ child-replaced key tree1 - repl04 = begin - node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡⟨ cong (λ k → node key₁ value₁ k right) repl03 ⟩ - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 - repl05 = begin - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ repl right) - repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ repl right) ) repl04 (r-left a (replacePR.ri Pre)) - repl13 : treeInvariant (node key₁ value₁ repl right) - repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeRightDown _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) repl11 ) )) repl12 - ... | s-left _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 (node key₁ value₁ left right) tree₁ - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl03 : child-replaced key (node key₁ value₁ left right) ≡ left - repl03 with <-cmp key key₁ - ... | tri< a1 ¬b ¬c = refl - ... | tri≈ ¬a b ¬c = ⊥-elim (¬a a) - ... | tri> ¬a ¬b c = ⊥-elim (¬a a) - repl02 : child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡ node key₁ value₁ left right - repl02 with repl09 | <-cmp key key₂ - ... | refl | tri< a ¬b ¬c = refl - ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬a lt) - ... | refl | tri> ¬a ¬b c = ⊥-elim (¬a lt) - repl04 : node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡ child-replaced key tree1 - repl04 = begin - node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡⟨ cong (λ k → node key₁ value₁ k right) repl03 ⟩ - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 - repl05 = begin - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ repl right) - repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ repl right) ) repl04 (r-left a (replacePR.ri Pre)) - repl11 = subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10 - repl13 : treeInvariant (node key₁ value₁ repl right) - repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeLeftDown _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) repl11 ) )) repl12 + Post = ? -- with replacePR.si Pre +-- ... | s-right _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 +-- ; rti = repl13 +-- ; ri = repl12 ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 tree₁ (node key₁ value₁ left right) +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl11 : stackInvariant key (node key₂ v1 tree₁ (node key₁ value₁ left right)) (replacePR.tree0 Pre) (node key₂ v1 tree₁ (node key₁ value₁ left right)∷ st1) +-- repl11 = subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10 +-- repl03 : child-replaced key (node key₁ value₁ left right) ≡ left +-- repl03 with <-cmp key key₁ +-- ... | tri< a1 ¬b ¬c = refl +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬a a) +-- ... | tri> ¬a ¬b c = ⊥-elim (¬a a) +-- repl02 : child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡ node key₁ value₁ left right +-- repl02 with repl09 | <-cmp key key₂ +-- ... | refl | tri< a ¬b ¬c = ⊥-elim (¬c lt) +-- ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬c lt) +-- ... | refl | tri> ¬a ¬b c = refl +-- repl04 : node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡ child-replaced key tree1 +-- repl04 = begin +-- node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡⟨ cong (λ k → node key₁ value₁ k right) repl03 ⟩ +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 +-- repl05 = begin +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ repl right) +-- repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ repl right) ) repl04 (r-left a (replacePR.ri Pre)) +-- repl13 : treeInvariant (node key₁ value₁ repl right) +-- repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeRightDown _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) repl11 ) )) repl12 +-- ... | s-left _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 (node key₁ value₁ left right) tree₁ +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl03 : child-replaced key (node key₁ value₁ left right) ≡ left +-- repl03 with <-cmp key key₁ +-- ... | tri< a1 ¬b ¬c = refl +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬a a) +-- ... | tri> ¬a ¬b c = ⊥-elim (¬a a) +-- repl02 : child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡ node key₁ value₁ left right +-- repl02 with repl09 | <-cmp key key₂ +-- ... | refl | tri< a ¬b ¬c = refl +-- ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬a lt) +-- ... | refl | tri> ¬a ¬b c = ⊥-elim (¬a lt) +-- repl04 : node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡ child-replaced key tree1 +-- repl04 = begin +-- node key₁ value₁ (child-replaced key (node key₁ value₁ left right)) right ≡⟨ cong (λ k → node key₁ value₁ k right) repl03 ⟩ +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 +-- repl05 = begin +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ repl right) +-- repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ repl right) ) repl04 (r-left a (replacePR.ri Pre)) +-- repl11 = subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10 +-- repl13 : treeInvariant (node key₁ value₁ repl right) +-- repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeLeftDown _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) repl11 ) )) repl12 ... | tri≈ ¬a b ¬c = next key value (node key₁ value left right ) st Post ≤-refl where Post : replacePR key value tree1 (node key₁ value left right ) (tree1 ∷ st1) (λ _ _ _ → Lift n ⊤) - Post with replacePR.si Pre - ... | s-right _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 b ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 tree₁ tree -- (node key₁ value₁ left right) - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl07 : child-replaced key (node key₂ v1 tree₁ tree) ≡ tree - repl07 with <-cmp key key₂ - ... | tri< a ¬b ¬c = ⊥-elim (¬c x) - ... | tri≈ ¬a b ¬c = ⊥-elim (¬c x) - ... | tri> ¬a ¬b c = refl - repl12 : (key ≡ key₁) → replacedTree key value (child-replaced key tree1 ) (node key₁ value left right ) - repl12 refl with repl09 - ... | refl = subst (λ k → replacedTree key value k (node key₁ value left right )) (sym repl07) r-node - repl13 : treeInvariant (node key₁ value left right) - repl13 = RTtoTI0 _ _ _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) (replacePR.si Pre)) r-node - ... | s-left _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 b ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 tree tree₁ - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl07 : child-replaced key (node key₂ v1 tree tree₁ ) ≡ tree - repl07 with <-cmp key key₂ - ... | tri< a ¬b ¬c = refl - ... | tri≈ ¬a b ¬c = ⊥-elim (¬a x) - ... | tri> ¬a ¬b c = ⊥-elim (¬a x) - repl12 : (key ≡ key₁) → replacedTree key value (child-replaced key tree1 ) (node key₁ value left right ) - repl12 refl with repl09 - ... | refl = subst (λ k → replacedTree key value k (node key₁ value left right )) (sym repl07) r-node - repl13 : treeInvariant (node key₁ value left right) - repl13 = RTtoTI0 _ _ _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) (replacePR.si Pre)) r-node + Post = ? +-- with replacePR.si Pre +-- ... | s-right _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 b ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 tree₁ tree -- (node key₁ value₁ left right) +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl07 : child-replaced key (node key₂ v1 tree₁ tree) ≡ tree +-- repl07 with <-cmp key key₂ +-- ... | tri< a ¬b ¬c = ⊥-elim (¬c x) +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬c x) +-- ... | tri> ¬a ¬b c = refl +-- repl12 : (key ≡ key₁) → replacedTree key value (child-replaced key tree1 ) (node key₁ value left right ) +-- repl12 refl with repl09 +-- ... | refl = subst (λ k → replacedTree key value k (node key₁ value left right )) (sym repl07) r-node +-- repl13 : treeInvariant (node key₁ value left right) +-- repl13 = RTtoTI0 _ _ _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) (replacePR.si Pre)) r-node +-- ... | s-left _ _ tree₁ {key₂} {v1} x si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 b ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 tree tree₁ +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl07 : child-replaced key (node key₂ v1 tree tree₁ ) ≡ tree +-- repl07 with <-cmp key key₂ +-- ... | tri< a ¬b ¬c = refl +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬a x) +-- ... | tri> ¬a ¬b c = ⊥-elim (¬a x) +-- repl12 : (key ≡ key₁) → replacedTree key value (child-replaced key tree1 ) (node key₁ value left right ) +-- repl12 refl with repl09 +-- ... | refl = subst (λ k → replacedTree key value k (node key₁ value left right )) (sym repl07) r-node +-- repl13 : treeInvariant (node key₁ value left right) +-- repl13 = RTtoTI0 _ _ _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) (replacePR.si Pre)) r-node ... | tri> ¬a ¬b c = next key value (node key₁ value₁ left repl ) st Post ≤-refl where Post : replacePR key value tree1 (node key₁ value₁ left repl ) st (λ _ _ _ → Lift n ⊤) - Post with replacePR.si Pre - ... | s-right _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 tree₁ (node key₁ value₁ left right) - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl03 : child-replaced key (node key₁ value₁ left right) ≡ right - repl03 with <-cmp key key₁ - ... | tri< a1 ¬b ¬c = ⊥-elim (¬c c) - ... | tri≈ ¬a b ¬c = ⊥-elim (¬c c) - ... | tri> ¬a ¬b c = refl - repl02 : child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡ node key₁ value₁ left right - repl02 with repl09 | <-cmp key key₂ - ... | refl | tri< a ¬b ¬c = ⊥-elim (¬c lt) - ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬c lt) - ... | refl | tri> ¬a ¬b c = refl - repl04 : node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡ child-replaced key tree1 - repl04 = begin - node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡⟨ cong (λ k → node key₁ value₁ left k ) repl03 ⟩ - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 - repl05 = begin - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ left repl) - repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ left repl) ) repl04 (r-right c (replacePR.ri Pre)) - repl11 = subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10 - repl13 : treeInvariant (node key₁ value₁ left repl) - repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeRightDown _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) repl11 ) )) repl12 - ... | s-left _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 ; ci = lift tt } where - repl09 : tree1 ≡ node key₂ v1 (node key₁ value₁ left right) tree₁ - repl09 = si-property1 si - repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) - repl10 with si-property1 si - ... | refl = si - repl03 : child-replaced key (node key₁ value₁ left right) ≡ right - repl03 with <-cmp key key₁ - ... | tri< a1 ¬b ¬c = ⊥-elim (¬c c) - ... | tri≈ ¬a b ¬c = ⊥-elim (¬c c) - ... | tri> ¬a ¬b c = refl - repl02 : child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡ node key₁ value₁ left right - repl02 with repl09 | <-cmp key key₂ - ... | refl | tri< a ¬b ¬c = refl - ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬a lt) - ... | refl | tri> ¬a ¬b c = ⊥-elim (¬a lt) - repl04 : node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡ child-replaced key tree1 - repl04 = begin - node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡⟨ cong (λ k → node key₁ value₁ left k ) repl03 ⟩ - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 - repl05 = begin - node key₁ value₁ left right ≡⟨ sym repl02 ⟩ - child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ - child-replaced key tree1 ∎ where open ≡-Reasoning - repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ left repl) - repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ left repl) ) repl04 (r-right c (replacePR.ri Pre)) - repl13 : treeInvariant (node key₁ value₁ left repl) - repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeLeftDown _ _ - (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) (subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10)) )) repl12 + Post = ? + -- with replacePR.si Pre +-- ... | s-right _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 tree₁ (node key₁ value₁ left right) +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl03 : child-replaced key (node key₁ value₁ left right) ≡ right +-- repl03 with <-cmp key key₁ +-- ... | tri< a1 ¬b ¬c = ⊥-elim (¬c c) +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬c c) +-- ... | tri> ¬a ¬b c = refl +-- repl02 : child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡ node key₁ value₁ left right +-- repl02 with repl09 | <-cmp key key₂ +-- ... | refl | tri< a ¬b ¬c = ⊥-elim (¬c lt) +-- ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬c lt) +-- ... | refl | tri> ¬a ¬b c = refl +-- repl04 : node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡ child-replaced key tree1 +-- repl04 = begin +-- node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡⟨ cong (λ k → node key₁ value₁ left k ) repl03 ⟩ +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 +-- repl05 = begin +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 tree₁ (node key₁ value₁ left right) ) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ left repl) +-- repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ left repl) ) repl04 (r-right c (replacePR.ri Pre)) +-- repl11 = subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10 +-- repl13 : treeInvariant (node key₁ value₁ left repl) +-- repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeRightDown _ _ (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) repl11 ) )) repl12 +-- ... | s-left _ _ tree₁ {key₂} {v1} lt si = record { tree0 = replacePR.tree0 Pre ; ti = replacePR.ti Pre ; si = repl10 ; rti = repl13 ; ri = repl12 ; ci = lift tt } where +-- repl09 : tree1 ≡ node key₂ v1 (node key₁ value₁ left right) tree₁ +-- repl09 = si-property1 si +-- repl10 : stackInvariant key tree1 (replacePR.tree0 Pre) (tree1 ∷ st1) +-- repl10 with si-property1 si +-- ... | refl = si +-- repl03 : child-replaced key (node key₁ value₁ left right) ≡ right +-- repl03 with <-cmp key key₁ +-- ... | tri< a1 ¬b ¬c = ⊥-elim (¬c c) +-- ... | tri≈ ¬a b ¬c = ⊥-elim (¬c c) +-- ... | tri> ¬a ¬b c = refl +-- repl02 : child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡ node key₁ value₁ left right +-- repl02 with repl09 | <-cmp key key₂ +-- ... | refl | tri< a ¬b ¬c = refl +-- ... | refl | tri≈ ¬a b ¬c = ⊥-elim (¬a lt) +-- ... | refl | tri> ¬a ¬b c = ⊥-elim (¬a lt) +-- repl04 : node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡ child-replaced key tree1 +-- repl04 = begin +-- node key₁ value₁ left (child-replaced key (node key₁ value₁ left right)) ≡⟨ cong (λ k → node key₁ value₁ left k ) repl03 ⟩ +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl05 : node key₁ value₁ left right ≡ child-replaced key tree1 +-- repl05 = begin +-- node key₁ value₁ left right ≡⟨ sym repl02 ⟩ +-- child-replaced key (node key₂ v1 (node key₁ value₁ left right) tree₁) ≡⟨ cong (λ k → child-replaced key k ) (sym repl09) ⟩ +-- child-replaced key tree1 ∎ where open ≡-Reasoning +-- repl12 : replacedTree key value (child-replaced key tree1 ) (node key₁ value₁ left repl) +-- repl12 = subst (λ k → replacedTree key value k (node key₁ value₁ left repl) ) repl04 (r-right c (replacePR.ri Pre)) +-- repl13 : treeInvariant (node key₁ value₁ left repl) +-- repl13 = RTtoTI0 _ _ _ _ (subst (λ k → treeInvariant k) repl05 (treeLeftDown _ _ +-- (siToTreeinvariant _ _ _ _ (replacePR.ti Pre) (subst (λ k → stackInvariant key k (replacePR.tree0 Pre) (k ∷ st1)) repl09 repl10)) )) repl12 TerminatingLoopS : {l m : Level} {t : Set l} (Index : Set m ) → {Invraiant : Index → Set m } → ( reduce : Index → ℕ) → (r : Index) → (p : Invraiant r) → (loop : (r : Index) → Invraiant r → (next : (r1 : Index) → Invraiant r1 → reduce r1 < reduce r → t ) → t) → t TerminatingLoopS {_} {_} {t} Index {Invraiant} reduce r p loop with <-cmp 0 (reduce r) -... | tri≈ ¬a b ¬c = loop r p (λ r1 p1 lt → ⊥-elim (lemma3 b lt) ) +... | tri≈ ¬a b ¬c = loop r p (λ r1 p1 lt → ⊥-elim ? ) -- ... | tri< a ¬b ¬c = loop r p (λ r1 p1 lt1 → TerminatingLoop1 (reduce r) r r1 (m≤n⇒m≤1+n lt1) p1 lt1 ) where TerminatingLoop1 : (j : ℕ) → (r r1 : Index) → reduce r1 < suc j → Invraiant r1 → reduce r1 < reduce r → t - TerminatingLoop1 zero r r1 n≤j p1 lt = loop r1 p1 (λ r2 p1 lt1 → ⊥-elim (lemma5 n≤j lt1)) + TerminatingLoop1 zero r r1 n≤j p1 lt = loop r1 p1 (λ r2 p1 lt1 → ⊥-elim ?) -- (lemma5 n≤j lt1)) TerminatingLoop1 (suc j) r r1 n≤j p1 lt with <-cmp (reduce r1) (suc j) ... | tri< a ¬b ¬c = TerminatingLoop1 j r r1 a p1 lt ... | tri≈ ¬a b ¬c = loop r1 p1 (λ r2 p2 lt1 → TerminatingLoop1 j r1 r2 (subst (λ k → reduce r2 < k ) b lt1 ) p2 lt1 ) @@ -849,57 +983,44 @@ → (left right : bt (Color ∧ A)) → RBtreeInvariant (node key ⟪ c , value ⟫ left right) → RBtreeInvariant left -RBtreeLeftDown left right (rb-red _ _ x x₁ x₂ rb rb₁) = rb -RBtreeLeftDown left right (rb-black _ _ x rb rb₁) = rb +RBtreeLeftDown left right = ? RBtreeRightDown : {n : Level} {A : Set n} { key : ℕ} {value : A} {c : Color} → (left right : bt (Color ∧ A)) → RBtreeInvariant (node key ⟪ c , value ⟫ left right) → RBtreeInvariant right -RBtreeRightDown left right (rb-red _ _ x x₁ x₂ rb rb₁) = rb₁ -RBtreeRightDown left right (rb-black _ _ x rb rb₁) = rb₁ +RBtreeRightDown left right = ? RBtreeEQ : {n : Level} {A : Set n} {key : ℕ} {value : A} {c : Color} → {left right : bt (Color ∧ A)} → RBtreeInvariant (node key ⟪ c , value ⟫ left right) → black-depth left ≡ black-depth right -RBtreeEQ (rb-red _ _ x x₁ x₂ rb rb₁) = x₂ -RBtreeEQ (rb-black _ _ x rb rb₁) = x +RBtreeEQ = ? RBtreeToBlack : {n : Level} {A : Set n} → (tree : bt (Color ∧ A)) → RBtreeInvariant tree → RBtreeInvariant (to-black tree) -RBtreeToBlack leaf rb-leaf = rb-leaf -RBtreeToBlack (node key ⟪ Red , value ⟫ left right) (rb-red _ _ x x₁ x₂ rb rb₁) = rb-black key value x₂ rb rb₁ -RBtreeToBlack (node key ⟪ Black , value ⟫ left right) (rb-black _ _ x rb rb₁) = rb-black key value x rb rb₁ +RBtreeToBlack = ? RBtreeToBlackColor : {n : Level} {A : Set n} → (tree : bt (Color ∧ A)) → RBtreeInvariant tree → color (to-black tree) ≡ Black -RBtreeToBlackColor leaf rb-leaf = refl -RBtreeToBlackColor (node key ⟪ Red , value ⟫ left right) (rb-red _ _ x x₁ x₂ rb rb₁) = refl -RBtreeToBlackColor (node key ⟪ Black , value ⟫ left right) (rb-black _ _ x rb rb₁) = refl +RBtreeToBlackColor = ? RBtreeParentColorBlack : {n : Level} {A : Set n} → (left right : bt (Color ∧ A)) { value : A} {key : ℕ} { c : Color} → RBtreeInvariant (node key ⟪ c , value ⟫ left right) → (color left ≡ Red) ∨ (color right ≡ Red) → c ≡ Black -RBtreeParentColorBlack leaf leaf (rb-red _ _ x₁ x₂ x₃ x₄ x₅) (case1 ()) -RBtreeParentColorBlack leaf leaf (rb-red _ _ x₁ x₂ x₃ x₄ x₅) (case2 ()) -RBtreeParentColorBlack (node key ⟪ Red , proj4 ⟫ left left₁) right (rb-red _ _ () x₁ x₂ rb rb₁) (case1 x₃) -RBtreeParentColorBlack (node key ⟪ Black , proj4 ⟫ left left₁) right (rb-red _ _ x x₁ x₂ rb rb₁) (case1 ()) -RBtreeParentColorBlack left (node key ⟪ Red , proj4 ⟫ right right₁) (rb-red _ _ x () x₂ rb rb₁) (case2 x₃) -RBtreeParentColorBlack left (node key ⟪ Black , proj4 ⟫ right right₁) (rb-red _ _ x x₁ x₂ rb rb₁) (case2 ()) -RBtreeParentColorBlack left right (rb-black _ _ x rb rb₁) x₃ = refl +RBtreeParentColorBlack = ? RBtreeChildrenColorBlack : {n : Level} {A : Set n} → (left right : bt (Color ∧ A)) { value : Color ∧ A} {key : ℕ} → RBtreeInvariant (node key value left right) → proj1 value ≡ Red → (color left ≡ Black) ∧ (color right ≡ Black) -RBtreeChildrenColorBlack left right (rb-red _ _ x x₁ x₂ rbi rbi₁) refl = ⟪ x , x₁ ⟫ +RBtreeChildrenColorBlack left right = ? -- -- findRBT exit with replaced node @@ -1082,80 +1203,80 @@ → c ≡ Red → RBtreeInvariant tree → (black-depth tree ≡ black-depth left ) ∧ (black-depth tree ≡ black-depth right) -red-children-eq {n} {A} {.(node key₁ ⟪ Red , value₁ ⟫ left right)} {left} {right} {.key₁} {.value₁} {Red} refl eq₁ rb2@(rb-red key₁ value₁ x x₁ x₂ rb rb₁) = - ⟪ ( begin - black-depth left ⊔ black-depth right ≡⟨ cong (λ k → black-depth left ⊔ k) (sym (RBtreeEQ rb2)) ⟩ - black-depth left ⊔ black-depth left ≡⟨ ⊔-idem _ ⟩ - black-depth left ∎ ) , ( - begin - black-depth left ⊔ black-depth right ≡⟨ cong (λ k → k ⊔ black-depth right ) (RBtreeEQ rb2) ⟩ - black-depth right ⊔ black-depth right ≡⟨ ⊔-idem _ ⟩ - black-depth right ∎ ) ⟫ where open ≡-Reasoning -red-children-eq {n} {A} {tree} {left} {right} {key} {value} {Black} eq () rb +red-children-eq {n} {A} = ? + + + + + + + + + black-children-eq : {n : Level} {A : Set n} {tree left right : bt (Color ∧ A)} → {key : ℕ} → {value : A} → {c : Color} → tree ≡ node key ⟪ c , value ⟫ left right → c ≡ Black → RBtreeInvariant tree → (black-depth tree ≡ suc (black-depth left) ) ∧ (black-depth tree ≡ suc (black-depth right)) -black-children-eq {n} {A} {.(node key₁ ⟪ Black , value₁ ⟫ left right)} {left} {right} {.key₁} {.value₁} {Black} refl eq₁ rb2@(rb-black key₁ value₁ x rb rb₁) = - ⟪ ( begin - suc (black-depth left ⊔ black-depth right) ≡⟨ cong (λ k → suc (black-depth left ⊔ k)) (sym (RBtreeEQ rb2)) ⟩ - suc (black-depth left ⊔ black-depth left) ≡⟨ ⊔-idem _ ⟩ - suc (black-depth left) ∎ ) , ( - begin - suc (black-depth left ⊔ black-depth right) ≡⟨ cong (λ k → suc (k ⊔ black-depth right)) (RBtreeEQ rb2) ⟩ - suc (black-depth right ⊔ black-depth right) ≡⟨ ⊔-idem _ ⟩ - suc (black-depth right) ∎ ) ⟫ where open ≡-Reasoning -black-children-eq {n} {A} {tree} {left} {right} {key} {value} {Red} eq () rb +black-children-eq {n} {A} = ? + + + + + + + + + black-depth-cong : {n : Level} (A : Set n) {tree tree₁ : bt (Color ∧ A)} → tree ≡ tree₁ → black-depth tree ≡ black-depth tree₁ -black-depth-cong {n} A {leaf} {leaf} refl = refl -black-depth-cong {n} A {node key ⟪ Red , value ⟫ left right} {node .key ⟪ Red , .value ⟫ .left .right} refl - = cong₂ (λ j k → j ⊔ k ) (black-depth-cong A {left} {left} refl) (black-depth-cong A {right} {right} refl) -black-depth-cong {n} A {node key ⟪ Black , value ⟫ left right} {node .key ⟪ Black , .value ⟫ .left .right} refl - = cong₂ (λ j k → suc (j ⊔ k) ) (black-depth-cong A {left} {left} refl) (black-depth-cong A {right} {right} refl) +black-depth-cong {n} A = ? + + + + black-depth-resp : {n : Level} (A : Set n) (tree tree₁ : bt (Color ∧ A)) → {c1 c2 : Color} { l1 l2 r1 r2 : bt (Color ∧ A)} {key1 key2 : ℕ} {value1 value2 : A} → tree ≡ node key1 ⟪ c1 , value1 ⟫ l1 r1 → tree₁ ≡ node key2 ⟪ c2 , value2 ⟫ l2 r2 → color tree ≡ color tree₁ → black-depth l1 ≡ black-depth l2 → black-depth r1 ≡ black-depth r2 → black-depth tree ≡ black-depth tree₁ -black-depth-resp A _ _ {Black} {Black} refl refl refl eql eqr = cong₂ (λ j k → suc (j ⊔ k) ) eql eqr -black-depth-resp A _ _ {Red} {Red} refl refl refl eql eqr = cong₂ (λ j k → j ⊔ k ) eql eqr +black-depth-resp A _ _ = ? + red-children-eq1 : {n : Level} {A : Set n} {tree left right : bt (Color ∧ A)} → {key : ℕ} → {value : A} → {c : Color} → tree ≡ node key ⟪ c , value ⟫ left right → color tree ≡ Red → RBtreeInvariant tree → (black-depth tree ≡ black-depth left ) ∧ (black-depth tree ≡ black-depth right) -red-children-eq1 {n} {A} {.(node key₁ ⟪ Red , value₁ ⟫ left right)} {left} {right} {.key₁} {.value₁} {Red} refl eq₁ rb2@(rb-red key₁ value₁ x x₁ x₂ rb rb₁) = - ⟪ ( begin - black-depth left ⊔ black-depth right ≡⟨ cong (λ k → black-depth left ⊔ k) (sym (RBtreeEQ rb2)) ⟩ - black-depth left ⊔ black-depth left ≡⟨ ⊔-idem _ ⟩ - black-depth left ∎ ) , ( - begin - black-depth left ⊔ black-depth right ≡⟨ cong (λ k → k ⊔ black-depth right ) (RBtreeEQ rb2) ⟩ - black-depth right ⊔ black-depth right ≡⟨ ⊔-idem _ ⟩ - black-depth right ∎ ) ⟫ where open ≡-Reasoning -red-children-eq1 {n} {A} {.(node key ⟪ Black , value ⟫ left right)} {left} {right} {key} {value} {Black} refl () rb +red-children-eq1 {n} {A} = ? + + + + + + + + + black-children-eq1 : {n : Level} {A : Set n} {tree left right : bt (Color ∧ A)} → {key : ℕ} → {value : A} → {c : Color} → tree ≡ node key ⟪ c , value ⟫ left right → color tree ≡ Black → RBtreeInvariant tree → (black-depth tree ≡ suc (black-depth left) ) ∧ (black-depth tree ≡ suc (black-depth right)) -black-children-eq1 {n} {A} {.(node key₁ ⟪ Black , value₁ ⟫ left right)} {left} {right} {.key₁} {.value₁} {Black} refl eq₁ rb2@(rb-black key₁ value₁ x rb rb₁) = - ⟪ ( begin - suc (black-depth left ⊔ black-depth right) ≡⟨ cong (λ k → suc (black-depth left ⊔ k)) (sym (RBtreeEQ rb2)) ⟩ - suc (black-depth left ⊔ black-depth left) ≡⟨ ⊔-idem _ ⟩ - suc (black-depth left) ∎ ) , ( - begin - suc (black-depth left ⊔ black-depth right) ≡⟨ cong (λ k → suc (k ⊔ black-depth right)) (RBtreeEQ rb2) ⟩ - suc (black-depth right ⊔ black-depth right) ≡⟨ ⊔-idem _ ⟩ - suc (black-depth right) ∎ ) ⟫ where open ≡-Reasoning -black-children-eq1 {n} {A} {.(node key ⟪ Red , value ⟫ left right)} {left} {right} {key} {value} {Red} refl () rb +black-children-eq1 {n} {A} = ? + + + + + + + + + rbi-from-red-black : {n : Level } {A : Set n} → (n1 rp-left : bt (Color ∧ A)) → (kp : ℕ) → (vp : Color ∧ A) @@ -1195,60 +1316,60 @@ RB-repl→eq : {n : Level} {A : Set n} → (tree repl : bt (Color ∧ A)) → {key : ℕ} → {value : A} → RBtreeInvariant tree → replacedRBTree key value tree repl → black-depth tree ≡ black-depth repl -RB-repl→eq {n} {A} .leaf .(node _ ⟪ Red , _ ⟫ leaf leaf) rbt rbr-leaf = refl -RB-repl→eq {n} {A} (node _ ⟪ Red , _ ⟫ _ _) .(node _ ⟪ Red , _ ⟫ _ _) rbt rbr-node = refl -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ _ _) .(node _ ⟪ Black , _ ⟫ _ _) rbt rbr-node = refl -RB-repl→eq {n} {A} (node _ ⟪ Red , _ ⟫ left _) .(node _ ⟪ Red , _ ⟫ left _) (rb-red _ _ x₂ x₃ x₄ rbt rbt₁) (rbr-right x x₁ t) = - cong (λ k → black-depth left ⊔ k ) (RB-repl→eq _ _ rbt₁ t) -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ left _) .(node _ ⟪ Black , _ ⟫ left _) (rb-black _ _ x₂ rbt rbt₁) (rbr-right x x₁ t) = - cong (λ k → suc (black-depth left ⊔ k)) (RB-repl→eq _ _ rbt₁ t) -RB-repl→eq {n} {A} (node _ ⟪ Red , _ ⟫ _ right) .(node _ ⟪ Red , _ ⟫ _ right) (rb-red _ _ x₂ x₃ x₄ rbt rbt₁) (rbr-left x x₁ t) = cong (λ k → k ⊔ black-depth right) (RB-repl→eq _ _ rbt t) -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ _ right) .(node _ ⟪ Black , _ ⟫ _ right) (rb-black _ _ x₂ rbt rbt₁) (rbr-left x x₁ t) = cong (λ k → suc (k ⊔ black-depth right)) (RB-repl→eq _ _ rbt t) -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ t₁ _) .(node _ ⟪ Black , _ ⟫ t₁ _) (rb-black _ _ x₂ rbt rbt₁) (rbr-black-right x x₁ t) = cong (λ k → suc (black-depth t₁ ⊔ k)) (RB-repl→eq _ _ rbt₁ t) -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ _ t₁) .(node _ ⟪ Black , _ ⟫ _ t₁) (rb-black _ _ x₂ rbt rbt₁) (rbr-black-left x x₁ t) = cong (λ k → suc (k ⊔ black-depth t₁)) (RB-repl→eq _ _ rbt t) -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ t₁ t₂) t₃) .(node _ ⟪ Red , _ ⟫ (node _ ⟪ Black , _ ⟫ t₄ t₂) (to-black t₃)) (rb-black _ _ x₃ (rb-red _ _ x₄ x₅ x₆ rbt rbt₂) rbt₁) (rbr-flip-ll {_} {_} {t₄} x x₁ x₂ t) = begin - suc (black-depth t₁ ⊔ black-depth t₂ ⊔ black-depth t₃) ≡⟨ cong (λ k → suc (k ⊔ black-depth t₂ ⊔ black-depth t₃)) (RB-repl→eq _ _ rbt t) ⟩ - suc (black-depth t₄ ⊔ black-depth t₂) ⊔ suc (black-depth t₃) ≡⟨ cong (λ k → suc (black-depth t₄ ⊔ black-depth t₂) ⊔ k ) ( to-black-eq t₃ x₁ ) ⟩ - suc (black-depth t₄ ⊔ black-depth t₂) ⊔ black-depth (to-black t₃) ∎ - where open ≡-Reasoning -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ t₁ t₂) t₃) .(node _ ⟪ Red , _ ⟫ (node _ ⟪ Black , _ ⟫ t₁ t₄) (to-black t₃)) (rb-black _ _ x₄ (rb-red _ _ x₅ x₆ x₇ rbt rbt₂) rbt₁) (rbr-flip-lr {_} {_} {t₄} x x₁ x₂ x₃ t) = begin - suc (black-depth t₁ ⊔ black-depth t₂) ⊔ suc (black-depth t₃) ≡⟨ cong (λ k → suc (black-depth t₁ ⊔ black-depth t₂) ⊔ k ) ( to-black-eq t₃ x₁ ) ⟩ - suc (black-depth t₁ ⊔ black-depth t₂) ⊔ black-depth (to-black t₃) ≡⟨ cong (λ k → suc (black-depth t₁ ⊔ k ) ⊔ black-depth (to-black t₃)) (RB-repl→eq _ _ rbt₂ t) ⟩ - suc (black-depth t₁ ⊔ black-depth t₄) ⊔ black-depth (to-black t₃) ∎ - where open ≡-Reasoning -RB-repl→eq {n} {A} (node _ ⟪ Black , _ ⟫ _ (node _ ⟪ Red , _ ⟫ _ _)) .(node _ ⟪ Red , _ ⟫ (to-black t₄) (node _ ⟪ Black , _ ⟫ t₃ t₁)) (rb-black _ _ x₄ rbt (rb-red _ _ x₅ x₆ x₇ rbt₁ rbt₂)) (rbr-flip-rl {t₁} {t₂} {t₃} {t₄} x x₁ x₂ x₃ t) = begin - suc (black-depth t₄ ⊔ (black-depth t₂ ⊔ black-depth t₁)) ≡⟨ cong (λ k → suc (black-depth t₄ ⊔ ( k ⊔ black-depth t₁)) ) (RB-repl→eq _ _ rbt₁ t) ⟩ - suc (black-depth t₄ ⊔ (black-depth t₃ ⊔ black-depth t₁)) ≡⟨ cong (λ k → k ⊔ suc (black-depth t₃ ⊔ black-depth t₁)) ( to-black-eq t₄ x₁ ) ⟩ - black-depth (to-black t₄) ⊔ suc (black-depth t₃ ⊔ black-depth t₁) ∎ - where open ≡-Reasoning -RB-repl→eq {n} {A} .(node _ ⟪ Black , _ ⟫ _ (node _ ⟪ Red , _ ⟫ _ _)) .(node _ ⟪ Red , _ ⟫ (to-black _) (node _ ⟪ Black , _ ⟫ _ _)) (rb-black _ _ x₃ rbt (rb-red _ _ x₄ x₅ x₆ rbt₁ rbt₂)) (rbr-flip-rr {t₁} {t₂} {t₃} {t₄} x x₁ x₂ t) = begin - suc (black-depth t₄ ⊔ (black-depth t₁ ⊔ black-depth t₂)) ≡⟨ cong (λ k → suc (black-depth t₄ ⊔ (black-depth t₁ ⊔ k ))) ( RB-repl→eq _ _ rbt₂ t) ⟩ - suc (black-depth t₄ ⊔ (black-depth t₁ ⊔ black-depth t₃)) ≡⟨ cong (λ k → k ⊔ suc (black-depth t₁ ⊔ black-depth t₃)) ( to-black-eq t₄ x₁ ) ⟩ - black-depth (to-black t₄) ⊔ suc (black-depth t₁ ⊔ black-depth t₃) ∎ - where open ≡-Reasoning -RB-repl→eq {n} {A} .(node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) _) .(node _ ⟪ Black , _ ⟫ _ (node _ ⟪ Red , _ ⟫ _ _)) (rb-black _ _ x₂ (rb-red _ _ x₃ x₄ x₅ rbt rbt₂) rbt₁) (rbr-rotate-ll {t₁} {t₂} {t₃} {t₄} x x₁ t) = begin - suc (black-depth t₂ ⊔ black-depth t₁ ⊔ black-depth t₄) ≡⟨ cong suc ( ⊔-assoc (black-depth t₂) (black-depth t₁) (black-depth t₄)) ⟩ - suc (black-depth t₂ ⊔ (black-depth t₁ ⊔ black-depth t₄)) ≡⟨ cong (λ k → suc (k ⊔ (black-depth t₁ ⊔ black-depth t₄)) ) (RB-repl→eq _ _ rbt t) ⟩ - suc (black-depth t₃ ⊔ (black-depth t₁ ⊔ black-depth t₄)) ∎ - where open ≡-Reasoning -RB-repl→eq {n} {A} .(node _ ⟪ Black , _ ⟫ _ (node _ ⟪ Red , _ ⟫ _ _)) .(node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) _) (rb-black _ _ x₂ rbt (rb-red _ _ x₃ x₄ x₅ rbt₁ rbt₂)) (rbr-rotate-rr {t₁} {t₂} {t₃} {t₄} x x₁ t) = begin - suc (black-depth t₄ ⊔ (black-depth t₁ ⊔ black-depth t₂)) ≡⟨ cong (λ k → suc (black-depth t₄ ⊔ (black-depth t₁ ⊔ k ))) ( RB-repl→eq _ _ rbt₂ t) ⟩ - suc (black-depth t₄ ⊔ (black-depth t₁ ⊔ black-depth t₃)) ≡⟨ cong suc (sym ( ⊔-assoc (black-depth t₄) (black-depth t₁) (black-depth t₃))) ⟩ - suc (black-depth t₄ ⊔ black-depth t₁ ⊔ black-depth t₃) ∎ - where open ≡-Reasoning -RB-repl→eq {n} {A} .(node kg ⟪ Black , _ ⟫ (node kp ⟪ Red , _ ⟫ _ _) _) .(node kn ⟪ Black , _ ⟫ (node kp ⟪ Red , _ ⟫ _ t₂) (node kg ⟪ Red , _ ⟫ t₃ _)) (rb-black .kg _ x₃ (rb-red .kp _ x₄ x₅ x₆ rbt rbt₂) rbt₁) (rbr-rotate-lr {t₀} {t₁} {uncle} t₂ t₃ kg kp kn x x₁ x₂ t) = begin - suc (black-depth t₀ ⊔ black-depth t₁ ⊔ black-depth uncle) ≡⟨ cong suc ( ⊔-assoc (black-depth t₀) (black-depth t₁) (black-depth uncle)) ⟩ - suc (black-depth t₀ ⊔ (black-depth t₁ ⊔ black-depth uncle)) ≡⟨ cong (λ k → suc (black-depth t₀ ⊔ (k ⊔ black-depth uncle))) (RB-repl→eq _ _ rbt₂ t) ⟩ - suc (black-depth t₀ ⊔ ((black-depth t₂ ⊔ black-depth t₃) ⊔ black-depth uncle)) ≡⟨ cong (λ k → suc (black-depth t₀ ⊔ k )) ( ⊔-assoc (black-depth t₂) (black-depth t₃) (black-depth uncle)) ⟩ - suc (black-depth t₀ ⊔ (black-depth t₂ ⊔ (black-depth t₃ ⊔ black-depth uncle))) ≡⟨ cong suc (sym ( ⊔-assoc (black-depth t₀) (black-depth t₂) (black-depth t₃ ⊔ black-depth uncle))) ⟩ - suc (black-depth t₀ ⊔ black-depth t₂ ⊔ (black-depth t₃ ⊔ black-depth uncle)) ∎ - where open ≡-Reasoning -RB-repl→eq {n} {A} .(node kg ⟪ Black , _ ⟫ _ (node kp ⟪ Red , _ ⟫ _ _)) .(node kn ⟪ Black , _ ⟫ (node kg ⟪ Red , _ ⟫ _ t₂) (node kp ⟪ Red , _ ⟫ t₃ _)) (rb-black .kg _ x₃ rbt (rb-red .kp _ x₄ x₅ x₆ rbt₁ rbt₂)) (rbr-rotate-rl {t₀} {t₁} {uncle} t₂ t₃ kg kp kn x x₁ x₂ t) = begin - suc (black-depth uncle ⊔ (black-depth t₁ ⊔ black-depth t₀)) ≡⟨ cong (λ k → suc (black-depth uncle ⊔ (k ⊔ black-depth t₀))) (RB-repl→eq _ _ rbt₁ t) ⟩ - suc (black-depth uncle ⊔ ((black-depth t₂ ⊔ black-depth t₃) ⊔ black-depth t₀)) ≡⟨ cong (λ k → suc (black-depth uncle ⊔ k)) ( ⊔-assoc (black-depth t₂) (black-depth t₃) (black-depth t₀)) ⟩ - suc (black-depth uncle ⊔ (black-depth t₂ ⊔ (black-depth t₃ ⊔ black-depth t₀))) ≡⟨ cong suc (sym ( ⊔-assoc (black-depth uncle) (black-depth t₂) (black-depth t₃ ⊔ black-depth t₀))) ⟩ - suc (black-depth uncle ⊔ black-depth t₂ ⊔ (black-depth t₃ ⊔ black-depth t₀)) ∎ - where open ≡-Reasoning +RB-repl→eq {n} {A} = ? + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + RB-repl→ti> : {n : Level} {A : Set n} → (tree repl : bt (Color ∧ A)) → (key key₁ : ℕ) → (value : A) @@ -1329,491 +1450,7 @@ RB-repl→ti : {n : Level} {A : Set n} → (tree repl : bt (Color ∧ A) ) → (key : ℕ ) → (value : A) → treeInvariant tree → replacedRBTree key value tree repl → treeInvariant repl -RB-repl→ti .leaf .(node key ⟪ Red , value ⟫ leaf leaf) key value ti rbr-leaf = t-single key ⟪ Red , value ⟫ -RB-repl→ti .(node key ⟪ _ , _ ⟫ leaf leaf) .(node key ⟪ _ , value ⟫ leaf leaf) key value (t-single .key .(⟪ _ , _ ⟫)) (rbr-node ) = t-single key ⟪ _ , value ⟫ -RB-repl→ti .(node key ⟪ _ , _ ⟫ leaf (node key₁ _ _ _)) .(node key ⟪ _ , value ⟫ leaf (node key₁ _ _ _)) key value - (t-right .key key₁ x x₁ x₂ ti) (rbr-node ) = t-right key key₁ x x₁ x₂ ti -RB-repl→ti .(node key ⟪ _ , _ ⟫ (node key₁ _ _ _) leaf) .(node key ⟪ _ , value ⟫ (node key₁ _ _ _) leaf) key value - (t-left key₁ .key x x₁ x₂ ti) (rbr-node ) = t-left key₁ key x x₁ x₂ ti -RB-repl→ti .(node key ⟪ _ , _ ⟫ (node key₁ _ _ _) (node key₂ _ _ _)) .(node key ⟪ _ , value ⟫ (node key₁ _ _ _) (node key₂ _ _ _)) key value - (t-node key₁ .key key₂ x x₁ x₂ x₃ x₄ x₅ ti ti₁) (rbr-node ) = t-node key₁ key key₂ x x₁ x₂ x₃ x₄ x₅ ti ti₁ -RB-repl→ti (node key₁ ⟪ ca , v1 ⟫ leaf leaf) (node key₁ ⟪ ca , v1 ⟫ leaf tree@(node key₂ value₁ t t₁)) key value - (t-single key₁ ⟪ ca , v1 ⟫) (rbr-right _ x trb) = t-right _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₁ < key₂ ) ∧ tr> key₁ t ∧ tr> key₁ t₁ - rr00 = RB-repl→ti> _ _ _ _ _ trb x tt -RB-repl→ti (node _ ⟪ _ , _ ⟫ leaf (node key₁ _ _ _)) (node key₂ ⟪ ca , v1 ⟫ leaf (node key₃ value₁ t t₁)) key value - (t-right _ key₁ x₁ x₂ x₃ ti) (rbr-right _ x trb) = t-right _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ ti trb) where - rr00 : (key₂ < key₃) ∧ tr> key₂ t ∧ tr> key₂ t₁ - rr00 = RB-repl→ti> _ _ _ _ _ trb x ⟪ x₁ , ⟪ x₂ , x₃ ⟫ ⟫ -RB-repl→ti .(node key₂ ⟪ ca , v1 ⟫ (node key₁ value₁ t t₁) leaf) (node key₂ ⟪ ca , v1 ⟫ (node key₁ value₁ t t₁) (node key₃ value₂ t₂ t₃)) key value - (t-left key₁ _ x₁ x₂ x₃ ti) (rbr-right _ x trb) = t-node _ _ _ x₁ (proj1 rr00) x₂ x₃ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ti (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₂ < key₃) ∧ tr> key₂ t₂ ∧ tr> key₂ t₃ - rr00 = RB-repl→ti> _ _ _ _ _ trb x tt -RB-repl→ti .(node key₃ ⟪ ca , v1 ⟫ (node key₁ v2 t₁ t₂) (node key₂ _ _ _)) (node key₃ ⟪ ca , v1 ⟫ (node key₁ v2 t₁ t₂) (node key₄ value₁ t₃ t₄)) key value - (t-node key₁ _ key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-right _ x trb) = t-node _ _ _ x₁ - (proj1 rr00) x₃ x₄ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ti (RB-repl→ti _ _ _ _ ti₁ trb) where - rr00 : (key₃ < key₄) ∧ tr> key₃ t₃ ∧ tr> key₃ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb x ⟪ x₂ , ⟪ x₅ , x₆ ⟫ ⟫ -RB-repl→ti .(node key₁ ⟪ _ , _ ⟫ leaf leaf) (node key₁ ⟪ _ , _ ⟫ (node key₂ value₁ left left₁) leaf) key value - (t-single _ .(⟪ _ , _ ⟫)) (rbr-left _ x trb) = t-left _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₂ < key₁) ∧ tr< key₁ left ∧ tr< key₁ left₁ - rr00 = RB-repl→ti< _ _ _ _ _ trb x tt -RB-repl→ti .(node key₂ ⟪ _ , _ ⟫ leaf (node key₁ _ t₁ t₂)) (node key₂ ⟪ _ , _ ⟫ (node key₃ value₁ t t₃) (node key₁ _ t₁ t₂)) key value - (t-right _ key₁ x₁ x₂ x₃ ti) (rbr-left _ x trb) = t-node _ _ _ (proj1 rr00) x₁ (proj1 (proj2 rr00))(proj2 (proj2 rr00)) x₂ x₃ rr01 ti where - rr00 : (key₃ < key₂) ∧ tr< key₂ t ∧ tr< key₂ t₃ - rr00 = RB-repl→ti< _ _ _ _ _ trb x tt - rr01 : treeInvariant (node key₃ value₁ t t₃) - rr01 = RB-repl→ti _ _ _ _ t-leaf trb -RB-repl→ti .(node _ ⟪ _ , _ ⟫ (node key₁ _ _ _) leaf) (node key₃ ⟪ _ , _ ⟫ (node key₂ value₁ t t₁) leaf) key value - (t-left key₁ _ x₁ x₂ x₃ ti) (rbr-left _ x trb) = t-left key₂ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ ti trb) where - rr00 : (key₂ < key₃) ∧ tr< key₃ t ∧ tr< key₃ t₁ - rr00 = RB-repl→ti< _ _ _ _ _ trb x ⟪ x₁ , ⟪ x₂ , x₃ ⟫ ⟫ -RB-repl→ti .(node key₃ ⟪ _ , _ ⟫ (node key₁ _ _ _) (node key₂ _ t₁ t₂)) (node key₃ ⟪ _ , _ ⟫ (node key₄ value₁ t t₃) (node key₂ _ t₁ t₂)) key value - (t-node key₁ _ key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-left _ x trb) = t-node _ _ _ (proj1 rr00) x₂ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) x₅ x₆ (RB-repl→ti _ _ _ _ ti trb) ti₁ where - rr00 : (key₄ < key₃) ∧ tr< key₃ t ∧ tr< key₃ t₃ - rr00 = RB-repl→ti< _ _ _ _ _ trb x ⟪ x₁ , ⟪ x₃ , x₄ ⟫ ⟫ -RB-repl→ti .(node x₁ ⟪ Black , c ⟫ leaf leaf) (node x₁ ⟪ Black , c ⟫ leaf (node key₁ value₁ t t₁)) key value - (t-single x₂ .(⟪ Black , c ⟫)) (rbr-black-right x x₄ trb) = t-right _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (x₁ < key₁) ∧ tr> x₁ t ∧ tr> x₁ t₁ - rr00 = RB-repl→ti> _ _ _ _ _ trb x₄ tt -RB-repl→ti .(node key₂ ⟪ Black , _ ⟫ leaf (node key₁ _ _ _)) (node key₂ ⟪ Black , _ ⟫ leaf (node key₃ value₁ t₂ t₃)) key value - (t-right _ key₁ x₁ x₂ x₃ ti) (rbr-black-right x x₄ trb) = t-right _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ ti trb) where - rr00 : (key₂ < key₃) ∧ tr> key₂ t₂ ∧ tr> key₂ t₃ - rr00 = RB-repl→ti> _ _ _ _ _ trb x₄ ⟪ x₁ , ⟪ x₂ , x₃ ⟫ ⟫ -RB-repl→ti .(node key₂ ⟪ Black , _ ⟫ (node key₁ _ _ _) leaf) (node key₂ ⟪ Black , _ ⟫ (node key₁ _ _ _) (node key₃ value₁ t₂ t₃)) key value (t-left key₁ _ x₁ x₂ x₃ ti) (rbr-black-right x x₄ trb) = t-node _ _ _ x₁ (proj1 rr00) x₂ x₃ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ti (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₂ < key₃) ∧ tr> key₂ t₂ ∧ tr> key₂ t₃ - rr00 = RB-repl→ti> _ _ _ _ _ trb x₄ tt -RB-repl→ti .(node key₃ ⟪ Black , _ ⟫ (node key₁ _ _ _) (node key₂ _ _ _)) (node key₃ ⟪ Black , _ ⟫ (node key₁ _ _ _) (node key₄ value₁ t₂ t₃)) key value - (t-node key₁ _ key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-black-right x x₇ trb) = t-node _ _ _ x₁ (proj1 rr00) x₃ x₄ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ti (RB-repl→ti _ _ _ _ ti₁ trb) where - rr00 : (key₃ < key₄) ∧ tr> key₃ t₂ ∧ tr> key₃ t₃ - rr00 = RB-repl→ti> _ _ _ _ _ trb x₇ ⟪ x₂ , ⟪ x₅ , x₆ ⟫ ⟫ -RB-repl→ti .(node key₂ ⟪ Black , _ ⟫ leaf leaf) (node key₂ ⟪ Black , _ ⟫ (node key₁ value₁ t t₁) .leaf) key value - (t-single .key₂ .(⟪ Black , _ ⟫)) (rbr-black-left x x₇ trb) = t-left _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₁ < key₂) ∧ tr< key₂ t ∧ tr< key₂ t₁ - rr00 = RB-repl→ti< _ _ _ _ _ trb x₇ tt -RB-repl→ti .(node key₂ ⟪ Black , _ ⟫ leaf (node key₁ _ _ _)) (node key₂ ⟪ Black , _ ⟫ (node key₃ value₁ t t₁) .(node key₁ _ _ _)) key value - (t-right .key₂ key₁ x₁ x₂ x₃ ti) (rbr-black-left x x₇ trb) = t-node _ _ _ (proj1 rr00) x₁ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) x₂ x₃ (RB-repl→ti _ _ _ _ t-leaf trb) ti where - rr00 : (key₃ < key₂) ∧ tr< key₂ t ∧ tr< key₂ t₁ - rr00 = RB-repl→ti< _ _ _ _ _ trb x₇ tt -RB-repl→ti .(node key₂ ⟪ Black , _ ⟫ (node key₁ _ _ _) leaf) (node key₂ ⟪ Black , _ ⟫ (node key₃ value₁ t t₁) .leaf) key value - (t-left key₁ .key₂ x₁ x₂ x₃ ti) (rbr-black-left x x₇ trb) = t-left _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ ti trb) where - rr00 : (key₃ < key₂) ∧ tr< key₂ t ∧ tr< key₂ t₁ - rr00 = RB-repl→ti< _ _ _ _ _ trb x₇ ⟪ x₁ , ⟪ x₂ , x₃ ⟫ ⟫ -RB-repl→ti .(node key₂ ⟪ Black , _ ⟫ (node key₁ _ _ _) (node key₃ _ _ _)) (node key₂ ⟪ Black , _ ⟫ (node key₄ value₁ t t₁) .(node key₃ _ _ _)) key value - (t-node key₁ .key₂ key₃ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-black-left x x₇ trb) = t-node _ _ _ (proj1 rr00) x₂ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) x₅ x₆ (RB-repl→ti _ _ _ _ ti trb) ti₁ where - rr00 : (key₄ < key₂) ∧ tr< key₂ t ∧ tr< key₂ t₁ - rr00 = RB-repl→ti< _ _ _ _ _ trb x₇ ⟪ x₁ , ⟪ x₃ , x₄ ⟫ ⟫ -RB-repl→ti .(node key₂ ⟪ Black , value₁ ⟫ (node key₁ ⟪ Red , value₂ ⟫ _ t₁) leaf) (node key₂ ⟪ Red , value₁ ⟫ (node key₁ ⟪ Black , value₂ ⟫ t t₁) .(to-black leaf)) key value (t-left _ .key₂ x₁ x₂ x₃ ti) (rbr-flip-ll x () lt trb) -RB-repl→ti (node key₂ ⟪ Black , _ ⟫ (node key₁ ⟪ Red , _ ⟫ t₀ leaf) (node key₃ ⟪ c1 , v1 ⟫ left right)) (node key₂ ⟪ Red , value₁ ⟫ (node _ ⟪ Black , value₂ ⟫ (node key₄ value₃ t t₁) .leaf) (node key₃ ⟪ Black , v1 ⟫ left right)) key value (t-node _ .key₂ key₃ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-flip-ll x y lt trb) = t-node _ _ _ x₁ x₂ ⟪ <-trans (proj1 rr00) x₁ , ⟪ >-tr< (proj1 (proj2 rr00)) x₁ , >-tr< (proj2 (proj2 rr00)) x₁ ⟫ ⟫ tt x₅ x₆ (t-left _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ (treeLeftDown _ _ ti) trb)) (replaceTree1 _ _ _ ti₁) where - rr00 : (key₄ < key₁) ∧ tr< key₁ t ∧ tr< key₁ t₁ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt (proj1 (ti-property1 ti)) -RB-repl→ti (node key₂ ⟪ Black , _ ⟫ (node key₁ ⟪ Red , _ ⟫ .leaf (node key₄ value₃ t₁ t₂)) (node key₃ ⟪ c0 , v1 ⟫ left right)) (node key₂ ⟪ Red , value₁ ⟫ (node _ ⟪ Black , value₂ ⟫ (node key₅ value₄ t t₃) .(node key₄ value₃ t₁ t₂)) (node key₃ ⟪ Black , v1 ⟫ left right)) key value (t-node _ .key₂ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-right .key₁ .key₄ x₇ x₈ x₉ ti) ti₁) (rbr-flip-ll x y lt trb) - = t-node _ _ _ x₁ x₂ ⟪ <-trans (proj1 rr00) x₁ , ⟪ >-tr< (proj1 (proj2 rr00)) x₁ , >-tr< (proj2 (proj2 rr00)) x₁ ⟫ ⟫ x₄ x₅ x₆ (t-node _ _ _ (proj1 rr00) x₇ (proj1 (proj2 rr00)) (proj2 (proj2 (rr00))) x₈ x₉ (RB-repl→ti _ _ _ _ t-leaf trb) ti) (replaceTree1 _ _ _ ti₁) where - rr00 : (key₅ < key₁) ∧ tr< key₁ t ∧ tr< key₁ t₃ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt tt -RB-repl→ti (node key₂ ⟪ Black , _ ⟫ (node key₁ ⟪ Red , _ ⟫ .(node key₆ _ _ _) (node key₄ value₃ t₁ t₂)) (node key₃ ⟪ c0 , v1 ⟫ left right)) (node key₂ ⟪ Red , value₁ ⟫ (node _ ⟪ Black , value₂ ⟫ (node key₅ value₄ t t₃) .(node key₄ value₃ t₁ t₂)) (node key₃ ⟪ Black , v1 ⟫ left right)) key value (t-node _ .key₂ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-node key₆ .key₁ .key₄ x₇ x₈ x₉ x₁₀ x₁₁ x₁₂ ti ti₂) ti₁) (rbr-flip-ll x y lt trb) - = t-node _ _ _ x₁ x₂ ⟪ <-trans (proj1 rr00) x₁ , ⟪ >-tr< (proj1 (proj2 rr00)) x₁ , >-tr< (proj2 (proj2 rr00)) x₁ ⟫ ⟫ - x₄ x₅ x₆ (t-node _ _ _ (proj1 rr00) x₈ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) x₁₁ x₁₂ (RB-repl→ti _ _ _ _ ti trb) ti₂) (replaceTree1 _ _ _ ti₁) where - rr00 : (key₅ < key₁) ∧ tr< key₁ t ∧ tr< key₁ t₃ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt ⟪ x₇ , ⟪ x₉ , x₁₀ ⟫ ⟫ -RB-repl→ti (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ left right) leaf) (node key₂ ⟪ Red , v1 ⟫ (node key₃ ⟪ Black , v2 ⟫ left right₁) leaf) key value - (t-left _ _ x₁ x₂ x₃ ti) (rbr-flip-lr x () lt lt2 trb) -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₂ ⟪ Red , v2 ⟫ leaf leaf) (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃)) (node key₁ ⟪ Red , _ ⟫ (node _ ⟪ Black , _ ⟫ .leaf (node key₄ value₁ t₄ t₅)) .(to-black (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃))) key value (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-flip-lr x y lt lt2 trb) - = t-node _ _ _ x₁ x₂ tt rr00 x₅ x₆ (t-right _ _ (proj1 rr01) (proj1 (proj2 rr01)) (proj2 (proj2 rr01)) (RB-repl→ti _ _ _ _ t-leaf trb)) (replaceTree1 _ _ _ ti₁) where - rr00 : (key₄ < key₁) ∧ tr< key₁ t₄ ∧ tr< key₁ t₅ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt2 tt - rr01 : (key₂ < key₄) ∧ tr> key₂ t₄ ∧ tr> key₂ t₅ - rr01 = RB-repl→ti> _ _ _ _ _ trb lt tt -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₂ ⟪ Red , v2 ⟫ leaf (node key₅ value₂ t₁ t₆)) (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃)) (node key₁ ⟪ Red , _ ⟫ (node _ ⟪ Black , _ ⟫ .leaf (node key₄ value₁ t₄ t₅)) .(to-black (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃))) key value (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-right .key₂ .key₅ x₇ x₈ x₉ ti) ti₁) (rbr-flip-lr x y lt lt2 trb) = t-node _ _ _ x₁ x₂ tt rr00 x₅ x₆ (t-right _ _ (proj1 rr01) (proj1 (proj2 rr01)) (proj2 (proj2 rr01)) (RB-repl→ti _ _ _ _ ti trb)) (replaceTree1 _ _ _ ti₁) where - rr00 : (key₄ < key₁) ∧ tr< key₁ t₄ ∧ tr< key₁ t₅ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt2 x₄ - rr01 : (key₂ < key₄) ∧ tr> key₂ t₄ ∧ tr> key₂ t₅ - rr01 = RB-repl→ti> _ _ _ _ _ trb lt ⟪ x₇ , ⟪ x₈ , x₉ ⟫ ⟫ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₂ ⟪ Red , v2 ⟫ (node key₄ value₁ t t₅) .leaf) (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃)) (node key₁ ⟪ Red , _ ⟫ (node _ ⟪ Black , _ ⟫ .(node key₄ value₁ t t₅) (node key₅ value₂ t₄ t₆)) .(to-black (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃))) key value (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-left .key₄ .key₂ x₇ x₈ x₉ ti) ti₁) (rbr-flip-lr x y lt lt2 trb) - = t-node _ _ _ x₁ x₂ x₃ rr00 x₅ x₆ (t-node _ _ _ x₇ (proj1 rr01) x₈ x₉ (proj1 (proj2 rr01)) (proj2 (proj2 rr01)) ti (RB-repl→ti _ _ _ _ t-leaf trb)) (replaceTree1 _ _ _ ti₁) where - rr00 : (key₅ < key₁) ∧ tr< key₁ t₄ ∧ tr< key₁ t₆ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt2 tt - rr01 : (key₂ < key₅) ∧ tr> key₂ t₄ ∧ tr> key₂ t₆ - rr01 = RB-repl→ti> _ _ _ _ _ trb lt tt -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₂ ⟪ Red , v2 ⟫ (node key₄ value₁ t t₅) .(node key₆ _ _ _)) (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃)) (node key₁ ⟪ Red , _ ⟫ (node _ ⟪ Black , _ ⟫ .(node key₄ value₁ t t₅) (node key₅ value₂ t₄ t₆)) .(to-black (node key₃ ⟪ c3 , v3 ⟫ t₂ t₃))) key value (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-node .key₄ .key₂ key₆ x₇ x₈ x₉ x₁₀ x₁₁ x₁₂ ti ti₂) ti₁) (rbr-flip-lr x y lt lt2 trb) - = t-node _ _ _ x₁ x₂ x₃ rr00 x₅ x₆ (t-node _ _ _ x₇ (proj1 rr01) x₉ x₁₀ (proj1 (proj2 rr01)) (proj2 (proj2 rr01)) ti (RB-repl→ti _ _ _ _ ti₂ trb)) (replaceTree1 _ _ _ ti₁) where - rr00 : (key₅ < key₁) ∧ tr< key₁ t₄ ∧ tr< key₁ t₆ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt2 x₄ - rr01 : (key₂ < key₅) ∧ tr> key₂ t₄ ∧ tr> key₂ t₆ - rr01 = RB-repl→ti> _ _ _ _ _ trb lt ⟪ x₈ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ -RB-repl→ti (node _ ⟪ Black , _ ⟫ leaf (node _ ⟪ Red , _ ⟫ t t₁)) (node key₁ ⟪ Red , v1 ⟫ .(to-black leaf) (node key₂ ⟪ Black , v2 ⟫ t₂ t₁)) key value - (t-right _ _ x₁ x₂ x₃ ti) (rbr-flip-rl x () lt lt2 trb) -RB-repl→ti (node _ ⟪ Black , v1 ⟫ (node key₂ ⟪ c2 , v2 ⟫ t t₁) (node _ ⟪ Red , v3 ⟫ t₂ leaf)) (node key₁ ⟪ Red , _ ⟫ .(to-black (node key₂ ⟪ c2 , v2 ⟫ t t₁)) (node key₃ ⟪ Black , _ ⟫ (node key₄ value₁ t₄ t₅) .leaf)) key value (t-node key₂ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-flip-rl x y lt lt2 trb) - = t-node _ _ _ x₁ x₂ x₃ x₄ rr00 tt (replaceTree1 _ _ _ ti) (t-left _ _ (proj1 rr01) (proj1 (proj2 rr01)) (proj2 (proj2 rr01)) (RB-repl→ti _ _ _ _ (treeLeftDown _ _ ti₁) trb)) where - rr00 : (key₁ < key₄) ∧ tr> key₁ t₄ ∧ tr> key₁ t₅ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt x₅ - rr01 : (key₄ < key₃) ∧ tr< key₃ t₄ ∧ tr< key₃ t₅ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 (proj1 (ti-property1 ti₁)) -RB-repl→ti (node _ ⟪ Black , v1 ⟫ (node key₂ ⟪ c2 , v2 ⟫ t t₁) (node _ ⟪ Red , v3 ⟫ .leaf (node key₅ value₂ t₃ t₆))) (node key₁ ⟪ Red , _ ⟫ .(to-black (node key₂ ⟪ c2 , v2 ⟫ t t₁)) (node key₃ ⟪ Black , _ ⟫ (node key₄ value₁ t₄ t₅) .(node key₅ value₂ t₃ t₆))) key value (t-node key₂ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-right .key₃ .key₅ x₇ x₈ x₉ ti₁)) (rbr-flip-rl x y lt lt2 trb) = t-node _ _ _ x₁ x₂ x₃ x₄ rr00 rr02 (replaceTree1 _ _ _ ti) (t-node _ _ _ (proj1 rr01) x₇ (proj1 (proj2 rr01)) (proj2 (proj2 rr01)) x₈ x₉ (RB-repl→ti _ _ _ _ t-leaf trb) ti₁) where - rr00 : (key₁ < key₄) ∧ tr> key₁ t₄ ∧ tr> key₁ t₅ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt x₅ - rr01 : (key₄ < key₃) ∧ tr< key₃ t₄ ∧ tr< key₃ t₅ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 tt - rr02 : (key₁ < key₅) ∧ tr> key₁ t₃ ∧ tr> key₁ t₆ - rr02 = ⟪ <-trans x₂ x₇ , ⟪ <-tr> x₈ x₂ , <-tr> x₉ x₂ ⟫ ⟫ -RB-repl→ti (node _ ⟪ Black , v1 ⟫ (node key₂ ⟪ c2 , v2 ⟫ t t₁) (node _ ⟪ Red , v3 ⟫ .(node key₆ _ _ _) (node key₅ value₂ t₃ t₆))) (node key₁ ⟪ Red , _ ⟫ .(to-black (node key₂ ⟪ c2 , v2 ⟫ t t₁)) (node key₃ ⟪ Black , _ ⟫ (node key₄ value₁ t₄ t₅) .(node key₅ value₂ t₃ t₆))) key value (t-node key₂ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-node key₆ .key₃ .key₅ x₇ x₈ x₉ x₁₀ x₁₁ x₁₂ ti₁ ti₂)) (rbr-flip-rl x y lt lt2 trb) - = t-node _ _ _ x₁ x₂ x₃ x₄ rr00 rr02 (replaceTree1 _ _ _ ti) (t-node _ _ _ (proj1 rr01) x₈ (proj1 (proj2 rr01)) (proj2 (proj2 rr01)) x₁₁ x₁₂ (RB-repl→ti _ _ _ _ ti₁ trb) ti₂) where - rr00 : (key₁ < key₄) ∧ tr> key₁ t₄ ∧ tr> key₁ t₅ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt x₅ - rr01 : (key₄ < key₃ ) ∧ tr< key₃ t₄ ∧ tr< key₃ t₅ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₇ , ⟪ x₉ , x₁₀ ⟫ ⟫ - rr02 : (key₁ < key₅) ∧ tr> key₁ t₃ ∧ tr> key₁ t₆ - rr02 = ⟪ proj1 x₆ , ⟪ <-tr> x₁₁ x₂ , <-tr> x₁₂ x₂ ⟫ ⟫ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ leaf (node key₂ ⟪ Red , v2 ⟫ t t₁)) (node _ ⟪ Red , _ ⟫ .(to-black leaf) (node _ ⟪ Black , v2 ⟫ t t₂)) key value - (t-right _ _ x₁ x₂ x₃ ti) (rbr-flip-rr x () lt trb) -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₂ ⟪ c2 , v2 ⟫ t t₁) (node key₃ ⟪ Red , c3 ⟫ leaf t₃)) (node _ ⟪ Red , _ ⟫ .(to-black (node key₂ ⟪ c2 , v2 ⟫ t t₁)) (node _ ⟪ Black , c3 ⟫ .leaf (node key₄ value₁ t₄ t₅))) key value (t-node key₂ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti ti₁) (rbr-flip-rr x y lt trb) = t-node _ _ _ x₁ x₂ x₃ x₄ x₅ rr01 (replaceTree1 _ _ _ ti) (t-right _ _ (proj1 rr00) (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RB-repl→ti _ _ _ _ (treeRightDown _ _ ti₁) trb)) where - rr00 : (key₃ < key₄) ∧ tr> key₃ t₄ ∧ tr> key₃ t₅ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt (proj2 (ti-property1 ti₁)) - rr01 : (key₁ < key₄) ∧ tr> key₁ t₄ ∧ tr> key₁ t₅ - rr01 = RB-repl→ti> _ _ _ _ _ trb (<-trans x₂ lt) x₆ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₂ ⟪ c2 , v2 ⟫ t t₁) (node key₃ ⟪ Red , c3 ⟫ (node key₄ value₁ t₂ t₅) .leaf)) (node _ ⟪ Red , _ ⟫ .(to-black (node key₂ ⟪ c2 , v2 ⟫ t t₁)) (node _ ⟪ Black , c3 ⟫ .(node key₄ value₁ t₂ t₅) (node key₅ value₂ t₄ t₆))) key value (t-node key₂ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-left .key₄ .key₃ x₇ x₈ x₉ ti₁)) (rbr-flip-rr x y lt trb) = t-node _ _ _ x₁ x₂ x₃ x₄ x₅ rr02 (replaceTree1 _ _ _ ti) (t-node _ _ _ x₇ (proj1 rr00) x₈ x₉ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ti₁ (RB-repl→ti _ _ _ _ t-leaf trb)) where - rr00 : (key₃ < key₅) ∧ tr> key₃ t₄ ∧ tr> key₃ t₆ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt tt - rr02 : (key₁ < key₅) ∧ tr> key₁ t₄ ∧ tr> key₁ t₆ - rr02 = ⟪ <-trans x₂ (proj1 rr00) , ⟪ <-tr> (proj1 (proj2 rr00)) x₂ , <-tr> (proj2 (proj2 rr00)) x₂ ⟫ ⟫ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₂ ⟪ c2 , v2 ⟫ t t₁) (node key₃ ⟪ Red , c3 ⟫ (node key₄ value₁ t₂ t₅) .(node key₆ _ _ _))) (node _ ⟪ Red , _ ⟫ .(to-black (node key₂ ⟪ c2 , v2 ⟫ t t₁)) (node _ ⟪ Black , c3 ⟫ .(node key₄ value₁ t₂ t₅) (node key₅ value₂ t₄ t₆))) key value (t-node key₂ _ _ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-node .key₄ .key₃ key₆ x₇ x₈ x₉ x₁₀ x₁₁ x₁₂ ti₁ ti₂)) (rbr-flip-rr x y lt trb) = t-node _ _ _ x₁ x₂ x₃ x₄ x₅ rr02 (replaceTree1 _ _ _ ti) (t-node _ _ _ x₇ (proj1 rr00) x₉ x₁₀ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ti₁ (RB-repl→ti _ _ _ _ ti₂ trb)) where - rr00 : (key₃ < key₅) ∧ tr> key₃ t₄ ∧ tr> key₃ t₆ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt ⟪ x₈ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ - rr02 : (key₁ < key₅) ∧ tr> key₁ t₄ ∧ tr> key₁ t₆ - rr02 = ⟪ <-trans x₂ (proj1 rr00) , ⟪ <-tr> (proj1 (proj2 rr00)) x₂ , <-tr> (proj2 (proj2 rr00)) x₂ ⟫ ⟫ -RB-repl→ti {_} {A} (node k1 ⟪ Black , c1 ⟫ (node k2 ⟪ Red , c2 ⟫ .leaf .leaf) leaf) (node _ ⟪ Black , _ ⟫ (node key₁ value₁ t₂ t₃) (node _ ⟪ Red , _ ⟫ .leaf leaf)) key value (t-left _ _ x₁ x₂ x₃ - (t-single .k2 .(⟪ Red , c2 ⟫))) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr10) x₁ (proj1 (proj2 rr10)) (proj2 (proj2 rr10)) tt tt (RB-repl→ti _ _ _ _ t-leaf trb) (t-single _ _ ) where - rr10 : (key₁ < k2 ) ∧ tr< k2 t₂ ∧ tr< k2 t₃ - rr10 = RB-repl→ti< _ _ _ _ _ trb lt tt -RB-repl→ti {_} {A} (node k1 ⟪ Black , c1 ⟫ (node k2 ⟪ Red , c2 ⟫ .leaf .(node key₂ _ _ _)) leaf) (node _ ⟪ Black , _ ⟫ (node key₁ value₁ t₂ t₃) (node _ ⟪ Red , _ ⟫ (node key₂ value₂ t₁ t₄) leaf)) key value - (t-left _ _ x₁ x₂ x₃ (t-right .k2 key₂ x₄ x₅ x₆ ti)) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr10) x₁ (proj1 (proj2 rr10)) (proj2 (proj2 rr10)) ⟪ x₄ , ⟪ x₅ , x₆ ⟫ ⟫ tt rr05 rr04 where - rr10 : (key₁ < k2 ) ∧ tr< k2 t₂ ∧ tr< k2 t₃ - rr10 = RB-repl→ti< _ _ _ _ _ trb lt tt - rr04 : treeInvariant (node k1 ⟪ Red , c1 ⟫ (node key₂ value₂ t₁ t₄) leaf) - rr04 = RTtoTI0 _ _ _ _ (t-left key₂ _ {_} {⟪ Red , c1 ⟫} {t₁} {t₄} (proj1 x₃) (proj1 (proj2 x₃)) (proj2 (proj2 x₃)) ti) r-node - rr05 : treeInvariant (node key₁ value₁ t₂ t₃) - rr05 = RB-repl→ti _ _ _ _ t-leaf trb -RB-repl→ti {_} {A} (node k1 ⟪ Black , c1 ⟫ (node k2 ⟪ Red , c2 ⟫ (node key₂ value₂ t₁ t₄) .leaf) leaf) (node _ ⟪ Black , _ ⟫ (node key₁ value₁ t₂ t₃) (node _ ⟪ Red , _ ⟫ .leaf leaf)) key value - (t-left _ _ x₁ x₂ x₃ (t-left key₂ .k2 x₄ x₅ x₆ ti)) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr10) x₁ (proj1 (proj2 rr10)) (proj2 (proj2 rr10)) tt tt (RB-repl→ti _ _ _ _ ti trb) (t-single _ _) where - rr10 : (key₁ < k2 ) ∧ tr< k2 t₂ ∧ tr< k2 t₃ - rr10 = RB-repl→ti< _ _ _ _ _ trb lt ⟪ x₄ , ⟪ x₅ , x₆ ⟫ ⟫ -RB-repl→ti {_} {A} (node k1 ⟪ Black , c1 ⟫ (node k2 ⟪ Red , c2 ⟫ (node key₂ value₃ left right) (node key₃ value₂ t₄ t₅)) leaf) (node _ ⟪ Black , _ ⟫ (node key₁ value₁ t₂ t₃) (node _ ⟪ Red , _ ⟫ .(node key₃ _ _ _) leaf)) key value - (t-left _ _ x₁ x₂ x₃ (t-node key₂ .k2 key₃ x₄ x₅ x₆ x₇ x₈ x₉ ti ti₁)) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr10) x₁ (proj1 (proj2 rr10)) (proj2 (proj2 rr10)) ⟪ x₅ , ⟪ x₈ , x₉ ⟫ ⟫ tt rr05 rr04 where - rr06 : key < k2 - rr06 = lt - rr10 : (key₁ < k2) ∧ tr< k2 t₂ ∧ tr< k2 t₃ - rr10 = RB-repl→ti< _ _ _ _ _ trb rr06 ⟪ x₄ , ⟪ x₆ , x₇ ⟫ ⟫ - rr04 : treeInvariant (node k1 ⟪ Red , c1 ⟫ (node key₃ value₂ t₄ t₅) leaf) - rr04 = RTtoTI0 _ _ _ _ (t-left _ _ (proj1 x₃) (proj1 (proj2 x₃)) (proj2 (proj2 x₃)) ti₁ ) (r-left (proj1 x₃) r-node) - rr05 : treeInvariant (node key₁ value₁ t₂ t₃) - rr05 = RB-repl→ti _ _ _ _ ti trb -RB-repl→ti (node key₁ ⟪ Black , c1 ⟫ (node key₂ ⟪ Red , c2 ⟫ .leaf .leaf) (node key₃ v3 t₂ t₃)) (node _ ⟪ Black , _ ⟫ (node key₄ value₁ t₄ t₅) (node _ ⟪ Red , _ ⟫ .leaf (node key₃ _ _ _))) key value - (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-single .key₂ .(⟪ Red , c2 ⟫)) ti₁) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr00) x₁ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) tt ⟪ <-trans x₁ x₂ , ⟪ <-tr> x₅ x₁ , <-tr> x₆ x₁ ⟫ ⟫ rr02 rr03 where - rr00 : (key₄ < key₂) ∧ tr< key₂ t₄ ∧ tr< key₂ t₅ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt tt - rr02 : treeInvariant (node key₄ value₁ t₄ t₅) - rr02 = RB-repl→ti _ _ _ _ t-leaf trb - rr03 : treeInvariant (node key₁ ⟪ Red , c1 ⟫ leaf (node key₃ v3 t₂ t₃)) - rr03 = RTtoTI0 _ _ _ _ (t-right _ _ {v3} {_} x₂ x₅ x₆ ti₁) r-node -RB-repl→ti (node key₁ ⟪ Black , c1 ⟫ (node key₂ ⟪ Red , c2 ⟫ leaf (node key₅ _ _ _)) (node key₃ v3 t₂ t₃)) (node _ ⟪ Black , _ ⟫ (node key₄ value₁ t₄ t₅) (node _ ⟪ Red , _ ⟫ (node key₅ value₂ t₁ t₆) (node key₃ _ _ _))) key value - (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-right .key₂ key₅ x₇ x₈ x₉ ti) ti₁) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr00) x₁ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ⟪ x₇ , ⟪ x₈ , x₉ ⟫ ⟫ ⟪ <-trans x₁ x₂ , ⟪ <-tr> x₅ x₁ , <-tr> x₆ x₁ ⟫ ⟫ rr02 rr03 where - rr00 : (key₄ < key₂) ∧ tr< key₂ t₄ ∧ tr< key₂ t₅ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt tt - rr02 : treeInvariant (node key₄ value₁ t₄ t₅) - rr02 = RB-repl→ti _ _ _ _ t-leaf trb - rr03 : treeInvariant (node key₁ ⟪ Red , c1 ⟫ (node key₅ value₂ t₁ t₆) (node key₃ v3 t₂ t₃)) - rr03 = RTtoTI0 _ _ _ _ (t-node _ _ _ {_} {v3} {_} {_} {_} {_} {_} (proj1 x₄) x₂ (proj1 (proj2 x₄)) (proj2 (proj2 x₄)) x₅ x₆ ti ti₁ ) r-node -RB-repl→ti (node key₁ ⟪ Black , c1 ⟫ (node key₂ ⟪ Red , c2 ⟫ .(node key₅ _ _ _) .leaf) (node key₃ v3 t₂ t₃)) (node _ ⟪ Black , _ ⟫ (node key₄ value₁ t₄ t₅) (node _ ⟪ Red , _ ⟫ .leaf (node key₃ _ _ _))) key value (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ - (t-left key₅ .key₂ x₇ x₈ x₉ ti) ti₁) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr00) x₁ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) tt ⟪ <-trans x₁ x₂ , ⟪ <-tr> x₅ x₁ , <-tr> x₆ x₁ ⟫ ⟫ rr02 rr04 where - rr00 : (key₄ < key₂) ∧ tr< key₂ t₄ ∧ tr< key₂ t₅ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt ⟪ x₇ , ⟪ x₈ , x₉ ⟫ ⟫ - rr02 : treeInvariant (node key₄ value₁ t₄ t₅) - rr02 = RB-repl→ti _ _ _ _ ti trb - rr03 : treeInvariant (node key₁ ⟪ Red , c1 ⟫ (node key₅ _ _ _) (node key₃ v3 t₂ t₃)) - rr03 = RTtoTI0 _ _ _ _ (t-node _ _ _ {_} {v3} {_} {_} {_} {_} {_} (proj1 x₃) x₂ (proj1 (proj2 x₃)) (proj2 (proj2 x₃)) x₅ x₆ ti ti₁) r-node - rr04 : treeInvariant (node key₁ ⟪ Red , c1 ⟫ leaf (node key₃ v3 t₂ t₃)) - rr04 = RTtoTI0 _ _ _ _ (t-right _ _ {v3} {_} x₂ x₅ x₆ ti₁) r-node -RB-repl→ti {_} {A} (node key₁ ⟪ Black , c1 ⟫ (node key₂ ⟪ Red , c2 ⟫ .(node key₅ _ _ _) (node key₆ value₆ t₆ t₇)) (node key₃ v3 t₂ t₃)) (node _ ⟪ Black , _ ⟫ (node key₄ value₁ t₄ t₅) (node _ ⟪ Red , _ ⟫ .(node key₆ _ _ _) (node key₃ _ _ _))) key value - (t-node _ _ key₃ x₁ x₂ x₃ x₄ x₅ x₆ (t-node key₅ .key₂ key₆ x₇ x₈ x₉ x₁₀ x₁₁ x₁₂ ti ti₂) ti₁) (rbr-rotate-ll x lt trb) = t-node _ _ _ (proj1 rr00) x₁ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) ⟪ x₈ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ ⟪ <-trans x₁ x₂ , ⟪ rr05 , <-tr> x₆ x₁ ⟫ ⟫ rr02 rr03 where - rr00 : (key₄ < key₂) ∧ tr< key₂ t₄ ∧ tr< key₂ t₅ - rr00 = RB-repl→ti< _ _ _ _ _ trb lt ⟪ x₇ , ⟪ x₉ , x₁₀ ⟫ ⟫ - rr02 : treeInvariant (node key₄ value₁ t₄ t₅) - rr02 = RB-repl→ti _ _ _ _ ti trb - rr03 : treeInvariant (node key₁ ⟪ Red , c1 ⟫ (node key₆ value₆ t₆ t₇) (node key₃ v3 t₂ t₃)) - rr03 = RTtoTI0 _ _ _ _(t-node _ _ _ {_} {value₁} {_} {_} {_} {_} {_} (proj1 x₄) x₂ (proj1 (proj2 x₄)) (proj2 (proj2 x₄)) x₅ x₆ ti₂ ti₁) r-node - rr05 : tr> key₂ t₂ - rr05 = <-tr> x₅ x₁ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ leaf (node key₂ ⟪ Red , v2 ⟫ leaf leaf)) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₃ value₁ t₃ t₄)) key value - (t-right .key₁ .key₂ x₁ x₂ x₃ (t-single .key₂ .(⟪ Red , _ ⟫))) (rbr-rotate-rr x lt trb) - = t-node _ _ _ x₁ (proj1 rr00) tt tt (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (t-single _ _) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₂ < key₃) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt tt -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ leaf (node key₂ ⟪ Red , v2 ⟫ leaf (node key₃ value₃ t t₁))) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₄ value₁ t₃ t₄)) key value - (t-right .key₁ .key₂ x₁ x₂ x₃ (t-right .key₂ key₃ x₄ x₅ x₆ ti)) (rbr-rotate-rr x lt trb) - = t-node _ _ _ x₁ (proj1 rr00) tt tt (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (t-single _ _ ) (RB-repl→ti _ _ _ _ ti trb) where - rr00 : (key₂ < key₄) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt ⟪ x₄ , ⟪ x₅ , x₆ ⟫ ⟫ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ leaf (node key₂ ⟪ Red , v2 ⟫ (node key₃ _ _ _) leaf)) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₄ value₁ t₃ t₄)) key value - (t-right .key₁ .key₂ x₁ x₂ x₃ (t-left key₃ .key₂ x₄ x₅ x₆ ti)) (rbr-rotate-rr x lt trb) - = t-node _ _ _ x₁ (proj1 rr00) tt ⟪ x₄ , ⟪ x₅ , x₆ ⟫ ⟫ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (t-right _ _ (proj1 x₂) (proj1 (proj2 x₂)) (proj2 (proj2 x₂)) ti) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₂ < key₄) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt tt -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ leaf (node key₂ ⟪ Red , v2 ⟫ (node key₃ _ _ _) (node key₄ _ _ _))) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₅ value₁ t₃ t₄)) key value - (t-right .key₁ .key₂ x₁ x₂ x₃ (t-node key₃ .key₂ key₄ x₄ x₅ x₆ x₇ x₈ x₉ ti ti₁)) (rbr-rotate-rr x lt trb) = t-node _ _ _ x₁ (proj1 rr00) tt ⟪ x₄ , ⟪ x₆ , x₇ ⟫ ⟫ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (t-right _ _ (proj1 x₂) (proj1 (proj2 x₂)) (proj2 (proj2 x₂)) ti) (RB-repl→ti _ _ _ _ ti₁ trb) where - rr00 : (key₂ < key₅) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt ⟪ x₅ , ⟪ x₈ , x₉ ⟫ ⟫ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ .(node key₃ _ _ _) (node key₂ ⟪ Red , v2 ⟫ .leaf .leaf)) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₄ value₁ t₃ t₄)) key value - (t-node key₃ .key₁ .key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-single .key₂ .(⟪ Red , v2 ⟫))) (rbr-rotate-rr x lt trb) - = t-node _ _ _ x₂ (proj1 rr00) ⟪ <-trans x₁ x₂ , ⟪ >-tr< x₃ x₂ , >-tr< x₄ x₂ ⟫ ⟫ tt (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (t-left _ _ x₁ x₃ x₄ ti) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₂ < key₄) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt tt -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₃ v3 t t₁) (node key₂ ⟪ Red , v2 ⟫ leaf (node key₄ _ _ _))) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₅ value₁ t₃ t₄)) key value - (t-node key₃ .key₁ .key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-right .key₂ key₄ x₇ x₈ x₉ ti₁)) (rbr-rotate-rr x lt trb) - = t-node _ _ _ x₂ (proj1 rr00) ⟪ <-trans x₁ x₂ , ⟪ >-tr< x₃ x₂ , >-tr< x₄ x₂ ⟫ ⟫ tt (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (t-left _ _ x₁ x₃ x₄ ti) (RB-repl→ti _ _ _ _ ti₁ trb) where - rr00 : (key₂ < key₅) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt ⟪ x₇ , ⟪ x₈ , x₉ ⟫ ⟫ -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₃ _ _ _) (node key₂ ⟪ Red , v2 ⟫ (node key₄ _ _ _) leaf)) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₅ value₁ t₃ t₄)) key value - (t-node key₃ key₁ key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-left key₄ key₂ x₇ x₈ x₉ ti₁)) (rbr-rotate-rr x lt trb) - = t-node _ _ _ x₂ (proj1 rr00) ⟪ <-trans x₁ x₂ , ⟪ >-tr< x₃ x₂ , >-tr< x₄ x₂ ⟫ ⟫ ⟪ x₇ , ⟪ x₈ , x₉ ⟫ ⟫ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (t-node _ _ _ x₁ (proj1 x₅) x₃ x₄ (proj1 (proj2 x₅)) (proj2 (proj2 x₅)) ti ti₁) (RB-repl→ti _ _ _ _ t-leaf trb) where - rr00 : (key₂ < key₅) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt tt -RB-repl→ti (node key₁ ⟪ Black , v1 ⟫ (node key₃ _ _ _) (node key₂ ⟪ Red , v2 ⟫ (node key₄ _ left right) (node key₅ _ _ _))) (node _ ⟪ Black , _ ⟫ (node _ ⟪ Red , _ ⟫ _ _) (node key₆ value₁ t₃ t₄)) key value - (t-node key₃ key₁ key₂ x₁ x₂ x₃ x₄ x₅ x₆ ti (t-node key₄ key₂ key₅ x₇ x₈ x₉ x₁₀ x₁₁ x₁₂ ti₁ ti₂)) (rbr-rotate-rr x lt trb) - = t-node _ _ _ x₂ (proj1 rr00) ⟪ <-trans x₁ x₂ , ⟪ >-tr< x₃ x₂ , >-tr< x₄ x₂ ⟫ ⟫ ⟪ x₇ , ⟪ x₉ , x₁₀ ⟫ ⟫ (proj1 (proj2 rr00)) (proj2 (proj2 rr00)) (RTtoTI0 _ _ _ _ (t-node _ _ _ {_} {value₁} x₁ (proj1 x₅) x₃ x₄ (proj1 (proj2 x₅)) (proj2 (proj2 x₅)) ti ti₁ ) r-node ) - (RB-repl→ti _ _ _ _ ti₂ trb) where - rr00 : (key₂ < key₆) ∧ tr> key₂ t₃ ∧ tr> key₂ t₄ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt ⟪ x₈ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ leaf leaf) .leaf) (node kn ⟪ Black , _ ⟫ (node kp ⟪ Red , _ ⟫ _ leaf) (node kg ⟪ Red , _ ⟫ leaf _)) .kn _ (t-left .kp .kg x x₁ x₂ ti) (rbr-rotate-lr .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = t-node _ _ _ lt1 lt2 tt tt tt tt (t-single _ _) (t-single _ _) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ (node key₁ value₁ t t₁) leaf) .leaf) (node kn ⟪ Black , v3 ⟫ (node kp ⟪ Red , _ ⟫ _ leaf) (node kg ⟪ Red , _ ⟫ leaf _)) .kn .v3 (t-left .kp .kg x x₁ x₂ (t-left .key₁ .kp x₃ x₄ x₅ ti)) (rbr-rotate-lr .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = - t-node _ _ _ lt1 lt2 ⟪ <-trans x₃ lt1 , ⟪ >-tr< x₄ lt1 , >-tr< x₅ lt1 ⟫ ⟫ tt tt tt (t-left _ _ x₃ x₄ x₅ ti) (t-single _ _) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .leaf (node key₁ .(⟪ Red , _ ⟫) .leaf .leaf)) .leaf) (node .key₁ ⟪ Black , _ ⟫ (node kp ⟪ Red , _ ⟫ _ leaf) (node kg ⟪ Red , _ ⟫ leaf _)) .key₁ _ (t-left .kp .kg x x₁ x₂ (t-right .kp .key₁ x₃ x₄ x₅ ti)) (rbr-rotate-lr .leaf .leaf kg kp .key₁ _ lt1 lt2 (rbr-node )) = t-node _ _ _ lt1 lt2 tt tt tt tt (t-single _ _) (t-single _ _) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .leaf (node key₁ value₁ t₁ t₂)) .leaf) (node kn ⟪ Black , value₃ ⟫ (node kp ⟪ Red , _ ⟫ _ leaf) (node kg ⟪ Red , _ ⟫ (node key₂ value₂ t₄ t₅) t₆)) key value (t-left .kp .kg x x₁ x₂ (t-right .kp .key₁ x₃ x₄ x₅ ti)) (rbr-rotate-lr .leaf .(node key₂ value₂ t₄ t₅) kg kp kn _ lt1 lt2 trb) = - t-node _ _ _ (proj1 rr00) (proj1 rr01) tt tt rr03 tt (t-single _ _) (t-left _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) (treeRightDown _ _ ( RB-repl→ti _ _ _ _ ti trb))) where - rr00 : (kp < kn) ∧ ⊤ ∧ ((kp < key₂) ∧ tr> kp t₄ ∧ tr> kp t₅ ) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₃ , ⟪ x₄ , x₅ ⟫ ⟫ - rr01 : (kn < kg) ∧ ⊤ ∧ ((key₂ < kg ) ∧ tr< kg t₄ ∧ tr< kg t₅ ) -- tr< kg (node key₂ value₂ t₄ t₅) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₂ - rr02 = proj2 (proj2 rr01) - rr03 : (kn < key₂) ∧ tr> kn t₄ ∧ tr> kn t₅ - rr03 with RB-repl→ti _ _ _ _ ti trb - ... | t-right .kn .key₂ x x₁ x₂ t = ⟪ x , ⟪ x₁ , x₂ ⟫ ⟫ -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .leaf (node key₁ value₁ t₁ t₂)) .leaf) (node kn ⟪ Black , value₃ ⟫ (node kp ⟪ Red , _ ⟫ _ (node key₂ value₂ t₃ t₅)) (node kg ⟪ Red , _ ⟫ leaf _)) key value (t-left .kp .kg x x₁ x₂ (t-right .kp .key₁ x₃ x₄ x₅ ti)) (rbr-rotate-lr .(node key₂ value₂ t₃ t₅) .leaf kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti trb -... | t-left .key₂ .kn x₆ x₇ x₈ t = - t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ tt tt (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) t) (t-single _ _) where - rr00 : (kp < kn) ∧ ((kp < key₂) ∧ tr> kp t₃ ∧ tr> kp t₅) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₃ , ⟪ x₄ , x₅ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₂ < kg) ∧ tr< kg t₃ ∧ tr< kg t₅) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₂ -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .leaf (node key₁ value₁ t₁ t₂)) .leaf) (node kn ⟪ Black , value₄ ⟫ (node kp ⟪ Red , _ ⟫ _ (node key₂ value₂ t₃ t₅)) (node kg ⟪ Red , _ ⟫ (node key₃ value₃ t₄ t₆) _)) key value (t-left .kp .kg x x₁ x₂ (t-right .kp .key₁ x₃ x₄ x₅ ti)) (rbr-rotate-lr .(node key₂ value₂ t₃ t₅) .(node key₃ value₃ t₄ t₆) kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti trb -... | t-node .key₂ .kn .key₃ x₆ x₇ x₈ x₉ x₁₀ x₁₁ t t₇ = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₆ , ⟪ x₈ , x₉ ⟫ ⟫ ⟪ x₇ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) t) (t-left _ _ (proj1 rr03) (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) t₇) where - rr00 : (kp < kn) ∧ ((kp < key₂) ∧ tr> kp t₃ ∧ tr> kp t₅) ∧ ((kp < key₃) ∧ tr> kp t₄ ∧ tr> kp t₆ ) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₃ , ⟪ x₄ , x₅ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₂ < kg) ∧ tr< kg t₃ ∧ tr< kg t₅) ∧ ((key₃ < kg) ∧ tr< kg t₄ ∧ tr< kg t₆ ) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₂ - rr03 = proj2 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ (node key₂ value₂ t₅ t₆) (node key₁ value₁ t₁ t₂)) leaf) (node kn ⟪ Black , _ ⟫ (node kp ⟪ Red , _ ⟫ _ t₃) (node kg ⟪ Red , _ ⟫ t₄ _)) key value (t-left .kp .kg x x₁ x₂ (t-node key₂ .kp .key₁ x₃ x₄ x₅ x₆ x₇ x₈ ti ti₁)) (rbr-rotate-lr t₃ t₄ kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti₁ trb -... | t-single .kn .(⟪ Red , _ ⟫) = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₃ (proj1 rr00) , ⟪ >-tr< x₅ (proj1 rr00) , >-tr< x₆ (proj1 rr00) ⟫ ⟫ tt tt tt (t-left _ _ x₃ x₅ x₆ ti) (t-single _ _) where - rr00 : (kp < kn) ∧ ⊤ ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₄ , ⟪ x₇ , x₈ ⟫ ⟫ - rr01 : (kn < kg) ∧ ⊤ ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₂ -... | t-right .kn key₃ {v1} {v3} {t₇} {t₈} x₉ x₁₀ x₁₁ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₃ (proj1 rr00) , ⟪ >-tr< x₅ (proj1 rr00) , >-tr< x₆ (proj1 rr00) ⟫ ⟫ tt ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt (t-left _ _ x₃ x₅ x₆ ti) (t-left _ _ (proj1 rr03) (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) (treeRightDown _ _ (RB-repl→ti _ _ _ _ ti₁ trb))) where - rr00 : (kp < kn) ∧ ⊤ ∧ ((kp < key₃) ∧ tr> kp t₇ ∧ tr> kp t₈) -- tr> kp (node key₃ v3 t₇ t₈) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₄ , ⟪ x₇ , x₈ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ⊤ ∧ ((key₃ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) -- tr< kg (node key₃ v3 t₇ t₈) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₂ - rr03 = proj2 (proj2 rr01) -... | t-left key₃ .kn {v1} {v3} {t₇} {t₈} x₉ x₁₀ x₁₁ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₃ (proj1 rr00) , ⟪ >-tr< x₅ (proj1 rr00) , >-tr< x₆ (proj1 rr00) ⟫ ⟫ ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt tt (t-node key₂ kp key₃ x₃ (proj1 rr02) x₅ x₆ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti (treeLeftDown _ _ (RB-repl→ti _ _ _ _ ti₁ trb))) (t-single _ _) where - rr00 : (kp < kn) ∧ ((kp < key₃) ∧ tr> kp t₇ ∧ tr> kp t₈) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₄ , ⟪ x₇ , x₈ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₃ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₂ -... | t-node key₃ .kn key₄ {v0} {v1} {v2} {t₇} {t₈} {t₉} {t₁₀} x₉ x₁₀ x₁₁ x₁₂ x₁₃ x₁₄ t t₃ = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₃ (proj1 rr00) , ⟪ >-tr< x₅ (proj1 rr00) , >-tr< x₆ (proj1 rr00) ⟫ ⟫ ⟪ x₉ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ ⟪ x₁₀ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ tt (t-node _ _ _ x₃ (proj1 rr02) x₅ x₆ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti (treeLeftDown _ _ (RB-repl→ti _ _ _ _ ti₁ trb))) (t-left _ _ (proj1 rr03) (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) t₃) where - rr00 : (kp < kn) ∧ ((kp < key₃) ∧ tr> kp t₇ ∧ tr> kp t₈) ∧ ((kp < key₄) ∧ tr> kp t₉ ∧ tr> kp t₁₀) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₄ , ⟪ x₇ , x₈ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₃ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) ∧ ((key₄ < kg) ∧ tr< kg t₉ ∧ tr< kg t₁₀) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₂ - rr03 = proj2 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .leaf leaf) (node key₂ value₂ t₅ t₆)) (node kn ⟪ Black , _ ⟫ (node kp ⟪ Red , _ ⟫ _ .leaf) (node kg ⟪ Red , _ ⟫ .leaf _)) .kn _ (t-node .kp .kg key₂ x x₁ x₂ x₃ x₄ x₅ (t-single .kp .(⟪ Red , v2 ⟫)) ti₁) (rbr-rotate-lr .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = t-node _ _ _ lt1 lt2 tt tt tt ⟪ <-trans lt2 x₁ , ⟪ <-tr> x₄ lt2 , <-tr> x₅ lt2 ⟫ ⟫ (t-single _ _) (t-right _ _ x₁ x₄ x₅ ti₁) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .(node key _ _ _) leaf) (node key₂ value₂ t₅ t₆)) (node kn ⟪ Black , _ ⟫ (node kp ⟪ Red , _ ⟫ _ .leaf) (node kg ⟪ Red , _ ⟫ .leaf _)) .kn _ (t-node .kp .kg key₂ x x₁ x₂ x₃ x₄ x₅ (t-left key .kp x₆ x₇ x₈ ti) ti₁) (rbr-rotate-lr .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = t-node _ _ _ lt1 lt2 ⟪ <-trans x₆ lt1 , ⟪ >-tr< x₇ lt1 , >-tr< x₈ lt1 ⟫ ⟫ tt tt ⟪ <-trans lt2 x₁ , ⟪ <-tr> x₄ lt2 , <-tr> x₅ lt2 ⟫ ⟫ (t-left _ _ x₆ x₇ x₈ ti) (t-right _ _ x₁ x₄ x₅ ti₁) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .leaf (node key₁ value₁ t₁ t₂)) .(node key₂ _ _ _)) (node kn ⟪ Black , value₃ ⟫ (node kp ⟪ Red , _ ⟫ _ t₃) (node kg ⟪ Red , _ ⟫ t₄ _)) key value (t-node .kp .kg key₂ x x₁ x₂ x₃ x₄ x₅ (t-right .kp .key₁ x₆ x₇ x₈ ti) ti₁) (rbr-rotate-lr t₃ t₄ kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti trb -... | t-single .kn .(⟪ Red , value₃ ⟫) = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt tt tt ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-single _ _) (t-right _ _ x₁ x₄ x₅ ti₁) where - rr00 : (kp < kn) ∧ ⊤ ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ - rr01 : (kn < kg) ∧ ⊤ ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ -... | t-right .kn key₃ {v1} {v3} {t₇} {t₈} x₉ x₁₀ x₁₁ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt tt ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-single _ _) (t-node _ _ _ (proj1 rr03) x₁ (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) x₄ x₅ (treeRightDown _ _ (RB-repl→ti _ _ _ _ ti trb)) ti₁) where - rr00 : (kp < kn) ∧ ⊤ ∧ ((kp < key₃) ∧ tr> kp t₇ ∧ tr> kp t₈) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ⊤ ∧ ((key₃ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ - rr03 = proj2 (proj2 rr01) -... | t-left key₃ .kn {v1} {v3} {t₇} {t₈} x₉ x₁₀ x₁₁ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) (treeLeftDown _ _ (RB-repl→ti _ _ _ _ ti trb))) (t-right _ _ x₁ x₄ x₅ ti₁) where - rr00 : (kp < kn) ∧ ((kp < key₃) ∧ tr> kp t₇ ∧ tr> kp t₈) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₃ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ - rr03 = proj1 (proj2 rr01) -... | t-node key₃ .kn key₄ {v0} {v1} {v2} {t₇} {t₈} {t₉} {t₁₀} x₉ x₁₀ x₁₁ x₁₂ x₁₃ x₁₄ t t₃ = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₉ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ ⟪ x₁₀ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) (treeLeftDown _ _ (RB-repl→ti _ _ _ _ ti trb))) (t-node _ _ _ (proj1 rr03) x₁ (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) x₄ x₅ t₃ ti₁) where - rr00 : (kp < kn) ∧ ((kp < key₃) ∧ tr> kp t₇ ∧ tr> kp t₈) ∧ ((kp < key₄) ∧ tr> kp t₉ ∧ tr> kp t₁₀) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₃ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) ∧ ((key₄ < kg) ∧ tr< kg t₉ ∧ tr< kg t₁₀) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ - rr03 = proj2 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , v1 ⟫ (node kp ⟪ Red , v2 ⟫ .(node key₃ _ _ _) (node key₁ value₁ t₁ t₂)) .(node key₂ _ _ _)) (node kn ⟪ Black , value₃ ⟫ (node kp ⟪ Red , _ ⟫ _ t₃) (node kg ⟪ Red , _ ⟫ t₄ _)) key value (t-node .kp .kg key₂ x x₁ x₂ x₃ x₄ x₅ (t-node key₃ .kp .key₁ x₆ x₇ x₈ x₉ x₁₀ x₁₁ ti ti₂) ti₁) (rbr-rotate-lr t₃ t₄ kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti₂ trb -... | t-single .kn .(⟪ Red , value₃ ⟫) = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₆ (proj1 rr00) , ⟪ >-tr< x₈ (proj1 rr00) , >-tr< x₉ (proj1 rr00) ⟫ ⟫ tt tt ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-left _ _ x₆ x₈ x₉ ti) (t-right _ _ x₁ x₄ x₅ ti₁) where - rr00 : (kp < kn) ∧ ⊤ ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₇ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ - rr01 : (kn < kg) ∧ ⊤ ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ -... | t-right .kn key₄ {v1} {v3} {t₇} {t₈} x₁₂ x₁₃ x₁₄ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₆ (proj1 rr00) , ⟪ >-tr< x₈ (proj1 rr00) , >-tr< x₉ (proj1 rr00) ⟫ ⟫ tt ⟪ x₁₂ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-left _ _ x₆ x₈ x₉ ti) (t-node _ _ _ (proj1 rr03) x₁ (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) x₄ x₅ (treeRightDown _ _ (RB-repl→ti _ _ _ _ ti₂ trb)) ti₁ ) where - rr00 : (kp < kn) ∧ ⊤ ∧ ((kp < key₄) ∧ tr> kp t₇ ∧ tr> kp t₈) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₇ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ - rr02 = proj2 (proj2 rr00) - rr01 : (kn < kg) ∧ ⊤ ∧ ((key₄ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ - rr03 = proj2 (proj2 rr01) -... | t-left key₄ .kn {v1} {v3} {t₇} {t₈} x₁₂ x₁₃ x₁₄ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₆ (proj1 rr00) , ⟪ >-tr< x₈ (proj1 rr00) , >-tr< x₉ (proj1 rr00) ⟫ ⟫ ⟪ x₁₂ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ tt ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-node _ _ _ x₆ (proj1 rr02) x₈ x₉ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti (treeLeftDown _ _ (RB-repl→ti _ _ _ _ ti₂ trb)) ) (t-right _ _ x₁ x₄ x₅ ti₁) where - rr00 : (kp < kn) ∧ ((kp < key₄) ∧ tr> kp t₇ ∧ tr> kp t₈) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₇ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₄ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ - rr03 = proj1 (proj2 rr01) -... | t-node key₄ .kn key₅ {v0} {v1} {v2} {t₇} {t₈} {t₉} {t₁₀}x₁₂ x₁₃ x₁₄ x₁₅ x₁₆ x₁₇ t t₃ = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x₆ (proj1 rr00) , ⟪ >-tr< x₈ (proj1 rr00) , >-tr< x₉ (proj1 rr00) ⟫ ⟫ ⟪ x₁₂ , ⟪ x₁₄ , x₁₅ ⟫ ⟫ ⟪ x₁₃ , ⟪ x₁₆ , x₁₇ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₁ , ⟪ <-tr> x₄ (proj1 rr01) , <-tr> x₅ (proj1 rr01) ⟫ ⟫ (t-node _ _ _ x₆ (proj1 rr02) x₈ x₉ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti t ) (t-node _ _ _ (proj1 rr04) x₁ (proj1 (proj2 rr04)) (proj2 (proj2 rr04)) x₄ x₅ (treeRightDown _ _ (RB-repl→ti _ _ _ _ ti₂ trb)) ti₁ ) where - rr00 : (kp < kn) ∧ ((kp < key₄) ∧ tr> kp t₇ ∧ tr> kp t₈) ∧ ((kp < key₅) ∧ tr> kp t₉ ∧ tr> kp t₁₀) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 ⟪ x₇ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ - rr02 = proj1 (proj2 rr00) - rr05 = proj2 (proj2 rr00) - rr01 : (kn < kg) ∧ ((key₄ < kg) ∧ tr< kg t₇ ∧ tr< kg t₈) ∧ ((key₅ < kg) ∧ tr< kg t₉ ∧ tr< kg t₁₀) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 x₃ - rr03 = proj1 (proj2 rr01) - rr04 = proj2 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .leaf leaf)) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf leaf) (node kp ⟪ Red , _ ⟫ leaf _)) .kn .vn (t-right .kg .kp x x₁ x₂ ti) (rbr-rotate-rl .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = t-node _ _ _ lt1 lt2 tt tt tt tt (t-single _ _) (t-single _ _) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node kn ⟪ Red , _ ⟫ leaf leaf) leaf)) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf leaf) (node kp ⟪ Red , _ ⟫ leaf _)) .kn .vn (t-right .kg .kp x x₁ x₂ ti) (rbr-rotate-rl .leaf .leaf kg kp kn _ lt1 lt2 (rbr-node )) = t-node _ _ _ lt1 lt2 tt tt tt tt (t-single _ _) (t-single _ _) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .leaf (node key₁ value₁ t₅ t₆))) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf leaf) (node kp ⟪ Red , _ ⟫ leaf _)) .kn .vn (t-right .kg .kp x x₁ x₂ (t-right .kp .key₁ x₃ x₄ x₅ ti)) (rbr-rotate-rl .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = t-node _ _ _ lt1 lt2 tt tt tt ⟪ <-trans lt2 x₃ , ⟪ <-tr> x₄ lt2 , <-tr> x₅ lt2 ⟫ ⟫ (t-single _ _) (t-right _ _ x₃ x₄ x₅ ti) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₂ _ _ _) (node key₁ value₁ t₅ t₆))) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf leaf) (node kp ⟪ Red , _ ⟫ leaf _)) key value (t-right .kg .kp x x₁ x₂ (t-node key₂ .kp .key₁ x₃ x₄ x₅ x₆ x₇ x₈ ti ti₁)) (rbr-rotate-rl .leaf .leaf kg kp kn _ lt1 lt2 trb) = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt tt tt ⟪ <-trans (proj1 rr01) x₄ , ⟪ <-tr> x₇ (proj1 rr01) , <-tr> x₈ (proj1 rr01) ⟫ ⟫ (t-single _ _) (t-right _ _ x₄ x₇ x₈ ti₁) where - rr00 : (kg < kn) ∧ ⊤ ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₁ - rr01 : (kn < kp) ∧ ⊤ ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₃ , ⟪ x₅ , x₆ ⟫ ⟫ -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₂ _ _ _) .leaf)) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf (node key₁ value₁ t₂ t₃)) (node kp ⟪ Red , _ ⟫ leaf _)) key value (t-right .kg .kp x x₁ x₂ (t-left key₂ .kp x₃ x₄ x₅ ti)) (rbr-rotate-rl .(node key₁ value₁ t₂ t₃) .leaf kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti trb -... | t-left .key₁ .kn x₆ x₇ x₈ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ tt tt (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) t) (t-single _ _) where - rr00 : (kg < kn) ∧ ((kg < key₁) ∧ tr> kg t₂ ∧ tr> kg t₃) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₁ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₁ < kp) ∧ tr< kp t₂ ∧ tr< kp t₃) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₃ , ⟪ x₄ , x₅ ⟫ ⟫ -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₂ _ _ _) .(node key₃ _ _ _))) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf (node key₁ value₁ t₂ t₃)) (node kp ⟪ Red , _ ⟫ leaf _)) key value (t-right .kg .kp x x₁ x₂ (t-node key₂ .kp key₃ x₃ x₄ x₅ x₆ x₇ x₈ ti ti₁)) (rbr-rotate-rl .(node key₁ value₁ t₂ t₃) .leaf kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti trb -... | t-left .key₁ .kn x₉ x₁₀ x₁₁ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt ⟪ <-trans (proj1 rr01) x₄ , ⟪ <-tr> x₇ (proj1 rr01) , <-tr> x₈ (proj1 rr01) ⟫ ⟫ (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) t) (t-right _ _ x₄ x₇ x₈ ti₁) where - rr00 : (kg < kn) ∧ ((kg < key₁) ∧ tr> kg t₂ ∧ tr> kg t₃) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₁ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₁ < kp) ∧ tr< kp t₂ ∧ tr< kp t₃) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₃ , ⟪ x₅ , x₆ ⟫ ⟫ -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .leaf .leaf)) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .(node key₁ _ _ _) .leaf) (node kp ⟪ Red , _ ⟫ leaf _)) .kn .vn (t-node key₁ .kg .kp x x₁ x₂ x₃ x₄ x₅ ti (t-single .kp .(⟪ Red , vp ⟫))) (rbr-rotate-rl .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = t-node _ _ _ lt1 lt2 ⟪ <-trans x lt1 , ⟪ >-tr< x₂ lt1 , >-tr< x₃ lt1 ⟫ ⟫ tt tt tt (t-left _ _ x x₂ x₃ ti) (t-single _ _) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .leaf .(node key₂ _ _ _))) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .(node key₁ _ _ _) .leaf) (node kp ⟪ Red , _ ⟫ leaf _)) .kn .vn (t-node key₁ .kg .kp x x₁ x₂ x₃ x₄ x₅ ti (t-right .kp key₂ x₆ x₇ x₈ ti₁)) (rbr-rotate-rl .leaf .leaf kg kp kn _ lt1 lt2 rbr-leaf) = t-node _ _ _ lt1 lt2 ⟪ <-trans x lt1 , ⟪ >-tr< x₂ lt1 , >-tr< x₃ lt1 ⟫ ⟫ tt tt ⟪ <-trans lt2 x₆ , ⟪ <-tr> x₇ lt2 , <-tr> x₈ lt2 ⟫ ⟫ (t-left _ _ x x₂ x₃ ti) (t-right _ _ x₆ x₇ x₈ ti₁) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₂ _ _ _) .leaf)) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .(node key₁ _ _ _) t₂) (node kp ⟪ Red , _ ⟫ leaf _)) key value (t-node key₁ .kg .kp x x₁ x₂ x₃ x₄ x₅ ti (t-left key₂ .kp x₆ x₇ x₈ ti₁)) (rbr-rotate-rl t₂ .leaf kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti₁ trb -... | t-single .kn .(⟪ Red , vn ⟫) = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ tt tt tt (t-left _ _ x x₂ x₃ ti) (t-single _ _) where - rr00 : (kg < kn) ∧ ⊤ ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr01 : (kn < kp) ∧ ⊤ ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ -... | t-left key₃ .kn {v1} {v3} {t₇} {t₃} x₉ x₁₀ x₁₁ ti₀ = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt tt (t-node _ _ _ x (proj1 rr02) x₂ x₃ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti ti₀) (t-single _ _) where - rr00 : (kg < kn) ∧ ((kg < key₃) ∧ tr> kg t₇ ∧ tr> kg t₃) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₃ < kp) ∧ tr< kp t₇ ∧ tr< kp t₃) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ - rr03 = proj1 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₂ _ _ _) .(node key₃ _ _ _))) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .(node key₁ _ _ _) t₂) (node kp ⟪ Red , _ ⟫ leaf _)) key value (t-node key₁ .kg .kp x x₁ x₂ x₃ x₄ x₅ ti (t-node key₂ .kp key₃ x₆ x₇ x₈ x₉ x₁₀ x₁₁ ti₁ ti₂)) (rbr-rotate-rl t₂ .leaf kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti₁ trb -... | t-single .kn .(⟪ Red , vn ⟫) = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ tt tt ⟪ <-trans (proj1 rr01) x₇ , ⟪ <-tr> x₁₀ (proj1 rr01) , <-tr> x₁₁ (proj1 rr01) ⟫ ⟫ (t-left _ _ x x₂ x₃ ti) (t-right _ _ x₇ x₁₀ x₁₁ ti₂) where - rr00 : (kg < kn) ∧ ⊤ ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kp) ∧ ⊤ ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₈ , x₉ ⟫ ⟫ -... | t-left key₄ .kn {v1} {v3} {t₇} {t₃} x₁₂ x₁₃ x₁₄ ti₀ = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ ⟪ x₁₂ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ tt ⟪ <-trans (proj1 rr01) x₇ , ⟪ <-tr> x₁₀ (proj1 rr01) , <-tr> x₁₁ (proj1 rr01) ⟫ ⟫ (t-node _ _ _ x (proj1 rr02) x₂ x₃ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti ti₀) (t-right _ _ x₇ x₁₀ x₁₁ ti₂) where - rr00 : (kg < kn) ∧ ((kg < key₄) ∧ tr> kg t₇ ∧ tr> kg t₃) ∧ ⊤ - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr02 = proj1 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₄ < kp) ∧ tr< kp t₇ ∧ tr< kp t₃) ∧ ⊤ - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₈ , x₉ ⟫ ⟫ -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₂ _ _ _) .leaf)) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf t₂) (node kp ⟪ Red , _ ⟫ (node key₁ value₁ t₃ t₄) _)) key value (t-right .kg .kp x x₁ x₂ (t-left key₂ .kp x₃ x₄ x₅ ti)) (rbr-rotate-rl t₂ .(node key₁ value₁ t₃ t₄) kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti trb -... | t-right .kn .key₁ x₆ x₇ x₈ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt tt ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ tt (t-single _ _) (t-left _ _ (proj1 rr03) (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) t) where - rr00 : (kg < kn) ∧ ⊤ ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₁ - rr02 = proj2 (proj2 rr00) - rr01 : (kn < kp) ∧ ⊤ ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₃ , ⟪ x₄ , x₅ ⟫ ⟫ - rr03 = proj2 (proj2 rr01) -... | t-node key₃ .kn .key₁ {v0} {v1} {v2} {t₇} {t₈} {t₁₀} x₆ x₇ x₈ x₉ x₁₀ x₁₁ t t₁ = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₆ , ⟪ x₈ , x₉ ⟫ ⟫ ⟪ x₇ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) t) (t-left _ _ (proj1 rr03) (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) t₁) where - rr00 : (kg < kn) ∧ ((kg < key₃) ∧ tr> kg t₇ ∧ tr> kg t₈) ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₁ - rr02 = proj1 (proj2 rr00) - rr04 = proj2 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₃ < kp) ∧ tr< kp t₇ ∧ tr< kp t₈) ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₃ , ⟪ x₄ , x₅ ⟫ ⟫ - rr03 = proj2 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₂ _ _ _) .(node key₃ _ _ _))) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .leaf t₂) (node kp ⟪ Red , _ ⟫ (node key₁ value₁ t₃ t₄) _)) key value (t-right .kg .kp x x₁ x₂ (t-node key₂ .kp key₃ x₃ x₄ x₅ x₆ x₇ x₈ ti ti₁)) (rbr-rotate-rl t₂ .(node key₁ value₁ t₃ t₄) kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti trb -... | t-right .kn .key₁ x₉ x₁₀ x₁₁ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt tt ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₄ , ⟪ <-tr> x₇ (proj1 rr01) , <-tr> x₈ (proj1 rr01) ⟫ ⟫ (t-single _ _) (t-node _ _ _ (proj1 rr03) x₄ (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) x₇ x₈ t ti₁ ) where - rr00 : (kg < kn) ∧ ⊤ ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₁ - rr01 : (kn < kp) ∧ ⊤ ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₃ , ⟪ x₅ , x₆ ⟫ ⟫ - rr03 = proj2 (proj2 rr01) -... | t-node key₄ .kn .key₁ {v0} {v1} {v2} {t₇} {t₈} {t₁₀} x₉ x₁₀ x₁₁ x₁₂ x₁₃ x₁₄ t t₁ = t-node _ _ _ (proj1 rr00) (proj1 rr01) tt ⟪ x₉ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ ⟪ x₁₀ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₄ , ⟪ <-tr> x₇ (proj1 rr01) , <-tr> x₈ (proj1 rr01) ⟫ ⟫ (t-right _ _ (proj1 rr02) (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) t) (t-node _ _ _ (proj1 rr04) x₄ (proj1 (proj2 rr04)) (proj2 (proj2 rr04)) x₇ x₈ t₁ ti₁ ) where - rr00 : (kg < kn) ∧ ((kg < key₄) ∧ tr> kg t₇ ∧ tr> kg t₈) ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₁ - rr02 = proj1 (proj2 rr00) - rr05 = proj2 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₄ < kp) ∧ tr< kp t₇ ∧ tr< kp t₈) ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₃ , ⟪ x₅ , x₆ ⟫ ⟫ - rr03 = proj1 (proj2 rr01) - rr04 = proj2 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₃ _ _ _) .leaf)) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .(node key₂ _ _ _) t₂) (node kp ⟪ Red , _ ⟫ (node key₁ value₁ t₃ t₄) _)) key value (t-node key₂ .kg .kp x x₁ x₂ x₃ x₄ x₅ ti (t-left key₃ .kp x₆ x₇ x₈ ti₁)) (rbr-rotate-rl t₂ .(node key₁ value₁ t₃ t₄) kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti₁ trb -... | t-right .kn .key₁ x₉ x₁₀ x₁₁ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ tt ⟪ x₉ , ⟪ x₁₀ , x₁₁ ⟫ ⟫ tt (t-left _ _ x x₂ x₃ ti ) (t-left _ _ (proj1 rr03) (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) t) where - rr00 : (kg < kn) ∧ ⊤ ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr02 = proj2 (proj2 rr00) - rr01 : (kn < kp) ∧ ⊤ ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ - rr03 = proj2 (proj2 rr01) -... | t-node key₄ .kn .key₁ {v0} {v1} {v2} {t₇} {t₈} {t₁₀} x₉ x₁₀ x₁₁ x₁₂ x₁₃ x₁₄ t t₁ = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ ⟪ x₉ , ⟪ x₁₁ , x₁₂ ⟫ ⟫ ⟪ x₁₀ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ tt (t-node _ _ _ x (proj1 rr02) x₂ x₃ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti t) (t-left _ _ (proj1 rr04) (proj1 (proj2 rr04)) (proj2 (proj2 rr04)) t₁) where - rr00 : (kg < kn) ∧ ((kg < key₄) ∧ tr> kg t₇ ∧ tr> kg t₈) ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr02 = proj1 (proj2 rr00) - rr05 = proj2 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₄ < kp) ∧ tr< kp t₇ ∧ tr< kp t₈) ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₇ , x₈ ⟫ ⟫ - rr03 = proj1 (proj2 rr01) - rr04 = proj2 (proj2 rr01) -RB-repl→ti (node kg ⟪ Black , vg ⟫ _ (node kp ⟪ Red , vp ⟫ .(node key₃ _ _ _) .(node key₄ _ _ _))) (node kn ⟪ Black , vn ⟫ (node kg ⟪ Red , _ ⟫ .(node key₂ _ _ _) t₂) (node kp ⟪ Red , _ ⟫ (node key₁ value₁ t₃ t₄) _)) key value (t-node key₂ .kg .kp x x₁ x₂ x₃ x₄ x₅ ti (t-node key₃ .kp key₄ x₆ x₇ x₈ x₉ x₁₀ x₁₁ ti₁ ti₂)) (rbr-rotate-rl t₂ .(node key₁ value₁ t₃ t₄) kg kp kn _ lt1 lt2 trb) with RB-repl→ti _ _ _ _ ti₁ trb -... | t-right .kn .key₁ x₁₂ x₁₃ x₁₄ t = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ tt ⟪ x₁₂ , ⟪ x₁₃ , x₁₄ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₇ , ⟪ <-tr> x₁₀ (proj1 rr01) , <-tr> x₁₁ (proj1 rr01) ⟫ ⟫ (t-left _ _ x x₂ x₃ ti) (t-node _ _ _ (proj1 rr03) x₇ (proj1 (proj2 rr03)) (proj2 (proj2 rr03)) x₁₀ x₁₁ t ti₂ ) where - rr00 : (kg < kn) ∧ ⊤ ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr02 = proj2 (proj2 rr00) - rr01 : (kn < kp) ∧ ⊤ ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₈ , x₉ ⟫ ⟫ - rr03 = proj2 (proj2 rr01) -... | t-node key₅ .kn .key₁ {v0} {v1} {v2} {t₇} {t₈} {t₁₀} x₁₂ x₁₃ x₁₄ x₁₅ x₁₆ x₁₇ t t₁ = t-node _ _ _ (proj1 rr00) (proj1 rr01) ⟪ <-trans x (proj1 rr00) , ⟪ >-tr< x₂ (proj1 rr00) , >-tr< x₃ (proj1 rr00) ⟫ ⟫ ⟪ x₁₂ , ⟪ x₁₄ , x₁₅ ⟫ ⟫ ⟪ x₁₃ , ⟪ x₁₆ , x₁₇ ⟫ ⟫ ⟪ <-trans (proj1 rr01) x₇ , ⟪ <-tr> x₁₀ (proj1 rr01) , <-tr> x₁₁ (proj1 rr01) ⟫ ⟫ (t-node _ _ _ x (proj1 rr02) x₂ x₃ (proj1 (proj2 rr02)) (proj2 (proj2 rr02)) ti t ) (t-node _ _ _ (proj1 rr04) x₇ (proj1 (proj2 rr04)) (proj2 (proj2 rr04)) x₁₀ x₁₁ t₁ ti₂ ) where - rr00 : (kg < kn) ∧ ((kg < key₅) ∧ tr> kg t₇ ∧ tr> kg t₈) ∧ ((kg < key₁) ∧ tr> kg t₃ ∧ tr> kg t₄) - rr00 = RB-repl→ti> _ _ _ _ _ trb lt1 x₄ - rr02 = proj1 (proj2 rr00) - rr05 = proj2 (proj2 rr00) - rr01 : (kn < kp) ∧ ((key₅ < kp) ∧ tr< kp t₇ ∧ tr< kp t₈) ∧ ((key₁ < kp) ∧ tr< kp t₃ ∧ tr< kp t₄) - rr01 = RB-repl→ti< _ _ _ _ _ trb lt2 ⟪ x₆ , ⟪ x₈ , x₉ ⟫ ⟫ - rr03 = proj1 (proj2 rr01) - rr04 = proj2 (proj2 rr01) - +RB-repl→ti = ? -- -- if we consider tree invariant, this may be much simpler and faster @@ -1821,38 +1458,12 @@ stackToPG : {n : Level} {A : Set n} → {key : ℕ } → (tree orig : bt A ) → (stack : List (bt A)) → stackInvariant key tree orig stack → ( stack ≡ orig ∷ [] ) ∨ ( stack ≡ tree ∷ orig ∷ [] ) ∨ PG A key tree stack -stackToPG {n} {A} {key} tree .tree .(tree ∷ []) s-nil = case1 refl -stackToPG {n} {A} {key} tree .(node _ _ _ tree) .(tree ∷ node _ _ _ tree ∷ []) (s-right _ _ _ x s-nil) = case2 (case1 refl) -stackToPG {n} {A} {key} tree .(node k2 v2 t5 (node k1 v1 t2 tree)) (tree ∷ node _ _ _ tree ∷ .(node k2 v2 t5 (node k1 v1 t2 tree) ∷ [])) (s-right tree (node k2 v2 t5 (node k1 v1 t2 tree)) t2 {k1} {v1} x (s-right (node k1 v1 t2 tree) (node k2 v2 t5 (node k1 v1 t2 tree)) t5 {k2} {v2} x₁ s-nil)) = case2 (case2 - record { parent = node k1 v1 t2 tree ; grand = _ ; pg = s2-1s2p x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig (tree ∷ node _ _ _ tree ∷ .(node k2 v2 t5 (node k1 v1 t2 tree) ∷ _)) (s-right tree orig t2 {k1} {v1} x (s-right (node k1 v1 t2 tree) orig t5 {k2} {v2} x₁ (s-right _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 t2 tree ; grand = _ ; pg = s2-1s2p x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig (tree ∷ node _ _ _ tree ∷ .(node k2 v2 t5 (node k1 v1 t2 tree) ∷ _)) (s-right tree orig t2 {k1} {v1} x (s-right (node k1 v1 t2 tree) orig t5 {k2} {v2} x₁ (s-left _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 t2 tree ; grand = _ ; pg = s2-1s2p x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree .(node k2 v2 (node k1 v1 t1 tree) t2) .(tree ∷ node k1 v1 t1 tree ∷ node k2 v2 (node k1 v1 t1 tree) t2 ∷ []) (s-right _ _ t1 {k1} {v1} x (s-left _ _ t2 {k2} {v2} x₁ s-nil)) = case2 (case2 - record { parent = node k1 v1 t1 tree ; grand = _ ; pg = s2-1sp2 x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig .(tree ∷ node k1 v1 t1 tree ∷ node k2 v2 (node k1 v1 t1 tree) t2 ∷ _) (s-right _ _ t1 {k1} {v1} x (s-left _ _ t2 {k2} {v2} x₁ (s-right _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 t1 tree ; grand = _ ; pg = s2-1sp2 x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig .(tree ∷ node k1 v1 t1 tree ∷ node k2 v2 (node k1 v1 t1 tree) t2 ∷ _) (s-right _ _ t1 {k1} {v1} x (s-left _ _ t2 {k2} {v2} x₁ (s-left _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 t1 tree ; grand = _ ; pg = s2-1sp2 x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree .(node _ _ tree _) .(tree ∷ node _ _ tree _ ∷ []) (s-left _ _ t1 {k1} {v1} x s-nil) = case2 (case1 refl) -stackToPG {n} {A} {key} tree .(node _ _ _ (node k1 v1 tree t1)) .(tree ∷ node k1 v1 tree t1 ∷ node _ _ _ (node k1 v1 tree t1) ∷ []) (s-left _ _ t1 {k1} {v1} x (s-right _ _ _ x₁ s-nil)) = case2 (case2 - record { parent = node k1 v1 tree t1 ; grand = _ ; pg = s2-s12p x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig .(tree ∷ node k1 v1 tree t1 ∷ node _ _ _ (node k1 v1 tree t1) ∷ _) (s-left _ _ t1 {k1} {v1} x (s-right _ _ _ x₁ (s-right _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 tree t1 ; grand = _ ; pg = s2-s12p x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig .(tree ∷ node k1 v1 tree t1 ∷ node _ _ _ (node k1 v1 tree t1) ∷ _) (s-left _ _ t1 {k1} {v1} x (s-right _ _ _ x₁ (s-left _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 tree t1 ; grand = _ ; pg = s2-s12p x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree .(node _ _ (node k1 v1 tree t1) _) .(tree ∷ node k1 v1 tree t1 ∷ node _ _ (node k1 v1 tree t1) _ ∷ []) (s-left _ _ t1 {k1} {v1} x (s-left _ _ _ x₁ s-nil)) = case2 (case2 - record { parent = node k1 v1 tree t1 ; grand = _ ; pg = s2-s1p2 x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig .(tree ∷ node k1 v1 tree t1 ∷ node _ _ (node k1 v1 tree t1) _ ∷ _) (s-left _ _ t1 {k1} {v1} x (s-left _ _ _ x₁ (s-right _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 tree t1 ; grand = _ ; pg = s2-s1p2 x refl refl ; rest = _ ; stack=gp = refl } ) -stackToPG {n} {A} {key} tree orig .(tree ∷ node k1 v1 tree t1 ∷ node _ _ (node k1 v1 tree t1) _ ∷ _) (s-left _ _ t1 {k1} {v1} x (s-left _ _ _ x₁ (s-left _ _ _ x₂ si))) = case2 (case2 - record { parent = node k1 v1 tree t1 ; grand = _ ; pg = s2-s1p2 x refl refl ; rest = _ ; stack=gp = refl } ) +stackToPG {n} {A} {key} = ? stackCase1 : {n : Level} {A : Set n} → {key : ℕ } → {tree orig : bt A } → {stack : List (bt A)} → stackInvariant key tree orig stack → stack ≡ orig ∷ [] → tree ≡ orig -stackCase1 s-nil refl = refl +stackCase1 = ? pg-prop-1 : {n : Level} (A : Set n) → (key : ℕ) → (tree orig : bt A ) → (stack : List (bt A)) → (pg : PG A key tree stack) @@ -1871,12 +1482,7 @@ → (stack : List (bt (Color ∧ A))) → (si : stackInvariant key tree orig stack ) → RBtreeInvariant tree PGtoRBinvariant1 tree .tree rb .(tree ∷ []) s-nil = rb -PGtoRBinvariant1 tree orig rb (tree ∷ rest) (s-right .tree .orig tree₁ x si) with PGtoRBinvariant1 _ orig rb _ si -... | rb-red _ value x₁ x₂ x₃ t t₁ = t₁ -... | rb-black _ value x₁ t t₁ = t₁ -PGtoRBinvariant1 tree orig rb (tree ∷ rest) (s-left .tree .orig tree₁ x si) with PGtoRBinvariant1 _ orig rb _ si -... | rb-red _ value x₁ x₂ x₃ t t₁ = t -... | rb-black _ value x₁ t t₁ = t +PGtoRBinvariant1 tree orig rb = ? RBI-child-replaced : {n : Level} {A : Set n} (tr : bt (Color ∧ A)) (key : ℕ) → RBtreeInvariant tr → RBtreeInvariant (child-replaced key tr) RBI-child-replaced {n} {A} leaf key rbi = rbi @@ -1898,85 +1504,7 @@ → stackInvariant key tree1 tree0 stack → (tree1 ≡ leaf ) ∨ ( node-key tree1 ≡ just key ) → (exit : (stack : List ( bt (Color ∧ A))) (r : RBI key value tree0 stack ) → t ) → t -createRBT {n} {m} {A} {t} key value orig rbi ti tree (x ∷ []) si P exit = crbt00 orig P refl where - crbt00 : (tree1 : bt (Color ∧ A)) → (tree ≡ leaf ) ∨ ( node-key tree ≡ just key ) → tree1 ≡ orig → t - crbt00 leaf P refl = exit (x ∷ []) record { - tree = leaf - ; repl = node key ⟪ Red , value ⟫ leaf leaf - ; origti = ti - ; origrb = rbi - ; treerb = rb-leaf - ; replrb = rb-red key value refl refl refl rb-leaf rb-leaf - ; replti = t-single _ _ - ; si = subst (λ k → stackInvariant key k leaf _ ) crbt01 si - ; state = rotate leaf refl rbr-leaf - } where - crbt01 : tree ≡ leaf - crbt01 with si-property-last _ _ _ _ si | si-property1 si - ... | refl | refl = refl - crbt00 (node key₁ value₁ left right ) (case1 eq) refl with si-property-last _ _ _ _ si | si-property1 si - ... | refl | refl = ⊥-elim (bt-ne (sym eq)) - crbt00 (node key₁ value₁ left right ) (case2 eq) refl with si-property-last _ _ _ _ si | si-property1 si - ... | refl | refl = exit (x ∷ []) record { - tree = node key₁ value₁ left right - ; repl = node key₁ ⟪ proj1 value₁ , value ⟫ left right - ; origti = ti - ; origrb = rbi - ; treerb = rbi - ; replrb = crbt03 value₁ rbi - ; replti = RTtoTI0 _ _ _ _ (siToTreeinvariant _ _ _ _ ti si) r-node - ; si = si - ; state = rebuild refl (crbt01 value₁ ) (λ ()) crbt04 - } where - crbt01 : (value₁ : Color ∧ A) → black-depth (node key₁ ⟪ proj1 value₁ , value ⟫ left right) ≡ black-depth (node key₁ value₁ left right) - crbt01 ⟪ Red , proj4 ⟫ = refl - crbt01 ⟪ Black , proj4 ⟫ = refl - crbt03 : (value₁ : Color ∧ A) → RBtreeInvariant (node key₁ value₁ left right) → RBtreeInvariant (node key₁ ⟪ proj1 value₁ , value ⟫ left right) - crbt03 ⟪ Red , proj4 ⟫ (rb-red .key₁ .proj4 x x₁ x₂ rbi rbi₁) = rb-red key₁ _ x x₁ x₂ rbi rbi₁ - crbt03 ⟪ Black , proj4 ⟫ (rb-black .key₁ .proj4 x rbi rbi₁) = rb-black key₁ _ x rbi rbi₁ - keq : ( just key₁ ≡ just key ) → key₁ ≡ key - keq refl = refl - crbt04 : replacedRBTree key value (node key₁ value₁ left right) (node key₁ ⟪ proj1 value₁ , value ⟫ left right) - crbt04 = subst (λ k → replacedRBTree k value (node key₁ value₁ left right) (node key₁ ⟪ proj1 value₁ , value ⟫ left right)) (keq eq) rbr-node -createRBT {n} {m} {A} {t} key value orig rbi ti tree (x ∷ leaf ∷ stack) si P exit = ⊥-elim (si-property-parent-node _ _ _ si refl) -createRBT {n} {m} {A} {t} key value orig rbi ti tree sp@(x ∷ node kp vp pleft pright ∷ stack) si P exit = crbt00 tree P refl where - crbt00 : (tree1 : bt (Color ∧ A)) → (tree ≡ leaf ) ∨ ( node-key tree ≡ just key ) → tree1 ≡ tree → t - crbt00 leaf P refl = exit sp record { - tree = leaf - ; repl = node key ⟪ Red , value ⟫ leaf leaf - ; origti = ti - ; origrb = rbi - ; treerb = rb-leaf - ; replrb = rb-red key value refl refl refl rb-leaf rb-leaf - ; replti = t-single _ _ - ; si = si - ; state = rotate leaf refl rbr-leaf - } - crbt00 (node key₁ value₁ left right ) (case1 eq) refl = ⊥-elim (bt-ne (sym eq)) - crbt00 (node key₁ value₁ left right ) (case2 eq) refl with si-property-last _ _ _ _ si | si-property1 si - ... | eq1 | eq2 = exit sp record { - tree = node key₁ value₁ left right - ; repl = node key₁ ⟪ proj1 value₁ , value ⟫ left right - ; origti = ti - ; origrb = rbi - ; treerb = treerb - ; replrb = crbt03 value₁ treerb - ; replti = RB-repl→ti _ _ _ _ (siToTreeinvariant _ _ _ _ ti (subst (λ k → stackInvariant _ _ orig (k ∷ _)) eq2 si )) crbt04 - ; si = si - ; state = rebuild refl (crbt01 value₁ ) (λ ()) crbt04 - } where - crbt01 : (value₁ : Color ∧ A) → black-depth (node key₁ ⟪ proj1 value₁ , value ⟫ left right) ≡ black-depth (node key₁ value₁ left right) - crbt01 ⟪ Red , proj4 ⟫ = refl - crbt01 ⟪ Black , proj4 ⟫ = refl - crbt03 : (value₁ : Color ∧ A) → RBtreeInvariant (node key₁ value₁ left right) → RBtreeInvariant (node key₁ ⟪ proj1 value₁ , value ⟫ left right) - crbt03 ⟪ Red , proj4 ⟫ (rb-red .key₁ .proj4 x x₁ x₂ rbi rbi₁) = rb-red key₁ _ x x₁ x₂ rbi rbi₁ - crbt03 ⟪ Black , proj4 ⟫ (rb-black .key₁ .proj4 x rbi rbi₁) = rb-black key₁ _ x rbi rbi₁ - keq : ( just key₁ ≡ just key ) → key₁ ≡ key - keq refl = refl - crbt04 : replacedRBTree key value (node key₁ value₁ left right) (node key₁ ⟪ proj1 value₁ , value ⟫ left right) - crbt04 = subst (λ k → replacedRBTree k value (node key₁ value₁ left right) (node key₁ ⟪ proj1 value₁ , value ⟫ left right)) (keq eq) rbr-node - treerb : RBtreeInvariant (node key₁ value₁ left right) - treerb = PGtoRBinvariant1 _ orig rbi _ si +createRBT {n} {m} {A} {t} key value orig rbi ti tree = ? ti-to-black : {n : Level} {A : Set n} → {tree : bt (Color ∧ A)} → treeInvariant tree → treeInvariant (to-black tree) @@ -2015,14 +1543,12 @@ → t insertCase4 leaf eq1 eq rot col si = ⊥-elim (rb04 eq eq1 si) where -- can't happen rb04 : {stack : List ( bt ( Color ∧ A))} → stack ≡ RBI.tree r ∷ orig ∷ [] → leaf ≡ orig → stackInvariant key (RBI.tree r) orig stack → ⊥ - rb04 refl refl (s-right tree leaf tree₁ x si) = si-property2 _ (s-right tree leaf tree₁ x si) refl - rb04 refl refl (s-left tree₁ leaf tree x si) = si-property2 _ (s-left tree₁ leaf tree x si) refl + rb04 = ? insertCase4 tr0@(node key₁ value₁ left right) refl eq rot col si with <-cmp key key₁ ... | tri< a ¬b ¬c = rb07 col where rb04 : stackInvariant key (RBI.tree r) orig stack → stack ≡ RBI.tree r ∷ orig ∷ [] → tr0 ≡ orig → left ≡ RBI.tree r - rb04 (s-left tree₁ .(node key₁ value₁ left right) tree {key₂} x s-nil) refl refl = refl - rb04 (s-right tree .(node key₁ _ tree₁ tree) tree₁ x s-nil) refl refl with si-property1 si - ... | refl = ⊥-elim ( nat-<> x a ) + rb04 = ? -- (s-left tree₁ .(node key₁ value₁ left right) tree {key₂} x s-nil) eq eq1 = ? + -- rb04 (s-right tree .(node key₁ _ tree₁ tree) tree₁ x s-nil) eq eq1 = ? rb06 : black-depth repl ≡ black-depth right rb06 = begin black-depth repl ≡⟨ sym (RB-repl→eq _ _ (RBI.treerb r) rot) ⟩ @@ -2067,12 +1593,12 @@ rb10 : replacedRBTree key value (node key₁ ⟪ Black , proj2 value₁ ⟫ left right) (node key₁ ⟪ Black , proj2 value₁ ⟫ repl right) rb10 = rbr-black-left repl-red a (subst (λ k → replacedRBTree key value k repl) (sym (rb04 si eq refl)) rot) - ... | tri≈ ¬a b ¬c = ⊥-elim ( si-property-pne _ _ stack eq si b ) -- can't happen + ... | tri≈ ¬a b ¬c = ? -- ⊥-elim ( si-property-pne _ _ stack eq si b ) -- can't happen ... | tri> ¬a ¬b c = rb07 col where rb04 : stackInvariant key (RBI.tree r) orig stack → stack ≡ RBI.tree r ∷ orig ∷ [] → tr0 ≡ orig → right ≡ RBI.tree r - rb04 (s-right tree .(node key₁ _ tree₁ tree) tree₁ x s-nil) refl refl = refl - rb04 (s-left tree₁ .(node key₁ value₁ left right) tree {key₂} x si) refl refl with si-property1 si - ... | refl = ⊥-elim ( nat-<> x c ) + rb04 = ? -- (s-right tree .(node key₁ _ tree₁ tree) tree₁ x s-nil) refl refl = refl + -- rb04 (s-left tree₁ .(node key₁ value₁ left right) tree {key₂} x si) refl refl with si-property1 si + -- ... | refl = ⊥-elim ( nat-<> x c ) rb06 : black-depth repl ≡ black-depth left rb06 = begin black-depth repl ≡⟨ sym (RB-repl→eq _ _ (RBI.treerb r) rot) ⟩ @@ -2150,9 +1676,10 @@ rb03 : black-depth n1 ≡ black-depth repl rb03 = trans (sym (RBtreeEQ (subst (λ k → RBtreeInvariant k) x (treerb pg)))) (RB-repl→eq _ _ (RBI.treerb r) rot) rb02 : RBtreeInvariant rb01 - rb02 with subst (λ k → RBtreeInvariant k) x (treerb pg) - ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value (trans (sym ceq) cx) cx₁ (sym rb03) (RBI.replrb r) t₁ - ... | rb-black .kp value ex t t₁ = rb-black kp value (sym rb03) (RBI.replrb r) t₁ + rb02 = ? + -- with subst (λ k → RBtreeInvariant k) x (treerb pg) + -- ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value (trans (sym ceq) cx) cx₁ (sym rb03) (RBI.replrb r) t₁ + -- ... | rb-black .kp value ex t t₁ = rb-black kp value (sym rb03) (RBI.replrb r) t₁ rb05 : treeInvariant (node kp vp (RBI.tree r) n1 ) rb05 = subst (λ k → treeInvariant k) x (rb08 pg) rb04 : key < kp @@ -2180,9 +1707,9 @@ rb03 : black-depth n1 ≡ black-depth repl rb03 = trans (RBtreeEQ (subst (λ k → RBtreeInvariant k) x (treerb pg))) ((RB-repl→eq _ _ (RBI.treerb r) rot)) rb02 : RBtreeInvariant rb01 - rb02 with subst (λ k → RBtreeInvariant k) x (treerb pg) - ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value cx (trans (sym ceq) cx₁) rb03 t (RBI.replrb r) - ... | rb-black .kp value ex t t₁ = rb-black kp value rb03 t (RBI.replrb r) + rb02 = ? -- with subst (λ k → RBtreeInvariant k) x (treerb pg) + -- ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value cx (trans (sym ceq) cx₁) rb03 t (RBI.replrb r) + -- ... | rb-black .kp value ex t t₁ = rb-black kp value rb03 t (RBI.replrb r) rb05 : treeInvariant (node kp vp n1 (RBI.tree r) ) rb05 = subst (λ k → treeInvariant k) x (rb08 pg) rb04 : kp < key @@ -2210,9 +1737,9 @@ rb03 : black-depth n1 ≡ black-depth repl rb03 = trans (sym (RBtreeEQ (subst (λ k → RBtreeInvariant k) x (treerb pg)))) ((RB-repl→eq _ _ (RBI.treerb r) rot)) rb02 : RBtreeInvariant rb01 - rb02 with subst (λ k → RBtreeInvariant k) x (treerb pg) - ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value (trans (sym ceq) cx) cx₁ (sym rb03) (RBI.replrb r) t₁ - ... | rb-black .kp value ex t t₁ = rb-black kp value (sym rb03) (RBI.replrb r) t₁ + rb02 = ? -- with subst (λ k → RBtreeInvariant k) x (treerb pg) + -- ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value (trans (sym ceq) cx) cx₁ (sym rb03) (RBI.replrb r) t₁ + -- ... | rb-black .kp value ex t t₁ = rb-black kp value (sym rb03) (RBI.replrb r) t₁ rb05 : treeInvariant (node kp vp (RBI.tree r) n1) rb05 = subst (λ k → treeInvariant k) x (rb08 pg) rb04 : key < kp @@ -2240,9 +1767,9 @@ rb03 : black-depth n1 ≡ black-depth repl rb03 = trans (RBtreeEQ (subst (λ k → RBtreeInvariant k) x (treerb pg))) ((RB-repl→eq _ _ (RBI.treerb r) rot)) rb02 : RBtreeInvariant rb01 - rb02 with subst (λ k → RBtreeInvariant k) x (treerb pg) - ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value cx (trans (sym ceq) cx₁) rb03 t (RBI.replrb r) - ... | rb-black .kp value ex t t₁ = rb-black kp value rb03 t (RBI.replrb r) + rb02 = ? -- with subst (λ k → RBtreeInvariant k) x (treerb pg) + -- ... | rb-red .kp value cx cx₁ ex₂ t t₁ = rb-red kp value cx (trans (sym ceq) cx₁) rb03 t (RBI.replrb r) + -- ... | rb-black .kp value ex t t₁ = rb-black kp value rb03 t (RBI.replrb r) rb05 : treeInvariant (node kp vp n1 (RBI.tree r)) rb05 = subst (λ k → treeInvariant k) x (rb08 pg) rb04 : kp < key @@ -2261,8 +1788,8 @@ → color repl ≡ Red → color (PG.uncle pg) ≡ Black → color (PG.parent pg) ≡ Red → t insertCase5 leaf eq pg rot repl-red uncle-black pcolor = ⊥-elim ( rb00 repl repl-red (cong color (sym eq))) where rb00 : (repl : bt (Color ∧ A)) → color repl ≡ Red → color repl ≡ Black → ⊥ - rb00 (node key ⟪ Black , proj4 ⟫ repl repl₁) () eq1 - rb00 (node key ⟪ Red , proj4 ⟫ repl repl₁) eq () + rb00 = ? -- (node key ⟪ Black , proj4 ⟫ repl repl₁) () eq1 + -- rb00 (node key ⟪ Red , proj4 ⟫ repl repl₁) eq () insertCase5 (node rkey vr rp-left rp-right) eq pg rot repl-red uncle-black pcolor = insertCase51 where rb00 : stackInvariant key (RBI.tree r) orig (RBI.tree r ∷ PG.parent pg ∷ PG.grand pg ∷ PG.rest pg) rb00 = subst (λ k → stackInvariant key (RBI.tree r) orig k) (PG.stack=gp pg) (RBI.si r) @@ -2643,8 +2170,8 @@ ... | rebuild ceq bdepth-eq ¬leaf rot = rebuildCase ceq bdepth-eq ¬leaf rot ... | top-black eq rot = exit stack (trans eq (cong (λ k → k ∷ []) rb00)) r where rb00 : RBI.tree r ≡ orig - rb00 with si-property-last _ _ _ _ (subst (λ k → stackInvariant key (RBI.tree r) orig k) (eq) (RBI.si r)) - ... | refl = refl + rb00 = ? -- with si-property-last _ _ _ _ (subst (λ k → stackInvariant key (RBI.tree r) orig k) (eq) (RBI.si r)) + -- ... | refl = refl ... | rotate _ repl-red rot with stackToPG (RBI.tree r) orig stack (RBI.si r) ... | case1 eq = exit stack eq r -- no stack, replace top node ... | case2 (case1 eq) = insertCase4 orig refl eq rot (case1 repl-red) (RBI.si r) -- one level stack, orig is parent of repl
--- a/logic.agda Sun Aug 04 13:05:12 2024 +0900 +++ b/logic.agda Tue Aug 13 23:03:40 2024 +0900 @@ -91,8 +91,8 @@ no0 : (A → ⊥) → Dec0 A open _∧_ -∧-injective : {n m : Level} {A : Set n} {B : Set m} → {a b : A ∧ B} → proj1 a ≡ proj1 b → proj2 a ≡ proj2 b → a ≡ b -∧-injective refl refl = refl +∧-uniue : {n m : Level} {A : Set n} {B : Set m} → {a b : A ∧ B} → proj1 a ≡ proj1 b → proj2 a ≡ proj2 b → a ≡ b +∧-uniue refl refl = refl not-not-bool : { b : Bool } → not (not b) ≡ b not-not-bool {true} = refl