OrdColl.st
author claus
Fri, 25 Feb 1994 14:00:53 +0100
changeset 56 be0ed17e6f85
parent 42 e33491f6f260
child 68 59faa75185ba
permissions -rw-r--r--
*** empty log message ***
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
     1
"
5
67342904af11 *** empty log message ***
claus
parents: 3
diff changeset
     2
 COPYRIGHT (c) 1989 by Claus Gittinger
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
     3
              All Rights Reserved
a27a279701f8 Initial revision
claus
parents:
diff changeset
     4
a27a279701f8 Initial revision
claus
parents:
diff changeset
     5
 This software is furnished under a license and may be used
a27a279701f8 Initial revision
claus
parents:
diff changeset
     6
 only in accordance with the terms of that license and with the
a27a279701f8 Initial revision
claus
parents:
diff changeset
     7
 inclusion of the above copyright notice.   This software may not
a27a279701f8 Initial revision
claus
parents:
diff changeset
     8
 be provided or otherwise made available to, or used by, any
a27a279701f8 Initial revision
claus
parents:
diff changeset
     9
 other person.  No title to or ownership of the software is
a27a279701f8 Initial revision
claus
parents:
diff changeset
    10
 hereby transferred.
a27a279701f8 Initial revision
claus
parents:
diff changeset
    11
"
a27a279701f8 Initial revision
claus
parents:
diff changeset
    12
a27a279701f8 Initial revision
claus
parents:
diff changeset
    13
SequenceableCollection subclass:#OrderedCollection
a27a279701f8 Initial revision
claus
parents:
diff changeset
    14
         instanceVariableNames:'contentsArray firstIndex lastIndex'
a27a279701f8 Initial revision
claus
parents:
diff changeset
    15
         classVariableNames:''
a27a279701f8 Initial revision
claus
parents:
diff changeset
    16
         poolDictionaries:''
a27a279701f8 Initial revision
claus
parents:
diff changeset
    17
         category:'Collections-Sequenceable'
a27a279701f8 Initial revision
claus
parents:
diff changeset
    18
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
    19
a27a279701f8 Initial revision
claus
parents:
diff changeset
    20
OrderedCollection comment:'
a27a279701f8 Initial revision
claus
parents:
diff changeset
    21
5
67342904af11 *** empty log message ***
claus
parents: 3
diff changeset
    22
COPYRIGHT (c) 1989 by Claus Gittinger
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
    23
              All Rights Reserved
a27a279701f8 Initial revision
claus
parents:
diff changeset
    24
56
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
    25
$Header: /cvs/stx/stx/libbasic/Attic/OrdColl.st,v 1.10 1994-02-25 13:00:53 claus Exp $
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    26
written spring 89 by claus
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    27
'!
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    28
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    29
!OrderedCollection class methodsFor:'documentation'!
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    30
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    31
documentation
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    32
"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
    33
OrderedCollection have ordered elements. Insertion and removal at both ends
a27a279701f8 Initial revision
claus
parents:
diff changeset
    34
is possible - therefore they can be used for queues and stacks.
a27a279701f8 Initial revision
claus
parents:
diff changeset
    35
a27a279701f8 Initial revision
claus
parents:
diff changeset
    36
Instance variables:
a27a279701f8 Initial revision
claus
parents:
diff changeset
    37
a27a279701f8 Initial revision
claus
parents:
diff changeset
    38
contentsArray   <Array>         the actual contents
a27a279701f8 Initial revision
claus
parents:
diff changeset
    39
firstIndex      <SmallInteger>  index of first valid element
a27a279701f8 Initial revision
claus
parents:
diff changeset
    40
lastIndex       <SmallInteger>  index of last valid element
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    41
"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
    42
! !
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
    43
a27a279701f8 Initial revision
claus
parents:
diff changeset
    44
!OrderedCollection class methodsFor:'instance creation'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
    45
a27a279701f8 Initial revision
claus
parents:
diff changeset
    46
new:size
a27a279701f8 Initial revision
claus
parents:
diff changeset
    47
    "create a new OrderedCollection"
a27a279701f8 Initial revision
claus
parents:
diff changeset
    48
a27a279701f8 Initial revision
claus
parents:
diff changeset
    49
    ^ (self basicNew) initContents:size
a27a279701f8 Initial revision
claus
parents:
diff changeset
    50
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
    51
a27a279701f8 Initial revision
claus
parents:
diff changeset
    52
new
a27a279701f8 Initial revision
claus
parents:
diff changeset
    53
    "create a new OrderedCollection"
a27a279701f8 Initial revision
claus
parents:
diff changeset
    54
