ripnews/set/intspan.rb

# $Dwarf: intspan.rb,v 1.20 2005/03/11 12:17:35 ward Exp $
# $Source$

#
# Copyright (c) 2002, 2003 Ward Wouts <ward@wouts.nl>
#
# Permission to use, copy, modify, and distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
#

class Integer
	def even?
		return self%2 == 0
	end

	def odd?
		return self%2 == 1
	end
end

module Set

class IntSpan

Empty_String = ''
Debuglevel = 0

def initialize(setspec=nil)
	print "initialize: Calling copy\n" if Debuglevel > 0
	copy(setspec)
end

def IntSpan.valid(run_list)
	testset = new
	begin
		testset._copy_run_list(run_list)
	rescue SystemExit
		return false
	end
	return true
end

def copy(set_spec)
	print "Copy #{set_spec.class.to_s}\n" if Debuglevel > 0
	case set_spec.class.to_s
		when "NilClass"
			print "copy: Calling _copy_empty\n" if Debuglevel > 0
			_copy_empty
		when "String"
			print "copy: Calling _copy_run_list\n" if Debuglevel > 0
			_copy_run_list(set_spec)
		when "Array"
			print "copy: Calling _copy_array\n" if Debuglevel > 0
			_copy_array(set_spec)
		when "Set::IntSpan"
			print "copy: Calling _copy_set\n" if Debuglevel > 0
			_copy_set(set_spec)
		else
			print "eeps\n"
	end
end

def _copy_empty			# makes @set the empty set
	@set = {}
	set_neg_inf(false)
	set_pos_inf(false)
	@set["edges"] = []
	@set["run"] = []
end

def _copy_array(array)		# copies an array into @set
	_copy_empty
	set_neg_inf(false)
	set_pos_inf(false)

	edges = []
	for element in array.sort
		next if (edges.length > 0) and (edges[-1] == element) # skip duplicates

		if (edges.length > 0) and (edges[-1] == element-1)
			edges[-1] = element
		else
			edges.push(element-1, element)
		end
	end

	@set["edges"] = edges
	@set["run"] = []
end

def _copy_set(src)	# copies one set to another
	_copy_empty
	set_neg_inf(src.neg_inf?)
	set_pos_inf(src.pos_inf?)
	@set["edges"] = src.edges
	@set["run"] = []
end

def _copy_run_list(runlist)
	_copy_empty

	runlist.gsub!(/\s|_/, '')
	return true if runlist == ""

	print "copy run list...\n" if Debuglevel > 0

	first = true
	last = false

	edges = []

	for i in runlist.split(/,/)
		print "#{i}\n" if Debuglevel > 0
		begin
			if i =~ /^(-?\d+)$/x
				edges.push(($1.to_i-1), $1.to_i)
				next
			end

			if i =~ /^ (-?\d+) - (-?\d+) $/x
				if $1.to_i > $2.to_i
					print "match rule 1 #{$1} > #{$2}\n"
					print "Set::IntSpan::_copy_run_list: Bad order: #{runlist}\n"
					exit
				else
					edges.push(($1.to_i-1),  $2.to_i)
					next
				end
			end

			if i =~ /^\(-(-?\d+)$/x
				unless first
					print "match rule 2\n"
					print "Set::IntSpan::_copy_run_list: Bad order: #{runlist}\n"
					exit
				end
				set_neg_inf(true)
				edges.push($1.to_i)
				next
			end

			if i =~ /^(-?\d+)-\)$/x
#				print "match rule 3\n"
				edges.push(($1.to_i-1))
				set_pos_inf(true)
				last = true
				next
			end

			if i =~ /^\(-\)$/x
				unless first
					print "match rule 4\n"
					print "Set::IntSpan::_copy_run_list: Bad order: #{runlist}\n"
					exit
				end
				set_neg_inf(true)
				set_pos_inf(true)
				last = true
				next
			end

			print "no match! \"#{i}\"\n"
			print "Set::IntSpan::_copy_run_list: Bad syntax: #{runlist}\n"
		end
		first = false
	end

	@set["edges"] = edges
	@set["run"] = []

	return true
end

