Bug 684759 - Part 2 - Add DirectedGraph and gfxQuad classes. r=roc
authorMatt Woodrow <mwoodrow@mozilla.com>
Fri, 07 Oct 2011 10:22:18 +1300
changeset 78271 3ef0db7dc18dd42295595630c7536a8c979fbc85
parent 78270 72de40b3ac74e1d324e073f7a372a0d21f5eb192
child 78272 39d6e79b44ad645d6050d79877aca414b40dbeb8
push id2464
push usermwoodrow@mozilla.com
push dateThu, 06 Oct 2011 21:29:43 +0000
treeherdermozilla-inbound@2465969e8c76 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersroc
bugs684759
milestone10.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 684759 - Part 2 - Add DirectedGraph and gfxQuad classes. r=roc
gfx/layers/DirectedGraph.h
gfx/thebes/Makefile.in
gfx/thebes/gfx3DMatrix.cpp
gfx/thebes/gfx3DMatrix.h
gfx/thebes/gfxQuad.h
new file mode 100644
--- /dev/null
+++ b/gfx/layers/DirectedGraph.h
@@ -0,0 +1,148 @@
+/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla Corporation code.
+ *
+ * The Initial Developer of the Original Code is Mozilla Foundation.
+ * Portions created by the Initial Developer are Copyright (C) 2011
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Matt Woodrow <mwoodrow@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifndef GFX_DIRECTEDGRAPH_H
+#define GFX_DIRECTEDGRAPH_H
+
+#include "gfxTypes.h"
+#include "nsTArray.h"
+
+namespace mozilla {
+namespace layers {
+
+template <typename T>
+class DirectedGraph {
+public:
+
+  class Edge {
+    public:
+    Edge(T aFrom, T aTo) : mFrom(aFrom), mTo(aTo) {}
+
+    bool operator==(const Edge& aOther) const
+    {
+      return mFrom == aOther.mFrom && mTo == aOther.mTo;
+    }
+
+    T mFrom;
+    T mTo;
+  };
+
+  class RemoveEdgesToComparator 
+  {
+  public:
+    PRBool Equals(const Edge& a, T const& b) const { return a.mTo == b; }
+  };
+
+  /**
+   * Add a new edge to the graph.
+   */
+  void AddEdge(Edge aEdge)
+  {
+    NS_ASSERTION(!mEdges.Contains(aEdge), "Adding a duplicate edge!");
+    mEdges.AppendElement(aEdge);
+  }
+
+  void AddEdge(T aFrom, T aTo)
+  {
+    AddEdge(Edge(aFrom, aTo));
+  }
+
+  /**
+   * Get the list of edges.
+   */
+  const nsTArray<Edge>& GetEdgeList() const
+  {
+    return mEdges; 
+  }
+
+  /**
+   * Remove the given edge from the graph.
+   */
+  void RemoveEdge(Edge aEdge)
+  {
+    mEdges.RemoveElement(aEdge);
+  }
+
+  /**
+   * Remove all edges going into aNode.
+   */
+  void RemoveEdgesTo(T aNode)
+  {
+    RemoveEdgesToComparator c;
+    while (mEdges.RemoveElement(aNode, c)) {}
+  }
+  
+  /**
+   * Get the number of edges going into aNode.
+   */
+  unsigned int NumEdgesTo(T aNode)
+  {
+    unsigned int count = 0;
+    for (unsigned int i = 0; i < mEdges.Length(); i++) {
+      if (mEdges.ElementAt(i).mTo == aNode) {
+        count++;
+      }
+    }
+    return count;
+  }
+
+  /**
+   * Get the list of all edges going from aNode
+   */
+  void GetEdgesFrom(T aNode, nsTArray<Edge>& aResult)
+  {
+    for (unsigned int i = 0; i < mEdges.Length(); i++) {
+      if (mEdges.ElementAt(i).mFrom == aNode) {
+        aResult.AppendElement(mEdges.ElementAt(i));
+      }
+    }
+  }
+
+  /**
+   * Get the total number of edges.
+   */
+  unsigned int GetEdgeCount() { return mEdges.Length(); }
+
+private:
+
+  nsTArray<Edge> mEdges;
+};
+
+}
+}
+
+#endif // GFX_DIRECTEDGRAPH_H
--- a/gfx/thebes/Makefile.in
+++ b/gfx/thebes/Makefile.in
@@ -29,16 +29,17 @@ EXPORTS	= \
 	gfxImageSurface.h \
 	gfxMatrix.h \
 	gfxPath.h \
 	gfxPattern.h \
 	gfxPlatform.h \
 	gfxPoint.h \
 	gfxPoint3D.h \
 	gfxPointH3D.h \
+	gfxQuad.h \
 	gfxQuaternion.h \
 	gfxRect.h \
 	gfxSkipChars.h \
 	gfxTeeSurface.h \
 	gfxTypes.h \
 	gfxTextRunCache.h \
 	gfxTextRunWordCache.h \
 	gfxUnicodeProperties.h \
--- a/gfx/thebes/gfx3DMatrix.cpp
+++ b/gfx/thebes/gfx3DMatrix.cpp
@@ -662,16 +662,32 @@ gfx3DMatrix::TransformBounds(const gfxRe
     max_x = max(points[i].x, max_x);
     min_y = min(points[i].y, min_y);
     max_y = max(points[i].y, max_y);
   }
 
   return gfxRect(min_x, min_y, max_x - min_x, max_y - min_y);
 }
 
