-- 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/trees/ReingoldTilford1981.lua,v 1.11 2014/03/19 09:20:59 tantau Exp $



---
-- @section subsubsection {The Reingold--Tilford Layout}
--
-- @end

local ReingoldTilford1981 = {}

-- Imports
local layered = require "pgf.gd.layered"
local declare = require("pgf.gd.interface.InterfaceToAlgorithms").declare
local Storage = require "pgf.gd.lib.Storage"

---
declare {
  key       = "tree layout",
  algorithm = ReingoldTilford1981,
  
  preconditions = {
    connected = true,
    tree      = true
  },

  postconditions = {
    upward_oriented = true
  },

  documentation_in = "pgf.gd.trees.doc"
}


---
declare {
  key    = "missing nodes get space",
  type   = "boolean",
  documentation_in = "pgf.gd.trees.doc"
}



---
declare {
  key     = "significant sep",
  type    = "length",
  initial = "0",
  documentation_in = "pgf.gd.trees.doc"
}


---
declare {
  key  = "binary tree layout",
  use = {
    { key = "tree layout" },
    { key = "minimum number of children" , value=2 },
    { key = "significant sep", value = 10 },
  },
  documentation_in = "pgf.gd.trees.doc"
}
    
---
declare {
  key = "extended binary tree layout",
  use = {
    { key = "tree layout" },
    { key = "minimum number of children" , value=2 },
    { key = "missing nodes get space" },
    { key = "significant sep", value = 0 },
  },
  documentation_in = "pgf.gd.trees.doc"
}




-- Now comes the implementation:
  
function ReingoldTilford1981:run()

  local root = self.spanning_tree.root

  local layers = Storage.new()
  local descendants = Storage.new()
  
  self.extended_version = self.digraph.options['missing nodes get space']
  
  self:precomputeDescendants(root, 1, layers, descendants)
  self:computeHorizontalPosition(root, layers, descendants)
  layered.arrange_layers_by_baselines(layers, self.adjusted_bb, self.ugraph)

end


function ReingoldTilford1981:precomputeDescendants(node, depth, layers, descendants)
  local my_descendants = { node }

  for _,arc in ipairs(self.spanning_tree:outgoing(node)) do
    local head = arc.head
    self:precomputeDescendants(head, depth+1, layers, descendants)
    for _,d in ipairs(descendants[head]) do
      my_descendants[#my_descendants + 1] = d
    end
  end
  
  layers[node] = depth
  descendants[node] = my_descendants
end



function ReingoldTilford1981:computeHorizontalPosition(node, layers, descendants)
  
  local children = self.spanning_tree:outgoing(node)

  node.pos.x = 0

  local child_depth = layers[node] + 1

  if #children > 0 then
    -- First, compute positions for all children:
    for i=1,#children do
      self:computeHorizontalPosition(children[i].head, layers, descendants)
    end
    
    -- Now, compute minimum distances and shift them
    local right_borders = {}

    for i=1,#children-1 do
      
      local local_right_borders = {}
      
      -- Advance "right border" of the subtree rooted at
      -- the i-th child
      for _,d in ipairs(descendants[children[i].head]) do
        local layer = layers[d]
        local x     = d.pos.x          
        if self.extended_version or not (layer > child_depth and d.kind == "dummy") then
          if not right_borders[layer] or right_borders[layer].pos.x < x then
            right_borders[layer] = d
          end
          if not local_right_borders[layer] or local_right_borders[layer].pos.x < x then
            local_right_borders[layer] = d
          end
        end
      end

      local left_borders = {}
      -- Now left for i+1 st child
      for _,d in ipairs(descendants[children[i+1].head]) do
        local layer = layers[d]
        local x     = d.pos.x          
        if self.extended_version or not (layer > child_depth and d.kind == "dummy") then
          if not left_borders[layer] or left_borders[layer].pos.x > x then
            left_borders[layer] = d
          end
        end
      end

      -- Now walk down the lines and try to find out what the minimum
      -- distance needs to be.

      local shift = -math.huge
      local first_dist = left_borders[child_depth].pos.x - local_right_borders[child_depth].pos.x
      local is_significant = false

      for layer,n2 in pairs(left_borders) do
        local n1 = right_borders[layer]
        if n1 then
          shift = math.max(
            shift, 
            layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, n1, n2) + n1.pos.x - n2.pos.x
          )
        end
        if local_right_borders[layer] then
          if layer > child_depth and
            (left_borders[layer].pos.x - local_right_borders[layer].pos.x <= first_dist) then 
            is_significant = true
          end
        end
      end

      if is_significant then
        shift = shift + self.ugraph.options['significant sep']
      end

      -- Shift all nodes in the subtree by shift:
      for _,d in ipairs(descendants[children[i+1].head]) do
        d.pos.x = d.pos.x + shift
      end
    end
    
    -- Finally, position root in the middle:
    node.pos.x = (children[1].head.pos.x + children[#children].head.pos.x) / 2
  end
end



return ReingoldTilford1981