#def splice(array, offset, length=nil, list=[])
#	if offset >= 0
#		length = array.length-offset unless length
#		leftarray = array.slice(0, offset)
#		rightarray = array.slice(offset+length, (array.length - offset))
#	else
#		length = array.length+offset unless length
#		leftarray = array.slice(0, (array.length+offset))
#		rightarray = array.slice(array.length+length+offset, array.length+offset)
#	end
#
#	array = leftarray
#	array += list
#	array += rightarray if rightarray
#
#	return array
#end

def to_s
	return run_list
end

def run_list
	if empty?
		return Empty_String
	end

	print "edges leng: ", @set["edges"].length, "\n" if Debuglevel > 0
	edges = []
	edges.concat(@set["edges"])
	runs = []

	if edges.length > 0
		edges.unshift('(') if neg_inf?
		edges.push(')') if pos_inf?

		print edges.join("/"),"\n" if Debuglevel > 0

		i = 0
		while i < edges.length
			print "edges leng: ", @set["edges"].length, "\n" if Debuglevel > 0
			lower = edges[i]
			i += 1
			upper = edges[i]
			i += 1
			print "Lower: \"#{lower}\" Upper: \"#{upper}\"\n" if Debuglevel > 0
			if !(lower.to_s == '(') and !(upper.to_s == ')') and ((lower+1) == upper)
				print "#{upper}\n" if Debuglevel > 0
				runs.push("#{upper}")
			else
				lower += 1 if (lower.to_s <=> "(")!=0
				print "#{lower}-#{upper}\n" if Debuglevel > 0
				runs.push("#{lower}-#{upper}")
			end
		end
	end

	print "edges leng: ", @set["edges"].length, "\n" if Debuglevel > 0

	return runs.join(',')
end

def elements
	if infinite?
		print "Set::IntSpan::elements: infinite set\n"
		exit
	end

	elements = []
	edges = @set["edges"].dup
	while (edges.length>0)
		lower, upper = edges.slice!(0..1)
		elements += (lower+1 .. upper).to_a
	end

	return elements
end

def _real_set(set_spec=nil)		# converts a set specification into a set
	(set_spec != nil and set_spec.class.to_s == "Set::IntSpan") ?
		set_spec :
		IntSpan.new(set_spec)
end

def union(set_spec)
	b = _real_set(set_spec)
	s = IntSpan.new
	
	s.set_neg_inf(neg_inf? || b.neg_inf?)

	eA = @set["edges"]
	eB = b.edges
	eS = s.edges

	inA = neg_inf?
	inB = b.neg_inf?

	iA = 0
	iB = 0

	while (iA < eA.length and iB < eB.length)
		xA = eA[iA]
		xB = eB[iB]

		if (xA < xB)
			iA += 1
			inA = ! inA
			not inB and eS.push(xA)
		elsif (xB < xA)
			iB += 1
			inB = ! inB
			not inA and eS.push(xB)
		else
			iA += 1
			iB += 1
			inA = ! inA
			inB = ! inB
			inA == inB and eS.push(xA)
		end
	end

	iA < eA.length and (! inB) and  eS.concat(eA[iA..eA.length])
	iB < eB.length and (! inA) and  eS.concat(eB[iB..eB.length])

	s.set_pos_inf(pos_inf? || b.pos_inf?)
	s.set_edges(eS)

	return s
end

def intersect(set_spec)
	b = _real_set(set_spec)
	s = IntSpan.new

	s.set_neg_inf(neg_inf? && b.neg_inf?)

	eA = @set["edges"]
	eB = b.edges
	eS = s.edges

	inA = neg_inf?
	inB = b.neg_inf?

	iA = 0
	iB = 0

	while (iA < eA.length and iB < eB.length)
		xA = eA[iA]
		xB = eB[iB]
		
		if (xA < xB)
			iA += 1
			inA = ! inA
			inB and eS.push(xA)
		elsif (xB < xA)
			iB += 1
			inB = ! inB
			inA and eS.push(xB)
		else
			iA += 1
			iB += 1
			inA = ! inA
			inB = ! inB
			inA == inB and eS.push(xA)
		end
	end

	iA < eA.length and inB and eS.concat(eA[iA..eA.length])
	iB < eB.length and inA and eS.concat(eB[iB..eB.length])

	s.set_neg_inf(pos_inf? && b.pos_inf?)
	s.set_edges(eS)
	return s
