/**
 * Copyright (c) 2007-2012, JGraph Ltd
 */
package com.mxgraph.util;

import java.awt.AlphaComposite;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.RenderingHints;
import java.awt.font.FontRenderContext;
import java.awt.font.TextAttribute;
import java.awt.geom.Line2D;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.awt.image.ImageObserver;
import java.io.BufferedReader;
import java.io.ByteArrayInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Formatter;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.SortedSet;
import java.util.Stack;
import java.util.TreeSet;
import java.util.logging.Level;
import java.util.logging.Logger;

import javax.imageio.ImageIO;
import javax.swing.text.html.HTMLDocument;

import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.NamedNodeMap;
import org.w3c.dom.Node;

import com.mxgraph.io.mxCodecRegistry;
import com.mxgraph.model.mxCellPath;
import com.mxgraph.model.mxICell;
import com.mxgraph.model.mxIGraphModel;
import com.mxgraph.view.mxCellState;

/**
 * Contains various helper methods for use with mxGraph.
 */
public class mxUtils
{

	private static final Logger log = Logger.getLogger(mxUtils.class.getName());

	/**
	 * True if the machine is a Mac.
	 */
	public static boolean IS_MAC = System.getProperty("os.name").toLowerCase()
			.indexOf("mac") >= 0;

	/**
	 * True if the machine is running a linux kernel.
	 */
	public static boolean IS_LINUX = System.getProperty("os.name")
			.toLowerCase().indexOf("linux") >= 0;

	/**
	 * Static Graphics used for Font Metrics.
	 */
	protected static transient Graphics fontGraphics;

	// Creates a renderer for HTML markup (only possible in
	// non-headless environment)
	static
	{
		try
		{
			fontGraphics = new BufferedImage(1, 1, BufferedImage.TYPE_INT_RGB)
					.getGraphics();
		}
		catch (Exception e)
		{
			log.log(Level.WARNING, "Failed to initialize font graphics", e);
		}
	}

	/**
	 * Returns the size for the given label. If isHtml is true then any HTML
	 * markup in the label is computed as HTML and all newlines inside the HTML
	 * body are converted into linebreaks.
	 */
	public static mxRectangle getLabelSize(String label,
			Map<String, Object> style, boolean isHtml, double scale)
	{
		return getLabelSize(label, style, isHtml, scale, 0);
	}

	/**
	 * Returns the size for the given label. If isHtml is true then any HTML
	 * markup in the label is computed as HTML and all newlines inside the HTML
	 * body are converted into linebreaks.
	 */
	public static mxRectangle getLabelSize(String label,
			Map<String, Object> style, boolean isHtml, double scale,
			double htmlWrapWidth)
	{
		mxRectangle size;

		if (isHtml)
		{
			size = getSizeForHtml(getBodyMarkup(label, true), style, scale,
					htmlWrapWidth);
		}
		else
		{
			size = getSizeForString(label, getFont(style), scale);
		}

		return size;
	}

	/**
	 * Returns the body part of the given HTML markup.
	 */
	public static String getBodyMarkup(String markup, boolean replaceLinefeeds)
	{
		String lowerCase = markup.toLowerCase();
		int bodyStart = lowerCase.indexOf("<body>");

		if (bodyStart >= 0)
		{
			bodyStart += 7;
			int bodyEnd = lowerCase.lastIndexOf("</body>");

			if (bodyEnd > bodyStart)
			{
				markup = markup.substring(bodyStart, bodyEnd).trim();
			}
		}

		if (replaceLinefeeds)
		{
			markup = markup.replaceAll("\n", "<br>");
		}

		return markup;
	}

	/**
	 * Returns the paint bounds for the given label.
	 */
	public static mxRectangle getLabelPaintBounds(String label,
			Map<String, Object> style, boolean isHtml, mxPoint offset,
			mxRectangle vertexBounds, double scale)
	{
		return getLabelPaintBounds(label, style, isHtml, offset, vertexBounds,
				scale, false);
	}

