home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 3 / CDPDIII.bin / pd / programming / gnusmalltalk / identitydictionary.st < prev    next >
Text File  |  1992-02-15  |  8KB  |  307 lines
  1. "======================================================================
  2. |
  3. |   IdentityDictionary 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.  Converted to use
  36. |              cascaded printing.
  37. |
  38. | sbb         16 Mar 91      Class creation now separate statement.
  39. |
  40. | sbyrne     25 Apr 89      created.
  41. |
  42. "
  43.  
  44. Dictionary variableSubclass: #IdentityDictionary
  45.        instanceVariableNames: 'values'
  46.        classVariableNames: ''
  47.        poolDictionaries: ''
  48.        category: nil
  49. !
  50.  
  51. IdentityDictionary comment:
  52. 'I am similar to dictionary, except that my representation is
  53. different, and I use the object identity comparision message == to
  54. determine equivalence of indices.' !
  55.  
  56. !IdentityDictionary class methodsFor: 'instance creation'!
  57.  
  58. new
  59.     ^self new: 4
  60. !
  61.  
  62. new: anInteger
  63.     ^(super new: anInteger) initValues
  64.  
  65. !!
  66.  
  67.  
  68.  
  69. !IdentityDictionary methodsFor: 'accessing'!
  70.  
  71. add: anAssociation
  72.     self at: anAssociation key put: anAssociation value.
  73.     ^anAssociation
  74. !
  75.  
  76. at: key put: value
  77.     | index |
  78.     index _ self findKeyIndex: key.
  79.     (self basicAt: index) isNil
  80.         ifTrue: [ tally _ tally + 1 ].
  81.     self basicAt: index put: key.
  82.     values basicAt: index put: value.
  83.     ^value
  84. !
  85.  
  86. at: key ifAbsent: aBlock
  87.     | index |
  88.     index _ self findKeyIndex: key.
  89.     (self basicAt: index) isNil
  90.         ifTrue: [ ^aBlock value ].
  91.     ^values basicAt: index
  92. !    
  93.     
  94. associationAt: key ifAbsent: aBlock
  95.     | index assoc|
  96.     ^Association key: key
  97.          value: (self at: key
  98.                       ifAbsent: [ ^aBlock value ])
  99. !
  100.  
  101. keyAtValue: value ifAbsent: exceptionBlock
  102.     self indicesDo:
  103.         [ :i | value = (values basicAt: i)
  104.                  ifTrue: [ ^self basicAt: i] ].
  105.     ^exceptionBlock value
  106. !!
  107.  
  108.  
  109.  
  110. !IdentityDictionary methodsFor: 'dictionary testing'!
  111.  
  112. includesAssociation: anAssociation
  113.     | index |
  114.     index _ self findKeyIndex: anAssociation key.
  115.     ^(self basicAt: index) notNil
  116.         and: [ (values basicAt: index) = anAssociation value ]
  117. !
  118.  
  119. includesKey: key
  120.     ^(self basicAt: (self findKeyIndex: key)) notNil
  121. !!
  122.  
  123.  
  124.  
  125. !IdentityDictionary methodsFor: 'dictionary removing'!
  126.  
  127. removeKey: key ifAbsent: aBlock
  128.     | index value|
  129.     index _ self findKeyIndexNoGrow: key ifAbsent: [ ^aBlock value ].
  130.     value _ values basicAt: index.
  131.     self basicAt: index put: nil.
  132.     values basicAt: index put: nil.
  133.     tally _ tally - 1.
  134.     self rehashObjectsAfter: index.
  135.     ^ value
  136. !!
  137.  
  138.  
  139.  
  140. !IdentityDictionary methodsFor: 'dictionary enumerating'!
  141.  
  142. associationsDo: aBlock
  143.     self indicesDo:
  144.         [ :i | aBlock value: (Association key: (self basicAt: i)
  145.                                       value: (values basicAt: i)) ]
  146. !
  147.  
  148. "These could be implemented more efficiently by 
  149.  doing the explicit scanning of the dictionary by hand"
  150. keysDo: aBlock
  151.     self indicesDo: [ :i | aBlock value: (self basicAt: i) ]
  152. !
  153.  
  154. do: aBlock
  155.     self indicesDo: [ :i | aBlock value: (values basicAt: i) ]
  156. !
  157.  
  158. select: aBlock
  159.     | newDict |
  160.     newDict _ self species new.
  161.     self indicesDo:
  162.         [ :i | (aBlock value: (values basicAt: i))
  163.                  ifTrue: [ newDict add: (Association key: (self basicAt: i)
  164.                                             value: (values basicAt: i))] ].
  165.     ^newDict
  166. !!
  167.  
  168.  
  169.  
  170. !IdentityDictionary methodsFor: 'misc math methods'!
  171.  
  172. = aDictionary
  173.     self class == aDictionary class
  174.     ifFalse: [ ^false ].
  175.     tally ~= aDictionary size ifTrue: [ ^false ].
  176.     self indicesDo:
  177.         [ :i | (values basicAt: i) = (aDictionary at: (self basicAt: i)
  178.                                               ifAbsent: [ ^false ])
  179.                  ifFalse: [ ^false ] ].
  180.     ^true
  181. !
  182.  
  183. hash
  184.     | hashValue |
  185.     hashValue _ tally.
  186.     self indicesDo:
  187.         [ :i | hashValue _ hashValue + (self basicAt: i) hash.
  188.            hashValue _ hashValue + (values basicAt: i) hash ].
  189.     ^hashValue
  190. !!
  191.  
  192.  
  193.  
  194. !IdentityDictionary methodsFor: 'printing'!
  195.  
  196. printOn: aStream
  197.     aStream nextPutAll: self class name , ' (' ; nl.
  198.     self indicesDo:
  199.         [ :i | aStream tab;
  200.            print: (self basicAt: i);
  201.            nextPutAll: '->';
  202.            print: (values basicAt: i);
  203.            nl ].
  204.     aStream nextPut: $)
  205. !!
  206.  
  207.  
  208.  
  209. !IdentityDictionary methodsFor: 'storing'!
  210.  
  211. storeOn: aStream
  212.     | hasElements |
  213.     aStream nextPutAll: '(', self class name , ' new'.
  214.     hasElements _ false.
  215.     self indicesDo:
  216.         [ :i | aStream nextPutAll: ' at: ';
  217.            store: (self basicAt: i);
  218.            nextPutAll: ' put: ';
  219.            store: (values basicAt: i);
  220.            nextPut: $;.
  221.            hasElements _ true ].
  222.     hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
  223.     aStream nextPut: $)
  224. !!
  225.  
  226.  
  227.  
  228. !IdentityDictionary methodsFor: 'private methods'!
  229.  
  230. initValues
  231.     values _ Array new: self basicSize
  232. !
  233.  
  234. indicesDo: aBlock
  235.     "Invokes aBlock with all the indices of the set that have valid keys"
  236.     1 to: self basicSize do:
  237.         [ :i | (self basicAt: i) notNil
  238.               ifTrue: [ aBlock value: i ] ]
  239. !    
  240.  
  241. rehashObjectsAfter: index
  242.     "### rehash bug needs to be fixed!!!!"
  243.     "Rehashes all the objects in the collection after index to see if any of
  244.     them hash to index.  If so, that object is copied to index, and the
  245.     process repeats with that object's index, until a nil is encountered."
  246.     | i size count key |
  247.     i _ index.
  248.     size _ self basicSize.
  249.     count _ size.
  250.     [ count > 0 ]
  251.         whileTrue:
  252.         [ i _ i \\ size + 1.
  253.               key _ self basicAt: i.
  254.           key isNil ifTrue: [ ^self ].
  255.               ((key hash \\ size) + 1) = index
  256.               ifTrue: [ self basicAt: index put: key.
  257.                   values basicAt: index put: (values basicAt: i).
  258.                   self basicAt: i put: nil.  "Be tidy"
  259.               values basicAt: i put: nil."Be tidy"
  260.               index _ i ].
  261.               count _ count - 1 ]
  262. !
  263.  
  264. findKeyIndex: aKey ifFull: aBlock
  265.     "Tries to see if aKey exists as the key of an indexed variable (which is an
  266.     association).  If it's searched the entire dictionary and the key is 
  267.     not to be found, aBlock is evaluated and it's value is returned."
  268.     | index count size key |
  269.     size _ self basicSize.
  270.     index _ aKey hash \\ size + 1.
  271.     count _ size.
  272.     [ count > 0 ]
  273.         whileTrue:
  274.         [ key _ self basicAt: index.
  275.               (key isNil or: [ key == aKey ])
  276.             ifTrue: [ ^index ].
  277.           index _ index \\ size + 1.
  278.           count _ count - 1. ].
  279.     ^aBlock value
  280. !
  281.         
  282. findKeyIndex: aKey
  283.     "Finds an association with the given key in the dictionary and returns its
  284.     index.  If the dictionary doesn't contain the object and there is no nil
  285.     element, the dictionary is grown and then the index of where the object
  286.     would go is returned."
  287.     ^self findKeyIndex: aKey
  288.            ifFull: [ self grow.
  289.                 self findKeyIndexNoGrow: aKey
  290.                   ifAbsent: [ ^self error: 'failed to grow a new empty element!!!' ] ]
  291. !
  292.  
  293. grow
  294.     | newDict |
  295.     newDict _ self species new: self basicSize + self growSize.
  296.     self indicesDo: [ :i | newDict at: (self basicAt: i)
  297.                    put: (values basicAt: i) ].
  298.     ^self become: newDict
  299. !
  300.  
  301. growSize
  302.     ^32
  303.  
  304. !!
  305.  
  306.  
  307.