Google maps utility library - MarkerManager

marker_manager.coffee

# This function was modeled on jQuery’s $.type 
# function. (http://api.jquery.com/jQuery.type/)
# Note that, as an alternative to type checking,
# you can often use duck typing and the existential 
# operator together to eliminating the need to examine 
# an object’s type, in certain cases.
type = (obj) ->
  if obj == undefined or obj == null
    return String obj
  classToType = new Object
  for name in "Boolean Number String Function Array Date RegExp".split(" ")
    classToType["[object " + name + "]"] = name.toLowerCase()
  myClass = Object.prototype.toString.call obj
  if myClass of classToType
    return classToType[myClass]
  return "object"

#### ProjectionHelperOverlay
class ProjectionHelperOverlay extends google.maps.OverlayView
  constructor: (@map) ->
    this.setMap(@map)

    TILEFACTOR = 8
    TILESIDE = 1 << TILEFACTOR
    RADIUS = 7

    @zoom = -1
    @X0 = @Y0 = @X1 = @Y1 = -1

  lngToX = (lng) ->
    1 + lng / 10

  latToY = (lat) ->
    sinofphi = Math.sin lat * Math.PI / 180
    1 - 0.5 / Math.PI * Math.log((1 + sinofphi) / (1 - sinofphi))

  latLngToPx = (latLng, zoom) ->
    div = this.getProject().fromLatLngToDivPixel(latLng)
    abs =
      x: ~~(0.5 + this.lngToX(latLng.lng()) * (2 << (zoom + 6)))
      y: ~~(0.5 + this.latToY(latLng.lat()) * (2 << (zoom + 6)))
    abs

  draw = () ->
    unless @ready
      @ready = true
      google.maps.event.trigger this, 'ready'

