December 4, 2022

Set and Bag


A set, in OO terms, is an object that represents a collection of unordered elements each of which is unique. These elements are themselves objects, or more accurately references to objects. The important point to remember here is that a instance of Set contains no duplicates. It can expand and contract, it may in fact be empty, but you cannot add an object that is already present in the set.

Employing the gallery scenario, the Quad Gallery wishes to create a list of all artists it currently represents. To store this list of names, and at this stage the ordering of that list is of no importance, an object, referenced by setOfArtists, is created by executing the following code.

setOfArtists := Set new

Inspection of the message answer reveals an instance of Set with an instance variable tally referencing the SmallInteger object 0. tally simply keeps a count of the number of elements in the set and at this stage reflects the fact that the set is empty.

By use of the add: message selector, objects of any class can be added to a set. Therefore by evaluating a series of expressions similar to

setOfArtists add: 'Richard Smith'

and so on, a set of strings can be made. The message answer is the argument supplied, in this case the string 'Richard Smith' and tally is incremented after each addition.

In the process of creating this set of names, a problem arises. The gallery have two artists named Richard Smith. This is a problem since only one string with the value 'Richard Smith' can be held in the set. The gallery would require a change, say by incorporating a middle name, or one of these artists would need to change his name. However, should it be necessary for the collection to hold duplicate elements, the Bag class can be used.

A bag is an unordered collection of elements. The Smalltalk Bag class stores these elements in a dictionary, tallying up occurrences of duplicate objects.

bagOfAllArtists := Bag new.
bagOfAllArtists add: 'Richard Smith';
                add: 'Richard Smith'

Bag has an instance variable contents that references a dictionary of associations between elements and the number of occurrences of each element in the bag. Dictionary and Association will be discussed later, but inspection of the bag created by the above code would reveal that the Bag object bagOfAllArtists holds a reference to a dictionary containing an instance of Association referenced by the expression
'Richard Smith'->2
with the tally of this dictionary referencing 1. If another string was added that was not equal to 'Richard Smith' , say 'Bert Irvin', then another association
'Bert Irvin'->1
would be created with contents now referencing a dictionary of two associations; the tally of this dictionary would be incremented to 2.

Sets and bags can contain any objects and although I have used strings, the elements of these two collections could be a mixture of any kind of object, including other collections.

Next page » The protocol of Set

Previous page « Introduction to collections
































































Up to top of page