#!/usr/bin/python2.5
 
# 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.
 
import bisect
 
from gtfsfactoryuser import GtfsFactoryUser
import problems as problems_module
import util
 
class Shape(GtfsFactoryUser):
  """This class represents a geographic shape that corresponds to the route
  taken by one or more Trips."""
  _REQUIRED_FIELD_NAMES = ['shape_id', 'shape_pt_lat', 'shape_pt_lon',
                           'shape_pt_sequence']
  _FIELD_NAMES = _REQUIRED_FIELD_NAMES + ['shape_dist_traveled']
  def __init__(self, shape_id):
    # List of shape point tuple (lat, lng, shape_dist_traveled), where lat and
    # lon is the location of the shape point, and shape_dist_traveled is an
    # increasing metric representing the distance traveled along the shape.
    self.points = []
    # An ID that uniquely identifies a shape in the dataset.
    self.shape_id = shape_id
    # The max shape_dist_traveled of shape points in this shape.
    self.max_distance = 0
    # List of shape_dist_traveled of each shape point.
    self.distance = []
    # List of shape_pt_sequence of each shape point.
    self.sequence = []
 
  def AddPoint(self, lat, lon, distance=None,
               problems=problems_module.default_problem_reporter):
    shapepoint_class = self.GetGtfsFactory().ShapePoint
    shapepoint = shapepoint_class(
        self.shape_id, lat, lon, len(self.sequence), distance)
    if shapepoint.ParseAttributes(problems):
      self.AddShapePointObjectUnsorted(shapepoint, problems)
 
  def AddShapePointObjectUnsorted(self, shapepoint, problems):
    """Insert a point into a correct position by sequence. """
    if (len(self.sequence) == 0 or
        shapepoint.shape_pt_sequence >= self.sequence[-1]):
      index = len(self.sequence)
    elif shapepoint.shape_pt_sequence <= self.sequence[0]:
      index = 0
    else:
      index = bisect.bisect(self.sequence, shapepoint.shape_pt_sequence)
 
    if shapepoint.shape_pt_sequence in self.sequence:
      problems.InvalidValue('shape_pt_sequence', shapepoint.shape_pt_sequence,
                            'The sequence number %d occurs more than once in '
                            'shape %s.' %
                            (shapepoint.shape_pt_sequence, self.shape_id))
 
    if shapepoint.shape_dist_traveled is not None and len(self.sequence) > 0:
      if (index != len(self.sequence) and
          shapepoint.shape_dist_traveled > self.distance[index]):
        problems.InvalidValue('shape_dist_traveled',
                              shapepoint.shape_dist_traveled,
                              'Each subsequent point in a shape should have '
                              'a distance value that shouldn\'t be larger '
                              'than the next ones. In this case, the next '
                              'distance was %f.' % self.distance[index])
 
      if (index > 0 and
          shapepoint.shape_dist_traveled < self.distance[index - 1]):
        problems.InvalidValue('shape_dist_traveled',
                              shapepoint.shape_dist_traveled,
                              'Each subsequent point in a shape should have '
                              'a distance value that\'s at least as large as '
                              'the previous ones. In this case, the previous '
                              'distance was %f.' % self.distance[index - 1])
 
    if shapepoint.shape_dist_traveled > self.max_distance:
      self.max_distance = shapepoint.shape_dist_traveled
 
    self.sequence.insert(index, shapepoint.shape_pt_sequence)
    self.distance.insert(index, shapepoint.shape_dist_traveled)
    self.points.insert(index, (shapepoint.shape_pt_lat,
                               shapepoint.shape_pt_lon,
                               shapepoint.shape_dist_traveled))
 
  def ClearPoints(self):
    self.points = []
 
  def __eq__(self, other):
    if not other:
      return False
 
    if id(self) == id(other):
      return True
 
    return self.points == other.points
 
  def __ne__(self, other):
    return not self.__eq__(other)
 
  def __repr__(self):
    return "<Shape %s>" % self.__dict__
 
  def ValidateShapeId(self, problems):
    if util.IsEmpty(self.shape_id):
      problems.MissingValue('shape_id')
 
  def ValidateShapePoints(self, problems):
    if not self.points:
      problems.OtherProblem('The shape with shape_id "%s" contains no points.' %
                            self.shape_id, type=problems_module.TYPE_WARNING)
 
  def Validate(self, problems=problems_module.default_problem_reporter):
    self.ValidateShapeId(problems)
    self.ValidateShapePoints(problems)
 
  def GetPointWithDistanceTraveled(self, shape_dist_traveled):
    """Returns a point on the shape polyline with the input shape_dist_traveled.
 
    Args:
      shape_dist_traveled: The input shape_dist_traveled.
 
    Returns:
      The shape point as a tuple (lat, lng, shape_dist_traveled), where lat and
      lng is the location of the shape point, and shape_dist_traveled is an
      increasing metric representing the distance traveled along the shape.
      Returns None if there is data error in shape.
    """
    if not self.distance:
      return None
    if shape_dist_traveled <= self.distance[0]:
      return self.points[0]
    if shape_dist_traveled >= self.distance[-1]:
      return self.points[-1]
 
    index = bisect.bisect(self.distance, shape_dist_traveled)
    (lat0, lng0, dist0) = self.points[index - 1]
    (lat1, lng1, dist1) = self.points[index]
 
    # Interpolate if shape_dist_traveled does not equal to any of the point
    # in shape segment.
    # (lat0, lng0)          (lat, lng)           (lat1, lng1)
    # -----|--------------------|---------------------|------
    #    dist0          shape_dist_traveled         dist1
    #      \------- ca --------/ \-------- bc -------/
    #       \----------------- ba ------------------/
    ca = shape_dist_traveled - dist0
    bc = dist1 - shape_dist_traveled
    ba = bc + ca
    if ba == 0:
      # This only happens when there's data error in shapes and should have been
      # catched before. Check to avoid crash.
      return None
    # This won't work crossing longitude 180 and is only an approximation which
    # works well for short distance.
    lat = (lat1 * ca + lat0 * bc) / ba
    lng = (lng1 * ca + lng0 * bc) / ba
    return (lat, lng, shape_dist_traveled)