git.mjollnir.org Git - moodle.git/blob

   1 package flare.vis.operator.layout
   2 {
   3         import flare.vis.operator.Operator;
   4         import flare.vis.data.NodeSprite;
   5         import flash.geom.Point;
   6         import flare.animate.Transitioner;
   7         import flare.util.Arrays;
   8
   9         /**
  10          * Layout that places nodes using a tidy layout of a node-link tree
  11          * diagram. This algorithm lays out a rooted tree such that each
  12          * depth level of the tree is on a shared line. The orientation of the
  13          * tree can be set such that the tree goes left-to-right (default),
  14          * right-to-left, top-to-bottom, or bottom-to-top.
  15          *
  16          * <p>The algorithm used is that of Christoph Buchheim, Michael Jünger,
  17          * and Sebastian Leipert from their research paper
  18          * <a href="http://citeseer.ist.psu.edu/buchheim02improving.html">
  19          * Improving Walker's Algorithm to Run in Linear Time</a>, Graph Drawing 2002.
  20          * This algorithm corrects performance issues in Walker's algorithm, which
  21          * generalizes Reingold and Tilford's method for tidy drawings of trees to
  22          * support trees with an arbitrary number of children at any given node.</p>
  23          */
  24         public class NodeLinkTreeLayout extends Layout
  25         {
  26                 // -- Properties ------------------------------------------------------
  27
  28                 /** Property name for storing parameters for this layout. */
  29                 public static const PARAMS:String = "nodeLinkTreeLayoutParams";
  30
  31                 private var _orient:String = Orientation.LEFT_TO_RIGHT; // orientation
  32                 private var _bspace:Number = 5;  // the spacing between sibling nodes
  33         private var _tspace:Number = 25; // the spacing between subtrees
  34         private var _dspace:Number = 50; // the spacing between depth levels
  35         private var _depths:Array = new Array(20); // stores depth co-ords
  36         private var _maxDepth:int = 0;
  37         private var _ax:Number, _ay:Number; // for holding anchor co-ordinates
  38                 private var _t:Transitioner; // temp variable for transitioner access
  39
  40                 /** The orientation of the layout. */
  41                 public function get orientation():String { return _orient; }
  42                 public function set orientation(o:String):void { _orient = o; }
  43
  44                 /** The space between successive depth levels of the tree. */
  45                 public function get depthSpacing():Number { return _dspace; }
  46                 public function set depthSpacing(s:Number):void { _dspace = s; }
  47
  48                 /** The space between siblings in the tree. */
  49                 public function get breadthSpacing():Number { return _bspace; }
  50                 public function set breadthSpacing(s:Number):void { _bspace = s; }
  51
  52                 /** The space between different sub-trees. */
  53                 public function get subtreeSpacing():Number { return _tspace; }
  54                 public function set subtreeSpacing(s:Number):void { _tspace = s; }
  55
  56
  57                 // -- Methods ---------------------------------------------------------
  58
  59                 /**
  60                  * Creates a new NodeLinkTreeLayout.
  61                  * @param orientation the orientation of the layout
  62                  * @param depthSpace the space between depth levels in the tree
  63                  * @param breadthSpace the space between siblings in the tree
  64                  * @param subtreeSpace the space between different sub-trees
  65                  */
  66                 public function NodeLinkTreeLayout(
  67                         orientation:String=Orientation.LEFT_TO_RIGHT, depthSpace:Number=50,
  68                         breadthSpace:Number=5, subtreeSpace:Number=25)
  69                 {
  70                         _orient = orientation;
  71                         _dspace = depthSpace;
  72                         _bspace = breadthSpace;
  73                         _tspace = subtreeSpace;
  74                 }
  75
  76                 /** @inheritDoc */
  77                 public override function operate(t:Transitioner=null):void
  78                 {
  79                         _t = t!=null ? t : Transitioner.DEFAULT; // set transitioner
  80
  81                 Arrays.fill(_depths, 0);
  82                 _maxDepth = 0;
  83
  84                 var a:Point = layoutAnchor;
  85                 _ax = a.x; _ay = a.y;
  86
  87                 var root:NodeSprite = layoutRoot as NodeSprite;
  88                 if (root == null) { _t = null; return; }
  89                 var rp:Params = params(root);
  90
  91                 // do first pass - compute breadth information, collect depth info
  92                 firstWalk(root, 0, 1);
  93
  94                 // sum up the depth info
  95                 determineDepths();
  96
  97                 // do second pass - assign layout positions
  98                 secondWalk(root, null, -rp.prelim, 0, true);
  99
 100                 updateEdgePoints(_t);
 101                 _t = null; // clear transitioner reference
 102         }
 103
 104         private function firstWalk(n:NodeSprite, num:int, depth:uint):void
 105         {
 106                 var np:Params = params(n);
 107                 np.number = num;
 108                 updateDepths(depth, n);
 109
 110                 var expanded:Boolean = n.expanded;
 111                 if (n.childDegree == 0 || !expanded) // is leaf
 112                 {
 113                         var l:NodeSprite = n.prevNode;
 114                         np.prelim = l==null ? 0 : params(l).prelim + spacing(l,n,true);
 115                 }
 116                 else if (expanded) // has children, is expanded
 117                 {
 118                         var midpoint:Number, i:uint;
 119                         var lefty:NodeSprite = n.firstChildNode;
 120                         var right:NodeSprite = n.lastChildNode;
 121                         var ancestor:NodeSprite = lefty;
 122                         var c:NodeSprite = lefty;
 123
 124                         for (i=0; c != null; ++i, c = c.nextNode) {
 125                                 firstWalk(c, i, depth+1);
 126                                 ancestor = apportion(c, ancestor);
 127                         }
 128                         executeShifts(n);
 129                         midpoint = 0.5 * (params(lefty).prelim + params(right).prelim);
 130
 131                         l = n.prevNode;
 132                         if (l != null) {
 133                                 np.prelim = params(l).prelim + spacing(l,n,true);
 134                                 np.mod = np.prelim - midpoint;
 135                         } else {
 136                                 np.prelim = midpoint;
 137                         }
 138                 }
 139         }
 140
 141         private function apportion(v:NodeSprite, a:NodeSprite):NodeSprite
 142         {
 143                 var w:NodeSprite = v.prevNode;
 144                 if (w != null) {
 145                         var vip:NodeSprite, vim:NodeSprite, vop:NodeSprite, vom:NodeSprite;
 146                         var sip:Number, sim:Number, sop:Number, som:Number;
 147
 148                         vip = vop = v;
 149                         vim = w;
 150                         vom = vip.parentNode.firstChildNode;
 151
 152                         sip = params(vip).mod;
 153                         sop = params(vop).mod;
 154                         sim = params(vim).mod;
 155                         som = params(vom).mod;
 156
 157                         var shift:Number;
 158                         var nr:NodeSprite = nextRight(vim);
 159                         var nl:NodeSprite = nextLeft(vip);
 160                         while (nr != null && nl != null) {
 161                                 vim = nr;
 162                                 vip = nl;
 163                                 vom = nextLeft(vom);
 164                                 vop = nextRight(vop);
 165                                 params(vop).ancestor = v;
 166                                 shift = (params(vim).prelim + sim) -
 167                                         (params(vip).prelim + sip) + spacing(vim,vip,false);
 168
 169                                 if (shift > 0) {
 170                                         moveSubtree(ancestor(vim,v,a), v, shift);
 171                                         sip += shift;
 172                                         sop += shift;
 173                                 }
 174
 175                                 sim += params(vim).mod;
 176                         sip += params(vip).mod;
 177                         som += params(vom).mod;
 178                         sop += params(vop).mod;
 179
 180                         nr = nextRight(vim);
 181                         nl = nextLeft(vip);
 182                 }
 183                 if (nr != null && nextRight(vop) == null) {
 184                         var vopp:Params = params(vop);
 185                         vopp.thread = nr;
 186                         vopp.mod += sim - sop;
 187                 }
 188                 if (nl != null && nextLeft(vom) == null) {
 189                         var vomp:Params = params(vom);
 190                         vomp.thread = nl;
 191                         vomp.mod += sip - som;
 192                         a = v;
 193                 }
 194                 }
 195                 return a;
 196         }
 197
 198         private function nextLeft(n:NodeSprite):NodeSprite
 199         {
 200                 var c:NodeSprite = null;
 201                 if (n.expanded) c = n.firstChildNode;
 202                 return (c != null ? c : params(n).thread);
 203         }
 204
 205         private function nextRight(n:NodeSprite):NodeSprite
 206         {
 207                 var c:NodeSprite = null;
 208                 if (n.expanded) c = n.lastChildNode;
 209                 return (c != null ? c : params(n).thread);
 210         }
 211
 212                 private function moveSubtree(wm:NodeSprite, wp:NodeSprite, shift:Number):void
 213                 {
 214                         var wmp:Params = params(wm);
 215                         var wpp:Params = params(wp);
 216                         var subtrees:Number = wpp.number - wmp.number;
 217                         wpp.change -= shift/subtrees;
 218                         wpp.shift += shift;
 219                         wmp.change += shift/subtrees;
 220                         wpp.prelim += shift;
 221                         wpp.mod += shift;
 222                 }
 223
 224                 private function executeShifts(n:NodeSprite):void
 225                 {
 226                         var shift:Number = 0, change:Number = 0;
 227                         for (var c:NodeSprite = n.lastChildNode; c != null; c = c.prevNode)
 228                         {
 229                                 var cp:Params = params(c);
 230                                 cp.prelim += shift;
 231                                 cp.mod += shift;
 232                                 change += cp.change;
 233                                 shift += cp.shift + change;
 234                         }
 235                 }
 236
 237                 private function ancestor(vim:NodeSprite, v:NodeSprite, a:NodeSprite):NodeSprite
 238                 {
 239                         var vimp:Params = params(vim);
 240                         var p:NodeSprite = v.parentNode;
 241                         return (vimp.ancestor.parentNode == p ? vimp.ancestor : a);
 242                 }
 243
 244         private function secondWalk(n:NodeSprite, p:NodeSprite, m:Number, depth:uint, visible:Boolean):void
 245         {
 246                 // set position
 247                 var np:Params = params(n);
 248                 var o:Object = _t.$(n);
 249                 setBreadth(o, p, (visible ? np.prelim : 0) + m);
 250                 setDepth(o, p, _depths[depth]);
 251                 setVisibility(n, o, visible);
 252
 253                 // recurse
 254                 var v:Boolean = n.expanded ? visible : false;
 255                 var b:Number = m + (n.expanded ? np.mod : np.prelim)
 256                 if (v) depth += 1;
 257                 for (var c:NodeSprite = n.firstChildNode; c!=null; c=c.nextNode)
 258                 {
 259                         secondWalk(c, n, b, depth, v);
 260                 }
 261                 np.clear();
 262         }
 263
 264                 private function setBreadth(n:Object, p:NodeSprite, b:Number):void
 265                 {
 266                         switch (_orient) {
 267                                 case Orientation.LEFT_TO_RIGHT:
 268                                 case Orientation.RIGHT_TO_LEFT:
 269                                         n.y = _ay + b;
 270                                         break;
 271                                 case Orientation.TOP_TO_BOTTOM:
 272                                 case Orientation.BOTTOM_TO_TOP:
 273                                         n.x = _ax + b;
 274                                         break;
 275                                 default:
 276                                         throw new Error("Unrecognized orientation value");
 277                         }
 278                 }
 279
 280                 private function setDepth(n:Object, p:NodeSprite, d:Number):void
 281                 {
 282                         switch (_orient) {
 283                                 case Orientation.LEFT_TO_RIGHT:
 284                                         n.x = _ax + d;
 285                                         break;
 286                                 case Orientation.RIGHT_TO_LEFT:
 287                                         n.x = _ax - d;
 288                                         break;
 289                                 case Orientation.TOP_TO_BOTTOM:
 290                                         n.y = _ay + d;
 291                                         break;
 292                                 case Orientation.BOTTOM_TO_TOP:
 293                                         n.y = _ax - d;
 294                                         break;
 295                                 default:
 296                                         throw new Error("Unrecognized orientation value");
 297                         }
 298                 }
 299
 300                 private function setVisibility(n:NodeSprite, o:Object, visible:Boolean):void
 301                 {
 302                 o.alpha = visible ? 1.0 : 0.0;
 303                 o.mouseEnabled = visible;
 304                 if (n.parentEdge != null) {
 305                         o = _t.$(n.parentEdge);
 306                         o.alpha = visible ? 1.0 : 0.0;
 307                         o.mouseEnabled = visible;
 308                 }
 309
 310                 }
 311
 312                 private function spacing(l:NodeSprite, r:NodeSprite, siblings:Boolean):Number
 313                 {
 314                         var w:Boolean = Orientation.isVertical(_orient);
 315                         return (siblings ? _bspace : _tspace) + 0.5 *
 316                                         (w ? l.width + r.width : l.height + r.height)
 317         }
 318
 319         private function updateDepths(depth:uint, item:NodeSprite):void
 320         {
 321                 var v:Boolean = Orientation.isVertical(_orient);
 322                 var d:Number = v ? item.height : item.width;
 323
 324                         // resize if needed
 325                         if (depth >= _depths.length) {
 326                         _depths = Arrays.copy(_depths, new Array(int(1.5*depth)));
 327                         for (var i:int=depth; i<_depths.length; ++i) _depths[i] = 0;
 328                         }
 329
 330                 _depths[depth] = Math.max(_depths[depth], d);
 331                 _maxDepth = Math.max(_maxDepth, depth);
 332         }
 333
 334         private function determineDepths():void
 335         {
 336                 for (var i:uint=1; i<_maxDepth; ++i)
 337                 _depths[i] += _depths[i-1] + _dspace;
 338         }
 339
 340                 // -- Parameter Access ------------------------------------------------
 341
 342                 private function params(n:NodeSprite):Params
 343                 {
 344                         var p:Params = n.props[PARAMS] as Params;
 345                         if (p == null) {
 346                                 p = new Params();
 347                                 n.props[PARAMS] = p;
 348                         }
 349                         if (p.number == -2) { p.init(n); }
 350                         return p;
 351         }
 352
 353         } // end of class NodeLinkTreeLayout
 354
 355 }
 356
 357
 358 import flare.vis.data.NodeSprite;
 359
 360 class Params {
 361         public var prelim:Number = 0;
 362         public var mod:Number = 0;
 363         public var shift:Number = 0;
 364         public var change:Number = 0;
 365         public var number:int = -2;
 366         public var ancestor:NodeSprite = null;
 367         public var thread:NodeSprite = null;
 368
 369     public function init(item:NodeSprite):void
 370     {
 371         ancestor = item;
 372         number = -1;
 373     }
 374
 375         public function clear():void
 376         {
 377                 number = -2;
 378                 prelim = mod = shift = change = 0;
 379                 ancestor = thread = null;
 380         }
 381 } // end of class Params