Mercurial > projects > dwt2
view org.eclipse.draw2d/src/org/eclipse/draw2d/graph/NestingTree.d @ 16:dbfb303e8fb0
first complete successful compile (win-only)
author | Frank Benoit <benoit@tionex.de> |
---|---|
date | Wed, 18 Mar 2009 08:56:47 +0100 |
parents | bc29606a740c |
children |
line wrap: on
line source
/******************************************************************************* * Copyright (c) 2005 IBM Corporation and others. * All rights reserved. This program and the accompanying materials * are made available under the terms of the Eclipse Public License v1.0 * which accompanies this distribution, and is available at * http://www.eclipse.org/legal/epl-v10.html * * Contributors: * IBM Corporation - initial API and implementation * Port to the D programming language: * Frank Benoit <benoit@tionex.de> *******************************************************************************/ module org.eclipse.draw2d.graph.NestingTree; import java.lang.all; import java.util.HashMap; import java.util.ArrayList; import java.util.List; import java.util.Map; import org.eclipse.draw2d.graph.Node; import org.eclipse.draw2d.graph.Rank; import org.eclipse.draw2d.graph.Subgraph; class NestingTree { List contents; bool isLeaf = true; int size; double sortValue; Node subgraph; public this(){ contents = new ArrayList(); } private static void addToNestingTree(Map map, Node child) { Subgraph subgraph = child.getParent(); NestingTree parent = cast(NestingTree)map.get(subgraph); if (parent is null) { parent = new NestingTree(); parent.subgraph = subgraph; map.put(subgraph, parent); if (subgraph !is null) addToNestingTree(map, parent); } parent.contents.add(child); } private static void addToNestingTree(Map map, NestingTree branch) { Subgraph subgraph = branch.subgraph.getParent(); NestingTree parent = cast(NestingTree)map.get(subgraph); if (parent is null) { parent = new NestingTree(); parent.subgraph = subgraph; map.put(subgraph, parent); if (subgraph !is null) addToNestingTree(map, parent); } parent.contents.add(branch); } static NestingTree buildNestingTreeForRank(Rank rank) { Map nestingMap = new HashMap(); for (int j = 0; j < rank.count(); j++) { Node node = rank.getNode(j); addToNestingTree(nestingMap, node); } return cast(NestingTree)nestingMap.get(cast(Object)null); } void calculateSortValues() { int total = 0; for (int i = 0; i < contents.size(); i++) { Object o = contents.get(i); if ( auto e = cast(NestingTree)o ) { isLeaf = false; e.calculateSortValues(); total += cast(int)(e.sortValue * e.size); size += e.size; } else { Node n = cast(Node)o; n.sortValue = n.index; total += n.index; size++; } } sortValue = cast(double)total / size; } void getSortValueFromSubgraph() { if (subgraph !is null) sortValue = subgraph.sortValue; for (int i = 0; i < contents.size(); i++) { Object o = contents.get(i); if (auto nt = cast(NestingTree)o ) nt.getSortValueFromSubgraph(); } } void recursiveSort(bool sortLeaves) { if (isLeaf && !sortLeaves) return; bool change = false; //Use modified bubble sort for almost-sorted lists. do { change = false; for (int i = 0; i < contents.size() - 1; i++) change |= swap(i); if (!change) break; change = false; for (int i = contents.size() - 2; i >= 0; i--) change |= swap(i); } while (change); for (int i = 0; i < contents.size(); i++) { Object o = contents.get(i); if (auto nt = cast(NestingTree)o ) nt.recursiveSort(sortLeaves); } } void repopulateRank(Rank r) { for (int i = 0; i < contents.size(); i++) { Object o = contents.get(i); if (null !is cast(Node)o ) r.add(o); else (cast(NestingTree)o).repopulateRank(r); } } bool swap(int index) { Object left = contents.get(index); Object right = contents.get(index + 1); double iL = (null !is cast(Node)left ) ? (cast(Node)left).sortValue : (cast(NestingTree)left).sortValue; double iR = (null !is cast(Node)right ) ? (cast(Node)right).sortValue : (cast(NestingTree)right).sortValue; if (iL <= iR) return false; contents.set(index, right); contents.set(index + 1, left); return true; } public String toString() { if( subgraph ) return "Nesting:" ~ subgraph.toString; //$NON-NLS-1$ return "Nesting: null"; //$NON-NLS-1$ } }