The Trunk: Collections-nice.372.mcz

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

The Trunk: Collections-nice.372.mcz

commits-2
Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-nice.372.mcz

==================== Summary ====================

Name: Collections-nice.372
Author: nice
Time: 26 August 2010, 10:38:04.98 pm
UUID: e9206906-ab54-4076-af3f-bf1bd833aa4e
Ancestors: Collections-ar.371

Enhance Dictionary comment.
Fix Set comment, a Set can includes: nil.
Fix a typo in IdentitySet.
Comment KeyedIdentitySet and SetElement.

Note: I didn't make any effort wrt style homogeneity. Prefered style should be defined first.

=============== Diff against Collections-ar.371 ===============

Item was changed:
  Set subclass: #IdentitySet
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''
  category: 'Collections-Unordered'!
 
+ !IdentitySet commentStamp: 'nice 8/26/2010 22:00' prior: 0!
- !IdentitySet commentStamp: 'sw 1/14/2003 22:35' prior: 0!
  The same as a Set, except that items are compared using #== instead of #=.
 
  Almost any class named IdentityFoo is the same as Foo except for the way items are compared.  In Foo, #= is used, while in IdentityFoo, #== is used.  That is, identity collections will treat items as the same only if they have the same identity.
 
  For example, note that copies of a string are equal:
 
  ('abc' copy) = ('abc' copy)
 
+ but they are not identical:
- but they are not identitcal:
 
  ('abc' copy) == ('abc' copy)
 
  A regular Set will only include equal objects once:
 
  | aSet |
  aSet := Set new.
  aSet add: 'abc' copy.
  aSet add: 'abc' copy.
  aSet
 
 
  An IdentitySet will include multiple equal objects if they are not identical:
 
  | aSet |
  aSet := IdentitySet new.
  aSet add: 'abc' copy.
  aSet add: 'abc' copy.
  aSet
  !

Item was changed:
  HashedCollection subclass: #Dictionary
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''
  category: 'Collections-Unordered'!
 
