DEFINITION MODULE @@module@@;

(* Generic Patricia Trie Template *)

(* ---------------------------------------------------------------------------
 * This template is expanded by the M2R10 template engine utility. Expansion
 * can be invoked from within a compiling source file using the MAKE pragma:
 * <* MAKE = "m2te PatriciaTrie module:'FooTrie' component:'FooRecord'" *>
 * IMPORT FooTrie;
 * ------------------------------------------------------------------------ *)


FROM Collections IMPORT Capacity, Status;


CONST

(* ---------------------------------------------------------------------------
 * Maximum trie size
 * ------------------------------------------------------------------------ *)

    maximumCapacity = 1014*1024*1024;  (* more than 1 billion entries *)


(* ---------------------------------------------------------------------------
 * Synonyms for status codes
 * ------------------------------------------------------------------------ *)

    invalidTrie = invalidCollection;
    entryLimitReached = collectionFull;


TYPE

(* ---------------------------------------------------------------------------
 * Opaque handle type:  @@module@@
 * ------------------------------------------------------------------------ *)

    @@module@@ = OPAQUE;

    ValueType = @@component@@;


(* ---------------------------------------------------------------------------
 * Trie Action Handler type
 * ---------------------------------------------------------------------------
 *
 * Action handlers are  called by function forEachEntryDo  to report key/value
 * pairs that match the search criteria passed to the forEachEntryDo function.
 *
 * Handlers take two arguments <key> and <value>:
 *
 *  o  <key> is a key that matches the search criteria
 *  o  <value> is the value stored for key <key> in the searched trie *)

    ActionHandler =
        PROCEDURE ( (* key *) ARRAY OF CHAR, (* value *) ValueType );


(* ---------------------------------------------------------------------------
 * function:  @@module@@.new ( status )
 * ---------------------------------------------------------------------------
 *
 * Creates  and  returns  a  new trie object.  Returns NIL  if the trie object
 * could not be created.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE new ( VAR status : Status ) : @@module@@;


(* ---------------------------------------------------------------------------
 * function:  @@module@@.storeEntry( trie, key, value, status )
 * ---------------------------------------------------------------------------
 *
 * Stores <value> for <key>  in <trie>.  The new entry is added  by reference,
 * NO data is copied.  The function fails  if NIL is passed in  for <trie>  or
 * <key> or if a zero length string is passed in for <key>.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE storeEntry ( trie   : @@module@@;
                       key    : ARRAY OF CHAR;
                       value  : ValueType;
                   VAR status : Status );


(* ---------------------------------------------------------------------------
 * function:  @@module@@.replaceEntry( trie, key, value, status )
 * ---------------------------------------------------------------------------
 *
 * Searches for  an entry in <trie>  whose key  exactly  matches <key> and re-
 * places its value with <value>.  The function fails  if NIL is passed in for
 * <trie> or <key>,  or  if a  zero length string  is passed in for <key>,  or
 * if no entry is found in <trie> with a key that exactly matches <key>.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE replaceEntry ( trie   : @@module@@;
                         key    : ARRAY OF CHAR;
                         value  : ValueType;
                     VAR status : Status );


(* ---------------------------------------------------------------------------
 * function:  @@module@@.valueForKey( trie, key, status )
 * ---------------------------------------------------------------------------
 *
 * Returns the value stored for <key< in <trie>.  If no value for <key> exists
 * in <trie> or if NIL is passed in for <trie> then NIL is returned.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE valueForKey ( trie   : @@module@@;
                        key    : ARRAY OF CHAR;
                    VAR status : Status ) : ValueType;


(* ---------------------------------------------------------------------------
 * function:  @@module@@.forEachEntryDo( trie, prefix, action, status )
 * ---------------------------------------------------------------------------
 *
 * Traverses <trie>  visiting all entries whose keys have a common prefix with
 * <prefix>  and invokes the  action handler  passed in for <action>  for each
 * entry visited.  If an  empty string  is passed in  for <prefix>  then every
 * entry in <trie> will be visited.  The function returns  the total number of
 * entries visited.  The function fails  and returns zero  if NIL is passed in
 * in for <trie> or <action>.
 *
 * Each time <action> is called,  the following parameters are passed to it:
 *
 *  o  first parameter :  the key of the visited node
 *  o  second parameter:  the value of the visited node
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE forEachEntryDo ( trie   : @@module@@;
                           prefix : ARRAY OF CHAR;
                           action : ActionHandler;
                       VAR status : Status ) : ValueType;


(* ---------------------------------------------------------------------------
 * function:  @@module@@.numberOfEntriesWithPrefix( trie, prefix )
 * ---------------------------------------------------------------------------
 *
 * Returns  the  number of entries  stored in <trie>  whose keys have a common
 * prefix with <prefix>.  If an  empty string is passed in for <prefix>,  then
 * the  total number  of entries  stored in <trie>  is returned.  The function
 * fails and returns zero if NULL is passed in for <trie> or <key>. *)

PROCEDURE numberOfEntriesWithPrefix ( trie   : @@module@@;
                                      prefix : ARRAY OF CHAR ) : Capacity;


(* ---------------------------------------------------------------------------
 * function:  @@module@@.removeEntry( trie, key, status )
 * ---------------------------------------------------------------------------
 *
 * Removes the entry stored for <key> from <trie>.  The function fails  if NIL
 * is passed in for <trie> or if no entry for <key> is stored in <trie>.
 *
 * The status of the operation is passed back in <status>. *)

PROCEDURE removeEntry ( trie   : @@module@@;
                        key    : ARRAY OF CHAR;
                    VAR status : Status );


(* ---------------------------------------------------------------------------
 * function:  @@module@@.capacity( trie )
 * ---------------------------------------------------------------------------
 *
 * Returns the total capacity of trie <trie>,  returns  zero  if NIL is passed
 * in for <trie>. *)

PROCEDURE capacity ( trie : @@module@@ ) : Capacity;


(* ---------------------------------------------------------------------------
 * function:  @@module@@.entryCount( trie )
 * ---------------------------------------------------------------------------
 *
 * Returns the number of entries stored in trie <trie>,  returns  zero  if NIL
 * is passed in for <trie>. *)

PROCEDURE entryCount ( trie : @@module@@ ) : Capacity;


(* ---------------------------------------------------------------------------
 * function:  @@module@@.isResizable( trie )
 * ---------------------------------------------------------------------------
 *
 * Returns TRUE  if the  capacity of <trie>  can change  after <trie> has been
 * instatiated,  returns FALSE otherwise. *)

PROCEDURE isResizable ( trie : @@module@@ ) : BOOLEAN;


(* ---------------------------------------------------------------------------
 * function:  @@module@@.dispose( trie )
 * ---------------------------------------------------------------------------
 *
 * Disposes of tree object <trie> and returns NIL. *)

PROCEDURE dispose ( trie : @@module@@ ) : @@module@@;


END @@module@@.