// 마커들을 클러스터링 하기 위한 Cluster class
export class Cluster<T extends Marker> {
  ...
}
 
export const useKMeansClustering = <T extends Marker>() => {
  // 지도의 확대 수준과 지도의 반경에 대한 상태, 움직임이 일어날 때 마다 변경 됩니다.
  const { zoom, bounds } = useMapStore((state) => state.mapInfo);
 
 // API 요청이 변경 될 때 마다 캐싱된 값을 변경하기 위해 사용하는 ref
  const clusterKey = useRef<string>("");
  // 지도 이동 시 마다 값 비싼 클러스터링 연산을 시행하지 않기 위해 데이터를 캐싱해두는 ref
  const cachedMarkerIdsMap = useRef<CachedMarkerIdsMap>({});
  const cachedClusteredMarkersMap = useRef<CachedClusterdMarkersMap<T>>({});
  const cachedSingleMarkersMap = useRef<CachedSingleMarkersMap<T>>({});
 
  const getClusteredMarkers = (
    markers: T[],
    _clusterKey: ClusterKey = ""
  ): { clusteredMarkers: Cluster<T>[]; singleMarker: T[] } => {
    // 만약 클러스터 키가 변경된 경우 캐싱된 데이터를 초기화 합니다.
    if (JSON.stringify(_clusterKey) !== clusterKey.current) {
    ...
    }
 
 
    // 전체 마커에 대해 지도 내부에 있는 마커를 필터링 하고 이전에 사용되지 않은 마커를 필터링 합니다.
    const innerBoundaryMarkers = markers.filter(filterInnerBoundary);
    const nonCachedMarker = filterNonCachedMarker(innerBoundaryMarkers);
 
    // 이전에 캐싱 해둔 클러스터 중 현재 바운더리 내부에 있는 클러스터만 필터링 합니다.
 
    // 이전에 캐싱 해둔 싱글마커 중 현재 바운더리 내부에 있는 마커만 필터링 합니다.
 
    // 클러스터를 생성 할 마커들이 없다면 캐싱 된 데이터들을 반환하고 종료 합니다.
 
    // 줌 레벨에 따라 numOfCluster 를 고르고 Marker[] 에서 랜덤한 마커들의 위치로 초기 군집 위치를 생성 합니다. 이렇게 생성된 클러스터들을 clusters 라는 배열에 담습니다.
 
    // 클러스터링을 시행하는 반복문
    let isChanged = true;
    while (isChanged) {
      clusters.forEach((cluster) => cluster.clearMarke문s());
 
      nonCachedMarker.forEach((marker) => {
        const [, closestClusterIndex] = clusters.reduce(
          ([minDistance, minClusterIndex], cluster, index) => {
            const distance = cluster.calculateDistance(marker);
            return distance < minDistance
              ? [distance, index]
              : [minDistance, minClusterIndex];
          },
          [Infinity, -1]
        );
        // 가장 가까운 클러스터에게 마커를 추가합니다.
        clusters[closestClusterIndex].addMarker(marker);
      });
      // 클러스터의 중심점을 재조정합니다.
      // 이 때 모든 클러스터의 중심점이 재조정 되지 않았다면 반복문을 종료 합니다.
      isChanged = clusters.some((cluster) => cluster.revalidateCluster());
    }
 
    // 클러스터링 된 마커들과 단일 마커들을 구분지어 반환 합니다.
    // 이 때 생성된 클러스터들은 캐싱해두도록 합니다.
    clusteredMarkers = [...clusteredMarkers, ...cachedClusteredMarkers];
    singleMarker = [...singleMarker, ...cachedSingleMarkers];
 
    cachedClusteredMarkersMap.current[zoom] = clusteredMarkers;
    cachedSingleMarkersMap.current[zoom] = singleMarker;
 
    return { clusteredMarkers, singleMarker };
  };
 
  return getClusteredMarkers;
};

/**
 * @description 지도의 경계를 나타내는 타입으로 현재 보고 있는 지도 전체의 바운더리를 의미 합니다.
 */
type MapBounds = MapCameraChangedEvent["detail"]["bounds"];
/**
 * @description 타일의 경계를 나타내는 타입으로 해당 타일의 바운더리를 의미 합니다.
 */
