--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/AATree.st Mon Sep 28 18:17:17 2009 +0200
@@ -0,0 +1,269 @@
+"{ Package: 'stx:libbasic2' }"
+
+BinaryTree subclass:#AATree
+ instanceVariableNames:''
+ classVariableNames:''
+ poolDictionaries:''
+ category:'Collections-Ordered'
+!
+
+!AATree class methodsFor:'documentation'!
+
+documentation
+"
+ An AA tree is a form of balanced tree used for storing and retrieving ordered data efficiently.
+ AA trees are named for Arne Andersson, their inventor.
+
+ AA trees are a variation of the red-black tree, which in turn is an enhancement to the
+ binary search tree. One caveat with the implementation is that it needs an extra level instvar
+ in the treeNode; this results in 25% more storage overhead as compared to a Red/Black or plain Binary tree.
+ For performance data, see performance.
+
+ [author:]
+ Original algorithm by Arne Andersson
+ ported from wikipedia to smalltalk code by Claus Gittinger
+"
+!
+
+examples
+"
+ [exBegin]
+ |coll|
+
+ coll := AATree new.
+ (1 to:10) do:[:i | coll add:i].
+ coll addAll:(20 to:30).
+ coll inspect
+ [exEnd]
+
+ [exBegin]
+ |tree|
+
+ tree := AATree new.
+ tree add:'hello'.
+ tree add:'aaaa'.
+ tree add:'AAAb'.
+ tree add:'aaaC'.
+ tree add:'world'.
+ tree asOrderedCollection
+ [exEnd]
+
+ [exBegin]
+ |tree|
+
+ tree := AATree sortBlock:[:a :b | a asLowercase < b asLowercase].
+ tree add:'hello'.
+ tree add:'aaaa'.
+ tree add:'AAAb'.
+ tree add:'aaaC'.
+ tree add:'world'.
+ tree asOrderedCollection
+ [exEnd]
+
+ timing 1:
+ [exBegin]
+ |N randomNumbers coll1_BT coll2_AT coll3_SC t1_BT t2_AT t3_SC|
+
+ N := 1000000.
+ randomNumbers := (1 to:N) collect:[:i | Random nextInteger].
+
+ ObjectMemory garbageCollect.
+ t1_BT := Time millisecondsToRun:[
+ coll1_BT := BinaryTree new.
+ coll1_BT addAll:randomNumbers
+ ].
+ coll1_BT := nil.
+ ObjectMemory garbageCollect.
+
+ t2_AT := Time millisecondsToRun:[
+ coll2_AT := AATree new.
+ coll2_AT addAll:randomNumbers
+ ].
+ coll2_AT := nil.
+ ObjectMemory garbageCollect.
+
+ t3_SC := Time millisecondsToRun:[
+ coll3_SC := SortedCollection new.
+ coll3_SC addAll:randomNumbers
+ ].
+ coll3_SC := nil.
+ ObjectMemory garbageCollect.
+ randomNumbers := nil.
+
+ Transcript show:'Time to insert random '; show:N; show:' into SortedCollection: '; show:t3_SC; showCR:'ms'.
+ Transcript show:'Time to insert random '; show:N; show:' into BinaryTree: '; show:t1_BT; showCR:'ms'.
+ Transcript show:'Time to insert random '; show:N; show:' into AATree: '; show:t2_AT; showCR:'ms'.
+
+ ObjectMemory garbageCollect.
+ t1_BT := Time millisecondsToRun:[
+ coll1_BT := BinaryTree new.
+ coll1_BT addAll:(1 to:100000).
+ ].
+ coll1_BT := nil.
+ ObjectMemory garbageCollect.
+
+ t2_AT := Time millisecondsToRun:[
+ coll2_AT := AATree new.
+ coll2_AT addAll:(1 to:100000)
+ ].
+ coll2_AT := nil.
+ ObjectMemory garbageCollect.
+
+ t3_SC := Time millisecondsToRun:[
+ coll3_SC := SortedCollection new.
+ coll3_SC addAll:(1 to:100000)
+ ].
+ coll3_SC := nil.
+ ObjectMemory garbageCollect.
+
+ Transcript show:'Time to insert ordered '; show:N; show:' into SortedCollection: '; show:t3_SC; showCR:'ms'.
+ Transcript show:'Time to insert ordered '; show:N; show:' into BinaryTree: '; show:t1_BT; showCR:'ms'.
+ Transcript show:'Time to insert ordered '; show:N; show:' into AATree: '; show:t2_AT; showCR:'ms'.
+
+ ObjectMemory garbageCollect.
+ t1_BT := Time millisecondsToRun:[
+ coll1_BT := BinaryTree new.
+ coll1_BT addAll:(100000 downTo:1).
+ ].
+ coll1_BT := nil.
+ ObjectMemory garbageCollect.
+
+ t2_AT := Time millisecondsToRun:[
+ coll2_AT := AATree new.
+ coll2_AT addAll:(100000 downTo:1)
+ ].
+ coll2_AT := nil.
+ ObjectMemory garbageCollect.
+
+ t3_SC := Time millisecondsToRun:[
+ coll3_SC := SortedCollection new.
+ coll3_SC addAll:(100000 downTo:1)
+ ].
+ coll3_SC := nil.
+ ObjectMemory garbageCollect.
+
+ Transcript show:'Time to insert reverse ordered '; show:N; show:' into SortedCollection: '; show:t3_SC; showCR:'ms'.
+ Transcript show:'Time to insert reverse ordered '; show:N; show:' into BinaryTree: '; show:t1_BT; showCR:'ms'.
+ Transcript show:'Time to insert reverse ordered '; show:N; show:' into AATree: '; show:t2_AT; showCR:'ms'.
+ [exEnd]
+
+ timing 2:
+ [exBegin]
+ |allSelectors coll1_SC coll2_BT coll3_AT t1_SC t2_BT t3_AT|
+
+ allSelectors := OrderedCollection new.
+ Smalltalk allClassesDo:[:cls |
+ cls instAndClassSelectorsAndMethodsDo:[:sel :mthd |
+ allSelectors add:sel.
+ ].
+ ].
+
+ t1_SC := Time millisecondsToRun:[
+ coll1_SC := SortedCollection new.
+ allSelectors do:[:sel |
+ coll1_SC add:sel
+ ].
+ ].
+ Transcript show:'Time to insert '; show:coll1_SC size; show:' selectors into SortedCollection: '; show:t1_SC; showCR:'ms'.
+
+ t2_BT := Time millisecondsToRun:[
+ coll2_BT := BinaryTree new.
+ allSelectors do:[:sel |
+ coll2_BT add:sel
+ ].
+ ].
+ Transcript show:'Time to insert '; show:coll2_BT size; show:' selectors into BinaryTree: '; show:t2_BT; showCR:'ms'.
+
+ t3_AT := Time millisecondsToRun:[
+ coll3_AT := BinaryTree new.
+ allSelectors do:[:sel |
+ coll3_AT add:sel
+ ].
+ ].
+ Transcript show:'Time to insert '; show:coll3_AT size; show:' selectors into AATree: '; show:t3_AT; showCR:'ms'.
+
+ t1_SC := Time millisecondsToRun:[
+ allSelectors do:[:sel |
+ coll1_SC remove:sel
+ ].
+ ].
+ self assert:(coll1_SC isEmpty).
+ Transcript show:'Time to remove selectors from SortedCollection: '; show:t1_SC; showCR:'ms'.
+
+ t2_BT := Time millisecondsToRun:[
+ allSelectors do:[:sel |
+ coll2_BT remove:sel
+ ].
+ ].
+ self assert:(coll2_BT isEmpty).
+ Transcript show:'Time to remove selectors from BinaryTree: '; show:t2_BT; showCR:'ms'.
+
+ t3_AT := Time millisecondsToRun:[
+ allSelectors do:[:sel |
+ coll3_AT remove:sel
+ ].
+ ].
+ self assert:(coll3_AT isEmpty).
+ Transcript show:'Time to remove selectors from BinaryTree: '; show:t3_AT; showCR:'ms'.
+ [exEnd]
+
+"
+!
+
+performance
+"
+ Time to insert random 100000 individually into SortedCollection: 6037ms
+ Time to insert random 100000 en-bloque into SortedCollection: 172ms
+ Time to insert in order 100000 individually into SortedCollection: 31ms
+ Time to insert in order 100000 en-bloque into SortedCollection: 125ms
+ Time to insert in reverse order 100000 individually into SortedCollection: 93ms
+ Time to insert in reverse order 100000 en-bloque into SortedCollection: 125ms
+ Time to remove in random order 100000 from SortedCollection: 6380ms
+ Time to remove in order 100000 from SortedCollection: 109ms
+ Time to remove in reverse order 100000 from SortedCollection: 125ms
+
+ Time to insert random 100000 individually into AATree: 281ms
+ Time to insert random 100000 en-bloque into AATree: 265ms
+ Time to insert in order 100000 individually into AATree: 281ms
+ Time to insert in order 100000 en-bloque into AATree: 328ms
+ Time to insert in reverse order 100000 individually into AATree: 203ms
+ Time to insert in reverse order 100000 en-bloque into AATree: 218ms
+ Time to remove in random order 100000 from AATree: 452ms
+ Time to remove in order 100000 from AATree: 312ms
+ TSourceCodeManager [warning]: class `CollectionBenchmarks' has neither source nor compiled-in info
+ ime to remove in reverse order 100000 from AATree: 499ms
+
+ Time to insert random 100000 individually into BinaryTree: 156ms
+ Time to insert random 100000 en-bloque into BinaryTree: 156ms
+ Time to insert in order 100000 individually into BinaryTree: 195921ms
+ Time to insert in order 100000 en-bloque into BinaryTree: 205266ms
+ Time to insert in reverse order 100000 individually into BinaryTree: 202271ms
+ Time to insert in reverse order 100000 en-bloque into BinaryTree: 197684ms
+ Time to remove in random order 100000 from BinaryTree: 234ms
+ Time to remove in order 100000 from BinaryTree: 78ms
+ Time to remove in reverse order 100000 from BinaryTree: 78ms
+"
+! !
+
+!AATree methodsFor:'adding & removing'!
+
+add:anObject
+ "add the argument, anObject to the receiver.
+ Returns the object (sigh).
+
+ WARNING: do not add/remove elements while iterating over the receiver.
+ Iterate over a copy to do this."
+
+ treeRoot isNil ifTrue:[
+ treeRoot := AATreeNode data:anObject level:1.
+ ^ self.
+ ].
+ treeRoot := treeRoot insert:anObject usingSortBlock:sortBlock.
+ ^ anObject "sigh - collection protocol"
+! !
+
+!AATree class methodsFor:'documentation'!
+
+version
+ ^ '$Header: /cvs/stx/stx/libbasic2/AATree.st,v 1.1 2009-09-28 16:17:17 cg Exp $'
+! !