"

 COPYRIGHT.

 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 

"

"{ Package: 'stx:libbasic' }"

"{ NameSpace: Smalltalk }"

Dictionary subclass:#OrderedDictionary

	instanceVariableNames:'order'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Sequenceable'

!

!OrderedDictionary class methodsFor:'documentation'!

copyright

"

 COPYRIGHT.

 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 

"

!

documentation

"

    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: O(n)

        insertion: mostly O(1)

        removal: mostly O(N) (because order will have O(n) behavior)

    [author:]

        Ifor Wyn Williams <ifor@uk.ac.man.cs>

        Changed by: exept

    [see also:]

        OrderedCollection Dictionary

        OrderedSet

"

!

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:[:eachAssoc | eachAssoc key -> eachAssoc value squared]. 

    o associations.  

    o order.         

    o reverse.    

    o atIndex:1.  

    o atIndex:5. 

    o atIndex:10. 

"

!

info

"

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

"

! !

!OrderedDictionary class methodsFor:'instance creation'!

new:anInteger

    ^ (super new:anInteger) initializeOrder:anInteger

! !

!OrderedDictionary methodsFor:'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"

    |sz "{ Class:SmallInteger }"|

    sz := order size.

    1 to:sz do:[:index | 

        (self associationAt:(order at:index)) = anAssociation ifTrue:[

            index == sz ifTrue:[^ nil].

            ^ self associationAt:(order at:index + 1)

        ]

    ].

    ^ self errorNotFound:anAssociation.

!

associations

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

    ^ order collect: [:key | self associationAt: key ].

!

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

    ^ self at:aKey put:(aBlock value:(self at:aKey ifAbsent:default)).

    "

     |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

    ^ self at:aKey ifAbsent:[self at:aKey put:valueBlock value]

!

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

    (self includesKey: key) ifFalse:[order add: key].

    ^ super at:key put:anObject

!

at:aKey put:aValue ifPresent:aBlock

    |v|

    v := self at:aKey ifAbsent:[^ self at:aKey put:aValue].

    ^ aBlock value:v.

    "

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

    "

    "

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

    indexCollection 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 | super 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 ifAbsent:aBlock

    "return an element at a given index"

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

!

atIndex:index put:anAssociation

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

    |key|

    key := anAssociation key.

    (super includesKey:key) ifTrue:[

        ^ self error:'duplicate key'.

    ].

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

    order at:index put:key.

    super at:key put:anAssociation value.

    ^ anAssociation.

    "Created: 28.9.1995 / 16:30:15 / stefan"

!

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"

    |sz "{ Class:SmallInteger }"|

    sz := order size.

    1 to:sz do:[:index | 

        (self associationAt:(order at:index)) = anAssociation ifTrue:[

            index == 1 ifTrue:[^ nil].

            ^ self associationAt:(order at:index - 1)

        ]

    ].

    ^ self errorNotFound:anAssociation.

!

first

    "Return the first association of the receiver.  

     Provide an error notification if the receiver contains no elements."

    ^ self associationAt: (order first)

    "

        OrderedDictionary new first

    "

!

keyAt:index

    "get the key at the given index"

    ^ order at:index.

    "

     |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    

    "

    "Created: 29.9.1995 / 11:32:07 / stefan"

!

keys

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

    ^ order copy.

    "

     |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 association of the receiver. 

     Provide an error notification if the receiver contains no elements."

    ^ self associationAt: (order last)

    "

        OrderedDictionary new last

    "

!

order

    "returns the keys in the order of their appearance"

    ^ order

    "

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

    ^ self at:(order at:index).

    "

     |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 valueAt:2       

    "

!

values

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

    ^ order collect:[:key | self at:key].

! !

!OrderedDictionary methodsFor:'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."

    | index key |

    index := self indexOfAssociation: oldAssociation 

                            ifAbsent: [^ self errorNotFound:anAssociation].

    key := anAssociation key.

    order remove:key ifAbsent:[].

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

    super at:key put:anAssociation value.

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

    index := self indexOfAssociation: oldAssociation 

                            ifAbsent: [^ self errorNotFound:anAssociation].

    key := anAssociation key.

    order remove:key ifAbsent:[].

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

    super at:key put:anAssociation value.

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

    |key|

    key := anAssociation key.

    order remove:key ifAbsent:[].

    order add:key beforeIndex:spot.

    super at:key put:anAssociation value.

    ^ anAssociation

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

!

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

    ^ self addAllLast:aCollectionOfAssociations.

    "Modified: 28.2.1997 / 15:51:23 / cg"

!

addAllAssociations:aDictionaryOrOrderedDictionary

    "Add each association of aDictionaryOrOrderedDictionary to my end.

     We expect the argument to respond to #associationsDo:."

    ^ self addAllAssociationsLast:aDictionaryOrOrderedDictionary.

    "Created: 28.2.1997 / 15:52:02 / cg"

!

addAllAssociationsFirst:aDictionaryOrOrderedDictionary

    "Add each association of aDictionaryOrOrderedDictionary at the beginning of the 

     receiver. We expect the argument to respond to #associationsReverseDo:."

    aDictionaryOrOrderedDictionary associationsReverseDo:[:each | self addFirst:each].

    ^ aDictionaryOrOrderedDictionary

    "Created: 28.2.1997 / 15:50:14 / cg"

!

addAllAssociationsLast:aDictionaryOrOrderedDictionary

    "Add each association of aDictionaryOrOrderedDictionary at the end of the 

     receiver. We expect the argument to respond to #associationsDo:."

    aDictionaryOrOrderedDictionary associationsDo:[:each | self addLast:each].

    ^ aDictionaryOrOrderedDictionary

    "Created: 28.2.1997 / 15:48:37 / cg"

!

addFirst:anAssociation 

    "Add anAssociation to the beginning of the receiver."

    |key|

    key := anAssociation key.

    order remove:key ifAbsent:[].

    order addFirst:key.

    super at:key put:anAssociation value.

    ^ anAssociation

!

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

    |key|

    key := anAssociation key.

    order remove:key ifAbsent:[].

    order add:key.

    super at:key put:anAssociation value.

    ^ anAssociation

! !

!OrderedDictionary methodsFor:'copying'!

copyEmpty

    "Return a copy of the receiver that contains no elements."

    ^ self species new: 10

!

copyFrom:startIndex to:endIndex