Mercurial > hg > Members > Moririn
diff hoareBinaryTree.agda @ 718:93ec11846a27
...
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 16 May 2022 09:27:13 +0900 |
parents | 52938e8a54a2 |
children | 0b791ae19543 |
line wrap: on
line diff
--- a/hoareBinaryTree.agda Wed May 11 09:56:11 2022 +0900 +++ b/hoareBinaryTree.agda Mon May 16 09:27:13 2022 +0900 @@ -56,7 +56,6 @@ find : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A ) → (stack : List (bt A)) → (next : (tree1 : bt A) → (stack : List (bt A)) → t) → (exit : (tree1 : bt A) → (stack : List (bt A)) → t) → t -find key _ (leaf ∷ st) _ exit = exit leaf [] find key leaf st _ exit = exit leaf st find key (node key₁ v1 tree tree₁) st next exit with <-cmp key key₁ find key n st _ exit | tri≈ ¬a refl ¬c = exit n st @@ -97,8 +96,8 @@ insertTest1 = insertTree leaf 1 1 (λ x → x ) insertTest2 = insertTree insertTest1 2 1 (λ x → x ) -insertTest3 = insertTree insertTest2 3 2 (λ x → x ) -insertTest4 = insertTree insertTest3 2 2 (λ x → x ) -- this is wrong +insertTest3 = insertTree insertTest2 3 3 (λ x → x ) +insertTest4 = insertTree insertTest3 1 4 (λ x → x ) -- this is wrong updateTree : {n m : Level} {A : Set n} {t : Set m} → (tree : bt A) → (key : ℕ) → (value : A) → (empty : bt A → t ) → (next : A → bt A → t ) → t updateTree {_} {_} {A} {t} tree key value empty next = find-loop key tree ( tree ∷ [] ) @@ -260,22 +259,22 @@ treeRightDown {n} {A} {_} {v1} .(node _ _ _ _) .(node _ _ _ _) (t-node x x₁ ti ti₁) = ti₁ -record FindCond {n : Level} {A : Set n} (C : ℕ → bt A → Set n) : Set (Level.suc n) where - field - c1 : {key key₁ : ℕ} {v1 : A } { tree tree₁ : bt A } → C key (node key₁ v1 tree tree₁) → key < key₁ → C key tree - c2 : {key key₁ : ℕ} {v1 : A } { tree tree₁ : bt A } → C key (node key₁ v1 tree tree₁) → key > key₁ → C key tree₁ - - -findP0 : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A ) → (stack : List (bt A)) - → {C : ℕ → bt A → Set n} → C key tree → FindCond C - → (next : (tree1 : bt A) → (stack : List (bt A)) → C key tree1 → bt-depth tree1 < bt-depth tree → t ) - → (exit : (tree1 : bt A) → (stack : List (bt A)) → C key tree1 - → (tree1 ≡ leaf ) ∨ ( node-key tree1 ≡ just key ) → t ) → t -findP0 key leaf st Pre _ _ exit = exit leaf st Pre (case1 refl) -findP0 key (node key₁ v1 tree tree₁) st Pre _ next exit with <-cmp key key₁ -findP0 key n st Pre e _ exit | tri≈ ¬a refl ¬c = exit n st Pre (case2 refl) -findP0 {n} {_} {A} key (node key₁ v1 tree tree₁) st Pre e next _ | tri< a ¬b ¬c = next tree (tree ∷ st) (FindCond.c1 e Pre a) depth-1< -findP0 key n@(node key₁ v1 tree tree₁) st Pre e next _ | tri> ¬a ¬b c = next tree₁ (tree₁ ∷ st) (FindCond.c2 e Pre c) depth-2< +-- record FindCond {n : Level} {A : Set n} (C : ℕ → bt A → Set n) : Set (Level.suc n) where +-- field +-- c1 : {key key₁ : ℕ} {v1 : A } { tree tree₁ : bt A } → C key (node key₁ v1 tree tree₁) → key < key₁ → C key tree +-- c2 : {key key₁ : ℕ} {v1 : A } { tree tree₁ : bt A } → C key (node key₁ v1 tree tree₁) → key > key₁ → C key tree₁ +-- +-- +-- findP0 : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A ) → (stack : List (bt A)) +-- → {C : ℕ → bt A → Set n} → C key tree → FindCond C +-- → (next : (tree1 : bt A) → (stack : List (bt A)) → C key tree1 → bt-depth tree1 < bt-depth tree → t ) +-- → (exit : (tree1 : bt A) → (stack : List (bt A)) → C key tree1 +-- → (tree1 ≡ leaf ) ∨ ( node-key tree1 ≡ just key ) → t ) → t +-- findP0 key leaf st Pre _ _ exit = exit leaf st Pre (case1 refl) +-- findP0 key (node key₁ v1 tree tree₁) st Pre _ next exit with <-cmp key key₁ +-- findP0 key n st Pre e _ exit | tri≈ ¬a refl ¬c = exit n st Pre (case2 refl) +-- findP0 {n} {_} {A} key (node key₁ v1 tree tree₁) st Pre e next _ | tri< a ¬b ¬c = next tree (tree ∷ st) (FindCond.c1 e Pre a) depth-1< +-- findP0 key n@(node key₁ v1 tree tree₁) st Pre e next _ | tri> ¬a ¬b c = next tree₁ (tree₁ ∷ st) (FindCond.c2 e Pre c) depth-2< findP : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree tree0 : bt A ) → (stack : List (bt A)) → treeInvariant tree ∧ stackInvariant key tree tree0 stack