- live browsing of Self object memory -

lobby traitssequence

CopyDowns: vector

CreatorPath: traits sequence

Module: sequence

parent* = traits mutableIndexable
defaultSlop = 4

accessing

at:IfAbsent: =
( 
    (firstKey <= k) && [k <= lastKey] ifFalse: [ ^b value: k ].
    elems at: start + (k - firstKey))
at:Put:IfAbsent: =
( 
    (firstKey <= k) && [k <= lastKey] ifFalse: [ ^b value: k ].
    elems at: start + (k - firstKey) Put: v.
    self)

adding

add: = ( addLast: el)
add:WithKey: = ( addLast: el)
addAll: = ( addAllLast: els)
addAllFirst: =
( | i <- 0. s <- 0 |
    s: els size.
    makeSpaceAtStart: s.
    start: start - s.
    i: start.
    els do: [| :el |
        elems at: i Put: el.
        i: 1 + i.
    ].
    size: size + s.
    self)
addAllLast: =
( | i <- 0. s <- 0 |
    s: els size.
    makeSpaceAtEnd: s.
    i: start + size.
    els do: [| :el |
        elems at: i Put: el.
        i: 1 + i.
    ].
    size: s + size.
    self)
addFirst: =
( 
    makeSpaceAtStart: 1.
    start: start - 1.
    elems at: start Put: el.
    size: 1 + size.
    self)
addLast: =
( | s <- 0 |
    s: size.
    elems at: s + start Put: el IfAbsent: [
        makeSpaceAtEnd: 1.
        elems at: s + start Put: el.
    ].
    size: 1 + s.
    self)
insert:At: =
( 
    insert: el At: k IfAbsent:
        [ error: 'bad key for insertion: ', k printString ])
insert:At:IfAbsent: =
( | i |
    "Insert the given element at the given index. Elements
     at indices index through lastKey are shifted up to make
     room. If index >= size, then the element is appended."

    (firstKey <= k) && [k <= lastKey succ] ifFalse: [ ^b value ].
    makeSpaceAtEnd: 1.
    i: start + (k - firstKey).
    shiftElemsFrom: i Through: (start + size) - 1 By: 1.
    elems at: i Put: el.
    size: 1 + size.
    self)
insertAll:At: =
( 
    insertAll: els At: k IfAbsent:
        [ error: 'bad key for insertion: ', k printString ])
insertAll:At:IfAbsent: =
( | i. n |
    "Inserts the given elements at the given index. Elements
     at indices index through lastKey are shifted up to make
     room. If index >= size, then the element is appended."

    (firstKey <= k) && [k <= lastKey succ] ifFalse: [ ^b value ].
    n: els size.
    makeSpaceAtEnd: n.
    i: start + (k - firstKey).
    shiftElemsFrom: i Through: (start + size) - 1 By: n.
    els do: [| :el |
        elems at: i Put: el.
        i: 1 + i.
    ].
    size: size + n.
    self)

creating

copy = ( clone elems: elems copy)
copyAddLast: = ( copy addLast: x)
copyRemoveAll = ( ((clone elems: vector copySize: defaultSlop) start: 0) size: 0)
copySize:FillingWith: =
( | newElems |
     n = size ifTrue: [ ^copy ].
     n < size ifTrue: [ "copy is truncated"
         newElems: elems copyFrom: start UpTo: start + n.
    ] False: [          "copy is extended"
         newElems: vector copySize: n FillingWith: f.
         size do: [| :i | newElems at: i Put: (elems at: start + i) ].
     ].
     ((clone elems: newElems) start: 0) size: n)

iterating

do: =
( | i <- 0 |
    "Optimizes away the overhead of checking keys in at:."
    isEmpty ifTrue: [^ self].  "An optim."
    i: start.
    firstKey to: lastKey Do: [|:k|
        block value: (elems at: i) With: k.
        i: 1 + i.
    ].
    self)

printing

collectionName = 'sequence'

private utilities

clearFrom:UpTo: =
( 
    "Set the elements in the given range of of indices
     to nil to allow the objects to be garbage collected."

    from upTo: to Do: [| :i | elems at: i Put: nil ].
    self)
makeSpaceAtEnd: =
( 
    "Make room for the given number of new elements to be
     added to the end of this sequence. Current contents of
     elems are shifted to the beginning if necessary, based
     on the expectation that a typical client will add new
     elements to the same end of the sequence repeately."

    desiredMinCapacity: size + space.
    (elems size - (start + size)) < space ifTrue: [
        "slide elem contents to the beginning to make room"
        size do: [| :i | elems at: i Put: elems at: start + i ].
        clearFrom: (start max: size) UpTo: (start + size).
        start: 0.
    ].
    self)
