package application.layouts;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import com.mxgraph.layout.mxGraphLayout;
import com.mxgraph.model.mxCell;
import com.mxgraph.model.mxGeometry;
import com.mxgraph.model.mxIGraphModel;
import com.mxgraph.view.mxCellState;
import com.mxgraph.view.mxGraph;
import com.mxgraph.view.mxGraphView;

public class DAGLayout extends mxGraphLayout {
	private mxIGraphModel graphModel;
	private mxGraphView view;
	private Map<mxCell, Set<mxCell>> dotEdges;
	private List<List<mxCell>> paths;
	private List<Integer> order;
	private Map<mxCell, List<mxCell>> orderInResourceHierarchy;
	private Set<Integer> usedPathIndex;
	private List<mxCell> cells;
	private Set<mxCell> roots;
	private Map<mxCell, mxCell> resourceToRoot;
	private Set<mxCell> resources;
	private Set<mxCell> channels;
	private Set<mxCell> eventChannels;
	private Map<mxCell, List<Integer>> vertexToDepths;
	private Map<mxCell, List<Integer>> cellToPathIndex;
	private Map<mxCell, Map<String, Double>> cellGeo;
	final double MOVE_X = 100;
	final double MOVE_Y = 50;
	final double WIDTH = 80;
	final double HEIGHT = 30;
	final double SHIFT = WIDTH / 4;
	final double SPACE = 10;
	final double MARGIN_WIDTH = 30;
	final double MARGIN_HEIGHT = 30;
	final double delta = Math.pow(10, -3);

	public DAGLayout(mxGraph graph) {
		super(graph);
		
		graphModel = graph.getModel();
		view = graph.getView();
		dotEdges = new HashMap<>();
		paths = new ArrayList<>();
		order = new ArrayList<>();
		orderInResourceHierarchy = new HashMap<>();
		usedPathIndex = new HashSet<>();
		cells = new ArrayList<>();
		roots = new HashSet<>();
		resourceToRoot = new HashMap<>();
		resources = new HashSet<>();
		channels = new HashSet<>();
		eventChannels = new HashSet<>();
		vertexToDepths = new HashMap<>();
		cellToPathIndex = new HashMap<>();
		cellGeo = new HashMap<>();
	}
	
	public void execute(Object rootCell) {
		graphModel.beginUpdate();
		try {
			// Initialize cells, roots, channels and eventChannels fields.
			for (int i = 0; i < graphModel.getChildCount(rootCell); i++) {
				mxCell cell = (mxCell) graphModel.getChildAt(rootCell, i);
				
				if (graphModel.isVertex(cell)) {
					mxCellState state = view.getState(cell);
					cells.add(cell);
					
					if ("ellipse".equals(state.getStyle().get("shape"))) {
						// If the cell represents a root resource.
						roots.add(cell);
						orderInResourceHierarchy.put(cell, new ArrayList<>());
						traverseResourceHierarchy(cell, cell, 0);
					}
					
					if ("rectangle".equals(state.getStyle().get("shape"))) {
						// If the cell represents a root channel.
						if ("true".equals(state.getStyle().get("dashed"))) {
							continue;
						}
						
						boolean bEventChannel = true;
						for (int j = 0; j < cell.getEdgeCount(); j++) {
							mxCell edge = (mxCell) cell.getEdgeAt(j);
							if (edge.getTarget() == cell) {
								bEventChannel = false;
							}
						}
						
						if (bEventChannel) {
							// If the cell represents a root event channel.
							eventChannels.add(cell);
						} else {
							channels.add(cell);
						}
						orderInResourceHierarchy.put(cell, new ArrayList<>());
					}
				}
			}
			
			// For all cells
			for (mxCell c : cells) {
				c.getGeometry().setX(0);
				c.getGeometry().setY(0);
				
				if (resources.contains(c)) {
					// For a resource cell.
					view.getState(c).getStyle().put("verticalAlign", "top");
					c.getGeometry().setWidth(WIDTH);
					c.getGeometry().setHeight(HEIGHT);
				}
			}
			
			// Initialize dotEdges.
			for (mxCell c : cells) {
				dotEdges.put(c, new HashSet<>());
			}
			
			for (mxCell eventCh : eventChannels) {
				List<mxCell> newPath = new ArrayList<mxCell>();
				paths.add(newPath);
				constructPaths(eventCh, 0);
			}
			
			recalcDepths();
			
			for (int i = 0; i < paths.size(); i++) {
				for (mxCell cell : paths.get(i)) {
					if (cellToPathIndex.get(cell) == null) {
						cellToPathIndex.put(cell, new ArrayList<>());
					}
					cellToPathIndex.get(cell).add(i);
				}
			}
			
			sortPaths();
			
			boolean isVersion1 = true;
			
			System.out.println(vertexToDepths);
			if (isVersion1) {
				layout1((mxCell) rootCell);
			} else {
				layout2((mxCell) rootCell);
			}
		} finally {
			graphModel.endUpdate();
		}
	}
	
