"       NAME            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). 

"!

'From Smalltalk-80, Version 2.4 of 28 January 1989 on 28 March 1990 at 11:32:50 am'!

Dictionary subclass: #OrderedDictionary

	instanceVariableNames: 'order '

	classVariableNames: ''

	poolDictionaries: ''

	category: 'Collections-Sequenceable'

!

OrderedDictionary comment:

'I am a subclass of Dictionary whose elements (associations) are ordered in a

 similar fashion to OrderedCollection.

I have one instance variable:

order <OrderedCollection>       Ordered collection of keys reflecting the order of

				associations in the dictionary. '

!

!OrderedDictionary methodsFor: 'adding'!

add: anAssociation 

	"add anAssociation to the dictionary"

	| key |

	key := anAssociation key.

	(super includesKey: key)

		ifFalse: [order add: key].

	super add: anAssociation

!

add: anAssociation after: oldAssociation 

	"Add the argument, anAssociation, as an element of the dictionary. Put it 

	in the position just succeeding oldAssociation. Return anAssociation."

	| index |

	index := self indexOfAssociation: oldAssociation 

				ifAbsent: [self error: 'association not found'].

	self removeFromOrder: anAssociation key.

	order add: anAssociation key after: (order at: index).

	super add: anAssociation.

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

	| index |

	index := self indexOfAssociation: oldAssociation 

				ifAbsent: [self error: 'association not found'].

	self removeFromOrder: anAssociation key.

	order add: anAssociation key before: (order at: index).

	super add: anAssociation.

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

	self removeFromOrder: anAssociation key.

	order add: anAssociation key beforeIndex: spot.

	super add: anAssociation

    "Modified: 28.9.1995 / 14:06:53 / stefan"

!

addAll: aCollectionOfAssociations 

	"Add each element of aCollectionOfAssociations at my end."

	aCollectionOfAssociations associationsDo: [:elems | self add: elems]

!

addAllFirst: anOrderedCollectionOfAssociations 

	"Add each element of anOrderedCollectionOfAssociations at the beginning 

	 of the receiver."

	anOrderedCollectionOfAssociations reverseDo: [:each | self addFirst: each]

!

addAllLast: anOrderedCollectionOfAssociations 

	"Add each element of anOrderedCollectionOfAssociations at the end of the 

	receiver."

	anOrderedCollectionOfAssociations do: [:each | self addLast: each]

!

addFirst: anAssociation 

	"Add anAssociation to the beginning of the receiver."

	self removeFromOrder: anAssociation key.

	order addFirst: anAssociation key.

	super add: anAssociation.

!

addLast: anAssociation 

	"Add anAssociation to the end of the receiver."

	self removeFromOrder: anAssociation key.

	order addLast: anAssociation key.

	super add: anAssociation.

"/!

"/

"/grow

"/        "Increase the number of elements in the dictionary"

"/

"/        ^ super grow

"/

"/        | newSelf |

"/

"/        newSelf := (self class) new: (self basicSize + self growSize).

"/        order do: [:key | newSelf add: (self associationAt: key)].

"/        self become: newSelf

"/

! !

!OrderedDictionary methodsFor: 'enumerating'!

associationsDo: aBlock 

	"Evaluate aBlock for each of the dictionary's associations."

	order do: [:key | aBlock value: (self associationAt: key)]

!

associationsDo: aBlock from: firstIndex to: secondIndex 

	"Evaluate aBlock with each of the dictionary's associations from index 

	firstIndex to index secondIndex as the argument."

	firstIndex to: secondIndex do: [:index | 

	    aBlock value: (self associationAt: (order at: index))

	]

!

collect: aBlock 

	"Evaluate aBlock with each of the associations of the dictionary as the 

	argument. The block should return an association which will be added to the

	new OrderedDictionary"

	| newDict |

	newDict := OrderedDictionary new.

	1 to: order size do: [:index | 

	    newDict add: (aBlock value: (self associationAt: (order at: index)))

	].

	^ newDict

!

do: aBlock 

	"Evaluate aBlock for each of the dictionary's values."

	order do: [:key | aBlock value: (self at: key)]

!

do: aBlock from: firstIndex to: secondIndex 

	"Evaluate aBlock with each of the dictionary's associations from index 

	firstIndex to index secondIndex as the argument."

	firstIndex to: secondIndex do: [:index | 

	    aBlock value: (self at: (order at: index))

	]

!

findFirst: aBlock 

	"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 0"

	1 to: order size do: [:index | 

	    (aBlock value: (self associationAt: (order at: index))) ifTrue: [^index]

	].

	^ 0

!

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"

	order size to: 1 by: -1 do: [:index | 

	    (aBlock value: (self associationAt: (order at: index))) ifTrue: [^index]

	].

	^ 0

!

reverse

	"Return with a new OrderedDictionary with its associations in reverse order."

	| newDict|

	newDict := OrderedDictionary new.

	order size to: 1 by: -1 do:[:index | 

	    |key|

	    key := order at: index.

	    newDict at: key put: (self at: key)

	].

	^newDict

!

reverseDo: aBlock 

	"Evaluate aBlock with each of the dictionary's associations as the argument,

	starting with the last element and taking each in sequence up to the first."

	order size to: 1 by: -1 do: [:index | 

	    aBlock value: (self associationAt: (order at: index))

	]

!

