Mercurial > projects > dwt-addons

annotate dwtx/draw2d/graph/NestingTree.d @ 115:ae94c50641a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix compile error
author Frank Benoit <benoit@tionex.de>
date Fri, 08 Aug 2008 11:26:13 +0200
parents 95307ad235d9
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
98
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
1 /*******************************************************************************
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
2 * Copyright (c) 2005 IBM Corporation and others.
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
3 * All rights reserved. This program and the accompanying materials
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
4 * are made available under the terms of the Eclipse Public License v1.0
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
5 * which accompanies this distribution, and is available at
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
6 * http://www.eclipse.org/legal/epl-v10.html
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
7 *
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
8 * Contributors:
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
9 * IBM Corporation - initial API and implementation
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
10 * Port to the D programming language:
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
11 * Frank Benoit <benoit@tionex.de>
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
12 *******************************************************************************/
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
13 module dwtx.draw2d.graph.NestingTree;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
14
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
15 import dwt.dwthelper.utils;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
16 import dwtx.dwtxhelper.Collection;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
17 import dwtx.draw2d.graph.Node;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
18 import dwtx.draw2d.graph.Rank;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
19 import dwtx.draw2d.graph.Subgraph;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
20
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
21 class NestingTree {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
22
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
23 List contents;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
24 bool isLeaf = true;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
25 int size;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
26 double sortValue;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
27 Node subgraph;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
28
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
29 public this(){
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
30 contents = new ArrayList();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
31 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
32 private static void addToNestingTree(Map map, Node child) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
33 Subgraph subgraph = child.getParent();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
34 NestingTree parent = cast(NestingTree)map.get(subgraph);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
35 if (parent is null) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
36 parent = new NestingTree();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
37 parent.subgraph = subgraph;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
38 map.put(subgraph, parent);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
39 if (subgraph !is null)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
40 addToNestingTree(map, parent);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
41 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
42 parent.contents.add(child);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
43 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
44
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
45 private static void addToNestingTree(Map map, NestingTree branch) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
46 Subgraph subgraph = branch.subgraph.getParent();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
47 NestingTree parent = cast(NestingTree)map.get(subgraph);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
48 if (parent is null) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
49 parent = new NestingTree();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
50 parent.subgraph = subgraph;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
51 map.put(subgraph, parent);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
52 if (subgraph !is null)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
53 addToNestingTree(map, parent);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
54 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
55 parent.contents.add(branch);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
56 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
57
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
58 static NestingTree buildNestingTreeForRank(Rank rank) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
59 Map nestingMap = new HashMap();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
60
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
61 for (int j = 0; j < rank.count(); j++) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
62 Node node = rank.getNode(j);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
63 addToNestingTree(nestingMap, node);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
64 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
65
115
ae94c50641a0 Fix compile error
Frank Benoit <benoit@tionex.de>
parents: 98
diff changeset
66 return cast(NestingTree)nestingMap.get(cast(Object)null);
98
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
67 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
68
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
69 void calculateSortValues() {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
70 int total = 0;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
71 for (int i = 0; i < contents.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
72 Object o = contents.get(i);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
73 if ( auto e = cast(NestingTree)o ) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
74 isLeaf = false;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
75 e.calculateSortValues();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
76 total += cast(int)(e.sortValue * e.size);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
77 size += e.size;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
78 } else {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
79 Node n = cast(Node)o;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
80 n.sortValue = n.index;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
81 total += n.index;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
82 size++;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
83 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
84 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
85 sortValue = cast(double)total / size;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
86 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
87
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
88 void getSortValueFromSubgraph() {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
89 if (subgraph !is null)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
90 sortValue = subgraph.sortValue;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
91 for (int i = 0; i < contents.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
92 Object o = contents.get(i);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
93 if (auto nt = cast(NestingTree)o )
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
94 nt.getSortValueFromSubgraph();
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
95 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
96 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
97
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
98 void recursiveSort(bool sortLeaves) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
99 if (isLeaf && !sortLeaves)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
100 return;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
101 bool change = false;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
102 //Use modified bubble sort for almost-sorted lists.
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
103 do {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
104 change = false;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
105 for (int i = 0; i < contents.size() - 1; i++)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
106 change |= swap(i);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
107 if (!change)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
108 break;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
109 change = false;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
110 for (int i = contents.size() - 2; i >= 0; i--)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
111 change |= swap(i);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
112 } while (change);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
113 for (int i = 0; i < contents.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
114 Object o = contents.get(i);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
115 if (auto nt = cast(NestingTree)o )
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
116 nt.recursiveSort(sortLeaves);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
117 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
118 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
119
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
120 void repopulateRank(Rank r) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
121 for (int i = 0; i < contents.size(); i++) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
122 Object o = contents.get(i);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
123 if (null !is cast(Node)o )
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
124 r.add(o);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
125 else
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
126 (cast(NestingTree)o).repopulateRank(r);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
127 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
128 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
129
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
130
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
131 bool swap(int index) {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
132 Object left = contents.get(index);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
133 Object right = contents.get(index + 1);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
134 double iL = (null !is cast(Node)left )
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
135 ? (cast(Node)left).sortValue
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
136 : (cast(NestingTree)left).sortValue;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
137 double iR = (null !is cast(Node)right )
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
138 ? (cast(Node)right).sortValue
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
139 : (cast(NestingTree)right).sortValue;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
140 if (iL <= iR)
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
141 return false;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
142 contents.set(index, right);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
143 contents.set(index + 1, left);
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
144 return true;
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
145 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
146
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
147 public String toString() {
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
148 if( subgraph )
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
149 return "Nesting:" ~ subgraph.toString; //$NON-NLS-1$
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
150 return "Nesting: null"; //$NON-NLS-1$
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
151 }
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
152
95307ad235d9 Added Draw2d code, still work in progress
Frank Benoit <benoit@tionex.de>
parents:
diff changeset
153 }