	/**
	 * Returns the paint bounds for the given label.
	 */
	public static mxRectangle getLabelPaintBounds(String label,
			Map<String, Object> style, boolean isHtml, mxPoint offset,
			mxRectangle vertexBounds, double scale, boolean isEdge)
	{
		double wrapWidth = 0;

		if (isHtml
				&& vertexBounds != null
				&& mxUtils.getString(style, mxConstants.STYLE_WHITE_SPACE,
						"nowrap").equals("wrap"))
		{
			wrapWidth = vertexBounds.getWidth();
		}

		mxRectangle size = mxUtils.getLabelSize(label, style, isHtml, scale,
				wrapWidth);

		// Measures font with full scale and scales back
		size.setWidth(size.getWidth() / scale);
		size.setHeight(size.getHeight() / scale);

		double x = offset.getX();
		double y = offset.getY();
		double width = 0;
		double height = 0;

		if (vertexBounds != null)
		{
			x += vertexBounds.getX();
			y += vertexBounds.getY();

			if (mxUtils.getString(style, mxConstants.STYLE_SHAPE, "").equals(
					mxConstants.SHAPE_SWIMLANE))
			{
				// Limits the label to the swimlane title
				boolean horizontal = mxUtils.isTrue(style,
						mxConstants.STYLE_HORIZONTAL, true);
				double start = mxUtils.getDouble(style,
						mxConstants.STYLE_STARTSIZE,
						mxConstants.DEFAULT_STARTSIZE)
						* scale;

				if (horizontal)
				{
					width += vertexBounds.getWidth();
					height += start;
				}
				else
				{
					width += start;
					height += vertexBounds.getHeight();
				}
			}
			else
			{
				width += (isEdge) ? 0 : vertexBounds.getWidth();
				height += vertexBounds.getHeight();
			}
		}

		return mxUtils.getScaledLabelBounds(x, y, size, width, height, style,
				scale);
	}

	/**
	 * Returns the bounds for a label for the given location and size, taking
	 * into account the alignment and spacing in the specified style, as well as
	 * the width and height of the rectangle that contains the label. (For edge
	 * labels this width and height is 0.) The scale is used to scale the given
	 * size and the spacings in the specified style.
	 */
	public static mxRectangle getScaledLabelBounds(double x, double y,
			mxRectangle size, double outerWidth, double outerHeight,
			Map<String, Object> style, double scale)
	{
		double inset = mxConstants.LABEL_INSET * scale;

		// Scales the size of the label
		// FIXME: Correct rounded font size and not-rounded scale
		double width = size.getWidth() * scale + 2 * inset;
		double height = size.getHeight() * scale + 2 * inset;

		// Gets the global spacing and orientation
		boolean horizontal = isTrue(style, mxConstants.STYLE_HORIZONTAL, true);
		int spacing = (int) (getInt(style, mxConstants.STYLE_SPACING) * scale);

		// Gets the alignment settings
		Object align = getString(style, mxConstants.STYLE_ALIGN,
				mxConstants.ALIGN_CENTER);
		Object valign = getString(style, mxConstants.STYLE_VERTICAL_ALIGN,
				mxConstants.ALIGN_MIDDLE);

		// Gets the vertical spacing
		int top = (int) (getInt(style, mxConstants.STYLE_SPACING_TOP) * scale);
		int bottom = (int) (getInt(style, mxConstants.STYLE_SPACING_BOTTOM) * scale);

		// Gets the horizontal spacing
		int left = (int) (getInt(style, mxConstants.STYLE_SPACING_LEFT) * scale);
		int right = (int) (getInt(style, mxConstants.STYLE_SPACING_RIGHT) * scale);

		// Applies the orientation to the spacings and dimension
		if (!horizontal)
		{
			int tmp = top;
			top = right;
			right = bottom;
			bottom = left;
			left = tmp;

			double tmp2 = width;
			width = height;
			height = tmp2;
		}

		// Computes the position of the label for the horizontal alignment
		if ((horizontal && align.equals(mxConstants.ALIGN_CENTER))
				|| (!horizontal && valign.equals(mxConstants.ALIGN_MIDDLE)))
		{
			x += (outerWidth - width) / 2 + left - right;
		}
		else if ((horizontal && align.equals(mxConstants.ALIGN_RIGHT))
				|| (!horizontal && valign.equals(mxConstants.ALIGN_BOTTOM)))
		{
			x += outerWidth - width - spacing - right;
		}
		else
		{
			x += spacing + left;
		}

		// Computes the position of the label for the vertical alignment
		if ((!horizontal && align.equals(mxConstants.ALIGN_CENTER))
				|| (horizontal && valign.equals(mxConstants.ALIGN_MIDDLE)))
		{
			y += (outerHeight - height) / 2 + top - bottom;
		}
		else if ((!horizontal && align.equals(mxConstants.ALIGN_LEFT))
				|| (horizontal && valign.equals(mxConstants.ALIGN_BOTTOM)))
		{
			y += outerHeight - height - spacing - bottom;
		}
		else
		{
			y += spacing + top;
		}

		return new mxRectangle(x, y, width, height);
	}

