"
 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.

 This is a demo example:

 THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTOR ``AS IS'' AND
 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 ARE DISCLAIMED.  IN NO EVENT SHALL THE CONTRIBUTOR BE LIABLE
 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 SUCH DAMAGE.
"

'From Smalltalk/X, Version:2.2.1 on 11-Jul-92 at 12:27:25'!

SequenceableCollection subclass:#NumberSet
	 instanceVariableNames:'intervals'
	 classVariableNames:''
	 poolDictionaries:''
	 category:'Collections-Ordered'
!

!NumberSet class methodsFor:'documentation'!

documentation
"
    NumberSets are Sets holding positive integers.
    This class has been written to represent number-ranges from .newsrc-file.
    Implementation uses an array of intervals or numbers.

    Reading and writing is done in .newsrc-format.

    written spring 92 by claus
"
!

version
"
$Header: /cvs/stx/stx/libbasic2/NumberSet.st,v 1.3 1995-11-11 17:17:19 cg Exp $
"
! !

!NumberSet class methodsFor:'instance creation'!

with:aNumberOrInterval
    ^ self new setFirst:aNumberOrInterval
! !

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

readFrom:aStream
    "read a NumberSet (in .newsrc format) from aStream.
     return empty NumberSet if nothing can be read (or wrong format)"

    ^ self new readFrom:aStream

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

!NumberSet methodsFor:'queries'!

first
    "answer the first i.e. lowest number in the set"

    |element|

    intervals isNil ifTrue:[^ nil].
    element := intervals at:1.
    (element isKindOf:Number) ifTrue:[
	^ element
    ].
    ^ element start
!

last
    "answer the last i.e. highest number in the set"

    |element|

    intervals isNil ifTrue:[^ nil].
    element := intervals at:(intervals size).
    (element isKindOf:Number) ifTrue:[
	^ element
    ].
    ^ element stop
!

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.

    "check middle to limit search"
    middle := (endIndex + index) // 2.
    [(middle > (index + 1)) and:[middle < (endIndex - 1)]] whileTrue:[
	element := intervals at:middle.
	(element isMemberOf:Interval) ifTrue:[
	    (element stop <= aNumber) ifTrue:[
		index := middle
	    ] ifFalse:[
		(element start >= aNumber) ifTrue:[
		    endIndex := middle
		] ifFalse:[
		    (element includes:aNumber) ifTrue:[^ true]
		]
	    ]
	] ifFalse:[
	    (element <= aNumber) ifTrue:[
		(element == aNumber) ifTrue:[^ true].
		index := middle
	    ] ifFalse:[
		endIndex := middle
	    ]
	].
	middle := (endIndex + index) // 2
    ].
    [index <= endIndex] whileTrue:[
	element := intervals at:index.
	(element isMemberOf:Interval) ifTrue:[
	    (element start > aNumber) ifTrue:[ ^ false].
	    (element stop >= aNumber) ifTrue:[ ^ true]
	] ifFalse:[
	    (element > aNumber) ifTrue:[ ^ false].
	    (element = aNumber) ifTrue:[ ^ true]
	].
	index := index + 1
    ]. 

    ^ false
!

size
    "return the number of elements in the Set"

    |tally|

    intervals isNil ifTrue:[^ 0].
    tally := 0.
    intervals do:[:element |
	(element isKindOf:Number) ifTrue:[
	    tally := tally + 1
	] ifFalse:[
	    tally := tally + element size
	] 
    ].
    ^ tally
! !

!NumberSet methodsFor:'looping'!

do:aBlock
    intervals isNil ifTrue:[^ self].
    intervals do:[:element |
	(element isKindOf:Number) ifTrue:[
	    aBlock value:element
	] ifFalse:[
	    element do:aBlock
	] 
    ] 
! !

!NumberSet methodsFor:'printing'!

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

    |first|

    intervals isNil ifTrue:[^ self].

    first := true.
    intervals do:[:element |
	first ifTrue:[
	    first := false
	] ifFalse:[
	    aStream nextPut:$,
	]. 
	(element isKindOf:Number) ifTrue:[
	    aStream nextPutAll:(element printString)
	] ifFalse:[
	    aStream nextPutAll:(element start printString).
	    aStream nextPut:$-.
	    aStream nextPutAll:(element stop printString)
	] 
    ] 
!

displayString
    |first s|

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

    s := 'NumberSet'.
    first := true.
    intervals do:[:element |
	first ifTrue:[
	    first := false
	] ifFalse:[
	    s := s , ','
	]. 
	(element isKindOf:Number) ifTrue:[
	    s := s , (element printString)
	] ifFalse:[
	    s := s , (element start printString).
	    s := s , '-'.
	    s := s , (element stop printString)
	] 
    ].
    s := s , ')'.
    ^ s
!

printString
    |first s|

    intervals isNil ifTrue:[^ 'nil'].

    s := ''.
    first := true.
    intervals do:[:element |
	first ifTrue:[
	    first := false
	] ifFalse:[
	    s := s , ','
	]. 
	(element isKindOf:Number) ifTrue:[
	    s := s , (element printString)
	] ifFalse:[
	    s := s , (element start printString).
	    s := s , '-'.
	    s := s , (element stop printString)
	] 
    ].
    ^ s
! !

!NumberSet methodsFor:'adding & removing'!

   add:aNumber
    "add the argument, aNumber to the NumberSet"

    |index endIndex searching element nextElement newIntervals|

    intervals isNil ifTrue:[
	intervals := VariableArray 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 isKindOf:Number) 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"
    newIntervals := VariableArray new:(endIndex + 1).
    newIntervals replaceFrom:1 to:(index - 1) with:intervals.
    newIntervals at:index put:aNumber.
    newIntervals replaceFrom:(index + 1) to:(endIndex + 1)
			with:intervals startingAt:index.
    intervals := newIntervals
!

remove:aNumber ifAbsent:aBlock
    "remove the argument, aNumber from the NumberSet"

    |index endIndex element newIntervals|

    (intervals isNil or:[intervals size == 0]) ifTrue:[
	^ aBlock value
    ].

    index := 1.
    endIndex := intervals size.
    [true] whileTrue:[
	element := intervals at:index.
	(element isKindOf:Number) 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 := VariableArray 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]
    ]
! !

!NumberSet methodsFor:'private'!

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

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

    |nextChar arr start stop done|

    aStream skipSeparators.
    aStream atEnd ifTrue:[^ nil].

    intervals := VariableArray new.

    done := false.
    [done] whileFalse:[
	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 size == 0) ifTrue:[
	intervals := nil
    ]

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

!NumberSet methodsFor:'private accessing'!

setFirst:aNumberOrInterval 
    intervals := VariableArray with:aNumberOrInterval
! !

!NumberSet methodsFor:'accessing'!

lastOfFirstInterval
    |element|

    intervals isNil ifTrue:[^ nil].
    element := intervals at:1.
    (element isKindOf:Interval) ifTrue:[^ element stop].
    ^ element

! !