select: 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."

	| newDict|

	newDict := OrderedDictionary new.

	1 to: order size do:[:index | 

	    |key assoc|

	    key := order at: index.

	    assoc := self associationAt: key.

	    (aBlock value: assoc) ifTrue: [

		newDict add: assoc

	    ]

	].

	^newDict

! !

!OrderedDictionary methodsFor: 'accessing index'!

identityIndexOfAssociation: anAssociation 

	"Return the identity index of anAssociation within the receiver. If the receiver

	does not contain anAssociation, return 0."

	^self identityIndexOfAssociation: anAssociation ifAbsent: [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."

	1 to: order size do: [:i | 

	    (self associationAt: (order at: i)) == anAssociation ifTrue: [^i]

	].

	^exceptionBlock value

!

identityIndexOfKey: aKey 

	"Return the identity index of aKey within the receiver. If the receiver 

	does not contain aKey, return 0."

	^self identityIndexOfKey: aKey ifAbsent: [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."

	1 to: order size do: [:i | (order at: i) == aKey ifTrue: [^i]].

	^exceptionBlock value

!

identityIndexOfValue: aValue 

	"Return the identity index of aValue within the receiver. If the receiver 

	does not contain aValue, return 0."

	^self identityIndexOfValue: aValue ifAbsent: [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."

	1 to: order size do: [:i | 

	    (self at: (order at: i)) == aValue ifTrue: [^i]].

	^exceptionBlock value

!

indexOfAssociation: anAssociation 

	"Return the index of anAssociation within the receiver. If the receiver does

	not contain anAssociation, return 0."

	^self indexOfAssociation: anAssociation ifAbsent: [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."

	1 to: order size do: [:i | 

	    (self associationAt: (order at: i)) = anAssociation ifTrue: [^i]

	].

	^exceptionBlock value

!

indexOfKey: aKey 

	"Return the index of aKey within the receiver. If the receiver does 

	not contain aKey, return 0."

	^self indexOfKey: aKey ifAbsent: [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."

	1 to: order size do: [:i | (order at: i) = aKey ifTrue: [^i]].

	^exceptionBlock value

!

indexOfValue: aValue 

	"Return the index of aValue within the receiver. If the receiver does 

	not contain aValue, return 0."

	^self indexOfValue: aValue ifAbsent: [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."

	1 to: order size do: [:i | 

	    (self at: (order at: i)) = aValue ifTrue: [^i]].

	^exceptionBlock value

!

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"

	startIndex to: stopIndex do: [:i | 

	    (self associationAt: (order at: i)) = aAssociation ifTrue: [^i]].

	^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"

	startIndex to: stopIndex do: [:i | 

	    (order at: i) = aKey ifTrue: [^i]].

	^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"

	startIndex to: stopIndex do: [:i | 

	    (self at: (order at: i)) = aValue ifTrue: [^i]].

	^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"

	startIndex

		to: stopIndex

		by: -1

		do: [:i | (self associationAt: (order at: i))

				= aAssociation ifTrue: [^i]].

	^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"

	startIndex

		to: stopIndex

		by: -1

		do: [:i | (order at: i)

				= aKey ifTrue: [^i]].

	^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"

	startIndex

		to: stopIndex

		by: -1

		do: [:i | (self at: (order at: i))

				= aValue ifTrue: [^i]].

	^nil! !

!OrderedDictionary methodsFor: 'testing'!

occurrencesOfKey: aKey 

	"Return how many of the dictionary's keys are equal to aKey."

	| count |

	count := 0.

	1 to: self size do: [:index | aKey = (order at: index) ifTrue: [count := count

 + 1]].

	^count!

occurrencesOfValue: aValue 

	"Return how many of the dictionary's values are equal to aValue."

	| count |

	count := 0.

	1 to: self size do: [:index | aValue = (self at: (order at: index)) ifTrue:

 [count := count + 1]].

	^count! !

!OrderedDictionary methodsFor: 'accessing'!

after: anAssociation 

	"Return the association after anAssociation in the order. If anAssociation is

 the 

	last association in the order, return the undefined object. If anAssociation

 is 

	not found, invoke an error notifier"

	1 to: order size - 1 do: [:index | (self associationAt: (order at: index))

			= anAssociation ifTrue: [^self associationAt: (order at: index + 1)]].

	(self associationAt: (order last))

		= anAssociation

		ifTrue: [^nil]

		ifFalse: [^self error: 'not found']!

associations

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

	| anOrderedCollection |

	anOrderedCollection := OrderedCollection new: order size.

	order do: [:key | anOrderedCollection add: (self associationAt: key)].

	^anOrderedCollection!

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 is value to anObject. Return anObject."

	(order includes: key)

		ifFalse: [order add: key].

	super at: key put: anObject!

atAll: anInterval put: anObject 

	"Put anObject into the value field of every association specified by the interval"

	anInterval do: [:index | self at: (order at: index)

			put: anObject]!

atAllPut: anObject 

	"Put anObject into the value field of every association in the dictionary"

	order do: [:key|  self at: key put: anObject]!

atIndex:index

    "return an element at a given index"

    ^ self at:(order at:index)

    "Created: 28.9.1995 / 13:49:39 / stefan"

!

atIndex:index put:anAssociation

    "put an association to a given index. remove the old associatioan at this index"

    |key|

    key := anAssociation key.

    (super includesKey:key) ifTrue:[

	^ self error:'duplicate key'.

    ].

    super removeKey:(order at:index) ifAbsent:[].