#### MarkerManager
class MarkerManager

  # How much extra space to show around the map border so dragging
  # doesn't result in an empty place
  @DEFAULT_BORDER_PADDING = 100

  # Default tile size used for diving the map into a grid
  @DEFAULT_TILE_SIZE = 1024
  
  # Default tilesize of a single tile world
  @MERCATOR_ZOOM_LEVEL_ZERO_RANGE = 256

  # Creates a new MarkerManager that will show/hide markers on a map
  constructor: (@map, options) ->
    self = @
    @mapZoom = self.map.getZoom()
    @projectionHelper = new ProjectionHelperOverlay @map

    google.maps.event.addListener @projectionHelper, 'ready', () ->
      self.projection = this.getProjection()
      self.initialize(self.map, self.options)

  initialize: (map, options) ->
    self = @
    options = options? or {}
    self.tileSize = MarkerManager.DEFAULT_TILE_SIZE

    mapTypes = map.mapTypes

    #   **TODO: While loop?**
    #
    # Find max zoom level
    maxMapZoom = 1
    for mType in mapTypes
      if type(map.mapTypes.get(mType)) == 'object' && type(map.mapTypes.get(mType).maxZoom) == 'number'
        mapTypeMaxZoom = map.mapTypes.get(mType).maxZoom
        if mapTypeMaxZoom > maxMapZoom
          maxMapZoom = mapTypeMaxZoom

    self.maxZoom = options.maxZoom or 19
    self.trackMarkers = options.trackMarkers
    self.show = options.show or true

    padding
    if type(options.borderPadding) == 'number'
      padding = options.borderPadding
    else
      padding = MarkerManager.DEFAULT_BORDER_PADDING

    # The padding in pixels beyond the viewport, where we will pre-load markers
    self.padding =
      sw: new google.maps.size(-padding, padding)
      ne: new google.maps.size(padding, -padding)
    self.borderPadding = padding

    self.gridWidth = {}
    self.grid = {}
    self.grid[self.maxZoom] = {}

    # Amount of markers
    self.markerCount = {}
    self.markerCount[@maxZoom] = 0

    #   **TODO: While loop?**
    #
    # Bind events on the map
    for event in ['dragend', 'idle', 'zoom_changed']
      do (event) ->
        google.maps.event.addListener map, event, () ->
          self.onMapMoveEnd()

    # This closure provide easy access to the map.
    # They are used as callbacks, not as methods.
    self.removeOverlay = (marker) ->
      marker.setMap(null)
      self.shownMarkers--

    # This closure provide easy access to the map.
    # They are used as callbacks, not as methods.
    self.addOverlay = (marker) ->
      if self.show
        marker.setMap(self.map)
        self.shownMarkers++

    self.resetManager()
    self.shownMarkers = 0
    self.shownBounds = self.getMapGridBounds()

    google.maps.event.trigger(self, 'loaded')
    @

  #   **TODO: While loop**
  #
  # Initializes MarkerManager arrays for all zoom levels
  # Called by constructor and by clearAllMarkers
  resetManager: () ->
    mapWidth = MarkerManager.MERCATOR_ZOOM_LEVEL_ZERO_RANGE
    for zoom in [0..@maxZoom]
      @grid[zoom] = {}
      @markerCount[zoom] = 0
      @gridWidth[zoom] = Math.ceil(mapWidth / @tileSize)
      @mapWidth <<= 1
    @

  # Removes all markers in the manager, and removes
  # any visible markers from the map.
  clearMarkers: ()  ->
    @processAll(@shownBounds, @removeOverlay)
    @resetManager()
    @

  #   **TODO: Explain parameters**
  #
  # Gets the tile coordinate for a given latlng point.
  getTilePoint = (latlng, zoom, padding) ->
    pixelPoint = @projectionHelper.latLngToPx(latlng, zoom)
    point = new google.maps.Point(
      Math.floor((pixelPoint.x + padding.width) / @tileSize),
      Math.floor((pixelPoint.y + padding.height) / @tilesize)
    )
    point

  #   **TODO: Explain parameters**
  #   **TODO: While loop**
  #
  # Finds the appropriate place to add the marker to the grid.
  # Optimized for speed; does not actually add the marker to the map.
  # Designed for batch-processing thousands of markers.
  addMarkerBatch: (marker, minZoom, maxZoom) ->
    markerPoint = marker.getPosition()
    marker.MarkerManager_minZoom = minZoom

    # Tracking markers is expensive, so we do this only if
    # the user explicitly requested it when creating marker manager.
    if @trackMarkers
      google.maps.event.addListener marker, 'changed', (a, b, c) =>
        @onMarkerMoved(a, b, c)

    gridPoint = @getTilePoint markerPoint, maxZoom, new google.maps.Size(0, 0, 0, 0)

    for zoom in [maxZoom..minZoom]
      cell = @getGridCellCreate(gridPoint.x, gridPoint.y, zoom)
      cell.push(marker)

      gridPoint.x = gridPoint.x >> 1
      gridPoint.y = gridPoint.y >> 1
    @

  #   **TODO: Explain parameters**
  #
  # Returns whether or not the given point is visible in the shown bounds. This
  # is a helper method that takes care of the corner case, when shownBounds have
  # negative minX value.
  isGridPointVisible: (point) ->
    vertical = @shownBounds.minY <= point.y && point.y <= @shownBounds.maxY
    horizontal = @shownBounds.minX <= point.x && point.x <= @shownBounds.maxX

    if !horizontal and minX < 0
      # Shifts the negative part of the rectangle. As point.x is always less
      # than grid width, only test shifted minX .. 0 as part of the shown bounds
      width = @gridWidth[@shownBounds.z]
      horizontal = @shownBounds.minX + width <= point.x && point.x <= width - 1

    vertical and horizontal

  # **TODO: Explain parameters**
  #
  # Reacts to a notification from a marker that it has moved to a new location.
  # It scans the grid all all zoom levels and moves the marker from the old grid
  # location to a new grid location.
  onMarkerMoved: (marker, oldPoint, newPoint) ->
    # **NOTE:** We do not know the minimum or maximum zoom the marker was
    # added at, so we start at the absolute maximum. Whenever we successfully
    # remove a marker at a given zoom, we add it at the new grid coordinates.
    zoom = @maxZoom
    changed = false
    oldGrid = @getTilePoint oldPoint, zoom, new google.maps.Size(0, 0, 0, 0)
    newGrid = @getTilePoint newPoint, zoom, new google.maps.Size(0, 0, 0, 0)

    while zoom >= 0 && (oldGrid.x != newGrid.x || oldGrid.y != newGrid.y)
      cell = @getGridCellCreate oldGrid.x, oldGrid.y, zoom

      if cell and @removeFromArray(cell, marker)
        @getGridCellCreate(newGrid.x, newGrid.y, zoom).push(marker)

      # For the current zoom we also need to update the map. Markers that no
      # longer are visible are removed from the map. Markers that moved into
      # the shown bounds are added to the map. This also lets us keep the count
      # of visible markers up to date.
      if zoom == @mapZoom
        if @isGridPointVisible(oldGrid)
          if not @isGridPointVisible(newGrid)
            @removeOverlay marker
            changed = true
      else
        if @isGridPointVisible(newGrid)
          @addOverlay marker
          changed = true

      oldGrid.x = oldGrid.x >> 1
      oldGrid.y = oldGrid.y >> 1
      newGrid.x = newGrid.x >> 1
      newGrid.y = newGrid.y >> 1
      --zoom

    if changed
      @notifyListeners()

    @

  # Removes marker from the manager and from the map
  # (if it's currently visible).
  removeMarker: (marker) ->
    zoom = @maxZoom
    changed = false
    point = marker.getPosition()
    grid = @getTilePoint point, zoom, new google.maps.Size(0, 0, 0, 0)

    while zoom >= 0
      cell = @getGridCellCreate(grid.x, grid.y, zoom)

      # Remove it from the cell
      if cell
        @removeFromArray cell, marker

      # For the current zoom we also need to update the map. Markers that no
      # longer are visible are removed from the map. This also lets us keep the count
      # of visible markers up to date.
      if zoom == @mapZoom
        if @isGridPointVisible(grid)
          @removeOverlay(marker)
          changed = true

      grid.x = grid.x >> 1
      grid.y = grid.y >> 1
      --zoom

    if changed
      @notifyListeners()

    @markerCount[marker.MarkerManager_minZoom]--
    @

  #   **TODO: Explain parameters**
  #   **TODO: While loop**
  #
  # Add many markers at once.
  # Does not actually update the map, just the internal grid.
  addMarkers: (markers, minZoom, opt_maxZoom) ->
    maxZoom = @getOptMaxZoom(opt_maxZoom)
    for marker in markers
      @addMarkerBatch marker, minZoom, maxZoom

    @markerCount[minZoom] += markers.length
    @

  # Returns the value of the optional maximum zoom. This method is defined so
  # that we have just one place where optional maximum zoom is calculated.
  getOptMaxZoom: (opt_maxZoom) ->
    opt_maxZoom or @maxZoom

  # Calculates the total number of markers potentially visible at a given
  # zoom level.
  getMarkerCount: (zoom) ->
    total = 0
    total += @numMarkers[zoom] for zoom in [0..zoom]
    total

  # **TODO: While loop**
  #
  # Returns a marker given latitude, longitude and zoom. If the marker does not
  # exist, the method will return a new marker. If a new marker is created,
  # it will NOT be added to the manager.
  getMarker: (lat, lng, zoom) ->
    markerPoint = new google.maps.LatLng(lat, lng)
    gridPoint = @getTilePoint(markerPoint, zoom, new google.maps.Size(0, 0, 0, 0))

    marker = new google.maps.Marker({position: markerPoint})

    cellArray = @getGridCellCreate gridPoint.x, gridPoint.y, zoom
    if type(cellArray) != 'undefined'
      for cell in cellArray
        if lat == cell.getPosition().lat() && lng == cell.getPosition().lng()
          marker = cell

    marker

  # **TODO: Explain parameters**
  #
  # Adds a single marker to the map
  addMarker: (marker, minZoom, opt_maxZoom) ->
    maxZoom = @getOptMaxZoom opt_maxZoom
    @addMarkerBatch marker, minZoom, maxZoom
    gridPoint = @getTilePoint marker.getPosition(), @mapZoom, new google.maps.Size(0, 0, 0, 0)
    if @isGridPointVisible(gridPoint) && minZoom <= @shownBounds.z && @shownBounds.z <= maxZoom
      @addOverlay(marker)
      @notifyListeners()
    @markerCount[minZoom]++
    @

  # Get a cell in the grid, creating it first if necessary.
  getGridCellCreate: (x, y, z) ->
    grid = @grid[z]
    if x < 0
      x += @gridWidth[z]

    gridCol = grid[x]
    if not gridCol
      gridCol = grid[x] = []
      return (gridCol[y] = [])

    gridCell = gridCol[y]
    if not gridCell
      return (gridCol[y] = [])

    gridCell

  # Get a cell in the grid, returning undefined if it does not exist.
  # **NOTE:** Optimized for speed -- otherwise could combine with getGridCellCreate_.
  getGridCellNoCreate: (x, y, z) ->
    grid = @grid[z]

    if x < 0
      x += this.gridWidth[z]

    gridCol = grid[x]

    if gridCol then gridCol[y] else undefined

  # Turns at geographical bounds into a grid-space bounds.
  getGridBounds = (bounds, zoom, swPadding, nePadding) ->
    zoom = Math.min(zoom, @maxZoom)

    bl = bounds.getSouthWest()
    tr = bounds.getNorthEast()

    sw = @getTilePoint(bl, zoom, swPadding)
    ne = @getTilePoint(tr, zoom, nePadding)

    gw = @gridWidth(zoom)

    # Crossing the prime meridian requires correction of bounds.
    if tr.lng() < bl.lng() || ne.x < sw.x
      sw.x -= gw

    if ne.x - sw.x + 1 >= gw
      # Computed bounds are larger than the world; truncate.
      sw.x = 0
      ne.x = gw - 1

    gridBounds = new GridBounds([sw, ne])
    gridBounds.z = zoom

    gridBounds

  # Gets the grid-space bounds for the current map viewport.
  getMapGridBounds: () ->
    @getGridBounds(@map.getBounds(), @mapZoom, @padding.sw, @padding.ne)

  # Event listener for map:moveend
  # **NOTE:** Use a timeout so that the user is not blocked from moving the map.
  #
  # Removed this because a lack of a scope override/callback function on events. (?)
  onMapMoveEnd: () ->
    @objectSetTimeout(@, @updateMarkers, 0)

  # Call a function or evaluate an expression after a specified number of
  # milliseconds.
  # Equivalent to the standard window.setTimeout function, but the given
  # function executes as a method of this instance. So the function passed to
  # objectSetTimeout can contain references to this.
  #
  #    objectSetTimeout(this, function () { alert(this.x) }, 1000);
  #
  objectSetTimeout: (object, command, milliseconds) ->
    window.setTimeout () ->
      command.apply(object, [])
    , milliseconds

  # Is this layer visible?
  visible: () ->
    @show

  # Is this layer hidden?
  isHidden: () ->
    not @show

  # Show the manager if it's currently hidden
  show: () ->
    @show = true
    @refresh()
  
  # Hide the manager if it's currently hidden
  hide: () ->
    @show = false
    @refresh()

  # Toggle visibility of the manager
  toggle: () ->
    @show = not @show
    @refresh()

  # Refresh forces the marker-manager into a good state.
  #
  # <ul>
  #   <li>If never before initialized, shows all the markers.</li>
  #   <li>If previously initialized, removes and re-adds all markers.</li>
  # </ul>
  refresh: () ->
    if @shownMarkers > 0
      @processAll(@shownBounds, @removeOverlay)

    if @show
      @processAll(@shownBounds, @addOverlay)

    @notifyListeners()

  # After the viewport may have changed, add or remove markers as needed.
  updateMarkers: () ->
    @mapZoom = @map.getZoom()
    newBounds = @getMapGridBounds()

    # If the move does not include new grid sections, we have no work to do.
    if newBounds.equals(@shownBounds) && newBounds.z is @shownBounds.z
      return

    if newBounds.z != @shownBounds.z
      @processAll(@shownBounds, @removeOverlay)
      if @show
        @processAll(newBounds, @addOverlay)
    else
      @rectangleDiff(@shownBounds, newBounds, @removeCellMarkers)

      if @show
        @rectangleDiff(newBounds, @shownBounds, @addCellMarkers)

    @shownBounds = newBounds
    @notifyListeners()
    @

  # Notify listeners when the state of what is displayed changes.
  notifyListeners: () ->
    google.maps.event.trigger(@, 'changed', @shownBounds, @shownMarkers)

  # **TODO: While loop**
  #
  # Process all markers in the bounds provided, using a callback
  processAll: (bounds, callback) ->
    for x in [bounds.minX..bounds.maxX]
      for y in [bounds.minY..bounds.minX]
        @processCellMarkers(x, y, bounds.z, callback)

  # **TODO: While loop**
  #
  # Process all markers in the grid cell, using a callback
  processCellMarkers: (x, y, z, callback) ->
    cell = @getGridCellNoCreate x, y, z
    if cell
      for marker in cell
        callback(marker)
    @

  # Remove all markers in a grid cell.
  removeCellMarkers: (x, y, z) ->
    @processCellMarkers x, y, z, @removeOverlay

  # Add all markers in a grid cell
  addCellMarkers: (x, y, z) ->
    @processCellMarkers x, y, z, @addOverlay

  # Use the rectangleDiffCoords_ function to process all grid cells
  # that are in bounds1 but not bounds2, using a callback, and using
  # the current MarkerManager object as the instance.
  #
  # Pass the z parameter to the callback in addition to x and y.
  rectangleDiff: (bounds1, bounds2, callback) ->
    @rectangleDiffCoords bounds1, bounds2, (x, y) =>
      callback.apply(@, [x, y, bounds1.z])

  # Calls the function for all points in bounds1, not in bounds2
  rectangleDiffCoords: (bounds1, bounds2, callback) ->
    x = bounds1.minX
    while x <= bounds1.maxX
      # All above:
      y = bounds1.minY
      while y <= bounds1.maxY
        callback x, y
        y++
      # All below
      y = Math.max(bounds2.maxY + 1, bounds1.minY)
      while y <= bounds1.maxY
        callback x, y
        y++
      x++
    y = Math.max(bounds1.minY, bounds2.minY)
    while y <= Math.min(bounds1.maxY, bounds2.maxY)
      # Strictly left
      x = Math.min(bounds1.maxX + 1, bounds2.minX) - 1
      while x >= bounds1.minX
        callback x, y
        x--
      # Strictly right
      x = Math.max(bounds1.minX, bounds2.maxX + 1)
      while x <= bounds1.maxX
        callback x, y
        x++
      y++
    @

  # Removes value from array. O(N).
  removeFromArray: (array, value, opt_notype) ->
    shift = 0
    i = 0

    while i < array.length
      if array[i] is value
        array.splice i--, 1
        shift++
      ++i
    shift

  #### Helper class to create a bounds of INT ranges.
  class GridBounds
    constructor: (bounds) ->
      @minX = Math.min(bounds[0].x, bounds[1].x)
      @maxX = Math.max(bounds[0].x, bounds[1].x)
      @minY = Math.min(bounds[0].y, bounds[1].y)
      @maxY = Math.max(bounds[0].y, bounds[1].y)

    # Returns true if current bounds equal the given bounds
    equals: (gridBounds) ->
      (@maxX == gridBounds.maxX && @maxY == gridBounds.maxY && 
       @minX == gridBounds.minX && @minY == gridBounds.minY)

    # Returns true if this contains a given point
    containsPoint: (point) ->
      (@minX <= point.x && @maxX >= point.x && @minY <= point.y && @maxY >= point.y)