|
1 " |
|
2 COPYRIGHT (c) 1993 by Claus Gittinger |
|
3 All Rights Reserved |
|
4 |
|
5 This software is furnished under a license and may be used |
|
6 only in accordance with the terms of that license and with the |
|
7 inclusion of the above copyright notice. This software may not |
|
8 be provided or otherwise made available to, or used by, any |
|
9 other person. No title to or ownership of the software is |
|
10 hereby transferred. |
|
11 " |
|
12 |
|
13 OrderedCollection subclass:#SortedCollection |
|
14 instanceVariableNames:'sortBlock' |
|
15 classVariableNames:'DefaultSortBlock' |
|
16 poolDictionaries:'' |
|
17 category:'Collections-Ordered' |
|
18 ! |
|
19 |
|
20 SortedCollection comment:' |
|
21 |
|
22 COPYRIGHT (c) 1993 by Claus Gittinger |
|
23 All Rights Reserved |
|
24 |
|
25 I keep my elements sorted. The sort order is defined by a sortblock, |
|
26 which is a two-argument block which, when given two elements of the |
|
27 collection, returns true if the element given as first arg has to |
|
28 come before the element given as second arg. |
|
29 Thus a sortBlock of [:a :b | a < b] defines ascending sort-order, |
|
30 while [:a :b | a > b] defines descening order. |
|
31 |
|
32 %W% %E% |
|
33 '! |
|
34 |
|
35 !SortedCollection class methodsFor:'initialization'! |
|
36 |
|
37 initialize |
|
38 DefaultSortBlock := [:a :b | a < b ] |
|
39 |
|
40 "SortedCollection initialize" |
|
41 ! ! |
|
42 |
|
43 !SortedCollection class methodsFor:'instance creation'! |
|
44 |
|
45 new |
|
46 ^ super new setSortBlock:DefaultSortBlock |
|
47 ! |
|
48 |
|
49 new:size |
|
50 ^ (super new:size) setSortBlock:DefaultSortBlock |
|
51 ! |
|
52 |
|
53 sortBlock:aBlock |
|
54 ^ super new setSortBlock:aBlock |
|
55 ! ! |
|
56 |
|
57 !SortedCollection methodsFor:'adding & removing'! |
|
58 |
|
59 addFirst:anObject |
|
60 self shouldNotImplement |
|
61 ! |
|
62 |
|
63 addLast:anObject |
|
64 self shouldNotImplement |
|
65 ! |
|
66 |
|
67 at:index put:anObject |
|
68 self shouldNotImplement |
|
69 ! |
|
70 |
|
71 add:newObject after:oldObject |
|
72 self shouldNotImplement |
|
73 ! |
|
74 |
|
75 add:newObject before:oldObject |
|
76 self shouldNotImplement |
|
77 ! |
|
78 |
|
79 addAll:aCollection |
|
80 "add all elements of the argument, aCollection to the |
|
81 receiver" |
|
82 |
|
83 |mySize "{ Class: SmallInteger }" |
|
84 otherSize "{ Class: SmallInteger }" |
|
85 dstIndex "{ Class: SmallInteger }" |
|
86 newSize newContents| |
|
87 |
|
88 "if aCollection is bigger than a threshhold, its faster |
|
89 to add all and resort - question: what is a good treshhold ?" |
|
90 |
|
91 mySize := self size. |
|
92 otherSize := aCollection size. |
|
93 ((mySize == 0) or:[otherSize > 5]) ifTrue:[ |
|
94 newSize := mySize + otherSize. |
|
95 newContents := Array new:newSize. |
|
96 newContents replaceFrom:1 to:mySize with:contentsArray startingAt:1. |
|
97 (aCollection isKindOf:SequenceableCollection) ifTrue:[ |
|
98 "maybe we can do it in one big move" |
|
99 newContents replaceFrom:(mySize + 1) to:newSize with:aCollection startingAt:1. |
|
100 ] ifFalse:[ |
|
101 dstIndex := mySize + 1. |
|
102 aCollection do:[:element | |
|
103 newContents at:dstIndex put:element. |
|
104 dstIndex := dstIndex + 1 |
|
105 ] |
|
106 ]. |
|
107 firstIndex := 1. |
|
108 lastIndex := newSize. |
|
109 contentsArray := newContents. |
|
110 contentsArray sort:sortBlock. |
|
111 ^ self |
|
112 ]. |
|
113 super addAll:aCollection |
|
114 |
|
115 "#(7 3 9 10 99) asSortedCollection addAll:#(77 0 1 16 5)" |
|
116 ! |
|
117 |
|
118 add:anObject |
|
119 "add the argument, anObject at the proper place in the |
|
120 receiver" |
|
121 |
|
122 |sz index| |
|
123 |
|
124 sz := self size. |
|
125 sz == 0 ifTrue:[ |
|
126 super addLast:anObject |
|
127 ] ifFalse:[ |
|
128 index := self findIndexFor:anObject. |
|
129 self makeRoomAtIndex:index. |
|
130 contentsArray at:index put:anObject |
|
131 ]. |
|
132 ^ anObject |
|
133 ! ! |
|
134 |
|
135 !SortedCollection methodsFor:'testing'! |
|
136 |
|
137 includes:anObject |
|
138 "return true, if the argument, anObject is in the collection. |
|
139 (can reduce the number of compares since we are sorted)" |
|
140 |
|
141 |index| |
|
142 |
|
143 index := self findIndexFor:anObject. |
|
144 ^ (index <= self size) and:[(contentsArray at:index) = anObject] |
|
145 ! |
|
146 |
|
147 occurrencesOf:anObject |
|
148 "return how many times the argument, anObject is in the collection. |
|
149 (can reduce the number of compares since we are sorted)" |
|
150 |
|
151 |index "{ Class: SmallInteger }" |
|
152 mySize "{ Class: SmallInteger }" |
|
153 tally "{ Class: SmallInteger }" | |
|
154 |
|
155 index := self findIndexFor:anObject. |
|
156 mySize := self size. |
|
157 index > mySize ifTrue:[^ 0]. |
|
158 tally := 0. |
|
159 [(index <= mySize) and:[(contentsArray at:index) = anObject]] whileTrue:[ |
|
160 tally := tally + 1. |
|
161 index := index + 1 |
|
162 ]. |
|
163 ^ tally |
|
164 ! ! |
|
165 |
|
166 !SortedCollection methodsFor:'instance protocol'! |
|
167 |
|
168 sortBlock |
|
169 "return the block used for sorting" |
|
170 |
|
171 ^ sortBlock |
|
172 ! |
|
173 |
|
174 sortBlock:aSortBlock |
|
175 "change the sort criteria for a sorted collection, resort the elements of |
|
176 the collection, and return the receiver. The argument, aSortBlock must |
|
177 be a two-argument block which returns true if its arg1 has to come before |
|
178 its arg2 in the collection." |
|
179 |
|
180 sortBlock := aSortBlock. |
|
181 lastIndex > firstIndex ifTrue:[ |
|
182 contentsArray quickSortFrom:firstIndex to:lastIndex sortBlock:aSortBlock |
|
183 ] |
|
184 |
|
185 "#(9 8 7 6 5 4 3) asSortedCollection" |
|
186 "#(9 8 7 6 5 4 3) asSortedCollection sortBlock:[:a : b | a > b]" |
|
187 "#($f $G $z $Y $o $H) asSortedCollectionSortedCollection" |
|
188 "#($f $G $z $Y $o $H) asSortedCollection sortBlock:[:a : b | a asUppercase < b asUppercase]" |
|
189 ! ! |
|
190 |
|
191 !SortedCollection methodsFor:'enumerating'! |
|
192 |
|
193 collect: aBlock |
|
194 | newOrderedCollection | |
|
195 newOrderedCollection := OrderedCollection new. |
|
196 self do: [ :element | newOrderedCollection add: (aBlock value: element) ]. |
|
197 ^newOrderedCollection |
|
198 ! ! |
|
199 |
|
200 !SortedCollection methodsFor:'private'! |
|
201 |
|
202 setSortBlock: aSortBlock |
|
203 "set the sortblock without resorting - private only" |
|
204 |
|
205 sortBlock := aSortBlock |
|
206 ! |
|
207 |
|
208 findIndexFor:anObject |
|
209 "search the index at which to insert anObject. Can also be used |
|
210 to search for an existing element by checking if the element at |
|
211 the returned index is the one we look for." |
|
212 |
|
213 |low "{ Class: SmallInteger}" |
|
214 high "{ Class: SmallInteger}" |
|
215 middle "{ Class: SmallInteger}" |
|
216 element| |
|
217 |
|
218 low := firstIndex. |
|
219 high := lastIndex. |
|
220 [low <= high] whileTrue:[ |
|
221 middle := (low + high) // 2. |
|
222 element := super at:middle. |
|
223 (sortBlock value:element value:anObject) ifTrue:[ |
|
224 "middleelement is smaller than object" |
|
225 low := middle + 1 |
|
226 ] ifFalse:[ |
|
227 high := middle - 1 |
|
228 ] |
|
229 ]. |
|
230 ^ low |
|
231 |
|
232 "#(1 2 3 4 7 99 1313 981989 898989898) asSortedCollection" |
|
233 |
|
234 ! ! |