PPP Exercises: Dictionaries in binary trees

1. Write a module that implements the following interface:
   

   interface NewDictionary
   import
     
     :Iter 
     :Order
     
   export 
     
     insertError, lookupError :Exception with :String end
     (* Exception handling for 'insert' und 'lookup'. *)
     
     
     T (Element, Key <:Ok) <:Ok
     (* Dictionary of elements of type 'Element'
        with keys of type 'Key'. *)
   
         
     Let Hooks(Element, Key <:Ok) = 
        Tuple
           getKey(:Element) :Key 
           keyOrder :Order.T(Key)
           fmtKey(:Key) :String
           fmtElement(:Element) :String
        end
     (* Set of elemantary function for dictionary handling. *)
   
     
     new(Element, Key <:Ok  hooks :Hooks(Element Key))
         :T(Element Key)
     (* Builds an empty dictionary being handled by functions 
        in tuple 'hooks'. *) 
   
       
     empty(Element, Key <:Ok  dict :T(Element Key)) :Bool
     (* Checks if 'dict' is empty. *)
   
       
     insert(Element, Key <:Ok  dict :T(Element Key)
            element :Element) :Ok
     (* Inserts an 'element' into 'dict'. If 'getKey(element)'
        already exists, then 'raise insertError with 
        ...fmtElement(element)'. *)
   
              
     enter(Element, Key <:Ok  dict :T(Element Key)
           element :Element) :Ok
     (* Inserts an 'element' into 'dict'. If the key retrieved by    
        'getKey(element)' already exists in 'dict', then override
        the former entry, so that the new 'element' is really inserted. *)
   
              
     lookup(Element, Key <:Ok  dict :T(Element Key)
            key :Key) :Element
     (* Searches for 'key' and returns the element found in 'dict'. 
        If search is unsuccesful 'raise lookupError with ...fmtKey(key)'. *)
   
     
     elements(Element, Key <:Ok  dict :T(Element Key))
              :Iter.T(Element)
     (* Returns an iteration over the elements of 'dict'. *) 
   
     
     create(Element, Key <:Ok  hooks :Hooks(Element Key)
            from :Iter.T(Element)) :T(Element Key)
       (* Creates a dictionary from the iteration 'from'.
          'hooks' contains functions for dictionary handling
          (see 'new'). *)
     
   end;
   

   Imagine this "dictionary" as a kind of database relation with elements that are identified by a key attribute.
   Implement the generic 'NewDictionary' using the module 'bTree :BTree'. For your module consider an extended type 'T' containing functions similar to those in 'Hooks'. Note that the function 'keyOrder' in Hooks is only used for creating a bTree.
2. Test the module by creating a new dictionary of persons consisting of name and age with keys of type ':String' which are actually the persons' names. Remember that you'll now need an instance of type ':Hooks'.

   Insert or enter serveral persons into your dictionary and try to look them up. Don't forget to test the dictionary on exceptions, too.

   Construct an iteration of Persons and make a dictionary out of it afterwards.

   Test this second dictionary by looking up persons.