View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

Fall01 Final Exam Review: Transposing a Dictionary

Back to Final Exam Review - Fall2001







Alright, so let's assume we have a Dictionary, "myDict" that contains all the initial stuff.(i.e. a Dictionary('Barney'->'Betty' 'Fred'->'Wilma' 'George'->'Martha' 'Ozzie'->'Harriet' ) ).



This code will transpose it:



(myDict keys) do:[:currKey| myDict at:(myDict at:currKey) put:currKey.myDict removeKey:currKey].



Yinka Alaran

Why not use keysDo:? Mark Guzdial

keysDo: will NOT work for the same reson that i mentioned below Rocky's example. you ABSOLUTELY CAN'T expect to be able to chage an object while you are iterating though it becuase you don't know internally how that iteration is implemented (ie sychnronized or not). Jason Fulghum



I think the previous code needs a little adjustment. Let's say one key/value pair was 'Wilma'->'Wilma'. It would be added and then immediately removed. Here is a small modification that should fix the problem.



myDict keysAndValuesDo: [:k :v | myDict removeKey: k. myDict at: v put: k. ].



Rocky Dunlap

i just tried this in squeak and it doesn't work correctly. If you try it, you will see that only half of the names are switched. I think this is because of the implementation of the keysAndValuesDo method. You have the same problem in Java when you try to modify and enumerator while it's in the process of enumerating. it gets confused because it's elements are moving around while it's trying to step through them.



Jason Fulghum

I agree with you Jason, keysDo: didn't work exactly like I thought it would(it only transposes about half of the dictionary elements). I tried:

myDict keysDo:[:currKey| myDict at:(myDict at:currKey)put:currKey.myDict removeKey:currKey].

Rocky, I guess this would fix the little inefficiency you reported.

(myDict keys) do:[:currKey| ((myDict at: currKey)=currKey) ifFalse:[myDict at:(myDict at:currKey) put:currKey.myDict removeKey:currKey].].

Yinka Alaran

(myDict copy) keysAndValuesDo: [ :key :value | myDict remove:key. (myDict at: key) put: value) ].
Four monkeys and a bag of bannanas


"Here is my answer"
d keys do: [:key | | element | element _ d at: key. d keysAndValuesRemove: [:tKey :value | tKey == key]. d at: element put: key.].

Here is the commend for keysAndValuesRemove, it helps explain much:
keysAndValuesRemove: keyValueBlock
"Removes all entries for which keyValueBlock returns true."
"When removing many items, you must not do it while iterating over the dictionary, since it may be changing. This method takes care of tallying the removals in a first pass, and then performing all the deletions afterward. Many places in the sytem could be simplified by using this method."


There may be a more efficient way to answer this problem, but this avoids a major problem with dictionaries. Deleting is tricky. If you iterate with keysAndValuesDo to delete items, you may be faced with a constantly changing collection to work from. Therefore, I have adopted the strategy of working with the collection of keys and using keysAndValuesRemove.

Jonathan D'Andries


Has anyone thought about the following dictionary?
KeyValue
JaneSmith
JoeSmith
JohnTimberland
MichaelKovak
TonySmith

The transpose doesn't work right, because the dictionary associates one and only one key to every entry. If the value is not unique than a transpose of the dictionary is not possible.

KeyValue
SmithJane
SmithJoe
SmithTony
KovakMichael
TimberlandJohn
is not possible in a dictionary (because unique keys are required)...

That doesn't stop our program though. We get "undefined behavior". We loose entries...
Unknown Assailant

I just have to ask what is the act point of trying to do this in one line of code? Won't the VM run say 3 lines writen efficently at the same speed since it does the thing. It just doesn't seem to gain any optimization. Am I wrong?
Robert Schierholz
I think this is a pretty straightforward way of doing it rather than using obscure methods, just a simple swap:
d keys do: [:key | temp := d at: key. d removeKey: key. d at: temp put: key].
Ken Edwards
Or better yet:
d keys do: [:key | d at: (d at: key) put: key. d removeKey: key].
Ken Edwards
Or best (truly in one line, only one period):
d keys do: [:key | d removeKey: (d at: (d at: key) put: key)].
Ken Edwards
"make values keys, make keys values, then remove old keys..."

d keysDo:[:key | d at:(d at:key) put:key. d removeKey:key].

Ken Bohannon



Link to this Page