# axis_of_symmetry.rb -- final version
# Wyatt Carss
# February 26, 2011
#
# Documentation:

# Final version:
#
# I woke up this morning and couldn’t help but think “that can’t be right” 
# about the issue I ran into with the Hash yesterday -- it doesn’t make sense 
# that that’s the only way a hash-default value works. So I went to the docs 
# and found out that if I specify a call-block, it will then work as 
# originally expected. So I went back and removed the imitation of positive 
# y-values only, fixed some names, simplified the code, and in the process, 
# added good comments to everything. 
#
# It’s in a state where I’m happy to show it off - so I’m going to host this 
# file (and make it executable) at wcarss.ca/axis_of_symmetry.rb and 
# wcarss.ca/axis_of_symmetry.txt -- I guess I should just put them on a 
# github, but that’s where they’ll reside for now.
#
# Thanks again,
# Wyatt

##########
# begin notes written as I fixed the program: (each stop separated by \n’s)

# I’m going to go test this out and fix it. Thanks again :)     (old code is below new work)

# Things are looking good; I’ve got a battery of tests and the code runs / tests pass, but it’s
# only in a trivial way at the moment. I’m not truly generating symmetric and nonsymmetric
# fields yet, only 2-point symmetric or nonsymmetric arrays. I also haven’t written
# ‘sort_by_x’ yet. The two of them work together to allow the tests to pass at the moment,
# and for me to verify that the existing code is good. Next up: generate_symmetry
# and generate_nonsymmetry. That’ll show me that my tests definitely work (they’ll fail)
# then, sort_by_x, and at that point I can reign in the algorithm should any errors be found.

# looks like I’m returning false positive for some reason! Too many fields are being returned
# as symmetric at the moment.

# That was a long stretch. I was indexing negative y values into my array; and that just won’t
# do! So I switched to using a Hash to hold my arrays of points at each y value. Things didn’t
# work as expected, I had a lot of null data flying around for some reason. So I switched back
# to arrays, and kept a class variable across all points determining the minimum point.
#
# Class variables have some oddness to them that I wasn’t familiar with, so I had to read some
# docs and work things out -- I got it working, but found the same issue as with the hash!
# The hash was more elegant, so I put it back in, but kept the book-keeping for the min-y val.
# I came up with an alternate way of iterating over the hash, and it is working properly now:
# Most tests are failing! Next up: implementing sort_by_x, and then it should work as desired. :)

# Went away for a bit there, had a piece of pizza. Instead of implementing ‘sort_by_x’, I chose to
# just insert the points into each array in ascending order of their x-values. Everything seems to
# work at this point, aside from one test-case that I’m still pondering. For some reason, two
# points (1,1) and (2,2) are coming out as having a vertical symmetry. It’s doing something funny
# there, so I’ll check it out, but it works for large numbers of symmetrical and non-symmetrical
# points, and works for 1 point and 3 points but, not in this case! Finish line in sight.

# Done! It took a while but I figured out what has held this off from working -- it turns out that, in
# Ruby, if you create a Hash and give it a default value of a new Array, every block is the same
# array. So when you append to any array, you append to all of them. It was completely
# counterintuitive - I’d thought that Hash.new(Array.new) implied that Array.new would be called
# every time you access an unset array, but in fact, one new array is instantiated, and its
# address is just passed in. I switched back to an array of arrays, and the whole thing worked
# fine.
# That was quite a bit longer than I’d expected -- but the only problems I encountered were
# conceptual challenges to Ruby, which I must admit I am still learning. The algorithm has been
# correct since it was designed, and remains essentially unchanged.
# - Wyatt



#
# axis_of_symmetry.rb
#
# Contains function(s) to find( and generate) point-fields containing a
# vertical line of symmetry, and a quick test-suite to ensure proper operation.
#
# To run the suite, just uncomment the very last line, which reads:
#
# test_suite
#
# Otherwise the functions can be called as desired with this file required.
#
# Uses a hash-of-arrays indexed by y-value, each array sorted ascending by
# x-value, to iterate over and determine if a field holds a common vertical
# line of symmetry. At present, generates/deals with ~2000 points, from -1000
# to 1000 in x and y values, at random. No known bugs.
#
# Wyatt Carss
# February 26th, 2011
#