a27a279701f8 Initial revision
claus
parents:
diff changeset
    55
    ^ (self basicNew) initContents:10
a27a279701f8 Initial revision
claus
parents:
diff changeset
    56
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
    57
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    58
!OrderedCollection methodsFor:'queries'!
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
    59
a27a279701f8 Initial revision
claus
parents:
diff changeset
    60
size
a27a279701f8 Initial revision
claus
parents:
diff changeset
    61
    "return the number of elements in the collection"
a27a279701f8 Initial revision
claus
parents:
diff changeset
    62
a27a279701f8 Initial revision
claus
parents:
diff changeset
    63
    ^ lastIndex - firstIndex + 1
a27a279701f8 Initial revision
claus
parents:
diff changeset
    64
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
    65
a27a279701f8 Initial revision
claus
parents:
diff changeset
    66
isFixedSize
a27a279701f8 Initial revision
claus
parents:
diff changeset
    67
    "return true if the receiver cannot grow - this will vanish once
a27a279701f8 Initial revision
claus
parents:
diff changeset
    68
     Arrays and Strings learn how to grow ..."
a27a279701f8 Initial revision
claus
parents:
diff changeset
    69
a27a279701f8 Initial revision
claus
parents:
diff changeset
    70
    ^ false
a27a279701f8 Initial revision
claus
parents:
diff changeset
    71
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
    72
a27a279701f8 Initial revision
claus
parents:
diff changeset
    73
!OrderedCollection methodsFor:'copying'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
    74
a27a279701f8 Initial revision
claus
parents:
diff changeset
    75
, aCollection
a27a279701f8 Initial revision
claus
parents:
diff changeset
    76
    "return a new collection formed from concatenating the receiver with
a27a279701f8 Initial revision
claus
parents:
diff changeset
    77
     the argument"
a27a279701f8 Initial revision
claus
parents:
diff changeset
    78
a27a279701f8 Initial revision
claus
parents:
diff changeset
    79
    |newCollection|
a27a279701f8 Initial revision
claus
parents:
diff changeset
    80
a27a279701f8 Initial revision
claus
parents:
diff changeset
    81
    newCollection := self species new:(self size + aCollection size).