	/**
	 * Returns the font metrics of the static font graphics instance
	 * @param font The font whose metrics are to be returned
	 * @return the font metrics of the specified font
	 */
	public static FontMetrics getFontMetrics(Font font)
	{
		if (fontGraphics != null)
		{
			return fontGraphics.getFontMetrics(font);
		}

		return null;
	}

	/**
	 * Returns an <mxRectangle> with the size (width and height in pixels) of
	 * the given string.
	 * 
	 * @param text
	 *            String whose size should be returned.
	 * @param font
	 *            Font to be used for the computation.
	 */
	public static mxRectangle getSizeForString(String text, Font font,
			double scale)
	{
		FontRenderContext frc = new FontRenderContext(null, false, false);
		font = font.deriveFont((float) (font.getSize2D() * scale));
		FontMetrics metrics = null;

		if (fontGraphics != null)
		{
			metrics = fontGraphics.getFontMetrics(font);
		}

		double lineHeight = mxConstants.LINESPACING;

		if (metrics != null)
		{
			lineHeight += metrics.getHeight();
		}
		else
		{
			lineHeight += font.getSize2D() * 1.27;
		}

		String[] lines = text.split("\n");

		Rectangle2D boundingBox = null;

		if (lines.length == 0)
		{
			boundingBox = font.getStringBounds("", frc);
		}
		else
		{
			for (int i = 0; i < lines.length; i++)
			{
				Rectangle2D bounds = font.getStringBounds(lines[i], frc);

				if (boundingBox == null)
				{
					boundingBox = bounds;
				}
				else
				{
					boundingBox
							.setFrame(
									0,
									0,
									Math.max(boundingBox.getWidth(),
											bounds.getWidth()),
									boundingBox.getHeight() + lineHeight);
				}
			}
		}

		return new mxRectangle(boundingBox);
	}

