eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'OrderedDictionary':

Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: OrderedDictionary


Inheritance:

   Object
   |
   +--Collection
      |
      +--Set
         |
         +--Dictionary
            |
            +--OrderedDictionary

Package:
stx:libbasic
Category:
Collections-Sequenceable
Version:
rev: 1.63 date: 2018/05/17 19:32:49
user: cg
file: OrderedDictionary.st directory: libbasic
module: stx stc-classLibrary: libbasic
Author:
Ifor Wyn Williams <ifor@uk.ac.man.cs>
Changed by: exept

Description:


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)
    


Related information:

    OrderedCollection
    Dictionary
    OrderedSet

Class protocol:

instance creation
o  new: anInteger


Instance protocol:

accessing
o  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

o  associations
Return an OrderedCollection containing the receiver's associations.

o  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.

o  at: aKey ifAbsentPut: valueBlock

o  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.

o  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 ].

o  atAll: indexCollection put: anObject
Put anObject into the value field of every association specified by indexCollection,
which is typically an interval.

o  atAllPut: anObject
Put anObject into the value field of every association in the dictionary

o  atIndex: index
return an element at a given index

o  atIndex: index ifAbsent: aBlock
return an element at a given index

o  atIndex: index put: anAssociation
put an association to a given index. remove the old association at this index

o  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

o  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

o  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

o  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

o  keyAt: index
get the key at the given index

o  keys
Return a OrderedCollection containing the receiver's keys.

o  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

o  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

o  lastKey
Return the last key of the receiver.
Raises an error if the receiver contains no elements.

o  order
returns the keys in the order of their appearance

o  valueAt: index
get the value at the given index

o  values
Return a OrderedCollection containing the receiver's values.

adding
o  add: anAssociation after: oldAssociation
Add the argument, anAssociation, as an element of the dictionary. Put it
in the position just succeeding oldAssociation. Return anAssociation.

o  add: anAssociation before: oldAssociation
Add the argument, anAssociation, as an element of the dictionary. Put it
in the position just preceding oldAssociation. Return anAssociation.

o  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.

o  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).

o  addAllAssociations: aDictionaryOrOrderedDictionary
Add each association of aDictionaryOrOrderedDictionary to my end.
We expect the argument to respond to #associationsDo:.

o  addAllAssociationsFirst: aDictionaryOrOrderedDictionary
Add each association of aDictionaryOrOrderedDictionary at the beginning of the
receiver. We expect the argument to respond to #associationsReverseDo:.

o  addAllAssociationsLast: aDictionaryOrOrderedDictionary
Add each association of aDictionaryOrOrderedDictionary at the end of the
receiver. We expect the argument to respond to #associationsDo:.

o  addFirst: anAssociation
Add anAssociation to the beginning of the receiver.

o  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:)

copying
o  copyEmpty
Return a copy of the receiver that contains no elements.

o  copyFrom: startIndex to: endIndex
Return a copy of the receiver that contains elements from
position startIndex to endIndex.

o  copyWithout: anAssociation
Return a copy of the dictionary that is 1 smaller than the receiver and
does not include the argument, anAssociation
No error is reported, if elementToSkip is not in the collection.

o  postCopy
have to copy the order too

enumerating
o  associationsCollect: aBlock
Evaluate aBlock with each of the associations of the dictionary as argument,
and return a new (ordered) collection with the results

o  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)

o  associationsDo: aBlock from: firstIndex to: secondIndex
Evaluate aBlock with each of the dictionary's associations from index
firstIndex to index secondIndex as the argument.

o  associationsReverseDo: aBlock
Evaluate aBlock for each of the dictionary's associations in reverse order.

o  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.

o  collect: aBlock
Evaluate aBlock with each of the values of the dictionary as argument,
and return a new (ordered) collection with the results

o  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

o  do: aBlock
Evaluate aBlock for each of the dictionary's values.
Enumerate them in the order by which they were added.

o  do: aBlock from: firstIndex to: lastIndex

o  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

o  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

o  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

o  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

o  from: firstIndex to: lastIndex do: aBlock
Evaluate aBlock with each of the dictionary's associations from index
firstIndex to index secondIndex as the argument.

o  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

o  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.

o  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.

o  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.

o  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.

o  reversed
Return with a new OrderedDictionary with its associations in reverse order.

o  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
o  initializeOrder: count

private
o  removeFromOrder: aKey

queries
o  occurrencesOfKey: aKey
Return how many of the dictionary's keys are equal to aKey.

o  occurrencesOfValue: aValue
Return how many of the dictionary's values are equal to aValue.

removing
o  clearContents
remove all elements from the receiver, but do not shrink. Returns the receiver.

o  removeFirst
error if collection is empty

o  removeFromIndex: fromIndex toIndex: toIndex
Returns the receiver.

o  removeIndex: anInteger

o  removeKey: aKey

o  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.

o  removeLast
error if collection is empty

searching
o  identityIndexOfAssociation: anAssociation
Return the identity index of anAssociation within the receiver. If the receiver
does not contain anAssociation, return 0.

o  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.

o  identityIndexOfKey: aKey
Return the identity index of aKey within the receiver. If the receiver
does not contain aKey, return 0.

o  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.

o  identityIndexOfValue: aValue
Return the identity index of aValue within the receiver. If the receiver
does not contain aValue, return 0.

o  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.

o  indexOfAssociation: anAssociation
Return the index of anAssociation within the receiver. If the receiver does
not contain anAssociation, return 0.

o  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.

o  indexOfKey: aKey
Return the index of aKey within the receiver. If the receiver does
not contain aKey, return 0.

o  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.

o  indexOfValue: aValue
Return the index of aValue within the receiver.
If the receiver does not contain aValue, return 0.

o  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.

o  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

o  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

o  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

o  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

o  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

o  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
o  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.

o  sort
Destructively sort my order.
WARNING: this is a destructive operation, which modifies the receiver

o  sort: aSortBlock
Destructively sort my order.
WARNING: this is a destructive operation, which modifies the receiver

testing
o  isOrdered
return true, if the receiver's elements are ordered.
Re-redefined to true here, as I do have an order


Examples:


|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.

ST/X 7.1.0.0; WebServer 1.663 at exept.de:8081; Wed, 19 Sep 2018 12:44:09 GMT