home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 3 / CDPDIII.bin / pd / programming / gnusmalltalk / dictionary.st < prev    next >
Text File  |  1992-02-15  |  11KB  |  399 lines
  1. "======================================================================
  2. |
  3. |   Dictionary Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1990, 1991, 1992 Free Software Foundation, Inc.
  11. | Written by Steve Byrne.
  12. |
  13. | This file is part of GNU Smalltalk.
  14. |
  15. | GNU Smalltalk is free software; you can redistribute it and/or modify it
  16. | under the terms of the GNU General Public License as published by the Free
  17. | Software Foundation; either version 1, or (at your option) any later version.
  18. | 
  19. | GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20. | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21. | FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22. | details.
  23. | 
  24. | You should have received a copy of the GNU General Public License along with
  25. | GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26. | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27. |
  28.  ======================================================================"
  29.  
  30.  
  31. "
  32. |     Change Log
  33. | ============================================================================
  34. | Author       Date       Change 
  35. | sbb         28 Jul 91      Fixed #= to check argument class.  Also fixed
  36. |              printing and storing to use cascaded messages.
  37. |
  38. | sbb         16 Mar 91      Class creation now separate statement.
  39. |
  40. | sbb         16 Feb 91      Override the #new method from builtins when this file
  41. |              is loaded so that subclasses of Dictionary have a
  42. |              proper #new method instead of the built-in one that
  43. |              only creates Dictionary instances.
  44. |
  45. | sbb         21 Sep 90      Changed printOn: to print the associations directly.
  46. |
  47. | sbyrne      6 May 90      Fixed grow method to preserve associations in use in
  48. |              the dictionary instead of making new ones.  This
  49. |              should be faster, and doesn't break compiled methods
  50. |              that reference global variables when Smalltalk grows.
  51. |
  52. | sbyrne     24 Apr 90      Fix at:ifAbsent: to deal with failure better (and be
  53. |              a tad more efficient).  Kudos (or BarNone's,
  54. |              depending on preference) to Andy Valencia.
  55. |
  56. | sbyrne      7 Apr 90      Modified at:put: to resuse the existing Association
  57. |              if there is one, rather than create a new one all the
  58. |              time.  This was causing lossage when setting global
  59. |              variables in Smalltalk that previous usages weren't
  60. |              being changed.
  61. |
  62. | sbyrne     25 Apr 89      created.
  63. |
  64. "
  65.  
  66. Set variableSubclass: #Dictionary
  67.     instanceVariableNames: ''
  68.     classVariableNames: ''
  69.     poolDictionaries: ''
  70.     category: nil
  71. !
  72.  
  73. Dictionary comment: 
  74. 'I implement a dictionary, which is an object that is indexed by
  75. unique objects (typcially instances of Symbol), and associates another
  76. object with that index.  I use the equality operator = to determine
  77. equality of indices.' !
  78.  
  79. "### The initblocks variable should not be globally visible, I think"
  80. "This is a HACK HACK HACK.  We want to reference the InitBlocks global variable
  81. from within some methods in System Dictionary.  However, after this file
  82. redefines at:put: from the built-in one, and until UndefinedObject.st is 
  83. loaded, defining isNil for nil, at:put: for dictionaries does not work
  84. properly.  So we do it here.  The basic problem is that InitBlocks should
  85. maybe be kept elsewhere, and not be globally visible."
  86. Smalltalk at: #InitBlocks put: nil!
  87.  
  88. !Dictionary class methodsFor: 'instance creation'!
  89.  
  90. new
  91.     "Builtins defines a #new method, so that during bootstrap there is a way
  92.      to create dictionaries.  Unfortunately, this #new method only creates
  93.      dictionaries, so subclasses when trying to use this method, lose big.
  94.      This fixes the problem."
  95.     ^self new: 32
  96. ! !
  97.  
  98.  
  99.  
  100. !Dictionary methodsFor: 'accessing'!
  101.  
  102. add: anAssociation
  103.     | index |
  104.     index _ self findKeyIndex: anAssociation key.
  105.     (self basicAt: index) isNil
  106.     ifTrue: [ tally _ tally + 1].
  107.     self basicAt: index put: anAssociation.
  108.     ^anAssociation
  109. !
  110.  
  111. at: key put: value
  112.     | index assoc |
  113.     index _ self findKeyIndex: key.
  114.     (assoc _ self basicAt: index) isNil
  115.     ifTrue: [ self basicAt: index
  116.                put: (Association key: key value: value).
  117.           tally _ tally + 1 ]
  118.     ifFalse: [ assoc value: value ].
  119.     ^value
  120. !
  121.  
  122. at: key
  123.     ^self at: key ifAbsent: [ ^self error: 'key not found' ]
  124. !
  125.  
  126. at: key ifAbsent: aBlock
  127.     | assoc |
  128.     assoc _ self basicAt: (self findKeyIndex: key).
  129.     assoc isNil
  130.             ifTrue: [ ^aBlock value ]
  131.             ifFalse: [ ^assoc value ]
  132. !
  133.     
  134. associationAt: key
  135.     ^self associationAt: key ifAbsent: [ ^self error: 'key not found' ]
  136. !
  137.  
  138. associationAt: key ifAbsent: aBlock
  139.     | index assoc|
  140.     index _ self findKeyIndex: key.
  141.     assoc _ self basicAt: index.
  142.     assoc isNil ifTrue: [ ^aBlock value ]
  143.                 ifFalse: [ ^assoc ]
  144. !
  145.  
  146. keyAtValue: value ifAbsent: exceptionBlock
  147.     self associationsDo:
  148.         [ :assoc | value = assoc value
  149.                  ifTrue: [ ^assoc key ] ].
  150.     ^exceptionBlock value
  151. !
  152.  
  153. keyAtValue: value
  154.     ^self keyAtValue: value ifAbsent: []
  155. !
  156.  
  157. keys
  158.     | aSet |
  159.     aSet _ Set new: tally.
  160.     self keysDo: [ :aKey | aSet add: aKey ].
  161.     ^aSet
  162. !
  163.  
  164. values
  165.     | aBag |
  166.     aBag _ Bag new.
  167.     self do: [ :aValue | aBag add: aValue ].
  168.     ^aBag
  169. !!
  170.  
  171.  
  172.  
  173. !Dictionary methodsFor: 'dictionary testing'!
  174.  
  175. includesAssociation: anAssociation
  176.     | assoc |
  177.     assoc _ self associationAt: anAssociation key ifAbsent: [ ^false ].
  178.     ^assoc value = anAssociation value
  179. !
  180.  
  181. includesKey: key
  182.     self associationAt: key ifAbsent: [ ^false ].
  183.     ^true
  184. !
  185.  
  186. includes: anObject
  187.     self do: [ :element | element = anObject ifTrue: [ ^true ] ].
  188.     ^false
  189. !
  190.  
  191. occurrencesOf: aValue
  192.     | count |
  193.     count _ 0.
  194.     self do: [ :element | element = aValue
  195.                     ifTrue: [ count _ count + 1] ].
  196.     ^count
  197. !!
  198.  
  199.  
  200.  
  201. !Dictionary methodsFor: 'dictionary removing'!
  202.  
  203. removeAssociation: anAssociation
  204.     "### does this check the value as well as the key?"
  205.     self removeKey: anAssociation key ifAbsent: [].
  206.     ^anAssociation
  207. !
  208.  
  209. removeKey: key
  210.     ^self removeKey: key ifAbsent: [ ^self error: 'key not found' ]
  211. !
  212.  
  213. removeKey: key ifAbsent: aBlock
  214.     | index assoc |
  215.     index _ self findKeyIndexNoGrow: key ifAbsent: [ ^aBlock value ].
  216.     assoc _ self basicAt: index.
  217.     self basicAt: index put: nil.
  218.     tally _ tally - 1.
  219.     self rehashObjectsAfter: index.
  220.     ^assoc value
  221. !
  222.  
  223. remove: anObject
  224.     self error: 'remove: not allowed in Dictionary'
  225. !
  226.  
  227. remove: anObject ifAbsent: aBlock
  228.     self error: 'remove:ifAbsent: not allowed in Dictionary'
  229. !!
  230.  
  231.  
  232.  
  233. !Dictionary methodsFor: 'dictionary enumerating'!
  234. associationsDo: aBlock
  235.     super do: [ :assoc | aBlock value: assoc ]
  236. !
  237.  
  238. "These could be implemented more efficiently by doing the super do
  239.  directly, or doing the explicit scanning of the dictionary by hand"
  240. keysDo: aBlock
  241.     self associationsDo: [ :assoc | aBlock value: assoc key ]
  242. !
  243.  
  244. do: aBlock
  245.     self associationsDo: [ :assoc | aBlock value: assoc value ]
  246. !
  247.  
  248. collect: aBlock
  249.     | aBag |
  250.     aBag _ Bag new.
  251.     self do: [ :element | aBag add: (aBlock value: element) ].
  252.     ^aBag
  253. !
  254.  
  255. select: aBlock
  256.     | newDict |
  257.     newDict _ self species new.
  258.     self associationsDo:
  259.         [ :assoc | (aBlock value: assoc value)
  260.              ifTrue: [ newDict add: assoc ] ].
  261.     ^newDict
  262. !
  263.  
  264. reject: aBlock
  265.     self shouldNotImplement
  266. !
  267.  
  268. inject: value into: aBlock
  269.     self shouldNotImplement
  270. !!
  271.  
  272.  
  273.  
  274. !Dictionary methodsFor: 'misc math methods'!
  275.  
  276. = aDictionary
  277.     self class == aDictionary class
  278.     ifFalse: [ ^false ].
  279.     tally ~= aDictionary size ifTrue: [ ^false ].
  280.     self associationsDo:
  281.         [ :assoc | assoc value ~= (aDictionary at: assoc key
  282.                                            ifAbsent: [ ^false ])
  283.                      ifTrue: [ ^false ] ].
  284.     ^true
  285. !
  286.  
  287. hash
  288.     | hashValue |
  289.     hashValue _ tally.
  290.     self associationsDo:
  291.         [ :assoc | hashValue _ hashValue + assoc hash ].
  292.     ^hashValue
  293. !!
  294.  
  295.  
  296.  
  297. !Dictionary methodsFor: 'printing'!
  298.  
  299. printOn: aStream
  300.     aStream nextPutAll: self class name , ' (' .
  301.     self associationsDo:
  302.         [ :assoc | aStream print: assoc;
  303.                nextPut: Character space ].
  304.     aStream nextPut: $)
  305. !!
  306.  
  307.  
  308.  
  309. !Dictionary methodsFor: 'storing'!
  310.  
  311. storeOn: aStream
  312.     | hasElements |
  313.     aStream nextPutAll: '(', self class name , ' new'.
  314.     hasElements _ false.
  315.     self associationsDo:
  316.         [ :assoc | aStream nextPutAll: ' at: ';
  317.                store: assoc key;
  318.                nextPutAll: ' put: ';
  319.                store: assoc value;
  320.                nextPut: $;.
  321.            hasElements _ true ].
  322.     hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
  323.     aStream nextPut: $)
  324. !!
  325.  
  326.  
  327.  
  328. !Dictionary methodsFor: 'private methods'!
  329.  
  330. rehashObjectsAfter: index
  331.     "Rehashes all the objects in the collection after index to see if any of
  332.     them hash to index.  If so, that object is copied to index, and the
  333.     process repeats with that object's index, until a nil is encountered."
  334.     | i size count assoc |
  335.     i _ index.
  336.     size _ self basicSize.
  337.     count _ size.
  338.     [ count > 0 ]
  339.         whileTrue:
  340.         [ i _ i \\ size + 1.
  341.               assoc _ self basicAt: i.
  342.           assoc isNil ifTrue: [ ^self ].
  343.               ((assoc key hash \\ size) + 1) = index
  344.               ifTrue: [ self basicAt: index put: assoc.
  345.                   self basicAt: i put: nil.  "Be tidy"
  346.               index _ i ].
  347.               count _ count - 1 ]
  348. !
  349.  
  350. findKeyIndex: aKey ifFull: aBlock
  351.     "Tries to see if aKey exists as the key of an indexed variable (which is an
  352.     association).  If it's searched the entire dictionary and the key is 
  353.     not to be found, aBlock is evaluated and it's value is returned."
  354.     | index count size assoc |
  355.     size _ self basicSize.
  356.     index _ aKey hash \\ size + 1.
  357.     count _ size.
  358.     [ count > 0 ]
  359.         whileTrue:
  360.         [ assoc _ self basicAt: index.
  361.               (assoc isNil or: [ assoc key = aKey ])
  362.             ifTrue: [ ^index ].
  363.           index _ index \\ size + 1.
  364.           count _ count - 1. ].
  365.     ^aBlock value
  366. !
  367.         
  368. findKeyIndex: aKey
  369.     "Finds an association with the given key in the dictionary and returns its
  370.     index.  If the dictionary doesn't contain the object and there is no nil
  371.     element, the dictionary is grown and then the index of where the object
  372.     would go is returned."
  373.     ^self findKeyIndex: aKey
  374.            ifFull: [ self grow.
  375.                 self findKeyIndexNoGrow: aKey
  376.                   ifAbsent: [ ^self error: 'failed to grow a new empty element!!!' ] ]
  377. !
  378.  
  379. findKeyIndexNoGrow: aKey ifAbsent: aBlock
  380.     | index |
  381.     index _ self findKeyIndex: aKey ifFull: [ 0 ].
  382.     (index = 0 )
  383.         ifTrue: [ ^aBlock value ]
  384.     ifFalse: [ ^index ]
  385. !
  386.  
  387. grow
  388.     | newDict |
  389.     newDict _ self species new: self basicSize + self growSize.
  390.     self associationsDo: [ :assoc | newDict add: assoc ].
  391.     ^self become: newDict
  392. !
  393.  
  394. growSize
  395.     ^32
  396.  
  397. !!
  398.  
  399.