	/**
	 * Returns the specified text in lines that fit within the specified
	 * width when the specified font metrics are applied to the text
	 * @param text the text to wrap
	 * @param metrics the font metrics to calculate the text size for
	 * @param width the width that the text must fit within
	 * @return the input text split in lines that fit the specified width
	 */
	public static String[] wordWrap(String text, FontMetrics metrics,
			double width)
	{
		List<String> result = new ArrayList<String>();
		// First split the processing into lines already delimited by
		// newlines. We want the result to retain all newlines in position.
		String[] lines = text.split("\n");

		for (int i = 0; i < lines.length; i++)
		{
			int lineWidth = 0; // the display width of the current line
			int charCount = 0; // keeps count of current position in the line
			StringBuilder currentLine = new StringBuilder();

			// Split the words of the current line by spaces and tabs
			// The words are trimmed of tabs, space and newlines, therefore
			String[] words = lines[i].split("\\s+");

			// Need to a form a stack of the words in reverse order
			// This is because if a word is split during the process 
			// the remainder of the word is added to the front of the 
			// stack and processed next
			Stack<String> wordStack = new Stack<String>();

			for (int j = words.length - 1; j >= 0; j--)
			{
				wordStack.push(words[j]);
			}

			while (!wordStack.isEmpty())
			{
				String word = wordStack.pop();

				// Work out what whitespace exists before this word.
				// and add the width of the whitespace to the calculation
				int whitespaceCount = 0;

				if (word.length() > 0)
				{
					// Concatenate any preceding whitespace to the
					// word and calculate the number of characters of that
					// whitespace
					char firstWordLetter = word.charAt(0);
					int letterIndex = lines[i].indexOf(firstWordLetter,
							charCount);
					String whitespace = lines[i].substring(charCount,
							letterIndex);
					whitespaceCount = whitespace.length();
					word = whitespace.concat(word);
				}

				double wordLength;

				// If the line width is zero, we are at the start of a newline
				// We don't proceed preceeding whitespace in the width
				// calculation
				if (lineWidth > 0)
				{
					wordLength = metrics.stringWidth(word);
				}
				else
				{
					wordLength = metrics.stringWidth(word.trim());
				}

				// Does the width of line so far plus the width of the 
				// current word exceed the allowed width?
				if (lineWidth + wordLength > width)
				{
					if (lineWidth > 0)
					{
						// There is already at least one word on this line
						// and the current word takes the overall width over
						// the allowed width. Because there is something on
						// the line, complete the current line, reset the width
						// counter, create a new line and put the current word
						// back on the stack for processing in the next round
						result.add(currentLine.toString());
						currentLine = new StringBuilder();
						wordStack.push(word.trim());
						lineWidth = 0;
					}
					else if (mxConstants.SPLIT_WORDS)
					{
						// There are no words on the current line and the 
						// current word does not fit on it. Find the maximum
						// number of characters of this word that just fit
						// in the available width
						word = word.trim();

						for (int j = 1; j <= word.length(); j++)
						{
							wordLength = metrics.stringWidth(word.substring(0,
									j));

							if (lineWidth + wordLength > width)
							{
								// The last character took us over the allowed
								// width, deducted it unless there is only one
								// character, in which case we have to use it
								// since we can't split it...
								j = j > 1 ? j - 1 : j;
								String chars = word.substring(0, j);
								currentLine = currentLine.append(chars);
								// Return the unprocessed part of the word 
								// to the stack
								wordStack
										.push(word.substring(j, word.length()));
								result.add(currentLine.toString());
								currentLine = new StringBuilder();
								lineWidth = 0;
								// Increment char counter allowing for white 
								// space in the original word
								charCount = charCount + chars.length()
										+ whitespaceCount;
								break;
							}
						}
					}
					else
					{
						// There are no words on the current line, but
						// we are not splitting.
						word = word.trim();
						result.add(word);
						currentLine = new StringBuilder();
						lineWidth = 0;
						// Increment char counter allowing for white 
						// space in the original word
						charCount = word.length() + whitespaceCount;
					}
				}
				else
				{
					// The current word does not take the total line width
					// over the allowed width. Append the word, removing
					// preceeding whitespace if it is the first word in the
					// line.
					if (lineWidth > 0)
					{
						currentLine = currentLine.append(word);
					}
					else
					{
						currentLine = currentLine.append(word.trim());
					}

					lineWidth += wordLength;
					charCount += word.length();
				}
			}

			result.add(currentLine.toString());
		}

		return result.toArray(new String[result.size()]);
	}

	/**
	 * Returns an mxRectangle with the size (width and height in pixels) of the
	 * given HTML markup.
	 * 
	 * @param markup
	 *            HTML markup whose size should be returned.
	 */
	public static mxRectangle getSizeForHtml(String markup,
			Map<String, Object> style, double scale, double wrapWidth)
	{
		mxLightweightLabel textRenderer = mxLightweightLabel
				.getSharedInstance();

		if (textRenderer != null)
		{
			// First run measures size with no wrapping
			textRenderer.setText(createHtmlDocument(style, markup));
			Dimension size = textRenderer.getPreferredSize();

			// Second run measures size with wrapping if required.
			// Note that this is only required because max-width
			// is not supported and we can't get the width of an
			// inner HTML element (or is this possible?).
			if (wrapWidth > 0)
			{
				textRenderer.setText(createHtmlDocument(
						style,
						markup,
						1,
						(int) Math.ceil(wrapWidth - mxConstants.LABEL_INSET
								* scale)));
				Dimension size2 = textRenderer.getPreferredSize();

				// Uses wrapped text size if any text was actually wrapped
				if (size2.width < size.width)
				{
					size = size2;
				}
			}

			return new mxRectangle(0, 0, size.width * scale, size.height
					* scale);
		}
		else
		{
			return getSizeForString(markup, getFont(style), scale);
		}
	}