	public void traverseResourceHierarchy(mxCell rootResourceCell, mxCell curResourceCell, int layer) {
		resourceToRoot.put(curResourceCell, rootResourceCell);
		resources.add(curResourceCell);
		if (rootResourceCell != curResourceCell) {
			orderInResourceHierarchy.get(rootResourceCell).add(curResourceCell);
		}
		
		int childNum = graphModel.getChildCount(curResourceCell);
		for (int i = 0; i < childNum; i++) {
			mxCell childCell = (mxCell) graphModel.getChildAt(curResourceCell, i);
			cells.add(childCell);
			resources.add(childCell);
			traverseResourceHierarchy(rootResourceCell, childCell, layer + 1);
		}
	}
	
	public void constructPaths(mxCell curCell, int depth) {
		if (vertexToDepths.get(curCell) == null) {
			vertexToDepths.put(curCell, Arrays.asList(depth, depth));
		} else {
			List<Integer> depths = vertexToDepths.get(curCell);
			depths.set(0, Math.max(depths.get(0), depth));
			depths.set(1, depths.get(0));
		}
		
		paths.get(paths.size() - 1).add(curCell);
		
		int branchCount = 0;
		for (int i = 0; i < curCell.getEdgeCount(); i++) {
			mxCell edge = (mxCell) curCell.getEdgeAt(i);
			mxCellState state = view.getState(edge);
			mxCell dstCell = (mxCell) edge.getTarget();
			
			if ((curCell != dstCell) && (dstCell != null)) {
				if ("true".equals(state.getStyle().get("dashed"))) {
					state.getStyle().put("strokeColor", "#800080");
					dotEdges.get(curCell).add(dstCell);
				} else {
					branchCount++;
					if (branchCount > 1) {
						// If a branch is found.
						List<mxCell> newPath = new ArrayList<mxCell>(paths.get(paths.size() - 1));
						while (newPath.get(newPath.size() - 1).getId() != curCell.getId()) {
							newPath.remove(newPath.size() - 1);
						}
						paths.add(newPath);
						constructPaths(dstCell, depth + 1);
					} else {
						constructPaths(dstCell, depth + 1);
					}
				}
			}
		}
	}
	
	public void recalcDepths() {		
		while (true) {			
			boolean isUpdated = false;
			
			for (List<mxCell> path : paths) {
				for (int i = 1; i < path.size(); i++) {
					mxCell curCell = path.get(i);
					mxCell prevCell = path.get(i - 1);
					if (!(resources.contains(curCell) && resources.contains(prevCell))) {
						// An edge from a resource to a channel
						if (vertexToDepths.get(curCell).get(0) < vertexToDepths.get(prevCell).get(1) + 1) {
							List<Integer> dists = vertexToDepths.get(curCell);
							dists.set(1, Math.max(dists.get(0), dists.get(1)));
							dists.set(0, vertexToDepths.get(prevCell).get(1) + 1);
							isUpdated = true;
						}
					}
				}
			}
			
			for (mxCell rootCell : roots) {
				
				// For all resource cells included in (under) the root resource cell.
				for (mxCell cell : orderInResourceHierarchy.get(rootCell)) {
					mxCell parentCell = (mxCell) graphModel.getParent(cell);
					if (!vertexToDepths.containsKey(cell)) {
						if (vertexToDepths.get(parentCell) != null) vertexToDepths.put(cell, Arrays.asList(vertexToDepths.get(parentCell).get(0), vertexToDepths.get(parentCell).get(0)));
					} else {
						if (vertexToDepths.get(parentCell) != null && vertexToDepths.get(parentCell).get(0) > vertexToDepths.get(cell).get(0)) {
							List<Integer> dists = vertexToDepths.get(cell);
							dists.set(1, Math.max(dists.get(0), dists.get(1)));
							dists.set(0, vertexToDepths.get(parentCell).get(0));
							isUpdated = true;
						}
						
						if (vertexToDepths.get(parentCell) != null && vertexToDepths.get(parentCell).get(1) < vertexToDepths.get(cell).get(1)) {
							List<Integer> dists = vertexToDepths.get(parentCell);
							dists.set(1, vertexToDepths.get(cell).get(1));
							isUpdated = true;
						}
					}
				}
			}
			
			if (!isUpdated) {
				break;
			}
		}
	}
	
