Mercurial > hg > Members > Moririn
annotate hoareBinaryTree.agda @ 603:41e1c9e9718d
add fig
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 02 Nov 2021 19:32:10 +0900 |
| parents | 803c423c2855 |
| children | 2075785a124a |
| rev | line source |
|---|---|
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
1 module hoareBinaryTree where |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
2 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
3 open import Level renaming (zero to Z ; suc to succ) |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
4 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
5 open import Data.Nat hiding (compare) |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
6 open import Data.Nat.Properties as NatProp |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
7 open import Data.Maybe |
| 588 | 8 -- open import Data.Maybe.Properties |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
9 open import Data.Empty |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
10 open import Data.List |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
11 open import Data.Product |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
12 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
13 open import Function as F hiding (const) |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
14 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
15 open import Relation.Binary |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
16 open import Relation.Binary.PropositionalEquality |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
17 open import Relation.Nullary |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
18 open import logic |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
19 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
20 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
21 SingleLinkedStack = List |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
22 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
23 emptySingleLinkedStack : {n : Level } {Data : Set n} -> SingleLinkedStack Data |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
24 emptySingleLinkedStack = [] |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
25 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
26 clearSingleLinkedStack : {n m : Level } {Data : Set n} {t : Set m} -> SingleLinkedStack Data → ( SingleLinkedStack Data → t) → t |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
27 clearSingleLinkedStack [] cg = cg [] |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
28 clearSingleLinkedStack (x ∷ as) cg = cg [] |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
29 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
30 pushSingleLinkedStack : {n m : Level } {t : Set m } {Data : Set n} -> List Data -> Data -> (Code : SingleLinkedStack Data -> t) -> t |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
31 pushSingleLinkedStack stack datum next = next ( datum ∷ stack ) |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
32 |
| 587 | 33 |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
34 popSingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> t) -> t |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
35 popSingleLinkedStack [] cs = cs [] nothing |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
36 popSingleLinkedStack (data1 ∷ s) cs = cs s (just data1) |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
37 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
38 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
39 |
| 587 | 40 emptySigmaStack : {n : Level } { Data : Set n} → List Data |
| 41 emptySigmaStack = [] | |
| 42 | |
| 43 pushSigmaStack : {n m : Level} {d d2 : Set n} {t : Set m} → d2 → List d → (List (d × d2) → t) → t | |
| 44 pushSigmaStack {n} {m} {d} d2 st next = next (Data.List.zip (st) (d2 ∷ []) ) | |
| 45 | |
| 46 tt = pushSigmaStack 3 (true ∷ []) (λ st → st) | |
| 47 | |
| 588 | 48 _iso_ : {n : Level} {a : Set n} → ℕ → ℕ → Set |
| 49 d iso d' = (¬ (suc d ≤ d')) ∧ (¬ (suc d' ≤ d)) | |
| 50 | |
| 51 iso-intro : {n : Level} {a : Set n} {x y : ℕ} → ¬ (suc x ≤ y) → ¬ (suc y ≤ x) → _iso_ {n} {a} x y | |
| 52 iso-intro = λ z z₁ → record { proj1 = z ; proj2 = z₁ } | |
| 53 | |
| 54 | |
| 590 | 55 -- |
| 56 -- | |
| 57 -- no children , having left node , having right node , having both | |
| 58 -- | |
| 597 | 59 data bt {n : Level} (A : Set n) : Set n where |
| 600 | 60 L : bt A |
| 61 N : (key : ℕ) → | |
| 62 (ltree : bt A ) → (rtree : bt A ) → bt A | |
| 63 | |
| 64 data bt-path' {n : Level} (A : Set n) : Set n where | |
| 65 left : (bt A) → bt-path' A | |
| 66 right : (bt A) → bt-path' A | |
| 67 | |
| 68 | |
| 69 | |
| 70 tree->key : {n : Level} {A : Set n} → (tree : bt A) → ℕ | |
| 71 tree->key {n} L = zero | |
| 72 tree->key {n} (N key tree tree₁) = key | |
| 73 | |
| 601 | 74 node-ex : {n : Level} {A : Set n} → bt A |
| 75 node-ex {n} {A} = (N zero (L) (L)) | |
| 76 | |
| 77 ex : {n : Level} {A : Set n} → bt A | |
| 78 ex {n} {A} = (N {n} {A} 8 (N 6 (N 2 (N 1 L L) (N 3 L L)) (N 7 L L)) (N 9 L L)) | |
| 79 | |
| 80 exLR : {n : Level} {A : Set n} → bt A | |
| 81 exLR {n} {A} = (N {n} {A} 4 (N 2 L (N 3 L L)) (N 5 L L)) | |
| 82 | |
| 83 exRL : {n : Level} {A : Set n} → bt A | |
| 84 exRL {n} {A} = (N {n} {A} 3 L (N 5 (N 4 L L) L)) | |
| 85 | |
| 86 leaf-ex : {n : Level} {A : Set n} → bt A | |
| 87 leaf-ex {n} {A} = L | |
| 88 | |
| 89 | |
| 90 findLoopInv : {n m : Level} {A : Set n} {t : Set m} → (orig : bt A) → (modify : bt A ) | |
| 91 → (stack : List (bt-path' A)) → Set n | |
| 92 findLoopInv {n} {m} {A} {t} tree mtree [] = tree ≡ mtree | |
| 93 findLoopInv {n} {m} {A} {t} tree mtree (left L ∷ st) = mtree ≡ (L) | |
| 94 findLoopInv {n} {m} {A} {t} tree mtree (right L ∷ st) = mtree ≡ (L) | |
| 95 findLoopInv {n} {m} {A} {t} tree mtree (left (N key x x₁) ∷ st) = mtree ≡ x | |
| 96 findLoopInv {n} {m} {A} {t} tree mtree (right (N key x x₁) ∷ st) = mtree ≡ x₁ | |
| 97 | |
| 98 | |
| 99 hightMerge : {n m : Level} {A : Set n} {t : Set m} → (l r : ℕ) → (ℕ → t) → t | |
| 100 hightMerge lh rh next with <-cmp lh rh | |
| 101 hightMerge lh rh next | tri< a ¬b ¬c = next rh | |
| 102 hightMerge lh rh next | tri≈ ¬a b ¬c = next lh | |
| 103 hightMerge lh rh next | tri> ¬a ¬b c = next lh | |
| 104 | |
| 105 | |
| 106 isHightL : {n m : Level} {A : Set n} {t : Set m} → bt A → (ℕ → t) → t | |
| 107 isHightL L next = next zero | |
| 108 isHightL {n} {_} {A} (N key tree tree₁) next = isHightL tree λ x → next (suc x) | |
| 109 | |
| 110 isHightR : {n m : Level} {A : Set n} {t : Set m} → bt A → (ℕ → t) → t | |
| 111 isHightR L next = next zero | |
| 112 isHightR {n} {_} {A} (N key tree tree₁) next = isHightR tree₁ λ x → next (suc x) | |
| 113 | |
| 114 isHight : {n m : Level} {A : Set n} {t : Set m} → bt A → (ℕ → t) → t | |
| 115 isHight L next = next zero | |
| 116 isHight {n} {_} {A} tr@(N key tree tree₁) next = isHightL tr (λ lh → isHightR tr λ rh → hightMerge {n} {_} {A} (suc lh) (suc rh) next) | |
| 117 | |
| 118 treeHight : {n m : Level} {A : Set n} {t : Set m} → bt A → (ℕ → t) → t | |
| 119 treeHight L next = next zero | |
| 120 treeHight {n} {_} {A} (N key tree tree₁) next = isHight tree (λ lh → isHight tree₁ (λ rh → hightMerge {n} {_} {A} (lh) (rh) next)) | |
| 121 | |
| 122 rhight : {n : Level} {A : Set n} → bt A → ℕ | |
| 123 rhight L = zero | |
| 124 rhight (N key tree tree₁) with <-cmp (rhight tree) (rhight tree₁) | |
| 125 rhight (N key tree tree₁) | tri< a ¬b ¬c = suc (rhight tree₁) | |
| 126 rhight (N key tree tree₁) | tri≈ ¬a b ¬c = suc (rhight tree₁) | |
| 127 rhight (N key tree tree₁) | tri> ¬a ¬b c = suc (rhight tree) | |
| 128 | |
| 129 leaf≠node : {n : Level} {A : Set n} {a : ℕ} {l r : bt A} → ((N {n} {A} a l r) ≡ L) → ⊥ | |
| 130 leaf≠node () | |
| 131 | |
| 132 leafIsNoHight : {n : Level} {A : Set n} (tree : bt A) → tree ≡ L → (treeHight tree (λ x → x) ≡ 0) | |
| 133 leafIsNoHight L refl = refl | |
| 134 | |
| 135 | |
| 136 hight-tree : {n : Level} {A : Set n} {k : ℕ} {l r : bt A} → ℕ → (tree : bt A) → Set n | |
| 137 hight-tree zero tree = tree ≡ L | |
| 138 hight-tree {n} {A} {k} {l} {r} (suc h) tree = tree ≡ (N k l r) | |
| 139 | |
| 140 | |
| 141 hightIsNotLeaf : {n : Level} {A : Set n} (h : ℕ) → (tree : bt A) → (0 ≡ treeHight tree (λ x → x)) → (tree ≡ L) | |
| 142 hightIsNotLeaf h tree eq = {!!} | |
| 143 | |
| 144 -- leaf≡0 : {n : Level} {A : Set n} (tree : bt A) → (rhight tree ≡ 0) → tree ≡ L | |
| 145 -- leaf≡0 L _ = refl | |
| 146 | |
| 147 -- find-function sepalate "next", "loop" | |
| 148 find-hoare-next : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree mt : bt A ) → (st : List (bt-path' A)) → (findLoopInv {n} {m} {A} {t} tree mt st) | |
| 149 → (next : (nt : bt A) → (ns : List (bt-path' A)) → (findLoopInv {n} {m} {A} {t} tree nt ns) → t ) | |
| 150 → (exit : (nt : bt A) → (ns : List (bt-path' A)) → (nt ≡ L) ∨ (key ≡ tree->key nt) → t ) → t | |
| 151 find-hoare-next key leaf@(L) mt st eq _ exit = exit leaf st (case1 refl) | |
| 152 find-hoare-next key (N key₁ tree tree₁) mt st eq next exit with <-cmp key key₁ | |
| 153 find-hoare-next key node@(N key₁ tree tree₁) mt st eq _ exit | tri≈ ¬a b ¬c = exit node st (case2 b) | |
| 154 find-hoare-next key node@(N key₁ tree tree₁) mt st eq next _ | tri< a ¬b ¬c = next tree ((left node) ∷ st) refl | |
| 155 find-hoare-next key node@(N key₁ tree tree₁) mt st eq next _ | tri> ¬a ¬b c = next tree₁ ((right node) ∷ st) refl | |
| 156 | |
| 157 find-hoare-loop : {n m : Level} {A : Set n} {t : Set m} → (hight key : ℕ) → (tree mt : bt A ) → (st : List (bt-path' A)) → (findLoopInv {n} {m} {A} {t} tree mt st) | |
| 158 → (exit : (nt : bt A) → (ns : List (bt-path' A)) → (nt ≡ L) ∨ (key ≡ tree->key nt) → t) → t | |
| 159 find-hoare-loop zero key tree mt st eq exit with key ≟ (tree->key tree) | |
| 160 find-hoare-loop zero key tree mt st eq exit | yes p = exit tree st (case2 p) | |
| 161 find-hoare-loop zero key tree mt st eq exit | no ¬p = exit tree st (case1 {!!}) | |
| 162 | |
| 163 find-hoare-loop (suc h) key otr lf@(L) st eq exit = exit lf st (case1 refl) | |
| 164 find-hoare-loop (suc h) key otr tr@(N key₁ tree tree₁) st eq exit = find-hoare-next key otr tr st eq ((λ tr1 st1 eq → find-hoare-loop h key otr tr1 st1 eq exit)) exit | |
| 165 | |
| 600 | 166 |
| 167 | |
| 168 -- bt-find : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A ) → List (bt-path A) | |
| 169 -- → ( bt A → List (bt-path A) → t ) → t | |
| 170 -- bt-find {n} {m} {A} {t} key leaf@(L) stack exit = exit leaf stack | |
| 171 -- bt-find {n} {m} {A} {t} key (N key₁ tree tree₁) stack next with <-cmp key key₁ | |
| 172 -- bt-find {n} {m} {A} {t} key node@(N key₁ tree tree₁) stack exit | tri≈ ¬a b ¬c = exit node stack | |
| 173 -- bt-find {n} {m} {A} {t} key node@(N key₁ ltree rtree) stack next | tri< a ¬b ¬c = bt-find key ltree (bt-left key node ∷ stack) next | |
| 174 -- bt-find {n} {m} {A} {t} key node@(N key₁ ltree rtree) stack next | tri> ¬a ¬b c = bt-find key rtree (bt-right key node ∷ stack) next | |
| 175 | |
| 176 | |
| 177 -- bt-find' : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A ) → List (bt-path' A) → ( bt A → List (bt-path' A) → t ) → t | |
| 178 -- bt-find' key leaf@(L) stack exit = exit leaf stack | |
| 179 -- bt-find' key node@(N key1 lnode rnode) stack exit with <-cmp key key1 | |
| 180 -- bt-find' key node@(N key1 lnode rnode) stack exit | tri≈ ¬a b ¬c = exit node stack | |
| 181 -- bt-find' key node@(N key1 lnode rnode) stack next | tri< a ¬b ¬c = bt-find' key lnode ((left node) ∷ stack) next | |
| 182 -- bt-find' key node@(N key1 lnode rnode) stack next | tri> ¬a ¬b c = bt-find' key rnode ((right node) ∷ stack) next | |
| 597 | 183 |
| 184 | |
| 600 | 185 -- find-next : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A ) → List (bt-path' A) |
| 186 -- → (next : bt A → List (bt-path' A) → t ) → (exit : bt A → List (bt-path' A) → t ) → t | |
| 187 -- find-next key leaf@(L) st _ exit = exit leaf st | |
| 188 -- find-next key (N key₁ tree tree₁) st next exit with <-cmp key key₁ | |
| 189 -- find-next key node@(N key₁ tree tree₁) st _ exit | tri≈ ¬a b ¬c = exit node st | |
| 190 -- find-next key node@(N key₁ tree tree₁) st next _ | tri< a ¬b ¬c = next tree ((left node) ∷ st) | |
| 191 -- find-next key node@(N key₁ tree tree₁) st next _ | tri> ¬a ¬b c = next tree₁ ((right node) ∷ st) | |
| 192 | |
| 193 -- find-loop は bt-find' とだいたい一緒(induction してるくらい) | |
| 194 -- これも多分 Zコンビネータの一種? | |
| 195 -- loop で induction してる hight は現在の木の最大長より大きければよい(find-next が抜けきるため) | |
| 196 -- 逆に木の最大長より小さい(たどるルートより小さい)場合は途中経過の値が返る | |
| 197 | |
| 198 -- find-loop : {n m : Level} {A : Set n} {t : Set m} → (hight key : ℕ) → (tree : bt A ) → List (bt-path' A) → (exit : bt A → List (bt-path' A) → t) → t | |
| 199 -- find-loop zero key tree st exit = exit tree st | |
| 200 -- find-loop (suc h) key lf@(L) st exit = exit lf st | |
| 201 -- find-loop (suc h) key tr@(N key₁ tree tree₁) st exit = find-next key tr st ((λ tr1 st1 → find-loop h key tr1 st1 exit)) exit | |
| 202 | |
| 203 -- bt-replace : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → bt A → List (bt-path A) → (bt A → t ) → t | |
| 204 -- bt-replace {n} {m} {A} {t} ikey otree stack next = bt-replace0 otree where | |
| 205 -- bt-replace1 : bt A → List (bt-path A) → t | |
| 206 -- bt-replace1 tree [] = next tree | |
| 207 -- bt-replace1 node (bt-left key (L) ∷ stack) = bt-replace1 node stack | |
| 208 -- bt-replace1 node (bt-right key (L) ∷ stack) = bt-replace1 node stack | |
| 209 -- bt-replace1 node (bt-left key (N key₁ x x₁) ∷ stack) = bt-replace1 (N key₁ node x₁) stack | |
| 210 -- bt-replace1 node (bt-right key (N key₁ x x₁) ∷ stack) = bt-replace1 (N key₁ x node) stack | |
| 211 -- bt-replace0 : (tree : bt A) → t | |
| 212 -- bt-replace0 tree@(N key ltr rtr) = bt-replace1 tree stack -- find case | |
| 213 -- bt-replace0 (L) = {!!} | |
| 214 | |
| 215 | |
| 216 | |
| 217 -- bt-insert : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → bt A → (bt A → t ) → t | |
| 218 -- bt-insert {n} {m} {A} {t} key tree next = bt-find key tree [] (λ tr st → bt-replace key tr st (λ new → next new)) | |
| 219 | |
| 597 | 220 |
| 221 {-- | |
| 600 | 222 [ok] find でステップ毎にみている node と stack の top を一致させる |
| 223 [ok] find 中はnode と stack の top が一致する(pre は stack の中身がなく, post は stack の top とずれる) | |
| 224 | |
| 597 | 225 tree+stack≡tree は find 後の tree と stack をもって |
| 226 reverse した stack を使って find をチェックするかんじ? | |
| 227 --} | |
| 588 | 228 |
| 600 | 229 {-- |
| 230 tree+stack は tree と stack を受け取ってひとしさ(関係)を返すやつ | |
| 588 | 231 |
| 600 | 232 --} |
| 233 | |
| 234 -- tree+stack : {n m : Level} {A : Set n} {t : Set m} → (tree mtree : bt A ) | |
| 235 -- → (stack : List (bt-path A)) → Set n | |
| 236 -- tree+stack tree mtree [] = tree ≡ mtree -- fin case | |
| 237 -- tree+stack {n} {m} {A} {t} tree mtree@(L) (bt-left key x ∷ stack) = (mtree ≡ x) -- unknow case | |
| 238 -- tree+stack {n} {m} {A} {t} tree mtree@(L) (bt-right key x ∷ stack) = (mtree ≡ x) -- we nofound leaf's left, right node | |
| 239 -- tree+stack {n} {m} {A} {t} tree mtree@(N key1 ltree rtree) (bt-left key x ∷ stack) = (mtree ≡ x) ∧ (tree+stack {n} {m} {_} {t} tree ltree stack) -- correct case | |
| 240 -- tree+stack {n} {m} {A} {t} tree mtree@(N key₁ ltree rtree) (bt-right key x ∷ stack) = (mtree ≡ x) ∧ (tree+stack {n} {m} {_} {t} tree rtree stack) | |
| 241 | |
| 242 {-- | |
| 243 tree+stack | |
| 244 2. find loop → "top of reverse stack" ≡ "find route orig tree" | |
| 245 --} | |
| 246 | |
| 247 -- s+t≡t : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A ) → (stack : List (bt-path' {n} A)) → bt-find' key tree stack (λ mt st → s+t {n} {A} tree mt st) | |
| 248 -- s+t≡t {n} {m} {A} {t} key (L) [] = refl | |
| 249 -- s+t≡t {n} {m} {A} {t} key (L) (left x ∷ []) = refl | |
| 250 -- s+t≡t {n} {m} {A} {t} key (L) (left x ∷ x₁ ∷ stack) = refl | |
| 251 -- s+t≡t {n} {m} {A} {t} key (L) (right x ∷ []) = refl | |
| 252 -- s+t≡t {n} {m} {A} {t} key (L) (right x ∷ x₁ ∷ stack) = refl | |
| 253 -- s+t≡t {n} {m} {A} {t} key (N key₁ tree tree₁) [] with <-cmp key key₁ | |
| 254 -- s+t≡t {n} {m} {A} {t} key (N key₁ tree tree₁) [] | tri≈ ¬a b ¬c = refl | |
| 255 -- s+t≡t {n} {m} {A} {t} key (N key₁ tree tree₁) [] | tri< a ¬b ¬c = {!!} | |
| 256 -- s+t≡t {n} {m} {A} {t} key (N key₁ tree tree₁) [] | tri> ¬a ¬b c = {!!} | |
| 257 -- s+t≡t {n} {m} {A} {t} key (N key₁ tree tree₁) (x ∷ stack) = {!!} | |
| 258 | |
| 597 | 259 |
| 260 | |
| 600 | 261 -- s+t : {n : Level} {A : Set n} → (tree mtree : bt A ) → (stack : List (bt-path' {n} A)) → Set n |
| 262 -- s+t tree mtree [] = tree ≡ mtree | |
| 263 -- s+t tree mtree (x ∷ []) = tree ≡ mtree | |
| 264 -- s+t tr@(L) mt (left x ∷ x₁ ∷ stack) = tr ≡ mt | |
| 265 -- s+t {n} {A} tr@(N key tree tree₁) mt (left x ∷ x₁ ∷ stack) = (mt ≡ x) ∧ (s+t {n} {A} tree (path2tree x₁) stack) | |
| 266 -- s+t tr@(L) mt (right x ∷ x₁ ∷ stack) = tr ≡ mt | |
| 267 -- s+t {n} {A} tr@(N key tree tree₁) mt (right x ∷ x₁ ∷ stack) = (mt ≡ x) ∧ (s+t {n} {A} tree₁ (path2tree x₁) stack) | |
| 268 | |
| 269 -- data treeType {n : Level} (A : Set n) : Set n where | |
| 270 -- leaf-t : treeType A | |
| 271 -- node-t : treeType A | |
| 272 | |
| 273 -- isType : {n : Level} {A : Set n} → bt A → treeType A | |
| 274 -- isType (L) = leaf-t | |
| 275 -- isType (N key tree tree₁) = node-t | |
| 276 | |
| 277 -- data findState : Set where | |
| 278 -- s1 : findState | |
| 279 -- s2 : findState | |
| 280 -- sf : findState | |
| 281 | |
| 282 -- findStateP : {n : Level} {A : Set n} → findState → ℕ → bt A → (mnode : bt A) → List (bt-path' A) → Set n | |
| 283 -- findStateP s1 key node mnode stack = stack ≡ [] | |
| 284 -- findStateP s2 key node mnode stack = (s+t node mnode (reverse stack)) | |
| 285 -- findStateP sf key node mnode stack = (key ≡ (tree->key mnode)) ∨ ((isType mnode) ≡ leaf-t) | |
| 286 | |
| 287 -- findStartPwP : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree mtree : bt A ) → (findStateP s1 key tree mtree [] → t) → t | |
| 288 -- findStartPwP key tree mtree next = next refl | |
| 289 | |
| 290 | |
| 291 | |
| 292 -- findLoopPwP : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree mtree : bt A ) → (st : List (bt-path' A)) | |
| 293 -- → (findStateP s2 key tree mtree st) | |
| 294 -- → (next : (tr : bt A) → (st : List (bt-path' A)) → (findStateP s2 key tree mtree st) → t) | |
| 295 -- → (exit : (tr : bt A) → (st : List (bt-path' A)) → (findStateP sf key tree mtree st) → t ) → t | |
| 296 -- findLoopPwP key tree (L) [] state next exit = exit tree [] (case2 refl) | |
| 297 -- findLoopPwP key tree (N key₁ mtree mtree₁) [] state next exit = next tree [] {!!} | |
| 298 -- findLoopPwP key tree mtree (x ∷ []) state next exit = {!!} | |
| 299 -- findLoopPwP key tree (L) (x ∷ x₁ ∷ stack) state next exit = {!!} | |
| 300 -- findLoopPwP key tree (N key₁ mtree mtree₁) (left x ∷ x₁ ∷ stack) state next exit = | |
| 301 -- next {!!} {!!} {!!} | |
| 302 -- findLoopPwP key tree (N key₁ mtree mtree₁) (right x ∷ x₁ ∷ stack) state next exit = {!!} | |
| 303 | |
| 304 | |
| 305 -- -- tree+stack' {n} {m} {A} {t} (N key ltree rtree) mtree@(N key₁ lmtree rmtree) (x ∷ stack) with <-cmp key key₁ | |
| 306 -- tree+stack' {n} {m} {A} {t} tt@(N key ltree rtree) mt@(N key₁ lmtree rmtree) (x ∷ stack) | tri≈ ¬a b ¬c = tt ≡ mt | |
| 307 -- tree+stack' {n} {m} {A} {t} tt@(N key ltree rtree) mt@(N key₁ lmtree rmtree) st@(x ∷ stack) | tri< a ¬b ¬c = (mt ≡ x) ∧ tree+stack' {n} {m} {A} {t} tt lmtree (mt ∷ st) | |
| 308 -- tree+stack' {n} {m} {A} {t} tt@(N key ltree rtree) mt@(N key₁ lmtree rmtree) st@(x ∷ stack) | tri> ¬a ¬b c = (mt ≡ x) ∧ tree+stack' {n} {m} {A} {t} tt rmtree (mt ∷ st) | |
| 309 | |
| 310 | |
| 311 | |
| 312 -- tree+stack≡tree : {n m : Level} {A : Set n} {t : Set m} → (tree mtree : bt A ) | |
| 313 -- → (stack : List (bt-path A )) → tree+stack {_} {m} {_} {t} tree mtree (reverse stack) | |
| 314 -- tree+stack≡tree tree (L key) stack = {!!} | |
| 315 -- tree+stack≡tree tree (N key rtree ltree) stack = {!!} | |
| 316 | |
| 597 | 317 |
| 318 | |
| 319 -- loop はきっと start, running, stop の3つに分けて考えるといいよね | |
| 320 {-- find status | |
| 321 1. find start → stack empty | |
| 322 2. find loop → stack Not empty ∧ node Not empty | |
| 323 or "in reverse stack" ≡ "find route orig tree" | |
| 324 3. find fin → "stack Not empty ∧ current node is leaf" | |
| 325 or "stack Not empty ∧ current node key ≡ find-key" | |
| 326 --} | |
| 327 | |
| 600 | 328 -- find-step : {n m : Level} {A : Set n} {t : Set m} → (key : ℕ) → (tree : bt A) → (stack : List (bt A)) |
| 329 -- → (next : (mtree : bt A) → (stack1 : List (bt A)) → (tree+stack' {n} {m} {A} {t} tree mtree stack1 ) → t) | |
| 330 -- → (exit : (mtree : bt A) → List (bt A) → (tree ≡ L (tree->key mtree )) ∨ (key ≡ (tree->key mtree)) → t) → t | |
| 331 -- find-step {n} {m} {A} {t} key (L) stack next exit = exit (L) stack (case1 refl) | |
| 332 -- find-step {n} {m} {A} {t} key (N key₁ node node₁) stack next exit with <-cmp key key₁ | |
| 333 -- find-step {n} {m} {A} {t} key (N key₁ node node₁) stack next exit | tri≈ ¬a b ¬c = exit (N key₁ node node₁) stack (case2 b) | |
| 334 -- find-step {n} {m} {A} {t} key (N key₁ node node₁) stack next exit | tri< a ¬b ¬c = next node stack {!!} | |
| 335 -- find-step {n} {m} {A} {t} key (N key₁ node node₁) stack next exit | tri> ¬a ¬b c = next node₁ stack {!!} | |
| 336 | |
| 337 | |
| 338 -- find-check : {n m : Level} {A : Set n} {t : Set m} → (k : ℕ) → (tree : bt A ) | |
| 339 -- → (stack : List (bt-path A )) → bt-find k tree [] (λ mtree mstack → tree+stack {_} {m} {_} {t} tree mtree (reverse mstack)) | |
| 340 -- find-check {n} {m} {A} {t} key (L) [] = refl | |
| 341 -- find-check {n} {m} {A} {t} key (N key₁ tree tree₁) [] with <-cmp key key₁ | |
| 342 -- find-check {n} {m} {A} {t} key (N key₁ tree tree₁) [] | tri≈ ¬a b ¬c = refl | |
| 343 -- find-check {n} {m} {A} {t} key (N key₁ tree tree₁) [] | tri< a ¬b ¬c = {!!} | |
| 344 -- find-check {n} {m} {A} {t} key (N key₁ tree tree₁) [] | tri> ¬a ¬b c = {!!} | |
| 345 -- find-check {n} {m} {A} {t} key tree (x ∷ stack) = {!!} | |
| 597 | 346 |
| 347 | |
| 600 | 348 -- module ts where |
| 349 -- tbt : {n : Level} {A : Set n} → bt A | |
| 350 -- tbt {n} {A} = N {n} {A} 8 (N 6 (N 2 (L) (L)) (L)) (L) | |
| 597 | 351 |
| 600 | 352 -- find : {n : Level} {A : Set n} → ℕ → List (bt-path A) |
| 353 -- find {n} {A} key = bt-find key tbt [] (λ x y → y ) | |
| 354 | |
| 355 -- find' : {n : Level} {A : Set n} → ℕ → bt A | |
| 356 -- find' {n} {A} key = bt-find' key tbt [] (λ x y → x ) | |
| 597 | 357 |
| 600 | 358 -- rep : {n m : Level} {A : Set n} {t : Set m} → ℕ → bt A |
| 359 -- rep {n} {m} {A} {t} key = bt-find {n} {_} {A} key tbt [] (λ tr st → bt-replace key tr st (λ mtr → mtr)) | |
| 597 | 360 |
| 600 | 361 -- ins : {n m : Level} {A : Set n} {t : Set m} → ℕ → bt A |
| 362 -- ins {n} {m} {A} {t} key = bt-insert key tbt (λ tr → tr) | |
| 597 | 363 |
| 600 | 364 -- test : {n m : Level} {A : Set n} {t : Set m} (key : ℕ) |
| 365 -- → bt-find {n} {_} {A} {_} key tbt [] (λ x y → tree+stack {n} {m} {A} {t} tbt x y) | |
| 366 -- test key = {!!} | |
| 367 -- -- | |
| 597 | 368 -- |
| 369 -- no children , having left node , having right node , having both | |
| 370 -- | |
| 600 | 371 data bt' {n : Level} (A : Set n) : (key : ℕ) → Set n where -- (a : Setn) |
| 372 bt'-leaf : (key : ℕ) → bt' A key | |
| 373 bt'-node : { l r : ℕ } → (key : ℕ) → (value : A) → | |
| 374 bt' A l → bt' A r → l ≤ key → key ≤ r → bt' A key | |
| 597 | 375 |
| 376 -- data bt'-path {n : Level} (A : Set n) : ℕ → Set n where -- (a : Setn) | |
| 377 -- bt'-left : (key : ℕ) → {left-key : ℕ} → (bt' A left-key ) → (key ≤ left-key) → bt'-path A left-key | |
| 378 -- bt'-right : (key : ℕ) → {right-key : ℕ} → (bt' A right-key ) → (right-key ≤ key) → bt'-path A right-key | |
| 379 | |
| 380 | |
| 381 -- test = bt'-left {Z} {ℕ} 3 {5} (bt'-leaf 5) (s≤s (s≤s (s≤s z≤n))) | |
| 588 | 382 |
| 594 | 383 |
| 384 | |
| 385 -- reverse1 : List (bt' A tn) → List (bt' A tn) → List (bt' A tn) | |
| 600 | 386 -- reverse1 [] s1 = s1+ |
| 594 | 387 -- reverse1 (x ∷ s0) s1 with reverse1 s0 (x ∷ s1) |
| 388 -- ... | as = {!!} | |
| 389 | |
| 390 | |
| 596 | 391 |
| 597 | 392 -- bt-find' : {n m : Level} {A : Set n} {t : Set m} {tn : ℕ} → (key : ℕ) → (tree : bt' A tn ) → List (bt'-path A tn) |
| 393 -- → ( {key1 : ℕ } → bt' A key1 → List (bt'-path A key1) → t ) → t | |
| 394 -- bt-find' key tr@(bt'-leaf key₁) stack next = next tr stack -- no key found | |
| 395 -- bt-find' key (bt'-node key₁ value tree tree₁ x x₁) stack next with <-cmp key key₁ | |
| 396 -- bt-find' key tr@(bt'-node {l} {r} key₁ value tree tree₁ x x₁) stack next | tri< a ¬b ¬c = | |
| 397 -- bt-find' key tree ( (bt'-left key {!!} ({!!}) ) ∷ {!!}) next | |
| 398 -- bt-find' key found@(bt'-node key₁ value tree tree₁ x x₁) stack next | tri≈ ¬a b ¬c = next found stack | |
| 399 -- bt-find' key tr@(bt'-node key₁ value tree tree₁ x x₁) stack next | tri> ¬a ¬b c = | |
| 400 -- bt-find' key tree ( (bt'-right key {!!} {!!} ) ∷ {!!}) next | |
| 588 | 401 |
| 594 | 402 |
| 597 | 403 -- bt-find-step : {n m : Level} {A : Set n} {t : Set m} {tn : ℕ} → (key : ℕ) → (tree : bt' A tn ) → List (bt'-path A tn) |
| 404 -- → ( {key1 : ℕ } → bt' A key1 → List (bt'-path A key1) → t ) → t | |
| 405 -- bt-find-step key tr@(bt'-leaf key₁) stack exit = exit tr stack -- no key found | |
| 406 -- bt-find-step key (bt'-node key₁ value tree tree₁ x x₁) stack next = {!!} | |
| 594 | 407 |
| 597 | 408 -- a<sa : { a : ℕ } → a < suc a |
| 409 -- a<sa {zero} = s≤s z≤n | |
| 410 -- a<sa {suc a} = s≤s a<sa | |
| 588 | 411 |
| 597 | 412 -- a≤sa : { a : ℕ } → a ≤ suc a |
| 413 -- a≤sa {zero} = z≤n | |
| 414 -- a≤sa {suc a} = s≤s a≤sa | |
| 592 | 415 |
| 597 | 416 -- pa<a : { a : ℕ } → pred (suc a) < suc a |
| 417 -- pa<a {zero} = s≤s z≤n | |
| 418 -- pa<a {suc a} = s≤s pa<a | |
| 590 | 419 |
| 597 | 420 -- bt-replace' : {n m : Level} {A : Set n} {t : Set m} {tn : ℕ} → (key : ℕ) → (value : A ) → (tree : bt' A tn ) → List (bt'-path A {!!}) |
| 421 -- → ({key1 : ℕ } → bt' A key1 → t ) → t | |
| 422 -- bt-replace' {n} {m} {A} {t} {tn} key value node stack next = bt-replace1 tn node where | |
| 423 -- bt-replace0 : {tn : ℕ } (node : bt' A tn ) → List (bt'-path A {!!}) → t | |
| 424 -- bt-replace0 node [] = next node | |
| 425 -- bt-replace0 node (bt'-left key (bt'-leaf key₁) x₁ ∷ stack) = {!!} | |
| 426 -- bt-replace0 {tn} node (bt'-left key (bt'-node key₁ value x x₂ x₃ x₄) x₁ ∷ stack) = bt-replace0 {key₁} (bt'-node key₁ value node x₂ {!!} x₄ ) stack | |
| 427 -- bt-replace0 node (bt'-right key x x₁ ∷ stack) = {!!} | |
| 428 -- bt-replace1 : (tn : ℕ ) (tree : bt' A tn ) → t | |
| 429 -- bt-replace1 tn (bt'-leaf key0) = bt-replace0 (bt'-node tn value | |
| 430 -- (bt'-leaf (pred tn)) (bt'-leaf (suc tn) ) (≤⇒pred≤ ≤-refl) a≤sa) stack | |
| 431 -- bt-replace1 tn (bt'-node key value node node₁ x x₁) = bt-replace0 (bt'-node key value node node₁ x x₁) stack | |
| 588 | 432 |
| 597 | 433 -- tree->key : {n : Level} {tn : ℕ} → (A : Set n) → (tree : bt' A tn ) → ℕ |
| 434 -- tree->key {n} {.key} (A) (bt'-leaf key) = key | |
| 435 -- tree->key {n} {.key} (A) (bt'-node key value tree tree₁ x x₁) = key | |
| 593 | 436 |
| 437 | |
| 597 | 438 -- bt-find'-assert1 : {n m : Level} {A : Set n} {t : Set m} {tn : ℕ} → (tree : bt' A tn ) → Set n |
| 439 -- bt-find'-assert1 {n} {m} {A} {t} {tn} tree = (key : ℕ) → (val : A) → bt-find' key tree [] (λ tree1 stack → key ≡ (tree->key A tree1)) | |
| 593 | 440 |
| 441 | |
| 597 | 442 -- bt-replace-hoare : {n m : Level} {A : Set n} {t : Set m} {tn : ℕ} → (key : ℕ) → (value : A ) → (tree : bt' A tn ) |
| 443 -- → (pre : bt-find'-assert1 {n} {m} {A} {t} tree → bt-replace' {!!} {!!} {!!} {!!} {!!}) → t | |
| 444 -- bt-replace-hoare key value tree stack = {!!} | |
| 593 | 445 |
| 588 | 446 |
| 447 | |
| 448 -- find'-support : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → (tree : bt' {n} {a} ) → SingleLinkedStack (bt' {n} {a} ) → ( (bt' {n} {a} ) → SingleLinkedStack (bt' {n} {a} ) → Maybe (Σ ℕ (λ d' → _iso_ {n} {a} d d')) → t ) → t | |
| 449 | |
| 450 -- find'-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key leaf@(bt'-leaf x) st cg = cg leaf st nothing | |
| 451 -- find'-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (bt'-node d tree₁ tree₂ x x₁) st cg with <-cmp key d | |
| 452 -- find'-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key node@(bt'-node d tree₁ tree₂ x x₁) st cg | tri≈ ¬a b ¬c = cg node st (just (d , iso-intro {n} {a} ¬a ¬c)) | |
| 453 | |
| 454 -- find'-support {n} {m} {a} {t} key node@(bt'-node ⦃ nl ⦄ ⦃ l' ⦄ ⦃ nu ⦄ ⦃ u' ⦄ d L R x x₁) st cg | tri< a₁ ¬b ¬c = | |
| 455 -- pushSingleLinkedStack st node | |
| 456 -- (λ st2 → find'-support {n} {m} {a} {t} {{l'}} {{d}} key L st2 cg) | |
| 457 | |
| 458 -- find'-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key node@(bt'-node ⦃ ll ⦄ ⦃ ll' ⦄ ⦃ lr ⦄ ⦃ lr' ⦄ d L R x x₁) st cg | tri> ¬a ¬b c = pushSingleLinkedStack st node | |
| 459 -- (λ st2 → find'-support {n} {m} {a} {t} {{d}} {{lr'}} key R st2 cg) | |
| 460 | |
| 461 | |
| 462 | |
| 597 | 463 -- lleaf : {n : Level} {a : Set n} → bt {n} {a} |
| 600 | 464 -- lleaf = (L ⦃ 0 ⦄ ⦃ 3 ⦄ z≤n) |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
465 |
| 597 | 466 -- lleaf1 : {n : Level} {A : Set n} → (0 < 3) → (a : A) → (d : ℕ ) → bt' {n} A d |
| 467 -- lleaf1 0<3 a d = bt'-leaf d | |
| 588 | 468 |
| 597 | 469 -- test-node1 : bt' ℕ 3 |
| 470 -- test-node1 = bt'-node (3) 3 (bt'-leaf 2) (bt'-leaf 4) (s≤s (s≤s {!!})) (s≤s (s≤s (s≤s {!!}))) | |
| 588 | 471 |
| 472 | |
| 597 | 473 -- rleaf : {n : Level} {a : Set n} → bt {n} {a} |
| 600 | 474 -- rleaf = (L ⦃ 3 ⦄ ⦃ 3 ⦄ (s≤s (s≤s (s≤s z≤n)))) |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
475 |
| 597 | 476 -- test-node : {n : Level} {a : Set n} → bt {n} {a} |
| 600 | 477 -- test-node {n} {a} = (N ⦃ 0 ⦄ ⦃ 0 ⦄ ⦃ 4 ⦄ ⦃ 4 ⦄ 3 lleaf rleaf z≤n ≤-refl ) |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
478 |
| 597 | 479 -- -- stt : {n m : Level} {a : Set n} {t : Set m} → {!!} |
| 480 -- -- stt {n} {m} {a} {t} = pushSingleLinkedStack [] (test-node ) (λ st → pushSingleLinkedStack st lleaf (λ st2 → st2) ) | |
| 587 | 481 |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
482 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
483 |
| 597 | 484 -- -- search の {{ l }} {{ u }} はその時みている node の 大小。 l が小さく u が大きい |
| 485 -- -- ここでは d が現在の node のkey値なので比較後のsearch では値が変わる | |
| 486 -- bt-search : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → bt {n} {a} → (Maybe (Σ ℕ (λ d' → _iso_ {n} {a} d d')) → t ) → t | |
| 600 | 487 -- bt-search {n} {m} {a} {t} key (L x) cg = cg nothing |
| 488 -- bt-search {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N ⦃ ll ⦄ ⦃ l' ⦄ ⦃ uu ⦄ ⦃ u' ⦄ d L R x x₁) cg with <-cmp key d | |
| 489 -- bt-search {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N ⦃ ll ⦄ ⦃ l' ⦄ ⦃ uu ⦄ ⦃ u' ⦄ d L R x x₁) cg | tri< a₁ ¬b ¬c = bt-search ⦃ l' ⦄ ⦃ d ⦄ key L cg | |
| 490 -- bt-search {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N ⦃ ll ⦄ ⦃ l' ⦄ ⦃ uu ⦄ ⦃ u' ⦄ d L R x x₁) cg | tri≈ ¬a b ¬c = cg (just (d , iso-intro {n} {a} ¬a ¬c)) | |
| 491 -- bt-search {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N ⦃ ll ⦄ ⦃ l' ⦄ ⦃ uu ⦄ ⦃ u' ⦄ d L R x x₁) cg | tri> ¬a ¬b c = bt-search ⦃ d ⦄ ⦃ u' ⦄ key R cg | |
| 587 | 492 |
| 600 | 493 -- -- bt-search {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N ⦃ l ⦄ ⦃ l' ⦄ ⦃ u ⦄ ⦃ u' ⦄ d L R x x₁) cg | tri< a₁ ¬b ¬c = ? -- bt-search ⦃ l' ⦄ ⦃ d ⦄ key L cg |
| 494 -- -- bt-search {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N d L R x x₁) cg | tri≈ ¬a b ¬c = cg (just (d , iso-intro {n} {a} ¬a ¬c)) | |
| 495 -- -- bt-search {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N ⦃ l ⦄ ⦃ l' ⦄ ⦃ u ⦄ ⦃ u' ⦄ d L R x x₁) cg | tri> ¬a ¬b c = bt-search ⦃ d ⦄ ⦃ u' ⦄ key R cg | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
496 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
497 |
| 597 | 498 -- -- この辺の test を書くときは型を考えるのがやや面倒なので先に動作を書いてから型を ? から補間するとよさそう |
| 499 -- bt-search-test : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (x : (x₁ : Maybe (Σ ℕ (λ z → ((x₂ : 4 ≤ z) → ⊥) ∧ ((x₂ : suc z ≤ 3) → ⊥)))) → t) → t | |
| 500 -- bt-search-test {n} {m} {a} {t} = bt-search {n} {m} {a} {t} ⦃ zero ⦄ ⦃ 4 ⦄ 3 test-node | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
501 |
| 597 | 502 -- bt-search-test-bad : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (x : (x₁ : Maybe (Σ ℕ (λ z → ((x₂ : 8 ≤ z) → ⊥) ∧ ((x₂ : suc z ≤ 7) → ⊥)))) → t) → t |
| 503 -- bt-search-test-bad {n} {m} {a} {t} = bt-search {n} {m} {a} {t} ⦃ zero ⦄ ⦃ 4 ⦄ 7 test-node | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
504 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
505 |
| 597 | 506 -- -- up-some : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ {d : ℕ} → (Maybe (Σ ℕ (λ d' → _iso_ {n} {a} d d'))) → (Maybe ℕ) |
| 507 -- -- up-some (just (fst , snd)) = just fst | |
| 508 -- -- up-some nothing = nothing | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
509 |
| 597 | 510 -- search-lem : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (key : ℕ) → (tree : bt {n} {a} ) → bt-search ⦃ l ⦄ ⦃ u ⦄ key tree (λ gdata → gdata ≡ gdata) |
| 600 | 511 -- search-lem {n} {m} {a} {t} key (L x) = refl |
| 512 -- search-lem {n} {m} {a} {t} key (N d tree₁ tree₂ x x₁) with <-cmp key d | |
| 513 -- search-lem {n} {m} {a} {t} key (N ⦃ ll ⦄ ⦃ ll' ⦄ ⦃ lr ⦄ ⦃ lr' ⦄ d tree₁ tree₂ x x₁) | tri< lt ¬eq ¬gt = search-lem {n} {m} {a} {t} ⦃ ll' ⦄ ⦃ d ⦄ key tree₁ | |
| 514 -- search-lem {n} {m} {a} {t} key (N d tree₁ tree₂ x x₁) | tri≈ ¬lt eq ¬gt = refl | |
| 515 -- search-lem {n} {m} {a} {t} key (N ⦃ ll ⦄ ⦃ ll' ⦄ ⦃ lr ⦄ ⦃ lr' ⦄ d tree₁ tree₂ x x₁) | tri> ¬lt ¬eq gt = search-lem {n} {m} {a} {t} ⦃ d ⦄ ⦃ lr' ⦄ key tree₂ | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
516 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
517 |
| 597 | 518 -- -- bt-find |
| 519 -- find-support : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → (tree : bt {n} {a} ) → SingleLinkedStack (bt {n} {a} ) → ( (bt {n} {a} ) → SingleLinkedStack (bt {n} {a} ) → Maybe (Σ ℕ (λ d' → _iso_ {n} {a} d d')) → t ) → t | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
520 |
| 600 | 521 -- find-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key leaf@(L x) st cg = cg leaf st nothing |
| 522 -- find-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key (N d tree₁ tree₂ x x₁) st cg with <-cmp key d | |
| 523 -- find-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key node@(N d tree₁ tree₂ x x₁) st cg | tri≈ ¬a b ¬c = cg node st (just (d , iso-intro {n} {a} ¬a ¬c)) | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
524 |
| 600 | 525 -- find-support {n} {m} {a} {t} key node@(N ⦃ nl ⦄ ⦃ l' ⦄ ⦃ nu ⦄ ⦃ u' ⦄ d L R x x₁) st cg | tri< a₁ ¬b ¬c = |
| 597 | 526 -- pushSingleLinkedStack st node |
| 527 -- (λ st2 → find-support {n} {m} {a} {t} {{l'}} {{d}} key L st2 cg) | |
| 587 | 528 |
| 600 | 529 -- find-support {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key node@(N ⦃ ll ⦄ ⦃ ll' ⦄ ⦃ lr ⦄ ⦃ lr' ⦄ d L R x x₁) st cg | tri> ¬a ¬b c = pushSingleLinkedStack st node |
| 597 | 530 -- (λ st2 → find-support {n} {m} {a} {t} {{d}} {{lr'}} key R st2 cg) |
| 587 | 531 |
| 597 | 532 -- bt-find : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → (tree : bt {n} {a} ) → SingleLinkedStack (bt {n} {a} ) → ( (bt {n} {a} ) → SingleLinkedStack (bt {n} {a} ) → Maybe (Σ ℕ (λ d' → _iso_ {n} {a} d d')) → t ) → t |
| 533 -- bt-find {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ key tr st cg = clearSingleLinkedStack st | |
| 534 -- (λ cst → find-support ⦃ l ⦄ ⦃ u ⦄ key tr cst cg) | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
535 |
| 597 | 536 -- find-test : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → List bt -- ? |
| 537 -- find-test {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ = bt-find {n} {_} {a} ⦃ l ⦄ ⦃ u ⦄ 3 test-node [] (λ tt st ad → st) | |
| 538 -- {-- result | |
| 539 -- λ {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ → | |
| 600 | 540 -- N 3 (L z≤n) (L (s≤s (s≤s (s≤s z≤n)))) z≤n (s≤s (s≤s (s≤s (s≤s z≤n)))) ∷ [] |
| 597 | 541 -- --} |
| 587 | 542 |
| 597 | 543 -- find-lem : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → (tree : bt {n} {a}) → (st : List (bt {n} {a})) → find-support {{l}} {{u}} d tree st (λ ta st ad → ta ≡ ta) |
| 600 | 544 -- find-lem d (L x) st = refl |
| 545 -- find-lem d (N d₁ tree tree₁ x x₁) st with <-cmp d d₁ | |
| 546 -- find-lem d (N d₁ tree tree₁ x x₁) st | tri≈ ¬a b ¬c = refl | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
547 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
548 |
| 600 | 549 -- find-lem d (N d₁ tree tree₁ x x₁) st | tri< a ¬b ¬c with tri< a ¬b ¬c |
| 550 -- find-lem {n} {m} {a} {t} {{l}} {{u}} d (N d₁ tree tree₁ x x₁) st | tri< lt ¬b ¬c | tri< a₁ ¬b₁ ¬c₁ = find-lem {n} {m} {a} {t} {{l}} {{u}} d tree {!!} | |
| 551 -- find-lem d (N d₁ tree tree₁ x x₁) st | tri< a ¬b ¬c | tri≈ ¬a b ¬c₁ = {!!} | |
| 552 -- find-lem d (N d₁ tree tree₁ x x₁) st | tri< a ¬b ¬c | tri> ¬a ¬b₁ c = {!!} | |
| 587 | 553 |
| 600 | 554 -- find-lem d (N d₁ tree tree₁ x x₁) st | tri> ¬a ¬b c = {!!} |
| 587 | 555 |
| 597 | 556 -- bt-singleton :{n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → ( (bt {n} {a} ) → t ) → t |
| 600 | 557 -- bt-singleton {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ d cg = cg (N ⦃ 0 ⦄ ⦃ 0 ⦄ ⦃ d ⦄ ⦃ d ⦄ d (L ⦃ 0 ⦄ ⦃ d ⦄ z≤n ) (L ⦃ d ⦄ ⦃ d ⦄ ≤-refl) z≤n ≤-refl) |
| 587 | 558 |
| 559 | |
| 597 | 560 -- singleton-test : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → bt -- ? |
| 561 -- singleton-test {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ = bt-singleton {n} {_} {a} ⦃ l ⦄ ⦃ u ⦄ 10 λ x → x | |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
562 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
563 |
| 597 | 564 -- replace-helper : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (tree : bt {n} {a} ) → SingleLinkedStack (bt {n} {a} ) → ( (bt {n} {a} ) → t ) → t |
| 565 -- replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ tree [] cg = cg tree | |
| 600 | 566 -- replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ tree@(N d L R x₁ x₂) (L x ∷ st) cg = replace-helper ⦃ l ⦄ ⦃ u ⦄ tree st cg -- Unknown Case |
| 567 -- replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ (N d tree tree₁ x₁ x₂) (N d₁ x x₃ x₄ x₅ ∷ st) cg with <-cmp d d₁ | |
| 568 -- replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ subt@(N d tree tree₁ x₁ x₂) (N d₁ x x₃ x₄ x₅ ∷ st) cg | tri< a₁ ¬b ¬c = replace-helper ⦃ l ⦄ ⦃ u ⦄ (N d₁ subt x₃ x₄ x₅) st cg | |
| 569 -- replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ subt@(N d tree tree₁ x₁ x₂) (N d₁ x x₃ x₄ x₅ ∷ st) cg | tri≈ ¬a b ¬c = replace-helper ⦃ l ⦄ ⦃ u ⦄ (N d₁ subt x₃ x₄ x₅) st cg | |
| 570 -- replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ subt@(N d tree tree₁ x₁ x₂) (N d₁ x x₃ x₄ x₅ ∷ st) cg | tri> ¬a ¬b c = replace-helper ⦃ l ⦄ ⦃ u ⦄ (N d₁ x₃ subt x₄ x₅) st cg | |
| 597 | 571 -- replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ tree (x ∷ st) cg = replace-helper ⦃ l ⦄ ⦃ u ⦄ tree st cg -- Unknown Case |
| 587 | 572 |
| 573 | |
| 574 | |
| 597 | 575 -- bt-replace : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ |
| 576 -- → (d : ℕ) → (bt {n} {a} ) → SingleLinkedStack (bt {n} {a} ) | |
| 577 -- → Maybe (Σ ℕ (λ d' → _iso_ {n} {a} d d')) → ( (bt {n} {a} ) → t ) → t | |
| 600 | 578 -- bt-replace {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ d tree st eqP cg = replace-helper {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ ((N ⦃ 0 ⦄ ⦃ 0 ⦄ ⦃ d ⦄ ⦃ d ⦄ d (L ⦃ 0 ⦄ ⦃ d ⦄ z≤n ) (L ⦃ d ⦄ ⦃ d ⦄ ≤-refl) z≤n ≤-refl)) st cg |
|
586
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
579 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
580 |
|
0ddfa505d612
isolate search function problem, and add hoareBinaryTree.agda.
ryokka
parents:
diff
changeset
|
581 |
| 597 | 582 -- -- 証明に insert がはいっててほしい |
| 583 -- bt-insert : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → (tree : bt {n} {a}) | |
| 584 -- → ((bt {n} {a}) → t) → t | |
| 587 | 585 |
| 597 | 586 -- bt-insert {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ d tree cg = bt-find {n} {_} {a} ⦃ l ⦄ ⦃ u ⦄ d tree [] (λ tt st ad → bt-replace ⦃ l ⦄ ⦃ u ⦄ d tt st ad cg ) |
| 587 | 587 |
| 597 | 588 -- pickKey : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (tree : bt {n} {a}) → Maybe ℕ |
| 600 | 589 -- pickKey (L x) = nothing |
| 590 -- pickKey (N d tree tree₁ x x₁) = just d | |
| 587 | 591 |
| 597 | 592 -- insert-test : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → bt -- ? |
| 593 -- insert-test {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ = bt-insert {n} {_} {a} ⦃ l ⦄ ⦃ u ⦄ 1 test-node λ x → x | |
| 587 | 594 |
| 597 | 595 -- insert-test-l : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → bt -- ? |
| 596 -- insert-test-l {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ = bt-insert {n} {_} {a} ⦃ l ⦄ ⦃ u ⦄ 1 (lleaf) λ x → x | |
| 587 | 597 |
| 598 | |
| 597 | 599 -- insert-lem : {n m : Level} {a : Set n} {t : Set m} ⦃ l u : ℕ ⦄ → (d : ℕ) → (tree : bt {n} {a}) |
| 600 -- → bt-insert {n} {_} {a} ⦃ l ⦄ ⦃ u ⦄ d tree (λ tree1 → bt-find ⦃ l ⦄ ⦃ u ⦄ d tree1 [] | |
| 601 -- (λ tt st ad → (pickKey {n} {m} {a} {t} ⦃ l ⦄ ⦃ u ⦄ tt) ≡ just d ) ) | |
| 587 | 602 |
| 603 | |
| 600 | 604 -- insert-lem d (L x) with <-cmp d d -- bt-insert d (L x) (λ tree1 → {!!}) |
| 605 -- insert-lem d (L x) | tri< a ¬b ¬c = ⊥-elim (¬b refl) | |
| 606 -- insert-lem d (L x) | tri≈ ¬a b ¬c = refl | |
| 607 -- insert-lem d (L x) | tri> ¬a ¬b c = ⊥-elim (¬b refl) | |
| 608 -- insert-lem d (N d₁ tree tree₁ x x₁) with <-cmp d d₁ | |
| 609 -- -- bt-insert d (N d₁ tree tree₁ x x₁) (λ tree1 → {!!}) | |
| 610 -- insert-lem d (N d₁ tree tree₁ x x₁) | tri≈ ¬a b ¬c with <-cmp d d | |
| 611 -- insert-lem d (N d₁ tree tree₁ x x₁) | tri≈ ¬a b ¬c | tri< a ¬b ¬c₁ = ⊥-elim (¬b refl) | |
| 612 -- insert-lem d (N d₁ tree tree₁ x x₁) | tri≈ ¬a b ¬c | tri≈ ¬a₁ b₁ ¬c₁ = refl | |
| 613 -- insert-lem d (N d₁ tree tree₁ x x₁) | tri≈ ¬a b ¬c | tri> ¬a₁ ¬b c = ⊥-elim (¬b refl) | |
| 587 | 614 |
| 600 | 615 -- insert-lem d (N d₁ tree tree₁ x x₁) | tri< a ¬b ¬c = {!!} |
| 597 | 616 -- where |
| 600 | 617 -- lem-helper : find-support ⦃ {!!} ⦄ ⦃ {!!} ⦄ d tree (N d₁ tree tree₁ x x₁ ∷ []) (λ tt₁ st ad → replace-helper ⦃ {!!} ⦄ ⦃ {!!} ⦄ (N ⦃ {!!} ⦄ ⦃ {!!} ⦄ ⦃ {!!} ⦄ ⦃ {!!} ⦄ d (L ⦃ 0 ⦄ ⦃ d ⦄ z≤n) (L ⦃ {!!} ⦄ ⦃ {!!} ⦄ (≤-reflexive refl)) z≤n (≤-reflexive refl)) st (λ tree1 → find-support ⦃ {!!} ⦄ ⦃ {!!} ⦄ d tree1 [] (λ tt₂ st₁ ad₁ → pickKey {{!!}} {{!!}} {{!!}} {{!!}} ⦃ {!!} ⦄ ⦃ {!!} ⦄ tt₂ ≡ just d))) |
| 597 | 618 -- lem-helper = {!!} |
| 587 | 619 |
| 600 | 620 -- insert-lem d (N d₁ tree tree₁ x x₁) | tri> ¬a ¬b c = {!!} |
| 587 | 621 |