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