+gfxQuad 
+gfx3DMatrix::TransformRect(const gfxRect& aRect) const
+{
+  gfxPoint points[4];
+
+  points[0] = Transform(aRect.TopLeft());
+  points[1] = Transform(gfxPoint(aRect.X() + aRect.Width(), aRect.Y()));
+  points[2] = Transform(gfxPoint(aRect.X() + aRect.Width(),
+                                 aRect.Y() + aRect.Height()));
+  points[3] = Transform(gfxPoint(aRect.X(), aRect.Y() + aRect.Height()));
+
+
+  // Could this ever result in lines that intersect? I don't think so.
+  return gfxQuad(points[0], points[1], points[2], points[3]);
+}
+
 bool
 gfx3DMatrix::Is2D() const
 {
   if (_13 != 0.0f || _14 != 0.0f ||
       _23 != 0.0f || _24 != 0.0f ||
       _31 != 0.0f || _32 != 0.0f || _33 != 1.0f || _34 != 0.0f ||
       _43 != 0.0f || _44 != 1.0f) {
     return PR_FALSE;
--- a/gfx/thebes/gfx3DMatrix.h
+++ b/gfx/thebes/gfx3DMatrix.h
@@ -38,16 +38,17 @@
 
 #ifndef GFX_3DMATRIX_H
 #define GFX_3DMATRIX_H
 
 #include <gfxTypes.h>
 #include <gfxPoint3D.h>
 #include <gfxPointH3D.h>
 #include <gfxMatrix.h>
+#include <gfxQuad.h>
 
 /**
  * This class represents a 3D transformation. The matrix is laid
  * out as follows:
  *
  * _11 _12 _13 _14
  * _21 _22 _23 _24
  * _31 _32 _33 _34
@@ -242,16 +243,19 @@ public:
    */
   gfxPoint Transform(const gfxPoint& point) const;
 
   /**
    * Transforms a rectangle according to this matrix
    */
   gfxRect TransformBounds(const gfxRect& rect) const;
 
+
+  gfxQuad TransformRect(const gfxRect& aRect) const;
+
   /** 
    * Transforms a 3D vector according to this matrix.
    */
   gfxPoint3D Transform3D(const gfxPoint3D& point) const;
   gfxPointH3D Transform4D(const gfxPointH3D& aPoint) const;
   gfxPointH3D TransposeTransform4D(const gfxPointH3D& aPoint) const;
 
   gfxPoint ProjectPoint(const gfxPoint& aPoint) const;
new file mode 100644
--- /dev/null
+++ b/gfx/thebes/gfxQuad.h
@@ -0,0 +1,87 @@
+/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla Corporation code.
+ *
+ * The Initial Developer of the Original Code is Oracle Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2005
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Matt Woodrow <mwoodrow@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifndef GFX_QUAD_H
+#define GFX_QUAD_H
+
+#include "nsMathUtils.h"
+#include "mozilla/gfx/BaseSize.h"
+#include "mozilla/gfx/BasePoint.h"
+#include "nsSize.h"
+#include "nsPoint.h"
+
+#include "gfxTypes.h"
+
+static PRBool SameSideOfLine(const gfxPoint& aPoint1, const gfxPoint& aPoint2, const gfxPoint& aTest, const gfxPoint& aRef)
+{
+  // Solve the equation y - aPoint1.y - ((aPoint2.y - aPoint1.y)/(aPoint2.x - aPoint1.x))(x - aPoint1.x) for both test and ref
+  
+  gfxFloat deltaY = (aPoint2.y - aPoint1.y);
+  gfxFloat deltaX = (aPoint2.x - aPoint1.x);
+  
+  gfxFloat test = deltaX * (aTest.y - aPoint1.y) - deltaY * (aTest.x - aPoint1.x);
+  gfxFloat ref = deltaX * (aRef.y - aPoint1.y) - deltaY * (aRef.x - aPoint1.x);
+
+  // If both results have the same sign, then we're on the correct side of the line.
+  // 0 (on the line) is always considered in.
+
+  if ((test >= 0 && ref >= 0) || (test <= 0 && ref <= 0))
+    return PR_TRUE;
+  return PR_FALSE;
+}
+
+struct THEBES_API gfxQuad {
+    gfxQuad(const gfxPoint& aOne, const gfxPoint& aTwo, const gfxPoint& aThree, const gfxPoint& aFour)
+    {
+        mPoints[0] = aOne;
+        mPoints[1] = aTwo;
+        mPoints[2] = aThree;
+        mPoints[3] = aFour;
+    }
+
+    PRBool Contains(const gfxPoint& aPoint)
+    {
+        return (SameSideOfLine(mPoints[0], mPoints[1], aPoint, mPoints[2]) &&
+                SameSideOfLine(mPoints[1], mPoints[2], aPoint, mPoints[3]) &&
+                SameSideOfLine(mPoints[2], mPoints[3], aPoint, mPoints[0]) &&
+                SameSideOfLine(mPoints[3], mPoints[0], aPoint, mPoints[1]));
+    }
+
+    gfxPoint mPoints[4];
+};
+
+#endif /* GFX_QUAD_H */