-- Copyright 2012 by Till Tantau
--
-- This file may be distributed an/or modified
--
-- 1. under the LaTeX Project Public License and/or
-- 2. under the GNU Public License
--
-- See the file doc/generic/pgf/licenses/LICENSE for more information

-- @release $Header: /cvsroot/pgf/pgf/generic/pgf/graphdrawing/lua/pgf/gd/control/Sublayouts.lua,v 1.4 2013/09/23 20:04:26 tantau Exp $

local function full_print(g, pref)
  local s = ""

  for _,v in ipairs(g.vertices) do
    s = s .. tostring(v) .. "[" .. tostring(v.pos) .. "]\n "
  end
  
  s = s .. "\n"

  for _,a in ipairs(g.arcs) do
    for _,e in ipairs(a.syntactic_edges) do
      s = s .. tostring(e) .. "(" .. tostring(e.path) .. ")\n"
    end
  end
  
  pgf.debug((pref or "") .. s)
end


---
-- The |Sublayouts| module handles graphs for which multiple layouts are defined. 
--
-- Please see Section~\ref{section-gd-sublayouts} for an overview of
-- sublayouts. 
--

local Sublayouts = {}

-- Namespace
require("pgf.gd.control").Sublayouts = Sublayouts


-- Includes

local Digraph    = require "pgf.gd.model.Digraph"
local Vertex     = require "pgf.gd.model.Vertex"
local Coordinate = require "pgf.gd.model.Coordinate"
local Path       = require "pgf.gd.model.Path"

local lib        = require "pgf.gd.lib"

local InterfaceCore = require "pgf.gd.interface.InterfaceCore"

local Storage    = require "pgf.gd.lib.Storage"



-- Storages

local subs           = Storage.newTableStorage()
local already_nudged = Storage.new()
local positions      = Storage.newTableStorage()




-- Offset a node by an offset. This will \emph{also} offset all
-- subnodes, which arise from sublayouts.
--
-- @param vertex A vertex
-- @param pos A offset
--
local function offset_vertex(v, delta)
  v.pos:shiftByCoordinate(delta)
  for _,sub in ipairs(subs[v]) do
    offset_vertex(sub, delta)
  end
end


-- Nudge positioning. You can call this function  several times on the
-- same graph; nudging will be done only once. 
--
-- @param graph A graph
--
local function nudge(graph)
  for _,v in ipairs(graph.vertices) do
    local nudge = v.options['nudge']
    if nudge and not already_nudged[v] then
      offset_vertex(v, nudge)
      already_nudged[v] = true
    end
  end
end



