Smalltalk/X Webserver

Documentation of class 'OrderedDictionary':

Class: OrderedDictionary

Inheritance
Description
Class protocol
- instance creation
Instance protocol
Examples

Inheritance:

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

Package:: stx:libbasic

Category:: Collections-Sequenceable

Version:: rev: 1.99 date: 2023/12/15 13:57:36; user: stefan; file: OrderedDictionary.st directory: libbasic; module: stx stc-classLibrary: libbasic

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)
    

copyrightCOPYRIGHT.
This is a Manchester Goodie protected by copyright.
These conditions are imposed on the whole Goodie, and on any significant
part of it which is separately transmitted or stored:
       * You must ensure that every copy includes this notice, and that
         source and author(s) of the material are acknowledged.
       * These conditions must be imposed on anyone who receives a copy.
       * The material shall not be used for commercial gain without the prior
         written consent of the author(s).
Further information on the copyright conditions may be obtained by
sending electronic mail:
       To: goodies-lib@cs.man.ac.uk
       Subject: copyright
or by writing to The Smalltalk Goodies Library Manager, Dept of
Computer Science, The University, Manchester M13 9PL, UK

(C) Copyright 1992 University of Manchester
For more information about the Manchester Goodies Library (from which 
this file was distributed) send e-mail:
       To: goodies-lib@cs.man.ac.uk
       Subject: help 

infoNAME            OrderedDictionary
AUTHOR          Ifor Wyn Williams <ifor@uk.ac.man.cs>
CONTRIBUTOR     Ifor Wyn Williams <ifor@uk.ac.man.cs>
FUNCTION        An ordered dictionary
ST-VERSIONS     2.3-5, 4.0
PREREQUISITES   
CONFLICTS       
DISTRIBUTION    global
VERSION         1.2
DATE            28.3.90
SUMMARY         A dictionary that behaves like a SequencableCollection
                (except that associations cannot be removed).

Class protocol:

instance creation

new: anInteger

(comment from inherited method)
return a new empty Set with space for anInteger elements

newFromObject: anObject

return a new instance with slots named after anObject's instance variables.

Usage example(s):

     OrderedDictionary newFromObject:(100 @ 200)

Instance protocol:

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.

Usage example(s):

     |d|

     d := OrderedDictionary new.
     d at:'one'  ifAbsent:0 update:[:val | val + 1].
     d at:'two'  ifAbsent:0 update:[:val | val + 1].
     d at:'three' ifAbsent:0  update:[:val | val + 1].
     d at:'one' ifAbsent:0  update:[:val | val + 1].
     d at:'two' ifAbsent:0  update:[:val | val + 1].
     d

at: aKey ifAbsentPut: valueBlock

return the element indexed by aKey if present,
if not present, store the result of evaluating valueBlock
under aKey and return it.
WARNING: do not add elements while iterating over the receiver.
Iterate over a copy to do this.

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

if the receiver contains an element stored under aKey,
retrieve it and evaluate aBlock passing the element as argument,
returning the block's value.
If no element was stored under that key, store aValue under the key.
Use this with an error-reporting block, to ensure that no keys are reused

Usage example(s):

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

Usage example(s):

     |d|

     d := Dictionary 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

Usage example(s):

     |s|

     s := OrderedDictionary new.
     s at:#a put:'aaa'; at:#b put:'bbb'; at:#c put:'ccc'; at:#d put:'ddd'; at:#a put:'aaaa'.
     s keyAt:2

keys

Return a OrderedCollection containing the receiver's keys.

Usage example(s):

     |s|

     s := OrderedDictionary new.
     s at:#a put:'aaa'; at:#b put:'bbb'; at:#c put:'ccc'; at:#d put:'ddd'; at:#a put:'aaaa'.
     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

Usage example(s):

     |s|

     s := OrderedDictionary new.
     s at:#a put:'aaa'; at:#b put:'bbb'; at:#c put:'ccc'; at:#d put:'ddd'; at:#a put:'aaaa'.
     s order