end

def diff (set_spec)
	b = _real_set(set_spec)
	s = IntSpan.new

	s.set_neg_inf(neg_inf? && ! b.neg_inf?)

	eA = @set["edges"]
	eB = b.edges
	eS = s.edges

	inA = neg_inf?
	inB = b.neg_inf?

	iA = 0
	iB = 0

	while (iA < eA.length and iB < eB.length)
		xA = eA[iA]
		xB = eB[iB]
		
		if (xA < xB)
			iA += 1
			inA = ! inA
			not inB and eS.push(xA)
		elsif (xB < xA)
			iB += 1
			inB = ! inB
			inA and eS.push(xB)
		else
			iA += 1
			iB += 1
			inA = ! inA
			inB = ! inB
			inA != inB and eS.push(xA)
		end
	end

	iA < eA.length and not inB and eS.concat(eA[iA..eA.length])
	iB < eB.length and     inA and eS.concat(eB[iB..eB.length])

	s.set_edges(eS)

	s.set_pos_inf(pos_inf? && ! b.pos_inf?)
	return s
end

def xor(set_spec)
	b = _real_set(set_spec)
	s = IntSpan.new

	s.set_neg_inf(neg_inf? ^ b.neg_inf?)

	eA = @set["edges"]
	eB = b.edges
	eS = s.edges

	iA = 0
	iB = 0

	while (iA < eA.length and iB < eB.length)
		xA = eA[iA]
		xB = eB[iB]
		
		if (xA < xB)
			iA += 1
			eS.push(xA)
		elsif (xB < xA)
			iB += 1
			eS.push(xB)
		else
			iA += 1
			iB += 1
		end
	end

	iA < eA.length and eS.concat(eA[iA..eA.length])
	iB < eB.length and eS.concat(eB[iB..eB.length])

	s.set_pos_inf(pos_inf? ^ b.pos_inf?)
	s.set_edges(eS)
	return s
end

def complement
# complement is inverse set; dit klopt hier dus niet
	a = first
	b = last

	print "first #{a} last #{b}\n" if Debuglevel > 0
	if a!=b
		s = IntSpan.new("#{a}-#{b}")
		comp = xor(s)
	else
		comp = IntSpan.new("#{a}")
	end

	if Debuglevel > 0
		while i = comp.next
			print "#{i}\n"
		end
	end

	comp.set_neg_inf(! comp.neg_inf?)
	comp.set_pos_inf(! comp.pos_inf?)
	return comp
end

def superset(set_spec)
	b = _real_set(set_spec)

	s = b.diff(self)
	return s.empty?
end

def subset(set_spec)
	b = _real_set(set_spec)

	s = diff(b)
	return s.empty?
end

def equal(set_spec)
	b = _real_set(set_spec)

print "a\n"
	neg_inf? == b.neg_inf? or return false
print "b\n"
	pos_inf? == b.pos_inf? or return false

	aEdge = @set["edges"]
	bEdge = b.edges
	print "aEdge #{aEdge.length} bEdge #{bEdge.length}\n"
	aEdge.length == bEdge.length or return false
print "c\n"

	for i in (0...aEdge.length)
		aEdge[i] == bEdge[i] or return false
	end

	return true
end

def equivalent(set_spec)
	b = _real_set(set_spec)

	cardinality == b.cardinality
end

def cardinality
	(neg_inf? or pos_inf?) and return -1

	car = 0
	edges = @set["edges"]
	i=0
	while (i < edges.length)
		lower = edges[i]
		upper = edges[i+1]
		car += upper - lower
		i += 2
	end

	return car
end

def empty?
	if neg_inf? || pos_inf? ||  @set["edges"].length > 0
		return false
	end
	return true
end

def edges
	return @set["edges"]
end

def set_edges(edges)
	@set["edges"] = edges
end

def neg_inf?
	return @set["negInf"]
end

def set_neg_inf(negInf)
	@set["negInf"] = negInf