	/**
	 * Function: arcToCurves
	 * 
	 * Converts the given arc to a series of curves.
	 */
	public static double[] arcToCurves(double x0, double y0, double r1,
			double r2, double angle, double largeArcFlag, double sweepFlag,
			double x, double y)
	{
		x -= x0;
		y -= y0;

		if (r1 == 0 || r2 == 0)
		{
			return new double[0];
		}

		double fS = sweepFlag;
		double psai = angle;
		r1 = Math.abs(r1);
		r2 = Math.abs(r2);
		double ctx = -x / 2;
		double cty = -y / 2;
		double cpsi = Math.cos(psai * Math.PI / 180);
		double spsi = Math.sin(psai * Math.PI / 180);
		double rxd = cpsi * ctx + spsi * cty;
		double ryd = -1 * spsi * ctx + cpsi * cty;
		double rxdd = rxd * rxd;
		double rydd = ryd * ryd;
		double r1x = r1 * r1;
		double r2y = r2 * r2;
		double lamda = rxdd / r1x + rydd / r2y;
		double sds;

		if (lamda > 1)
		{
			r1 = Math.sqrt(lamda) * r1;
			r2 = Math.sqrt(lamda) * r2;
			sds = 0;
		}
		else
		{
			double seif = 1;

			if (largeArcFlag == fS)
			{
				seif = -1;
			}

			sds = seif
					* Math.sqrt((r1x * r2y - r1x * rydd - r2y * rxdd)
							/ (r1x * rydd + r2y * rxdd));
		}

		double txd = sds * r1 * ryd / r2;
		double tyd = -1 * sds * r2 * rxd / r1;
		double tx = cpsi * txd - spsi * tyd + x / 2;
		double ty = spsi * txd + cpsi * tyd + y / 2;
		double rad = Math.atan2((ryd - tyd) / r2, (rxd - txd) / r1)
				- Math.atan2(0, 1);
		double s1 = (rad >= 0) ? rad : 2 * Math.PI + rad;
		rad = Math.atan2((-ryd - tyd) / r2, (-rxd - txd) / r1)
				- Math.atan2((ryd - tyd) / r2, (rxd - txd) / r1);
		double dr = (rad >= 0) ? rad : 2 * Math.PI + rad;

		if (fS == 0 && dr > 0)
		{
			dr -= 2 * Math.PI;
		}
		else if (fS != 0 && dr < 0)
		{
			dr += 2 * Math.PI;
		}

		double sse = dr * 2 / Math.PI;
		int seg = (int) Math.ceil(sse < 0 ? -1 * sse : sse);
		double segr = dr / seg;
		double t = 8 / 3 * Math.sin(segr / 4) * Math.sin(segr / 4)
				/ Math.sin(segr / 2);
		double cpsir1 = cpsi * r1;
		double cpsir2 = cpsi * r2;
		double spsir1 = spsi * r1;
		double spsir2 = spsi * r2;
		double mc = Math.cos(s1);
		double ms = Math.sin(s1);
		double x2 = -t * (cpsir1 * ms + spsir2 * mc);
		double y2 = -t * (spsir1 * ms - cpsir2 * mc);
		double x3 = 0;
		double y3 = 0;

		double[] result = new double[seg * 6];

		for (int n = 0; n < seg; ++n)
		{
			s1 += segr;
			mc = Math.cos(s1);
			ms = Math.sin(s1);

			x3 = cpsir1 * mc - spsir2 * ms + tx;
			y3 = spsir1 * mc + cpsir2 * ms + ty;
			double dx = -t * (cpsir1 * ms + spsir2 * mc);
			double dy = -t * (spsir1 * ms - cpsir2 * mc);

			// CurveTo updates x0, y0 so need to restore it
			int index = n * 6;
			result[index] = x2 + x0;
			result[index + 1] = y2 + y0;
			result[index + 2] = x3 - dx + x0;
			result[index + 3] = y3 - dy + y0;
			result[index + 4] = x3 + x0;
			result[index + 5] = y3 + y0;

			x2 = x3 + dx;
			y2 = y3 + dy;
		}

		return result;
	}

	/**
	 * Returns the bounding box for the rotated rectangle.
	 */
	public static mxRectangle getBoundingBox(mxRectangle rect, double rotation)
	{
		mxRectangle result = null;

		if (rect != null && rotation != 0)
		{
			double rad = Math.toRadians(rotation);
			double cos = Math.cos(rad);
			double sin = Math.sin(rad);

			mxPoint cx = new mxPoint(rect.getX() + rect.getWidth() / 2,
					rect.getY() + rect.getHeight() / 2);

			mxPoint p1 = new mxPoint(rect.getX(), rect.getY());
			mxPoint p2 = new mxPoint(rect.getX() + rect.getWidth(), rect.getY());
			mxPoint p3 = new mxPoint(p2.getX(), rect.getY() + rect.getHeight());
			mxPoint p4 = new mxPoint(rect.getX(), p3.getY());

			p1 = getRotatedPoint(p1, cos, sin, cx);
			p2 = getRotatedPoint(p2, cos, sin, cx);
			p3 = getRotatedPoint(p3, cos, sin, cx);
			p4 = getRotatedPoint(p4, cos, sin, cx);

			Rectangle tmp = new Rectangle((int) p1.getX(), (int) p1.getY(), 0,
					0);
			tmp.add(p2.getPoint());
			tmp.add(p3.getPoint());
			tmp.add(p4.getPoint());

			result = new mxRectangle(tmp);
		}
		else if (rect != null)
		{
			result = (mxRectangle) rect.clone();
		}

		return result;
	}