makeSpaceAtStart: =
( 
    "Make room for the given number of new elements to be
     added to the start of this sequence. Current contents of
     elems are shifted to the end if necessary, based
     on the expectation that a typical client will add new
     elements to the same end of the sequence repeately."

    desiredMinCapacity: size + space.
    space > start ifTrue: [| newStart. j |
        "slide elem contents to the end to make room"
        newStart: elems size - size.
        j: elems size - 1.
        ((start + size) - 1) downTo: start Do: [| :i |
            elems at: j Put: elems at: i.
            j: j - 1.
        ].
        clearFrom: start UpTo: ((start + size) min: newStart).
        start: newStart.
    ].
    self)
shiftElemsFrom:Through:By: =
( 
    "Shift the given subrange of the elems vector by the
     given number of positions. A positive offset shifts
     right; a negative one shifts left."

    0 = offset ifTrue: [ ^self ].
    0 < offset ifTrue: [ "shift right"
        endIndex downTo: startIndex Do: [| :i |
            elems at: (i + offset) Put: (elems at: i).
        ].
    ] False: [ "shift left"
        startIndex to: endIndex Do: [| :i |
            elems at: (i + offset) Put: (elems at: i).
        ].
    ].
    self)

removing

remove: = ( remove: el IfAbsent: [ error: el printString, ' is absent' ])
remove:IfAbsent: =
( 
    do: [| :v. :k | el = v ifTrue: [ removeKey: k. ^self ]].
    b value: el)
removeAll =
( 
    "Details: The start index is set to zero. For clients that
     always add at the end, this is the right thing. For clients
     that always add at the beginning, the first add will fix
     things up."

    clearFrom: start UpTo: start + size.
    start: 0.
    size:  0.
    self)
removeFirst =
( | el |
    0 = size ifTrue: [error: 'removing from an empty sequence'].
    el: (elems at: start).
    elems at: start Put: nil.
    start: start + 1.
    size:  size - 1. 
    el)
removeKey: = ( removeKey: k IfAbsent: [ error: k printString, ' is absent' ])
removeKey:IfAbsent: =
( | last |
    (firstKey <= k) && [k <= lastKey] ifFalse: [ ^b value: k ].
    last: (start + size) - 1.
    shiftElemsFrom: 1 + (start + (k - firstKey)) Through: last By: -1.
    elems at: last Put: nil.
    size: size - 1.
    self)
removeKeysFrom:To: =
( 
    removeKeysFrom: k1 To: k2 IfAbsent:
        [ error: 'bad key range for removeKeys ',
              k1 printString, '...', k2 printString ])
removeKeysFrom:To:IfAbsent: =
( | n. newSize |
    (firstKey <= k1) && [(k1 <= k2) && [k2 <= lastKey]]
        ifFalse: [ ^b value ].
    n: 1 + (k2 - k1).
    newSize: size - n.
    shiftElemsFrom: 1 + (start + (k2 - firstKey))
        Through: (start + size) - 1
        By: n negate.
    clearFrom: start + newSize UpTo: start + size.
    size: newSize.
    self)
removeLast =
( | el. i. s <- 0 |
    s: size.
    0 = s ifTrue: [error: 'removing from an empty sequence'].
    i: (start + s) - 1.
    el: (elems at: i).
    elems at: i Put: nil.
    size: s - 1. 
    el)

resizing

compress =
( 
    size != elems size ifTrue: [
        elems: (elems copyFrom: start UpTo: start + size). 
        start: 0.
    ].
    self)
desiredMinCapacity: =
( 
    "Ensure that the receiver has enough space to store at
     least the given number of elements."
    "Note: this method never shrinks the receiver; see compress."

    n > elems size ifTrue: [
        "Double the current capacity, at least."
        elems: elems copySize: ((2 * elems size) max: n).
    ].
    self)

sorting

mergeSortFirst:Count:By: =
( 
    (firstKey <= k) && [k <= lastKey] ifFalse: [
        error: 'bad start index to mergeSortFirst:Count:By:'.
    ].
    n > (size - (k - firstKey)) ifTrue: [
        error: 'bad count to mergeSortFirst:Count:By:'.
    ].
    elems mergeSortFirst: start + (k - firstKey) Count: n By: cmp.
    self)

transforming

asByteVector =
( | bv |
    bv: byteVector copySize: size.
    do: [|:b. :i| bv at: i Put: b].
    bv)
asVector = ( elems copyFrom: start UpTo: start + size)
filterBy: =
( | i <- 0. k <- 0 |
    "Details: i is the index of the next element to test.
     j is the original key of that element."

    [i < size] whileTrue: [
        (filterBlock value: (at: i) With: k) ifTrue: [i: 1 + i]
                                              False: [removeKey: i].
        k: k + 1.
    ].
    self)
mapBy: =
( | i <- 0 |
    "Optimizes away the overhead of checking keys in at:."

    i: start.
    firstKey to: lastKey Do: [|:k|
        elems at: i Put: (mapBlock value: (elems at: i) With: k).
        i: 1 + i.
    ].
    self)