end

def pos_inf?
	return @set["posInf"]
end

def set_pos_inf(posInf)
	@set["posInf"] = posInf
end

def finite?
	return (! neg_inf? and ! pos_inf?)
end

def infinite?
	return ! finite?
end

def universal
	neg_inf? and not @set["edges"].length > 0 and pos_inf?
end

# XXX this should probably have some recursion to make it faster
def member?(n)
	inSet = neg_inf?
	edge  = @set["edges"]

	for i in (0...edge.length)
		if inSet
			return true if n <= edge[i]
			inSet = false
		else
			return false if n <= edge[i]
			inSet = true
		end
	end

	inSet
end

def insert!(n)
	if @set["edges"].empty?
		@set["edges"] = [n-1, n]
		return
	end

	if n == @set["edges"][-1]+1
		@set["edges"][-1] += 1
		return
	elsif n > @set["edges"][-1]
		@set["edges"].push(n-1, n)
		return
	end

# XXX dit kan vast netter... toch de Dijkstra neuronen nog eens aansteken
# XXX this should probably have some recursion to make it faster
	l = 0
	r = @set["edges"].length-1
	i = r/2
	while true
		if n < @set["edges"][i] && n > @set["edges"][i-1]
			inSet = i.odd?
			break
		elsif n < @set["edges"][i] && i == 0
			inSet = false
			break
		elsif n < @set["edges"][i]
			r = i
			i = l + ((r-l)/2)
			# tikkeltje sneller dan neg_inf? aanroepen
			inSet = @set["negInf"]
		elsif n == @set["edges"][i]
			inSet = i.odd?
			break
		else
			l = i
			i = l + ((r-l)/2)
		end
	end

	inSet and return

	lGap = i == 0 || n-1 - @set["edges"][i-1]
	lGap = false if lGap == 0

	rGap = i == @set["edges"].length-1 ? i : @set["edges"][i] - n
	rGap = false if rGap == 0

	if ( lGap and rGap)
		@set["edges"].insert(i, n-1, n)
	elsif (not lGap and rGap)
		@set["edges"][i-1] += 1
	elsif ( lGap and not rGap)
		@set["edges"][i] -= 1
	else
		@set["edges"].slice!(i-1, 2)
	end
end

def remove!(n)
	n or return

	inSet = neg_inf?
	edge  = @set["edges"]

	for i in (0...edge.length)
		if (inSet)
			break if n <= edge[i]
			inSet = false
		else
			return if n <= edge[i]
			inSet = true
		end
	end

	return unless inSet

	for i in (0...edge.length)
		if edge[i] == n-1 and edge[i+1] == n
			lower = edge[0...i]
			upper = edge[i+2..edge.length]
			edge = lower + upper
			break
		elsif edge[i] == n-1
			edge[i] += 1
			break
		elsif edge[i] == n
			edge[i] += 1
			break
		elsif edge[i+1] == n
			edge[i+1] -= 1
			break
		elsif edge[i]<n and edge[i+1]>n
			lower = edge[0..i]
			upper = edge[i+1..edge.length]
			edge = lower + [n-1, n] +upper
			break
		end
		i += 1
	end

	@set["edges"] = edge
	return self
end

def min
	empty? and return nil
	neg_inf? and return nil
	@set["edges"][0]+1
end

def max
	empty? and return nil
	pos_inf? and return nil
	@set["edges"][-1]
end

def grep_set(block)
	return nil if neg_inf? or pos_inf?

	edges     = @set["edges"]
	sub_edges = []

	while (edges.length > 0)
		lower, upper = edges.slice!(0..1)
		#lower = edges[0]
		#upper = edges[1]
		#edges = edges.slice(2..edges.length)

		for i in (lower+1..upper)
#			local $_ = i
#			&$block() or next		# definately wrong, must eval block

			if (sub_edges.length > 0 and sub_edges[-1] == i-1)
				sub_edges[-1] = i
			else
				sub_edges += [ i-1, i ]
			end
		end
	end

	sub_set = new
	sub_set["edges"] = sub_edges
	sub_set
end