type TileBounds = MapCameraChangedEvent["detail"]["bounds"];
/**
 * @description 마커를 나타내는 타입으로 해당 마커의 위도, 경도, 마킹 아이디, 미리보기 이미지를 의미 합니다.
 */
interface Marker extends LatLng {
  markingId: number;
  previewImage: string;
}
 
export class Tile {
  bounds: TileBounds;
  markerCount: number = 0;
  position: LatLng = { lat: 0, lng: 0 };
 
  markerMap: Map<Marker["markingId"], boolean> = new Map();
 
  previewImage: Marker["previewImage"] = "";
  markingId: Marker["markingId"] = 0;
 
  constructor(bounds: TileBounds) {
    this.bounds = bounds;
  }
 
  addMarker({ lat, lng, previewImage, markingId }: Marker) {
    if (this.markerCount < 1) {
      this.previewImage = previewImage;
      this.markingId = markingId;
    }
 
    this.markerMap.set(markingId, true);
    this.markerCount += 1;
 
    this.position = {
      lat: this.position.lat + (lat - this.position.lat) / this.markerCount,
      lng: this.position.lng + (lng - this.position.lng) / this.markerCount,
    };
  }
}

export const useTiling = () => {
  const bounds = useMapStore((state) => state.mapInfo.bounds);
  const zoom = useMapStore((state) => state.mapInfo.zoom);
 
  // 지도 영역을 채울 타일을 담는 2차원 배열
  const tiles = useRef<Tile[][]>([]);
  // 지도를 이동할 때 마다 군집이 새로 생성되지 않도록 이전에 생성된 타일들을 저장하는 ref
  const cachedTiles = useRef<Tile[]>([]);
  // 캐시된 타일을 초기화 하는 상황에 영향을 미치는 요소들을 저장하는 ref
  // 예를 들어 줌 레벨이 바뀌면 캐ㅅ 변경해야 합니다.
  // 혹은 외부에서 주입하는 타일링 키가 변경되면 캐시된 타일도 모두 지워야 합니다.
  const previousZoom = useRef<number>(zoom);
  const tilingKey = useRef<TilingKey>("");
 
  const getTiles = (_markers: Marker[], _tilingKey: TilingKey = "") => {
    // 만약 줌이 변경되었거나 타일 키가 변경된 경우엔 캐시된 타일을 초기화 합니다.
    const stringfiedTilingKey = JSON.stringify(_tilingKey);
    if (
      zoom !== previousZoom.current ||
      stringfiedTilingKey !== tilingKey.current
    ) {
      cachedTiles.current = [];
      tilingKey.current = stringfiedTilingKey;
    }
    previousZoom.current = zoom;
 
    // 지도가 이동했더라도 여전히 지도 내부에 존재하는 타일을 필터링 합니다.
    const intersectedCachedTiles = cachedTiles.current.filter((tile) =>
      filterIntercsectedTiles(bounds, tile.bounds)
    );
 
    // 전체 마커들 중 현재 지도 내부에 있는 마커를 필터링 합니다.
    const innerBoundaryMarkers = _markers.filter((marker) =>
      filterInnerBoundary(marker, bounds)
    );
 
    // 현재 지도 내부에 있으면서 캐싱된 타일에 포함되지 않는 마커를 필터링 합니다.
    // 이 마커들을 이용해 새롭게 타일들을 생성합니다.
    const markers = innerBoundaryMarkers.filter(({ markingId }) => {
      return !intersectedCachedTiles.some((tile) =>
        tile.markerMap.has(markingId)
      );
    });
 
    if (markers.length < 1) {
      return cachedTiles.current;
    }
 
    // 줌 레벨에 따라 타일 개수를 결정합니다. numOfTiles 의 타입은 [number , number] 입니다.
    const TileZoomLevel = Math.floor(zoom) as TileZoomLevel;
    const numOfTiles = NUM_OF_TILE_MAP[TileZoomLevel];
 
    // 전체 지도의 크기를  타일 개수로 나눠 타일의 가로 세로 길이를 계산합니다.
    const tileArea = getTileArea(bounds, numOfTiles);
 
    // tileArea 만큼의 크기를 가진   Tile[][] 형태의 배열을 생성해줍니다.
    tiles.current = createTiles(bounds, numOfTiles);
 
    // 각 lat , lng 값을 이용해 Tile[][] 배열에서 해당하는 타일을 찾아 값을 추가 합니다.
    markers.forEach((marker) => {
      const [lngIndex, latIndex] = calculateTileIndex(marker, tileArea, bounds);
      tiles.current[lngIndex][latIndex].addMarker(marker);
    });
 
    // 캐싱 된 타일과 함께 타일을 반환합니다. 이 때 생성된 타일은 다시 캐싱해두도록 합니다.
    const newTiles = tiles.current.flat().concat(intersectedCachedTiles);
 
    cachedTiles.current = newTiles;
 
    return newTiles;
  };
 
  return getTiles;
};