	public void sortPaths() {		
		for (int i = 0; i < paths.size(); i++) {
			List<mxCell> path = paths.get(i);
			
			if (path.size() > 1 && roots.contains(path.get(1))) {
				for (mxCell c : path) {
					addPath(c);
				}
			}
		}
	}
	
	public void addPath(mxCell c) {
		if (cellToPathIndex.get(c) != null) {
			for (int i : cellToPathIndex.get(c)) {
				if (!usedPathIndex.contains(i)) {
					order.add(i);
				}
				usedPathIndex.add(i);
			}
		}
		
		for (int i = 0; i < graphModel.getChildCount(c); i++) {
			mxCell child = (mxCell) graphModel.getChildAt(c, i);
			addPath(child);
		}
	}
	
	public void layout1(mxCell s) {
		Set<mxCell> movedSet = new HashSet<>();
		Map<Integer, List<mxCell>> movedMap = new TreeMap<>();
		Map<Integer, Double> distToMaxX = new HashMap<>();
		double maxY = 0;
		int maxD = 0;
		
		putCellGeo(s, 0, 0);
		
		for (mxCell c : cells) {
			if (vertexToDepths.get(c) != null) maxD = Math.max(maxD, vertexToDepths.get(c).get(1));
		}
		
		distToMaxX.put(-1, 0.0);
		for (int d = 0; d <= maxD; d++) {
			movedMap.put(d, new ArrayList<>());
			distToMaxX.put(d, -1.0);
		}
		
		for (int i : order) {
			double centerY = -1;
			for (mxCell cur : paths.get(i)) {
				if (movedSet.contains(cur)) {
					continue;
				}
				
				int d = vertexToDepths.get(cur).get(0);
				double x = distToMaxX.get(d - 1) + MOVE_X;
				double endX = 0;
				double endY = 0;
				
				if (roots.contains(cur) || channels.contains(cur) || eventChannels.contains(cur)) {
					if (centerY == -1) {
						centerY = maxY + MOVE_Y + cur.getGeometry().getHeight() / 2;
					}
					double y = centerY - cur.getGeometry().getHeight() / 2;
					double ny = y;
					double nx = x;
					
					for (mxCell m : movedSet) {
						if (roots.contains(m) || channels.contains(m)) {
							if (cellOverlap(m.getGeometry().getX(), m.getGeometry().getY(), m.getGeometry().getWidth(), m.getGeometry().getHeight(), x, y, cur.getGeometry().getWidth(), cur.getGeometry().getHeight())) {
								ny = m.getGeometry().getY() + m.getGeometry().getHeight() + MOVE_Y;
							}
						}
					}
					
					cur.getGeometry().setX(nx);
					cur.getGeometry().setY(ny);
					endX = nx + cur.getGeometry().getWidth();
					endY = ny + cur.getGeometry().getHeight();
					putCellGeo(cur, nx, ny);
					addMoved(movedSet, movedMap, cur, d);
					graphModel.setGeometry(cur, (mxGeometry) cur.getGeometry().clone());
					
					if (distToMaxX.get(d) < endX) {
						updateDistToMaxX(distToMaxX, movedSet, movedMap, d, maxD, endX);
					}
					maxY = Math.max(maxY, endY);
					
					// For all resource cells included in (under) the root resource cell.
					for (mxCell c : orderInResourceHierarchy.get(cur)) {
						d = vertexToDepths.get(c).get(0);
						nx = x;
						mxCell parent = (mxCell) graphModel.getParent(c);
						
						if (d == vertexToDepths.get(parent).get(0)) {
							nx = cellGeo.get(parent).get("x") + MARGIN_WIDTH;
						} else {
							nx = distToMaxX.get(d - 1) + MOVE_X;
						}
						
						double brotherMaxY = MOVE_Y;
						for (int k = 0; k < graphModel.getChildCount(parent); k++) {
							mxCell child = (mxCell) graphModel.getChildAt(parent, k);
							if (child == c) {
								continue;
							}
							
							if (movedSet.contains(child) && (vertexToDepths.get(child).get(0) <= d && d <= vertexToDepths.get(child).get(1))) {
								brotherMaxY = Math.max(brotherMaxY, child.getGeometry().getY() + child.getGeometry().getHeight() + SPACE);
							}
						}
						
						c.getGeometry().setX(nx - cellGeo.get(parent).get("x"));
						c.getGeometry().setY(brotherMaxY);
						graphModel.setGeometry(c, (mxGeometry) c.getGeometry().clone());
						addMoved(movedSet, movedMap, c, d);
						putCellGeo(c, nx, cellGeo.get(parent).get("y") + brotherMaxY);
						
						endX = cellGeo.get(c).get("x") + c.getGeometry().getWidth();
						endY = cellGeo.get(c).get("y") + c.getGeometry().getHeight();
						endY = resize(parent, endX, endY);
						
						if (distToMaxX.get(d) < endX) {
							updateDistToMaxX(distToMaxX, movedSet, movedMap, d, maxD, endX);
						}
						maxY = Math.max(maxY, endY);
					}		
				}
			}
		}
		
		for (mxCell c : resources) {
			for (mxCell cc : dotEdges.get(c)) {		
				for (Map.Entry<mxCell, Set<mxCell>> entry : dotEdges.entrySet()) {
					mxCell u = entry.getKey();
					for (mxCell v : entry.getValue()) {
						if ((c == u && cc == v) || (c == v && cc == u)) {
							continue;
						}
						
						double []posC = {cellGeo.get(c).get("x") + c.getGeometry().getWidth() / 2, cellGeo.get(c).get("y") + c.getGeometry().getHeight() / 2};
						double []posCC = {cellGeo.get(cc).get("x") + cc.getGeometry().getWidth() / 2, cellGeo.get(cc).get("y") + cc.getGeometry().getHeight() / 2};
						double []posU = {cellGeo.get(u).get("x") + u.getGeometry().getWidth() / 2, cellGeo.get(u).get("y") + u.getGeometry().getHeight() / 2};
						double []posV = {cellGeo.get(v).get("x") + v.getGeometry().getWidth() / 2, cellGeo.get(v).get("y") + v.getGeometry().getHeight() / 2};
						
						if (isStraightLine(posC, posCC, posU, posV)) {
							c.getGeometry().setX(c.getGeometry().getX() + SHIFT);
							cellGeo.get(c).replace("x", cellGeo.get(c).get("x"));
							cc.getGeometry().setX(cc.getGeometry().getX() + SHIFT);
							cellGeo.get(cc).replace("x", cellGeo.get(cc).get("x") + SHIFT);
							graphModel.setGeometry(c, c.getGeometry());
							graphModel.setGeometry(cc, cc.getGeometry());
						}
					}
				}
			}
		}
		
		for (int i : order) {
			mxCell cur = paths.get(i).get(1);
			List<mxCell> ecs = new ArrayList<>();
			for (int j : cellToPathIndex.get(cur)) {
				if (!ecs.contains(paths.get(j).get(0)) && cur == paths.get(j).get(1)) {
					ecs.add(paths.get(j).get(0));
				}
			}

			double centerY = cellGeo.get(cur).get("y") + cur.getGeometry().getHeight() / 2;
			double y = 0;
			if (ecs.size() % 2 != 0) {
				y = centerY - ecs.size()*HEIGHT / 2 - ((ecs.size() - 1) / 2)*SPACE;
			} else {
				y = centerY - ecs.size()*HEIGHT / 2 - (ecs.size() - 1)*SPACE / 2;
			}

			for (int j : order) {
				mxCell other = paths.get(j).get(0);
				if (ecs.contains(other)) {
					continue;
				}
			}
			
			for (mxCell ec : ecs) {
				ec.getGeometry().setY(y);
				graphModel.setGeometry(ec, ec.getGeometry());
				cellGeo.get(ec).replace("y", y);
				y += HEIGHT + SPACE;
			}
		}
		
		List<mxCell> sortedEcs = new ArrayList<>();
		Set<mxCell> usedEcs = new HashSet<>();
		for (int i = 0; i < eventChannels.size(); i++) {
			mxCell minEc = movedMap.get(0).get(0);
			double ecMinY = Double.MAX_VALUE;
			for (mxCell ec : movedMap.get(0)) {
				if (usedEcs.contains(ec)) {
					continue;
				}
				if (cellGeo.get(ec).get("y") < ecMinY) {
					minEc = ec;
					ecMinY = cellGeo.get(ec).get("y");
				}
			}
			sortedEcs.add(minEc);
			usedEcs.add(minEc);
		}
		
		for (int i = 1; i < sortedEcs.size(); i++) {
			mxCell cur = sortedEcs.get(i);
			mxCell pre = sortedEcs.get(i - 1);
			
			if (cellGeo.get(cur).get("y") < cellGeo.get(pre).get("y") + pre.getGeometry().getHeight() + SPACE) {
				double dy = cellGeo.get(pre).get("y") + pre.getGeometry().getHeight() + SPACE - cellGeo.get(cur).get("y");
				cur.getGeometry().setY(cur.getGeometry().getY() + dy);
				cellGeo.get(cur).replace("y", cellGeo.get(cur).get("y") + dy);
				graphModel.setGeometry(cur, cur.getGeometry());
			}
		}
	}
	
