-- 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/examples/SimpleHuffman.lua,v 1.5 2013/12/20 14:44:46 tantau Exp $


---
-- @section subsubsection {How To Generate Nodes Inside an Algorithm}
--
-- @end



-- Imports
local layered               = require "pgf.gd.layered"
local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms"
local declare               = require "pgf.gd.interface.InterfaceToAlgorithms".declare

-- The class
local SimpleHuffman = {}


---

declare {
  key       = "simple Huffman layout",
  algorithm = SimpleHuffman,
  
  postconditions = {
    upward_oriented = true
  },

  summary = [["
      This algorithm demonstrates how an algorithm can generate new
      nodes.
  "]],
  documentation = [["  
      The input graph should just consist of some nodes (without
      edges) and each node should have a |probability| key set. The nodes
      will then be arranged in a line (as siblings) and a Huffman tree
      will be constructed ``above'' these nodes. For the construction of
      the Huffman tree, new nodes are created and connected.
      
      \pgfgdset{
        HuffmanLabel/.style={/tikz/edge node={node[fill=white,font=\footnotesize,inner sep=1pt]{#1}}},
        HuffmanNode/.style={/tikz/.cd,circle,inner sep=0pt,outer sep=0pt,draw,minimum size=3pt}
      }
      
\begin{codeexample}[]
\tikz \graph [simple Huffman layout,
              level distance=7mm, sibling distance=8mm, grow'=up]
{
  a ["0.5",  probability=0.5],
  b ["0.12", probability=0.12],
  c ["0.2",  probability=0.2],
  d ["0.1",  probability=0.1],
  e ["0.11", probability=0.11]
};    
\end{codeexample}
     The file starts with some setups and declarations:
\begin{codeexample}[code only, tikz syntax=false]
-- File pgf.gd.examples.SimpleHuffman
      
local declare = require "pgf.gd.interface.InterfaceToAlgorithms".declare
      
-- The class
local SimpleHuffman = {}

declare {
  key            = "simple Huffman layout",
  algorithm      = SimpleHuffman,
  postconditions = { upward_oriented = true  }
  summary = "..."
}

declare {
  key = "probability",
  type = "number",
  initial = "1",
  summary = "..."
}
      
-- Import
local layered = require "pgf.gd.layered"
local InterfaceToAlgorithms = require "pgf.gd.interface.InterfaceToAlgorithms"
local Storage = require "pgf.gd.lib.Storage"

local probability = Storage.new()
local layer       = Storage.new()

function SimpleHuffman:run()
  -- Construct a Huffman tree on top of the vertices...
\end{codeexample}
      
         Next comes a setup, where we create the working list of vertices
         that changes as the Huffman coding method proceeds:
\begin{codeexample}[code only, tikz syntax=false]
  -- Shorthand
  local function prop (v)
    return probability[v] or v.options['probability']
  end
        
  -- Copy the vertex table, since we are going to modify it:
  local vertices = {}
  for i,v in ipairs(self.ugraph.vertices) do
    vertices[i] = v
  end
\end{codeexample}
      
         The initial vertices are arranged in a line on the last layer. The
         function |ideal_sibling_distance| takes care of the rather
         complicated handling of the (possibly rotated) bounding boxes and
         separations. The |props| and |layer| are tables used by
         algorithms to ``store stuff'' at a vertex or at an arc. The
         table will be accessed by |arrange_layers_by_baselines| to
         determine the ideal vertical placements.
\begin{codeexample}[code only, tikz syntax=false]
  -- Now, arrange the nodes in a line:
  vertices [1].pos.x = 0
  layer[ vertices [1] ] = #vertices
  for i=2,#vertices do
    local d = layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, vertices[i-1], vertices[i])
    vertices [i].pos.x = vertices[i-1].pos.x + d
    layer[ vertices [i] ] = #vertices
  end
\end{codeexample}  
      
         Now comes the actual Huffman algorithm: Always find the vertices
         with a minimal probability\dots
\begin{codeexample}[code only, tikz syntax=false]
  -- Now, do the Huffman thing...
  while #vertices > 1 do
    -- Find two minimum probabilities
    local min1, min2
    
    for i=1,#vertices do
      if not min1 or prop(vertices[i]) < prop(vertices[min1]) then
        min2 = min1
        min1 = i
      elseif not min2 or prop(vertices[i]) < prop(vertices[min2]) then
        min2 = i
      end
    end
\end{codeexample}
         \dots and connect them with a new node. This new node gets the
         option |HuffmanNode|. It is now the job of the higher layers to map
         this option to something ``nice''.
\begin{codeexample}[code only, tikz syntax=false]
    -- Create new node:
    local p = prop(vertices[min1]) + prop(vertices[min2])
    local v = InterfaceToAlgorithms.createVertex(self, { generated_options = {{key="HuffmanNode"}}})
    probability[v] = p
    layer[v] = #vertices-1
    v.pos.x = (vertices[min1].pos.x + vertices[min2].pos.x)/2
    vertices[#vertices + 1] = v
    
    InterfaceToAlgorithms.createEdge (self, v, vertices[min1],
        {generated_options = {{key="HuffmanLabel", value = "0"}}})
    InterfaceToAlgorithms.createEdge (self, v, vertices[min2],
        {generated_options = {{key="HuffmanLabel", value = "1"}}})
      
    table.remove(vertices, math.max(min1, min2))
    table.remove(vertices, math.min(min1, min2))
  end
\end{codeexample}
         Ok, we are mainly done now. Finish by computing vertical placements
         and do formal cleanup.
\begin{codeexample}[code only, tikz syntax=false]
  layered.arrange_layers_by_baselines(layers, self.adjusted_bb, self.ugraph)
end
\end{codeexample}
      
       In order to use the class, we have to make sure that, on the
       display layer, the options |HuffmanLabel| and |HuffmanNode| are
       defined. This is done by adding, for instance, the following to
       \tikzname:
\begin{codeexample}[code only]
\pgfkeys{
  /graph drawing/HuffmanLabel/.style={
    /tikz/edge node={node[fill=white,font=\footnotesize,inner sep=1pt]{#1}}
  },
  /graph drawing/HuffmanNode/.style={
    /tikz/.cd,circle,inner sep=0pt,outer sep=0pt,draw,minimum size=3pt
  }
}
\end{codeexample}
  "]]
}    
    

---

declare {
  key = "probability",
  type = "number",
  initial = "1",

  summary = [["  
       The probability parameter. It is used by the Huffman algorithm to
       group nodes.
   "]]
}
  
-- Imports
    
local Storage    =  require 'pgf.gd.lib.Storage'
    
-- Storages
    
local probability = Storage.new()
local layer       = Storage.new()


function SimpleHuffman:run()
  -- Construct a Huffman tree on top of the vertices...

  -- Shorthand
  local function prop (v)
    return probability[v] or v.options['probability']
  end
  
  -- Copy the vertex table, since we are going to modify it:
  local vertices = {}
  for i,v in ipairs(self.ugraph.vertices) do
    vertices[i] = v
  end
  
  -- Now, arrange the nodes in a line:
  vertices [1].pos.x = 0
  layer[vertices [1]] = #vertices
  for i=2,#vertices do
    local d = layered.ideal_sibling_distance(self.adjusted_bb, self.ugraph, vertices[i-1], vertices[i])
    vertices [i].pos.x = vertices[i-1].pos.x + d
    layer[vertices [i]] = #vertices
  end
  
  -- Now, do the Huffman thing...
  while #vertices > 1 do
    -- Find two minimum probabilities
    local min1, min2

    for i=1,#vertices do
      if not min1 or prop(vertices[i]) < prop(vertices[min1]) then
        min2 = min1
        min1 = i
      elseif not min2 or prop(vertices[i]) < prop(vertices[min2]) then
        min2 = i
      end
    end

    -- Create new node:
    local p = prop(vertices[min1]) + prop(vertices[min2])
    local v = InterfaceToAlgorithms.createVertex(self, { generated_options = {{key="HuffmanNode"}}})
    probability[v] = p
    layer[v] = #vertices-1
    v.pos.x = (vertices[min1].pos.x + vertices[min2].pos.x)/2
    vertices[#vertices + 1] = v
    
    InterfaceToAlgorithms.createEdge (self, v, vertices[min1],
                                 {generated_options = {{key="HuffmanLabel", value = "0"}}})
    InterfaceToAlgorithms.createEdge (self, v, vertices[min2],
                                 {generated_options = {{key="HuffmanLabel", value = "1"}}})

    table.remove(vertices, math.max(min1, min2))
    table.remove(vertices, math.min(min1, min2))
  end
  
  layered.arrange_layers_by_baselines(layer, self.adjusted_bb, self.ugraph)
end

return SimpleHuffman