def map_set(block)
	return nil if neg_inf? or pos_inf?

	map_set = new

	edges = @set["edges"]
	while (edges.length > 0)
		lower, upper = edges.slice!(0..1)
		#lower = edges[0]
		#upper = edges[1]
		#edges = edges.slice(2..edges.length)

		for domain in (lower+1..upper)
			local $_ = domain;

#			for range (&$block())		# definately wrong, must eval block
#				map_set.insert(range)
#			end
		end
	end

	map_set
end

def first
	@set["iterator"] = min
	@set["run"] = []
	@set["run"][0]   = 0
	@set["run"][1]   = @set["edges"].length > 0 ? 1 : nil

	@set["iterator"]
end

def last
	lastEdge     = @set["edges"].length - 1
	@set["iterator"] = max
	@set["run"][0]   = lastEdge > 0 ? lastEdge-1 : nil
	@set["run"][1]   = lastEdge

	@set["iterator"]
end

def start(startval)
	set["iterator"] = nil
	startval or return nil

	inSet = neg_inf?
	edges = @set["edges"]

	for i in (0...edges.length)
		if (inSet)
			if (startval <= edges[i])
				@set["iterator"] = startval
				@set["run"][0] = i ? i-1 : nil
				@set["run"][1] = i
				return $startval
			end
			inSet = false
		else
			if (startval <= edges[i])
				return nil
			end
			inSet = true
		end
	end

	if (inSet)
		@set["iterator"] = startval
		@set["run"][0]   = edges.length > 0 ? edges.length: nil
		@set["run"][1]   = nil
	end

	@set["iterator"]
end

def current
	@set["iterator"]
end

def next
	@set["iterator"] or return first

	run1 = @set["run"][1]
	run1 or return ++@set["iterator"]

	edges = @set["edges"]
	if (@set["iterator"] < edges[run1])
		@set["iterator"] += 1
		return @set["iterator"]
	end

	if (run1 < edges.length-2)
		run0 = run1 + 1
		@set["run"] = [run0, run0+1]
		@set["iterator"] = edges[run0]+1
	elsif (run1 < edges.length-1)
		run0 = run1 + 1
		@set["run"] = [run0, nil]
		@set["iterator"] = edges[run0]+1
	else
		@set["iterator"] = nil
	end

	@set["iterator"]
end

def prev
	@set["iterator"] or return last

	run0 = @set["run"][0]
	run0 or return --@set["iterator"]

	edges = @set["edges"]

	if (@set["iterator"] > edges[run0]+1)
		@set["iterator"] -= 1
		return @set["iterator"]
	end

	if (run0 > 1)
		run1 = run0 - 1
		@set["run"] = [run1-1, run1]
		@set["iterator"] = edges[run1]
	elsif (run0 > 0)
		run1 = run0 - 1
		@set["run"] = [nil, run1]
		@set["iterator"] = edges[run1]
	else
		@set["iterator"] = nil
	end

	@set["iterator"]
end

end	# class

end	# module


# TODO
# Do not kill an item until it's tested!

# [x] new
# [x] valid
# [ ] copy
# [ ] _copy_empty			# makes $set the empty set
# [x] _copy_array			# copies an array into a set
# [ ] _copy_set			# copies one set to another
# [ ] _copy_run_list		# parses a run list
# [x] run_list
# [x] elements
# [x] _real_set		# converts a set specification into a set
# [x] union
# [x] intersect
# [x] diff
# [x] xor
# [ ] complement
# [x] superset
# [x] subset
# [x] equal
# [x] equivalent
# [x] cardinality
# [x] empty?
# [x] finite
# [x] neg_inf? { shift->{negInf} }
# [x] pos_inf? { shift->{posInf} }
# [x] infinite
# [ ] universal
# [x] member
# [x] insert		# way to much code i think
# [x] remove
# [x] min
# [x] max
# [ ] grep_set(&$)
# [ ] map_set(&$)
# [x] first($)
# [x] last($)
# [ ] start($$)
# [x] current($) { shift->{iterator} }
# [x] next($)
# [x] prev($)

# New methods
# [x] set_neg_inf
# [x] set_pos_inf
# [x] set_edges
# [x] edges