/* 
 * MarkerManager, v1.0
 * 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. 
 *
 *
 * Author: Doug Ricket, others
 * 
 * Marker manager is an interface between the map and the user, designed
 * to manage adding and removing many points when the viewport changes.
 *
 *
 * Algorithm: The MM places its markers onto a grid, similar to the map tiles.
 * When the user moves the viewport, the MM computes which grid cells have
 * entered or left the viewport, and shows or hides all the markers in those
 * cells.
 * (If the users scrolls the viewport beyond the markers that are loaded,
 * no markers will be visible until the EVENT_moveend triggers an update.)
 *
 * In practical consequences, this allows 10,000 markers to be distributed over
 * a large area, and as long as only 100-200 are visible in any given viewport,
 * the user will see good performance corresponding to the 100 visible markers,
 * rather than poor performance corresponding to the total 10,000 markers.
 *
 * Note that some code is optimized for speed over space,
 * with the goal of accommodating thousands of markers.
 *
 */
function MarkerManager(D,E){var B=this;B.map_=D;B.mapZoom_=D.getZoom();B.projection_=D.getCurrentMapType().getProjection();E=E||{};B.tileSize_=MarkerManager.DEFAULT_TILE_SIZE_;var A=MarkerManager.DEFAULT_MAX_ZOOM_;if(E.maxZoom!=undefined){A=E.maxZoom;
}B.maxZoom_=A;B.trackMarkers_=E.trackMarkers;var C;if(typeof E.borderPadding=="number"){C=E.borderPadding;}else{C=MarkerManager.DEFAULT_BORDER_PADDING_;}B.swPadding_=new GSize(-C,C);B.nePadding_=new GSize(C,-C);B.borderPadding_=C;B.gridWidth_=[];B.grid_=[];
B.grid_[A]=[];B.numMarkers_=[];B.numMarkers_[A]=0;GEvent.bind(D,"moveend",B,B.onMapMoveEnd_);B.removeOverlay_=function(F){D.removeOverlay(F);B.shownMarkers_--;};B.addOverlay_=function(F){D.addOverlay(F);B.shownMarkers_++;};B.resetManager_();B.shownMarkers_=0;
B.shownBounds_=B.getMapGridBounds_();}MarkerManager.DEFAULT_TILE_SIZE_=1024;MarkerManager.DEFAULT_MAX_ZOOM_=17;MarkerManager.DEFAULT_BORDER_PADDING_=100;MarkerManager.MERCATOR_ZOOM_LEVEL_ZERO_RANGE=256;MarkerManager.prototype.resetManager_=function(){var C=this;
var A=MarkerManager.MERCATOR_ZOOM_LEVEL_ZERO_RANGE;for(var B=0;B<=C.maxZoom_;++B){C.grid_[B]=[];C.numMarkers_[B]=0;C.gridWidth_[B]=Math.ceil(A/C.tileSize_);A<<=1;}};MarkerManager.prototype.clearMarkers=function(){var A=this;A.processAll_(A.shownBounds_,A.removeOverlay_);
A.resetManager_();};MarkerManager.prototype.getTilePoint_=function(D,B,C){var A=this.projection_.fromLatLngToPixel(D,B);return new GPoint(Math.floor((A.x+C.width)/this.tileSize_),Math.floor((A.y+C.height)/this.tileSize_));};MarkerManager.prototype.addMarkerBatch_=function(C,G,B){var F=C.getPoint();
if(this.trackMarkers_){GEvent.bind(C,"changed",this,this.onMarkerMoved_);}var D=this.getTilePoint_(F,B,GSize.ZERO);for(var E=B;E>=G;E--){var A=this.getGridCellCreate_(D.x,D.y,E);A.push(C);D.x=D.x>>1;D.y=D.y>>1;}};MarkerManager.prototype.isGridPointVisible_=function(B){var F=this;
var D=F.shownBounds_.minY<=B.y&&B.y<=F.shownBounds_.maxY;var A=F.shownBounds_.minX;var C=A<=B.x&&B.x<=F.shownBounds_.maxX;if(!C&&A<0){var E=F.gridWidth_[F.shownBounds_.z];C=A+E<=B.x&&B.x<=E-1;}return D&&C;};MarkerManager.prototype.onMarkerMoved_=function(E,A,C){var G=this;
var I=G.maxZoom_;var D=false;var B=G.getTilePoint_(A,I,GSize.ZERO);var F=G.getTilePoint_(C,I,GSize.ZERO);while(I>=0&&(B.x!=F.x||B.y!=F.y)){var H=G.getGridCellNoCreate_(B.x,B.y,I);if(H){if(G.removeFromArray(H,E)){G.getGridCellCreate_(F.x,F.y,I).push(E);
}}if(I==G.mapZoom_){if(G.isGridPointVisible_(B)){if(!G.isGridPointVisible_(F)){G.removeOverlay_(E);D=true;}}else{if(G.isGridPointVisible_(F)){G.addOverlay_(E);D=true;}}}B.x=B.x>>1;B.y=B.y>>1;F.x=F.x>>1;F.y=F.y>>1;--I;}if(D){G.notifyListeners_();}};MarkerManager.prototype.removeMarker=function(C){var F=this;
var E=F.maxZoom_;var G=false;var B=C.getPoint();var D=F.getTilePoint_(B,E,GSize.ZERO);while(E>=0){var A=F.getGridCellNoCreate_(D.x,D.y,E);if(A){F.removeFromArray(A,C);}if(E==F.mapZoom_){if(F.isGridPointVisible_(D)){F.removeOverlay_(C);G=true;}}D.x=D.x>>1;
D.y=D.y>>1;--E;}if(G){F.notifyListeners_();}};MarkerManager.prototype.addMarkers=function(D,E,C){var A=this.getOptMaxZoom_(C);for(var B=D.length-1;B>=0;B--){this.addMarkerBatch_(D[B],E,A);}this.numMarkers_[E]+=D.length;};MarkerManager.prototype.getOptMaxZoom_=function(A){return A!=undefined?A:this.maxZoom_;
};MarkerManager.prototype.getMarkerCount=function(B){var A=0;for(var C=0;C<=B;C++){A+=this.numMarkers_[C];}return A;};MarkerManager.prototype.addMarker=function(B,F,D){var E=this;var A=this.getOptMaxZoom_(D);E.addMarkerBatch_(B,F,A);var C=E.getTilePoint_(B.getPoint(),E.mapZoom_,GSize.ZERO);
if(E.isGridPointVisible_(C)&&F<=E.shownBounds_.z&&E.shownBounds_.z<=A){E.addOverlay_(B);E.notifyListeners_();}this.numMarkers_[F]++;};MarkerManager.prototype.getGridCellCreate_=function(A,F,E){var C=this.grid_[E];if(A<0){A+=this.gridWidth_[E];}var B=C[A];
if(!B){B=C[A]=[];return B[F]=[];}var D=B[F];if(!D){return B[F]=[];}return D;};MarkerManager.prototype.getGridCellNoCreate_=function(A,E,D){var C=this.grid_[D];if(A<0){A+=this.gridWidth_[D];}var B=C[A];return B?B[E]:undefined;};MarkerManager.prototype.getGridBounds_=function(A,I,H,F){I=Math.min(I,this.maxZoom_);
var B=A.getSouthWest();var E=A.getNorthEast();var G=this.getTilePoint_(B,I,H);var D=this.getTilePoint_(E,I,F);var J=this.gridWidth_[I];if(E.lng()<B.lng()||D.x<G.x){G.x-=J;}if(D.x-G.x+1>=J){G.x=0;D.x=J-1;}var C=new GBounds([G,D]);C.z=I;return C;};MarkerManager.prototype.getMapGridBounds_=function(){var A=this;
return A.getGridBounds_(A.map_.getBounds(),A.mapZoom_,A.swPadding_,A.nePadding_);};MarkerManager.prototype.onMapMoveEnd_=function(){var A=this;A.objectSetTimeout_(this,this.updateMarkers_,0);};MarkerManager.prototype.objectSetTimeout_=function(B,C,A){return window.setTimeout(function(){C.call(B);
},A);};MarkerManager.prototype.refresh=function(){var A=this;if(A.shownMarkers_>0){A.processAll_(A.shownBounds_,A.removeOverlay_);}A.processAll_(A.shownBounds_,A.addOverlay_);A.notifyListeners_();};MarkerManager.prototype.updateMarkers_=function(){var A=this;
A.mapZoom_=this.map_.getZoom();var B=A.getMapGridBounds_();if(B.equals(A.shownBounds_)&&B.z==A.shownBounds_.z){return ;}if(B.z!=A.shownBounds_.z){A.processAll_(A.shownBounds_,A.removeOverlay_);A.processAll_(B,A.addOverlay_);}else{A.rectangleDiff_(A.shownBounds_,B,A.removeCellMarkers_);
A.rectangleDiff_(B,A.shownBounds_,A.addCellMarkers_);}A.shownBounds_=B;A.notifyListeners_();};MarkerManager.prototype.notifyListeners_=function(){GEvent.trigger(this,"changed",this.shownBounds_,this.shownMarkers_);};MarkerManager.prototype.processAll_=function(B,D){for(var A=B.minX;
A<=B.maxX;A++){for(var C=B.minY;C<=B.maxY;C++){this.processCellMarkers_(A,C,B.z,D);}}};MarkerManager.prototype.processCellMarkers_=function(B,F,D,E){var A=this.getGridCellNoCreate_(B,F,D);if(A){for(var C=A.length-1;C>=0;C--){E(A[C]);}}};MarkerManager.prototype.removeCellMarkers_=function(A,C,B){this.processCellMarkers_(A,C,B,this.removeOverlay_);
};MarkerManager.prototype.addCellMarkers_=function(A,C,B){this.processCellMarkers_(A,C,B,this.addOverlay_);};MarkerManager.prototype.rectangleDiff_=function(B,A,D){var C=this;C.rectangleDiffCoords(B,A,function(E,F){D.apply(C,[E,F,B.z]);});};MarkerManager.prototype.rectangleDiffCoords=function(B,A,L){var F=B.minX;
var M=B.minY;var H=B.maxX;var D=B.maxY;var E=A.minX;var K=A.minY;var G=A.maxX;var C=A.maxY;for(var J=F;J<=H;J++){for(var I=M;I<=D&&I<K;I++){L(J,I);}for(var I=Math.max(C+1,M);I<=D;I++){L(J,I);}}for(var I=Math.max(M,K);I<=Math.min(D,C);I++){for(var J=Math.min(H+1,E)-1;
J>=F;J--){L(J,I);}for(var J=Math.max(F,G+1);J<=H;J++){L(J,I);}}};MarkerManager.prototype.removeFromArray=function(E,C,D){var A=0;for(var B=0;B<E.length;++B){if(E[B]===C||(D&&E[B]==C)){E.splice(B--,1);A++;}}return A;};