1/*
2* Copyright (c) 2018 (https://github.com/phase1geo/Minder)
3*
4* This program is free software; you can redistribute it and/or
5* modify it under the terms of the GNU General Public
6* License as published by the Free Software Foundation; either
7* version 2 of the License, or (at your option) any later version.
8*
9* This program is distributed in the hope that it will be useful,
10* but WITHOUT ANY WARRANTY; without even the implied warranty of
11* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12* General Public License for more details.
13*
14* You should have received a copy of the GNU General Public
15* License along with this program; if not, write to the
16* Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17* Boston, MA 02110-1301 USA
18*
19* Authored by: Trevor Williams <phase1geo@gmail.com>
20*/
21
22/*
23 This class stores a pointer to a node to partition as well as its pixel size
24 that is used for balancing purposes.
25*/
26public class PartNode : Object {
27
28  private Node?  _node = null;
29  private double _size;
30
31  /* Creates a single partitioner node */
32  public PartNode( Node n ) {
33    var nb = n.tree_bbox;
34    if( (n.side == NodeSide.LEFT) || (n.side == NodeSide.RIGHT) ) {
35      _size = nb.height;
36    } else {
37      _size = nb.width;
38    }
39    _node = n;
40  }
41
42  /* Returns the size required by this node */
43  public double size() { return( _size ); }
44
45  /* Returns the stored node */
46  public Node? node() { return( _node ); }
47
48  /* Updates the node based on the given information */
49  public void update_node( Node root, int index, int side ) {
50    NodeSide orig_side = _node.side;
51    if( (_node.side == NodeSide.LEFT) || (_node.side == NodeSide.RIGHT) ) {
52      _node.side = (side == 0) ? NodeSide.LEFT : NodeSide.RIGHT;
53    } else {
54      _node.side = (side == 0) ? NodeSide.TOP  : NodeSide.BOTTOM;
55    }
56    if( orig_side != _node.side ) {
57      _node.layout.propagate_side( _node, _node.side );
58    }
59    _node.attach_init( root, index );
60  }
61
62}
63
64/*
65 Main class used for root node balancing.  This class uses a greedy partioning
66 algorithm to provide node balancing.
67*/
68public class Partitioner : Object {
69
70  /* Default constructor */
71  public Partitioner() {}
72
73  /* Partitions the given root node */
74  public void partition_node( Node root ) {
75    if( root.children().length > 2 ) {
76      var data = new SList<PartNode>();
77      for( int i=0; i<root.children().length; i++ ) {
78        var node = root.children().index( i );
79        var pn   = new PartNode( node );
80        data.append( pn );
81      }
82      CompareFunc<PartNode> pn_cmp1 = (a, b) => {
83        return( (a.node().id() < b.node().id()) ? 1 : -1 );
84      };
85      CompareFunc<PartNode> pn_cmp2 = (a, b) => {
86        return( (a.size() < b.size()) ? 1 : ((a.size() == b.size()) ? 0 : -1) );
87      };
88      data.sort( pn_cmp1 );
89      data.sort( pn_cmp2 );
90      partition( root, data );
91    }
92  }
93
94  /*
95   Performs a greedy algorithm for node balancing. This is not an optimal
96   algorithm (unlike the KK number partioning algorithm), but it is simple
97   to implement and I'm not sure that it really matters that we are completely
98   optimal anyways.
99  */
100  protected virtual void partition( Node root, SList<PartNode> data ) {
101
102    double sum0  = 0;
103    double sum1  = 0;
104    int    size0 = 0;
105
106    /* Detach all of the nodes */
107    data.@foreach((item) => {
108      item.node().detach( item.node().side );
109    });
110
111    /* Attach the nodes according to the side */
112    data.@foreach((item) => {
113      if( sum0 < sum1 ) {
114        sum0 += item.size();
115        item.update_node( root, size0, 0 );
116        size0++;
117      } else {
118        sum1 += item.size();
119        item.update_node( root, -1, 1 );
120      }
121    });
122
123  }
124
125}
126