	public void layout2(mxCell s) {		
		Set<mxCell> movedSet = new HashSet<>();
		Map<Integer, List<mxCell>> movedMap = new TreeMap<>();
		Map<Integer, Double> distToMaxX = new HashMap<>();
		double maxY = 0;
		int maxD = 0;
		
		putCellGeo(s, 0, 0);
		
		for (mxCell c : cells) {
			maxD = Math.max(maxD, vertexToDepths.get(c).get(1));
		}
		
		distToMaxX.put(-1, 0.0);
		for (int d = 0; d <= maxD; d++) {
			movedMap.put(d, new ArrayList<>());
			distToMaxX.put(d, -1.0);
		}
		
		for (int i : order) {
			double centerY = -1;
			for (int j = 0; j < paths.get(i).size(); j++) {
				mxCell cur = paths.get(i).get(j);
				
				if (movedSet.contains(cur)) {
					continue;
				}
				
				int d = vertexToDepths.get(cur).get(0);
				double x = distToMaxX.get(d - 1) + MOVE_X;
				double endX = 0;
				double endY = 0;
				
				if (roots.contains(cur) || eventChannels.contains(cur)) {
					if (centerY == -1) {
						centerY = maxY + MOVE_Y + cur.getGeometry().getHeight() / 2;
					}
					double y = centerY - cur.getGeometry().getHeight() / 2;
					double ny = y;
					double nx = x;
					
					cur.getGeometry().setX(nx);
					cur.getGeometry().setY(ny);
					endX = nx + cur.getGeometry().getWidth();
					endY = ny + cur.getGeometry().getHeight();
					putCellGeo(cur, nx, ny);
					addMoved(movedSet, movedMap, cur, d);
					graphModel.setGeometry(cur, (mxGeometry) cur.getGeometry().clone());
					
					if (distToMaxX.get(d) < endX) {
						updateDistToMaxX(distToMaxX, movedSet, movedMap, d, maxD, endX);
					}
					maxY = Math.max(maxY, endY);
					
					for (mxCell c : orderInResourceHierarchy.get(cur)) {
						d = vertexToDepths.get(c).get(0);
						nx = x;
						mxCell parent = (mxCell) graphModel.getParent(c);
						
						if (d == vertexToDepths.get(parent).get(0)) {
							nx = cellGeo.get(parent).get("x") + MARGIN_WIDTH;
						} else {
							nx = distToMaxX.get(d - 1) + MOVE_X;
						}
						
						double brotherMaxY = MOVE_Y;
						for (int k = 0; k < graphModel.getChildCount(parent); k++) {
							mxCell child = (mxCell) graphModel.getChildAt(parent, k);
							if (child == c) {
								continue;
							}
							
							if (movedSet.contains(child) && (vertexToDepths.get(child).get(0) <= d && d <= vertexToDepths.get(child).get(1))) {
								brotherMaxY = Math.max(brotherMaxY, child.getGeometry().getY() + child.getGeometry().getHeight() + SPACE);
							}
						}
						
						c.getGeometry().setX(nx - cellGeo.get(parent).get("x"));
						c.getGeometry().setY(brotherMaxY);
						graphModel.setGeometry(c, (mxGeometry) c.getGeometry().clone());
						addMoved(movedSet, movedMap, c, d);
						putCellGeo(c, nx, cellGeo.get(parent).get("y") + brotherMaxY);
						
						endX = cellGeo.get(c).get("x") + c.getGeometry().getWidth();
						endY = cellGeo.get(c).get("y") + c.getGeometry().getHeight();
						endY = resize(parent, endX, endY);
						
						if (distToMaxX.get(d) < endX) {
							updateDistToMaxX(distToMaxX, movedSet, movedMap, d, maxD, endX);
						}
						maxY = Math.max(maxY, endY);
					}
				}
				
				if (channels.contains(cur)) {
					mxCell pre = paths.get(i).get(j - 1);
					centerY = cellGeo.get(pre).get("y") + pre.getGeometry().getHeight() / 2;
					double y = centerY - cur.getGeometry().getHeight() / 2;
					
					cur.getGeometry().setX(x);
					cur.getGeometry().setY(y);
					endX = x + cur.getGeometry().getWidth();
					endY = y + cur.getGeometry().getHeight();
					putCellGeo(cur, x, y);
					addMoved(movedSet, movedMap, cur, d);
					graphModel.setGeometry(cur, (mxGeometry) cur.getGeometry().clone());
					
					if (distToMaxX.get(d) < endX) {
						updateDistToMaxX(distToMaxX, movedSet, movedMap, d, maxD, endX);
					}
					maxY = Math.max(maxY, endY);
				}
			}
		}
		
		for (mxCell c : resources) {
			for (mxCell cc : dotEdges.get(c)) {		
				for (Map.Entry<mxCell, Set<mxCell>> entry : dotEdges.entrySet()) {
					mxCell u = entry.getKey();
					for (mxCell v : entry.getValue()) {
						if ((c == u && cc == v) || (c == v && cc == u)) {
							continue;
						}
						
						double []posC = {cellGeo.get(c).get("x") + c.getGeometry().getWidth() / 2, cellGeo.get(c).get("y") + c.getGeometry().getHeight() / 2};
						double []posCC = {cellGeo.get(cc).get("x") + cc.getGeometry().getWidth() / 2, cellGeo.get(cc).get("y") + cc.getGeometry().getHeight() / 2};
						double []posU = {cellGeo.get(u).get("x") + u.getGeometry().getWidth() / 2, cellGeo.get(u).get("y") + u.getGeometry().getHeight() / 2};
						double []posV = {cellGeo.get(v).get("x") + v.getGeometry().getWidth() / 2, cellGeo.get(v).get("y") + v.getGeometry().getHeight() / 2};
						
						if (isStraightLine(posC, posCC, posU, posV)) {
							c.getGeometry().setX(c.getGeometry().getX() + SHIFT);
							cellGeo.get(c).replace("x", cellGeo.get(c).get("x"));
							cc.getGeometry().setX(cc.getGeometry().getX() + SHIFT);
							cellGeo.get(cc).replace("x", cellGeo.get(cc).get("x") + SHIFT);
							graphModel.setGeometry(c, c.getGeometry());
							graphModel.setGeometry(cc, cc.getGeometry());
						}
					}
				}
			}
		}
		
		for (int i : order) {
			mxCell cur = paths.get(i).get(1);
			List<mxCell> ecs = new ArrayList<>();
			for (int j : cellToPathIndex.get(cur)) {
				if (!ecs.contains(paths.get(j).get(0)) && cur == paths.get(j).get(1)) {
					ecs.add(paths.get(j).get(0));
				}
			}
			
			double centerY = cellGeo.get(cur).get("y") + cur.getGeometry().getHeight() / 2;
			double y = 0;
			if (ecs.size() % 2 != 0) {
				y = centerY - ecs.size()*HEIGHT / 2 - ((ecs.size() - 1) / 2)*SPACE;
			} else {
				y = centerY - ecs.size()*HEIGHT / 2 - (ecs.size() - 1)*SPACE / 2;
			}

			for (int j : order) {
				mxCell other = paths.get(j).get(0);
				if (ecs.contains(other)) {
					continue;
				}
			}
			
			for (mxCell ec : ecs) {
				ec.getGeometry().setY(y);
				graphModel.setGeometry(ec, ec.getGeometry());
				cellGeo.get(ec).replace("y", y);
				y += HEIGHT + SPACE;
			}
		}
		
		List<mxCell> sortedEcs = new ArrayList<>();
		Set<mxCell> usedEcs = new HashSet<>();
		for (int i = 0; i < eventChannels.size(); i++) {
			mxCell minEc = movedMap.get(0).get(0);
			double ecMinY = Double.MAX_VALUE;
			for (mxCell ec : movedMap.get(0)) {
				if (usedEcs.contains(ec)) {
					continue;
				}
				if (cellGeo.get(ec).get("y") < ecMinY) {
					minEc = ec;
					ecMinY = cellGeo.get(ec).get("y");
				}
			}
			sortedEcs.add(minEc);
			usedEcs.add(minEc);
		}
		
		for (int i = 1; i < sortedEcs.size(); i++) {
			mxCell cur = sortedEcs.get(i);
			mxCell pre = sortedEcs.get(i - 1);
			
			if (cellGeo.get(cur).get("y") < cellGeo.get(pre).get("y") + pre.getGeometry().getHeight() + SPACE) {
				double dy = cellGeo.get(pre).get("y") + pre.getGeometry().getHeight() + SPACE - cellGeo.get(cur).get("y");
				cur.getGeometry().setY(cur.getGeometry().getY() + dy);
				cellGeo.get(cur).replace("y", cellGeo.get(cur).get("y") + dy);
				graphModel.setGeometry(cur, cur.getGeometry());
			}
		}
	}
	
