
function isBound(val, b1, b2)
	return ((val >= math.min(b1, b2)) and (val <= math.max(b1, b2)))
end

function math.sgn(x)
	return (x==0) and 0 or ( (x>0) and 1 or -1 )
end

---- Point stuff ----
-------------------------------------------------------------------------------

function isSamePoint(p1, p2)
	return (p1[1] == p2[1] and p1[2] == p2[2])
end

function isRightTurn(p1, p2, p3)
	if p1[1] < p2[1] then -- to the right
		return (p3[2] > p1[2])
	elseif p1[1] > p2[1] then -- to the left
		return (p3[2] < p1[2])
	elseif p1[2] < p2[2] then -- going down
		return (p3[1] < p1[1])
	elseif p1[2] > p2[2] then -- elevator goooing up
		return (p3[1] > p1[1])
	end
	Debug:print("BUGCHECK", "Nonsensical isRightTurn call", p1, p2, p3)
end

function ULPoint(...)
	local r = {1000, 1000}
	for _, p in ipairs(arg) do
		if p[1] <= r[1] and p[2] <= r[2] then r = p end
	end
	return r
end
function LLPoint(...)
	local r = {1000, -1000}
	for i, p in ipairs(arg) do
		if p[1] <= r[1] and p[2] >= r[2] then r = p end
	end
	return r
end
function URPoint(...)
	local r = {-1000, 1000}
	for i, p in ipairs(arg) do
		if p[1] >= r[1] and p[2] <= r[2] then r = p end
	end
	return r
end
function LRPoint(...)
	local r = {-1000, -1000}
	for i, p in ipairs(arg) do
		if p[1] >= r[1] and p[2] >= r[2] then r = p end
	end
	return r
end

function orderedRect(p, q, r, s)
	return {ULPoint(p,q,r,s), LRPoint(p,q,r,s)}
end

function colDetRectPoint(rect, p)
	local rx1, ry1, rx2, ry2 = rect[1][1]+1, rect[1][2]+1, rect[2][1]-1, rect[2][2]-1
	return (p[1] > rx1 and p[1] < rx2 and p[2] > ry1 and p[2] < ry2)
end

-- note before you reuse: works only if lines are always horizontal or vertical
function colDetRectLine(rect, line)
	local rx1, ry1, rx2, ry2 = rect[1][1]+1, rect[1][2]+1, rect[2][1]-1, rect[2][2]-1
	local lx1, ly1, lx2, ly2 = line[1][1], line[1][2], line[2][1], line[2][2]
	return (
		colDetRectPoint(rect, line[1]) or -- point 1 inside?
		colDetRectPoint(rect, line[2]) or -- point 2 inside?
		(isBound(lx1, rx1, rx2) and -- crossing top to bottom?
			((ly1<ry1 and ly2>ry2) or (ly2<ry1 and ly1>ry2))) or
		(isBound(ly1, ry1, ry2) and -- crossing left to right?
			((lx1<rx1 and lx2>rx2) or (lx2<rx1 and lx1>rx2)))
		)
end

-- uh oh, performance optimized
LEEWAY = 3
function colDetRectLineAlt(rect, p1, p2, hor)
	local rx1, ry1, rx2, ry2 = rect[1][1], rect[1][2], rect[2][1], rect[2][2]
	if hor then
		local ly = p1[2]
		if ly >= ry1 and ly <= ry2 then
			local lx1, lx2 = p1[1], p2[1]
			if lx1 < lx2 then
				lx1, lx2 = lx1+LEEWAY, lx2-LEEWAY
				return (lx1<rx2 and lx2>rx1)
			else
				lx1, lx2 = lx1-LEEWAY, lx2+LEEWAY
				return (lx2<rx2 and lx1>rx1)
			end
		end
	else
		local lx = p1[1]
		if lx >= rx1 and lx <= rx2 then
			local ly1, ly2 = p1[2], p2[2]
			if ly1 < ly2 then
				ly1, ly2 = ly1+LEEWAY, ly2-LEEWAY
				return (ly1<ry2 and ly2>ry1)
			else
				ly1, ly2 = ly1-LEEWAY, ly2+LEEWAY
				return (ly2<ry2 and ly1>ry1)
			end
		end
	end