	/**
	 * Find the first character matching the input character in the given
	 * string where the character has no letter preceding it.
	 * 
	 * @param text the string to test for the presence of the input character
	 * @param inputChar the test character
	 * @param fromIndex the index position of the string to start from
	 * @return the position of the first character matching the input character
	 * 			in the given string where the character has no letter preceding it.
	 */
	public static int firstCharAt(String text, int inputChar, int fromIndex)
	{
		int result = 0;

		while (result >= 0)
		{
			result = text.indexOf(inputChar, fromIndex);

			if (result == 0)
			{
				return result;
			}
			else if (result > 0)
			{
				// Check there is a whitespace or symbol before the hit character
				if (Character.isLetter(text.codePointAt(result - 1)))
				{
					// The pre-increment is used in if and else branches.
					if (++fromIndex >= text.length())
					{
						return -1;
					}
					else
					{
						// Test again from next candidate character
						// This isn't the first letter of this word
						result = text.indexOf(inputChar, fromIndex);
					}
				}
				else
				{
					return result;
				}
			}

		}

		return result;
	}

	/**
	 * Rotates the given point by the given cos and sin.
	 */
	public static mxPoint getRotatedPoint(mxPoint pt, double cos, double sin)
	{
		return getRotatedPoint(pt, cos, sin, new mxPoint());
	}

	/**
	 * Finds the index of the nearest segment on the given cell state for the
	 * specified coordinate pair.
	 */
	public static int findNearestSegment(mxCellState state, double x, double y)
	{
		int index = -1;

		if (state.getAbsolutePointCount() > 0)
		{
			mxPoint last = state.getAbsolutePoint(0);
			double min = Double.MAX_VALUE;

			for (int i = 1; i < state.getAbsolutePointCount(); i++)
			{
				mxPoint current = state.getAbsolutePoint(i);
				double dist = new Line2D.Double(last.x, last.y, current.x,
						current.y).ptSegDistSq(x, y);

				if (dist < min)
				{
					min = dist;
					index = i - 1;
				}

				last = current;
			}
		}

		return index;
	}

	/**
	 * Rotates the given point by the given cos and sin.
	 */
	public static mxPoint getRotatedPoint(mxPoint pt, double cos, double sin,
			mxPoint c)
	{
		double x = pt.getX() - c.getX();
		double y = pt.getY() - c.getY();

		double x1 = x * cos - y * sin;
		double y1 = y * cos + x * sin;

		return new mxPoint(x1 + c.getX(), y1 + c.getY());
	}

	/**
	 * Returns an integer mask of the port constraints of the given map
	 * @param terminal the cached cell state of the cell to determine the
	 * 			port constraints for
	 * @param edge the edge connected to the constrained terminal
	 * @param source whether or not the edge specified is connected to the
	 * 			terminal specified at its source end
	 * @return the mask of port constraint directions
	 */
	public static int getPortConstraints(mxCellState terminal,
			mxCellState edge, boolean source)
	{
		return getPortConstraints(terminal, edge, source,
				mxConstants.DIRECTION_MASK_ALL);
	}