	public void putCellGeo(mxCell c, double x, double y) {
		cellGeo.put(c, new HashMap<>());
		cellGeo.get(c).put("x", x);
		cellGeo.get(c).put("y", y);
	}
	
	public void addMoved(Set<mxCell> ms, Map<Integer, List<mxCell>> mm, mxCell c, int d) {
		ms.add(c);
		mm.get(d).add(c);
	}
	
	public boolean isStraightLine(double []u1, double []v1, double []u2, double []v2) {
		double gradient1 = 0;
		double length1 = Math.pow(u1[0] - v1[0], 2) + Math.pow(u1[1] - v1[1], 2);
		double gradient2 = 0;
		double length2 = Math.pow(u2[0] - v2[0], 2) + Math.pow(u2[1] - v2[1], 2);
		boolean isVertical = false;
		
		if (u1[0] == v1[0]) {
			isVertical = true;
		} else {
			gradient1 = (u1[1] - v1[1]) / (u1[0] - v1[0]);
		}
		
		if (isVertical) {
			if (u2[0] != v2[0]) {
				return false;
			} else {
				gradient2 = (u2[1] - v2[1]) / (u2[0] - v2[0]);
			}
		} else {
			if (gradient1 - gradient2 > delta) {
				return false;
			}
		}
		
		double [][]a = {u1, v1};
		double [][]b = {u2, v2};
		double maxLength = 0;
		for (double []c1 : a) {
			for (double []c2 : b) {
				double gradient3 = 0;
				double length3 = Math.pow(c1[0] - c2[0], 2) + Math.pow(c1[1] - c2[1], 2);
				
				if(isVertical) {
					if (c1[0] == c2[0]) {
						maxLength = Math.max(maxLength, length3);
					} else {
						return false;
					}
				} else {
					if (c1[0] == c2[0]) {
						return false;
					} else {
						gradient3 = (c2[1] - c1[1]) / (c2[0] - c1[0]);
						if (gradient1 - gradient3 > delta) {
							return false;
						}
						maxLength = Math.max(maxLength, length3);
					}
				}
			}
		}
		
		if (length1 + length2 < maxLength) {
			return false;
		} else {
			return true;
		}
	}
	