valueAt: index

get the value at the given index

** This is an obsolete interface - do not use it (it may vanish in future versions) **

valueAtIndex: index

get the value at the given index

valueAtIndex: index put: newValue

set 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.
Make sure, that the key in
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: start to: end: 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: firstIndexArg to: secondIndexArg

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

** This is an obsolete interface - do not use it (it may vanish in future versions) **

doWithIndex: aBlock

Squeak/V'Age compatibility;
like keysAndValuesDo:, but passes the index as second argument.
Same as withIndexDo:, due to parallel evolution of different Smalltalk dialects

Usage example(s):

     |d|
     d := OrderedDictionary new.
     d at:'z' put:'ZZZ'.
     d at:'b' put:'BBB'.
     d at:'a' put:'AAA'.
     d doWithIndex:[:val :idx | Transcript showCR:'idx: %1 val: %2' with:idx with:val].

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

initializeForCapacity: minSize: initialize the contents array (for at least minSize slots)
and set tally to zero.
The size is increased to the next prime for better hashing behavior.
initializeOrder: count

private

removeFromOrder: aKey: ** This is an obsolete interface - do not use it (it may vanish in future versions) **

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.

dropAllSuchThat: conditionBlockOnValueOrKeyAndValue

Apply the condition block to each key and value (if it is a 2-arg block)
or to each value (if it is a one arg block)
and drop the entry (key and value) if the condition is true.
Returns the receiver.
Differs from #removeAllSuchThat:
returns self instead of the removed associations.

Usage example(s):

     |d|

     d := OrderedDictionary new.
     d at:'one' put:1.
     d at:'two' put:2.
     d at:'three' put:3.
     d at:'four' put:4.
     d at:'uno' put:1.
     d at:'due' put:2.
     d at:'tre' put:3.
     d at:'eins' put:1.
     d at:'zwei' put:2.
     d at:'drei' put:3.

     d dropAllSuchThat:[:k :v | k startsWith:'t'].
     d dropAllSuchThat:[:k :v | v = 2].
     d inspect

removeAllSuchThat: conditionBlockOnValueOrKeyAndValue

Apply the condition block to each key and value (if it is a 2-arg block)
or to each value (if it is a one arg block)
and remove the entry (key and value) if the condition is true.
Return a collection of removed associations.

Usage example(s):

     |d|

     d := OrderedDictionary new.
     d at:'one' put:1.
     d at:'two' put:2.
     d at:'three' put:3.
     d at:'four' put:4.
     d at:'uno' put:1.
     d at:'due' put:2.
     d at:'tre' put:3.
     d at:'eins' put:1.
     d at:'zwei' put:2.
     d at:'drei' put:3.

     d removeAllSuchThat:[:k :v | k startsWith:'t'].
     d removeAllSuchThat:[:k :v | v = 2].
     d inspect

removeFirst

remove the first element from the receiver.
Return the removed element.
Raise an error if the receiver is empty

removeFirstIfAbsent: exceptionBlock

remove the first element from the receiver.
Return the removed element or the value of exceptionBlock, 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 #safeRemoveKey: 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

safeRemoveKey: aKey

remove the association under aKey from the collection,
return the value previously stored there.
If it was not in the collection return nil.

In contrast to #removeKey:, this does not resize the underlying collection
and therefore does NOT rehash & change the elements order.
Therefore this can be used while enumerating the receiver,
which is not possible if #removeKey: is used.

WARNING: since no resizing is done, the physical amount of memory used
by the container remains the same, although the logical size shrinks.
You may want to manually resize the receiver using #possiblyShrink
after the enumeration.

WARNING: this is not really safe, since order will be changed!

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
isSequenceable: return true if the receiver is sequenceable;
i.e. if its elements are accessible by by at:/at:put: and an integer index,
and support the do:-protocol.

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.7.0.0; WebServer 1.702 at 20f6060372b9.unknown:8081; Mon, 18 Nov 2024 04:20:51 GMT