20 OrderedCollection comment:' |
20 OrderedCollection comment:' |
21 |
21 |
22 COPYRIGHT (c) 1989 by Claus Gittinger |
22 COPYRIGHT (c) 1989 by Claus Gittinger |
23 All Rights Reserved |
23 All Rights Reserved |
24 |
24 |
25 $Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.11 1994-03-30 09:36:27 claus Exp $ |
25 $Header: /cvs/stx/stx/libbasic/OrderedCollection.st,v 1.12 1994-05-17 10:08:27 claus Exp $ |
26 written spring 89 by claus |
26 written spring 89 by claus |
27 '! |
27 '! |
28 |
28 |
29 !OrderedCollection class methodsFor:'documentation'! |
29 !OrderedCollection class methodsFor:'documentation'! |
30 |
30 |
412 |
412 |
413 |end| |
413 |end| |
414 |
414 |
415 end := stop + firstIndex - 1. |
415 end := stop + firstIndex - 1. |
416 ((start >= 1) and:[end <= lastIndex]) ifTrue:[ |
416 ((start >= 1) and:[end <= lastIndex]) ifTrue:[ |
417 ^ contentsArray replaceFrom:(start + firstIndex - 1) |
417 contentsArray |
418 to:end |
418 replaceFrom:(start + firstIndex - 1) |
419 with:aCollection |
419 to:end |
420 startingAt:repStart |
420 with:aCollection |
|
421 startingAt:repStart. |
|
422 ^ self |
421 ]. |
423 ]. |
422 ^ super replaceFrom:start to:stop with:aCollection startingAt:repStart |
424 ^ super replaceFrom:start to:stop with:aCollection startingAt:repStart |
|
425 ! ! |
|
426 |
|
427 !OrderedCollection methodsFor:'searching'! |
|
428 |
|
429 after:anObject |
|
430 "return the element, after anObject. |
|
431 If anObject is not in the receiver, report an error." |
|
432 |
|
433 ^ self after:anObject ifAbsent:[self errorNotFound] |
|
434 |
|
435 " |
|
436 #(4 3 2 1) asOrderedCollection after:3. |
|
437 #(4 3 2 1) asOrderedCollection after:5 |
|
438 #(4 3 2 1) asOrderedCollection after:1 |
|
439 " |
|
440 ! |
|
441 |
|
442 after:anObject ifAbsent:exceptionBlock |
|
443 "return the element after the argument anObject, nil if there is none. |
|
444 If anObject is not in the receiver, return the result from evaluating exceptionBlock." |
|
445 |
|
446 |idx| |
|
447 |
|
448 idx := self indexOf:anObject. |
|
449 idx ~~ 0 ifTrue:[ |
|
450 idx == lastIndex ifTrue:[^ nil]. |
|
451 ^ self at:(idx + 1). |
|
452 ]. |
|
453 ^ exceptionBlock value |
|
454 |
|
455 " |
|
456 #(4 3 2 1) asOrderedCollection after:3. |
|
457 #(4 3 2 1) asOrderedCollection after:5 |
|
458 #(4 3 2 1) asOrderedCollection after:1 |
|
459 " |
|
460 ! |
|
461 |
|
462 before:anObject |
|
463 "return the element before the argument, anObject. |
|
464 If anObject is not in the receiver, report an error." |
|
465 |
|
466 ^ self before:anObject ifAbsent:[self errorNotFound] |
|
467 |
|
468 " |
|
469 #(4 3 2 1) asOrderedCollection before:3. |
|
470 #(4 3 2 1) asOrderedCollection before:4 |
|
471 #(4 3 2 1) asOrderedCollection before:0 |
|
472 " |
|
473 ! |
|
474 |
|
475 before:anObject ifAbsent:exceptionBlock |
|
476 "return the element before the argument anObject, nil if there is none. |
|
477 If anObject is not in the receiver, return the result from evaluating exceptionBlock." |
|
478 |
|
479 |idx| |
|
480 |
|
481 idx := self indexOf:anObject. |
|
482 idx ~~ 0 ifTrue:[ |
|
483 idx == firstIndex ifTrue:[^ nil]. |
|
484 ^ self at:(idx - 1). |
|
485 ]. |
|
486 ^ exceptionBlock value |
|
487 |
|
488 " |
|
489 #(4 3 2 1) asOrderedCollection before:3. |
|
490 #(4 3 2 1) asOrderedCollection before:5 |
|
491 #(4 3 2 1) asOrderedCollection before:1 |
|
492 #(4 3 2 1) asOrderedCollection before:4 |
|
493 " |
423 ! ! |
494 ! ! |
424 |
495 |
425 !OrderedCollection methodsFor:'private'! |
496 !OrderedCollection methodsFor:'private'! |
426 |
497 |
427 setFirstIndex:newFirstIndex lastIndex:newLastIndex |
498 setFirstIndex:newFirstIndex lastIndex:newLastIndex |
444 sz := self size. |
515 sz := self size. |
445 |
516 |
446 "if there is lots of room at the beginning (> 50%), shift instead of growing" |
517 "if there is lots of room at the beginning (> 50%), shift instead of growing" |
447 oldSize > (sz * 2) ifTrue:[ |
518 oldSize > (sz * 2) ifTrue:[ |
448 startIndex := firstIndex // 4. |
519 startIndex := firstIndex // 4. |
449 contentsArray replaceFrom:startIndex to:startIndex + sz - 1 with:contentsArray startingAt:firstIndex. |
520 contentsArray |
|
521 replaceFrom:startIndex |
|
522 to:startIndex + sz - 1 |
|
523 with:contentsArray |
|
524 startingAt:firstIndex. |
450 contentsArray from:startIndex + sz to:lastIndex put:nil. |
525 contentsArray from:startIndex + sz to:lastIndex put:nil. |
451 firstIndex := startIndex. |
526 firstIndex := startIndex. |
452 lastIndex := startIndex + sz - 1. |
527 lastIndex := startIndex + sz - 1. |
453 ^ self |
528 ^ self |
454 ]. |
529 ]. |
472 sz := self size. |
547 sz := self size. |
473 |
548 |
474 "if there is lots of room at the end (> 50%), shift instead of growing" |
549 "if there is lots of room at the end (> 50%), shift instead of growing" |
475 oldSize > (sz * 2) ifTrue:[ |
550 oldSize > (sz * 2) ifTrue:[ |
476 startIndex := oldSize // 4. |
551 startIndex := oldSize // 4. |
477 contentsArray replaceFrom:startIndex to:startIndex + sz - 1 with:contentsArray startingAt:1. |
552 contentsArray |
|
553 replaceFrom:startIndex |
|
554 to:startIndex + sz - 1 |
|
555 with:contentsArray |
|
556 startingAt:1. |
478 contentsArray from:1 to:(startIndex - 1) put:nil. |
557 contentsArray from:1 to:(startIndex - 1) put:nil. |
479 firstIndex := startIndex. |
558 firstIndex := startIndex. |
480 lastIndex := startIndex + sz - 1. |
559 lastIndex := startIndex + sz - 1. |
481 ^ self |
560 ^ self |
482 ]. |
561 ]. |
483 newSize := oldSize * 2. |
562 newSize := oldSize * 2. |
484 newSize == 0 ifTrue:[ newSize := 1]. |
563 newSize == 0 ifTrue:[ newSize := 1]. |
485 newContents := Array new:newSize. |
564 newContents := Array new:newSize. |
486 newContents replaceFrom:(oldSize + 1) to:newSize with:contentsArray startingAt:1. |
565 newContents |
|
566 replaceFrom:(oldSize + 1) |
|
567 to:newSize |
|
568 with:contentsArray |
|
569 startingAt:1. |
487 contentsArray := newContents. |
570 contentsArray := newContents. |
488 firstIndex := firstIndex + oldSize. |
571 firstIndex := firstIndex + oldSize. |
489 lastIndex := lastIndex + oldSize |
572 lastIndex := lastIndex + oldSize |
490 ! |
573 ! |
491 |
574 |
500 newSize "{ Class:SmallInteger }" |
583 newSize "{ Class:SmallInteger }" |
501 oldSize "{ Class:SmallInteger }" | |
584 oldSize "{ Class:SmallInteger }" | |
502 |
585 |
503 oldSize := contentsArray size. |
586 oldSize := contentsArray size. |
504 ((firstIndex > 1) and:[firstIndex > (oldSize // 4)]) ifTrue:[ |
587 ((firstIndex > 1) and:[firstIndex > (oldSize // 4)]) ifTrue:[ |
505 "there is room at the beginning" |
588 "there is room (>25%) at the beginning" |
506 |
589 |
507 index == 1 ifFalse:[ |
590 index == 1 ifFalse:[ |
508 contentsArray replaceFrom:(firstIndex - 1) to:(index - 1) |
591 contentsArray |
509 with:contentsArray startingAt:firstIndex. |
592 replaceFrom:(firstIndex - 1) |
|
593 to:(index - 1) |
|
594 with:contentsArray |
|
595 startingAt:firstIndex. |
510 contentsArray at:index put:nil. |
596 contentsArray at:index put:nil. |
511 ]. |
597 ]. |
512 firstIndex := firstIndex - 1. |
598 firstIndex := firstIndex - 1. |
513 ^ self |
599 ^ self |
514 ]. |
600 ]. |
515 lastIndex < (oldSize * 3 // 4) ifTrue:[ |
601 lastIndex < (oldSize * 3 // 4) ifTrue:[ |
516 "there is room at the end" |
602 "there is room (>25%) at the end" |
517 |
603 |
518 index == (lastIndex + 1) ifFalse:[ |
604 index == (lastIndex + 1) ifFalse:[ |
519 contentsArray replaceFrom:(index + 1) to:(lastIndex + 1) |
605 contentsArray |
520 with:contentsArray startingAt:index. |
606 replaceFrom:(index + 1) |
|
607 to:(lastIndex + 1) |
|
608 with:contentsArray |
|
609 startingAt:index. |
521 contentsArray at:index put:nil |
610 contentsArray at:index put:nil |
522 ]. |
611 ]. |
523 lastIndex := lastIndex + 1. |
612 lastIndex := lastIndex + 1. |
524 ^ self |
613 ^ self |
525 ]. |
614 ]. |
529 index == 1 ifFalse:[ |
618 index == 1 ifFalse:[ |
530 newContents replaceFrom:1 to:index-1 |
619 newContents replaceFrom:1 to:index-1 |
531 with:contentsArray startingAt:1. |
620 with:contentsArray startingAt:1. |
532 ]. |
621 ]. |
533 index == newSize ifFalse:[ |
622 index == newSize ifFalse:[ |
534 newContents replaceFrom:index + 1 to:oldSize + 1 |
623 newContents |
535 with:contentsArray startingAt:index. |
624 replaceFrom:index + 1 |
|
625 to:oldSize + 1 |
|
626 with:contentsArray |
|
627 startingAt:index. |
536 ]. |
628 ]. |
537 contentsArray := newContents. |
629 contentsArray := newContents. |
538 lastIndex := lastIndex + 1 |
630 lastIndex := lastIndex + 1 |
539 ! |
631 ! |
540 |
632 |