author | Jan Vrany <jan.vrany@labware.com> |
Thu, 09 Jul 2020 21:48:49 +0100 | |
branch | jv |
changeset 5477 | 11c625b9ecca |
parent 4248 | 998a831e6c9d |
permissions | -rw-r--r-- |
2789 | 1 |
" |
2 |
COPYRIGHT (c) 2012 by eXept Software AG |
|
5477
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
3 |
COPYRIGHT (c) 2020 LabWare |
2789 | 4 |
All Rights Reserved |
5 |
||
6 |
This software is furnished under a license and may be used |
|
7 |
only in accordance with the terms of that license and with the |
|
8 |
inclusion of the above copyright notice. This software may not |
|
9 |
be provided or otherwise made available to, or used by, any |
|
10 |
other person. No title to or ownership of the software is |
|
11 |
hereby transferred. |
|
12 |
" |
|
13 |
"{ Package: 'stx:libbasic2' }" |
|
14 |
||
4248 | 15 |
"{ NameSpace: Smalltalk }" |
16 |
||
2789 | 17 |
OrderedSet subclass:#SortedSet |
18 |
instanceVariableNames:'' |
|
19 |
classVariableNames:'' |
|
20 |
poolDictionaries:'' |
|
21 |
category:'Collections-Sequenceable' |
|
22 |
! |
|
23 |
||
24 |
!SortedSet class methodsFor:'documentation'! |
|
25 |
||
26 |
copyright |
|
27 |
" |
|
28 |
COPYRIGHT (c) 2012 by eXept Software AG |
|
5477
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
29 |
COPYRIGHT (c) 2020 LabWare |
2789 | 30 |
All Rights Reserved |
31 |
||
32 |
This software is furnished under a license and may be used |
|
33 |
only in accordance with the terms of that license and with the |
|
34 |
inclusion of the above copyright notice. This software may not |
|
35 |
be provided or otherwise made available to, or used by, any |
|
36 |
other person. No title to or ownership of the software is |
|
37 |
hereby transferred. |
|
38 |
" |
|
39 |
! |
|
40 |
||
41 |
documentation |
|
42 |
" |
|
43 |
I am a subclass of Set whose elements are ordered in a |
|
44 |
similar fashion to SortedCollection. |
|
45 |
That is, I have both Set behavior (only keeping a single instance of |
|
46 |
an element) but I also remember the sort order. |
|
47 |
||
48 |
I have one additional instance variable: |
|
49 |
||
50 |
order <SortedCollection> Sorted collection of values reflecting the order |
|
51 |
in the set. |
|
52 |
||
2790 | 53 |
[caveat:] |
54 |
a tree may be a better choice, |
|
55 |
as although the set shows O(1) behavior when adding, |
|
56 |
the sortedCollection does not (especially as inserting is expensive). |
|
57 |
A balanced tree would show O(lg n) behavior. |
|
58 |
||
2789 | 59 |
[author:] |
60 |
Claus Gittinger |
|
61 |
||
62 |
[see also:] |
|
63 |
OrderedCollection |
|
64 |
Dictionary OrderedDictionary |
|
65 |
Set Bag |
|
66 |
" |
|
67 |
! |
|
68 |
||
69 |
examples |
|
70 |
" |
|
71 |
[exBegin] |
|
72 |
|s| |
|
73 |
||
74 |
s := SortedSet new. |
|
75 |
s add:'one'. |
|
76 |
s add:'two'. |
|
77 |
s add:'one'. |
|
78 |
s add:'two'. |
|
79 |
s add:'three'. |
|
80 |
s size. |
|
81 |
s do:[:each | Transcript showCR:each]. |
|
82 |
[exEnd] |
|
83 |
||
84 |
||
85 |
[exBegin] |
|
86 |
|s| |
|
87 |
||
88 |
s := SortedSet new. |
|
89 |
s add:'one'. |
|
90 |
s add:'two'. |
|
91 |
s add:'one'. |
|
92 |
s add:'two'. |
|
93 |
s add:'three'. |
|
94 |
s remove:'one'. |
|
95 |
s size. |
|
96 |
s do:[:each | Transcript showCR:each]. |
|
97 |
[exEnd] |
|
98 |
||
99 |
[exBegin] |
|
100 |
|s| |
|
101 |
||
102 |
s := SortedSet new. |
|
103 |
s add:'one'. |
|
104 |
s add:'two'. |
|
105 |
s add:'three'. |
|
106 |
s add:'one'. |
|
107 |
s add:'two'. |
|
108 |
s add:'three'. |
|
109 |
s size. |
|
110 |
Transcript showCR:s. |
|
111 |
s removeFirst. |
|
112 |
Transcript showCR:s. |
|
113 |
s removeFirst. |
|
114 |
Transcript showCR:s. |
|
115 |
s removeFirst. |
|
116 |
Transcript showCR:s. |
|
117 |
[exEnd] |
|
118 |
" |
|
119 |
! ! |
|
120 |
||
121 |
!SortedSet class methodsFor:'instance creation'! |
|
122 |
||
123 |
sortBlock:aBlock |
|
124 |
"return a new sortedSet, whe the sort order is defined by aBlock. |
|
125 |
This must be a two-argument block which returns true if its arg1 has to come before |
|
126 |
its arg2 in the collection." |
|
127 |
||
128 |
^ self new setSortBlock:aBlock |
|
129 |
||
130 |
"Created: / 06-08-2012 / 12:34:29 / cg" |
|
131 |
! ! |
|
132 |
||
3438 | 133 |
!SortedSet methodsFor:'accessing'! |
134 |
||
135 |
sortBlock |
|
136 |
^ order sortBlock |
|
137 |
! ! |
|
138 |
||
2789 | 139 |
!SortedSet methodsFor:'adding & removing'! |
140 |
||
141 |
addFirst:anObject |
|
142 |
"blocked; only the sort order determines the order" |
|
143 |
||
144 |
self shouldNotImplement |
|
145 |
||
146 |
"Modified: / 06-08-2012 / 12:37:23 / cg" |
|
147 |
! |
|
148 |
||
149 |
addLast:anObject |
|
150 |
"blocked; only the sort order determines the order" |
|
151 |
||
152 |
self shouldNotImplement |
|
153 |
||
154 |
"Modified: / 06-08-2012 / 12:37:30 / cg" |
|
155 |
! ! |
|
156 |
||
3438 | 157 |
!SortedSet methodsFor:'enumerating'! |
158 |
||
159 |
collect:aBlock |
|
160 |
"for each element in the receiver, evaluate the argument, aBlock |
|
161 |
and return a new collection with the results" |
|
162 |
||
163 |
|newCollection| |
|
164 |
||
165 |
newCollection := self speciesForAdding new. |
|
166 |
newCollection setSortBlock:self sortBlock. |
|
167 |
self do:[:element | newCollection add:(aBlock value:element)]. |
|
168 |
^ newCollection |
|
169 |
||
170 |
" |
|
171 |
#(1 2 3 4) collect:[:e | e odd] |
|
172 |
(1 to:10) collect:[:e | e even] |
|
173 |
" |
|
174 |
||
175 |
"Modified: / 07-08-2010 / 16:26:40 / cg" |
|
176 |
! |
|
177 |
||
178 |
select:aBlock |
|
179 |
"return a new collection with all elements from the receiver, for which |
|
180 |
the argument aBlock evaluates to true. |
|
181 |
See also: #removeAllFoundIn: and #removeAllSuchThat:" |
|
182 |
||
183 |
|newCollection| |
|
184 |
||
185 |
newCollection := self speciesForAdding new. |
|
186 |
newCollection setSortBlock:self sortBlock. |
|
187 |
self do:[:each | |
|
188 |
(aBlock value:each) ifTrue:[newCollection add:each]. |
|
189 |
]. |
|
190 |
^ newCollection |
|
191 |
||
192 |
" |
|
193 |
#(1 2 3 4) select:[:e | e odd] |
|
194 |
(1 to:10) select:[:e | e even] |
|
195 |
" |
|
196 |
||
197 |
"Modified: / 07-08-2010 / 16:26:40 / cg" |
|
198 |
! ! |
|
199 |
||
2789 | 200 |
!SortedSet methodsFor:'initialization'! |
201 |
||
4248 | 202 |
initializeOrder:anInteger |
203 |
order := SortedCollection new:anInteger |
|
2789 | 204 |
|
205 |
"Created: / 06-08-2012 / 12:33:31 / cg" |
|
206 |
! |
|
207 |
||
208 |
setSortBlock:aBlock |
|
209 |
order sortBlock:aBlock |
|
210 |
||
211 |
"Created: / 06-08-2012 / 12:35:07 / cg" |
|
212 |
! ! |
|
213 |
||
5477
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
214 |
!SortedSet methodsFor:'sorting & reordering'! |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
215 |
|
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
216 |
sort:aSortBlock |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
217 |
"Destructively sort my order. |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
218 |
WARNING: this is a destructive operation, which modifies the receiver" |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
219 |
|
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
220 |
order sortBlock:aSortBlock |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
221 |
|
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
222 |
"Created: / 09-07-2020 / 20:37:01 / Jan Vrany <jan.vrany@labware.com>" |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
223 |
! ! |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
224 |
|
2789 | 225 |
!SortedSet class methodsFor:'documentation'! |
226 |
||
227 |
version |
|
4248 | 228 |
^ '$Header$' |
2789 | 229 |
! |
230 |
||
231 |
version_CVS |
|
4248 | 232 |
^ '$Header$' |
5477
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
233 |
! |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
234 |
|
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
235 |
version_HG |
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
236 |
|
11c625b9ecca
Add `SortedSet >> sort:`
Jan Vrany <jan.vrany@labware.com>
parents:
4248
diff
changeset
|
237 |
^ '$Changeset: <not expanded> $' |
2789 | 238 |
! ! |
3438 | 239 |