instanceVariableNames:'intervals'

	classVariableNames:''

	poolDictionaries:''

	category:'Collections-Ordered'

    This class has been written to represent number-ranges 

    from .newsrc-files.

    The implementation uses an array of intervals or numbers.

    [author:]

        Claus Gittinger

    [see also:]

        NewsHandler

    "return a new numberSet containing a single number

     or the numbers from an interval"

    "

     NumberSet with:69

     NumberSet with:(1 to:50)

    "

    "Modified: 9.5.1996 / 17:25:18 / cg"

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

    "

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

    "

!NumberSet methodsFor:'accessing'!

lastOfFirstInterval

    "return the last element of the first interval.

     Return nil if the receiver is empty."

    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 nextElement newIntervals|

    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"

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

                element start:aNumber.

                self tryMerge:(index - 1).

                ^ self

            ]. 

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

                element stop:aNumber.

                self tryMerge:index.

                ^ self

            ].

            "already in set"

            ((element start <= aNumber) and:[

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

            "not in - stop search"

            (element start > 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: 9.5.1996 / 17:31:05 / cg"

remove:aNumber ifAbsent:aBlock

    "remove the argument, aNumber from the NumberSet"

    |index endIndex element newIntervals|

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

        ^ aBlock value

    ].

    [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 ?"

            (element start = aNumber) ifTrue:[ 

                element start:(aNumber + 1).

                (element start = element stop) ifTrue:[

                    intervals at:index put:(element start)

                ].

                ^ self

            ]. 

            (element stop = aNumber) ifTrue:[ 

                element stop:(aNumber - 1).

                (element start = element stop) ifTrue:[

                    intervals at:index put:(element start)

                ].

                ^ self

            ].

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

            ((element start <= aNumber) and:[

             (element stop >= aNumber)]) ifTrue:[

                "must make it two intervals"

                newIntervals := OrderedCollection new:(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: 9.5.1996 / 17:30:52 / cg"

!NumberSet methodsFor:'enumerating'!

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

        (element isNumber) ifTrue:[

            aBlock value:element

        ] ifFalse:[

            element do:aBlock

        ] 

    ]

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

displayString

    "return a nice string"

    |first s|

    intervals size == 0 ifTrue:[^ 'NumberSet()'].

    s := 'NumberSet('.

    first := true.

    intervals do:[:element |

        first ifTrue:[

            first := false

        ] ifFalse:[

            s := s , ','

        ]. 

        (element isNumber) ifTrue:[

            s := s , (element printString)

        ] ifFalse:[

            s := s , (element start printString).

            s := s , '-'.

            s := s , (element stop printString)

        ] 

    ].

    s := s , ')'.

    ^ s

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

!

        first ifTrue:[

            first := false

        ] ifFalse:[

            aStream nextPut:$,

        ]. 

        (element isNumber) ifTrue:[

            aStream nextPutAll:(element printString)

        ] ifFalse:[

            aStream nextPutAll:(element start printString).

            aStream nextPut:$-.

            aStream nextPutAll:(element stop printString)

        ] 

    ]

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

        aStream atEnd ifTrue:[

            done := true

        ] ifFalse:[

            start := Number readFrom:aStream.

            start isNil ifTrue:[

                done := true

            ] ifFalse:[

                aStream skipSeparators.

                aStream atEnd ifTrue:[

                    intervals add:start. 

                    done := true

                ] ifFalse:[

                    nextChar := aStream peek.

                    (nextChar == $-) ifTrue:[

                        aStream next.

                        stop := Number readFrom:aStream.

                        intervals add:(start to:stop)

                    ] ifFalse:[

                        intervals add:start

                    ].

                    aStream skipSeparators.

                    aStream atEnd ifTrue:[

                        done := true

                    ] ifFalse:[

                        nextChar := aStream peek.

                        (nextChar == $,) ifFalse:[

                             done := true

                        ] ifTrue:[

                             aStream next

                        ]

                    ]

                ]

            ]

        ]

        intervals := nil

    "

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

    "

    "Modified: 9.5.1996 / 17:30:02 / 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"

    "set the first element"

    "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 isNumber) ifTrue:[

        ^ element

    ].

    ^ element start

    "Modified: 9.5.1996 / 17:29:14 / 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:[^ nil].

    element := intervals last.

    (element isNumber) ifTrue:[

        ^ element

    ].

    ^ element stop

    "Modified: 9.5.1996 / 17:29:10 / cg"

!

size

    "return the number of elements in the Set"

    |tally|

    intervals isNil ifTrue:[^ 0].

    tally := 0.

    intervals do:[:element |

        (element isNumber) ifTrue:[

            tally := tally + 1

        ] ifFalse:[

            tally := tally + element size