-- 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/layered.lua,v 1.2 2013/02/08 17:14:04 tantau Exp $


local layered = {}

-- Namespace

require("pgf.gd").layered = layered


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

-- 
-- This file defines some basic functions to compute and/or set the
-- ideal distances between nodes of any kind of layered drawing of a
-- graph.


---
-- Compute the ideal distance between two siblings
--
-- @param paddings A |Storage| object in which the computed distances
-- (paddings) are stored. 
-- @param graph The graph object
-- @param n1 The first node
-- @param n2 The second node

function layered.ideal_sibling_distance (paddings, graph, n1, n2)
  local ideal_distance
  local sep

  local n1_is_node = n1.kind == "node"
  local n2_is_node = n2.kind == "node"

  if not n1_is_node and not n2_is_node then
    ideal_distance = graph.options['sibling distance']
    sep =   graph.options['sibling post sep']
          + graph.options['sibling pre sep']
  else
    if n1_is_node then
      ideal_distance = lib.lookup_option('sibling distance', n1, graph)
    else
      ideal_distance = lib.lookup_option('sibling distance', n2, graph)
    end
    sep =   (n1_is_node and lib.lookup_option('sibling post sep', n1, graph) or 0)
          + (n2_is_node and lib.lookup_option('sibling pre sep', n2, graph) or 0)
  end
  
  return math.max(ideal_distance, sep + 
		  ((n1_is_node and paddings[n1].sibling_post) or 0) -
                  ((n2_is_node and paddings[n2].sibling_pre) or 0))
end



---
-- Compute the baseline distance between two layers
--
-- The "baseline" distance is the distance between two layers that
-- corresponds to the distance of the two layers if the nodes where
-- "words" on two adjacent lines. In this case, the distance is
-- normally the layer_distance, but will be increased such that if we
-- draw a horizontal line below the deepest character on the first
-- line and a horizontal line above the highest character on the
-- second line, the lines will have a minimum distance of layer sep.
--
-- Since each node on the lines might have a different layer sep and
-- layer distance specified, the maximum over all the values is taken.
--
-- @param paddings A |Storage| object in which the distances
-- (paddings) are stored.
-- @param graph The graph in which the nodes reside
-- @param l1 An array of the nodes of the first layer
-- @param l2 An array of the nodes of the second layer

function layered.baseline_distance (paddings, graph, l1, l2)

  if #l1 == 0 or #l2 == 0 then
    return 0
  end
  
  local layer_distance = -math.huge
  local layer_pre_sep  = -math.huge
  local layer_post_sep = -math.huge

  local max_post = -math.huge
  local min_pre = math.huge

  for _,n in ipairs(l1) do
    layer_distance = math.max(layer_distance, lib.lookup_option('level distance', n, graph))
    layer_post_sep = math.max(layer_post_sep, lib.lookup_option('level post sep', n, graph))
    if n.kind == "node" then
      max_post = math.max(max_post, paddings[n].layer_post)
    end
  end

  for _,n in ipairs(l2) do
    layer_pre_sep = math.max(layer_pre_sep, lib.lookup_option('level pre sep', n, graph))
    if n.kind == "node" then
      min_pre = math.min(min_pre, paddings[n].layer_pre)
    end
  end
  
  return math.max(layer_distance, layer_post_sep + layer_pre_sep + max_post - min_pre)
end



---
-- Position nodes in layers using baselines
--
-- @param layers A |Storage| object assigning layers to vertices.
-- @param paddings A |Storage| object storing the computed distances
-- (paddings). 
-- @param graph The graph in which the nodes reside

function layered.arrange_layers_by_baselines (layers, paddings, graph)

  local layer_vertices = Storage.newTableStorage()
  
  -- Decompose into layers:
  for _,v in ipairs(graph.vertices) do
    table.insert(layer_vertices[layers[v]], v)
  end
  
  if #layer_vertices > 0 then -- sanity check
    -- Now compute ideal distances and store
    local height = 0

    for _,v in ipairs(layer_vertices[1]) do
      v.pos.y = 0
    end
    
    for i=2,#layer_vertices do
      height = height + layered.baseline_distance(paddings, graph, layer_vertices[i-1], layer_vertices[i])

      for _,v in ipairs(layer_vertices[i]) do
	v.pos.y = height 
      end
    end
  end
end




-- Done

return layered