Smalltalk Lecture 5
1
Node (helper class for Queue)
Object subclass: #Node.
Node instanceVariableNames: ‘data next’.
Node extend [ data [ ^ data ]
next [ ^ next ] data: d [ data := d ] next: n [ next := n ]
]
2
Queue class and insert:
Object subclass: #Queue.
Queue instanceVariableNames: ‘front back’.
Queue extend [
insert: key [ “enqueue”
|p|
p := Node new data: key. front isNil
ifTrue: [ front := p. back := p ]
ifFalse: [ back next: p. back := p ] ]
]
3
remove:
Queue extend [ remove [
“dequeue”
| key |
front isNil ifTrue: [ ^ nil ]. key := front data.
front := front next.
^ key
] ]
“automatic garbage collection”
4
display
Queue extend [ display [
|p|
p := front.
[ p notNil ] whileTrue:
[ Transcript display: p data; cr. p := p next] ]
]
5
Client code
q := Queue new.
q insert: 20; insert: 40; insert: 10; insert: 30. q display.
5 timesRepeat:
[ Transcript display: q remove; cr ].
20 40 10 30
20 40 10 30 nil
6
do:
Queue extend [ do: aBlock [
|p|
p := front.
[ p notNil ] whileTrue:
[ aBlock value: p data. p := p next ]
] ]
q := Queue new.
q insert: 20; insert: 40; insert: 10; insert: 30. q do: [ 😡 | Transcript display: x; cr ].
7
20 40 10 30
collect:
Queue extend [
collect: aBlock [ “map”
|q|
q := Queue new.
self do: [ :key | q insert: (aBlock value: key) ]. ^q
] ]
r := q collect: [ 😡 | x*x ].
r do: [ 😡 | Transcript display: x; cr ].
8
400
1600
100
900
select:
Queue extend [
select: aBlock [ “filter”
|q|
q := Queue new.
self do: [ :key | (aBlock value: key)
^q ]
]
s := q select: [ 😡 | x>15 and: [x<35] ]. s do: [ :x | Transcript display: x; cr ].
9
ifTrue: [ q insert: key ] ].
20 30
reject:
Queue extend [ reject: aBlock [
|q|
q := Queue new.
self do: [ :key | (aBlock value: key)
^q ]
]
t := q reject: [ :x | x>15 and: [x<35] ]. t do: [ :x | Transcript display: x; cr ].
10
ifFalse: [ q insert: key ] ].
40 10
reject: (simpler version)
Queue extend [ reject: aBlock [
^ self select: [ :x | (aBlock value: x) not ] ]
]
u := q reject: [ :x | x>15 and: [x<35] ]. u do: [ :x | Transcript display: x; cr ].
40 10
11
inject: into:
Queue extend [
inject: id into: aBlock [ "fold-left"
|x|
x := id.
self do: [ :key | x := aBlock value: x value: key ]. ^x
] ]
Transcript display: ( q inject: 0 into: [ :a :b | a+b ] ); cr. Transcript display: ( q inject: 1 into: [ :a :b | a*b ] ); cr.
100 240000
12
detect: ifNone:
Queue extend [
detect: aBlock ifNone: defaultBlock [
self do: [ :key | (aBlock value: key) ifTrue: [ ^ key ] ].
^ defaultBlock value ]
]
Transcript display: (q detect: [ :x | x<15 ] ifNone: [99]); cr. Transcript display: (q detect: [ :x | x>25 ] ifNone: [99]); cr. Transcript display: (q detect: [ 😡 | x>50 ] ifNone: [99]); cr.
10 40 99
13
PriorityQueue subclass (version 1)
Queue subclass: #PriorityQueue1. PriorityQueue1 extend [
insert: key [ “maintain keys in ascending order” |p|
(front isNil or: [ key < front data ])
ifTrue: [ front := Node new data: key; next: front. ^ self ].
p := front.
[ p next isNil or: [ key < p next data ] ]
whileFalse: [ p := p next ].
p next: (Node new data: key; next: p next)
] ]
14
PriorityQueue1 client
q := PriorityQueue1 new.
q insert: 20; insert: 40; insert: 10; insert: 30. q display.
5 timesRepeat: [ Transcript display: q remove; cr ].
10 20 30 40
10 20 30 40 nil
15
PriorityQueue subclass (version 2) ...
Queue subclass: #PriorityQueue2. PriorityQueue2 extend [
remove [
| p key |
front isNil ifTrue: [ ^ nil ]. p := front.
key := front data.
[ p isNil ] whileFalse: [
"remove minimum key"
(p data < key) ifTrue: [ key := p data ].
p := p next ].
...
16
... continued
PriorityQueue2 extend [
remove [ "remove minimum key¡°
...
(key == front data) ifTrue: [ front := front next. ^ key ]. p := front.
[ key ~= p next data ] whileTrue: [ p := p next ].
p next: p next next.
^ key
] ]
17
PriorityQueue2 client
q := PriorityQueue2 new.
q insert: 20; insert: 40; insert: 10; insert: 30. q display.
5 timesRepeat: [ Transcript display: q remove; cr ].
20 40 10 30
10 20 30 40 nil
18