	public boolean cellOverlap(double ax, double ay, double aw, double ah, double bx, double by, double bw, double bh) {
		if (((ax <= bx) && (bx <= ax + aw)) || ((bx <= ax) && (ax <= bx + bw))) {
			if (((ay <= by) && (by <= ay + ah)) || ((by <= ay) && (ay <= by + bh))) {
				return true;
			}
		}
		return false;
	}
	
	public void updateDistToMaxX(Map<Integer, Double> distToMaxX, Set<mxCell> movedSet, Map<Integer, List<mxCell>> movedMap, int d, int md, double endX) {
		double preEndX = distToMaxX.get(d);
		distToMaxX.replace(d, endX);
		for (int i = d + 1; i <= md; i++) {
			if (distToMaxX.get(i) == -1) {
				distToMaxX.replace(i, endX);
			}
		}
		
		for (Map.Entry<Integer, List<mxCell>> entry : movedMap.entrySet()) {
			if (entry.getKey() <= d) {
				continue;
			}
			
			for (mxCell cell : entry.getValue()) {
				double newX = cellGeo.get(cell).get("x") + endX - preEndX;
				mxCell cp = (mxCell) cell.getParent();
				relocateX(cell, newX, cellGeo.get(cp).get("x"));
				
				if (!(roots.contains(cell) || channels.contains(cell))) {
					mxCell ancestor = (mxCell) graphModel.getParent(cell);
					resize(ancestor, cellGeo.get(cell).get("x") + cell.getGeometry().getWidth(), cellGeo.get(cell).get("y") + cell.getGeometry().getHeight());
				}
				if (distToMaxX.get(entry.getKey()) < cellGeo.get(cell).get("x") + cell.getGeometry().getWidth()) {
					distToMaxX.replace(entry.getKey(), cellGeo.get(cell).get("x") + cell.getGeometry().getWidth());
					for (int i = entry.getKey() + 1; i <= md; i++) {
						if (distToMaxX.get(i) == -1) {
							distToMaxX.replace(i, cellGeo.get(cell).get("x") + cell.getGeometry().getWidth());
						}
					}
				}
			}
		}
	}
	
