home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 5 / 05.iso / a / a066 / 1.img / DICT.PRG < prev    next >
Encoding:
Text File  |  1992-03-20  |  2.8 KB  |  140 lines
  1. /*
  2.     dict.prg
  3.  
  4.  
  5.     Copyright (c) 1991 John F Kaster and Anton van Straaten
  6.  
  7.         Portions copyright (c) 1991 Nantucket Corp
  8.  
  9.     Bibliography:
  10.         Compiler Design in C - Allen Holub
  11.         Actor User's Manual  - The Whitewater Group
  12. */
  13.  
  14.  
  15. #include "class(y).ch"
  16. #include "gen.ch"
  17.  
  18.  
  19. #define     DEFAULT_HASH_SIZE   31
  20. #define     MAX_BUCKETS         4096
  21.  
  22.  
  23.  
  24. create class Dictionary
  25.     instvar     buckets
  26.  
  27.     method      grow
  28.     method      getBucket
  29.  
  30. export:
  31.     method      at = get        // can't use 'at' coz it's reserved by Clipper
  32.     method      get
  33.     method      put
  34.     method      putAssoc
  35.     method      remove
  36.     method      do
  37. endclass
  38.  
  39.  
  40. constructor new(nHashSize)
  41.     local i
  42.  
  43.     ifnil nHashSize := DEFAULT_HASH_SIZE
  44.  
  45.     ::buckets := array(nHashSize)
  46.  
  47.     for i := 1 to nHashSize
  48.         ::buckets[i] := {}
  49.     next
  50. return
  51.  
  52.  
  53.  
  54. method function getBucket(cKey, nAssoc)
  55.     local bucket := ::buckets[ CsyHashVal(cKey, len(::buckets)) ]
  56.     local nPos   := nAssoc := 0
  57.  
  58.     for nPos := 1 to len(bucket)
  59.         if bucket[nPos]:key == cKey
  60.             nAssoc := nPos
  61.             exit
  62.         end
  63.     next
  64.  
  65. return bucket
  66.  
  67.  
  68. method function get(cKey)
  69.     local nAssoc
  70.     local bucket := ::getBucket(cKey, @nAssoc)
  71. return if (nAssoc == 0, nil, bucket[nAssoc]:value)
  72.  
  73.  
  74. method procedure putAssoc(assoc)
  75.     local nAssoc
  76.     local bucket := ::getBucket(assoc:key, @nAssoc)
  77.  
  78.     if nAssoc == 0
  79.         AAdd( bucket, assoc )
  80.         nAssoc := len( bucket )
  81.     else
  82.         bucket[nAssoc] := assoc
  83.     end
  84.  
  85.     if nAssoc > 3 .and. len(::buckets) < MAX_BUCKETS
  86.         ::grow()        // this bucket is big, grow dict
  87.     end
  88.  
  89. return 
  90.  
  91.  
  92. method procedure put(cKey, value)
  93.     local assoc := Association():new(cKey, value)
  94.     ::putAssoc(assoc)
  95. return
  96.  
  97.  
  98. method procedure grow
  99.     local i
  100.     local nSize   := min( len(::buckets) * 4 - 1, MAX_BUCKETS )
  101.     local newDict := Dictionary():new(nSize)
  102.  
  103.     // rehash pairs into dict
  104.     AEval( ::buckets, ;
  105.         { |bucket| AEval( bucket, ;
  106.             { |assoc| newDict:putAssoc( assoc ) } ) } )
  107.  
  108.     ::buckets := newDict:buckets
  109.  
  110. return
  111.  
  112.  
  113. method procedure remove(cKey)
  114.     local nAssoc
  115.     local bucket := ::getBucket(cKey, @nAssoc)
  116.  
  117.     if nAssoc <> 0
  118.         ADel( bucket, nAssoc )
  119.         ASize( bucket, len(bucket) - 1 )
  120.     end
  121. return 
  122.  
  123.  
  124. method procedure do(block)
  125.     local nBucket, nAssoc, bucket
  126.     local buckets  := ::buckets
  127.     local nBuckets := len(buckets)
  128.  
  129.     // don't use aeval because of performance
  130.     for nBucket := 1 to nBuckets
  131.         bucket := buckets[nBucket]
  132.         for nAssoc := 1 to len(bucket)
  133.             eval(block, bucket[nAssoc], nAssoc)
  134.         next
  135.     next
  136. return
  137.  
  138.  
  139. // eof dict.prg
  140.