prototypes addPrototype: #SortedArray derivedFrom: {ExtensibleArray}. SortedArray addSlot: #sortBlock valued: [| :x :y | x <= y]. c@(Collection traits) sort [| newSC | newSC: (SortedArray newSizeOf: c). newSC addAll: c. newSC ]. c@(Collection traits) sortBy: block [| newSC | newSC: (SortedArray newSizeOf: c). newSC sortBlock: block. newSC addAll: c. newSC ]. sc@(SortedArray traits) newSortedBy: block [| newSC | newSC: sc newEmpty. newSC sortBlock: block. newSC ]. sc@(SortedArray traits) at: index put: obj [ sc shouldNotImplement ]. sc@(SortedArray traits) median [ sc at: sc size + 1 // 2 ]. sc@(SortedArray traits) add: obj [ sc insert: obj before: (sc indexForInserting: obj) ]. sc@(SortedArray traits) addAll: c "If the number of elements to add is great enough, add the elements unsafely, and then sort. Otherwise, add each in turn." [ c size > (sc size // 3) ifTrue: [c do: [| :each | sc addLast: each. sc reSort]] ifFalse: [c do: [| :each | sc add: each]]. c ]. sc@(SortedArray traits) = sc2@(SortedArray traits) [ sc sortBlock = sc2 sortBlock and: [resend]. ]. sc@(SortedArray traits) copy "Make a new SortedArray with the same sortBlock. Since we know the order will not change, use the minimally-checking addLast: method vice addAll:." [| newC | newC: sc newSameSize. newC do: [| :each | newC addLast: each]. newC ]. sc@(SortedArray traits) copyWith: obj "Non-destructively append, but don't use addLast: as ExtensibleArray does." [| newC | (newC: sc copy) add: obj. newC ]. sc@(SortedArray traits) copyFrom: start to: end "Copy the range into a new SortedArray which keeps the same sortBlock." [| newC | end < start ifTrue: [^ sc newEmpty]. newC: (sc newSize: end - start + 1). start to: end do: [| :index | newC addLast: (sc at: index)]. newC ]. sc@(SortedArray traits) reversed [| newC | newC: resend. newC sortBlock: sc sortBlock converse. newC ]. sc@(SortedArray traits) collect: block "Override in order to return an ExtensibleArray instead of a SortedArray." [| newC | newC: (ExtensibleArray newSizeOf: sc). sc do: [| :each | newC addLast: (block applyWith: each)]. newC ]. sc@(SortedArray traits) indexOf: obj ifAbsent: block "Subdivides the SortedArray into segments by comparing mid-elements with the object, narrowing until the object is found, or running the block if it isn't." [| index low high | low: sc firstIndex. high: sc lastIndex. [index: high + low // 2. low > high] whileFalse: [(sc contents at: index) = object ifTrue: [^ index]. (sc sortBlock applyWith: (sc contents at: index) with: obj) ifTrue: [low: index + 1] ifFalse: [high: index - 1]]. block do ]. sc@(SortedArray traits) includes: obj "Overridden because the sort order makes a faster implementation possible." [ (sc indexOf: obj ifAbsent: [^ False]) isPositive ]. sc@(SortedArray traits) indexForInserting: obj "This returns the internal array index where the object should be inserted to preserve sort order." [| index low high | low: sc firstIndex. high: sc lastIndex. [index: high + low // 2. low > high] whileFalse: [(sc sortBlock applyWith: (sc contents at: index) with: obj) ifTrue: [low: index + 1] ifFalse: [high: index - 1]]. low ]. sc@(SortedArray traits) replaceNextLargerWith: obj "Find the place at which obj would normally be inserted into the Sequence. If that place is already occupied by obj, just return Nil. If the place does not exist (i.e., it is off the end of the collection), add it to the end, otherwise replace the element at that point with obj. This returns the destination index in any normal case. This operation does preserve the sort order." [| index | index: (sc indexForInserting: obj). index > lastIndex ifTrue: [sc addLast: obj. ^ sc size - 1]. (sc contents at: index) = obj ifTrue: [^ Nil]. sc contents at: index put: obj. index - firstIndex + 1 ]. sc@(SortedArray traits) reSort [ sc contents sortFrom: sc firstIndex to: sc lastIndex by: sc sortBlock. sc ].