end

-- only checks for collisions from the "inside"
--~ function colDetRectLineIn(rect, p1, p2, hor)
--~ 	local rx1, ry1, rx2, ry2 = rect[1][1], rect[1][2], rect[2][1], rect[2][2]
--~ 	if hor then
--~ 		local ly = p1[2]
--~ 		local lx1, lx2 = p1[1], p2[1]
--~ 		if lx1 < lx2 then -- left to right // upper bound
--~ 			return (ry1 <= ly and ry2 > ly and lx1<rx2 and lx2>rx1)
--~ 		else
--~ 			return (ry2 >= ly and ry1 < ly and lx2<rx2 and lx1>rx1)
--~ 		end
--~ 	else
--~ 		local lx = p1[1]
--~ 		local ly1, ly2 = p1[2], p2[2]
--~ 		if ly1 < ly2 then -- top to bottom // right bound
--~ 			return (rx2 >= lx and rx1 < lx and ly1<ry2 and ly2>ry1)
--~ 		else
--~ 			return (rx1 <= lx and rx2 > lx and ly2<ry2 and ly1>ry1)
--~ 		end
--~ 	end
--~ end
function colDetRectLineIn(rect, p1, p2, hor)
	if hor then
		if p1[1] < p2[1] then -- left to right // upper bound
			return (rect[1][2] <= p1[2] and rect[2][2] > p1[2] and p1[1]<rect[2][1] and p2[1]>rect[1][1])
		else
			return (rect[2][2] >= p1[2] and rect[1][2] < p1[2] and p2[1]<rect[2][1] and p1[1]>rect[1][1])
		end
	else
		if p1[2] < p2[2] then -- top to bottom // right bound
			return (rect[2][1] >= p1[1] and rect[1][1] < p1[1] and p1[2]<rect[2][2] and p2[2]>rect[1][2])
		else
			return (rect[1][1] <= p1[1] and rect[2][1] > p1[1] and p2[2]<rect[2][2] and p1[2]>rect[1][2])
		end
	end
end


function colDetRectRect(r1, r2)
	local r1x1, r1y1, r1x2, r1y2 = r1[1][1], r1[1][2], r1[2][1], r1[2][2]
	local r2x1, r2y1, r2x2, r2y2 = r2[1][1], r2[1][2], r2[2][1], r2[2][2]
	return not(r1x2 < r2x1 or r1y2 < r2y1 or r1x1 > r2x2 or r1y1 > r2y2)
end

function rectArea(r)
	return ((r[2][1] - r[1][1]) * (r[2][2] - r[1][2]))
end

function removeSuperfluous(linelist)
	local i = 1
	local p1, p2, p3
	while linelist[i] do
		p1, p2, p3 = linelist[i-1] or linelist[table.getn(linelist)], 
			linelist[i], linelist[i+1] or linelist[1]
		if (p1[1] == p2[1] and p1[1] == p3[1]) or
				(p1[2] == p2[2] and p1[2] == p3[2]) then
			table.remove(linelist, i)
		else i = i+1 end
	end
end

function polarToCartesian(p)
	local a = math.rad(p[1])
	return { math.cos(a)*p[2], math.sin(a)*p[2] }
end

function cartesianToPolar(p)
	return { math.deg(math.atan2(p[2], p[1])), math.sqrt(p[1]*p[1] + p[2]*p[2]) }
end

---- Debugging ----
-------------------------------------------------------------------------------

Debug = {
	argcache = {},
	enabled = true
}

function Debug:print(...)
	if self.enabled then
		table.insert(self.argcache, arg)
		self:printNumbered(table.getn(self.argcache))
	end
