|
5
|
1 record TreeMethods {n m : Level } {a : Set n } {t : Set m } (treeImpl : Set n ) : Set (m Level.!$\sqcup$! n) where
|
|
0
|
2 field
|
|
5
|
3 putImpl : treeImpl !$\rightarrow$! a !$\rightarrow$! (treeImpl !$\rightarrow$! t) !$\rightarrow$! t
|
|
|
4 getImpl : treeImpl !$\rightarrow$! (treeImpl !$\rightarrow$! Maybe a !$\rightarrow$! t) !$\rightarrow$! t
|
|
0
|
5 open TreeMethods
|
|
|
6
|
|
5
|
7 record Tree {n m : Level } {a : Set n } {t : Set m } (treeImpl : Set n ) : Set (m Level.!$\sqcup$! n) where
|
|
0
|
8 field
|
|
|
9 tree : treeImpl
|
|
|
10 treeMethods : TreeMethods {n} {m} {a} {t} treeImpl
|
|
5
|
11 putTree : a !$\rightarrow$! (Tree treeImpl !$\rightarrow$! t) !$\rightarrow$! t
|
|
|
12 putTree d next = putImpl (treeMethods ) tree d (\t1 !$\rightarrow$! next (record {tree = t1 ; treeMethods = treeMethods} ))
|
|
|
13 getTree : (Tree treeImpl !$\rightarrow$! Maybe a !$\rightarrow$! t) !$\rightarrow$! t
|
|
|
14 getTree next = getImpl (treeMethods ) tree (\t1 d !$\rightarrow$! next (record {tree = t1 ; treeMethods = treeMethods} ) d )
|
|
0
|
15 open Tree
|
|
|
16
|
|
5
|
17 record RedBlackTree {n m : Level } {t : Set m} (a k : Set n) : Set (m Level.!$\sqcup$! n) where
|
|
0
|
18 field
|
|
|
19 root : Maybe (Node a k)
|
|
|
20 nodeStack : SingleLinkedStack (Node a k)
|
|
5
|
21 compare : k !$\rightarrow$! k !$\rightarrow$! CompareResult {n}
|
|
0
|
22 open RedBlackTree
|
