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