-- Create subgraph nodes
--
-- @param scope A scope
-- @param syntactic_digraph The syntactic digraph.
-- @param test Only for vertices whose subgraph collection passes this test will we create subgraph nodes 
local function create_subgraph_node(scope, syntactic_digraph, vertex)
  
  local subgraph_collection = vertex.subgraph_collection
  local binding = InterfaceCore.binding
  
  local cloud = {}
  -- Add all points of n's collection, except for v itself, to the cloud:
  for _,v in ipairs(subgraph_collection.vertices) do
    if vertex ~= v then
      assert(syntactic_digraph:contains(v), "the layout must contain all nodes of the subgraph")
      for _,p in ipairs(v.path) do
	if type(p) == "table" then
	  cloud[#cloud+1] = p + v.pos
	end
      end
    end
  end
  for _,e in ipairs(subgraph_collection.edges) do
    for _,p in ipairs(e.path) do
      if type(p) == "table" then
	cloud[#cloud+1] = p:clone()
      end
    end
  end
  local x_min, y_min, x_max, y_max, c_x, c_y = Coordinate.boundingBox(cloud)

  -- Shift the graph so that it is centered on the origin:
  for _,p in ipairs(cloud) do
    p:unshift(c_x,c_y)
  end

  local o = vertex.subgraph_info.generated_options

  o[#o+1] = { key = "subgraph point cloud", value = table.concat(lib.imap(cloud, tostring)) }
  o[#o+1] = { key = "subgraph bounding box height", value = tostring(y_max-y_min) .. "pt" }
  o[#o+1] = { key = "subgraph bounding box width", value = tostring(x_max-x_min) .. "pt" }
    
  -- And now, the "grand call":
  binding:createVertex(vertex.subgraph_info)
  
  -- Shift it were it belongs
  vertex.pos:shift(c_x,c_y)
  
  -- Remember all the subnodes for nudging and regardless
  -- positioning
  local s = {}
  for _,v in ipairs(subgraph_collection.vertices) do
    if v ~= vertex then
      s[#s+1] = v
    end
  end

  subs[vertex] = s
end


-- Tests whether two graphs have a vertex in common
local function intersection(g1, g2)
  for _,v in ipairs(g1.vertices) do
    if g2:contains(v) then
      return v
    end
  end
end

-- Tests whether a graph is a set is a subset of another
local function special_vertex_subset(vertices, graph)
  for _,v in ipairs(vertices) do
    if not graph:contains(v) and not (v.kind == "subgraph node") then
      return false
    end
  end
  return true
end



---
-- The layout recursion. See \ref{section-gd-sublayouts} for details.
--
-- @param scope The graph drawing scope
-- @param layout The to-be-laid-out collection
-- @param fun The to-be-called function for laying out the graph.
-- processed. This stack is important when a new syntactic vertex is
-- added by the algorithm: In this case, this vertex is added to all
-- layouts on this stack.
--
-- @return A laid out graph.

function Sublayouts.layoutRecursively(scope, layout, fun)
  
  -- Step 1: Iterate over all sublayouts of the current layout:
  local resulting_graphs = {}
  local loc = Storage.new()
   
  -- Now, iterate over all sublayouts
  for i,child in ipairs(layout:childrenOfKind(InterfaceCore.sublayout_kind)) do
    resulting_graphs[i] = Sublayouts.layoutRecursively(scope, child, fun)
    loc[resulting_graphs[i]] = child
  end
  
  -- Step 2: Run the merge process:
  local merged_graphs = {}
  
  while #resulting_graphs > 0 do
    
    local n = #resulting_graphs

    -- Setup marked array:
    local marked = {}
    for i=1,n do
      marked[i] = false
    end
    
    -- Mark first graph and copy everything from there
    marked[1] = true
    local touched = Storage.new()
    for _,v in ipairs(resulting_graphs[1].vertices) do
      v.pos = positions[v][resulting_graphs[1]]
      touched[v] = true
    end    

    -- Repeatedly find a node that is connected to a marked node:
    local i = 1
    while i <= n do
      if not marked[i] then
	for j=1,n do
	  if marked[j] then
	    local v = intersection(resulting_graphs[i], resulting_graphs[j])
	    if v then
	      -- Aha, they intersect at vertex v

	      -- Mark the i-th graph:
	      marked[i] = true
	      connected_some_graph = true
	      
	      -- Shift the i-th graph:
	      local x_offset = v.pos.x - positions[v][resulting_graphs[i]].x
	      local y_offset = v.pos.y - positions[v][resulting_graphs[i]].y
	      	      
	      for _,u in ipairs(resulting_graphs[i].vertices) do
		if not touched[u] then
		  touched[u] = true
		  u.pos = positions[u][resulting_graphs[i]]:clone()
		  u.pos:shift(x_offset, y_offset)

		  for _,a in ipairs(resulting_graphs[i]:outgoing(u)) do
		    for _,e in ipairs(a.syntactic_edges) do
		      for _,p in ipairs(e.path) do
			if type(p) == "table" then
			  p:shift(x_offset, y_offset)
			end
		      end
		    end
		  end
		end
	      end
	      
	      -- Restart
	      i = 0
	      break
	    end		
	  end
	end
      end
      i = i + 1
    end

    -- Now, we can collapse all marked graphs into one graph:
    local merge = Digraph.new {}
    merge.syntactic_digraph = merge
    local remaining = {}
    
    -- Add all vertices and edges:
    for i=1,n do
      if marked[i] then
	merge:add (resulting_graphs[i].vertices)
	for _,a in ipairs(resulting_graphs[i].arcs) do
	  local ma = merge:connect(a.tail,a.head)
	  for _,e in ipairs(a.syntactic_edges) do
	    ma.syntactic_edges[#ma.syntactic_edges+1] = e
	  end
	end
      else
	remaining[#remaining + 1] = resulting_graphs[i]
      end
    end

    -- Remember the first layout this came from:
    loc[merge] = loc[resulting_graphs[1]]

    -- Restart with rest:
    merged_graphs[#merged_graphs+1] = merge
    
    resulting_graphs = remaining
  end
  
  -- Step 3: Run the algorithm on the layout:
  
  local class = layout.options.algorithm_phases.main 
  assert (type(class) == "table", "algorithm selection failed")
  
  local algorithm = class
  local uncollapsed_subgraph_nodes = lib.imap(
    scope.collections[InterfaceCore.subgraph_node_kind] or {},
    function (c)
      if c.parent_layout == layout then
	return c.subgraph_node
      end
    end)

  
  -- Create a new syntactic digraph:
  local syntactic_digraph = Digraph.new {
    options = layout.options
  }

  syntactic_digraph.syntactic_digraph = syntactic_digraph
  
  -- Copy all vertices and edges from the collection...
  syntactic_digraph:add (layout.vertices)
  for _,e in ipairs(layout.edges) do
    syntactic_digraph:add {e.head, e.tail}
    local arc = syntactic_digraph:connect(e.tail, e.head)    
    arc.syntactic_edges[#arc.syntactic_edges+1] = e
  end

  -- Find out which subgraph nodes can be created now and make them part of the merged graphs
  for i=#uncollapsed_subgraph_nodes,1,-1 do
    local v = uncollapsed_subgraph_nodes[i]
    local vertices = v.subgraph_collection.vertices
    -- Test, if all vertices of the subgraph are in one of the merged graphs.
    for _,g in ipairs(merged_graphs) do
      if special_vertex_subset(vertices, g) then
	-- Ok, we can create a subgraph now
	create_subgraph_node(scope, syntactic_digraph, v)
	-- Make it part of the collapse!
	g:add{v}
	-- Do not consider again
	uncollapsed_subgraph_nodes[i] = false
	break
      end
    end
  end

  -- Collapse the nodes that are part of a merged_graph
  local collapsed_vertices = {}
  for _,g in ipairs(merged_graphs) do

    local intersection = {}
    for _,v in ipairs(g.vertices) do
      if syntactic_digraph:contains(v) then
	intersection[#intersection+1] = v
      end
    end
    if #intersection > 0 then
      -- Compute bounding box of g (this should actually be the convex
      -- hull) Hmm...:
      local array = {}
      for _,v in ipairs(g.vertices) do
	local min_x, min_y, max_x, max_y = v:boundingBox()
	array[#array+1] = Coordinate.new(min_x + v.pos.x, min_y + v.pos.y)
	array[#array+1] = Coordinate.new(max_x + v.pos.x, max_y + v.pos.y)
      end
      for _,a in ipairs(g.arcs) do
	for _,e in ipairs(a.syntactic_edges) do
	  for _,p in ipairs(e.path) do
	    if type(p) == "table" then
	      array[#array+1] = p
	    end
	  end
	end
      end
      local x_min, y_min, x_max, y_max, c_x, c_y = Coordinate.boundingBox(array)

      -- Shift the graph so that it is centered on the origin:
      for _,v in ipairs(g.vertices) do
	v.pos:unshift(c_x,c_y)
      end
      for _,a in ipairs(g.arcs) do
	for _,e in ipairs(a.syntactic_edges) do
	  for _,p in ipairs(e.path) do
	    if type(p) == "table" then
	      p:unshift(c_x,c_y)
	    end
	  end
	end
      end

      x_min = x_min - c_x
      x_max = x_max - c_x
      y_min = y_min - c_y
      y_max = y_max - c_y

      local index = loc[g].event.index

      local v = Vertex.new {
	-- Standard stuff
	shape = "none",
	kind  = "node",
	path  = Path.new {
	  "moveto",
	  x_min, y_min,
	  x_min, y_max, 
	  x_max, y_max,
	  x_max, y_min,
	  "closepath"
	},
	options = {},
	event = scope.events[index]
      }
      
      -- Update node_event
      scope.events[index].parameters = v
      
      local collapse_vertex = syntactic_digraph:collapse(
	intersection,
	v,
	nil,
	function (new_arc, arc)
	  for _,e in ipairs(arc.syntactic_edges) do
	    new_arc.syntactic_edges[#new_arc.syntactic_edges+1] = e
	  end
	end)

      syntactic_digraph:remove(intersection)
      collapsed_vertices[#collapsed_vertices+1] = collapse_vertex
    end
  end

  -- Sort the vertices
  table.sort(syntactic_digraph.vertices, function(u,v) return u.event.index < v.event.index end) 
  
  -- Should we "hide" the subgraph nodes?
  local hidden_node
  if not algorithm.include_subgraph_nodes then
    local subgraph_nodes = lib.imap (syntactic_digraph.vertices,
      function (v) if v.kind == "subgraph node" then return v end end) 
    
    if #subgraph_nodes > 0 then
      hidden_node = Vertex.new {}
      syntactic_digraph:collapse(subgraph_nodes, hidden_node)
      syntactic_digraph:remove (subgraph_nodes)
      syntactic_digraph:remove {hidden_node}
    end
  end

  -- Now, we want to call the actual algorithm. This call may modify
  -- the layout's vertices and edges fields, namely when new vertices
  -- and edges are created. We then need to add these to our local
  -- syntactic digraph. So, we remember the length of these fields
  -- prior to the call and then add everything ``behind'' these
  -- positions later on.

  -- Ok, everything setup! Run the algorithm...
  fun(scope, algorithm, syntactic_digraph, layout)
    
  if hidden_node then
    syntactic_digraph:expand(hidden_node)
  end
  
  -- Now, we need to expand the collapsed vertices once more:
  for i=#collapsed_vertices,1,-1 do
    syntactic_digraph:expand(
      collapsed_vertices[i],
      function (c, v)
	v.pos:shiftByCoordinate(c.pos)
      end,
      function (a, v)
	for _,e in ipairs(a.syntactic_edges) do
	  for _,p in ipairs(e.path) do
	    if type(p) == "table" then
	      p:shiftByCoordinate(v.pos)
	    end
	  end
	end
      end
    )
    for _,a in ipairs(syntactic_digraph:outgoing(collapsed_vertices[i])) do
      for _,e in ipairs(a.syntactic_edges) do
	for _,p in ipairs(e.path) do
	  if type(p) == "table" then
	    p:shiftByCoordinate(a.tail.pos)
	    p:unshiftByCoordinate(e.tail.pos)
	  end
	end
      end
    end
  end
  syntactic_digraph:remove(collapsed_vertices)

  -- Step 4: Create the layout node if necessary
  for i=#uncollapsed_subgraph_nodes,1,-1 do
    if uncollapsed_subgraph_nodes[i] then
      create_subgraph_node(scope, syntactic_digraph, uncollapsed_subgraph_nodes[i])
    end
  end
  
  -- Now seems like a good time to nudge and do regardless positioning
  nudge(syntactic_digraph)

  -- Step 5: Cleanup  
  -- Push the computed position into the storage:
  for _,v in ipairs(syntactic_digraph.vertices) do
    positions[v][syntactic_digraph] = v.pos:clone()
  end
  
  return syntactic_digraph
end





---
-- Regardless positioning.
--
-- @param graph A graph
--
function Sublayouts.regardless(graph)
  for _,v in ipairs(graph.vertices) do
    local regardless = v.options['regardless at']
    if regardless then
      offset_vertex(v, regardless - v.pos)
    end
  end
end



-- Done 

return Sublayouts