Collections-Sequenceable

Heap
Class Heap implements a special data structure commonly referred to as 'heap'. Heaps are more efficient than SortedCollections if:
a) Elements are only removed at the beginning
b) Elements are added with arbitrary sort order.
The sort time for a heap is O(n log n) in all cases.
Instance variables:
array <Array> The data repository
tally <Integer> The number of elements in the heap
sortBlock <Block|nil> A two-argument block defining the sort order,
or nil in which case the default sort order is
[:element1 :element2| element1 <= element2]
indexUpdateBlock <Block|nil>
A two-argument block of the form [:data :index | ... ]
which allows an application object to keep track of its
index within the heap. Useful for quick heap update
when object's sort value changes (for example, when an
object in a priority queue has its priority increased
by an external event, you don't want to have to search
through the whole heap to find the index before fixing
the heap). No update occurs if nil.
=
Answer true if the receiver is equivalent to the otherCollection.
First test for identity, then rule out different species and sizes of
collections. As a last resort, examine each element of the receiver
and the otherCollection.
add:
Include newObject as one of the receiver's elements. Answer newObject.
array
at:
Return the element at the given position within the receiver
at:put:
Heaps are accessed with #add: not #at:put:
do:
Evaluate aBlock with each of the receiver's elements as the argument.
downHeap:
Check the heap downwards for correctness starting at anIndex.
Everything above (i.e. left of) anIndex is ok.
downHeapSingle:
This version is optimized for the case when only one element in the receiver can be at a wrong position. It avoids one comparison at each node when travelling down the heap and checks the heap upwards after the element is at a bottom position. Since the probability for being at the bottom of the heap is much larger than for being somewhere in the middle this version should be faster.
first
Return the first element in the receiver
grow
Become larger.
growSize
Return the size by which the receiver should grow if there are no empty slots left.
growTo:
Grow to the requested size.
indexUpdateBlock:
isEmpty
Answer whether the receiver contains any elements.
isHeap
new
new:
privateRemoveAt:
Remove the element at the given index and make sure the sorting order is okay
reSort
Resort the entire heap
remove:ifAbsent:
Remove oldObject as one of the receiver's elements. If several of the
elements are equal to oldObject, only one is removed. If no element is
equal to oldObject, answer the result of evaluating anExceptionBlock.
Otherwise, answer the argument, oldObject.
removeAt:
Remove the element at given position
removeFirst
Remove the first element from the receiver
setCollection:
setCollection:tally:
size
Answer how many elements the receiver contains.
sortBlock
sortBlock:
sorts:before:
Return true if element1 should be sorted before element2.
This method defines the sort order in the receiver
species
Answer the preferred class for reconstructing the receiver. For example,
collections create new collections whenever enumeration messages such as
collect: or select: are invoked. The new kind of collection is determined by
the species of the original collection. Species and class are not always the
same. For example, the species of Interval is Array.
trim
Remove any empty slots in the receiver.
upHeap:
Check the heap upwards for correctness starting at anIndex.
Everything below anIndex is ok.
updateObjectIndex:
If indexUpdateBlock is not nil, notify the object at index of its new position in the heap array.
withAll:
withAll:sortBlock:
Interval
I represent a finite arithmetic progression.
+
-
=
Answer true if the receiver is equivalent to the otherCollection.
First test for identity, then rule out different species and sizes of
collections. As a last resort, examine each element of the receiver
and the otherCollection.
add:
Adding to an Interval is not allowed.
at:
Answer the anInteger'th element.
at:put:
Storing into an Interval is not allowed.
collect:
Evaluate aBlock with each of the receiver's elements as the argument.
Collect the resulting values into a collection like the receiver. Answer
the new collection.
collect:displayingProgress:
Evaluate aBlock with each of the receiver's elements as the argument.
Collect the resulting values into a collection like the receiver. Answer
the new collection.
copy
Return a copy of me. Override the superclass because my species is
Array and copy, as inherited from SequenceableCollection, uses
copyFrom:to:, which creates a new object of my species.
do:
Evaluate aBlock for each value of the interval.
Implementation note: instead of repeatedly incrementing the value
aValue := aValue + step.
until stop is reached,
We prefer to recompute value from start
aValue := aValue + (index * step).
This is better for floating points, while not degrading Integer and
Fraction case too much.
Moreover, this is consistent with methods #at: and #size
extent
Answer the max - min of the receiver interval.
first
Refer to the comment in SequenceableCollection|first.
from:to:
from:to:by:
hash
Hash is reimplemented because = is implemented.
increment
Answer the receiver's interval increment.
indexOf:startingAt:ifAbsent:
startIndex is an positive integer, the collection index where the search is started.
isInterval
isSelfEvaluating
javascriptOn:
last
Refer to the comment in SequenceableCollection|last.
new
newFrom:
permutationsDo:
Repeatly value aBlock with a single copy of the receiver. Reorder the copy
so that aBlock is presented all (self size factorial) possible permutations.
printOn:
Append a sequence of characters that identify the receiver to aStream.
rangeIncludes:
Return true if the number lies in the interval between start and stop.
remove:
Removing from an Interval is not allowed.
reverseDo:
Evaluate aBlock for each element of my interval, in reverse order.
Implementation notes: see do: for an explanation on loop detail
setFrom:to:by:
shallowCopy
Without this method, #copy would return an array instead of a new interval.
The whole problem is burried in the class hierarchy and every fix will worsen
the problem, so once the whole issue is resolved one should come back to this
method fix it.
size
Answer how many elements the receiver contains.
species
Answer the preferred class for reconstructing the receiver. For example,
collections create new collections whenever enumeration messages such as
collect: or select: are invoked. The new kind of collection is determined by
the species of the original collection. Species and class are not always the
same. For example, the species of Interval is Array.
storeOn:
This is possible because we know numbers store and print the same.
LinkedList
I represent a collection of links, which are containers for other objects. Using the message sequence addFirst:/removeLast causes the receiver to behave as a stack; using addLast:/removeFirst causes the receiver to behave as a queue.
add:
Add aLink to the end of the receiver's list. Answer aLink.
add:after:
Add otherLink after link in the list. Answer aLink.
add:before:
addFirst:
Add aLink to the beginning of the receiver's list. Answer aLink.
addLast:
Add aLink to the end of the receiver's list. Answer aLink.
at:
Primitive. Assumes receiver is indexable. Answer the value of an
indexable element in the receiver. Fail if the argument index is not an
Integer or is out of bounds. Essential. See Object documentation
whatIsAPrimitive.
do:
Refer to the comment in Collection|do:.
first
Answer the first link. Create an error notification if the receiver is
empty.
isEmpty
Answer whether the receiver contains any elements.
last
Answer the last link. Create an error notification if the receiver is
empty.
remove:ifAbsent:
Remove aLink from the receiver. If it is not there, answer the result of
evaluating aBlock.
removeAll
Implementation note: this has to be fast
removeFirst
Remove the first element and answer it. If the receiver is empty, create
an error notification.
removeLast
Remove the receiver's last element and answer it. If the receiver is
empty, create an error notification.
species
Answer the preferred class for reconstructing the receiver. For example,
collections create new collections whenever enumeration messages such as
collect: or select: are invoked. The new kind of collection is determined by
the species of the original collection. Species and class are not always the
same. For example, the species of Interval is Array.
OrderedCollection
I represent a collection of objects ordered by the collector.
add:
Include newObject as one of the receiver's elements. Answer newObject.
ArrayedCollections cannot respond to this message.
add:after:
Add the argument, newObject, as an element of the receiver. Put it in
the sequence just succeeding oldObject. Answer newObject.
add:afterIndex:
Add the argument, newObject, as an element of the receiver. Put it in
the sequence just after index. Answer newObject.
add:before:
Add the argument, newObject, as an element of the receiver. Put it in
the sequence just preceding oldObject. Answer newObject.
add:beforeIndex:
Add the argument, newObject, as an element of the receiver. Put it in
the sequence just before index. Answer newObject.
addAll:
Add each element of aCollection at my end. Answer aCollection.
addAllFirst:
Add each element of anOrderedCollection at the beginning of the
receiver. Answer anOrderedCollection.
addAllFirstUnlessAlreadyPresent:
Add each element of anOrderedCollection at the beginning of the receiver, preserving the order, but do not add any items that are already in the receiver. Answer anOrderedCollection.
addAllLast:
Add each element of anOrderedCollection at the end of the receiver.
Answer anOrderedCollection.
addFirst:
Add newObject to the beginning of the receiver. Answer newObject.
addLast:
Add newObject to the end of the receiver. Answer newObject.
asArray
Answer an Array whose elements are the elements of the receiver.
at:
Answer my element at index anInteger. at: is used by a knowledgeable
client to access an existing element
at:ifAbsentPut:
Return value at index, however, if value does not exist (nil or out of bounds) then add block's value at index (growing self if necessary)
at:put:
Put anObject at element index anInteger. at:put: cannot be used to
append, front or back, to an ordered collection; it is used by a
knowledgeable client to replace an element.
capacity
Answer the current capacity of the receiver.
collect:
Evaluate aBlock with each of my elements as the argument. Collect the
resulting values into a collection that is like me. Answer the new
collection. Override superclass in order to use addLast:, not at:put:.
collect:displayingProgress:
Evaluate aBlock with each of my elements as the argument. Collect the
resulting values into a collection that is like me. Answer the new
collection. Override superclass in order to use addLast:, not at:put:.
collect:from:to:
Override superclass in order to use addLast:, not at:put:.
collect:thenSelect:
Utility method to improve readability.
Do not create the intermediate collection.
collector
Private
copyEmpty
Answer a copy of the receiver that contains no elements.
copyFrom:to:
Answer a copy of the receiver that contains elements from position
startIndex to endIndex.
copyReplaceFrom:to:with:
Answer a copy of the receiver with replacementCollection's elements in
place of the receiver's start'th to stop'th elements. This does not expect
a 1-1 map from replacementCollection to the start to stop elements, so it
will do an insert or append.
copyWith:
Answer a copy of the receiver that is 1 bigger than the receiver and
includes the argument, newElement, at the end.
do:
Override the superclass for performance reasons.
errorConditionNotSatisfied
errorNoSuchElement
find:
This method answers an index in the range firstIndex .. lastIndex, which is meant for internal use only.
Never use this method in your code, the methods for public use are:
#indexOf:
#indexOf:ifAbsent:
grow
Become larger. Typically, a subclass has to override this if the subclass
adds instance variables.
growSize
hasContentsInExplorer
insert:before:
spot is an index in the range firstIndex .. lastIndex, such an index is not known from outside the collection.
Never use this method in your code, it is meant for private use by OrderedCollection only.
The methods for use are:
#add:before: to insert an object before another object
#add:beforeIndex: to insert an object before a given position.
inspectorClass
Answer the class of the inspector to be used on the receiver. Called by inspect;
use basicInspect to get a normal (less useful) type of inspector.
join:
NB: this implementation only works for Array, since WriteStreams only work for Arrays and Strings. (!)
Overridden in OrderedCollection and SortedCollection.
makeRoomAtFirst
makeRoomAtLast
makeRoomFor:
new
new:
new:withAll:
newFrom:
niActions
niAddLast
niChildrenBlockForIndexedFields
ofSize:
postCopyFrom:to:
finish copying the array in a certain range.
remove:ifAbsent:
SequencableCollections cannot implement removing.
removeAll
remove all the elements from this collection.
Keep same amount of storage
removeAllSuchThat:
Remove each element of the receiver for which aBlock evaluates to true.
The method in Collection is O(N^2), this is O(N).
removeAt:
removeFirst
Remove the first element of the receiver and answer it. If the receiver is
empty, create an error notification.
removeFirst:
Remove first n object into an array
removeIndex:
removedIndex is an index in the range firstIndex .. lastIndex, such an index is not known from outside the collection.
Never use this method in your code, it is meant for private use by OrderedCollection only.
The method for public use is:
#removeAt:
removeLast
Remove the last element of the receiver and answer it. If the receiver is
empty, create an error notification.
removeLast:
Remove last n object into an array with last in last position
replaceFrom:to:with:startingAt:
An ordered collection is growable, so a call to this can make the collection grow.
reset
resetTo:
restoreFromSnapshot:
reverseDo:
Override the superclass for performance reasons.
reversed
Answer a copy of the receiver with element order reversed.
select:
Evaluate aBlock with each of my elements as the argument. Collect into
a new collection like the receiver, only those elements for which aBlock
evaluates to true.
select:thenCollect:
Utility method to improve readability.
Do not create the intermediate collection.
setCollection:
setContents:
size
Answer how many elements the receiver contains.
unsafeRemoveFirst
Remove the first element of the receiver and answer it. If the receiver is
empty, create an error notification.
with:collect:
Collect and return the result of evaluating twoArgBlock with
corresponding elements from this collection and otherCollection.
withIndexCollect:
Just like with:collect: except that the iteration index supplies the second argument to the block. Override superclass in order to use addLast:, not at:put:.
withIndexCollect:displayingProgress:
Just like with:collect: except that the iteration index supplies the second argument to the block. Override superclass in order to use addLast:, not at:put:.
SharedQueue
I provide synchronized communication of arbitrary objects between Processes. An object is sent by sending the message nextPut: and received by sending the message next. If no object has been sent when a next message is sent, the Process requesting the object will be suspended until one is sent.
findFirst:
Answer the next object that satisfies aBlock, skipping any intermediate objects.
If no object is found, answer <nil>.
NOTA BENE: aBlock MUST NOT contain a non-local return (^).
flush
Throw out all pending contents
flushAllSuchThat:
Remove from the queue all objects that satisfy aBlock.
initialize:
isEmpty
Answer whether any objects have been sent through the receiver and
not yet received by anyone.
makeRoomAtEnd
new
new:
next
Answer the object that was sent through the receiver first and has not
yet been received by anyone. If no object has been sent, suspend the
requesting process until one is.
nextOrNil
Answer the object that was sent through the receiver first and has not
yet been received by anyone. If no object has been sent, answer <nil>.
nextOrNilSuchThat:
Answer the next object that satisfies aBlock, skipping any intermediate objects.
If no object has been sent, answer <nil> and leave me intact.
NOTA BENE: aBlock MUST NOT contain a non-local return (^).
nextPut:
Send value through the receiver. If a Process has been suspended
waiting to receive a value through the receiver, allow it to proceed.
peek
Answer the object that was sent through the receiver first and has not
yet been received by anyone but do not remove it from the receiver. If
no object has been sent, return nil
size
Answer the number of objects that have been sent through the
receiver and not yet received by anyone.
SharedQueue2
An implementation of a shared queue based on class Monitor. Clients may may place items on the queue using nextPut: or remove them using methods like next or nextOrNil. Items are removed in first-in first-out (FIFO) order. It is safe for multiple threads to access the same shared queue, which is why this is a "shared" queue.
[monitor] is used to synchronize access from multiple threads.
[items] is an ordered collection holding the items that are in the queue. New items are added at the end, and old items are removed from the beginning.
All methods must hold the monitor while they run.
findFirst:
Answer the next object that satisfies aBlock, skipping any intermediate objects.
If no such object has been queued, answer <nil> and leave me intact.
flush
Remove from the queue all objects
flushAllSuchThat:
Remove from the queue all objects that satisfy aBlock.
initialize
Subclasses should redefine this method to perform initializations on instance creation
isEmpty
new
next
Answer the next object accessible by the receiver.
nextOrNil
nextOrNilSuchThat:
Answer the next object that satisfies aBlock, skipping any intermediate objects.
If no object has been sent, answer <nil> and leave me intact.
NOTA BENE: aBlock MUST NOT contain a non-local return (^).
nextPut:
Insert the argument, anObject, as the next object accessible by the
receiver. Answer anObject.
peek
Answer the object that was sent through the receiver first and has not
yet been received by anyone but do not remove it from the receiver. If
no object has been sent, return nil
printOn:
Append to the argument, aStream, a sequence of characters that
identifies the receiver.
size
Primitive. Answer the number of indexable variables in the receiver.
This value is the same as the largest legal subscript. Essential. See Object
documentation whatIsAPrimitive.
SortedCollection
I represent a collection of objects ordered by some property of the objects themselves. The ordering is specified in a BlockContext.
=
Answer true if my and aSortedCollection's species are the same,
and if our blocks are the same, and if our elements are the same.
add:
Include newObject as one of the receiver's elements. Answer newObject.
ArrayedCollections cannot respond to this message.
addAll:
Add each element of aCollection at my end. Answer aCollection.
addFirst:
Add newObject to the beginning of the receiver. Answer newObject.
at:put:
Put anObject at element index anInteger. at:put: cannot be used to
append, front or back, to an ordered collection; it is used by a
knowledgeable client to replace an element.
collect:
Evaluate aBlock with each of my elements as the argument. Collect the
resulting values into an OrderedCollection. Answer the new collection.
Override the superclass in order to produce an OrderedCollection instead
of a SortedCollection.
collect:displayingProgress:
Evaluate aBlock with each of my elements as the argument. Collect the
resulting values into an OrderedCollection. Answer the new collection.
Override the superclass in order to produce an OrderedCollection instead
of a SortedCollection.
copy
Answer another instance just like the receiver. Subclasses typically override postCopy; they typically do not override shallowCopy.
copyEmpty
Answer a copy of the receiver without any of the receiver's elements.
defaultSort:to:
Sort elements i through j of self to be nondescending according to
sortBlock.
indexForInserting:
insert:before:
spot is an index in the range firstIndex .. lastIndex, such an index is not known from outside the collection.
Never use this method in your code, it is meant for private use by OrderedCollection only.
The methods for use are:
#add:before: to insert an object before another object
#add:beforeIndex: to insert an object before a given position.
join:
Curiously addAllLast: does not trigger a reSort, so we must do it here.
median
Return the middle element, or as close as we can get.
new:
reSort
sort:to:
Sort elements i through j of self to be nondescending according to
sortBlock.
sortBlock
Answer the blockContext which is the criterion for sorting elements of
the receiver.
sortBlock:
Make the argument, aBlock, be the criterion for ordering elements of the
receiver.