+ !Dictionary commentStamp: 'nice 8/26/2010 22:30' prior: 0!
+ A Dictionary is an unordered collection of values which are indexed by arbitrary keys.
+ A Dictionary is accessed via #at: and #at:put: messages like a SequenceableCollection, but instead of being Integer, the keys can be any object that responds to =.
+
+ The = message is used to test for the existence of the key in the Dictionary.
+ If the key is absent, #at:put: adds a new entry to the Dictionary.
+
+ (Dictionary new)
+ at: 'foo' put: 1;
+ at: 'bar' put: 8;
+ yourself.
+
+ Each key is unique: storing another value with #at:put: at an already used key overwrites previously associated value.
+
+ (Dictionary new)
+ at: 'bar' put: 4;
+ at: 'bar' put: 8;
+ at: 'bar'.
+
+ The values are not necessarily unique, thus a Dictionary can also be seen as a sort of Bag with this respect.
+
+ (Dictionary new)
+ at: 'foo' put: 8;
+ at: 'bar' put: 8;
+ yourself.
+
+ If the key is absent, #at: raises an Error. An alternate block of code can be executed and its value returned in this case using #at:ifAbsent:.
+ See also #at:ifAbsentPut:.
+
+ (Dictionary new) at: 'foo' ifAbsent: [nil].
+
+ Dictionary is implemented as a HashedCollection of Association (a value is associated to its key et vice et versa).
+ Being a HashedCollection enables fast random access indexed by keys.
+ Consequently, keys must respond to #hash (see super).
+
+ BEWARE: as for every HashedCollection, it is better to not modify an object after it is used as a Dictionary key. The reason is that this might change the #hash code, making the Dictionary unable to find corresponding entry, or make two keys equal violating uniqueness. It's progammer responsibility to take care to not modify the keys, or eventually to send #rehash to the Dictionary if they ever happen to change.
+
+ It is possible to grow or shrink a Dictionary using the messages #add: and #remove: with an Association parameter, however the prefered way to do so is using #at:put: and #removeKey:.
+ BEWARE: as for super, space reserved in internal storage array can grow but never shrink.
+
+ For conveniency, it is also possible to create a Dictionary out of a Collection of associations, as for example in:
+
+     {'foo' -> 1. 'bar' -> 8} as: Dictionary.
+     Dictionary withAll: {'foo' -> 1. 'bar' -> 8}.
+     Dictionary new addAll: {'foo' -> 1. 'bar' -> 8}; yourself.
+
+ BEWARE: though a Sequence collection can be considered as a sequence of values with Integer keys (see #keysAndValuesDo: ), it cannot be converted into a Dictionary using these keys, and following message will fail:
+
+ #('foo' 'bar') as: Dictionary.
+
+ Enumerating a Dictionary with #do: will only enumerate the values, not the keys.
+ Remember, the order of evaluation is arbitrary and can change when you grow or shrink a Dictionary.
+
+     ({'foo' -> 1. 'bar' -> 8} as: Dictionary) do: [:each | Transcript cr; show: each printString].
+
+ For enumerating keys and values, use #keysAndValuesDo:, or use #associationsDo: to enumerate the associations.
+ #select: #reject: #collect: will operate on values while preserving the keys and thus answer a new Dictionary.
+
+     ({'foo' -> 1. 'bar' -> 8} as: Dictionary) collect: [:each | each squared].
+
+ The keys and values of a Dictionary can be extracted by sending #keys and #values message.
+ Though the keys are theoretically a Set and values a Bag, for efficiency reasons, these messages will both return an Array of keys
+ and an Array of values. A neat feature is that these messages are preserving the arbitrary storage order - in other words, (aDictionary values at: 3) is the value associated to key (aDictionary keys at: 3).!
- !Dictionary commentStamp: '<historical>' prior: 0!
- I represent a set of elements that can be viewed from one of two perspectives: a set of associations, or a container of values that are externally named where the name can be any object that responds to =. The external name is referred to as the key.  I inherit many operations from Set.!

Item was changed:
  HashedCollection subclass: #Set
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''
  category: 'Collections-Unordered'!
 
+ !Set commentStamp: 'nice 8/26/2010 22:14' prior: 0!
- !Set commentStamp: '<historical>' prior: 0!
  I represent a set of objects without duplicates.  I can hold anything that responds to
+ #hash and #=, except for nil.  My instances will automatically grow, if necessary.
- #hash and #=, except for nil.  My instances will automatically grow, if necessary,
  Note that I rely on #=, not #==.  If you want a set using #==, use IdentitySet.
 
  Instance structure:
 
    array An array whose non-nil elements are the elements of the set,
  and whose nil elements are empty slots.  There is always at least one nil.
  In fact I try to keep my "load" at 75% or less so that hashing will work well.
 
    tally The number of elements in the set.  The array size is always greater than this.
 
+ The core operation is #scanFor:, which either finds the position where an
- The core operation is #findElementOrNil:, which either finds the position where an
  object is stored in array, if it is present, or finds a suitable position holding nil, if
+ its argument is not present in array.
+
+ I can include an UndefinedObject (nil) thanks to a special implementation using a wrapper (see message #asSetElement and class SetElement).
+ Indeed, a nil entry in the storage array means vacuity, it cannot mean I contain nil.!
- its argument is not present in array,!

Item was changed:
  KeyedSet subclass: #KeyedIdentitySet
  instanceVariableNames: ''
  classVariableNames: ''
  poolDictionaries: ''
  category: 'Collections-Unordered'!
+
+ !KeyedIdentitySet commentStamp: 'nice 8/26/2010 22:01' prior: 0!
+ A KeyedIdentitySet is like a Bag, except that items are compared with #== instead of #= .
+
+ See the comment of IdentitySet for more information.!

Item was changed:
  Object subclass: #SetElement
  instanceVariableNames: 'enclosedElement'
  classVariableNames: 'NilElement'
  poolDictionaries: ''
  category: 'Collections-Support'!
+
+ !SetElement commentStamp: 'nice 8/26/2010 22:21' prior: 0!
+ A SetElement is a special wrapper used to handle addition of some special elements into Set.
+ This is necessary mainly for storing an UndefinedObject in a Set, since nil is used in Set algorithm to designate free slots in internal storage.
+
+ Instance Variables
+ enclosedElement: <Object>
+
+ enclosedElement
+ - the real element we wish to put into the set
+ !