Class: SegmentedOrderedCollection

• Inheritance
• Description
• Class protocol
  • instance creation
• Instance protocol
  • accessing
  • adding & removing
  • enumerating
  • grow & shrink
  • initialization
  • private
  • queries
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--SegmentedOrderedCollection

Package:

stx:libbasic2

Category:

Collections-Sequenceable

Version:

rev: 1.22 date: 2023/11/27 15:34:30

user: cg

file: SegmentedOrderedCollection.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

SegmentedOrderedCollections are intended as a replacement for huge OrderedCollections or Lists.
They keep their elements in chunks (segments), allowing for fast 
adding/removing at either end AND relatively fast add/remove inside the collection.
Compared to regular orderedColletions, there is not much of a difference if
elements are added at either end.
However, when adding/removing inner elements, the performance of SegmentedOrderedCollections
is much better above a certain number of elements (actually quite big).

However, notice again: 
    when only removing at either end only, an OrderedCollection is faster.

The break-even in performance depends on the number of elements and the usage pattern.
Consider it with (say) > 10000 elements and many adds/removes from the inside.

This class was added to support huge selection-in-lists (>100k elements), which are
constantly changing by adding/removing elements at arbitrary positions.

Possibly unfinished (may need optimized search and replace).


[complexity:] (M is the segment size)        
     access by index:                O(logM(n))           depends on segment size M which defaults to 200
     insertion at either end:        O(logM(n)) mostly    logM to find the segment; then append at either end
     removal at either end:          O(logM(n))
     insertion in the middle:        O(logM(n)) + O(M)    logM to find the segment; O(M) to shift in that segment
     removal in the middle:          O(logM(n)) + O(M)    - ditto -
     searching:                      O(n)
     min/max:                        O(n)

copyright
COPYRIGHT (c) 2013 by Claus Gittinger
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

Class protocol:

 new

return an initialized instance

 new: size

return an initialized instance with space for size elements.
However, be aware that the logical size is 0

Instance protocol:

 at: index

return the element at index, anInteger

 at: index put: newElement

set the element at index, to be anInteger.
Return anObject (sigh).

 first

return the first element

 last

return the last element

 add: anObject

add anObject to the end.
Returns the object (sigh)

 add: anObject beforeIndex: index

insert the first argument, anObject into the collection before slot index.
Return the receiver (sigh - ST-80 compatibility).

Notice that this modifies the receiver, NOT a copy.

 addAll: aCollection

add aCollection to the end.

Usage example(s):

|sc| sc := SegmentedOrderedCollection new. sc addAll:(1 to:100). sc addAll:(101 to:200). sc addAll:(201 to:300). sc. sc add:301. sc

 addFirst: anObject

add anObject to the beginning (insert as new first element).

 removeAll

remove all elements from the receiver. Returns the receiver.

 removeFirst

remove the first element from the collection; return the element.
If there is no element in the receiver collection, raise an error.

 removeFirstIfAbsent: exceptionBlock

remove the first element from the collection; return the element.
If there is no element in the receiver collection, return the value from
exceptionBlock.
Destructive: modifies the receiver

 removeFromIndex: startIndex toIndex: endIndex

remove the elements stored under startIndex up to and including
the elements under stopIndex.
Return the receiver.
Returning the receiver here is a historic leftover - it may change.
Please use yourself in a cascade, if you need the receiver's value
when using this method.

 removeLast

remove the last element from the collection; return the element

 do: aBlock

evaluate the argument, aBlock for every element in the collection.

 keysAndValuesDo: aBlock

evaluate the argument, aBlock for every element in the collection,
passing both index and element as arguments.

 grow: newSize

adjust the logical size to newSize

 initialize

Invoked when a new instance is created.

 splitSegmentAt: segmentIndex

 isFixedSize

return true if the receiver cannot grow

 size

return the number of elements in the collection

Examples:

|oc|
oc := OrderedCollection new.
Time millisecondsToRun:[
    1 to:100000 do:[:i |
        oc add:i
    ].
] => 21

|sc|

sc := SegmentedOrderedCollection new.
Time millisecondsToRun:[
    1 to:100000 do:[:i |
        sc add:i
    ].
] => 87

|oc|
oc := OrderedCollection new.
Time millisecondsToRun:[
    oc grow:100000.
    oc at:1 put:1.
    oc at:100000 put:100000.
]   

|sc|

sc := SegmentedOrderedCollection new.
Time millisecondsToRun:[
    sc grow:100000.
    sc at:1 put:1.
    sc at:100000 put:100000.
]  

|oc c|
oc := OrderedCollection new.
c := 1 to:100000.
Time millisecondsToRun:[
    oc addAll:c.
    oc addAll:c.
    oc addAll:c.
]   47 

|sc c|

sc := SegmentedOrderedCollection new.
c := 1 to:100000.
Time millisecondsToRun:[
    sc addAll:c.
    sc addAll:c.
    sc addAll:c.
]