From: Horst Duchene <Horst.Duchene@...>
Date: 2001-11-14T05:30:32+09:00
Subject: [ruby-talk:25068] Re: Set class in Ruby (Bag in Smalltalk)

"Hal E. Fulton" <hal9000@hypermetrics.com> schrieb im Newsbeitrag
news:008201c16c79$7dce4fc0$0300a8c0@austin.rr.com...
> ----- Original Message -----
> From: Paul Brannan <pbrannan@atdesk.com>
> To: ruby-talk ML <ruby-talk@ruby-lang.org>
> Sent: Tuesday, November 13, 2001 1:13 PM
> Subject: [ruby-talk:25056] Re: Set class in Ruby
>
>
> > On Wed, 14 Nov 2001, Hal E. Fulton wrote:
> > > Some people will want bags, by the way (though I've never
> > > really used one) which are like sets but allow duplicates.
> > > I don't know all the implications of this.
> >
> > Is a "bag" the same as C++'s "multiset"?
>
> I don't know. Never had a use for either.
>
> Hal

I already had uses of Bags in my Smalltalk experience. The most importend
method is:

#valuesAndCountsDo: aBlock
 "Evaluate aBlock with the distinct values contained
 in the receiver.  For each value, evaluate the block
 with the value and the number of occurrences of it."

This is the class comment:

A Bag is an unordered collection of elements.  It stores these elements in a
dictionary, tallying up occurrences of equal objects.  Because a Bag can
store an occurrence only once, its clients should beware that objects they
store will not necessarily be retrieved such that == is true.  This depends
on whether the Bag was created using #equalityNew: or #identityNew:--if
#identityNew: is used, identity will be preserved, but the space savings may
be substantially reduced.

Instance Variables:
 contents  <Dictionary> of associations between elements and the number of
occurrences of each element in the Bag


Object Reference:
A Bag is like a Set that permits duplicates. While it does not waste space
by keeping the actual duplicates, it does keep a count of the occurrences of
each object. Since, like a Set, a Bag's elements are not kept in any order,
knowing how many times a given object occurs is equivalent to having that
many copies of it in the Bag.
Because a Bag does not actually store duplicates, it is more space-efficient
than an Array or List. An Array or List preserves the order of its elements,
however. The difference shows up when you loop through (enumerate) the
elements -- the same Bag may loop through its elements in a different order
each time, while an Array or List offers a predictable order.
When using a Bag, it is important to remember the distinction between #==
and #=. When an object is added to a Bag, it is tallied and discarded if it
is #= to an existing element. Thus, the application cannot expect to use #==
after retrieving that element, since it may get an equal but not identical
object.
In addition to its inherited abilities, a Bag knows how to:
 -Add an object multiple times (adding protocol)
 -Convert itself to a Set, in effect keeping only unique elements
(converting)

Horst