|
Class: OrderedDictionary
Object
|
+--Collection
|
+--Set
|
+--Dictionary
|
+--OrderedDictionary
- Package:
- stx:libbasic
- Category:
- Collections-Sequenceable
- Version:
- rev:
1.78
date: 2019/07/11 18:15:34
- user: cg
- file: OrderedDictionary.st directory: libbasic
- module: stx stc-classLibrary: libbasic
- Author:
- Ifor Wyn Williams <ifor@uk.ac.man.cs>
- Changed by: exept
I am a subclass of Dictionary whose elements (associations) are ordered in a
similar fashion to OrderedCollection.
That is, while being filled via #at:put: messages (or similar Dictionary protocol),
the order in which associations are added, is remembered and accessible via the #atIndex:
or #order messages.
Therefore, this combines fast access via hashing with a defined order when enumerating.
[instance variables:]
order <OrderedCollection> Ordered collection of keys reflecting the order of
associations in the dictionary.
[complexity:]
access by index: O(1)
access by key: O(1)
searching index: O(n)
insertion: mostly (asymptotical) O(1)
removal: mostly O(N) (because order removal will have O(n) behavior)
OrderedCollection
Dictionary
OrderedSet
instance creation
-
new: anInteger
-
-
newFromObject: anObject
-
return a new instance with slots named after anObject's instance variables.
usage example(s):
OrderedDictionary newFromObject:(100 @ 200)
|
accessing
-
after: anAssociation
-
Return the association after anAssociation in the order.
If anAssociation is the last association in the order, return nil.
If anAssociation is not found, invoke an error notifier
-
associations
-
Return an OrderedCollection containing the receiver's associations.
-
at: aKey ifAbsent: default update: aBlock
-
update the element stored under aKey with the result from
evaluating aBlock with the previous stored value as argument, or with default,
if there was no such key initially.
-
at: aKey ifAbsentPut: valueBlock
-
-
at: key put: anObject
-
Set the value at key to be anObject.
If key is not found, create a new entry for key and set its value to anObject.
If key is already present, the order remains unchanged.
Return anObject.
-
at: aKey put: aValue ifPresent: aBlock
-
|d|
d := OrderedDictionary new.
d at:'foo' put:1234 ifPresent:[:v| self error: 'duplicate: ', v printString ].
d at:'foo' put:1234 ifPresent:[:v| self halt:'duplicate: ', v printString. 5555 ].
-
atAll: indexCollection put: anObject
-
Put anObject into the value field of every association specified by indexCollection,
which is typically an interval.
-
atAllPut: anObject
-
Put anObject into the value field of every association in the dictionary.
Return the receiver.
-
atIndex: index
-
return an element at a given index
-
atIndex: index ifAbsent: aBlock
-
return an element at a given index
-
atIndex: index put: anAssociation
-
put an association to a given index. remove the old association at this index
-
before: anAssociation
-
Return the association before anAssociation in the order.
If anAssociation is the first association in the order, return nil.
If anAssociation is not found, invoke an error notifier
-
first
-
Return the first value of the receiver.
Provide an error notification if the receiver contains no elements.
usage example(s):
OrderedDictionary new first
(OrderedDictionary new at:'one' put:1; yourself) first
(OrderedDictionary new at:'one' put:1; yourself) firstKey
(OrderedDictionary new at:'one' put:1; yourself) firstValue
(OrderedDictionary new at:'one' put:1; yourself) firstAssociation
|
-
firstAssociation
-
Return the first association of the receiver.
Provide an error notification if the receiver contains no elements.
usage example(s):
OrderedDictionary new firstAssociation
OrderedDictionary new first
(OrderedDictionary new at:'one' put:1; yourself) first
(OrderedDictionary new at:'one' put:1; yourself) firstKey
(OrderedDictionary new at:'one' put:1; yourself) firstValue
|
-
firstKey
-
Return the first key of the receiver.
Raises an error if the receiver contains no elements.
usage example(s):
OrderedDictionary new first
OrderedDictionary new firstKey
OrderedDictionary new first
(OrderedDictionary new at:'one' put:1; yourself) first
(OrderedDictionary new at:'one' put:1; yourself) firstKey
(OrderedDictionary new at:'one' put:1; yourself) firstValue
OrderedDictionary new
at:'foo' put:'Foo';
at:'bar' put:'Bar';
first
OrderedDictionary new
at:'foo' put:'Foo';
at:'bar' put:'Bar';
firstKey
|
-
keyAt: index
-
get the key at the given index
-
keys
-
Return a OrderedCollection containing the receiver's keys.
-
last
-
Return the last value of the receiver.
Provide an error notification if the receiver contains no elements.
usage example(s):
OrderedDictionary new last
(OrderedDictionary new at:'one' put:1; yourself) last
(OrderedDictionary new at:'one' put:1; yourself) lastKey
(OrderedDictionary new at:'one' put:1; yourself) lastValue
|
-
lastAssociation
-
Return the last association of the receiver.
Provide an error notification if the receiver contains no elements.
usage example(s):
OrderedDictionary new lastAssociation
OrderedDictionary new last
(OrderedDictionary new at:'one' put:1; at:'two' put:2; at:'one' put:111; yourself) lastAssociation
(OrderedDictionary new at:'one' put:1; at:'two' put:2; at:'one' put:111; yourself) last
(OrderedDictionary new at:'one' put:1; at:'two' put:2; at:'one' put:111; yourself) lastKey
(OrderedDictionary new at:'one' put:1; at:'two' put:2; at:'one' put:111; yourself) lastValue
|
-
lastKey
-
Return the last key of the receiver.
Raises an error if the receiver contains no elements.
-
order
-
returns the keys in the order of their appearance
-
valueAt: index
-
get the value at the given index
-
values
-
Return a OrderedCollection containing the receiver's values.
adding
-
add: anAssociation after: oldAssociation
-
Add the argument, anAssociation, as an element of the dictionary. Put it
in the position just succeeding oldAssociation. Return anAssociation.
-
add: anAssociation before: oldAssociation
-
Add the argument, anAssociation, as an element of the dictionary. Put it
in the position just preceding oldAssociation. Return anAssociation.
-
add: anAssociation beforeIndex: spot
-
Add the argument, anAssociation, as an element of the receiver. Put it
in the position just preceding the indexed position spot. Return newObject.
-
addAll: aCollectionOfAssociations
-
Add each element of anOrderedCollectionOfAssociations at my end.
We expect the argument to enumerate associations with #reverseDo:;
if it does not (i.e. it is another OD or a dictionary), use #addAllAssociationsFirst:.
Returns the argument, aCollectionOfAssociations (sigh).
-
addAllAssociations: aDictionaryOrOrderedDictionary
-
Add each association of aDictionaryOrOrderedDictionary to my end.
We expect the argument to respond to #associationsDo:.
-
addAllAssociationsFirst: aDictionaryOrOrderedDictionary
-
Add each association of aDictionaryOrOrderedDictionary at the beginning of the
receiver. We expect the argument to respond to #associationsReverseDo:.
-
addAllAssociationsLast: aDictionaryOrOrderedDictionary
-
Add each association of aDictionaryOrOrderedDictionary at the end of the
receiver. We expect the argument to respond to #associationsDo:.
-
addFirst: anAssociation
-
Add anAssociation to the beginning of the receiver.
-
addLast: anAssociation
-
Add anAssociation to the end of the receiver.
If anAssociation is already present in the dictionary,
it will be moved to the end. (See also: #add:)
converting
-
asInlineObject
-
return the receiver as an inline-object (which understands getters and setters for my slots)
copying
-
copyEmpty
-
Return a copy of the receiver that contains no elements.
-
copyFrom: startIndex
-
Return a copy of the receiver that contains associations from
position startIndex to the end.
-
copyFrom: startIndex to: endIndex
-
Return a copy of the receiver that contains associations from
position startIndex to endIndex.
-
copyTo: endIndex
-
Return a copy of the receiver that contains associations from
the start to endIndex.
-
copyValuesFrom: startIndex
-
Return a copy of the receiver that contains values from
position startIndex to the end.
-
copyValuesFrom: startIndex to: endIndex
-
Return a copy of the receiver that contains values from
position startIndex to endIndex.
-
copyValuesTo: endIndex
-
Return a copy of the receiver that contains values from
the start to endIndex.
copying-private
-
postCopy
-
have to copy the order too
enumerating
-
associationsCollect: aBlock
-
Evaluate aBlock with each of the associations of the dictionary as argument,
and return a new (ordered) collection with the results
-
associationsDo: aBlock
-
Evaluate aBlock for each of the dictionary's associations.
Enumerate them in the order by which they were added.
See also:
#keysAndValuesDo: (which passes keys & values separately)
#keysDo: (which passes keys only)
#do: (which passes values only)
-
associationsDo: aBlock from: firstIndex to: secondIndex
-
Evaluate aBlock with each of the dictionary's associations from index
firstIndex to index secondIndex as the argument.
-
associationsReverseDo: aBlock
-
Evaluate aBlock for each of the dictionary's associations in reverse order.
-
associationsSelect: aBlock
-
Evaluate aBlock with each of the dictionary's associations as the argument.
Collect into a new OrderedDictionary only those associations for which
aBlock evaluates to true. Return the new OrderedDictionary.
-
collect: aBlock
-
Evaluate aBlock with each of the values of the dictionary as argument,
and return a new (ordered) collection with the results
-
detect: aBlock ifNone: anExceptionValue
-
evaluate the argument, aBlock for each element in the receiver until
the block returns true; in this case return the element which caused
the true evaluation.
If none of the evaluations returns true, return the value of anExceptionValue
-
do: aBlock
-
Evaluate aBlock for each of the dictionary's values.
Enumerate them in the order by which they were added.
-
do: aBlock from: firstIndex to: lastIndex
-
-
findFirst: aBlock ifNone: exceptionalValue
-
Return the index of the first association in the dictionary for which aBlock
evaluates as true. If the block does not evaluate to true, return exceptionalValue
-
findLast: aBlock
-
Return the index of the last association in the dictionary for which aBlock
evaluates as true. If the block does not evaluate to true, return 0
-
findLast: aBlock startingAt: startIndex
-
Return the index of the last association in the dictionary for which aBlock
evaluates as true. Start the backward search at startIndex.
If the block does not evaluate to true, return 0
-
findLast: aBlock startingAt: startIndex endingAt: endIndex
-
Return the index of the last association in the dictionary for which aBlock
evaluates as true. Start the search at startIndex.
End the search at endIndex or when an element is found.
If the block does not evaluate to true, return 0
-
from: firstIndex to: lastIndex do: aBlock
-
Evaluate aBlock with each of the dictionary's associations from index
firstIndex to index secondIndex as the argument.
-
keysAndValuesDetect: aBlock ifNone: exceptionBlock
-
evaluate the argument, aBlock for each key and value in the receiver,
until the block returns true;
in this case return the value which caused the true evaluation.
If none of the evaluations returns true, return the result of the
evaluation of the exceptionBlock
-
keysAndValuesDo: aBlock
-
perform the block for all keys and values in the collection.
Enumerate them in the order by which they were added.
See also:
#associationsDo: (which passes key-value associations)
#keysDo: (which passes keys only)
#do: (which passes values only)
WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.
-
keysAndValuesReverseDo: aBlock
-
perform the block for all keys and values in the collection.
Enumerate them in the reverse order from which they were added.
See also:
#associationsDo: (which passes key-value associations)
#keysAndValuesDo: (which passes keys & values separately)
#do: (which passes values only)
WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.
-
keysDo: aBlock
-
evaluate the argument, aBlock for every key in the collection.
Enumerate them in the order by which they were added.
See also:
#associationsDo: (which passes key-value associations)
#keysAndValuesDo: (which passes keys & values separately)
#do: (which passes values only)
WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.
-
reverseDo: aBlock
-
Evaluate aBlock with each of the dictionary's associations as the argument,
starting with the last added element and taking each in sequence up to the first.
-
reversed
-
Return with a new OrderedDictionary with its associations in reverse order.
-
select: aBlock
-
Evaluate aBlock with each of the dictionary's values as the argument.
Collect into a new OrderedDictionary only those associations for which
aBlock evaluated to true. Return the new OrderedDictionary.
initialization
-
initializeOrder: count
-
private
-
removeFromOrder: aKey
-
queries
-
occurrencesOfKey: aKey
-
Return how many of the dictionary's keys are equal to aKey.
-
occurrencesOfValue: aValue
-
Return how many of the dictionary's values are equal to aValue.
removing
-
clearContents
-
remove all elements from the receiver, but do not shrink. Returns the receiver.
-
removeFirst
-
remove the first element from the receiver.
Return the removed element.
Raise an error if the receiver is empty
-
removeFromIndex: fromIndex toIndex: toIndex
-
Returns the receiver.
-
removeIndex: anInteger
-
remove an element from the receiver.
Return the removed element.
Raise an error if the index is invalid
-
removeKey: aKey
-
remove the association under aKey from the collection,
return the value previously stored there.
If it was not in the collection report an error.
WARNING: do not remove elements while iterating over the receiver.
See #saveRemoveKey: to do this.
-
removeKey: aKey ifAbsent: aBlock
-
remove key (and the associated value) from the receiver,
return the value previously stored there.
If it was not in the collection return the result
from evaluating aBlock.
-
removeLast
-
remove the last element from the receiver.
Return the removed element.
Raise an error if the receiver is empty
searching
-
identityIndexOfAssociation: anAssociation
-
Return the identity index of anAssociation within the receiver. If the receiver
does not contain anAssociation, return 0.
-
identityIndexOfAssociation: anAssociation ifAbsent: exceptionBlock
-
Return the identity index of anAssociation within the receiver.
If the receiver does not contain anAssociation,
return the result of evaluating the exceptionBlock.
-
identityIndexOfKey: aKey
-
Return the identity index of aKey within the receiver. If the receiver
does not contain aKey, return 0.
-
identityIndexOfKey: aKey ifAbsent: exceptionBlock
-
Return the identity index of aKey within the receiver. If the receiver does
not contain aKey, return the result of evaluating the exceptionBlock.
-
identityIndexOfValue: aValue
-
Return the identity index of aValue within the receiver. If the receiver
does not contain aValue, return 0.
-
identityIndexOfValue: aValue ifAbsent: exceptionBlock
-
Return the identity index of aValue within the receiver. If the receiver
does not contain aValue, return the result of evaluating the exceptionBlock.
-
indexOfAssociation: anAssociation
-
Return the index of anAssociation within the receiver. If the receiver does
not contain anAssociation, return 0.
-
indexOfAssociation: anAssociation ifAbsent: exceptionBlock
-
Return the identity index of anAssociation within the receiver. If the receiver
does not contain anAssociation, return the result of evaluating the exceptionBlock.
-
indexOfKey: aKey
-
Return the index of aKey within the receiver. If the receiver does
not contain aKey, return 0.
-
indexOfKey: aKey ifAbsent: exceptionBlock
-
Return the identity index of aKey within the receiver. If the receiver does
not contain aKey, return the result of evaluating the exceptionBlock.
-
indexOfValue: aValue
-
Return the index of aValue within the receiver.
If the receiver does not contain aValue, return 0.
-
indexOfValue: aValue ifAbsent: exceptionBlock
-
Return the identity index of aValue within the receiver.
If the receiver does not contain aValue, return the result of evaluating the exceptionBlock.
-
nextIndexOfAssociation: aAssociation from: startIndex to: stopIndex
-
Return the next index of aAssociation within the receiver between startIndex
and stopIndex. If the receiver does not contain aAssociation, return nil
-
nextIndexOfKey: aKey from: startIndex to: stopIndex
-
Return the next index of aKey within the receiver between startIndex and
stopIndex. If the receiver does not contain aKey, return nil
-
nextIndexOfValue: aValue from: startIndex to: stopIndex
-
Return the next index of aValue within the receiver between startIndex and
stopIndex. If the receiver does not contain aValue, return nil
-
prevIndexOfAssociation: aAssociation from: startIndex to: stopIndex
-
Return the previous index of aAssociation within the receiver between
startIndex and stopIndex working backwards through the receiver.
If the receiver does not contain aAssociation, return nil
-
prevIndexOfKey: aKey from: startIndex to: stopIndex
-
Return the previous index of aKey within the receiver between startIndex and
stopIndex working backwards through the receiver.
If the receiver does not contain aKey, return nil
-
prevIndexOfValue: aValue from: startIndex to: stopIndex
-
Return the previous index of aValue within the receiver between startIndex
and stopIndex working backwards through the receiver.
If the receiver does not contain aValue, return nil
sorting & reordering
-
reverse
-
Destructively reverse my order.
WARNING: this is a destructive operation, which modifies the receiver.
Please use reversed (with a d) for a functional version.
-
sort
-
Destructively sort my order.
WARNING: this is a destructive operation, which modifies the receiver
-
sort: aSortBlock
-
Destructively sort my order.
WARNING: this is a destructive operation, which modifies the receiver
testing
-
isOrdered
-
return true, if the receiver's elements are ordered.
Re-redefined to true here, as I do have an order
|o|
o := OrderedDictionary new.
o at:'one' put:1.
o at:'two' put:2.
o at:'three' put:3.
o at:'four' put:4.
o at:'five' put:5.
o at:'six' put:6.
o at:'seven' put:7.
o at:'eight' put:8.
o at:'nine' put:9.
o at:'zero' put:0.
o at:'eight'.
o atIndex:1.
o atIndex:5.
o atIndex:10.
o from:3 to:6 do:[:each | Transcript showCR:each ].
o collect:[:eachValue | eachValue squared].
o associationsCollect:[:eachAssoc | eachAssoc key -> eachAssoc value squared].
o associations.
o order.
o reverse.
o atIndex:1.
o atIndex:5.
o atIndex:10.
|