#FEATURE by cg
class: Socket class
added: #newTCPclientToHost:port:domain:domainOrder:withTimeout:
changed: #newTCPclientToHost:port:domain:withTimeout:
"{ Encoding: utf8 }"
"
Copyright (c) 2005 Ian Piumarta
All rights reserved.
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the 'Software'),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, provided that the above copyright notice(s) and this
permission notice appear in all copies of the Software and that both the
above copyright notice(s) and this permission notice appear in supporting
documentation.
THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK.
Last edited: 2007-01-25 03:17:27 by piumarta on emilia.local
"
"{ Package: 'stx:libbasic2' }"
"{ NameSpace: Smalltalk }"
SequenceableCollection subclass:#AVLTree
instanceVariableNames:'rootNode orderBlock'
classVariableNames:''
poolDictionaries:''
category:'Collections-Ordered-Trees'
!
Object subclass:#AVLNil
instanceVariableNames:''
classVariableNames:''
poolDictionaries:''
privateIn:AVLTree
!
Object subclass:#AVLTreeNode
instanceVariableNames:'left right height value'
classVariableNames:''
poolDictionaries:''
privateIn:AVLTree
!
!AVLTree class methodsFor:'documentation'!
copyright
"
Copyright (c) 2005 Ian Piumarta
All rights reserved.
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the 'Software'),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, provided that the above copyright notice(s) and this
permission notice appear in all copies of the Software and that both the
above copyright notice(s) and this permission notice appear in supporting
documentation.
THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK.
Last edited: 2007-01-25 03:17:27 by piumarta on emilia.local
"
!
documentation
"
AVLTree -- balanced trees.
This implements another kind of self-balancing tree, named after their inventors,
AVLTree is obsoleted by AATree, which has the same best/worst/average characteristics
(it is also self-balancing), but is always faster (roughly by a factor of 1.5 to 2).
Consider using an AATree instead.
(unless a special situation arises, of which we don't know yet)
[see also:]
AATree
BTree
SortedCollection
https://en.wikipedia.org/wiki/AVL_tree
Examples:
|t|
t := AVLTree new.
self assert:(t depth == 0).
self assert:(t size == 0).
self assert:(t isEmpty).
t add:'hello'.
self assert:(t depth == 0).
self assert:(t size == 1).
self assert:(t notEmpty).
t add:'world'.
self assert:(t depth == 1).
self assert:(t size == 2).
t add:'aaa'.
self assert:(t depth == 1).
self assert:(t size == 3).
t add:'bbb'.
self assert:(t depth == 2).
self assert:(t size == 4).
self assert:(t printString = 'AVLTree(aaa bbb hello world)').
t remove:'aaa'.
self assert:(t printString = 'AVLTree(bbb hello world)').
self assert:(t depth == 1).
self assert:(t size == 3).
| words tree |
words := #( Peter Piper picked a peck of pickled peppers
A peck of pickled peppers Peter Piper picked
If Peter Piper picked a peck of pickled peppers
Where is the peck of pickled peppers Peter Piper picked? ).
tree := AVLTree new.
tree addAll: words.
tree printOn:Transcript. Transcript cr; cr.
tree := AVLTree withSortBlock: [:a :b | b < a].
tree addAll: words.
tree printOn:Transcript. Transcript cr; cr.
"
!
performance
"
Time to insert random 1000000 into SortedCollection: 840ms
Time to insert random 1000000 into BinaryTree: 2040ms
Time to insert random 1000000 into AATree: 3060ms
Time to insert random 1000000 into AVLTree: 3780ms
Time to insert ordered 1000000 into SortedCollection: 30ms
Time to insert ordered 1000000 into BinaryTree: 72200ms
Time to insert ordered 1000000 into AATree: 110ms
Time to insert ordered 1000000 into AVLTree: 180ms
Time to insert reverse ordered 1000000 into SortedCollection: 30ms
Time to insert reverse ordered 1000000 into BinaryTree: 73880ms
Time to insert reverse ordered 1000000 into AATree: 80ms
Time to insert reverse ordered 1000000 into AVLTree: 160ms
"
! !
!AVLTree class methodsFor:'instance creation'!
new
^ super new initialize
!
withSortBlock: binaryBlock
^ self new orderBlock:binaryBlock.
! !
!AVLTree methodsFor:'accessing'!
orderBlock:aBlock
orderBlock := aBlock
! !
!AVLTree methodsFor:'adding & removing'!
add: anObject
self addNode: (AVLTreeNode withValue: anObject).
^anObject
!
remove: anObject
^self removeNode: (AVLTreeNode withValue: anObject)
! !
!AVLTree methodsFor:'enumeration'!
do: unaryBlock
rootNode avlTreeNodeDo: unaryBlock
!
reverseDo: unaryBlock
rootNode avlTreeNodeReverseDo: unaryBlock
! !
!AVLTree methodsFor:'initialization'!
initialize
super initialize.
rootNode := AVLNil.
orderBlock := [:a :b | a < b].
! !
!AVLTree methodsFor:'private'!
addNode: aNode
rootNode := rootNode avlTreeNodeInsert: aNode orderedBy: orderBlock.
^aNode
!
removeNode: aNode
^rootNode := rootNode avlTreeNodeRemove: aNode orderedBy: orderBlock
! !
!AVLTree methodsFor:'queries'!
depth
^rootNode avlTreeNodeHeight
!
isEmpty
^rootNode == AVLNil
!
size
^rootNode avlTreeSize
! !
!AVLTree methodsFor:'searching'!
find: anObject
^self findNode: (AVLTreeNode with: anObject)
!
findNode: aNode
^rootNode avlTreeNodeFind: aNode orderedBy: orderBlock
! !
!AVLTree::AVLNil class methodsFor:'avl polymorphy'!
avlTreeNodeDo: unaryBlock
^ nil
!
avlTreeNodeFind: aNode
^AVLNil
!
avlTreeNodeHeight
^0
!
avlTreeNodeInsert: aNode orderedBy: binaryBlock
^aNode
!
avlTreeNodeMoveRight: aNode
^aNode
!
avlTreeNodeRemove: aNode orderedBy: binaryBlock
^AVLNil
!
avlTreeNodeReverseDo: unaryBlock
^nil
!
avlTreeSize
^0
! !
!AVLTree::AVLTreeNode class methodsFor:'instance creation'!
new
^ self basicNew initialize.
!
withValue: anObject
^ self new value:anObject.
! !
!AVLTree::AVLTreeNode methodsFor:'accessing'!
height
^ height
!
left
^ left
!
left:aTreeNode
left := aTreeNode.
!
right
^ right
!
right:aTreeNode
right := aTreeNode.
!
value
^ value
!
value:anObject
value := anObject
! !
!AVLTree::AVLTreeNode methodsFor:'adding & removing'!
avlTreeNodeRemove: aNode orderedBy: binaryBlock
(aNode equals: self orderedBy: binaryBlock)
ifTrue:
[| temp |
temp := left avlTreeNodeMoveRight: right.
left := right := AVLTree::AVLNil.
^temp].
(aNode precedes: self orderedBy: binaryBlock)
ifTrue: [left := left avlTreeNodeRemove: aNode orderedBy: binaryBlock]
ifFalse: [right := right avlTreeNodeRemove: aNode orderedBy: binaryBlock].
^self balance
! !
!AVLTree::AVLTreeNode methodsFor:'enumeration'!
avlTreeNodeDo: unaryBlock
left avlTreeNodeDo: unaryBlock.
unaryBlock value: value.
right avlTreeNodeDo: unaryBlock.
!
avlTreeNodeReverseDo: unaryBlock
right avlTreeNodeReverseDo: unaryBlock.
unaryBlock value: value.
left avlTreeNodeReverseDo: unaryBlock.
! !
!AVLTree::AVLTreeNode methodsFor:'initialization'!
initialize
left := right := AVLTree::AVLNil.
height := 0.
value := nil.
! !
!AVLTree::AVLTreeNode methodsFor:'misc'!
avlTreeNodeFind: aNode orderedBy: binaryBlock
(self equals:aNode orderedBy: binaryBlock) ifTrue: [^self].
^(aNode precedes: self orderedBy: binaryBlock)
ifTrue: [left avlTreeNodeFind: aNode orderedBy: binaryBlock]
ifFalse: [right avlTreeNodeFind: aNode orderedBy: binaryBlock]
!
avlTreeNodeMoveRight: aNode
right := right avlTreeNodeMoveRight: aNode.
^self balance
! !
!AVLTree::AVLTreeNode methodsFor:'printing & storing'!
printOn: aStream
super printOn: aStream.
aStream
nextPut: $(;
print: value;
nextPut: $)
! !
!AVLTree::AVLTreeNode methodsFor:'private'!
balance
| delta |
delta := self delta.
delta < -1
ifTrue:
[right delta > 0 ifTrue: [right := right rotateRight].
^self rotateLeft].
delta > 1
ifTrue:
[left delta < 0 ifTrue: [left := left rotateLeft].
^self rotateRight].
height := 0.
(left avlTreeNodeHeight > height) ifTrue: [height := left avlTreeNodeHeight].
(right avlTreeNodeHeight > height) ifTrue: [height := right avlTreeNodeHeight].
height := height + 1.
!
rotateLeft
| pivot |
pivot := right.
right := pivot left.
pivot left: self balance.
^pivot balance
!
rotateRight
| pivot |
pivot := left.
left := pivot right.
pivot right: self balance.
^pivot balance
! !
!AVLTree::AVLTreeNode methodsFor:'queries'!
avlTreeNodeHeight
^height
!
avlTreeNodeInsert: aNode orderedBy: binaryBlock
(aNode precedes: self orderedBy: binaryBlock)
ifTrue: [left := left avlTreeNodeInsert: aNode orderedBy: binaryBlock]
ifFalse: [right := right avlTreeNodeInsert: aNode orderedBy: binaryBlock].
^self balance
!
avlTreeSize
^ (left avlTreeSize) + 1 + (right avlTreeSize)
!
delta
^ (left avlTreeNodeHeight) - (right avlTreeNodeHeight)
!
equals: aNode orderedBy: binaryBlock
| l r lr rl |
l := self value.
r := aNode value.
lr := binaryBlock value: l value: r.
rl := binaryBlock value: r value: l.
"Partial order (<=): l = r => (l <= r) and (l >= r) => lr and rl."
"Strict order (< ): l = r => not (l < r) and not (l > r) => not (lr) and not (rl)."
"Augustus tells us the latter really means l = r => not (lr or rl), saving us one send."
^(lr and: [rl]) or: [(lr or: [rl]) not]
!
precedes: aNode orderedBy: binaryBlock
^ binaryBlock value: (self value) value: (aNode value)
! !
!AVLTree class methodsFor:'documentation'!
version
^ '$Header$'
!
version_CVS
^ '$Header$'
! !