import { useRef } from "react";
import { MapCameraChangedEvent } from "@vis.gl/react-google-maps";
import { useMapStore } from "@/features/map/store";
import { NUM_OF_TILE_MAP } from "../constants";
 
/**
 * @description 지도의 경계를 나타내는 타입으로 현재 보고 있는 지도 전체의 바운더리를 의미 합니다.
 */
type MapBounds = MapCameraChangedEvent["detail"]["bounds"];
/**
 * @description 타일의 경계를 나타내는 타입으로 해당 타일의 바운더리를 의미 합니다.
 */
type TileBounds = MapCameraChangedEvent["detail"]["bounds"];
/**
 * @description 마커를 나타내는 타입으로 해당 마커의 위도, 경도, 마킹 아이디, 미리보기 이미지를 의미 합니다.
 */
 
interface LatLng {
  lat: number;
  lng: number;
}
interface Marker extends LatLng {
  markingId: number;
  previewImage: string;
}
 
export class Tile {
  bounds: TileBounds;
  markerCount: number = 0;
  position: LatLng = { lat: 0, lng: 0 };
 
  markerMap: Map<Marker["markingId"], boolean> = new Map();
 
  previewImage: Marker["previewImage"] = "";
  markingId: Marker["markingId"] = 0;
 
  constructor(bounds: TileBounds) {
    this.bounds = bounds;
  }
 
  addMarker({ lat, lng, previewImage, markingId }: Marker) {
    // 처음 삽입되는 마커의 썸네일과 마킹 아이디를 저장 합니다.
    if (this.markerCount < 1) {
      this.previewImage = previewImage;
      this.markingId = markingId;
    }
 
    this.markerMap.set(markingId, true);
    this.markerCount += 1;
 
    this.position = {
      lat: this.position.lat + (lat - this.position.lat) / this.markerCount,
      lng: this.position.lng + (lng - this.position.lng) / this.markerCount,
    };
  }
}
 
type TileZoomLevel = keyof typeof NUM_OF_TILE_MAP;
type NumOfTiles = (typeof NUM_OF_TILE_MAP)[TileZoomLevel];
 
/**
 * TileArea
 * @description 각 타일 별 위도, 경도의 길이를 나타내는 타입입니다.
 */
interface TileArea {
  width: number;
  height: number;
}
const getTileArea = (
  bounds: MapBounds,
  [numOfRowTiles, numOfColTiles]: NumOfTiles
): TileArea => {
  return {
    width: (bounds.east - bounds.west) / numOfRowTiles,
    height: (bounds.north - bounds.south) / numOfColTiles,
  };
};
 
/**
 * @description 지도의 바운더리와 타일의 개수를 받아 numOfRowTiles x numOfColTiles 타일을 생성합니다.
 */
const createTiles = (bounds: MapBounds, numOfTiles: NumOfTiles): Tile[][] => {
  const { width, height } = getTileArea(bounds, numOfTiles);
  const [numOfRowTiles, numOfColTiles] = numOfTiles;
  const { west, south } = bounds;
 
  const createTile = (rowIndex: number, colIndex: number): Tile => {
    return new Tile({
      east: west + width * (rowIndex + 1),
      west: west + width * rowIndex,
      north: south + height * colIndex,
      south: south + height * (colIndex + 1),
    });
  };
 
  return Array.from({ length: numOfRowTiles }, (_, lngIndex) =>
    Array.from({ length: numOfColTiles }, (_, latIndex) =>
      createTile(lngIndex, latIndex)
    )
  );
};
 