	public double resize(mxCell ancestor, double endX, double endY) {
		while (true) {
			boolean isChanging = false;
			
			if (ancestor.getGeometry().getWidth() < endX - cellGeo.get(ancestor).get("x") + MARGIN_WIDTH) {
				ancestor.getGeometry().setWidth(endX - cellGeo.get(ancestor).get("x") + MARGIN_WIDTH);
				isChanging = true;
			}
			if (ancestor.getGeometry().getHeight() < endY - cellGeo.get(ancestor).get("y") + MARGIN_HEIGHT) {
				ancestor.getGeometry().setHeight(endY - cellGeo.get(ancestor).get("y") + MARGIN_HEIGHT);
				isChanging = true;
			}
			if (isChanging) {
				graphModel.setGeometry(ancestor, ancestor.getGeometry());
			}
			
			endX = cellGeo.get(ancestor).get("x") + ancestor.getGeometry().getWidth();
			endY = cellGeo.get(ancestor).get("y") + ancestor.getGeometry().getHeight();
			
			if (roots.contains(ancestor)) {
				break;
			}
			ancestor = (mxCell) ancestor.getParent();
		}
		
		return endY;
	}
	
	public void relocateX(mxCell c, double nx, double dx) {
		c.getGeometry().setX(nx - dx);
		graphModel.setGeometry(c, (mxGeometry) c.getGeometry().clone());
		cellGeo.get(c).replace("x", nx);
	}
}