home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 1 / RISC_DISC_1.iso / pd_share / code / smalltalk / !GNUst / st / Set < prev    next >
Encoding:
Text File  |  1991-09-13  |  6.4 KB  |  254 lines
  1. "======================================================================
  2. |
  3. |   Set Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1990, 1991 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. | sbyrne     19 Sep 89      Converted to use real method categories.
  36. |
  37. | sbyrne     25 Apr 89      created.
  38. |
  39. "
  40.  
  41. Collection variableSubclass: #Set
  42.        instanceVariableNames: 'tally'
  43.        classVariableNames: ''
  44.        poolDictionaries: ''
  45.        category: nil.
  46.  
  47. Set comment:
  48. 'I am the typical set object; I can store any objects uniquely.  I
  49. use the = operator to determine duplication of objects.' !
  50.  
  51. !Set class methodsFor: 'instance creation'!
  52.  
  53. new
  54.     ^self new: 4
  55. !
  56.  
  57. new: anInteger
  58.     ^(super new: anInteger) setTally
  59. !!
  60.  
  61.  
  62.  
  63. !Set methodsFor: 'accessing'!
  64.  
  65. at: index
  66.     self error: 'at: not allowed for Set'
  67. !
  68.  
  69. at: index put: value
  70.     self error: 'at:put: not allowed for Set'
  71. !
  72.  
  73. add: newObject
  74.     | index |
  75.     newObject isNil ifTrue: [ ^newObject ].
  76.     index _ self findObjectIndex: newObject.
  77.     (self basicAt: index) isNil
  78.         ifTrue: [ self basicAt: index put: newObject.
  79.               tally _ tally + 1 ].
  80.     ^newObject
  81. !!
  82.  
  83.  
  84.  
  85. !Set methodsFor: 'Removing from a collection'!
  86.  
  87. remove: oldObject ifAbsent: anExceptionBlock
  88.     | index |
  89.     index _ self findObjectIndexNoGrow: oldObject
  90.                  ifAbsent: [ ^anExceptionBlock value ].
  91.     tally _ tally - 1.
  92.     self rehashObjectsAfter: index.
  93.     ^oldObject
  94. !!
  95.  
  96.  
  97.  
  98. !Set methodsFor: 'testing collections'!
  99.  
  100. includes: anObject
  101.     ^(self basicAt: (self findObjectIndex: anObject)) ~~ nil
  102. !
  103.  
  104. isEmpty
  105.     ^tally == 0
  106. !
  107.  
  108. occurrencesOf: anObject
  109.     "Return the number of occurrences of anObject.  Since we're a set, this
  110.     is either 0 or 1.  Nil is never directly in the set, so we special case
  111.     it here."
  112.     anObject isNil ifTrue: [ ^1 ].
  113.     (self includes: anObject)
  114.         ifTrue: [ ^1 ]
  115.     ifFalse: [ ^0 ]
  116. !
  117.  
  118. size
  119.     ^tally
  120. !
  121.  
  122. hash
  123.     "Return the hash code for the members of the set.  Since order is
  124.     unimportant; we use a commutative operator to compute the hash value."
  125.     ^self inject: tally
  126.           into: [ :hashValue :member | hashValue + member hash ]
  127. !
  128.  
  129. = aSet
  130.     "Returns true if the two sets have the same membership, false if not"
  131.     tally = aSet size  ifFalse: [ ^false ].
  132.     self do: [ :element | (aSet includes: element)
  133.                             ifFalse: [ ^false ] ].
  134.     ^true
  135. !!
  136.  
  137.  
  138.  
  139. !Set methodsFor: 'enumerating the elements of a collection'!
  140.  
  141. do: aBlock
  142.     "Enumerate all the non-nil members of the set"
  143.     1 to: self basicSize do:
  144.         [ :i | (self basicAt: i) notNil
  145.               ifTrue: [ aBlock value: (self basicAt: i) ] ]
  146. !!
  147.  
  148.  
  149.  
  150. !Set methodsFor: 'printing'!
  151.  
  152. printOn: aStream
  153.     | firstTime |
  154.     aStream nextPutAll: self class name , ' ('.
  155.     firstTime _ true.
  156.     self do:
  157.         [ :element | firstTime ifTrue: [ firstTime _ false ]
  158.                            ifFalse: [ aStream nextPutAll: ' ' ].
  159.              element storeOn: aStream ].
  160.     aStream nextPut: $).
  161. !!
  162.  
  163.  
  164.  
  165. !Set methodsFor: 'storing'!
  166.  
  167. storeOn: aStream
  168.     | hasElements |
  169.     aStream nextPutAll: '(Set new'.
  170.     hasElements _ false.
  171.     self do:
  172.         [ :element | aStream nextPutAll: ' add: '.
  173.              element storeOn: aStream.
  174.              aStream nextPut: $;.
  175.              hasElements _ true ].
  176.     hasElements ifTrue: [ aStream nextPutAll: ' yourself' ].
  177.     aStream nextPut: $).
  178. !!
  179.  
  180.  
  181.  
  182. !Set methodsFor: 'private methods'!
  183.  
  184. setTally
  185.     "Instance variable initialization."
  186.     tally _ 0
  187. !
  188.  
  189. rehashObjectsAfter: index
  190.     "Rehashes all the objects in the collection after index to see if any of
  191.     them hash to index.  If so, that object is copied to index, and the
  192.     process repeats with that object's index, until a nil is encountered."
  193.     | i size count element |
  194.     i _ index.
  195.     size _ self basicSize.
  196.     count _ size.
  197.     self basicAt: index put: nil.
  198.     [ count _ count - 1.
  199.       i _ i \\ size + 1.
  200.       element _ self basicAt: i.
  201.       count > 0 and: [ element notNil ] ]
  202.         whileTrue:
  203.         [ self basicAt: i put: nil.
  204.           self basicAt: (self findObjectIndex: element) put: element ].
  205.     ^self
  206. !
  207.  
  208. findObjectIndex: anObject ifFull: aBlock
  209.     "Tries to see if anObject exists as an indexed variable.  If it's searched
  210.     the entire set and the object is not to be found, aBlock is evaluated and
  211.     it's value is returned."
  212.     | index count size newSet element |
  213.     size _ self basicSize.
  214.     index _ anObject hash \\ size + 1.
  215.     count _ size.
  216.     [ count > 0 ]
  217.         whileTrue:
  218.         [ element _ self basicAt: index.
  219.               (element isNil or: [ element = anObject ])
  220.             ifTrue: [ ^index ].
  221.           index _ index \\ size + 1.
  222.           count _ count - 1 ].
  223.     ^aBlock value
  224. !
  225.         
  226. findObjectIndex: anObject
  227.     "Finds the given object in the set and returns its index.  If the set
  228.     doesn't contain the object and there is no nil element, the set is
  229.     grown and then the index of where the object would go is returned."
  230.     ^self findObjectIndex: anObject
  231.            ifFull: [ self grow.
  232.                 self findObjectIndexNoGrow: anObject
  233.                     ifAbsent: [ self error: 'failed to grow a new empty element!!!' ] ]
  234. !
  235.  
  236. findObjectIndexNoGrow: anObject ifAbsent: aBlock
  237.     | index |
  238.     index _ self findObjectIndex: anObject ifFull: [ 0 ].
  239.     index = 0 
  240.         ifTrue: [ ^aBlock value ]
  241.     ifFalse: [ ^index ]
  242. !
  243.  
  244. grow
  245.     | newSet |
  246.     newSet _ self species new: self basicSize + self growSize.
  247.     self do: [ :element | newSet add: element ].
  248.     ^self become: newSet
  249. !
  250.  
  251. growSize
  252.     ^self basicSize        "this will double the size"
  253. !!
  254.