Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/22/10 00:44:01 (14 years ago)
Author:
swagner
Message:

Sorted usings and removed unused usings in entire solution (#1094)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.ExtLibs/HeuristicLab.Netron/3.0.2672.12446/Netron.Diagramming.Core-3.0.2672.12446/Layout/StandardTreeLayout.cs

    r3776 r4068  
    11using System;
    2 using System.Diagnostics;
     2using System.Collections.Generic;
     3using System.ComponentModel;
     4using System.Drawing;
    35using Netron.Diagramming.Core.Analysis;
    4 using System.Drawing;
    5 using System.Collections.Generic;
    6 using System.Text;
    7 using System.Windows.Forms;
    8 using System.ComponentModel;
    9 namespace Netron.Diagramming.Core
    10 {
    11     /// <summary>
    12     /// <para>TreeLayout that computes a tidy layout of a node-link tree
    13     ///  diagram. This algorithm lays out a rooted tree such that each
    14     ///  depth level of the tree is on a shared line. The orientation of the
    15     ///  tree can be set such that the tree goes left-to-right (default),
    16     ///  right-to-left, top-to-bottom, or bottom-to-top.</para>
    17     /// 
    18     ///  <para>The algorithm used is that of Christoph Buchheim, Michael Jünger,
    19     ///  and Sebastian Leipert from their research paper
    20     ///  <a href="http://citeseer.ist.psu.edu/buchheim02improving.html">
    21     ///  Improving Walker's Algorithm to Run in Linear Time</a>, Graph Drawing 2002.
    22     ///  This algorithm corrects performance issues in Walker's algorithm, which
    23     ///  generalizes Reingold and Tilford's method for tidy drawings of trees to
    24     ///  support trees with an arbitrary number of children at any given node.</para>
    25     /// </summary>
    26     class StandardTreeLayout : TreeLayoutBase
    27     {
    28 
    29        
    30 
    31         #region Fields
    32         BackgroundWorker worker;
    33         private static TreeOrientation mOrientation = TreeOrientation.TopBottom;  // the orientation of the tree
    34         private static float mBreadth = 50F;   // the spacing between sibling nodes
    35         private static float mSubTreeSpacing = 50F;  // the spacing between subtrees
    36         private static float mDepth = 50F;  // the spacing between depth levels
    37         private float m_offset = 50;  // pixel offset for root node position
    38         private PointF m_anchor;
    39         private PointF m_tmpa;
    40         private float[] m_depths = new float[10];
    41         private int mMaxDepth = 0;
    42         private Dictionary<string, Params> Pars;
    43         private float m_ax, m_ay; // for holding anchor co-ordinates
    44         #endregion
    45 
    46         #region Properties
    47         /// <summary>
    48         /// Gets or sets the orientation of the tree.
    49         /// </summary>
    50         /// <value>The orientation.</value>
    51         public static TreeOrientation Orientation
    52         {
    53             get
     6namespace Netron.Diagramming.Core {
     7  /// <summary>
     8  /// <para>TreeLayout that computes a tidy layout of a node-link tree
     9  ///  diagram. This algorithm lays out a rooted tree such that each
     10  ///  depth level of the tree is on a shared line. The orientation of the
     11  ///  tree can be set such that the tree goes left-to-right (default),
     12  ///  right-to-left, top-to-bottom, or bottom-to-top.</para>
     13  /// 
     14  ///  <para>The algorithm used is that of Christoph Buchheim, Michael Jünger,
     15  ///  and Sebastian Leipert from their research paper
     16  ///  <a href="http://citeseer.ist.psu.edu/buchheim02improving.html">
     17  ///  Improving Walker's Algorithm to Run in Linear Time</a>, Graph Drawing 2002.
     18  ///  This algorithm corrects performance issues in Walker's algorithm, which
     19  ///  generalizes Reingold and Tilford's method for tidy drawings of trees to
     20  ///  support trees with an arbitrary number of children at any given node.</para>
     21  /// </summary>
     22  class StandardTreeLayout : TreeLayoutBase {
     23
     24
     25
     26    #region Fields
     27    BackgroundWorker worker;
     28    private static TreeOrientation mOrientation = TreeOrientation.TopBottom;  // the orientation of the tree
     29    private static float mBreadth = 50F;   // the spacing between sibling nodes
     30    private static float mSubTreeSpacing = 50F;  // the spacing between subtrees
     31    private static float mDepth = 50F;  // the spacing between depth levels
     32    private float m_offset = 50;  // pixel offset for root node position
     33    private PointF m_anchor;
     34    private PointF m_tmpa;
     35    private float[] m_depths = new float[10];
     36    private int mMaxDepth = 0;
     37    private Dictionary<string, Params> Pars;
     38    private float m_ax, m_ay; // for holding anchor co-ordinates
     39    #endregion
     40
     41    #region Properties
     42    /// <summary>
     43    /// Gets or sets the orientation of the tree.
     44    /// </summary>
     45    /// <value>The orientation.</value>
     46    public static TreeOrientation Orientation {
     47      get {
     48        return mOrientation;
     49      }
     50      set {
     51        mOrientation = value;
     52      }
     53    }
     54    /// <summary>
     55    /// Gets or sets the depth spacing.
     56    /// </summary>
     57    /// <value>The depth spacing.</value>
     58    public static float DepthSpacing {
     59      get { return mDepth; }
     60      set { mDepth = value; }
     61    }
     62
     63    /// <summary>
     64    /// Gets or sets the breadth spacing.
     65    /// </summary>
     66    /// <value>The breadth spacing.</value>
     67    public static float BreadthSpacing {
     68      get { return mBreadth; }
     69      set { mBreadth = value; }
     70    }
     71    /// <summary>
     72    /// Gets or sets the spacing between subtrees.
     73    /// </summary>
     74    /// <value>The sub tree spacing.</value>
     75    public static float SubTreeSpacing {
     76      get { return mSubTreeSpacing; }
     77      set { mSubTreeSpacing = value; }
     78
     79    }
     80
     81    public float RootOffset {
     82      get { return m_offset; }
     83      set { m_offset = value; }
     84    }
     85
     86    #endregion
     87
     88    #region Constructor
     89    public StandardTreeLayout(IController controller)
     90      : base("Standard TreeLayout", controller) {
     91
     92      Orientation = TreeOrientation.LeftRight;
     93
     94    }
     95    #endregion
     96
     97    #region Methods
     98
     99    public override void Run() {
     100      Run(2000);
     101    }
     102    public override void Run(int time) {
     103      if (worker != null && worker.IsBusy)
     104        worker.CancelAsync();
     105      worker = new BackgroundWorker();
     106      worker.WorkerSupportsCancellation = true;
     107      worker.DoWork += new DoWorkEventHandler(worker_DoWork);
     108      worker.RunWorkerAsync(time);
     109    }
     110
     111    public override void Stop() {
     112      if (worker != null && worker.IsBusy)
     113        worker.CancelAsync();
     114    }
     115
     116    private void worker_DoWork(object sender, DoWorkEventArgs e) {
     117      this.Controller.View.Suspend();
     118      Init();
     119      Layout();
     120      this.Controller.View.Resume();
     121    }
     122    /// <summary>
     123    /// Runs a single step.
     124    /// </summary>
     125    private void RunStep() {
     126
     127    }
     128    private bool Init() {
     129
     130      this.Graph = this.Model as IGraph;
     131
     132      if (Graph == null)
     133        throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'");
     134
     135      m_depths = new float[10];
     136      this.LayoutRoot = this.Controller.Model.LayoutRoot;//could be null if not set in the GUI
     137      Graph.ClearSpanningTree();
     138      Graph.MakeSpanningTree(LayoutRoot as INode);
     139
     140      //Trace.WriteLine((LayoutRoot as INode).ChildCount);
     141
     142      if (Graph.SpanningTree == null)
     143        throw new InconsistencyException("The spanning tree is not set (se the root of the tree layout first)");
     144
     145
     146
     147
     148
     149      Pars = new Dictionary<string, Params>();
     150      if (Graph.Nodes.Count == 0)
     151        return false;
     152      if (Graph.Edges.Count == 0) //this layout is base on embedded springs in the connections
     153        return false;
     154
     155
     156      Params par;
     157
     158      foreach (INode node in Graph.Nodes) {
     159        par = new Params();
     160        par.init(node);
     161        Pars.Add(node.Uid.ToString(), par);
     162      }
     163      return true;
     164    }
     165    public PointF LayoutAnchor {
     166      get {
     167        //if (m_anchor != null)
     168        //{
     169        //    return m_anchor;
     170        //}
     171
     172        m_tmpa = PointF.Empty;
     173        if (Graph != null) {
     174          Rectangle b = Bounds;
     175
     176          switch (mOrientation) {
     177            case TreeOrientation.LeftRight:
     178              m_tmpa = new PointF(m_offset, b.Height / 2F);
     179              break;
     180            case TreeOrientation.RightLeft:
     181              m_tmpa = new PointF(b.Width - m_offset, b.Height / 2F);
     182              break;
     183            case TreeOrientation.TopBottom:
     184              m_tmpa = new PointF(b.Width / 2F, m_offset);
     185              break;
     186            case TreeOrientation.BottomTop:
     187              m_tmpa = new PointF(b.Width / 2F, b.Height - m_offset);
     188              break;
     189            case TreeOrientation.Center:
     190              m_tmpa = new PointF(b.Width / 2F, b.Height / 2F);
     191              break;
     192            default:
     193              break;
     194          }
     195          //TODO: set the center of the layout here on the view
     196          //d.getInverseTransform().transform(m_tmpa, m_tmpa);
     197        }
     198        return m_tmpa;
     199      }
     200      set {
     201        m_anchor = value;
     202      }
     203    }
     204
     205    /// <summary>
     206    /// Returns the location of halfway the two given nodes
     207    /// </summary>
     208    /// <param name="l"></param>
     209    /// <param name="r"></param>
     210    /// <param name="siblings"></param>
     211    /// <returns></returns>
     212    private double spacing(INode l, INode r, bool siblings) {
     213      bool w = (mOrientation == TreeOrientation.TopBottom || mOrientation == TreeOrientation.BottomTop);
     214      return (siblings ? mBreadth : mSubTreeSpacing) + 0.5 * (w ? l.Rectangle.Width + r.Rectangle.Width : l.Rectangle.Height + r.Rectangle.Height);
     215    }
     216    private void updateDepths(int depth, INode item) {
     217      bool v = (mOrientation == TreeOrientation.TopBottom || mOrientation == TreeOrientation.BottomTop);
     218      double d = (v ? item.Rectangle.Height : item.Rectangle.Width);
     219      if (m_depths.Length <= depth)
     220        Array.Resize<float>(ref m_depths, (int)(3 * depth / 2));
     221      m_depths[depth] = (float)Math.Max(m_depths[depth], d);
     222      mMaxDepth = (int)Math.Max(mMaxDepth, depth);
     223    }
     224
     225    private void determineDepths() {
     226      for (int i = 1; i < mMaxDepth; ++i)
     227        m_depths[i] += m_depths[i - 1] + mDepth;
     228    }
     229
     230    public void Layout() {
     231      m_depths.Initialize();
     232
     233      mMaxDepth = 0;
     234
     235      PointF a = LayoutAnchor;
     236      m_ax = a.X;
     237      m_ay = a.Y;
     238
     239      INode root = LayoutRoot as INode;
     240      Params rp = Pars[root.Uid.ToString()];
     241
     242      // do first pass - compute breadth information, collect depth info
     243      firstWalk(root, 0, 1);
     244
     245      // sum up the depth info
     246      determineDepths();
     247
     248      // do second pass - assign layout positions
     249      secondWalk(root, null, -rp.prelim, 0);
     250    }
     251
     252    private void firstWalk(INode n, int num, int depth) {
     253      //Trace.WriteLine("depthj: " + depth);
     254      Params np = Pars[n.Uid.ToString()];
     255
     256      np.number = num;
     257      updateDepths(depth, n);
     258
     259      bool expanded = n.IsExpanded;
     260      if (n.ChildCount == 0 || !expanded) // is leaf
    54261            {
    55                 return mOrientation;
    56             }
    57             set
    58             {
    59                 mOrientation = value;
    60             }
    61         }
    62         /// <summary>
    63         /// Gets or sets the depth spacing.
    64         /// </summary>
    65         /// <value>The depth spacing.</value>
    66         public static float DepthSpacing
    67         {
    68             get { return mDepth; }
    69             set { mDepth = value; }
    70         }
    71 
    72         /// <summary>
    73         /// Gets or sets the breadth spacing.
    74         /// </summary>
    75         /// <value>The breadth spacing.</value>
    76         public static float BreadthSpacing
    77         {
    78             get { return mBreadth; }
    79             set { mBreadth = value; }
    80         }
    81         /// <summary>
    82         /// Gets or sets the spacing between subtrees.
    83         /// </summary>
    84         /// <value>The sub tree spacing.</value>
    85         public static float SubTreeSpacing
    86         {
    87             get { return mSubTreeSpacing; }
    88             set { mSubTreeSpacing = value; }
    89 
    90         }
    91 
    92         public float RootOffset
    93         {
    94             get { return m_offset; }
    95             set { m_offset = value; }
    96         }
    97 
    98         #endregion
    99 
    100         #region Constructor
    101         public StandardTreeLayout(IController controller)
    102             : base("Standard TreeLayout", controller)
    103         {
    104 
    105           Orientation = TreeOrientation.LeftRight;
    106 
    107         }
    108         #endregion
    109 
    110         #region Methods
    111 
    112         public override void Run()
    113         {
    114             Run(2000);
    115         }
    116         public override void Run(int time)
    117         {
    118             if (worker != null && worker.IsBusy)
    119                 worker.CancelAsync();               
    120             worker = new BackgroundWorker();
    121             worker.WorkerSupportsCancellation = true;
    122             worker.DoWork += new DoWorkEventHandler(worker_DoWork);
    123             worker.RunWorkerAsync(time);
    124         }
    125 
    126         public override void Stop()
    127         {
    128             if (worker != null && worker.IsBusy)
    129                 worker.CancelAsync();
    130         }
    131 
    132         private void worker_DoWork(object sender, DoWorkEventArgs e)
    133         {
    134             this.Controller.View.Suspend();
    135             Init();
    136             Layout();
    137             this.Controller.View.Resume();
    138         }
    139         /// <summary>
    140         /// Runs a single step.
    141         /// </summary>
    142         private void RunStep()
    143         {
    144 
    145         }
    146         private bool Init()
    147         {
    148 
    149             this.Graph = this.Model as IGraph;
    150 
    151             if (Graph == null)
    152                 throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'");
    153 
    154             m_depths = new float[10];
    155             this.LayoutRoot = this.Controller.Model.LayoutRoot;//could be null if not set in the GUI
    156             Graph.ClearSpanningTree();
    157             Graph.MakeSpanningTree(LayoutRoot as INode);
    158 
    159             //Trace.WriteLine((LayoutRoot as INode).ChildCount);
    160 
    161             if (Graph.SpanningTree == null)
    162                 throw new InconsistencyException("The spanning tree is not set (se the root of the tree layout first)");
    163 
    164            
    165            
    166 
    167 
    168             Pars = new Dictionary<string, Params>();
    169             if (Graph.Nodes.Count == 0)
    170                 return false;
    171             if (Graph.Edges.Count == 0) //this layout is base on embedded springs in the connections
    172                 return false;
    173 
    174 
    175             Params par;
    176 
    177             foreach (INode node in Graph.Nodes)
    178             {
    179                 par = new Params();
    180                 par.init(node);
    181                 Pars.Add(node.Uid.ToString(), par);
    182             }
    183             return true;
    184         }
    185         public PointF LayoutAnchor
    186         {
    187             get
    188             {
    189                 //if (m_anchor != null)
    190                 //{
    191                 //    return m_anchor;
    192                 //}
    193 
    194                 m_tmpa = PointF.Empty;
    195                 if (Graph != null)
    196                 {
    197                     Rectangle b = Bounds;
    198 
    199                     switch (mOrientation)
    200                     {
    201                         case TreeOrientation.LeftRight:
    202                             m_tmpa = new PointF(m_offset, b.Height / 2F);
    203                             break;
    204                         case TreeOrientation.RightLeft:
    205                             m_tmpa = new PointF(b.Width - m_offset, b.Height / 2F);
    206                             break;
    207                         case TreeOrientation.TopBottom:
    208                             m_tmpa = new PointF(b.Width / 2F, m_offset);
    209                             break;
    210                         case TreeOrientation.BottomTop:
    211                             m_tmpa = new PointF(b.Width / 2F, b.Height - m_offset);
    212                             break;
    213                         case TreeOrientation.Center:
    214                             m_tmpa = new PointF(b.Width / 2F, b.Height / 2F);
    215                             break;
    216                         default:
    217                             break;
    218                     }
    219                     //TODO: set the center of the layout here on the view
    220                     //d.getInverseTransform().transform(m_tmpa, m_tmpa);
    221                 }
    222                 return m_tmpa;
    223             }
    224             set
    225             {
    226                 m_anchor = value;
    227             }
    228         }
    229 
    230         /// <summary>
    231         /// Returns the location of halfway the two given nodes
    232         /// </summary>
    233         /// <param name="l"></param>
    234         /// <param name="r"></param>
    235         /// <param name="siblings"></param>
    236         /// <returns></returns>
    237         private double spacing(INode l, INode r, bool siblings)
    238         {
    239             bool w = (mOrientation == TreeOrientation.TopBottom || mOrientation == TreeOrientation.BottomTop);
    240             return (siblings ? mBreadth : mSubTreeSpacing) + 0.5 * (w ? l.Rectangle.Width + r.Rectangle.Width : l.Rectangle.Height + r.Rectangle.Height);
    241         }
    242         private void updateDepths(int depth, INode item)
    243         {
    244             bool v = (mOrientation == TreeOrientation.TopBottom || mOrientation == TreeOrientation.BottomTop);
    245             double d = (v ? item.Rectangle.Height : item.Rectangle.Width);
    246             if (m_depths.Length <= depth)
    247                 Array.Resize<float>(ref m_depths, (int)(3 * depth / 2));
    248             m_depths[depth] = (float)Math.Max(m_depths[depth], d);
    249             mMaxDepth = (int)Math.Max(mMaxDepth, depth);
    250         }
    251 
    252         private void determineDepths()
    253         {
    254             for (int i = 1; i < mMaxDepth; ++i)
    255                 m_depths[i] += m_depths[i - 1] + mDepth;
    256         }
    257 
    258         public void Layout()
    259         {
    260             m_depths.Initialize();
    261 
    262             mMaxDepth = 0;
    263 
    264             PointF a = LayoutAnchor;
    265             m_ax = a.X;
    266             m_ay = a.Y;
    267 
    268             INode root = LayoutRoot as INode;
    269             Params rp = Pars[root.Uid.ToString()];
    270 
    271             // do first pass - compute breadth information, collect depth info
    272             firstWalk(root, 0, 1);
    273 
    274             // sum up the depth info
    275             determineDepths();
    276 
    277             // do second pass - assign layout positions
    278             secondWalk(root, null, -rp.prelim, 0);
    279         }
    280 
    281         private void firstWalk(INode n, int num, int depth)
    282         {
    283             //Trace.WriteLine("depthj: " + depth);
    284             Params np = Pars[n.Uid.ToString()];
    285 
    286             np.number = num;
    287             updateDepths(depth, n);
    288 
    289             bool expanded = n.IsExpanded;
    290             if (n.ChildCount == 0 || !expanded) // is leaf
    291             {
    292                 INode l = (INode)n.PreviousSibling;
    293                 if (l == null)
    294                 {
    295                     np.prelim = 0;
    296                 }
    297                 else
    298                 {
    299                     np.prelim = Pars[l.Uid.ToString()].prelim + spacing(l, n, true);
    300                 }
    301             }
    302             else if (expanded)
    303             {
    304                 INode leftMost = n.FirstChild;
    305                 INode rightMost = n.LastChild;
    306                 INode defaultAncestor = leftMost;
    307                 INode c = leftMost;
    308                 for (int i = 0; c != null; ++i, c = c.NextSibling)
    309                 {
    310                     firstWalk(c, i, depth + 1);
    311                     defaultAncestor = apportion(c, defaultAncestor);
    312                 }
    313 
    314                 executeShifts(n);
    315 
    316                 double midpoint = 0.5 *
    317                     (Pars[leftMost.Uid.ToString()].prelim + Pars[rightMost.Uid.ToString()].prelim);
    318 
    319                 INode left = (INode)n.PreviousSibling;
    320                 if (left != null)
    321                 {
    322                     np.prelim = Pars[left.Uid.ToString()].prelim + spacing(left, n, true);
    323                     np.mod = np.prelim - midpoint;
    324                 }
    325                 else
    326                 {
    327                     np.prelim = midpoint;
    328                 }
    329             }
    330         }
    331         private INode apportion(INode v, INode a)
    332         {
    333             INode w = (INode)v.PreviousSibling;
    334             if (w != null)
    335             {
    336                 INode vip, vim, vop, vom;
    337                 double sip, sim, sop, som;
    338 
    339                 vip = vop = v;
    340                 vim = w;
    341                 vom = (INode)vip.ParentNode.FirstChild;
    342 
    343                 sip = Pars[vip.Uid.ToString()].mod;
    344                 sop = Pars[vop.Uid.ToString()].mod;
    345                 sim = Pars[vim.Uid.ToString()].mod;
    346                 som = Pars[vom.Uid.ToString()].mod;
    347                 Params parms;
    348                 INode nr = nextRight(vim);
    349                 INode nl = nextLeft(vip);
    350                 while (nr != null && nl != null)
    351                 {
    352                     vim = nr;
    353                     vip = nl;
    354                     vom = nextLeft(vom);
    355                     vop = nextRight(vop);
    356                     parms = Pars[vop.Uid.ToString()];
    357                     parms.ancestor = v;
    358                     double shift = (Pars[vim.Uid.ToString()].prelim + sim) -
    359                         (Pars[vip.Uid.ToString()].prelim + sip) + spacing(vim, vip, false);
    360                     if (shift > 0)
    361                     {
    362                         moveSubtree(ancestor(vim, v, a), v, shift);
    363                         sip += shift;
    364                         sop += shift;
    365                     }
    366                     sim += Pars[vim.Uid.ToString()].mod;
    367                     sip += Pars[vip.Uid.ToString()].mod;
    368                     som += Pars[vom.Uid.ToString()].mod;
    369                     sop += Pars[vop.Uid.ToString()].mod;
    370 
    371                     nr = nextRight(vim);
    372                     nl = nextLeft(vip);
    373                 }
    374                 if (nr != null && nextRight(vop) == null)
    375                 {
    376                     Params vopp = Pars[vop.Uid.ToString()];
    377                     vopp.thread = nr;
    378                     vopp.mod += sim - sop;
    379                 }
    380                 if (nl != null && nextLeft(vom) == null)
    381                 {
    382                     Params vomp = Pars[vom.Uid.ToString()];
    383                     vomp.thread = nl;
    384                     vomp.mod += sip - som;
    385                     a = v;
    386                 }
    387             }
    388             return a;
    389         }
    390         private INode nextLeft(INode n)
    391         {
    392             INode c = null;
    393             if (n.IsExpanded) c = n.FirstChild;
    394             return (c != null ? c : Pars[n.Uid.ToString()].thread);
    395         }
    396 
    397         private INode nextRight(INode n)
    398         {
    399             INode c = null;
    400             if (n.IsExpanded) c = n.LastChild;
    401             return (c != null ? c : Pars[n.Uid.ToString()].thread);
    402         }
    403 
    404         private void moveSubtree(INode wm, INode wp, double shift)
    405         {
    406             Params wmp = Pars[wm.Uid.ToString()];
    407             Params wpp = Pars[wp.Uid.ToString()];
    408             double subtrees = wpp.number - wmp.number;
    409             wpp.change -= shift / subtrees;
    410             wpp.shift += shift;
    411             wmp.change += shift / subtrees;
    412             wpp.prelim += shift;
    413             wpp.mod += shift;
    414         }
    415 
    416         private void executeShifts(INode n)
    417         {
    418             double shift = 0, change = 0;
    419             for (INode c = n.LastChild; c != null; c = c.PreviousSibling)
    420             {
    421                 Params cp = Pars[c.Uid.ToString()];
    422                 cp.prelim += shift;
    423                 cp.mod += shift;
    424                 change += cp.change;
    425                 shift += cp.shift + change;
    426             }
    427         }
    428 
    429         private INode ancestor(INode vim, INode v, INode a)
    430         {
    431             INode p = (INode)v.ParentNode;
    432             Params vimp = Pars[vim.Uid.ToString()];
    433             if (vimp.ancestor != null && vimp.ancestor.ParentNode == p)
    434             {
    435                 return vimp.ancestor;
    436             }
    437             else
    438             {
    439                 return a;
    440             }
    441         }
    442 
    443         private void secondWalk(INode n, INode p, double m, int depth)
    444         {
    445             Params np = Pars[n.Uid.ToString()];
    446             setBreadth(n, p, np.prelim + m);
    447             setDepth(n, p, m_depths[depth]);
    448 
    449             if (n.IsExpanded)
    450             {
    451                 depth += 1;
    452                 for (INode c = n.FirstChild; c != null; c = c.NextSibling)
    453                 {
    454                     if (worker.CancellationPending)
    455                         break;
    456                     secondWalk(c, n, m + np.mod, depth);
    457                 }
    458             }
    459 
    460             np.clear();
    461         }
    462 
    463         private void setBreadth(INode n, INode p, double b)
    464         {
    465             switch (mOrientation)
    466             {
    467                 case TreeOrientation.LeftRight:
    468                 case TreeOrientation.RightLeft:
    469                     setY(n, p, m_ay + b);
    470                     break;
    471                 case TreeOrientation.TopBottom:
    472                 case TreeOrientation.BottomTop:
    473                     setX(n, p, m_ax + b);
    474                     break;
    475                 default:
    476                     throw new InconsistencyException();
    477             }
    478         }
    479 
    480         private void setDepth(INode n, INode p, double d)
    481         {
    482             switch (mOrientation)
    483             {
    484                 case TreeOrientation.LeftRight:
    485                     setX(n, p, m_ax + d);
    486                     break;
    487                 case TreeOrientation.RightLeft:
    488                     setX(n, p, m_ax - d);
    489                     break;
    490                 case TreeOrientation.TopBottom:
    491                     setY(n, p, m_ay + d);
    492                     break;
    493                 case TreeOrientation.BottomTop:
    494                     setY(n, p, m_ay - d);
    495                     break;
    496                 default:
    497                     throw new InconsistencyException();
    498             }
    499         }
    500 
    501 
    502         #endregion
    503 
    504         /// <summary>
    505         /// Paramter blob to temporarily keep working data of one node.
    506         /// </summary>
    507         class Params
    508         {
    509             public double prelim;
    510             public double mod;
    511             public double shift;
    512             public double change;
    513             public int number;
    514             public INode ancestor;
    515             public INode thread;
    516 
    517             public void init(INode item)
    518             {
    519                 ancestor = item;
    520                 number = -1;
    521                 ancestor = thread = null;
    522             }
    523 
    524             public void clear()
    525             {
    526                 number = -2;
    527                 prelim = mod = shift = change = 0;
    528                 ancestor = thread = null;
    529             }
    530         }
    531     }
    532 
    533     public enum TreeOrientation
    534     {
    535         LeftRight,
    536         RightLeft,
    537         TopBottom,
    538         BottomTop,
    539         Center
    540     }
     262        INode l = (INode)n.PreviousSibling;
     263        if (l == null) {
     264          np.prelim = 0;
     265        } else {
     266          np.prelim = Pars[l.Uid.ToString()].prelim + spacing(l, n, true);
     267        }
     268      } else if (expanded) {
     269        INode leftMost = n.FirstChild;
     270        INode rightMost = n.LastChild;
     271        INode defaultAncestor = leftMost;
     272        INode c = leftMost;
     273        for (int i = 0; c != null; ++i, c = c.NextSibling) {
     274          firstWalk(c, i, depth + 1);
     275          defaultAncestor = apportion(c, defaultAncestor);
     276        }
     277
     278        executeShifts(n);
     279
     280        double midpoint = 0.5 *
     281            (Pars[leftMost.Uid.ToString()].prelim + Pars[rightMost.Uid.ToString()].prelim);
     282
     283        INode left = (INode)n.PreviousSibling;
     284        if (left != null) {
     285          np.prelim = Pars[left.Uid.ToString()].prelim + spacing(left, n, true);
     286          np.mod = np.prelim - midpoint;
     287        } else {
     288          np.prelim = midpoint;
     289        }
     290      }
     291    }
     292    private INode apportion(INode v, INode a) {
     293      INode w = (INode)v.PreviousSibling;
     294      if (w != null) {
     295        INode vip, vim, vop, vom;
     296        double sip, sim, sop, som;
     297
     298        vip = vop = v;
     299        vim = w;
     300        vom = (INode)vip.ParentNode.FirstChild;
     301
     302        sip = Pars[vip.Uid.ToString()].mod;
     303        sop = Pars[vop.Uid.ToString()].mod;
     304        sim = Pars[vim.Uid.ToString()].mod;
     305        som = Pars[vom.Uid.ToString()].mod;
     306        Params parms;
     307        INode nr = nextRight(vim);
     308        INode nl = nextLeft(vip);
     309        while (nr != null && nl != null) {
     310          vim = nr;
     311          vip = nl;
     312          vom = nextLeft(vom);
     313          vop = nextRight(vop);
     314          parms = Pars[vop.Uid.ToString()];
     315          parms.ancestor = v;
     316          double shift = (Pars[vim.Uid.ToString()].prelim + sim) -
     317              (Pars[vip.Uid.ToString()].prelim + sip) + spacing(vim, vip, false);
     318          if (shift > 0) {
     319            moveSubtree(ancestor(vim, v, a), v, shift);
     320            sip += shift;
     321            sop += shift;
     322          }
     323          sim += Pars[vim.Uid.ToString()].mod;
     324          sip += Pars[vip.Uid.ToString()].mod;
     325          som += Pars[vom.Uid.ToString()].mod;
     326          sop += Pars[vop.Uid.ToString()].mod;
     327
     328          nr = nextRight(vim);
     329          nl = nextLeft(vip);
     330        }
     331        if (nr != null && nextRight(vop) == null) {
     332          Params vopp = Pars[vop.Uid.ToString()];
     333          vopp.thread = nr;
     334          vopp.mod += sim - sop;
     335        }
     336        if (nl != null && nextLeft(vom) == null) {
     337          Params vomp = Pars[vom.Uid.ToString()];
     338          vomp.thread = nl;
     339          vomp.mod += sip - som;
     340          a = v;
     341        }
     342      }
     343      return a;
     344    }
     345    private INode nextLeft(INode n) {
     346      INode c = null;
     347      if (n.IsExpanded) c = n.FirstChild;
     348      return (c != null ? c : Pars[n.Uid.ToString()].thread);
     349    }
     350
     351    private INode nextRight(INode n) {
     352      INode c = null;
     353      if (n.IsExpanded) c = n.LastChild;
     354      return (c != null ? c : Pars[n.Uid.ToString()].thread);
     355    }
     356
     357    private void moveSubtree(INode wm, INode wp, double shift) {
     358      Params wmp = Pars[wm.Uid.ToString()];
     359      Params wpp = Pars[wp.Uid.ToString()];
     360      double subtrees = wpp.number - wmp.number;
     361      wpp.change -= shift / subtrees;
     362      wpp.shift += shift;
     363      wmp.change += shift / subtrees;
     364      wpp.prelim += shift;
     365      wpp.mod += shift;
     366    }
     367
     368    private void executeShifts(INode n) {
     369      double shift = 0, change = 0;
     370      for (INode c = n.LastChild; c != null; c = c.PreviousSibling) {
     371        Params cp = Pars[c.Uid.ToString()];
     372        cp.prelim += shift;
     373        cp.mod += shift;
     374        change += cp.change;
     375        shift += cp.shift + change;
     376      }
     377    }
     378
     379    private INode ancestor(INode vim, INode v, INode a) {
     380      INode p = (INode)v.ParentNode;
     381      Params vimp = Pars[vim.Uid.ToString()];
     382      if (vimp.ancestor != null && vimp.ancestor.ParentNode == p) {
     383        return vimp.ancestor;
     384      } else {
     385        return a;
     386      }
     387    }
     388
     389    private void secondWalk(INode n, INode p, double m, int depth) {
     390      Params np = Pars[n.Uid.ToString()];
     391      setBreadth(n, p, np.prelim + m);
     392      setDepth(n, p, m_depths[depth]);
     393
     394      if (n.IsExpanded) {
     395        depth += 1;
     396        for (INode c = n.FirstChild; c != null; c = c.NextSibling) {
     397          if (worker.CancellationPending)
     398            break;
     399          secondWalk(c, n, m + np.mod, depth);
     400        }
     401      }
     402
     403      np.clear();
     404    }
     405
     406    private void setBreadth(INode n, INode p, double b) {
     407      switch (mOrientation) {
     408        case TreeOrientation.LeftRight:
     409        case TreeOrientation.RightLeft:
     410          setY(n, p, m_ay + b);
     411          break;
     412        case TreeOrientation.TopBottom:
     413        case TreeOrientation.BottomTop:
     414          setX(n, p, m_ax + b);
     415          break;
     416        default:
     417          throw new InconsistencyException();
     418      }
     419    }
     420
     421    private void setDepth(INode n, INode p, double d) {
     422      switch (mOrientation) {
     423        case TreeOrientation.LeftRight:
     424          setX(n, p, m_ax + d);
     425          break;
     426        case TreeOrientation.RightLeft:
     427          setX(n, p, m_ax - d);
     428          break;
     429        case TreeOrientation.TopBottom:
     430          setY(n, p, m_ay + d);
     431          break;
     432        case TreeOrientation.BottomTop:
     433          setY(n, p, m_ay - d);
     434          break;
     435        default:
     436          throw new InconsistencyException();
     437      }
     438    }
     439
     440
     441    #endregion
     442
     443    /// <summary>
     444    /// Paramter blob to temporarily keep working data of one node.
     445    /// </summary>
     446    class Params {
     447      public double prelim;
     448      public double mod;
     449      public double shift;
     450      public double change;
     451      public int number;
     452      public INode ancestor;
     453      public INode thread;
     454
     455      public void init(INode item) {
     456        ancestor = item;
     457        number = -1;
     458        ancestor = thread = null;
     459      }
     460
     461      public void clear() {
     462        number = -2;
     463        prelim = mod = shift = change = 0;
     464        ancestor = thread = null;
     465      }
     466    }
     467  }
     468
     469  public enum TreeOrientation {
     470    LeftRight,
     471    RightLeft,
     472    TopBottom,
     473    BottomTop,
     474    Center
     475  }
    541476}
Note: See TracChangeset for help on using the changeset viewer.