|
1 " |
|
2 This class is not covered by or part of the ST/X licence. |
|
3 |
|
4 |
|
5 COPYRIGHT. |
|
6 The above file is a Manchester Goodie protected by copyright. |
|
7 These conditions are imposed on the whole Goodie, and on any significant |
|
8 part of it which is separately transmitted or stored: |
|
9 * You must ensure that every copy includes this notice, and that |
|
10 source and author(s) of the material are acknowledged. |
|
11 * These conditions must be imposed on anyone who receives a copy. |
|
12 * The material shall not be used for commercial gain without the prior |
|
13 written consent of the author(s). |
|
14 Further information on the copyright conditions may be obtained by |
|
15 sending electronic mail: |
|
16 To: goodies-lib@cs.man.ac.uk |
|
17 Subject: copyright |
|
18 or by writing to The Smalltalk Goodies Library Manager, Dept of |
|
19 Computer Science, The University, Manchester M13 9PL, UK |
|
20 |
|
21 (C) Copyright 1993 University of Manchester |
|
22 For more information about the Manchester Goodies Library (from which |
|
23 this file was distributed) send e-mail: |
|
24 To: goodies-lib@cs.man.ac.uk |
|
25 Subject: help |
|
26 " |
|
27 |
|
28 |
|
29 |
|
30 SequenceableCollection subclass:#RunArray |
|
31 instanceVariableNames:'runs' |
|
32 classVariableNames:'' |
|
33 poolDictionaries:'' |
|
34 category:'Collections-Sequenceable' |
|
35 ! |
|
36 |
|
37 RunArray comment:'This implements an ordered collection which uses runs to minimise the amount |
|
38 of data that it holds. Basically it should be used if you know that an ordered |
|
39 collections is giong to contain a lot of runs of eactly the same data. Implemented |
|
40 to allow simultation playback, since the ordered collctions which that generates |
|
41 are so big that the complier falls over, though most of it is extremely repetetive. |
|
42 This should be totally abstracted. The user should not be a ble to see the difference |
|
43 between an ordered collection and a ComrpessedOrderedCollection. This has a |
|
44 lot in common with RunArray, and the two should probably share implementation. |
|
45 but I could not do some of the things I wanted with the RunArray code, so this |
|
46 is all done on its own. |
|
47 Some of this could be made faster by adding a cache of the start and finish |
|
48 indices of each run, but since I envisage that most additions etc. will be to |
|
49 and from the end those are not included. In addition I have implemented the |
|
50 bare essentials of this for what I need it for - i.e. add to the end and take |
|
51 off the beginning.'! |
|
52 |
|
53 !RunArray class methodsFor:'documentation'! |
|
54 |
|
55 copyright |
|
56 " |
|
57 This class is not covered by or part of the ST/X licence. |
|
58 |
|
59 |
|
60 COPYRIGHT. |
|
61 The above file is a Manchester Goodie protected by copyright. |
|
62 These conditions are imposed on the whole Goodie, and on any significant |
|
63 part of it which is separately transmitted or stored: |
|
64 * You must ensure that every copy includes this notice, and that |
|
65 source and author(s) of the material are acknowledged. |
|
66 * These conditions must be imposed on anyone who receives a copy. |
|
67 * The material shall not be used for commercial gain without the prior |
|
68 written consent of the author(s). |
|
69 Further information on the copyright conditions may be obtained by |
|
70 sending electronic mail: |
|
71 To: goodies-lib@cs.man.ac.uk |
|
72 Subject: copyright |
|
73 or by writing to The Smalltalk Goodies Library Manager, Dept of |
|
74 Computer Science, The University, Manchester M13 9PL, UK |
|
75 |
|
76 (C) Copyright 1993 University of Manchester |
|
77 For more information about the Manchester Goodies Library (from which |
|
78 this file was distributed) send e-mail: |
|
79 To: goodies-lib@cs.man.ac.uk |
|
80 Subject: help |
|
81 " |
|
82 |
|
83 |
|
84 ! |
|
85 |
|
86 documentation |
|
87 " |
|
88 This implements an array which uses runs to minimise the amount |
|
89 of data that it holds. Basically it should be used if you know that an array |
|
90 is going to contain a lot of runs of exactly the same data. |
|
91 |
|
92 The user should not be able to see the difference between an Array and a RunArray. This has a |
|
93 |
|
94 Notice: |
|
95 there is only a space saving if there are really runs (i.e. multiple |
|
96 elements which compare same). |
|
97 Otherwise, an Array is more compact. |
|
98 |
|
99 |
|
100 [author:] |
|
101 Claus Gittinger |
|
102 |
|
103 [see also:] |
|
104 Array OrderedCollection CompressedorderedCollection |
|
105 " |
|
106 ! |
|
107 |
|
108 examples |
|
109 " |
|
110 this eats up a lot of memory ... |
|
111 ... but its relatively fast: |
|
112 [exBegin] |
|
113 |coll| |
|
114 |
|
115 coll := OrderedCollection new. |
|
116 Transcript showCr:( |
|
117 Time millisecondsToRun:[ |
|
118 100000 timesRepeat:[coll add:'hello']. |
|
119 100000 timesRepeat:[coll add:'world']. |
|
120 ] |
|
121 ). |
|
122 coll inspect. |
|
123 [exEnd] |
|
124 |
|
125 |
|
126 this is very space efficient ... |
|
127 ... but much slower: |
|
128 [exBegin] |
|
129 |coll| |
|
130 |
|
131 coll := RunArray new. |
|
132 Transcript showCr:( |
|
133 Time millisecondsToRun:[ |
|
134 100000 timesRepeat:[coll add:'hello']. |
|
135 100000 timesRepeat:[coll add:'world']. |
|
136 ] |
|
137 ). |
|
138 coll inspect. |
|
139 [exEnd] |
|
140 |
|
141 |
|
142 this is very space efficient ... |
|
143 ... AND much faster: |
|
144 [exBegin] |
|
145 |coll| |
|
146 |
|
147 coll := RunArray new. |
|
148 Transcript showCr:( |
|
149 Time millisecondsToRun:[ |
|
150 coll add:'hello' withCount:100000. |
|
151 coll add:'world' withCount:100000. |
|
152 ] |
|
153 ). |
|
154 coll inspect. |
|
155 [exEnd] |
|
156 |
|
157 |
|
158 this is very space INEFFICIENT (a real memory pig ;-) ... |
|
159 ... and much slower: |
|
160 [exBegin] |
|
161 |coll| |
|
162 |
|
163 coll := RunArray new. |
|
164 Transcript showCr:( |
|
165 Time millisecondsToRun:[ |
|
166 1 to:1000 do:[:i | coll add:i]. |
|
167 ] |
|
168 ). |
|
169 coll inspect. |
|
170 [exEnd] |
|
171 |
|
172 |
|
173 things like this are VERY slow: |
|
174 [exBegin] |
|
175 |coll| |
|
176 |
|
177 coll := RunArray new. |
|
178 1 to:1000 do:[:i | coll add:i]. |
|
179 Transcript showCr:( |
|
180 Time millisecondsToRun:[ |
|
181 1000 to:1 by:-2 do:[:i | coll removeIndex:i]. |
|
182 ] |
|
183 ) |
|
184 [exEnd] |
|
185 |
|
186 much faster with OCs (although these are not optimal for this, too): |
|
187 [exBegin] |
|
188 |coll| |
|
189 |
|
190 coll := OrderedCollection new. |
|
191 1 to:1000 do:[:i | coll add:i]. |
|
192 Transcript showCr:( |
|
193 Time millisecondsToRun:[ |
|
194 1000 to:1 by:-2 do:[:i | coll removeIndex:i]. |
|
195 ] |
|
196 ) |
|
197 [exEnd] |
|
198 |
|
199 in general, such things are better done by constructing a new collection |
|
200 from scratch (use #select: or #collect:) |
|
201 " |
|
202 ! ! |
|
203 |
|
204 !RunArray class methodsFor:'instance creation'! |
|
205 |
|
206 new:size |
|
207 "ignore the size argument - we dont know how many runs are |
|
208 needed - anyway" |
|
209 |
|
210 ^ self new |
|
211 ! ! |
|
212 |
|
213 !RunArray methodsFor:'accessing'! |
|
214 |
|
215 at:anInteger |
|
216 "Answer the element at index anInteger. |
|
217 at: is used by a knowledgeable client to access an existing element |
|
218 This is a pretty dumb thing to do a compressed collection and it is |
|
219 not at all efficient (think of that as a discouragement)." |
|
220 |
|
221 |position "{ Class: SmallInteger }" |
|
222 nRuns "{ Class: SmallInteger }"| |
|
223 |
|
224 (anInteger > 0) ifTrue:[ |
|
225 position := 1. |
|
226 nRuns := runs size. |
|
227 1 to:nRuns by:2 do:[:runIndex | |
|
228 |runLen| |
|
229 |
|
230 runLen := runs at:runIndex. |
|
231 anInteger >= position ifTrue:[ |
|
232 anInteger < (position + runLen) ifTrue:[ |
|
233 ^ runs at:(runIndex + 1) |
|
234 ]. |
|
235 ]. |
|
236 position := position + runLen |
|
237 ] |
|
238 ]. |
|
239 ^ self errorInvalidKey:anInteger |
|
240 |
|
241 " |
|
242 |c| |
|
243 |
|
244 c := RunArray new. |
|
245 c add:1; add:1; add:1; add:2; add:2; add:3; add:3; add:4; add:5. |
|
246 c at:1. |
|
247 c at:2. |
|
248 c at:3. |
|
249 c at:4. |
|
250 c at:5. |
|
251 c at:6. |
|
252 c at:7. |
|
253 c at:8. |
|
254 c at:9. |
|
255 c at:10. |
|
256 " |
|
257 |
|
258 "Modified: 10.5.1996 / 16:59:03 / cg" |
|
259 ! |
|
260 |
|
261 at:index put:anObject |
|
262 "Put anObject at element index anInteger. |
|
263 at:put: can not be used to append, front or back, to an ordered |
|
264 collection; it is used by a knowledgeable client to replace an |
|
265 element. It doesn't make a lot of sense for a compressed collection, |
|
266 and as you can see, the implementation is awful - still if you will |
|
267 insist on using this what can you expect. Basically this just copies |
|
268 itself up to the start point then adds the required element then |
|
269 copies the rest of itself" |
|
270 |
|
271 |runSz runIndex runOffset len l1 l2 prevIdx nextIdx |
|
272 val newRuns newValues prevLen prevVal nextLen nextVal idx| |
|
273 |
|
274 runSz := runs size. |
|
275 |
|
276 runIndex := nil. |
|
277 (index > 0) ifTrue:[ |
|
278 runOffset := 1. |
|
279 idx := 1. |
|
280 [runIndex isNil and:[idx < runSz]] whileTrue:[ |
|
281 len := runs at:idx. |
|
282 nextIdx := runOffset + len. |
|
283 index >= runOffset ifTrue:[ |
|
284 index < nextIdx ifTrue:[ |
|
285 runIndex := idx. |
|
286 nextIdx := runOffset. "/ dont advance |
|
287 ]. |
|
288 ]. |
|
289 runOffset := nextIdx. |
|
290 idx := idx + 2. |
|
291 ] |
|
292 ]. |
|
293 runIndex isNil ifTrue:[ |
|
294 ^ self errorInvalidKey:index |
|
295 ]. |
|
296 |
|
297 val := runs at:(runIndex + 1). |
|
298 |
|
299 "/ easiest: value there is the same ... |
|
300 |
|
301 val = anObject ifTrue:[ |
|
302 ^ anObject |
|
303 ]. |
|
304 |
|
305 "/ if the length is 1, this is an island ... |
|
306 "/ ... which is either easy, or requires a merge. |
|
307 |
|
308 len := runs at:runIndex. |
|
309 len = 1 ifTrue:[ |
|
310 "/ check if it can be merged into the next or previous run |
|
311 |
|
312 runIndex > 1 ifTrue:[ |
|
313 prevIdx := runIndex - 2. |
|
314 prevVal := runs at:(prevIdx + 1). |
|
315 prevVal = anObject ifTrue:[ |
|
316 "/ can merge it into previous |
|
317 |
|
318 prevLen := runs at:prevIdx. |
|
319 |
|
320 "/ check if merge into next is also possible (filling an island) |
|
321 |
|
322 runIndex < (runSz - 1) ifTrue:[ |
|
323 nextIdx := runIndex + 2. |
|
324 nextVal := runs at:(nextIdx + 1). |
|
325 nextVal = anObject ifTrue:[ |
|
326 "/ can merge with both. |
|
327 |
|
328 nextLen := runs at:nextIdx. |
|
329 |
|
330 runs at:prevIdx put:prevLen+nextLen+1. |
|
331 runSz := (runSz - 4). |
|
332 newRuns := Array new:runSz. |
|
333 newRuns replaceFrom:1 to:(prevIdx + 1) with:runs startingAt:1. |
|
334 newRuns replaceFrom:runIndex to:runSz with:runs startingAt:nextIdx+2. |
|
335 runs := newRuns. |
|
336 ^ anObject |
|
337 ] |
|
338 ]. |
|
339 |
|
340 runs at:prevIdx put:prevLen+1. |
|
341 |
|
342 runSz := (runSz - 2). |
|
343 newRuns := Array new:runSz. |
|
344 newRuns replaceFrom:1 to:(runIndex - 1) with:runs startingAt:1. |
|
345 newRuns replaceFrom:runIndex to:runSz with:runs startingAt:runIndex+2. |
|
346 runs := newRuns. |
|
347 |
|
348 ^ anObject |
|
349 ]. |
|
350 ]. |
|
351 |
|
352 "/ check if merge into next is possible |
|
353 |
|
354 runIndex < runSz ifTrue:[ |
|
355 nextIdx := runIndex + 2. |
|
356 nextVal := runs at:nextIdx+1. |
|
357 nextVal = anObject ifTrue:[ |
|
358 nextLen := runs at:nextIdx. |
|
359 runs at:nextIdx put:nextLen + 1. |
|
360 |
|
361 runSz := (runSz - 2). |
|
362 newRuns := Array new:runSz. |
|
363 newRuns replaceFrom:1 to:(runIndex - 1) with:runs startingAt:1. |
|
364 newRuns replaceFrom:runIndex to:runSz with:runs startingAt:nextIdx. |
|
365 runs := newRuns. |
|
366 ^ anObject |
|
367 ]. |
|
368 ]. |
|
369 |
|
370 "/ no merge; island remains |
|
371 |
|
372 runs at:(runIndex+1) put:anObject. |
|
373 ^ anObject |
|
374 ]. |
|
375 |
|
376 runOffset == index ifTrue:[ |
|
377 "/ at the beginning of that run ... |
|
378 |
|
379 "/ check if its better added to the previous run ... |
|
380 |
|
381 runIndex > 1 ifTrue:[ |
|
382 prevIdx := runIndex - 2. |
|
383 prevVal := runs at:prevIdx+1. |
|
384 prevVal = anObject ifTrue:[ |
|
385 prevLen := runs at:prevIdx. |
|
386 runs at:prevIdx put:prevLen + 1. |
|
387 runs at:runIndex put:len - 1. |
|
388 ^ anObject. |
|
389 ]. |
|
390 ]. |
|
391 |
|
392 "/ must cut off 1 & insert a new run before .. |
|
393 |
|
394 runs at:runIndex put:len - 1. |
|
395 |
|
396 runSz := (runSz + 2). |
|
397 newRuns := Array new:runSz. |
|
398 newRuns replaceFrom:1 to:(runIndex - 1) with:runs startingAt:1. |
|
399 newRuns replaceFrom:runIndex+2 to:runSz with:runs startingAt:runIndex. |
|
400 runs := newRuns. |
|
401 |
|
402 runs at:runIndex put:1. |
|
403 runs at:runIndex+1 put:anObject. |
|
404 ^ anObject |
|
405 ]. |
|
406 |
|
407 (runOffset + len - 1) == index ifTrue:[ |
|
408 "/ at the end ... |
|
409 |
|
410 "/ check if its better added to the next run ... |
|
411 |
|
412 runIndex < runSz ifTrue:[ |
|
413 nextIdx := runIndex + 2. |
|
414 nextVal := runs at:nextIdx+1. |
|
415 nextVal = anObject ifTrue:[ |
|
416 nextLen := runs at:nextIdx. |
|
417 runs at:nextIdx put:nextLen + 1. |
|
418 runs at:runIndex put:len - 1. |
|
419 ^ anObject. |
|
420 ]. |
|
421 ]. |
|
422 |
|
423 "/ must cut off 1 & insert a new run after .. |
|
424 |
|
425 runs at:runIndex put:len - 1. |
|
426 |
|
427 runSz := (runSz + 2). |
|
428 newRuns := Array new:runSz. |
|
429 newRuns replaceFrom:1 to:(runIndex + 1) with:runs startingAt:1. |
|
430 newRuns replaceFrom:runIndex+4 to:runSz with:runs startingAt:runIndex+2. |
|
431 runs := newRuns. |
|
432 |
|
433 runs at:runIndex+2 put:1. |
|
434 runs at:runIndex+2+1 put:anObject. |
|
435 ^ anObject |
|
436 ]. |
|
437 |
|
438 "/ hardest - split run into two, insert new run in-between |
|
439 |
|
440 runSz := (runSz + 4). |
|
441 newRuns := Array new:runSz. |
|
442 |
|
443 runIndex > 1 ifTrue:[ |
|
444 newRuns replaceFrom:1 to:runIndex-1 with:runs. |
|
445 ]. |
|
446 newRuns replaceFrom:runIndex+6 to:(runSz+4) with:runs startingAt:runIndex+2. |
|
447 |
|
448 l2 := len - (index - runOffset). |
|
449 l1 := len - l2. |
|
450 l2 := l2 - 1. |
|
451 |
|
452 newRuns at:runIndex put:l1. |
|
453 newRuns at:runIndex+1 put:val. |
|
454 |
|
455 newRuns at:runIndex+4 put:l2. |
|
456 newRuns at:runIndex+5 put:val. |
|
457 |
|
458 "/ insert |
|
459 newRuns at:runIndex+2 put:1. |
|
460 newRuns at:runIndex+3 put:anObject. |
|
461 |
|
462 runs := newRuns. |
|
463 ^ anObject |
|
464 |
|
465 " |
|
466 |c| |
|
467 |
|
468 Transcript cr. |
|
469 |
|
470 c := RunArray new. |
|
471 c add:1; add:1; add:1; add:2; add:2; add:3; add:3; add:4; add:5; yourself. |
|
472 Transcript showCr:c. |
|
473 |
|
474 c at:1 put:$a. |
|
475 Transcript showCr:c. |
|
476 c. |
|
477 |
|
478 c at:3 put:$a. |
|
479 Transcript showCr:c. |
|
480 c. |
|
481 |
|
482 c at:4 put:$a. |
|
483 Transcript showCr:c. |
|
484 c. |
|
485 |
|
486 c at:5 put:$a. |
|
487 Transcript showCr:c. |
|
488 c. |
|
489 |
|
490 c at:2 put:$0. |
|
491 Transcript showCr:c. |
|
492 c. |
|
493 |
|
494 c at:2 put:$a. |
|
495 Transcript showCr:c. |
|
496 c. |
|
497 |
|
498 Transcript showCr:c. |
|
499 " |
|
500 |
|
501 "Modified: 11.5.1996 / 08:41:49 / cg" |
|
502 ! |
|
503 |
|
504 size |
|
505 "Answer how many elements the receiver contains." |
|
506 |
|
507 |n "{ Class: SmallInteger }" |
|
508 runSz "{ Class: SmallInteger }"| |
|
509 |
|
510 n := 0. |
|
511 runSz := runs size. |
|
512 1 to:runSz by:2 do:[:i | |
|
513 n := n + (runs at:i) |
|
514 ]. |
|
515 ^ n |
|
516 ! ! |
|
517 |
|
518 !RunArray methodsFor:'adding'! |
|
519 |
|
520 add:newObject |
|
521 "add newObject at the end; returns the object (sigh)" |
|
522 |
|
523 ^ self add:newObject withOccurrences:1. |
|
524 |
|
525 " |
|
526 |c| |
|
527 |
|
528 c := RunArray new. |
|
529 c add:1; add:1; add:1; add:2; add:2; add:3; add:3; add:4; add:5; yourself. |
|
530 " |
|
531 |
|
532 "Modified: 10.5.1996 / 17:01:20 / cg" |
|
533 ! |
|
534 |
|
535 add:newObject withOccurrences:n |
|
536 "add newObject n times at the end; returns the object (sigh)" |
|
537 |
|
538 |lastIdx runSz newRuns| |
|
539 |
|
540 runs notNil ifTrue:[ |
|
541 "/ check for merge |
|
542 |
|
543 runSz := runs size. |
|
544 |
|
545 (runs at:runSz) = newObject ifTrue:[ |
|
546 lastIdx := runSz - 1. |
|
547 runs at:lastIdx put:(runs at:lastIdx) + n. |
|
548 ^ newObject |
|
549 ]. |
|
550 |
|
551 newRuns := Array new:(runSz + 2). |
|
552 newRuns replaceFrom:1 to:runSz with:runs. |
|
553 newRuns at:runSz+1 put:n. |
|
554 newRuns at:runSz+2 put:newObject. |
|
555 runs := newRuns. |
|
556 ] ifFalse:[ |
|
557 runs := Array with:n with:newObject. |
|
558 ]. |
|
559 ^ newObject |
|
560 |
|
561 " |
|
562 |c| |
|
563 |
|
564 c := RunArray new. |
|
565 c add:1 withOccurrences:1000; yourself. |
|
566 c add:2 withOccurrences:1000; yourself. |
|
567 " |
|
568 |
|
569 "Modified: 10.5.1996 / 18:29:56 / cg" |
|
570 ! |
|
571 |
|
572 grow:howBig |
|
573 "grow or shrink the receiver to contain howBig elements. |
|
574 If growing, new slots will be filled with nil." |
|
575 |
|
576 |sz info runIndex runOffset runSz newRuns| |
|
577 |
|
578 sz := self size. |
|
579 |
|
580 howBig == sz ifTrue:[^ self]. |
|
581 |
|
582 howBig == 0 ifTrue:[ |
|
583 runs := nil. |
|
584 ^ self. |
|
585 ]. |
|
586 |
|
587 runs isNil ifTrue:[ |
|
588 runs := Array with:howBig with:nil. |
|
589 ^ self |
|
590 ]. |
|
591 |
|
592 runSz := runs size. |
|
593 |
|
594 howBig > sz ifTrue:[ |
|
595 newRuns := Array new:(runSz + 2). |
|
596 newRuns replaceFrom:1 to:runSz with:runs startingAt:1. |
|
597 newRuns at:(runSz+1) put:(howBig - sz). |
|
598 runs := newRuns. |
|
599 ^ self |
|
600 ]. |
|
601 |
|
602 "/ shrinking; possibly cut of a run |
|
603 |
|
604 info := self runIndexAndStartIndexForIndex:howBig. |
|
605 runIndex := info at:1. |
|
606 runOffset := info at:2. |
|
607 |
|
608 howBig == (runOffset - 1) ifTrue:[ |
|
609 "/ we are lucky - new size is up-to previous run |
|
610 |
|
611 runs := runs copyFrom:1 to:runIndex-1. |
|
612 ] ifFalse:[ |
|
613 runs := runs copyFrom:1 to:(runIndex+1). |
|
614 runs at:runIndex put:(howBig - runOffset + 1) |
|
615 ]. |
|
616 |
|
617 " |
|
618 |c| |
|
619 |
|
620 c := RunArray new. |
|
621 c addAll:#(1 2 3 4 4 4 4 5 5 5 1 2 3); yourself. |
|
622 |
|
623 c grow:50; yourself. |
|
624 |
|
625 c grow:7; yourself. |
|
626 |
|
627 c grow:6; yourself. |
|
628 |
|
629 c grow:0; yourself. |
|
630 " |
|
631 |
|
632 "Modified: 10.5.1996 / 18:11:54 / cg" |
|
633 ! ! |
|
634 |
|
635 !RunArray methodsFor:'converting'! |
|
636 |
|
637 asOrderedCollection |
|
638 "Uncompress this collection." |
|
639 |
|
640 |newCollection| |
|
641 |
|
642 newCollection := OrderedCollection new. |
|
643 newCollection addAll:self. |
|
644 ^ newCollection |
|
645 |
|
646 "Modified: 10.5.1996 / 13:31:49 / cg" |
|
647 ! ! |
|
648 |
|
649 !RunArray methodsFor:'enumerating'! |
|
650 |
|
651 do:aBlock |
|
652 "Evaluate aBlock with each of the receiver's elements as the |
|
653 argument. " |
|
654 |
|
655 runs notNil ifTrue:[ |
|
656 runs pairWiseDo:[:len :val | |
|
657 len timesRepeat: [aBlock value:val] |
|
658 ] |
|
659 ] |
|
660 |
|
661 "Modified: 10.5.1996 / 16:56:01 / cg" |
|
662 ! ! |
|
663 |
|
664 !RunArray methodsFor:'printing'! |
|
665 |
|
666 storeOn:aStream |
|
667 "Append to aStream an expression which, if evaluated, will generate |
|
668 an object similar to the receiver." |
|
669 |
|
670 aStream nextPutAll: '(RunArray new'. |
|
671 runs notNil ifTrue:[ |
|
672 runs pairWiseDo:[:len :val | |
|
673 aStream nextPutAll: ' add:'; nextPutAll:val storeString. |
|
674 len == 1 ifFalse:[ |
|
675 aStream nextPutAll:' withCount:'; nextPutAll:len printString. |
|
676 ]. |
|
677 aStream nextPutAll:';' |
|
678 ]. |
|
679 aStream nextPutAll:' yourself' |
|
680 ]. |
|
681 aStream nextPutAll:')' |
|
682 |
|
683 " |
|
684 (RunArray new |
|
685 add:1; |
|
686 add:1; |
|
687 add:2; |
|
688 add:3; |
|
689 add:4 withCount:100; |
|
690 add:5; |
|
691 yourself) storeString |
|
692 |
|
693 RunArray new storeString |
|
694 " |
|
695 ! ! |
|
696 |
|
697 !RunArray methodsFor:'private'! |
|
698 |
|
699 find:oldObject |
|
700 "If I contain oldObject return its index, otherwise create an error |
|
701 notifier. It will answer with the position of the very first element of |
|
702 that value." |
|
703 |
|
704 |position| |
|
705 |
|
706 position := self find:oldObject ifAbsent:0. |
|
707 position ~~ 0 ifTrue:[ |
|
708 ^ position |
|
709 ]. |
|
710 |
|
711 self errorValueNotFound:oldObject |
|
712 |
|
713 " |
|
714 |c| |
|
715 |
|
716 c := RunArray new. |
|
717 c add:1; add:1; add:1; add:2; add:2; add:3; add:3; add:4; add:5. |
|
718 c find:2. |
|
719 |
|
720 c find:99 |
|
721 " |
|
722 |
|
723 "Modified: 10.5.1996 / 13:39:58 / cg" |
|
724 ! |
|
725 |
|
726 find:oldObject ifAbsent:exceptionBlock |
|
727 "If I contain oldObject return its index, otherwise execute the |
|
728 exception block. It will answer with the position of the very first |
|
729 element of that value." |
|
730 |
|
731 |position| |
|
732 |
|
733 position := 1. |
|
734 runs notNil ifTrue:[ |
|
735 runs pairWiseDo:[:len :val | |
|
736 val = oldObject ifTrue:[ |
|
737 ^ position |
|
738 ]. |
|
739 position := position + len. |
|
740 ]. |
|
741 ]. |
|
742 ^ exceptionBlock value |
|
743 |
|
744 "Modified: 10.5.1996 / 13:54:25 / cg" |
|
745 ! |
|
746 |
|
747 isEmpty |
|
748 "Am I empty or not. Returns a boolean" |
|
749 |
|
750 ^ runs notNil |
|
751 ! |
|
752 |
|
753 runIndexAndStartIndexForIndex:anIndex |
|
754 "given a logical index, find the index of that run and the logical index |
|
755 of the first item in that run." |
|
756 |
|
757 |position nRuns "{ Class: SmallInteger }"| |
|
758 |
|
759 position := 1. |
|
760 nRuns := runs size. |
|
761 1 to:nRuns by:2 do:[:runIndex | |
|
762 |runLen runLast| |
|
763 |
|
764 runLen := runs at:runIndex. |
|
765 anIndex >= position ifTrue:[ |
|
766 runLast := position + runLen - 1. |
|
767 anIndex <= runLast ifTrue:[ |
|
768 ^ Array with:runIndex with:position |
|
769 ]. |
|
770 ]. |
|
771 position := position + runLen |
|
772 ]. |
|
773 |
|
774 ^ #(0 0) |
|
775 |
|
776 "Created: 10.5.1996 / 17:12:28 / cg" |
|
777 "Modified: 10.5.1996 / 17:13:42 / cg" |
|
778 ! |
|
779 |
|
780 runIndexForIndex:anIndex |
|
781 "given a logical index, find the index of that run" |
|
782 |
|
783 ^ (self runIndexAndStartIndexForIndex:anIndex) at:1 |
|
784 |
|
785 "Modified: 10.5.1996 / 17:13:45 / cg" |
|
786 ! ! |
|
787 |
|
788 !RunArray methodsFor:'user interface'! |
|
789 |
|
790 inspect |
|
791 "Reimplement so that they don't get an ordered collection inspector |
|
792 which would get very confused." |
|
793 |
|
794 self basicInspect |
|
795 |
|
796 "Modified: 10.5.1996 / 18:24:43 / cg" |
|
797 ! ! |
|
798 |
|
799 !RunArray class methodsFor:'documentation'! |
|
800 |
|
801 version |
|
802 ^ '$Header: /cvs/stx/stx/libbasic2/RunArray.st,v 1.1 1996-05-11 10:47:55 cg Exp $' |
|
803 ! ! |