record TreeMethods {n m : Level } {a : Set n } {t : Set m } (treeImpl : Set n ) : Set (m Level.!$\sqcup$! n) where
  field
    putImpl : treeImpl !$\rightarrow$! a !$\rightarrow$! (treeImpl !$\rightarrow$! t) !$\rightarrow$! t
    getImpl  : treeImpl !$\rightarrow$! (treeImpl !$\rightarrow$! Maybe a !$\rightarrow$! t) !$\rightarrow$! t
open TreeMethods

record Tree  {n m : Level } {a : Set n } {t : Set m } (treeImpl : Set n ) : Set (m Level.!$\sqcup$! n) where
  field
    tree : treeImpl
    treeMethods : TreeMethods {n} {m} {a} {t} treeImpl
  putTree : a !$\rightarrow$! (Tree treeImpl !$\rightarrow$! t) !$\rightarrow$! t
  putTree d next = putImpl (treeMethods ) tree d (\t1 !$\rightarrow$! next (record {tree = t1 ; treeMethods = treeMethods} ))
  getTree : (Tree treeImpl !$\rightarrow$! Maybe a !$\rightarrow$! t) !$\rightarrow$! t
  getTree next = getImpl (treeMethods ) tree (\t1 d !$\rightarrow$! next (record {tree = t1 ; treeMethods = treeMethods} ) d )
open Tree

record RedBlackTree {n m : Level } {t : Set m} (a k : Set n) : Set (m Level.!$\sqcup$! n) where
  field
    root : Maybe (Node a k)
    nodeStack : SingleLinkedStack  (Node a k)
    compare : k !$\rightarrow$! k !$\rightarrow$! CompareResult {n}
open RedBlackTree