a27a279701f8 Initial revision
claus
parents:
diff changeset
    82
    self do:[:element |
a27a279701f8 Initial revision
claus
parents:
diff changeset
    83
        newCollection add:element
a27a279701f8 Initial revision
claus
parents:
diff changeset
    84
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
    85
    aCollection do:[:element |
a27a279701f8 Initial revision
claus
parents:
diff changeset
    86
        newCollection add:element
a27a279701f8 Initial revision
claus
parents:
diff changeset
    87
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
    88
    ^ newCollection
2
claus
parents: 1
diff changeset
    89
claus
parents: 1
diff changeset
    90
    "#(1 2 3) asOrderedCollection , #(4 5 6) asOrderedCollection"
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    91
!
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    92
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    93
copy
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    94
    "return a new OrderedCollection containing the elements of the receiver."
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    95
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    96
    "redefinition is a consequence of the implementation with a
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    97
     separate array - otherwise we get a shallow copy of the
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    98
     contents array, which is not what we want here"
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
    99
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   100
    ^ self copyFrom:1 to:self size
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   101
!
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   102
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   103
copyFrom:start to:stop
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   104
    "return a new OrderedCollection containing the elements
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   105
     from start to stop."
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   106
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   107
    |newCollection sz|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   108
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   109
    sz := stop - start + 1.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   110
    newCollection := self species new:sz.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   111
    newCollection grow:sz.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   112
    newCollection replaceFrom:1 to:sz with:self startingAt:start.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   113
    ^ newCollection
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   114
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
   115
a27a279701f8 Initial revision
claus
parents:
diff changeset
   116
!OrderedCollection methodsFor:'adding & removing'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   117
a27a279701f8 Initial revision
claus
parents:
diff changeset
   118
removeFirst
a27a279701f8 Initial revision
claus
parents:
diff changeset
   119
    "remove the first element from the collection; return the element"
a27a279701f8 Initial revision
claus
parents:
diff changeset
   120
a27a279701f8 Initial revision
claus
parents:
diff changeset
   121
    |anObject |
a27a279701f8 Initial revision
claus
parents:
diff changeset
   122
42
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   123
    firstIndex > lastIndex ifTrue:[
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   124
        "error if collection is empty"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   125
        self subscriptBoundsError.
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   126
        ^ nil
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   127
    ].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   128
    anObject := contentsArray at:firstIndex.
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   129
    contentsArray at:firstIndex put:nil.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   130
    firstIndex := firstIndex + 1.
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   131
    firstIndex > lastIndex ifTrue:[
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   132
        "reset to avoid ever growing"
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   133
        firstIndex := 1.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   134
        lastIndex := 0 
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   135
    ].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   136
    ^ anObject
42
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   137
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   138
    "(OrderedCollection withAll:#(1 2 3 4 5)) removeFirst; yourself"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   139
    "(SortedCollection withAll:#(5 4 3 2 1)) removeFirst; yourself"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   140
    "(SortedCollection new) removeFirst"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   141
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   142
a27a279701f8 Initial revision
claus
parents:
diff changeset
   143
removeLast
a27a279701f8 Initial revision
claus
parents:
diff changeset
   144
    "remove the last element from the collection; return the element"
a27a279701f8 Initial revision
claus
parents:
diff changeset
   145
a27a279701f8 Initial revision
claus
parents:
diff changeset
   146
    |anObject |
a27a279701f8 Initial revision
claus
parents:
diff changeset
   147
42
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   148
    firstIndex > lastIndex ifTrue:[
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   149
        "error if collection is empty"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   150
        self subscriptBoundsError.
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   151
        ^ nil
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   152
    ].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   153
    anObject := contentsArray at:lastIndex.
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   154
    contentsArray at:lastIndex put:nil.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   155
    lastIndex := lastIndex - 1.
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   156
    firstIndex > lastIndex ifTrue:[
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   157
        "reset to avoid ever growing"
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   158
        firstIndex := 1.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   159
        lastIndex := 0 
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   160
    ].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   161
    ^ anObject
42
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   162
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   163
    "(OrderedCollection withAll:#(1 2 3 4 5)) removeLast; yourself"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   164
    "(SortedCollection withAll:#(5 4 3 2 1)) removeLast; yourself"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   165
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   166
56
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   167
removeFromIndex:startIndex to:stopIndex
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   168
    "remove the elements stored under startIndex up to and including
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   169
     the elements under stopIndex.
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   170
     return the receiver."
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   171
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   172
    |nDeleted|
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   173
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   174
    nDeleted := stopIndex - startIndex + 1.
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   175
    contentsArray replaceFrom:(firstIndex + startIndex)
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   176
                           to:(lastIndex - nDeleted)
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   177
                         with:contentsArray 
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   178
                   startingAt:(firstIndex + stopIndex + 1).
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   179
    contentsArray from:(lastIndex - nDeleted + 1)
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   180
                    to:lastIndex
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   181
                   put:nil.
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   182
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   183
    lastIndex := lastIndex - nDeleted.
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   184
    firstIndex > lastIndex ifTrue:[
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   185
        "reset to avoid ever growing"
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   186
        firstIndex := 1.
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   187
        lastIndex := 0 
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   188
    ]
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   189
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   190
    "
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   191
     #(1 2 3 4 5 6 7 8 9) asOrderedCollection removeFromIndex:3 to:6
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   192
    "
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   193
!
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   194
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   195
remove:anObject ifAbsent:exceptionBlock
a27a279701f8 Initial revision
claus
parents:
diff changeset
   196
    "remove the first occurrence of anObject from the collection;
a27a279701f8 Initial revision
claus
parents:
diff changeset
   197
     return the value of exceptionBlock if anObject is not in
a27a279701f8 Initial revision
claus
parents:
diff changeset
   198
     the collection"
a27a279701f8 Initial revision
claus
parents:
diff changeset
   199
a27a279701f8 Initial revision
claus
parents:
diff changeset
   200
    |index "{ Class:SmallInteger }"|
a27a279701f8 Initial revision
claus
parents:
diff changeset
   201
a27a279701f8 Initial revision
claus
parents:
diff changeset
   202
    index := firstIndex.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   203
    [index <= lastIndex] whileTrue:[
a27a279701f8 Initial revision
claus
parents:
diff changeset
   204
        anObject = (contentsArray at:index) ifTrue:[
a27a279701f8 Initial revision
claus
parents:
diff changeset
   205
            contentsArray replaceFrom:index to:(contentsArray size - 1)
a27a279701f8 Initial revision
claus
parents:
diff changeset
   206
                            with:contentsArray startingAt:(index + 1).
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   207
            contentsArray at:lastIndex put:nil.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   208
            lastIndex := lastIndex - 1.
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   209
            firstIndex > lastIndex ifTrue:[
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   210
                "reset to avoid ever growing"
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   211
                firstIndex := 1.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   212
                lastIndex := 0 
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   213
            ].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   214
            ^ anObject
a27a279701f8 Initial revision
claus
parents:
diff changeset
   215
        ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
   216
        index := index + 1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   217
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
   218
    ^ exceptionBlock value
a27a279701f8 Initial revision
claus
parents:
diff changeset
   219
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   220
a27a279701f8 Initial revision
claus
parents:
diff changeset
   221
add:anObject
a27a279701f8 Initial revision
claus
parents:
diff changeset
   222
    "add the argument, anObject to the end of the collection
a27a279701f8 Initial revision
claus
parents:
diff changeset
   223
     Return the argument, anObject."
a27a279701f8 Initial revision
claus
parents:
diff changeset
   224
a27a279701f8 Initial revision
claus
parents:
diff changeset
   225
    (lastIndex == contentsArray size) ifTrue:[
a27a279701f8 Initial revision
claus
parents:
diff changeset
   226
        self makeRoomAtLast
a27a279701f8 Initial revision
claus
parents:
diff changeset
   227
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
   228
    lastIndex := lastIndex + 1.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   229
    contentsArray at:lastIndex put:anObject.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   230
    ^ anObject
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   231
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   232
    "
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   233
     |c|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   234
     c := #(4 3 2 1) asOrderedCollection.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   235
     c add:'here'
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   236
    "
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   237
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   238
a27a279701f8 Initial revision
claus
parents:
diff changeset
   239
addFirst:anObject
a27a279701f8 Initial revision
claus
parents:
diff changeset
   240
    "add the argument, anObject to the beginning of the collection.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   241
     Return the argument, anObject."
a27a279701f8 Initial revision
claus
parents:
diff changeset
   242
a27a279701f8 Initial revision
claus
parents:
diff changeset
   243
    (firstIndex == 1) ifTrue:[
a27a279701f8 Initial revision
claus
parents:
diff changeset
   244
        self makeRoomAtFront
a27a279701f8 Initial revision
claus
parents:
diff changeset
   245
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
   246
    firstIndex := firstIndex - 1.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   247
    contentsArray at:firstIndex put:anObject.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   248
    ^ anObject
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   249
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   250
    "
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   251
     |c|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   252
     c := #(4 3 2 1) asOrderedCollection.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   253
     c addFirst:'here'
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   254
    "
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   255
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   256
a27a279701f8 Initial revision
claus
parents:
diff changeset
   257
add:anObject beforeIndex:index
a27a279701f8 Initial revision
claus
parents:
diff changeset
   258
    "insert the argument, anObject to become located at index.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   259
     Return the argument, anObject."
a27a279701f8 Initial revision
claus
parents:
diff changeset
   260
a27a279701f8 Initial revision
claus
parents:
diff changeset
   261
    self makeRoomAtIndex:(index - firstIndex + 1).
a27a279701f8 Initial revision
claus
parents:
diff changeset
   262
    contentsArray at:(index - firstIndex + 1) put:anObject.
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   263
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   264
    "
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   265
     |c|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   266
     c := #(4 3 2 1) asOrderedCollection.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   267
     c add:'here' beforeIndex:3
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   268
    "
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   269
!
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   270
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   271
add:newObject after:oldObject
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   272
    "insert the argument, newObject after oldObject.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   273
     If oldObject is not in the receiver, report an error,
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   274
     otherwise return the argument, anObject."
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   275
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   276
    |idx|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   277
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   278
    idx := self indexOf:oldObject.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   279
    idx ~~ 0 ifTrue:[
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   280
        ^ self add:newObject beforeIndex:(idx + 1).
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   281
    ].
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   282
    self errorNotFound
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   283
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   284
    "
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   285
     |c|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   286
     c := #(4 3 2 1) asOrderedCollection.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   287
     c add:'here' after:3.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   288
     c add:'here' after:5 
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   289
    "
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   290
! 
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   291
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   292
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   293
add:newObject before:oldObject
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   294
    "insert the argument, newObject before oldObject.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   295
     If oldObject is not in the receiver, report an error,
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   296
     otherwise return the argument, anObject."
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   297
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   298
    |idx|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   299
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   300
    idx := self indexOf:oldObject.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   301
    idx ~~ 0 ifTrue:[
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   302
        ^ self add:newObject beforeIndex:idx.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   303
    ].
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   304
    self errorNotFound
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   305
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   306
    "
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   307
     |c|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   308
     c := #(4 3 2 1) asOrderedCollection.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   309
     c add:'here' before:3.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   310
     c add:'here' before:5 
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   311
    "
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   312
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
   313
a27a279701f8 Initial revision
claus
parents:
diff changeset
   314
!OrderedCollection methodsFor:'grow & shrink'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   315
a27a279701f8 Initial revision
claus
parents:
diff changeset
   316
grow:newSize
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   317
    "grow the receiver to newSize"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   318
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   319
    |newContents oldLast|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   320
a27a279701f8 Initial revision
claus
parents:
diff changeset
   321
    newSize <= (lastIndex - firstIndex + 1) ifTrue:[
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   322
        oldLast := lastIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   323
        lastIndex := firstIndex + newSize - 1.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   324
        contentsArray from:lastIndex + 1 to:oldLast put:nil. 
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   325
    ] ifFalse:[
a27a279701f8 Initial revision
claus
parents:
diff changeset
   326
        newContents := Array new:newSize.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   327
        newContents replaceFrom:1 to:(lastIndex - firstIndex + 1) with:contentsArray.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   328
        contentsArray := newContents.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   329
        firstIndex := 1.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   330
        lastIndex := newSize
a27a279701f8 Initial revision
claus
parents:
diff changeset
   331
    ]
a27a279701f8 Initial revision
claus
parents:
diff changeset
   332
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
   333
a27a279701f8 Initial revision
claus
parents:
diff changeset
   334
!OrderedCollection methodsFor:'accessing'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   335
a27a279701f8 Initial revision
claus
parents:
diff changeset
   336
at:anInteger
a27a279701f8 Initial revision
claus
parents:
diff changeset
   337
    "return the element at index, anInteger"
a27a279701f8 Initial revision
claus
parents:
diff changeset
   338
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   339
    |idx|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   340
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   341
    idx := anInteger + firstIndex - 1.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   342
    ((anInteger < 1) or:[idx > lastIndex]) ifTrue:[
2
claus
parents: 1
diff changeset
   343
        self subscriptBoundsError
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   344
    ] ifFalse:[
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   345
        ^ contentsArray at:idx
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   346
    ]
a27a279701f8 Initial revision
claus
parents:
diff changeset
   347
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   348
a27a279701f8 Initial revision
claus
parents:
diff changeset
   349
at:anInteger put:anObject
a27a279701f8 Initial revision
claus
parents:
diff changeset
   350
    "set the element at index, to be anInteger"
a27a279701f8 Initial revision
claus
parents:
diff changeset
   351
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   352
    |idx|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   353
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   354
    idx := anInteger + firstIndex - 1.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   355
    ((anInteger < 1) or:[idx > lastIndex]) ifTrue:[
2
claus
parents: 1
diff changeset
   356
        self subscriptBoundsError
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   357
    ] ifFalse:[
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   358
        ^ contentsArray at:idx put:anObject
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   359
    ]
42
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   360
!
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   361
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   362
first
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   363
    "return the first element"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   364
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   365
    firstIndex <= lastIndex ifTrue:[
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   366
        ^ contentsArray at:firstIndex
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   367
    ].
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   368
    "error if collection is empty"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   369
    self subscriptBoundsError
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   370
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   371
    "(OrderedCollection withAll:#(1 2 3 4 5)) first"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   372
    "(SortedCollection withAll:#(5 4 3 2 1)) first"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   373
!
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   374
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   375
last
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   376
    "return the last element"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   377
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   378
    firstIndex <= lastIndex ifTrue:[
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   379
        ^ contentsArray at:lastIndex
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   380
    ].
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   381
    "error if collection is empty"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   382
    self subscriptBoundsError
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   383
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   384
    "(OrderedCollection withAll:#(1 2 3 4 5)) last"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   385
    "(SortedCollection withAll:#(5 4 3 2 1)) last"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   386
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
   387
56
be0ed17e6f85 *** empty log message ***
claus
parents: 42
diff changeset
   388
!OrderedCollection methodsFor:'filling & replacing'!
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   389
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   390
replaceFrom:start to:stop with:aCollection startingAt:repStart
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   391
    "redefined - can be done faster"
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   392
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   393
    |end|
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   394
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   395
    end := stop + firstIndex - 1.
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   396
    ((start >= 1) and:[end <= lastIndex]) ifTrue:[
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   397
        ^ contentsArray replaceFrom:(start + firstIndex - 1)
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   398
                                 to:end
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   399
                               with:aCollection
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   400
                         startingAt:repStart
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   401
    ].
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   402
    ^ super replaceFrom:start to:stop with:aCollection startingAt:repStart
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   403
! !
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   404
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   405
!OrderedCollection methodsFor:'private'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   406
a27a279701f8 Initial revision
claus
parents:
diff changeset
   407
setFirstIndex:newFirstIndex lastIndex:newLastIndex
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   408
    "set first and last index"
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   409
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   410
    firstIndex := newFirstIndex.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   411
    lastIndex := newLastIndex.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   412
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   413
a27a279701f8 Initial revision
claus
parents:
diff changeset
   414
makeRoomAtLast
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   415
    "grow/shift the contents for more room at the end"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   416
a27a279701f8 Initial revision
claus
parents:
diff changeset
   417
    |newContents 
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   418
     oldSize    "{ Class:SmallInteger }"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   419
     newSize    "{ Class:SmallInteger }" 
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   420
     startIndex "{ Class:SmallInteger }"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   421
     sz         "{ Class:SmallInteger }"|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   422
a27a279701f8 Initial revision
claus
parents:
diff changeset
   423
    oldSize := contentsArray size.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   424
    sz := self size.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   425
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   426
    "if there is lots of room at the beginning (> 50%), shift instead of growing"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   427
    oldSize > (sz * 2) ifTrue:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   428
        startIndex := firstIndex // 4.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   429
        contentsArray replaceFrom:startIndex to:startIndex + sz - 1 with:contentsArray startingAt:firstIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   430
        contentsArray from:startIndex + sz to:lastIndex put:nil.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   431
        firstIndex := startIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   432
        lastIndex := startIndex + sz - 1.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   433
        ^ self
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   434
    ].
10
claus
parents: 5
diff changeset
   435
    newSize := oldSize * 2.
claus
parents: 5
diff changeset
   436
    newSize == 0 ifTrue:[ newSize := 1].
claus
parents: 5
diff changeset
   437
    newContents := Array new:newSize.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   438
    newContents replaceFrom:1 to:oldSize with:contentsArray.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   439
    contentsArray := newContents
a27a279701f8 Initial revision
claus
parents:
diff changeset
   440
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   441
a27a279701f8 Initial revision
claus
parents:
diff changeset
   442
makeRoomAtFront
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   443
    "grow/shift the contents for more room at the beginning"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   444
a27a279701f8 Initial revision
claus
parents:
diff changeset
   445
    |newContents
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   446
     oldSize    "{ Class:SmallInteger }"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   447
     newSize    "{ Class:SmallInteger }" 
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   448
     startIndex "{ Class:SmallInteger }"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   449
     sz         "{ Class:SmallInteger }"|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   450
a27a279701f8 Initial revision
claus
parents:
diff changeset
   451
    oldSize := contentsArray size.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   452
    sz := self size.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   453
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   454
    "if there is lots of room at the end (> 50%), shift instead of growing"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   455
    oldSize > (sz * 2) ifTrue:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   456
        startIndex := oldSize // 4.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   457
        contentsArray replaceFrom:startIndex to:startIndex + sz - 1 with:contentsArray startingAt:1.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   458
        contentsArray from:1 to:(startIndex - 1) put:nil.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   459
        firstIndex := startIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   460
        lastIndex := startIndex + sz - 1.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   461
        ^ self
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   462
    ].
2
claus
parents: 1
diff changeset
   463
    newSize := oldSize * 2.
10
claus
parents: 5
diff changeset
   464
    newSize == 0 ifTrue:[ newSize := 1].
2
claus
parents: 1
diff changeset
   465
    newContents := Array new:newSize.
claus
parents: 1
diff changeset
   466
    newContents replaceFrom:(oldSize + 1) to:newSize with:contentsArray startingAt:1.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   467
    contentsArray := newContents.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   468
    firstIndex := firstIndex + oldSize.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   469
    lastIndex := lastIndex + oldSize
a27a279701f8 Initial revision
claus
parents:
diff changeset
   470
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   471
a27a279701f8 Initial revision
claus
parents:
diff changeset
   472
makeRoomAtIndex:index
a27a279701f8 Initial revision
claus
parents:
diff changeset
   473
    "grow the contents for inserting at index
a27a279701f8 Initial revision
claus
parents:
diff changeset
   474
     i.e.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   475
     #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:3 -> #(1 2 nil 3 4 5 6)
a27a279701f8 Initial revision
claus
parents:
diff changeset
   476
     #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:1 -> #(nil 1 2 3 4 5 6)
a27a279701f8 Initial revision
claus
parents:
diff changeset
   477
     #(1 2 3 4 5 6) asOrderedCollection makeRoomAtIndex:7 -> #(1 2 3 4 5 6 nil)"
a27a279701f8 Initial revision
claus
parents:
diff changeset
   478
a27a279701f8 Initial revision
claus
parents:
diff changeset
   479
    |newContents
a27a279701f8 Initial revision
claus
parents:
diff changeset
   480
     newSize "{ Class:SmallInteger }" 
a27a279701f8 Initial revision
claus
parents:
diff changeset
   481
     oldSize "{ Class:SmallInteger }" |
a27a279701f8 Initial revision
claus
parents:
diff changeset
   482
a27a279701f8 Initial revision
claus
parents:
diff changeset
   483
    oldSize := contentsArray size.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   484
    firstIndex > (oldSize // 4) ifTrue:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   485
        "there is room at the beginning"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   486
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   487
        index == 1 ifFalse:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   488
            contentsArray replaceFrom:(firstIndex - 1) to:(index - 1)
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   489
                                 with:contentsArray startingAt:firstIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   490
            contentsArray at:index put:nil.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   491
        ].
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   492
        firstIndex := firstIndex - 1.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   493
        ^ self
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   494
    ].
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   495
    lastIndex < (oldSize * 3 // 4) ifTrue:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   496
        "there is room at the end"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   497
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   498
        index == (lastIndex + 1) ifFalse:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   499
            contentsArray replaceFrom:(index + 1) to:(lastIndex + 1) 
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   500
                                 with:contentsArray startingAt:index.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   501
            contentsArray at:index put:nil
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   502
        ].
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   503
        lastIndex := lastIndex + 1.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   504
        ^ self
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   505
    ].
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   506
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   507
    newSize := oldSize * 2.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   508
    newContents := Array new:newSize.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   509
    index == 1 ifFalse:[
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   510
        newContents replaceFrom:1 to:index-1 
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   511
                           with:contentsArray startingAt:1.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   512
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
   513
    index == newSize ifFalse:[
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   514
        newContents replaceFrom:index + 1 to:oldSize + 1 
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   515
                           with:contentsArray startingAt:index.
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   516
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
   517
    contentsArray := newContents.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   518
    lastIndex := lastIndex + 1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   519
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   520
a27a279701f8 Initial revision
claus
parents:
diff changeset
   521
initContents:size
40
a1defe2846d6 *** empty log message ***
claus
parents: 33
diff changeset
   522
    "setup the receiver-collection to hold size entries"
a1defe2846d6 *** empty log message ***
claus
parents: 33
diff changeset
   523
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   524
    contentsArray := Array new:size.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   525
    firstIndex := 1.
a27a279701f8 Initial revision
claus
parents:
diff changeset
   526
    lastIndex := 0 
a27a279701f8 Initial revision
claus
parents:
diff changeset
   527
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
   528
a27a279701f8 Initial revision
claus
parents:
diff changeset
   529
!OrderedCollection methodsFor:'testing'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   530
a27a279701f8 Initial revision
claus
parents:
diff changeset
   531
includes:anObject
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   532
    "return true if anObject is in the collection. Compare using ="
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   533
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   534
    |index "{ Class:SmallInteger }"|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   535
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   536
    index := contentsArray indexOf:anObject startingAt:firstIndex.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   537
    ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ false].
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   538
    ^ true
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   539
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   540
a27a279701f8 Initial revision
claus
parents:
diff changeset
   541
identityIndexOf:anObject
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   542
    "return the index of anObject or 0 if not found. Compare using =="
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   543
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   544
    |index "{ Class:SmallInteger }"|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   545
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   546
    index := contentsArray identityIndexOf:anObject startingAt:firstIndex.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   547
    ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   548
    ^ index - firstIndex + 1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   549
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   550
a27a279701f8 Initial revision
claus
parents:
diff changeset
   551
identityIndexOf:anObject startingAt:startIndex
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   552
    "return the index of anObject, starting search at startIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   553
     Compare using ==; return 0 if not found in the collection"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   554
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   555
    |index "{ Class:SmallInteger }"|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   556
a27a279701f8 Initial revision
claus
parents:
diff changeset
   557
    index := contentsArray identityIndexOf:anObject startingAt:(startIndex + firstIndex - 1).
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   558
    ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   559
    ^ index - firstIndex + 1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   560
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   561
a27a279701f8 Initial revision
claus
parents:
diff changeset
   562
indexOf:anObject
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   563
    "return the index of anObject or 0 if not found in the collection.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   564
     Compare using ="
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   565
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   566
    |index "{ Class:SmallInteger }"|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   567
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   568
    index := contentsArray indexOf:anObject startingAt:firstIndex.
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   569
    ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   570
    ^ index - firstIndex + 1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   571
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   572
a27a279701f8 Initial revision
claus
parents:
diff changeset
   573
indexOf:anObject startingAt:startIndex
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   574
    "return the index of anObject, starting search at startIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   575
     Compare using =; return 0 if not found in the collection"
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   576
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   577
    |index "{ Class:SmallInteger }"|
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   578
a27a279701f8 Initial revision
claus
parents:
diff changeset
   579
    index := contentsArray indexOf:anObject startingAt:(startIndex + firstIndex - 1).
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   580
    ((index < firstIndex) or:[index > lastIndex]) ifTrue:[^ 0].
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   581
    ^ index - firstIndex + 1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   582
! !
a27a279701f8 Initial revision
claus
parents:
diff changeset
   583
13
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   584
!OrderedCollection methodsFor:'converting'!
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   585
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   586
asOrderedCollection 
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   587
    "return the receiver as an ordered collection"
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   588
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   589
    "could be an instance of a subclass..."
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   590
    self class == OrderedCollection ifTrue:[
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   591
        ^ self
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   592
    ].
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   593
    ^ super asOrderedCollection
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   594
! !
62303f84ff5f *** empty log message ***
claus
parents: 10
diff changeset
   595
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   596
!OrderedCollection methodsFor:'enumeration'!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   597
a27a279701f8 Initial revision
claus
parents:
diff changeset
   598
do:aBlock
a27a279701f8 Initial revision
claus
parents:
diff changeset
   599
    "evaluate the argument, aBlock for every element in the collection."
a27a279701f8 Initial revision
claus
parents:
diff changeset
   600
a27a279701f8 Initial revision
claus
parents:
diff changeset
   601
    contentsArray from:firstIndex to:lastIndex do:aBlock
a27a279701f8 Initial revision
claus
parents:
diff changeset
   602
!
a27a279701f8 Initial revision
claus
parents:
diff changeset
   603
42
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   604
reverseDo:aBlock
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   605
    "evaluate the argument, aBlock for every element in the collection
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   606
     procesing elements in reverse direction (i.e. starting with the last)"
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   607
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   608
    contentsArray from:firstIndex to:lastIndex reverseDo:aBlock
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   609
!
e33491f6f260 *** empty log message ***
claus
parents: 40
diff changeset
   610
3
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   611
keysAndValuesDo:aTwoArgBlock
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   612
    "evaluate the argument, aBlock for every element in the collection,
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   613
     passing both index and element as arguments."
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   614
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   615
    |start  "{ Class:SmallInteger }"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   616
     stop   "{ Class:SmallInteger }" |
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   617
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   618
    stop := lastIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   619
    start := firstIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   620
    start to:stop do:[:index |
3
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   621
        aTwoArgBlock value:index value:(contentsArray at:index)
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   622
    ]
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   623
!
24d81bf47225 *** empty log message ***
claus
parents: 2
diff changeset
   624
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   625
collect:aBlock
a27a279701f8 Initial revision
claus
parents:
diff changeset
   626
    "evaluate the argument, aBlock for every element in the collection
a27a279701f8 Initial revision
claus
parents:
diff changeset
   627
     and return a collection of the results"
a27a279701f8 Initial revision
claus
parents:
diff changeset
   628
a27a279701f8 Initial revision
claus
parents:
diff changeset
   629
    |newCollection
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   630
     start  "{ Class:SmallInteger }"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   631
     stop   "{ Class:SmallInteger }" |
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   632
a27a279701f8 Initial revision
claus
parents:
diff changeset
   633
    newCollection := (self species new).
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   634
    stop := lastIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   635
    start := firstIndex.
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   636
    start to:stop do:[:index |
1
a27a279701f8 Initial revision
claus
parents:
diff changeset
   637
        newCollection add:(aBlock value:(contentsArray at:index)).
a27a279701f8 Initial revision
claus
parents:
diff changeset
   638
    ].
a27a279701f8 Initial revision
claus
parents:
diff changeset
   639
    ^ newCollection
a27a279701f8 Initial revision
claus
parents:
diff changeset
   640
! !
33
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   641
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   642
!OrderedCollection methodsFor:'misc'!
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   643
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   644
inspect
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   645
    "redefined to launch a SequenceableCollectionInspector on the receiver
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   646
     (instead of the default InspectorView)."
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   647
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   648
    OrderedCollectionInspectorView isNil ifTrue:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   649
        super inspect
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   650
    ] ifFalse:[
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   651
        OrderedCollectionInspectorView openOn:self
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   652
    ]
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   653
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   654
    "(OrderedCollection withAll:#(3 2 1)) inspect"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   655
    "(OrderedCollection withAll:#(3 2 1)) removeFirst; yourself; inspect"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   656
    "#(0 8 15 3 99 2) asSortedCollection inspect"
50cf0f6bc0ad *** empty log message ***
claus
parents: 13
diff changeset
   657
! !