--- a/origin-src/transitfeed-1.2.6/test/testshapelib.py
+++ b/origin-src/transitfeed-1.2.6/test/testshapelib.py
@@ -1,1 +1,373 @@
-
+#!/usr/bin/python2.4
+#
+# Copyright (C) 2007 Google Inc.
+#
+# Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Tests for transitfeed.shapelib.py"""
+
+__author__ = 'chris.harrelson.code@gmail.com (Chris Harrelson)'
+
+import math
+from transitfeed import shapelib
+from transitfeed.shapelib import Point
+from transitfeed.shapelib import Poly
+from transitfeed.shapelib import PolyCollection
+from transitfeed.shapelib import PolyGraph
+import unittest
+import util
+
+
+def formatPoint(p, precision=12):
+  formatString = "(%%.%df, %%.%df, %%.%df)" % (precision, precision, precision)
+  return formatString % (p.x, p.y, p.z)
+
+
+def formatPoints(points):
+    return "[%s]" % ", ".join([formatPoint(p, precision=4) for p in points])
+
+
+class ShapeLibTestBase(util.TestCase):
+  def assertApproxEq(self, a, b):
+    self.assertAlmostEqual(a, b, 8)
+
+  def assertPointApproxEq(self, a, b):
+    try:
+      self.assertApproxEq(a.x, b.x)
+      self.assertApproxEq(a.y, b.y)
+      self.assertApproxEq(a.z, b.z)
+    except AssertionError:
+      print 'ERROR: %s != %s' % (formatPoint(a), formatPoint(b))
+      raise
+
+  def assertPointsApproxEq(self, points1, points2):
+    try:
+      self.assertEqual(len(points1), len(points2))
+    except AssertionError:
+      print "ERROR: %s != %s" % (formatPoints(points1), formatPoints(points2))
+      raise
+    for i in xrange(len(points1)):
+      try:
+        self.assertPointApproxEq(points1[i], points2[i])
+      except AssertionError:
+        print ('ERROR: points not equal in position %d\n%s != %s'
+               % (i, formatPoints(points1), formatPoints(points2)))
+        raise
+
+
+class TestPoints(ShapeLibTestBase):
+  def testPoints(self):
+    p = Point(1, 1, 1)
+
+    self.assertApproxEq(p.DotProd(p), 3)
+
+    self.assertApproxEq(p.Norm2(), math.sqrt(3))
+
+    self.assertPointApproxEq(Point(1.5, 1.5, 1.5),
+                                    p.Times(1.5))
+
+    norm = 1.7320508075688772
+    self.assertPointApproxEq(p.Normalize(),
+                                    Point(1 / norm,
+                                          1 / norm,
+                                          1 / norm))
+
+    p2 = Point(1, 0, 0)
+    self.assertPointApproxEq(p2, p2.Normalize())
+
+  def testCrossProd(self):
+    p1 = Point(1, 0, 0).Normalize()
+    p2 = Point(0, 1 ,0).Normalize()
+    p1_cross_p2 = p1.CrossProd(p2)
+    self.assertApproxEq(p1_cross_p2.x, 0)
+    self.assertApproxEq(p1_cross_p2.y, 0)
+    self.assertApproxEq(p1_cross_p2.z, 1)
+
+  def testRobustCrossProd(self):
+    p1 = Point(1, 0, 0)
+    p2 = Point(1, 0, 0)
+    self.assertPointApproxEq(Point(0, 0, 0),
+                                    p1.CrossProd(p2))
+    # only needs to be an arbitrary vector perpendicular to (1, 0, 0)
+    self.assertPointApproxEq(
+        Point(0.000000000000000, -0.998598452020993, 0.052925717957113),
+        p1.RobustCrossProd(p2))
+
+  def testS2LatLong(self):
+    point = Point.FromLatLng(30, 40)
+    self.assertPointApproxEq(Point(0.663413948169,
+                                          0.556670399226,
+                                          0.5), point)
+    (lat, lng) = point.ToLatLng()
+    self.assertApproxEq(30, lat)
+    self.assertApproxEq(40, lng)
+
+  def testOrtho(self):
+    point = Point(1, 1, 1)
+    ortho = point.Ortho()
+    self.assertApproxEq(ortho.DotProd(point), 0)
+
+  def testAngle(self):
+    point1 = Point(1, 1, 0).Normalize()
+    point2 = Point(0, 1, 0)
+    self.assertApproxEq(45, point1.Angle(point2) * 360 / (2 * math.pi))
+    self.assertApproxEq(point1.Angle(point2), point2.Angle(point1))
+
+  def testGetDistanceMeters(self):
+    point1 = Point.FromLatLng(40.536895,-74.203033)
+    point2 = Point.FromLatLng(40.575239,-74.112825)
+    self.assertApproxEq(8732.623770873237,
+                        point1.GetDistanceMeters(point2))
+
+
+class TestClosestPoint(ShapeLibTestBase):
+  def testGetClosestPoint(self):
+    x = Point(1, 1, 0).Normalize()
+    a = Point(1, 0, 0)
+    b = Point(0, 1, 0)
+
+    closest = shapelib.GetClosestPoint(x, a, b)
+    self.assertApproxEq(0.707106781187, closest.x)
+    self.assertApproxEq(0.707106781187, closest.y)
+    self.assertApproxEq(0.0, closest.z)
+
+
+class TestPoly(ShapeLibTestBase):
+  def testGetClosestPointShape(self):
+    poly = Poly()
+
+    poly.AddPoint(Point(1, 1, 0).Normalize())
+    self.assertPointApproxEq(Point(
+        0.707106781187, 0.707106781187, 0), poly.GetPoint(0))
+
+    point = Point(0, 1, 1).Normalize()
+    self.assertPointApproxEq(Point(1, 1, 0).Normalize(),
+                                    poly.GetClosestPoint(point)[0])
+
+    poly.AddPoint(Point(0, 1, 1).Normalize())
+
+    self.assertPointApproxEq(
+        Point(0, 1, 1).Normalize(),
+        poly.GetClosestPoint(point)[0])
+
+  def testCutAtClosestPoint(self):
+    poly = Poly()
+    poly.AddPoint(Point(0, 1, 0).Normalize())
+    poly.AddPoint(Point(0, 0.5, 0.5).Normalize())
+    poly.AddPoint(Point(0, 0, 1).Normalize())
+
+    (before, after) = \
+       poly.CutAtClosestPoint(Point(0, 0.3, 0.7).Normalize())
+
+    self.assert_(2 == before.GetNumPoints())
+    self.assert_(2 == before.GetNumPoints())
+    self.assertPointApproxEq(
+        Point(0, 0.707106781187, 0.707106781187), before.GetPoint(1))
+
+    self.assertPointApproxEq(
+        Point(0, 0.393919298579, 0.919145030018), after.GetPoint(0))
+
+    poly = Poly()
+    poly.AddPoint(Point.FromLatLng(40.527035999999995, -74.191265999999999))
+    poly.AddPoint(Point.FromLatLng(40.526859999999999, -74.191140000000004))
+    poly.AddPoint(Point.FromLatLng(40.524681000000001, -74.189579999999992))
+    poly.AddPoint(Point.FromLatLng(40.523128999999997, -74.188467000000003))
+    poly.AddPoint(Point.FromLatLng(40.523054999999999, -74.188676000000001))
+    pattern = Poly()
+    pattern.AddPoint(Point.FromLatLng(40.52713,
+                                      -74.191146000000003))
+    self.assertApproxEq(14.564268281551, pattern.GreedyPolyMatchDist(poly))
+
+  def testMergePolys(self):
+    poly1 = Poly(name="Foo")
+    poly1.AddPoint(Point(0, 1, 0).Normalize())
+    poly1.AddPoint(Point(0, 0.5, 0.5).Normalize())
+    poly1.AddPoint(Point(0, 0, 1).Normalize())
+    poly1.AddPoint(Point(1, 1, 1).Normalize())
+
+    poly2 = Poly()
+    poly3 = Poly(name="Bar")
+    poly3.AddPoint(Point(1, 1, 1).Normalize())
+    poly3.AddPoint(Point(2, 0.5, 0.5).Normalize())
+
+    merged1 = Poly.MergePolys([poly1, poly2])
+    self.assertPointsApproxEq(poly1.GetPoints(), merged1.GetPoints())
+    self.assertEqual("Foo;", merged1.GetName())
+
+    merged2 = Poly.MergePolys([poly2, poly3])
+    self.assertPointsApproxEq(poly3.GetPoints(), merged2.GetPoints())
+    self.assertEqual(";Bar", merged2.GetName())
+
+    merged3 = Poly.MergePolys([poly1, poly2, poly3], merge_point_threshold=0)
+    mergedPoints = poly1.GetPoints()[:]
+    mergedPoints.append(poly3.GetPoint(-1))
+    self.assertPointsApproxEq(mergedPoints, merged3.GetPoints())
+    self.assertEqual("Foo;;Bar", merged3.GetName())
+
+    merged4 = Poly.MergePolys([poly2])
+    self.assertEqual("", merged4.GetName())
+    self.assertEqual(0, merged4.GetNumPoints())
+
+    # test merging two nearby points
+    newPoint = poly1.GetPoint(-1).Plus(Point(0.000001, 0, 0)).Normalize()
+    poly1.AddPoint(newPoint)
+    distance = poly1.GetPoint(-1).GetDistanceMeters(poly3.GetPoint(0))
+    self.assertTrue(distance <= 10)
+    self.assertTrue(distance > 5)
+
+    merged5 = Poly.MergePolys([poly1, poly2, poly3], merge_point_threshold=10)
+    mergedPoints = poly1.GetPoints()[:]
+    mergedPoints.append(poly3.GetPoint(-1))
+    self.assertPointsApproxEq(mergedPoints, merged5.GetPoints())
+    self.assertEqual("Foo;;Bar", merged5.GetName())
+
+    merged6 = Poly.MergePolys([poly1, poly2, poly3], merge_point_threshold=5)
+    mergedPoints = poly1.GetPoints()[:]
+    mergedPoints += poly3.GetPoints()
+    self.assertPointsApproxEq(mergedPoints, merged6.GetPoints())
+    self.assertEqual("Foo;;Bar", merged6.GetName())
+
+  def testReversed(self):
+    p1 = Point(1, 0, 0).Normalize()
+    p2 = Point(0, 0.5, 0.5).Normalize()
+    p3 = Point(0.3, 0.8, 0.5).Normalize()
+    poly1 = Poly([p1, p2, p3])
+    self.assertPointsApproxEq([p3, p2, p1], poly1.Reversed().GetPoints())
+
+  def testLengthMeters(self):
+    p1 = Point(1, 0, 0).Normalize()
+    p2 = Point(0, 0.5, 0.5).Normalize()
+    p3 = Point(0.3, 0.8, 0.5).Normalize()
+    poly0 = Poly([p1])
+    poly1 = Poly([p1, p2])
+    poly2 = Poly([p1, p2, p3])
+    try:
+      poly0.LengthMeters()
+      self.fail("Should have thrown AssertionError")
+    except AssertionError:
+      pass
+
+    p1_p2 = p1.GetDistanceMeters(p2)
+    p2_p3 = p2.GetDistanceMeters(p3)
+    self.assertEqual(p1_p2, poly1.LengthMeters())
+    self.assertEqual(p1_p2 + p2_p3, poly2.LengthMeters())
+    self.assertEqual(p1_p2 + p2_p3, poly2.Reversed().LengthMeters())
+
+
+class TestCollection(ShapeLibTestBase):
+  def testPolyMatch(self):
+    poly = Poly()
+    poly.AddPoint(Point(0, 1, 0).Normalize())
+    poly.AddPoint(Point(0, 0.5, 0.5).Normalize())
+    poly.AddPoint(Point(0, 0, 1).Normalize())
+
+    collection = PolyCollection()
+    collection.AddPoly(poly)
+    match = collection.FindMatchingPolys(Point(0, 1, 0),
+                                         Point(0, 0, 1))
+    self.assert_(len(match) == 1 and match[0] == poly)
+
+    match = collection.FindMatchingPolys(Point(0, 1, 0),
+                                         Point(0, 1, 0))
+    self.assert_(len(match) == 0)
+
+    poly = Poly()
+    poly.AddPoint(Point.FromLatLng(45.585212,-122.586136))
+    poly.AddPoint(Point.FromLatLng(45.586654,-122.587595))
+    collection = PolyCollection()
+    collection.AddPoly(poly)
+
+    match = collection.FindMatchingPolys(
+        Point.FromLatLng(45.585212,-122.586136),
+        Point.FromLatLng(45.586654,-122.587595))
+    self.assert_(len(match) == 1 and match[0] == poly)
+
+    match = collection.FindMatchingPolys(
+        Point.FromLatLng(45.585219,-122.586136),
+        Point.FromLatLng(45.586654,-122.587595))
+    self.assert_(len(match) == 1 and match[0] == poly)
+
+    self.assertApproxEq(0.0, poly.GreedyPolyMatchDist(poly))
+
+    match = collection.FindMatchingPolys(
+        Point.FromLatLng(45.587212,-122.586136),
+        Point.FromLatLng(45.586654,-122.587595))
+    self.assert_(len(match) == 0)
+
+
+class TestGraph(ShapeLibTestBase):
+  def testReconstructPath(self):
+    p1 = Point(1, 0, 0).Normalize()
+    p2 = Point(0, 0.5, 0.5).Normalize()
+    p3 = Point(0.3, 0.8, 0.5).Normalize()
+    poly1 = Poly([p1, p2])
+    poly2 = Poly([p3, p2])
+    came_from = {
+        p2: (p1, poly1),
+        p3: (p2, poly2)
+    }
+
+    graph = PolyGraph()
+    reconstructed1 = graph._ReconstructPath(came_from, p1)
+    self.assertEqual(0, reconstructed1.GetNumPoints())
+
+    reconstructed2 = graph._ReconstructPath(came_from, p2)
+    self.assertPointsApproxEq([p1, p2], reconstructed2.GetPoints())
+
+    reconstructed3 = graph._ReconstructPath(came_from, p3)
+    self.assertPointsApproxEq([p1, p2, p3], reconstructed3.GetPoints())
+
+  def testShortestPath(self):
+    p1 = Point(1, 0, 0).Normalize()
+    p2 = Point(0, 0.5, 0.5).Normalize()
+    p3 = Point(0.3, 0.8, 0.5).Normalize()
+    p4 = Point(0.7, 0.7, 0.5).Normalize()
+    poly1 = Poly([p1, p2, p3], "poly1")
+    poly2 = Poly([p4, p3], "poly2")
+    poly3 = Poly([p4, p1], "poly3")
+    graph = PolyGraph()
+    graph.AddPoly(poly1)
+    graph.AddPoly(poly2)
+    graph.AddPoly(poly3)
+    path = graph.ShortestPath(p1, p4)
+    self.assert_(path is not None)
+    self.assertPointsApproxEq([p1, p4], path.GetPoints())
+
+    path = graph.ShortestPath(p1, p3)
+    self.assert_(path is not None)
+    self.assertPointsApproxEq([p1, p4, p3], path.GetPoints())
+
+    path = graph.ShortestPath(p3, p1)
+    self.assert_(path is not None)
+    self.assertPointsApproxEq([p3, p4, p1], path.GetPoints())
+
+  def testFindShortestMultiPointPath(self):
+    p1 = Point(1, 0, 0).Normalize()
+    p2 = Point(0.5, 0.5, 0).Normalize()
+    p3 = Point(0.5, 0.5, 0.1).Normalize()
+    p4 = Point(0, 1, 0).Normalize()
+    poly1 = Poly([p1, p2, p3], "poly1")
+    poly2 = Poly([p4, p3], "poly2")
+    poly3 = Poly([p4, p1], "poly3")
+    graph = PolyGraph()
+    graph.AddPoly(poly1)
+    graph.AddPoly(poly2)
+    graph.AddPoly(poly3)
+    path = graph.FindShortestMultiPointPath([p1, p3, p4])
+    self.assert_(path is not None)
+    self.assertPointsApproxEq([p1, p2, p3, p4], path.GetPoints())
+
+
+if __name__ == '__main__':
+  unittest.main()
+