--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/SmallDictionary.st Fri Sep 14 18:22:11 2018 +0200
@@ -0,0 +1,290 @@
+"{ Package: 'stx:libbasic' }"
+
+"{ NameSpace: Smalltalk }"
+
+KeyedCollection subclass:#SmallDictionary
+ instanceVariableNames:'keysAndValues tally'
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Unordered'
+!
+
+!SmallDictionary class methodsFor:'documentation'!
+
+documentation
+"
+ A lightweight Dictionary implementation (without hashing)
+ for small dictionaries.
+
+ Use this, when you have to store a small number (e.g. < 20) key/value pairs.
+ As a side effect of the implementation, the dictionary is also ordered.
+
+ Inspired by and compatible with RBSmallDictionary from RefactoryBrowser
+ (although the implementaion is different).
+
+ [instance variables:]
+ keysAndValues Array keys are stored at odd indices, values at even indices
+ tally SmallInterger the number of valid key/value pairs
+
+ [class variables:]
+
+ [see also:]
+ Dictionary
+ MethodDictionary
+
+ [author:]
+ Stefan Vogel
+"
+! !
+
+!SmallDictionary class methodsFor:'instance creation'!
+
+new
+ ^ self basicNew initialize:2
+
+ "Modified: / 14-09-2018 / 15:58:29 / Stefan Vogel"
+!
+
+new:capacity
+ ^ self basicNew initialize:capacity
+
+ "Modified: / 14-09-2018 / 15:58:49 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'accessing'!
+
+at:key ifAbsent:aBlock
+ |keyIndex|
+
+ keyIndex := self findIndexFor:key.
+ ^ keyIndex == 0 ifTrue:[aBlock value] ifFalse:[keysAndValues at:keyIndex+1]
+
+ "Modified (format): / 14-09-2018 / 15:46:58 / Stefan Vogel"
+!
+
+at:key ifAbsentPut:aBlock
+ |keyIndex|
+
+ keyIndex := self findIndexFor:key.
+ ^ keyIndex == 0 ifTrue:[
+ self privateAt:key put:aBlock value
+ ] ifFalse:[
+ keysAndValues at:keyIndex+1.
+ ]
+
+ "Modified (format): / 14-09-2018 / 15:47:43 / Stefan Vogel"
+!
+
+keys
+ "return a collection containing the keys of the receiver"
+
+ |keys sz "{Class: SmallInteger}"|
+
+ keys := Array new:tally.
+ sz := tally.
+ 1 to:sz do:[:i | keys at:i put:(keysAndValues at:i*2-1)].
+ ^ keys
+
+ "Created: / 14-09-2018 / 17:35:25 / Stefan Vogel"
+!
+
+order
+ "returns the keys in the order of their appearance"
+
+ ^ self keys
+
+ "
+ |s|
+
+ s := SmallDictionary new.
+ s at:#a put:'aaa'; at:#b put:'bbb'; at:#c put:'ccc'; at:#d put:'ddd'; at:#a put:'aaaa'.
+ s order
+ "
+
+ "Created: / 14-09-2018 / 17:30:44 / Stefan Vogel"
+!
+
+size
+ ^ tally
+
+ "Modified (format): / 14-09-2018 / 15:44:11 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'adding'!
+
+add:anAssociation
+ self at:anAssociation key put:anAssociation value.
+ ^ anAssociation
+
+ "Modified (format): / 14-09-2018 / 15:25:38 / Stefan Vogel"
+!
+
+at:key put:value
+ |keyIndex|
+
+ keyIndex := self findIndexFor:key.
+ ^ keyIndex == 0 ifTrue:[
+ self privateAt:key put:value
+ ] ifFalse:[
+ keysAndValues at:keyIndex+1 put:value
+ ]
+
+ "Modified (format): / 14-09-2018 / 15:47:57 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'copying'!
+
+postCopy
+ keysAndValues := keysAndValues copy.
+
+ "Modified: / 14-09-2018 / 15:38:50 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'enumerating'!
+
+do:aBlock
+ |sz "{Class: SmallInteger}"|
+
+ sz := tally.
+ 2 to:sz by:2 do:[:i | aBlock value:(keysAndValues at:i)]
+
+ "Modified: / 14-09-2018 / 16:30:18 / Stefan Vogel"
+!
+
+keysAndValuesDo:aBlock
+ |sz "{Class: SmallInteger}"|
+
+ sz := tally * 2.
+ 1 to:sz-1 by:2 do:[:i | aBlock value:(keysAndValues at:i) value:(keysAndValues at:i+1)]
+
+ "Modified: / 14-09-2018 / 16:31:18 / Stefan Vogel"
+!
+
+keysDo:aBlock
+ |sz "{Class: SmallInteger}"|
+
+ sz := tally * 2.
+ 1 to:sz-1 by:2 do:[:i | aBlock value:(keysAndValues at:i)]
+
+ "Modified: / 14-09-2018 / 16:30:51 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'initialize-release'!
+
+initialize:capacity
+ keysAndValues := Array new:capacity*2.
+ tally := 0
+
+ "Created: / 14-09-2018 / 15:57:42 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'private'!
+
+findIndexFor:aKey
+ |sz "{Class: SmallInteger}"|
+
+ sz := tally * 2.
+ 1 to:sz-1 by:2 do:[:i | (keysAndValues at:i) = aKey ifTrue:[^ i]].
+ ^ 0
+
+ "Modified: / 14-09-2018 / 16:25:03 / Stefan Vogel"
+ "Modified (format): / 14-09-2018 / 17:40:17 / Stefan Vogel"
+!
+
+growKeysAndValues
+ "duplicate the capacity"
+
+ self growTo:tally * 2
+
+ "Modified (comment): / 14-09-2018 / 16:04:17 / Stefan Vogel"
+!
+
+growTo:capacity
+ |newKeysAndValues|
+
+ newKeysAndValues := Array new:capacity*2.
+ newKeysAndValues replaceFrom:1 to:tally * 2 with:keysAndValues.
+ keysAndValues := newKeysAndValues.
+
+ "Modified (format): / 14-09-2018 / 16:10:49 / Stefan Vogel"
+!
+
+privateAt:key put:value
+ |sz "{Class: SmallInteger}"|
+
+ sz := tally * 2.
+ sz == keysAndValues size ifTrue: [self growKeysAndValues].
+ keysAndValues at:sz+1 put:key.
+ keysAndValues at:sz+2 put:value.
+ tally := tally + 1.
+ ^ value.
+
+ "Modified: / 14-09-2018 / 17:39:13 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'removing'!
+
+empty
+ "RefactoryBrowser compatibility"
+
+ self removeAll
+
+ "Modified: / 14-09-2018 / 15:59:57 / Stefan Vogel"
+!
+
+remove: oldObject ifAbsent: anExceptionBlock
+ self removeKey: oldObject key ifAbsent: anExceptionBlock.
+ ^ oldObject
+
+ "Modified (format): / 14-09-2018 / 15:40:44 / Stefan Vogel"
+!
+
+removeAll
+ tally := 0.
+ keysAndValues from:1 to:keysAndValues size put:nil.
+
+ "Modified: / 14-09-2018 / 16:02:28 / Stefan Vogel"
+!
+
+removeKey:key ifAbsent:aBlock
+ |keyIndex "{Class:SmallInteger}"
+ sz "{Class:SmallInteger}"
+ value|
+
+ keyIndex := self findIndexFor:key.
+ keyIndex == 0 ifTrue:[
+ ^ aBlock value
+ ].
+ value := keysAndValues at:keyIndex+1.
+ sz := tally*2.
+ keyIndex to:sz-2 do:[:i |
+ keysAndValues at:i put:(keysAndValues at:i + 1).
+ ].
+ keysAndValues at:sz-1 put:nil.
+ keysAndValues at:sz put:nil.
+ tally := tally - 1.
+ ^ value
+
+ "Modified (format): / 14-09-2018 / 16:23:45 / Stefan Vogel"
+! !
+
+!SmallDictionary methodsFor:'testing'!
+
+includesKey:aKey
+ ^ (self findIndexFor:aKey) ~~ 0
+
+ "Modified (format): / 14-09-2018 / 16:11:03 / Stefan Vogel"
+!
+
+isEmpty
+ ^ tally == 0
+
+ "Created: / 14-09-2018 / 15:44:49 / Stefan Vogel"
+! !
+
+!SmallDictionary class methodsFor:'documentation'!
+
+version_CVS
+ ^ '$Header$'
+! !
+