--successor Function
function binary_tree(x) 
   --Graphics Hook
   if (stuff_to_draw.tree == nil) then stuff_to_draw.tree = {}; table.insert(stuff_to_draw.tree, 1); end
   table.insert(stuff_to_draw.tree, x*2);
   table.insert(stuff_to_draw.tree, x*2+1);
   table.sort(stuff_to_draw.tree);
   
   --Inference: return the two binary successors of the given node(integer)
   return {x*2, x*2+1};
end

function finite_binary_tree(n)
   return function(x)
      --Criteria function for remove_if: chomp off those beyond a certain tree-height
      local function criteria(child)
         return n <= (math.log(child)/math.log(2));
      end
      
      --using the Criteria function to remove nodes not within criteria
      return remove_if(binary_tree(x), criteria);
   end
end

--goalp function
function is(value) return (function (x) return value == x; end) end

--emptyp function
function is_empty(list) return #list == 0; end

--combiner functions
function add_to_end(x, t) for i,v in ipairs(x) do table.insert(t, x[i]); end return t; end
function add_to_front(x, t) for i,v in ipairs(x) do table.insert(t, 1, x[i]); end return t; end

--tail returns lisp-style tail of a list
function tail(t) table.remove(t, 1); return t; end

function remove_if(t, criteria_fn)
   t2= {};
   for i,v in ipairs(t) do if not criteria_fn(t[i]) then table.insert(t2,t[i]) end end
   return t2;
end

--print list
function print_list(list, tag)
   io.write(tag, ": ");
   if #list == 0 then io.write("(Empty_List)"); print(""); end
   for i,v in ipairs(list) do io.write("(", list[i], ")"); end; print("");

   --create if nil   
   if (stuff_to_draw.printlists == nil) then stuff_to_draw.printlists = {}; end
   
   --add to stuff to draw
   table.insert(stuff_to_draw.printlists, list);
   stuff_to_draw.printlists[#stuff_to_draw.printlists].tag = tag;
end

--tree search
function tree_search (states, goalp, successors, combiner)
   print_list(states, "search states");
   
   --no more states to check?  then search failed
   if is_empty(states) then io.write("NIL"); print(""); return nil; end

	--Overflow check
	if #states > 100 then print("This is going nowhere...give up..."); return nil; end
	
	--did we find the goal?  if so, then return it
	if goalp(states[1]) then print("Bingo!"); return states[1]; end

	--recursive
	return tree_search(
						combiner(successors(states[1]), tail(states)),
						goalp,
						successors,
						combiner)
end

--Depth First Search Successors go in front
function dfs(start, goalp, successors) return tree_search(start, goalp, successors, add_to_front)  end

--Breadth First Search: Successors go at end
function bfs(start, goalp, successors) return tree_search(start, goalp, successors, add_to_end) end

--Depth First Iterative Deepening (DFID)
function dfid(start, goalp, successors, max_tier, now_)
   
   now = now_ or 1;
   if now > max_tier then return nil; end
   print("Extending leash to ", now);
   return dfs({1}, goalp, successors(now)) or dfid({1}, goalp, successors, max_tier, (now+1));
end

--Best First Search
function bestfs(start, goalp, successors, cost_fn)
   return tree_search(start, goalp, successors, sorter(cost_fn));
end

--Beam Search
function beam_search(states, goalp, successors, cost_fn, beam_width)

   --sort a list and return a beam-width pruned list
   local function combiner(old, new)
      sorted_states = sorter(cost_fn)(old, new);
      if (beam_width > #sorted_states) then return sorted_states; else return subsequence(sorted_states, 1, beam_width); end
   end

   return tree_search(states, goalp, successors, combiner);
   
end

--A_Star
function a_star_search(states, goalp, successors, cost_fn, cost_left_fn, state, old_states)
   
   --check if empty
   if emptyp(states) then io.write("NIL"); print(""); return nil; end
   
   --check if goal is found
   if goalp(states[1]) then print("Bingo!"); return states[1]; end
   
   --Want to minimize f(x) = cost from (start, here) + cost from (here, goal)
   --i.e. cost_fn + cost_left_fn
   
   --update states and old_states
   table.insert(old_states, states[1]);
   add_to_end(successors(states[1]), states);
   states = tail(states);
   
   
   
   --place the new path, path2 in the right list
   old = find_path(state2, states, state)
   
   old = find_path(state2, old_states, state);
   --recurse
   return a_star_search(states, goalp, successors, cost_fn, cost_left_fn, state, old_states);
end

--Diff
function diff (num)
   return function(x) return math.abs(x - num); end
end

--Sorter
function sorter(cost_fn)
   return function(new, old) 
      t = add_to_end(new,old);
      table.sort(t, function(a,b) return cost_fn(a) < cost_fn(b); end)
      return t;
   end 
end

function price_is_right(price)
   return function(x) if (x > price) then return most_positive_fixnum() else return (price - x) end end
end

function most_positive_fixnum()
   --return a really big number, for now (but isn't too big to handle)
   return 100000000000;
end

function subsequence(t, start, last)
   t2 = {};
   for i,v in ipairs(t) do if i >= start and i <= last then table.insert(t2, t[i]); end end
   return t2;
end

function eql()
   return function(a,b) return a == b; end;
end


function demo_dfs()
   print("-----Demo of Depth First Search-----");
   dfs({1}, is(12), binary_tree);
end

function demo_bfs()
   print("-----Demo of Breadth First Search-----");
   bfs({1}, is(12), binary_tree);
end

function demo_dfid()
   print("-----Demo of Depth First Iterative Deepening-----");
   dfid({1}, is(12), finite_binary_tree, 5);
end

function demo_bestfs()
   print("-----Demo of Best First Search-----");
   goal = 12;
   bestfs({1}, is(goal), binary_tree, diff(goal))
end

function demo_bestfs2()
   print("-----Demo of Best First Search *using penalties*-----");
   goal = 12;
   bestfs({1}, is(goal), binary_tree, price_is_right(goal));
end

function demo_beam_search()
   print("-----Demo of Beam Search-----");
   goal = 12;
   beam_search({1}, is(goal), binary_tree, diff(goal), 3);
end

function demo_trip()
   print("-----Demo of Beam Search on City Details-----");
   trip(find_city("San-Francisco"), find_city("Boston"));
end

function demo_astar_search()
   print("-----Demo of A-Star Search-----");
   print("under construction");
   goal = 12;
   a_star_search({1}, is(goal), binary_tree, diff(goal), diff(goal), eql, {});
end

function love.load()
   --Init the graphics
   stuff_to_draw = {};
   require "graphics";


   --Run Demoes of different search techniques	
	demo_bfs();
	--demo_dfs();
	--demo_dfid();
	--demo_bestfs();
	--demo_bestfs2();
	--demo_beam_search();

	--require "city_details --not fully done yet

	--demo_astar_search --not fully done yet
end