# Just a simple x,y tuple, really.
class Point
	attr_reader :x, :y
	attr_writer :x, :y

	def initialize(x,y)
		@x = x
		@y = y
	end
end

def generate_symmetry(axis = 0)
	a = [] # our array of points
	num = rand(1000) # an indicator of ~ half the # of total points

	# the offset takes some explanation. (see below it)
	offset = 0
	# If a point is on the axis, then it has no twin-point to keep symmetry with.
	# If a point is off the axis, then it does have a twin point.
	# Every time a point is generated, it may be on or off the axis. It's random.
	# So if a point is on the axis, we just store it. If it's off the axis, we
	# store it and then, at 1-past-the end of the array, we store its twin.
	#
	# offset begins at 0 -- it is used to access the very end of the array. It is
	# increased every time we generate a twin, so that it always points to the
	# very end.


	# zero-indexing is cool:
	0.upto(num-1) do |i|
		# generate a random point x,y such that x,y e_of [-1000 to 1000]
		x = rand(2000)-1000
		y = rand(2000)-1000

		# create the point
		a[i] = Point.new(x,y)

		# if it's not on the axis, and
		if x != axis then
			# it's above it, then
			if x > axis then
				# the twin-x is the same distance below
				twin_x = axis - (x - axis)
			else
				# otherwise (the point was below), it's the same distance above
				twin_x = axis + (axis - x)
			end

			# generate the twin, increase the offset (see the note above)
			a[num+offset] = Point.new(twin_x, y)
			offset += 1
		end
	end

	# at last, return the array, filled with a field containing a vertical
	# symmetry at x = axis
	a
end

def generate_nonsymmetry()
	# begin with a symmetric space (at a random axis, no less)
	a = generate_symmetry(rand(2000)-1000)

	# then increase a random x-value by one. Guaranteed non-symmetric.
	a[rand(a.length)].x += 1

	# return the array...
	a
end

def is_vertically_symmetric(array)
	if array == nil then return 0
	elsif array.length == 0 then return 0
	elsif array.length  == 1 then return 1
	end

	#store the points in a hash of arrays, indexed by y-value
	point_hash = Hash.new { |hash, key| hash[key] = Array.new() }
	#we're going to store all of the y values used
	y_array = []

	array.each do |p|
		# append each point onto the end of the array, to give it the right size
		point_hash[p.y] << p

		#save the y position, if it's never been saved before
		if y_array.include?(p.y) == false then
			y_array << p.y
		end

		#insertion in ascending order
		i = 0    # set at the beginning of the array
		j = point_hash[p.y].length - 1 # set at the end of the array

		# walk forward until the x-value <= the next x-value, causes ascending
		# guaranteed to terminate because p.x already exists in last spot
		while p.x > point_hash[p.y][i].x
			i += 1 # this is the index to store p into
		end

		# walk backward, copying j[i-1] onto a[j], 'shifting' the array outward
		# this is fine, because they'll just copy over p at the end - and we
		# have it stored elsewhere. This leaves a duplicate at a[i] and a[i+1].
		while j > i
			point_hash[p.y][j] = point_hash[p.y][j-1]
			j -= 1
		end

		# write p into a[i], restoring ascending order, eliminating the duplicate
		point_hash[p.y][i] = p;
	end

	# we need to ensure that each y-level has the same axis as all the others -
	# so, we record a level's calculated axis in 'old_axis' and check it at each
	# iteration.
	#
	# 'nil' to start for first-run of the loop; thanks loose naming.
	old_axis = nil

	# For every y-value saved (doesn't matter the order):
	y_array.each do |y|
		# use 'y' as a key into the hash, retrieving the point array:
		p_array = point_hash[y]
		len = p_array.length-1

		# calculate the axis of the outer two points
		axis = (p_array[0].x + p_array[len].x)/2.0

		#if old_axis != nil and axis != old_axis then
		# if that axis isn't the same as the previous one, fail
		if axis != old_axis then
			return 0 unless old_axis == nil
		end

		# iterate over the points in the array; the axis should never change
		0.upto(len / 2) do |i|
			# if the axis did change, fail out
			if (p_array[i].x + p_array[len-i].x)/2.0 != axis then
				return 0
			end
		end

		# save for the next iteration
		old_axis = axis        
	end

	# Success! The point-field has a vertical line of symmetry!
	return 1
