link2.rb

def cmp(a, b)

	return a <=> b
	
end

def insert(l, x1)
	
	if (l.empty?) then
		i = 0
	elsif (cmp(l.last, x1) == -1) then
		i = l.size
	else
		i = (0...l.size).find { |x| cmp(x1, l[x]) != 1 }
	end
	
	l[i, 0] = [x1]
	
end

def testA()

	l = []
	10.times { insert(l, rand(50)) }
	p(l)

end

def val(l, a, x)
	
	t = 0
	l.size.times \
	{
		|y|
		next if (x == y)
		
		i, j, s = x < y ? [x, y, 1] : [y, x, -1]
		t += a[[i, j]] * s
	}
	return t
end

def val2(l, a)
	return (0...l.size).map { |x| val(l, a, x) }
end

def insert2(l, a, r, x)
	
	l << x
	(l.size - 1).times \
	{
		|j|
		t = 0
		l[0].size.times { |i| t += l[j][i] <=> l[-1][i] }
		a[[j, l.size - 1]] = t
	}
	r << val(l, a, l.size - 1) if (!l.empty?)
	(l.size - 1).times \
	{
		|j|
		r[j] += a[[j, l.size - 1]]
	}

end

def out2(a, c)

	c.times \
	{
		|j|
		p((0...j).map { |i| a[[i, j]] })
	}
	p(a)
end

def out(l, a, n)
	puts("\nl#{n}")
	l.each { |x| p(x) }
	
	puts("\na#{n}")
	out2(a, l.size)
	
end

def build(n, l)
	
	a = {}
	l2 = []
	r = []
	l.each { |x| insert2(l2, a, r, x) }
	out(l, a, n)
	return l2, a, r
end

def delete(l, a, x, r)

	r.size.times \
	{
		|y|
		next if (x == y)
		i, j, s = x < y ? [x, y, 1] : [y, x, -1]
		
		r[y] += a[[i, j]] * s
	}
	r.delete_at(x)

	l.delete_at(x)
	puts("\ndelete ##{x}")
	(0...x).each \
	{
		|i|
		(x..(l.size)).each \
		{
			|j|
			a[[i, j]] = a[[i, j + 1]]
		}
	}
	(x..l.size).each \
	{
		|i|
		((i + 1)..(l.size)).each \
		{
			|j|
			a[[i, j]] = a[[i + 1, j + 1]]
		}
	}
	l.size.times { |j| a.delete([j, l.size]) }
	
end

def eq(va, vb, a, b)

	t = a == b
	puts("\n#{va} == #{vb} #{t}")
	raise if (!t)
	
end

def testB(x)

	l1, a1, r1i = build('1', (1..5).map { (1..5).map { rand(10) } })
	
	r1 = val2(l1, a1)
	
	puts("\nr1")
	p(r1)
	puts("\nr1i")
	p(r1i)
	
	eq('r1', 'r1i', r1, r1i)
	
	delete(l1, a1d = a1.dup, x, r1d = r1.dup)

	l2, a2, = build('2', l1)
	
	puts("\na1d")
	out2(a1d, l2.size)

	eq('a2', 'a1d', a2, a1d)
	
	r2 = val2(l2, a2)
	
	puts("\nr2")
	p(r2)
	puts("\nr1d")
	p(r1d)
	
	eq('r2', 'r1d', r2, r1d)
	
	
end


3.times { |x| puts("\n*** test A ##{x + 1}\n"); testA() }
[0,2,4].each { |x| puts("\n*** test B ##{x + 1}\n"); testB(x) }