	/**
	 * Returns an integer mask of the port constraints of the given map
	 * @param terminal the cached cell state of the cell to determine the
	 * 			port constraints for
	 * @param edge the edge connected to the constrained terminal
	 * @param source whether or not the edge specified is connected to the
	 * 			terminal specified at its source end
	 * @param defaultValue Default value to return if the key is undefined.
	 * @return the mask of port constraint directions
	 */
	public static int getPortConstraints(mxCellState terminal,
			mxCellState edge, boolean source, int defaultValue)
	{
		Object value = terminal.getStyle().get(
				mxConstants.STYLE_PORT_CONSTRAINT);

		if (value == null)
		{
			return defaultValue;
		}
		else
		{
			String directions = value.toString();
			int returnValue = mxConstants.DIRECTION_MASK_NONE;

			if (directions.indexOf(mxConstants.DIRECTION_NORTH) >= 0)
			{
				returnValue |= mxConstants.DIRECTION_MASK_NORTH;
			}
			if (directions.indexOf(mxConstants.DIRECTION_WEST) >= 0)
			{
				returnValue |= mxConstants.DIRECTION_MASK_WEST;
			}
			if (directions.indexOf(mxConstants.DIRECTION_SOUTH) >= 0)
			{
				returnValue |= mxConstants.DIRECTION_MASK_SOUTH;
			}
			if (directions.indexOf(mxConstants.DIRECTION_EAST) >= 0)
			{
				returnValue |= mxConstants.DIRECTION_MASK_EAST;
			}

			return returnValue;
		}
	}

	public static int reversePortConstraints(int constraint)
	{
		int result = 0;

		result = (constraint & mxConstants.DIRECTION_MASK_WEST) << 3;
		result |= (constraint & mxConstants.DIRECTION_MASK_NORTH) << 1;
		result |= (constraint & mxConstants.DIRECTION_MASK_SOUTH) >> 1;
		result |= (constraint & mxConstants.DIRECTION_MASK_EAST) >> 3;

		return result;
	}

	/**
	 * Draws the image inside the clip bounds to the given graphics object.
	 */
	public static void drawImageClip(Graphics g, BufferedImage image,
			ImageObserver observer)
	{
		Rectangle clip = g.getClipBounds();

		if (clip != null)
		{
			int w = image.getWidth();
			int h = image.getHeight();

			int x = Math.max(0, Math.min(clip.x, w));
			int y = Math.max(0, Math.min(clip.y, h));

			w = Math.min(clip.width, w - x);
			h = Math.min(clip.height, h - y);

			if (w > 0 && h > 0)
			{
				// TODO: Support for normal images using fast subimage copies
				g.drawImage(image.getSubimage(x, y, w, h), clip.x, clip.y,
						observer);
			}
		}
		else
		{
			g.drawImage(image, 0, 0, observer);
		}
	}

	/**
	 * 
	 */
	public static void fillClippedRect(Graphics g, int x, int y, int width,
			int height)
	{
		Rectangle bg = new Rectangle(x, y, width, height);

		try
		{
			if (g.getClipBounds() != null)
			{
				bg = bg.intersection(g.getClipBounds());
			}
		}
		catch (Exception e)
		{
			log.log(Level.SEVERE, "Failed to compute intersection", e);
			// FIXME: Getting clipbounds sometimes throws an NPE
		}

		g.fillRect(bg.x, bg.y, bg.width, bg.height);
	}

	/**
	 * Creates a new list of new points obtained by translating the points in
	 * the given list by the given vector. Elements that are not mxPoints are
	 * added to the result as-is.
	 */
	public static List<mxPoint> translatePoints(List<mxPoint> pts, double dx,
			double dy)
	{
		List<mxPoint> result = null;

		if (pts != null)
		{
			result = new ArrayList<mxPoint>(pts.size());
			Iterator<mxPoint> it = pts.iterator();

			while (it.hasNext())
			{
				mxPoint point = (mxPoint) it.next().clone();

				point.setX(point.getX() + dx);
				point.setY(point.getY() + dy);

				result.add(point);
			}
		}

		return result;
	}

	/**
	 * Returns the intersection of two lines as an mxPoint.
	 * 
	 * @param x0
	 *            X-coordinate of the first line's startpoint.
	 * @param y0
	 *            Y-coordinate of the first line's startpoint.
	 * @param x1
	 *            X-coordinate of the first line's endpoint.
	 * @param y1
	 *            Y-coordinate of the first line's endpoint.
	 * @param x2
	 *            X-coordinate of the second line's startpoint.
	 * @param y2
	 *            Y-coordinate of the second line's startpoint.
	 * @param x3
	 *            X-coordinate of the second line's endpoint.
	 * @param y3
	 *            Y-coordinate of the second line's endpoint.
	 * @return Returns the intersection between the two lines.
	 */
	public static mxPoint intersection(double x0, double y0, double x1,
			double y1, double x2, double y2, double x3, double y3)
	{
		double denom = ((y3 - y2) * (x1 - x0)) - ((x3 - x2) * (y1 - y0));
		double nume_a = ((x3 - x2) * (y0 - y2)) - ((y3 - y2) * (x0 - x2));
		double nume_b = ((x1 - x0) * (y0 - y2)) - ((y1 - y0) * (x0 - x2));

		double ua = nume_a / denom;
		double ub = nume_b / denom;

		if (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0)
		{
			// Get the intersection point
			double intersectionX = x0 + ua * (x1 - x0);
			double intersectionY = y0 + ua * (y1 - y0);

			return new mxPoint(intersectionX, intersectionY);
		}

		// No intersection
		return null;
	}

