Changeset 1927


Ignore:
Timestamp:
Sep 19, 2010, 5:16:51 AM (11 years ago)
Author:
matkovic
Message:

-added PowerCollection library
-added QuadTree
-improved path finding performance

Location:
trunk/CrypPlugins/WorkspaceManager
Files:
20 added
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/WorkspaceManager/View/Container/PluginContainerView.xaml.cs

    r1925 r1927  
    4747        private List<UIElement> optionList = new List<UIElement>();
    4848        private int optionPointer = 0;
    49 
    5049        #endregion
    5150
     
    5655            get
    5756            {
    58                 return new Point[] {
    59                 new Point((this.RenderTransform as TranslateTransform).X-1 ,(this.RenderTransform as TranslateTransform).Y-1),
    60                 //new Point((this.RenderTransform as TranslateTransform).X + (this.ActualWidth / 2),(this.RenderTransform as TranslateTransform).Y-1),
    61                 //new Point((this.RenderTransform as TranslateTransform).X-1,(this.RenderTransform as TranslateTransform).Y + (this.ActualHeight / 2)),
    62                 new Point((this.RenderTransform as TranslateTransform).X-1,(this.RenderTransform as TranslateTransform).Y + this.ActualHeight+1),
    63                 new Point((this.RenderTransform as TranslateTransform).X+1 + this.ActualWidth,(this.RenderTransform as TranslateTransform).Y+1),
    64                 //new Point((this.RenderTransform as TranslateTransform).X + (this.ActualWidth / 2), (this.RenderTransform as TranslateTransform).Y + this.ActualHeight+1),
    65                 //new Point((this.RenderTransform as TranslateTransform).X + this.ActualWidth+1, (this.RenderTransform as TranslateTransform).Y + (this.ActualHeight / 2)),
    66                 new Point((this.RenderTransform as TranslateTransform).X + this.ActualWidth+1, (this.RenderTransform as TranslateTransform).Y + this.ActualHeight+1)};
     57                return  new Point[] {
     58                        new Point((this.RenderTransform as TranslateTransform).X-1 ,(this.RenderTransform as TranslateTransform).Y-1),
     59                        //new Point((this.RenderTransform as TranslateTransform).X + (this.ActualWidth / 2),(this.RenderTransform as TranslateTransform).Y-1),
     60                        //new Point((this.RenderTransform as TranslateTransform).X-1,(this.RenderTransform as TranslateTransform).Y + (this.ActualHeight / 2)),
     61                        new Point((this.RenderTransform as TranslateTransform).X-1,(this.RenderTransform as TranslateTransform).Y + this.ActualHeight+1),
     62                        new Point((this.RenderTransform as TranslateTransform).X+1 + this.ActualWidth,(this.RenderTransform as TranslateTransform).Y+1),
     63                        //new Point((this.RenderTransform as TranslateTransform).X + (this.ActualWidth / 2), (this.RenderTransform as TranslateTransform).Y + this.ActualHeight+1),
     64                        //new Point((this.RenderTransform as TranslateTransform).X + this.ActualWidth+1, (this.RenderTransform as TranslateTransform).Y + (this.ActualHeight / 2)),
     65                        new Point((this.RenderTransform as TranslateTransform).X + this.ActualWidth+1, (this.RenderTransform as TranslateTransform).Y + this.ActualHeight+1)};
    6766            }
    6867        }
     
    657656            Model.Height = PluginBase.ActualHeight;
    658657            Model.Width = PluginBase.ActualWidth;
     658           
     659     
    659660        }
    660661
  • trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/CryptoLineView.cs

    r1926 r1927  
    286286
    287287     
    288         private bool isConnectionPossible(Point p1, Point p2)
     288        private bool isConnectionPossible(Point p1, Point p2, QuadTreeLib.QuadTree<FakeNode> quadTree)
    289289        {
    290290            if (p1.X != p2.X && p1.Y != p2.Y)
    291291                throw new ArgumentException("only 90° allowed");
    292292
     293            System.Drawing.RectangleF queryRect;
    293294            if (p1.Y != p2.Y)
    294295            {
     
    296297                Point down = p2.Y < p1.Y?p1 : p2;
    297298
    298                 Panel parent = (Parent as Panel);
    299                 foreach (var element in parent.Children)
    300                 {
    301                     PluginContainerView plug1 = element as PluginContainerView;
    302                     if (plug1 == null)
    303                         continue;
    304                     Point pos = new Point((plug1.RenderTransform as TranslateTransform).X, (plug1.RenderTransform as TranslateTransform).Y);
    305 
    306                     if (!isBetween(pos.X, pos.X + plug1.ActualWidth, up.X))
    307                         continue;
    308 
    309                     // case 1: one point is inside the plugin
    310                     if (isBetween(pos.Y, pos.Y + plug1.ActualHeight, up.Y) ||
    311                         isBetween(pos.Y, pos.Y + plug1.ActualHeight, down.Y))
    312                     {
    313                         return false;
    314                     }
    315 
    316                     // case 2: goes through
    317                     if (pos.Y > up.Y && pos.Y + plug1.ActualHeight < down.Y)
    318                     {
    319                         return false;
    320                     }
    321                 }
     299                queryRect = new System.Drawing.RectangleF((float)up.X, (float)up.Y, 1, (float)(down.Y - up.Y));
    322300            }
    323301            else
    324302            {
    325303                Point left = p2.X < p1.X ? p2 : p1;
    326                 Point right = p2.X < p1.X ? p1 : p2;
    327 
    328                 Panel parent = (Parent as Panel);
    329                 foreach (var element in parent.Children)
    330                 {
    331                     PluginContainerView plug1 = element as PluginContainerView;
    332                     if (plug1 == null)
    333                         continue;
    334                     Point pos = new Point((plug1.RenderTransform as TranslateTransform).X, (plug1.RenderTransform as TranslateTransform).Y);
    335 
    336                     if (!isBetween(pos.Y, pos.Y + plug1.ActualHeight, left.Y))
    337                         continue;
    338 
    339                     // case 1: one point is inside the plugin
    340                     if(isBetween(pos.X, pos.X + plug1.ActualWidth, left.X) ||
    341                         isBetween(pos.X, pos.X + plug1.ActualWidth, right.X))
    342                     {
    343                         return false;
    344                     }
    345 
    346                     // case 2: goes through
    347                     if(pos.X > left.X && pos.X + plug1.ActualWidth < right.X)
    348                     {
    349                         return false;
    350                     }
    351                 }
    352             }
    353 
    354             return true;
     304                Point right = p2.X < p1.X ? p1 : p2;
     305
     306                queryRect = new System.Drawing.RectangleF((float)left.X, (float)left.Y, (float)(right.X-left.X), 1);
     307            }
     308
     309            return !quadTree.QueryAny(queryRect);
    355310        }
    356311
     
    380335        }
    381336
    382         private bool performOrthogonalPointConnection(Node n1, Point p2, Node n3, List<Node> nodeList)
    383         {
    384             if (isConnectionPossible(n1.Point, p2) && isConnectionPossible(p2, n3.Point))
     337        private bool performOrthogonalPointConnection(Node n1, Point p2, Node n3, List<Node> nodeList, QuadTreeLib.QuadTree<FakeNode> quadTree)
     338        {
     339            if (isConnectionPossible(n1.Point, p2, quadTree) && isConnectionPossible(p2, n3.Point, quadTree))
    385340            {
    386341                Node n2 = new Node() { Point = p2 };
     
    398353        }
    399354
    400         private void performOrthogonalPointConnection(Node p1, Node p2)
    401         {
    402             if (isConnectionPossible(p1.Point, p2.Point))
     355        private void performOrthogonalPointConnection(Node p1, Node p2, QuadTreeLib.QuadTree<FakeNode> quadTree)
     356        {
     357            if (isConnectionPossible(p1.Point, p2.Point, quadTree))
    403358            {
    404359                p1.Vertices.Add(p2);
     
    406361            }
    407362        }
    408 
     363        internal class FakeNode : QuadTreeLib.IHasRect
     364        {
     365            public System.Drawing.RectangleF Rectangle { get; set; }
     366        }
    409367        private void makeOrthogonalPoints()
    410368        {
     
    418376            nodeList.Add(endNode);
    419377
     378            QuadTreeLib.QuadTree<FakeNode> quadTree = new QuadTreeLib.QuadTree<FakeNode>(new System.Drawing.RectangleF(0,0,(float)parent.ActualWidth,(float) parent.ActualHeight));
     379
    420380            foreach (var element in parent.Children)
    421381            {
     
    427387                        nodeList.Add(new Node() { Point = routPoint });
    428388                    }
     389                    quadTree.Insert(new FakeNode() { Rectangle = new System.Drawing.RectangleF((float)(p1.RenderTransform as TranslateTransform).X,
     390                                                                                                (float)(p1.RenderTransform as TranslateTransform).Y,
     391                                                                                                (float)p1.ActualWidth,
     392                                                                                                (float)p1.ActualHeight)});
    429393                }
    430394            }
     
    466430                        p1.Point.Y == p2.Point.Y)
    467431                    {
    468                         performOrthogonalPointConnection(p1, p2);
     432                        performOrthogonalPointConnection(p1, p2, quadTree);
    469433                    }
    470434                    else
     
    472436                        Point help = new Point(p1.Point.X, p2.Point.Y);
    473437
    474                         if (!performOrthogonalPointConnection(p1, help, p2, nodeList))
     438                        if (!performOrthogonalPointConnection(p1, help, p2, nodeList, quadTree ))
    475439                        {
    476440                            help = new Point(p2.Point.X, p1.Point.Y);
    477                             if (!performOrthogonalPointConnection(p1, help, p2, nodeList))
     441                            if (!performOrthogonalPointConnection(p1, help, p2, nodeList, quadTree))
    478442                            {
    479443                                // optional todo: double edge helping routes
  • trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/StackFrameDijkstra/Dijkstra.cs

    r1923 r1927  
    33using System.Linq;
    44using System.Text;
     5using Wintellect.PowerCollections;
    56
    67namespace WorkspaceManager.View.VisualComponents.StackFrameDijkstra
    78{
    8 public class Dijkstra<T > : AbstractPathFinder<T> where T : Node<T> {
     9public class Dijkstra<T> where T : Node<T> {
    910
    1011    private class State : NodeState<T>, IComparable<State> {
    1112
    12         public double dist {get;set;}
     13        public double Dist {get;set;}
    1314
    1415        public State(T node, State parent, double dist) : base(node, parent) {
    15             this.dist = dist;
     16            this.Dist = dist;
    1617        }
    1718
    1819        public int CompareTo(State other) {
    19             return (int)(dist - other.dist);
     20            return Dist.CompareTo(other.Dist);
    2021        }
    2122
    2223    }
    23 
     24   
    2425    public LinkedList<T> findPath(IEnumerable<T> graph, T start, T goal) {
    25         canceled = false;
     26   
    2627        Dictionary<T, State> states = new Dictionary<T, State>();
    27         HashSet<T> Q = new HashSet<T>(graph);
     28        OrderedSet<State> unvisitedNodes = new OrderedSet<State>((a, b) => a.CompareTo(b));
     29        //BinaryQueue<State, double> unvisitedNodes = new BinaryQueue<State, double>(m => m.Dist, (a,b) => a.CompareTo(b));
    2830
    2931        foreach(T n in graph) {
    30             states.Add(n, new State(n, null, Double.PositiveInfinity));
     32            var state = new State(n, null, Double.PositiveInfinity);
     33            if(n.Equals(start))
     34            {
     35                state.Dist = 0;
     36            }
     37            states.Add(n, state);
     38            unvisitedNodes.Add(state);
    3139        }
    3240
    33         states[start].dist = 0;
    34         /*
    35         Predicate<Map.Entry<T, State>> notVisited = new Predicate<Map.Entry<T, State>>() {
     41        while (unvisitedNodes.Count!=0 ) {
     42            var visitingNode = unvisitedNodes.RemoveFirst();
    3643
    37             public boolean apply(Entry<T, State> t) {
    38                 return Q.contains(t.getKey());
    39             }
    40 
    41         };
    42         Ordering<Map.Entry<T, State>> orderByEntryValue = Utilities.orderByEntryValue();
    43         */
    44         while (!(Q.Count==0 || canceled)) {
    45             //Collection<Map.Entry<T, State>> inQ = Collections2.filter(states.entrySet(), notVisited);
    46             var inQ = states.Where(m => Q.Contains(m.Key));
    47             //TODO prefer in-place sort?
    48             var uEntry = inQ.OrderBy( (a) => a.Value.dist).First();
    49 
    50             if (uEntry.Value.dist == Double.PositiveInfinity) {
     44            if (visitingNode.Dist == Double.PositiveInfinity) {
    5145                break;
    5246            }
    5347
    54             T u = uEntry.Key;
    55             State state = uEntry.Value;
    5648           
    57             Q.Remove(u);
    58             if (goal.Equals(u)) {
    59                 return state.makePath();
     49            if (goal.Equals(visitingNode.Node)) {
     50                return visitingNode.makePath();
    6051            }
    6152
    62             foreach (T v in u.neighbors()) {
    63                 double alt = state.dist + u.traverseCost(v);
     53            foreach (T v in visitingNode.Node.neighbors()) {
     54                double altPathCost = visitingNode.Dist + visitingNode.Node.traverseCost(v);
    6455                State vState = states[v];
    65                 if (alt < vState.dist) {
    66                     vState.dist = alt;
    67                     vState.previous = state;
     56                if (altPathCost < vState.Dist) {
     57                    unvisitedNodes.Remove(vState);
     58                    vState.Dist = altPathCost;
     59                    vState.previous = visitingNode;
     60                    unvisitedNodes.Add(vState);
    6861                }
    6962            }
     
    7265        return null;
    7366    }
    74 
    7567}
    7668
  • trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/StackFrameDijkstra/NodeState.cs

    r1923 r1927  
    88    class NodeState<T> where T:Node<T> {
    99
    10         readonly T node;
     10        public readonly T Node;
    1111        public NodeState<T> previous{get;set;}
    1212
    1313        public NodeState(T node, NodeState<T> previous) {
    14             this.node = node;
     14            this.Node = node;
    1515            this.previous = previous;
    1616        }
     
    2121            NodeState<T> s = this;
    2222            while (s != null) {
    23                 result.AddFirst(s.node);
     23                result.AddFirst(s.Node);
    2424                s = s.previous;
    2525            }
  • trunk/CrypPlugins/WorkspaceManager/WorkspaceManager.csproj

    r1923 r1927  
    145145    </Compile>
    146146    <Compile Include="View\VisualComponents\CryptoLineView\IntersectPoint.cs" />
    147     <Compile Include="View\VisualComponents\CryptoLineView\StackFrameDijkstra\AbstractPathFinder.cs" />
     147    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Algorithms.cs" />
     148    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Bag.cs">
     149      <SubType>Code</SubType>
     150    </Compile>
     151    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\CollectionBase.cs" />
     152    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Comparers.cs" />
     153    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Hash.cs" />
     154    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\ListBase.cs" />
     155    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\OrderedSet.cs" />
     156    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Pair.cs">
     157      <SubType>Code</SubType>
     158    </Compile>
     159    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\ReadOnlyCollectionBase.cs">
     160      <SubType>Code</SubType>
     161    </Compile>
     162    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\ReadOnlyListBase.cs">
     163      <SubType>Code</SubType>
     164    </Compile>
     165    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\RedBlack.cs" />
     166    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Set.cs" />
     167    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Strings.cs" />
     168    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Triple.cs" />
     169    <Compile Include="View\VisualComponents\CryptoLineView\PowerCollections\Util.cs" />
     170    <Compile Include="View\VisualComponents\CryptoLineView\QuadTree\IHasRect.cs" />
     171    <Compile Include="View\VisualComponents\CryptoLineView\QuadTree\QuadTree.cs" />
     172    <Compile Include="View\VisualComponents\CryptoLineView\QuadTree\QuadTreeNode.cs" />
    148173    <Compile Include="View\VisualComponents\CryptoLineView\StackFrameDijkstra\Dijkstra.cs" />
    149174    <Compile Include="View\VisualComponents\CryptoLineView\StackFrameDijkstra\Node.cs" />
Note: See TracChangeset for help on using the changeset viewer.