/**
 * calculateTileIndex
 * @description 마커의 위도, 경도와 타일의 위도, 경도 길이를 받아 해당 마커가 속한 타일의 인덱스를 반환합니다.
 * 타일의 인덱스를 계산하는 방법은 다음과 같습니다.
 * 1. 전체 맵의 위도로부터 현재 마커의 위도와 경도를 뺍니다. 해당 값은 위경도 시작점으로부터 마커까지의 거리를 나타냅니다.
 * 2. 해당 거리를 타일의 길이로 나눠 몫을 구합니다. 해당 몫은 마커가 속한 타일의 인덱스를 나타냅니다.
 */
const calculateTileIndex = (
  { lat, lng }: Marker,
  { width, height }: TileArea,
  { west, south }: MapBounds
) => {
  const lngIndex = Math.floor((lng - west) / width);
  const latIndex = Math.floor((lat - south) / height);
  return [lngIndex, latIndex];
};
 
const filterInnerBoundary = ({ lat, lng }: LatLng, bounds: MapBounds) => {
  return (
    lat < bounds.north &&
    lat > bounds.south &&
    lng < bounds.east &&
    lng > bounds.west
  );
};
 
const filterIntercsectedTiles = (
  mapBounds: MapBounds,
  bounds: Tile["bounds"]
) => {
  return (
    mapBounds.north > bounds.south &&
    mapBounds.south < bounds.north &&
    mapBounds.east > bounds.west &&
    mapBounds.west < bounds.east
  );
};
 
type TilingKey = string | { [key: string]: number } | undefined;
 
export const useTiling = () => {
  const bounds = useMapStore((state) => state.mapInfo.bounds);
  const zoom = useMapStore((state) => state.mapInfo.zoom);
 
  const tiles = useRef<Tile[][]>([]);
  const cachedTiles = useRef<Tile[]>([]);
  const previousZoom = useRef<number>(zoom);
  const tilingKey = useRef<TilingKey>("");
 
  /**
   * @description 마커들을 받아 해당 마커들을 타일에 분배합니다.
   * @returns 2차원 배열로 분배된 타일들을 1차원 배열로 반환합니다.
   */
  const getTiles = (_markers: Marker[], _tilingKey: TilingKey = "") => {
    // 만약 줌이 변경되었거나 타일 키가 변경된 경우엔 캐시된 타일을 초기화 합니다.
    const stringfiedTilingKey = JSON.stringify(_tilingKey);
    if (
      zoom !== previousZoom.current ||
      stringfiedTilingKey !== tilingKey.current
    ) {
      cachedTiles.current = [];
      tilingKey.current = stringfiedTilingKey;
    }
    previousZoom.current = zoom;
 
    const intersectedCachedTiles = cachedTiles.current.filter((tile) =>
      filterIntercsectedTiles(bounds, tile.bounds)
    );
 
    const innerBoundaryMarkers = _markers.filter((marker) =>
      filterInnerBoundary(marker, bounds)
    );
 
    const markers = innerBoundaryMarkers.filter(({ markingId }) => {
      return !intersectedCachedTiles.some((tile) =>
        tile.markerMap.has(markingId)
      );
    });
 
    if (markers.length < 1) {
      return cachedTiles.current;
    }
 
    const TileZoomLevel = Math.floor(zoom) as TileZoomLevel;
    const numOfTiles = NUM_OF_TILE_MAP[TileZoomLevel];
 
    const tileArea = getTileArea(bounds, numOfTiles);
 
    tiles.current = createTiles(bounds, numOfTiles);
 
    markers.forEach((marker) => {
      const [lngIndex, latIndex] = calculateTileIndex(marker, tileArea, bounds);
      tiles.current[lngIndex][latIndex].addMarker(marker);
    });
 
    const newTiles = tiles.current.flat().concat(intersectedCachedTiles);
 
    cachedTiles.current = newTiles;
 
    return newTiles;
  };
 
  return getTiles;
};