- live browsing of Self object memory -

lobby traitssortedSequence

CopyDowns: vector

CreatorPath: traits sortedSequence

Module: sortedSequence

parent* = traits sequence
prototype = ( sortedSequence)

accessing

last = ( unsafeAt: lastKey)
indexForInserting: =
( | high. low |
    "Use indexes of elems to avoid arithmetic in loop"
    low: firstKey + start.
    high: lastKey + start.
    [| mid |
     low > high ifTrue: [^low - start].
     mid: (low + high) >> 1.
     (comparator element: (elems at: mid) Precedes: el)
          ifTrue: [low: mid succ]
           False: [high: mid pred]
    ] loop)
unsafeAt: = ( elems at: start + (k - firstKey))
unsafeAt:Put: =
( 
    elems at: start + (k - firstKey) Put: v.
    self)

adding

add: =
( | index |
    index: indexForInserting: el.
    insert: el At: index)
addAll: =
( | k |
    (els size < 5) || (els size < size half) ifTrue: [
      els do: [ | :el | add: el. ]
    ] False: [
      els do: [ | :el | resend.addLast: el. ].
      sortBy: comparator
    ].
    self)

printing

collectionName = 'sortedSequence'

replacing

replaceNextLargerWith: =
( | index. lastEl |
       isEmpty
    || [lastEl: last.
        comparator element: lastEl Precedes: aValue] ifTrue: [
          addLast: aValue.
          ^lastKey
    ].

    "quick check for common case: if
       (aValue < last) && (at: lastKey pred < aValue)
     replace last with aValue"

       (comparator element: aValue Precedes: lastEl)
    && [   (size = 1)
        || [comparator element: (unsafeAt: lastKey pred) Precedes: aValue]]  ifTrue: [
        unsafeAt: lastKey Put: aValue.
        ^lastKey
    ].

    index: indexForInserting: aValue.

    ((index != firstKey)
     && [comparator element: (unsafeAt: index pred) Equals: aValue])
           ifTrue: [^nil].
    unsafeAt: index Put: aValue.
    ^index)
Find the place at which aValue would normally be inserted into the sequence, and replace that element with aValue, returning the index. If aValue is already in the sequence, do nothing and return nil. Append to the end if necessary. Because this operation preserves the sort order, it can be implemented in an efficient and direct way.