end

def test_nil()
	# should return 0; no symmetry in nothing!
	is_vertically_symmetric(nil)
end

def test_zero_length()
	# should also return 0; no symmetry to be found in nothing
	is_vertically_symmetric([])
end

def test_one_point(p)
	# should return 1; a single point is symmetric in the axis of its x-value
	is_vertically_symmetric([p])
end

def test_two_points(p1, p2)
	# if p1.y == p2.y, returns 1, otherwise 0:
	# -- when they aren't equal: the points are at different heights; unsymmetric
	# -- when they're equal: always symmetric at the average of the 2 points
	is_vertically_symmetric([p1,p2])
end

def test_symmetric_field(axis)
	# generate a symmetry, test it -- should always return 1
	a = generate_symmetry(axis)
	is_vertically_symmetric(a)
end

def test_nonsymmetric_field()
	# generate a nonymmetry, test it -- should always return 0
	a = generate_nonsymmetry()
	is_vertically_symmetric(a)
end

# calls the test-suite
def test_suite()
	# Array of expected return values:
	ae = [0,0,1,1,0,1,1,1,1,0]
	# Array to store results:
	ar = [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]

	# Call the tests, print 'true' or 'false' if pass or fail.
	ar[0] = test_nil
	puts "test 0: " + (ar[0] == ae[0]).to_s
	ar[1] = test_zero_length
	puts "test 1: " + (ar[1] == ae[1]).to_s
	ar[2] = test_one_point(Point.new(0,1))
	puts "test 2: " + (ar[2] == ae[2]).to_s
	ar[3] = test_one_point(Point.new(1,1))
	puts "test 3: " + (ar[3] == ae[3]).to_s
	ar[4] = test_two_points(Point.new(1,1), Point.new(2,2))
	puts "test 4: " + (ar[4] == ae[4]).to_s
	ar[5] = test_two_points(Point.new(1,1), Point.new(-1,1))
	puts "test 5: " + (ar[5] == ae[5]).to_s
	ar[6] = is_vertically_symmetric([Point.new(-1,0), Point.new(0,0), Point.new(1,0)])
	puts "test 6: " + (ar[6] == ae[6]).to_s
	ar[7] = test_symmetric_field(0)
	puts "test 7: " + (ar[7] == ae[7]).to_s
	ar[8] = test_symmetric_field(1)
	puts "test 8: " + (ar[8] == ae[8]).to_s
	ar[9] = test_nonsymmetric_field()
	puts "test 9: " + (ar[9] == ae[9]).to_s

	# Determine if the suite passed.
	pass = 1
	ar.each_with_index do |e, i|
		if e != ae[i] then
			pass = 0
		end
	end

	# Give the user something prettier than 'true' and 'false'.
	if pass == 1 then
		puts "Tests pass!"
	else
		puts "Tests fail!"
		puts "Array reads: " + ar.to_s
	end

	# return pass/fail status if needed
	pass
end

test_suite


#
# original code below
#
# (using if-false to ‘kill’ the code

if false then

	# directly-commented out some of this so that the interpreter doesn't complain	
	#class point
	#    x = 0
	#    y = 0
	#end

	#def is_vertically_symmetric(array)
	#    if array == nil return 0
	#    elsif array.length == 0 return 0
	#    elsif array.length  == 1 return 1

	array.each do |p|
		new_array[p.y][new_array[p.y].length] = p
	end

	old_axis = nil

	new_array.each do |p_array|
		p_array.sort_by_x()
		len = p_array.length-1
		axis = (p_array[0].x + p_array[len].x)/2

		if old_axis != nil and axis != old_axis then
			return 0
		end

		0.upto(len / 2) do |i|
			if (p_array[i].x + p_array[len-i].x)/2 != axis then
				return 0
			end
		end

		old_axis = axis   
	end

	return 1
	#end # aligns with def is_vertically_symmetric
end