home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 5 / 05.iso / a / a009 / 6.ddi / SAMPLE.LIF / DICT.PRG < prev    next >
Encoding:
Text File  |  1991-04-14  |  4.5 KB  |  237 lines
  1. /***
  2. *    Dict.prg
  3. *    Keyed dictionary utility.
  4. *    Copyright (c) 1991 Nantucket Corp.  All rights reserved.
  5. *
  6. *
  7. *    Uses an array to contain list of "dictionary" entries.
  8. *    Each entry consists of a character key and a value of any type.
  9. *    New keys and values can be entered, and existing values can be
  10. *    retrieved based on their key.
  11. *
  12. *
  13. *    DictNew()  <--    <aDictionary>
  14. *
  15. *        Creates and returns an empty dictionary.
  16. *
  17. *
  18. *    DictAt( <aDictionary>, <cKey> )  <--  <xValue>
  19. *
  20. *        Returns the value associated with <xKey> in dictionary,
  21. *        NIL if <xKey> is not present in dictionary.
  22. *
  23. *
  24. *    DictPut( <aDictionary>, <cKey>, <xValue> )    <--  <xValue>
  25. *
  26. *        Associates <cKey> to <cValue> in <aDictionary>. Returns
  27. *        <xValue>.
  28. *
  29. *
  30. *    DictPutPair( <aDictionary>, <aPair> )  <-- <aPair>
  31. *
  32. *        Adds <aPair> to <aDictionary>. Returns <aPair>.
  33. *        <aPair> is a key/value pair: { <cKey>, <xValue> }.
  34. *
  35. *
  36. *    DictRemove( <aDictionary>, <cKey> )  <-- <aDictionary>
  37. *
  38. *        Removes the key/value pair for <cKey>.
  39. *        Returns <aDictionary>.
  40. *
  41. *
  42. *    DictEval( <aDictionary>, <bBlock> )  <-- <aDictionary>
  43. *
  44. *        Evaluates <bBlock> against each <cKey>/<xValue> pair in
  45. *        dictionary. Pair is passed to block as { <cKey>, <xValue> }
  46. *        (pair array indexes defined in "dict.ch").
  47. *        Returns <aDictionary>.
  48. *
  49. *
  50. *    Notes:
  51. *        Compile with /n/w/a/m
  52. *
  53. *        Key values must all be type 'C', case is significant.
  54. *
  55. *        These dictionaries are useful if you want to keep a list
  56. *        of keyed values without using a database. Since they're
  57. *        arrays, you can hange onto them with any variable or
  58. *        array element (handy for keeping track of multiple "cargo"
  59. *        items, for example). If you have lots of values, though,
  60. *        a database/index is usually more appropriate.
  61. *
  62. */
  63.  
  64.  
  65. #include "dict.ch"
  66.  
  67.  
  68. // hash machinery
  69. #define KEY_HASH(key)        ( Bin2W(key) + Bin2W( SubStr(Trim(key), -2) ) )
  70. #define HASH_VAL(key, size) ( ( KEY_HASH(key) % size ) + 1 )
  71.  
  72. #define DEFAULT_HASH_SIZE        31
  73. #define MAX_ARRAY_LEN            4096
  74.  
  75.  
  76.  
  77. /***
  78. *    DictNew()
  79. */
  80.  
  81. FUNCTION DictNew()
  82.  
  83.     LOCAL i
  84.     LOCAL dict
  85.  
  86.     dict := Array(DEFAULT_HASH_SIZE)
  87.  
  88.     FOR i := 1 to DEFAULT_HASH_SIZE
  89.         dict[i] := {}
  90.     NEXT
  91.  
  92.     RETURN ( dict )
  93.  
  94.  
  95.  
  96. /***
  97. *    DictAt()
  98. *    Return the value for a particular key.
  99. */
  100.  
  101. FUNCTION DictAt( dict, key )
  102.  
  103.     LOCAL bucket
  104.     LOCAL i
  105.  
  106.     bucket := dict[ HASH_VAL(key, Len(dict)) ]
  107.     i := AScan( bucket, { |assoc| assoc[ DI_KEY ] == key } )
  108.  
  109.     if ( i == 0 )
  110.         RETURN (NIL)
  111.     end
  112.  
  113.     RETURN ( bucket[i][DI_VAL] )
  114.  
  115.  
  116.  
  117. /***
  118. *    DictPut()
  119. *    Add or replace the value for a particular key.
  120. *    Returns the value being added.
  121. */
  122.  
  123. FUNCTION DictPut( dict, key, val )
  124.  
  125.     DictPutPair( dict, {key, val} )
  126.  
  127.     RETURN (val)
  128.  
  129.  
  130.  
  131. /***
  132. *    DictPutPair()
  133. *    Add or replace key/value pair for a particular key.
  134. *    Returns the pair being added.
  135. */
  136.  
  137. FUNCTION DictPutPair( dict, pair )
  138.  
  139.     LOCAL bucket
  140.     LOCAL key
  141.     LOCAL i
  142.  
  143.     key := pair[ DI_KEY ]
  144.  
  145.     bucket := dict[ HASH_VAL(key, Len(dict)) ]
  146.     i := AScan( bucket, { |assoc| assoc[ DI_KEY ] == key } )
  147.  
  148.     if ( i == 0 )
  149.         AAdd( bucket, pair )
  150.         i := Len( bucket )
  151.     else
  152.         bucket[i] := pair
  153.     end
  154.  
  155.     if ( i > 3 .and. Len(dict) < MAX_ARRAY_LEN )
  156.         // this bucket is big, grow dict
  157.         DictResize(dict)
  158.     end
  159.  
  160.     RETURN ( pair )
  161.  
  162.  
  163.  
  164. /***
  165. *    DictRemove()
  166. *    Remove the key/value pair for a particular key.
  167. *    Returns a reference to the dictionary.
  168. */
  169.  
  170. FUNCTION DictRemove( dict, key )
  171.  
  172.     LOCAL bucket
  173.     LOCAL i
  174.  
  175.     bucket := dict[ HASH_VAL(key, Len(dict)) ]
  176.     i := AScan( bucket, { |assoc| assoc[ DI_KEY ] == key } )
  177.  
  178.     if ( i <> 0 )
  179.         ADel( bucket, i )
  180.         ASize( bucket, Len(bucket) - 1 )
  181.     end
  182.  
  183.     RETURN ( dict )
  184.  
  185.  
  186.  
  187. /***
  188. *    DictEval()
  189. *    Evaluate block against each pair in dictionary. Pair is passed to
  190. *    block.
  191. *    Returns reference to dict.
  192. */
  193.  
  194. FUNCTION DictEval( dict, block )
  195.  
  196.     AEval( dict, ;
  197.         { |bucket| AEval( bucket, { |assoc| Eval(block, assoc) } ) } )
  198.  
  199.     RETURN ( dict )
  200.  
  201.  
  202.  
  203. /***
  204. *    DictResize()
  205. *
  206. *    Service. Grows dict hash table.
  207. *
  208. *    NOTE: rehashes, invalidating any direct indexes into dict held
  209. *    by caller across this call.
  210. */
  211.  
  212. STATIC FUNCTION DictResize( dict )
  213.  
  214.     LOCAL old
  215.     LOCAL size
  216.     LOCAL i
  217.  
  218.     // make copy of old dict
  219.     old := Array( Len(dict) )
  220.     ACopy( dict, old )
  221.  
  222.     // resize and clear dict
  223.     size := Min( Len(dict) * 4 - 1, MAX_ARRAY_LEN )
  224.     ASize( dict, size )
  225.  
  226.     FOR i := 1 to size
  227.         dict[i] := {}
  228.     NEXT
  229.  
  230.     // rehash pairs into dict
  231.     AEval( old, ;
  232.         { |bucket| AEval( bucket, ;
  233.             { |assoc| DictPutPair( dict, assoc ) } ) } )
  234.  
  235.     RETURN ( dict )
  236.  
  237.