"

 COPYRIGHT (c) 1992 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.

"

"{ Package: 'stx:libbasic2' }"

"{ NameSpace: Smalltalk }"

SequenceableCollection subclass:#NumberSet

	instanceVariableNames:'intervals'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Ordered'

!

!NumberSet class methodsFor:'documentation'!

copyright

"

 COPYRIGHT (c) 1992 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.

"

!

documentation

"

    NumberSets are sets holding positive integers.

    This class has been written especially to represent number-ranges as found in .newsrc-files,

    and it supports reading/writing of that format (for example: '0-62,69,82,84,86,88,91').

    It is space optimized for sparse sets of numbers, containing a mix of single numbers

    and chunks of sequential sub ranges. 

    When adding elements, holes between 2 subranges

    are detected, and merged into single subranges.

    It may need some care to be used in other situations.

    The implementation uses an array of intervals or individual numbers.

    Reading and writing is in .newsrc-format.

    [author:]

        Claus Gittinger (spring '92)

    [timing:]

        Time millisecondsToRun:[

            10000 timesRepeat:[

                (NumberSet with:(0 to:255)) removeAllFoundIn:(10 to:20); yourself.

            ]

        ]

        Time millisecondsToRun:[

            10000 timesRepeat:[

                (Set withAll:(0 to:255)) removeAllFoundIn:(10 to:20); yourself.

            ]

        ] 

    [example:]

        |s|

        s := NumberSet new.

        s add:123.

        s add:255.

        s add:124.

        s add:-5.

        s addAll:(125 to:188).

        s

    [see also:]

        NewsHandler

        Interval Set

"

! !

!NumberSet class methodsFor:'instance creation'!

new:size

    ^ self new

    "Created: / 08-11-2017 / 06:54:03 / cg"

!

with:aNumberOrInterval

    "return a new numberSet containing a single number

     or the numbers from an interval"

    ^ self new setFirst:aNumberOrInterval

    "

     NumberSet with:69

     NumberSet with:(1 to:50)

     NumberSet withAll:(1 to:50)

    "

    "Modified: / 09-05-1996 / 17:25:18 / cg"

    "Modified (comment): / 11-04-2017 / 12:28:39 / cg"

! !

!NumberSet class methodsFor:'input from a stream'!

readFrom:aStringOrStream

    "read a NumberSet (in .newsrc format) from aStream.

     return an empty NumberSet if nothing can be read (or wrong format)"

    ^ self readFrom:aStringOrStream onError:[ ConversionError raise ]

    "

     NumberSet readFrom:('0-62,69,82,84,86,88,91' readStream).

     NumberSet readFrom:('abc' readStream).

    "

    "

     |ns s string|

     ns := NumberSet new.

     ns add:1.

     ns add:2.

     ns add:3.

     ns add:5.

     s := '' writeStream.

     ns printOn:s.

     string := s contents.

     NumberSet readFrom:string.     

    "

    "Modified (comment): / 11-04-2017 / 12:27:45 / cg"

!

readFrom:aStringOrStream onError:exceptionalValue

    "read a NumberSet (in .newsrc format) from aStream.

     return an empty NumberSet if nothing can be read (or wrong format)"

    ^ self new readFrom:aStringOrStream onError:exceptionalValue

    "

     NumberSet readFrom:('0-62,69,82,84,86,88,91' readStream).

    "

    "

     |ns s string|

     ns := NumberSet new.

     ns add:1.

     ns add:2.

     ns add:3.

     ns add:5.

     s := '' writeStream.

     ns printOn:s.

     string := s contents.

     NumberSet readFrom:string.     

    "

    "Created: / 11-04-2017 / 12:22:53 / cg"

! !

!NumberSet methodsFor:'accessing'!

lastOfFirstInterval

    "return the last element of the first interval.

     Return nil if the receiver is empty."

    |element|

    intervals isNil ifTrue:[^ nil].

    element := intervals at:1.

    (element isNumber) ifFalse:[^ element stop].

    ^ element

    "Modified: 9.5.1996 / 17:31:37 / cg"

! !

!NumberSet methodsFor:'adding & removing'!

add:aNumber

    "add the argument, aNumber to the NumberSet"

    |index endIndex searching element intervalStart intervalStop|

    intervals isNil ifTrue:[

        intervals := OrderedCollection with:aNumber.

        ^ self

    ].

    "/ search for an interval to expand (on the fly watch out if already there)

    index := 1.

    endIndex := intervals size.

    searching := true.

    [searching] whileTrue:[

        element := intervals at:index.

        (element isNumber) ifTrue:[

            "make a number to an interval"

            (element = (aNumber - 1)) ifTrue:[ 

                intervals at:index put:(element to:aNumber).

                self tryMerge:index.

                ^ self

            ].

            (element = (aNumber + 1)) ifTrue:[ 

                intervals at:index put:(aNumber to:element).

                self tryMerge:(index - 1).

                ^ self

            ]. 

            "already in set"

            (element = aNumber) ifTrue:[^ self].

            "not in - stop search"

            (element > aNumber) ifTrue:[searching := false]

        ] ifFalse:[

            "expand interval"

            intervalStart := element start. 

            (intervalStart = (aNumber + 1)) ifTrue:[ 

                element start:aNumber.

                self tryMerge:(index - 1).

                ^ self

            ]. 

            intervalStop := element stop. 

            (intervalStop = (aNumber - 1)) ifTrue:[ 

                element stop:aNumber.

                self tryMerge:index.

                ^ self

            ].

            "already in set?"

            (aNumber between:intervalStart and:intervalStop) ifTrue:[^ self].

            "not in - stop search"

            (intervalStart > aNumber) ifTrue:[searching := false]

        ].

        searching ifTrue:[

            index := index + 1.

            (index > endIndex) ifTrue:[searching := false]

        ]

    ].

    "/ append at end

    (index > endIndex) ifTrue:[

        intervals add:aNumber.

        ^ self

    ].

    "/ insert before index

    intervals add:aNumber beforeIndex:index.

    "Modified: / 11-04-2017 / 12:12:56 / cg"

!

remove:aNumber ifAbsent:aBlock

    "remove the argument, aNumber from the NumberSet"

    |index endIndex element newIntervals intervalStart intervalStop|

    (intervals isNil or:[intervals size == 0]) ifTrue:[

        ^ aBlock value

    ].

    index := 1.

    endIndex := intervals size.

    [true] whileTrue:[

        element := intervals at:index.

        (element isNumber) ifTrue:[

            (element = aNumber) ifTrue:[

                (intervals size == 1) ifTrue:[

                    intervals := nil

                ] ifFalse:[

                    intervals removeIndex:index

                ].

                ^ self

            ].

            "not in - stop search"

            (element > aNumber) ifTrue:[^ aBlock value]

        ] ifFalse:[

            "can remove from interval ?"

            intervalStart := element start.

            intervalStop := element stop.

            (intervalStart = aNumber) ifTrue:[ 

                element start:(aNumber + 1).

                (element start = intervalStop) ifTrue:[

                    intervals at:index put:intervalStop

                ].

                ^ self

            ]. 

            (intervalStop = aNumber) ifTrue:[ 

                element stop:(aNumber - 1).

                (intervalStart = element stop) ifTrue:[

                    intervals at:index put:intervalStart

                ].

                ^ self

            ].

            (intervalStart > aNumber) ifTrue:[^ aBlock value].

            (aNumber between:intervalStart and:intervalStop) ifTrue:[

                "split; must make it two intervals"

                newIntervals := OrderedCollection newWithSize:(endIndex + 1).

                newIntervals replaceFrom:1 to:(index - 1) with:intervals.

                newIntervals replaceFrom:(index + 2) to:(endIndex + 1) with:intervals startingAt:(index + 1).

                (element start = (aNumber - 1)) ifTrue:[

                    newIntervals at:index put:element start

                ] ifFalse:[

                    newIntervals at:index put:(element start to:(aNumber - 1))

                ].

                ((aNumber + 1) = element stop) ifTrue:[

                    newIntervals at:(index + 1) put:(aNumber + 1)

                ] ifFalse:[

                    newIntervals at:(index + 1) put:((aNumber + 1) to:element stop)

                ].

                intervals := newIntervals.

                ^ self

            ]

        ].

        index := index + 1.

        (index > endIndex) ifTrue:[^ aBlock value]

    ]

    "Modified: / 11-04-2017 / 12:15:40 / cg"

! !

!NumberSet methodsFor:'enumerating'!

do:aBlock

    "evaluate the argument, aBlock for each element in the numberSet"

    intervals isNil ifTrue:[^ self].

    intervals do:[:element |

        (element isNumber) ifTrue:[

            aBlock value:element

        ] ifFalse:[

            element do:aBlock

        ] 

    ]

    "Modified: 9.5.1996 / 17:30:19 / cg"

! !

!NumberSet methodsFor:'printing'!

displayOn:aStream

    "return a nice string for the inspector"

    aStream nextPutAll:'NumberSet('.

    self printOn:aStream.

    aStream nextPutAll:')'.

    "

     (NumberSet readFrom:'1,2,4-10,15') displayOn:Transcript

     (NumberSet readFrom:'1,2,4-10,15') printOn:Transcript

    "

    "Created: / 11-04-2017 / 12:19:07 / cg"

!

printOn:aStream

    "output the NumberSet (in .newsrc format) on aStream"

    |first|

    intervals isEmptyOrNil ifTrue:[^ self].

    first := true.

    intervals do:[:element |

        first ifTrue:[

            first := false

        ] ifFalse:[

            aStream nextPut:$,

        ]. 

        (element isNumber) ifTrue:[

            element printOn:aStream

        ] ifFalse:[

            element start printOn:aStream.

            aStream nextPut:$-.

            element stop printOn:aStream.

        ] 

    ]

    "Modified: / 11-04-2017 / 12:33:11 / cg"

! !

!NumberSet methodsFor:'private'!

readFrom:aStringOrStream

    "read my value from aStream (in .newsrc format).

     Raise an error if the format is invalid"

    ^ self readFrom:aStringOrStream onError:[ ConversionError raise ]

    "

     NumberSet readFrom:'0-62,69,82,84,86,88,91'

     NumberSet readFrom:'0-62,69,82,84,86,88,91' readStream

     NumberSet new readFrom:('0-62,69,82,84,86,88,91' readStream)

     NumberSet new readFrom:'0-62,69,82,84,86,88,91'

     NumberSet readFromString:'0+62,69,82,84,86,88,91'      -- raises an error

     NumberSet readFrom:'1+62,69,82,84,86,88,91'            -- stops at '+'

    "

    "Modified: / 11-04-2017 / 12:27:13 / cg"

!

readFrom:aStringOrStream onError:exceptionalValue

    "read my value from aStream (in .newsrc format)"

    |s nextChar start stop done|

    s := aStringOrStream readStream.

    s skipSeparators.

    s atEnd ifTrue:[^ exceptionalValue value].

    intervals := OrderedCollection new.

    done := false.

    [done] whileFalse:[

        s atEnd ifTrue:[

            done := true

        ] ifFalse:[

            start := Number readFrom:s onError:[^ exceptionalValue value].

            start isNil ifTrue:[

                done := true

            ] ifFalse:[

                s skipSeparators.

                s atEnd ifTrue:[

                    intervals add:start. 

                    done := true

                ] ifFalse:[

                    nextChar := s peek.

                    (nextChar == $-) ifTrue:[

                        s next.

                        stop := Number readFrom:s onError:[^ exceptionalValue value].

                        intervals add:(start to:stop)

                    ] ifFalse:[

                        intervals add:start

                    ].

                    s skipSeparators.

                    s atEnd ifTrue:[

                        done := true

                    ] ifFalse:[

                        nextChar := s peek.

                        (nextChar == $,) ifFalse:[

                             done := true

                        ] ifTrue:[

                             s next

                        ]

                    ]

                ]

            ]

        ]

    ].

    (intervals size == 0) ifTrue:[

        intervals := nil

    ]

    "

     NumberSet readFrom:'0-62,69,82,84,86,88,91'

     NumberSet readFrom:'0-62,69,82,84,86,88,91' readStream

     NumberSet new readFrom:('0-62,69,82,84,86,88,91' readStream)

     NumberSet new readFrom:'0-62,69,82,84,86,88,91'

    "

    "Created: / 11-04-2017 / 12:23:39 / cg"

!

tryMerge:index

    "try to make element at index and index + 1 be one element"

    |element first last first2 last2 nextElement|

    (index > 0) ifTrue:[

        (index < (intervals size)) ifTrue:[

            element := intervals at:index.

            (element isNumber) ifFalse:[

                first := element start.

                last := element stop

            ] ifTrue:[