end

function Debug:printNumbered(i)
	arg = self.argcache[i]
	screen:clear()
	screen:print(10, 8, "Debug call:", colors.lightgray)
	local v
	for i=1,arg.n do
		v = arg[i]
		screen:print(10, 10+10*i, tostring(v), colors.white)
		if type(v) == "table" and table.getn(v) == 2 then -- it's a point, probably
			screen:print(200, 10+10*i, "{ " .. tostring(v[1]) .. ", " .. tostring(v[2]) .. " }", colors.white)
		end
	end
	screen:print(10, 250, "(press start to continue, select to save as \"debug"..i..".png\")", colors.lightgray)
	screen:print(10, 260, "(debug message "..i.." of "..
		table.getn(self.argcache)..", use L and R to navigate)", colors.lightgray)
	screen.flip()
	
	System.sleep(200)
	local n = nil
	repeat
		ctrl = Controls.read()
		if ctrl:start() then 
			if ctrl:triangle() then self.enabled = false end
			System.sleep(200)
			break
		elseif ctrl:select() then screen:save("debug"..i..".png")
		elseif ctrl:l() and i > 1 then n = i-1
		elseif ctrl:r() and i < table.getn(self.argcache) then n = i+1
		end
	until n
	if n then self:printNumbered(n) end
end

---- Table stuff ----
-------------------------------------------------------------------------------

function getIndex(t, elem)
	for i, e in pairs(t) do
		if e == elem then return i end
	end
	return 0
end

function copy(t)
	local copy = {}
	for i,v in pairs(t) do
		copy[i] = v
	end
	return copy
end

function deepCopy(t, lookup_table)
	local copy = {}
	for i,v in pairs(t) do
		if type(v) ~= "table" then
			copy[i] = v
		else
			lookup_table = lookup_table or {}
			lookup_table[t] = copy
			if lookup_table[v] then
				copy[i] = lookup_table[v] -- we already copied this table. reuse the copy.
			else
				copy[i] = deepCopy(v, lookup_table) -- not yet copied. copy it.
			end
		end
	end
	return copy
end

function tableString(x, tlevel) 
	local s 
	tlevel = (tlevel or 0) + 1
    if type(x) == "table" then
        s = "{" 
        local i, v = next(x) 
        while i do
            if tlevel < 10 then
                s = s .. i .. "=" .. tableString(v, tlevel) 
            else
                s = s .. i .. "={#}" 
            end 
			i, v = next(x, i) 
			if i then s = s .. ", " end 
		end
		return s .. "}\n" 
    elseif type(x) == "function" then return "FUNC" 
	elseif type(x) == "file" then return "FILE" end 
    return tostring(x) 
end

---- Directory listing stuff ----
-------------------------------------------------------------------------------

function dirContains(dir, fn)
	for _, v in dir do
		if v.name == fn then return true end
	end
end

---- LuaPlayer objects method additions ----
-------------------------------------------------------------------------------

function Sound:playAt(pos)
	local v = self:play()
	v:pan(pos)
end

function screen:flash(color)
	screen:fillRect(0, 0, SCREEN_WIDTH, SCREEN_HEIGHT, color)
end

---- Other stuff ----
-------------------------------------------------------------------------------

function serialize(o, stream)
	if type(o) == "number" then
		stream:write(o)
	elseif type(o) == "string" then
		stream:write(string.format("%q", o))
	elseif type(o) == "table" then
		stream:write("{\n")
		for k, v in pairs(o) do
			stream:write("  [")
			serialize(k, stream)
			stream:write("] = ")
			serialize(v, stream)
			stream:write(",\n")
		end
		stream:write("}\n")
	else
		Debug:print("Error: cannot serialize a " .. type(o))
	end
end

function placify(number)
	if number == 1 then return "first!"
	elseif number == 2 then return "second"
	elseif number == 3 then return "third"
	else return tostring(number).."th" end
end