	/**
	 * Sorts the given cells according to the order in the cell hierarchy.
	 */
	public static Object[] sortCells(Object[] cells, final boolean ascending)
	{
		return sortCells(Arrays.asList(cells), ascending).toArray();
	}

	/**
	 * Sorts the given cells according to the order in the cell hierarchy.
	 */
	public static Collection<Object> sortCells(Collection<Object> cells,
			final boolean ascending)
	{
		SortedSet<Object> result = new TreeSet<Object>(new Comparator<Object>()
		{
			public int compare(Object o1, Object o2)
			{
				int comp = mxCellPath.compare(mxCellPath.create((mxICell) o1),
						mxCellPath.create((mxICell) o2));

				return (comp == 0) ? 0 : (((comp > 0) == ascending) ? 1 : -1);
			}
		});

		result.addAll(cells);

		return result;
	}

	/**
	 * Returns true if the given array contains the given object.
	 */
	public static boolean contains(Object[] array, Object obj)
	{
		return indexOf(array, obj) >= 0;
	}

	/**
	 * Returns the index of the given object in the given array of -1 if the
	 * object is not contained in the array.
	 */
	public static int indexOf(Object[] array, Object obj)
	{
		if (obj != null && array != null)
		{
			for (int i = 0; i < array.length; i++)
			{
				if (array[i] == obj)
				{
					return i;
				}
			}
		}

		return -1;
	}

	/**
	 * Returns the stylename in a style of the form stylename[;key=value] or an
	 * empty string if the given style does not contain a stylename.
	 * 
	 * @param style
	 *            String of the form stylename[;key=value].
	 * @return Returns the stylename from the given formatted string.
	 * @deprecated Use <code>mxStyleUtils.getStylename(String)</code> (Jan 2012)
	 */
	public static String getStylename(String style)
	{
		return mxStyleUtils.getStylename(style);
	}

	/**
	 * Returns the stylenames in a style of the form stylename[;key=value] or an
	 * empty array if the given style does not contain any stylenames.
	 * 
	 * @param style
	 *            String of the form stylename[;stylename][;key=value].
	 * @return Returns the stylename from the given formatted string.
	 * @deprecated Use <code>mxStyleUtils.getStylenames(String)</code> (Jan 2012)
	 */
	public static String[] getStylenames(String style)
	{
		return mxStyleUtils.getStylenames(style);
	}

	/**
	 * Returns the index of the given stylename in the given style. This returns
	 * -1 if the given stylename does not occur (as a stylename) in the given
	 * style, otherwise it returns the index of the first character.
	 * @deprecated Use <code>mxStyleUtils.indexOfStylename(String, String)</code> (Jan 2012)
	 */
	public static int indexOfStylename(String style, String stylename)
	{
		return mxStyleUtils.indexOfStylename(style, stylename);
	}

	/**
	 * Removes all stylenames from the given style and returns the updated
	 * style.
	 * @deprecated Use <code>mxStyleUtils.removeAllStylenames(String)</code> (Jan 2012)
	 */
	public static String removeAllStylenames(String style)
	{
		return mxStyleUtils.removeAllStylenames(style);
	}

	/**
	 * Assigns the value for the given key in the styles of the given cells, or
	 * removes the key from the styles if the value is null.
	 * 
	 * @param model
	 *            Model to execute the transaction in.
	 * @param cells
	 *            Array of cells to be updated.
	 * @param key
	 *            Key of the style to be changed.
	 * @param value
	 *            New value for the given key.
	 * @deprecated Use <code>mxStyleUtils.setCellStyles(mxIGraphModel, Object[], String, String)</code> (Jan 2012)
	 */
	public static void setCellStyles(mxIGraphModel model, Object[] cells,
			String key, String value)
	{
