"
 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:[
                first := element.
                last := element
            ].
    
            nextElement := intervals at:(index + 1).
            (nextElement isNumber) ifFalse:[
                first2 := nextElement start.
                last2 := nextElement stop
            ] ifTrue:[
                first2 := nextElement.
                last2 := nextElement
            ].
    
            (last >= (first2 - 1)) ifTrue:[
                intervals at:index put:(first to:last2).
                intervals removeIndex:(index + 1)
            ]
        ]
    ]

    "Modified: 9.5.1996 / 17:29:50 / cg"
! !

!NumberSet methodsFor:'private accessing'!

setFirst:aNumberOrInterval 
    "set the first element"

    intervals := OrderedCollection with:aNumberOrInterval

    "Modified: 9.5.1996 / 17:26:26 / cg"
! !

!NumberSet methodsFor:'queries'!

first
    "answer the first i.e. lowest number in the set.
     If the receiver is empty, return nil."

    |element|

    intervals isNil ifTrue:[^ self emptyCollectionError].

    element := intervals at:1.
    (element isNumber) ifTrue:[
        ^ element
    ].
    ^ element start

    "Modified: / 11-04-2017 / 12:30:41 / cg"
!

includes:aNumber
    "answer true, if aNumber is in the set"

    |endIndex index middle delta element start stop|

    intervals isNil ifTrue:[^ false].

    index := 1.
    endIndex := intervals size.

    "/ use a binary search, to limit search

    middle := (endIndex + index) // 2.
    [(middle > (index + 1)) and:[middle < (endIndex - 1)]] whileTrue:[
        element := intervals at:middle.
        (element isNumber) ifFalse:[
            (element stop <= aNumber) ifTrue:[
                index := middle
            ] ifFalse:[
                (element start >= aNumber) ifTrue:[
                    endIndex := middle
                ] ifFalse:[
                    (element includes:aNumber) ifTrue:[^ true]
                ]
            ]
        ] ifTrue:[
            (element <= aNumber) ifTrue:[
                (element == aNumber) ifTrue:[^ true].
                index := middle
            ] ifFalse:[
                endIndex := middle
            ]
        ].
        middle := (endIndex + index) // 2
    ].

    [index <= endIndex] whileTrue:[
        element := intervals at:index.
        (element isNumber) ifFalse:[
            (element start > aNumber) ifTrue:[ ^ false].
            (element stop >= aNumber) ifTrue:[ ^ true]
        ] ifTrue:[
            (element > aNumber) ifTrue:[ ^ false].
            (element = aNumber) ifTrue:[ ^ true]
        ].
        index := index + 1
    ]. 

    ^ false

    "Modified: 9.5.1996 / 17:29:05 / cg"
!

last
    "answer the last i.e. highest number in the set.
     If the receiver is empty, return nil."

    |element|

    intervals isNil ifTrue:[^ self emptyCollectionError].

    element := intervals last.
    (element isNumber) ifTrue:[
        ^ element
    ].
    ^ element stop

    "Modified: / 11-04-2017 / 12:30:45 / cg"
!

size
    "return the number of elements in the Set"

    |tally|

    tally := 0.
    intervals notNil ifTrue:[
        intervals do:[:element |
            (element isNumber) ifTrue:[
                tally := tally + 1
            ] ifFalse:[
                tally := tally + element size
            ] 
        ].
    ].
    ^ tally

    "Modified: / 11-04-2017 / 12:19:54 / cg"
! !

!NumberSet class methodsFor:'documentation'!

version
    ^ '$Header$'
!

version_CVS
    ^ '$Header$'
! !