/*
javac LandPolygon.java Tag.java

osmconvert  d:/downloads/antarctica-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon antarctica
osmconvert  d:/downloads/central-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon central-america
osmconvert  d:/downloads/australia-oceania-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon australia-oceania
osmconvert  d:/downloads/south-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon south-america
osmconvert  d:/downloads/north-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon north-america
osmconvert  d:/downloads/africa-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon africa
osmconvert  d:/downloads/asia-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon asia
osmconvert  d:/downloads/europe-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon europe


osmconvert  d:/downloads/antarctica-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node antarctica
osmconvert  d:/downloads/australia-oceania-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node australia-oceania
osmconvert  d:/downloads/africa-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node africa
osmconvert  d:/downloads/central-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node central-america
osmconvert  d:/downloads/south-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node south-america
osmconvert  d:/downloads/europe-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node europe
osmconvert  d:/downloads/asia-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node asia
osmconvert  d:/downloads/north-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node north-america

java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon
*/

import java.io.*;
import java.nio.*;
import java.util.*;
import java.time.*;

public class LandPolygon {
    static String pathLands = "c:/osm/lands.dat";
    static double E7  = 10000000;
    static double B30 = 1024*1024*1024;   // (2 の 30乗)

    static int MAXSIZE = 130000000;
    static long[] nodes = new long[MAXSIZE];    // node id
    static int num_nodes;
    static int ixNode;
    static int[] lons;
    static int[] lats;
	static String[] areas = { "antarctica", "africa", "europe", "asia", "north-america", 
       		 				  "central-america", "south-america", "australia-oceania" };


    static double Lon2X(double lon, int zoom) {
        return (lon + 180.0) / 360.0 * (1<<zoom);
    }

    static double Lat2Y(double lat, int zoom) {
        return (1 - Math.log(Math.tan(lat*Math.PI/180.0) +
                1 / Math.cos(lat*Math.PI/180.0)) / Math.PI)/2.0 * (1<<zoom);
    }

    //
    static void parseNode(String name) {
        lons = new int[MAXSIZE];
        lats = new int[MAXSIZE];
        String file = "c:/osm/" + name + "_coastline.csv";
        try (BufferedReader br = new BufferedReader(new FileReader(file))) {
            String line;
            while ((line = br.readLine()) != null) {
                String[] nids = line.split(",");
                for (int n = 1; n < nids.length; n++) {
                    put(Long.parseLong(nids[n]), 0, 0);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }

        char quote = '"';
        int cntFound = 0;
        String pathOut = "c:/osm/" + name + "_idlonlat.dat";

        // 標準入力
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             DataOutputStream dos = new DataOutputStream(new FileOutputStream(pathOut))) {
            String line;
            while ((line = br.readLine()) != null) {
                int ix = line.indexOf('<');
                if (ix < 0) continue;
                String s = line.substring(ix);  // 行先頭のスペースを削除する
                if (s.startsWith("<node ")) {   // nodeオブジェクト
                    int bgnId = 10;  // <node id="31252942" lat="35.6528795" lon="139.7573991" ... >
                    int endId = s.indexOf(quote, bgnId);
                    String strId = s.substring(bgnId, endId);
                    long idNode = Long.parseLong(strId);

                    if (get(idNode) > 0) {  // 海岸線ノード
                        cntFound++;
                        int bgnLon = s.indexOf("lon=", endId);
                        int endLon = s.indexOf(quote, bgnLon+5);
                        String strLon = s.substring(bgnLon+5, endLon);
                        int bgnLat = s.indexOf("lat=", endId);
                        int endLat = s.indexOf(quote, bgnLat+5);
                        String strLat = s.substring(bgnLat+5, endLat);
                        int lon = (int)(Double.parseDouble(strLon)*E7);
                        int lat = (int)(Double.parseDouble(strLat)*E7);
                        dos.writeLong(idNode);
                        dos.writeInt(lon);
                        dos.writeInt(lat);
                    }
                } else if (s.startsWith("<way ")) {   // wayオブジェクト
                    break;
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    static int hash(long id) {
        return (int)(Math.abs(id * 137) % MAXSIZE);
    }

    static int put(long id, int lon, int lat) {
        int n, h = hash(id);
        for (n = 0; n < MAXSIZE; n++) {
            int ix = (h + n) % MAXSIZE;
            if (nodes[ix] == 0) {
                nodes[ix] = id;
                lons[ix] = lon;
                lats[ix] = lat;        
                num_nodes++;
                if (num_nodes % 1000000 == 0) {
                    System.out.printf("%d万\r", num_nodes / 10000);
                }
                return ix;                // 新規登録
            } else if (nodes[ix] == id) {
                return ix;                // 登録済み
            }
        }
        System.out.println("Error: Hash Table Full");
        return -1;
    }

    static int get(long id) {
        int n, h = hash(id);
        for (n = 0; n < MAXSIZE; n++) {
            int ix = (h + n) % MAXSIZE;
            if (nodes[ix] == 0) {
                return -1;                // 登録なし
            } else if (nodes[ix] == id) {
                return ix;                // 登録済み
            }
        }
        return -1;  // 存在しない
    }

    static void loadIdLonLat() {
        num_nodes = 0;
        lons = new int[MAXSIZE];
        lats = new int[MAXSIZE];
		for (String area : areas) {
        	loadIdLonLat(area);
		}
    }

    static HashMap<Integer,Long> map180 = new HashMap<>();

    static void loadIdLonLat(String name) {
        try (DataInputStream dis = new DataInputStream(new BufferedInputStream(
                    new FileInputStream("c:/osm/" + name + "_idlonlat.dat")))) {
            while (true) {
                long nid = dis.readLong();
                int lon = dis.readInt();
                int lat = dis.readInt();
                if (lon == 1800000000) map180.put(lat, nid);
                put(nid, lon, lat);
            }
        } catch (EOFException e) {
            System.out.println(""); // ファイル読み込み完了
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    static int cntPolygon = 0;


    // xmlファイルは標準入力（パイプ）から 
    static void parseWay(String name) {
        char quote = '"';
        String pathout = "c:/osm/" + name + "_coastline.csv";
        List<Long> listNodes = new ArrayList<>();
        long idWay = 0;

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                FileWriter fw = new FileWriter(new File(pathout)) ) {
            String line;
            boolean fCoastline = false;
            boolean fWaySection = false;

            while ((line = br.readLine()) != null) {
                int ix = line.indexOf('<');
                if (ix < 0) continue;
                String s = line.substring(ix);  // 行先頭のスペースを削除する
                if (fWaySection && s.startsWith("<nd ")) {
                    int bgn = 9;
                    int end = s.indexOf("\"", bgn);
                    String ref = s.substring(bgn, end);
                    long idRef = Long.parseLong(ref);
                    listNodes.add(idRef);
                } else if (fWaySection && s.startsWith("<tag ")) {
                    int kbgn = 8;
                    int kend = s.indexOf(quote, kbgn);
                    String key = s.substring(kbgn, kend);
                    int vbgn = kend + 5;
                    int vend = s.indexOf(quote, vbgn);
                    String val = s.substring(vbgn, vend);
                    if (key.equals("natural") && val.equals("coastline")) {
                        fCoastline = true;
                    }
                } else if (s.startsWith("<way ")) { // wayオブジェクト始まり
                    if (!fWaySection) fWaySection = true;
                    listNodes.clear();
                    fCoastline = false;
                    int bgnId = 9;
                    int endId = s.indexOf(quote, bgnId);
                    String strId = s.substring(bgnId, endId);
                    idWay = Long.parseLong(strId);

                } else if (fWaySection && s.startsWith("</way")) {  // wayオブジェクト終わり
                    if (fCoastline) {
                        fw.write("" + idWay);
                        for (int i = 0; i < listNodes.size(); i++) {
                            fw.write("," + listNodes.get(i));
                        }
                        fw.write("\n");
                    }
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    static HashMap<Long, long[]> mapCoastlines = new HashMap<>();
    static List<Long> listErrorNodes = new ArrayList<>();
    static HashSet<Long> setWayIds = new HashSet<>();

    static DataOutputStream dos;

    static void generateLandPolygon() throws Exception {
        dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(pathLands)));

        num_nodes = 0;
        lons = new int[MAXSIZE];
        lats = new int[MAXSIZE];

        // ノード座標値データを nodes, lons, lats にセット
		for (String area : areas) {
	        loadIdLonLat(area);
		}
        System.out.printf("ノード座標値読み込み完了 num_node=%d map180=%d\n", 
                        num_nodes, map180.size());

		for (String area : areas) {
	        procCoastline(area);
		}

        unclosedCoastlines();
    }

    static void procCoastline(String name) {
        String file = "c:/osm/" + name + "_coastline.csv";
        System.out.printf("procCoastLine %s\n", name);
        try (BufferedReader br = new BufferedReader(new FileReader(file))) {
            String line;
            while ((line = br.readLine()) != null) {
                String[] nids = line.split(",");

                long idWay = Long.parseLong(nids[0]);
                if (setWayIds.contains(idWay)) {
                    continue;   // 処理済み
                }
                setWayIds.add(idWay);

                List<Long> listNodes = new ArrayList<>();
                for (int n = 1; n < nids.length; n++) {
                    long nid = Long.parseLong(nids[n]);
                    int ix = get(nid);
                    if (ix < 0) {
                        System.out.println("Error 座標値が得られない Id＝" + nid);
                        continue;
                    }
                    int lon = lons[ix];
                    int lat = lats[ix];
                    if (lon == -1800000000 && map180.containsKey(lat)) {
                        listNodes.add(map180.get(lat));
                    } else {
                        listNodes.add(nid);
                    }
                }


                long[] nodes = new long[listNodes.size()];
                for (int n = 0; n < nodes.length; n++) {
                    nodes[n] = listNodes.get(n);
                }
                procCoastline(nodes);
            }
        } catch (Exception e) {
            e.printStackTrace();
            return;
        }
        System.out.printf("mapCoastLines エントリ数＝%d\n", mapCoastlines.size());
    }

    static void procCoastline(long[] nodes) throws Exception {
        long head = nodes[0];
        long tail = nodes[nodes.length-1];

        if (head == tail) {
            //System.out.printf("閉ループ %d\n", head);
            writePolygon(nodes);
            return;
        }
        if (!mapCoastlines.containsKey(head) && !mapCoastlines.containsKey(tail)) {
            mapCoastlines.put(head, nodes);     // 先頭ノードをキー
            mapCoastlines.put(tail, nodes);     // 末尾ノードをキー
            return;
        }

        while ((mapCoastlines.containsKey(head) || mapCoastlines.containsKey(tail))) {
            long[] src = mapCoastlines.get(head);
            if (src == null) src = mapCoastlines.get(tail);
            mapCoastlines.remove(src[0]);
            mapCoastlines.remove(src[src.length-1]);    // 上と同じ配列

            if (src[0] == head || src[src.length-1] == tail) {
                reverse(nodes);
                head = nodes[0];
                tail = nodes[nodes.length-1];
            }   // 反転する

            if (src[src.length-1] == head && src[0] == tail) {
                long[] dst = new long[src.length + nodes.length - 2];
                System.arraycopy(src, 0, dst, 0, src.length);
                System.arraycopy(nodes, 1, dst, src.length, nodes.length-2);
                writePolygon(dst);
                //System.out.printf( "閉ループ完成 nodes=%d mapCoastlines数=%d Polygons数=%d\n",
                //                     dst.length, mapCoastlines.size(), cntPolygon);
                return;     // 閉ループになる
            } 

            long[] dst = new long[src.length + nodes.length - 1];
            if (src[src.length-1] == head) {
                System.arraycopy(src, 0, dst, 0, src.length);
                System.arraycopy(nodes, 1, dst, src.length, nodes.length-1);
                // head は src配列の末尾と同じため、コピーしない
            } else if (src[0] == tail) {
                System.arraycopy(nodes, 0, dst, 0, nodes.length-1);
                System.arraycopy(src, 0, dst, nodes.length-1, src.length);
                // tail は src配列の先頭と同じため、コピーしない
            }

            if (dst[0] == dst[dst.length-1]) {  // 閉ループになった
                writePolygon(dst);
                //System.out.printf( "閉ループ完成 nodes=%d mapCoastlines数=%d Polygons数=%d\n",
                //                     dst.length, mapCoastlines.size(), cntPolygon);
                return;
            }

            nodes = Arrays.copyOf(dst, dst.length);
            head = nodes[0];
            tail = nodes[nodes.length-1];
        }
        mapCoastlines.put(head, nodes);     // HashMapに再登録
        mapCoastlines.put(tail, nodes);
        //System.out.printf( "再登録 dst=%d 登録数=%d\n", nodes.length, mapCoastlines.size() );
    }

    // 元の配列を並び替える
    static void reverse(long[] array) {
        for (int left=0, right=array.length-1; left < right; ) {
            long temp = array[left];
            array[left++] = array[right];
            array[right--] = temp;
        }
    }

    static void reverse(int[] array) {
        for (int left=0, right=array.length-1; left < right; ) {
            int temp = array[left];
            array[left++] = array[right];
            array[right--] = temp;
        }
    }

    static int cntErrPoly = 0;
    static byte[] ba = new byte[128*1024*1024];

    // ids: node id配列
    static void writePolygon(long[] ids) throws Exception {
        cntPolygon++;
        int[] ilons = new int[ids.length];  // 整数化した経度
        int[] ilats = new int[ids.length];  // 整数化した緯度
        int[] xs = new int[ids.length];
        int[] ys = new int[ids.length];
        int xmin = Integer.MAX_VALUE;
        int xmax = Integer.MIN_VALUE;
        int ymin = Integer.MAX_VALUE;
        int ymax = Integer.MIN_VALUE;
        for (int i = 0; i < ids.length; i++) {
            int ix = get(ids[i]);
            ilons[i] = lons[ix];
            ilats[i] = lats[ix];
            xs[i] = (int)(Lon2X(lons[ix]/E7, 0) * B30);
            ys[i] = (int)(Lat2Y(lats[ix]/E7, 0) * B30);
            if (xs[i] < xmin) xmin = xs[i];
            if (xs[i] > xmax) xmax = xs[i];
            if (ys[i] < ymin) ymin = ys[i];
            if (ys[i] > ymax) ymax = ys[i];
        }
        float way_area = (float)/*Math.abs*/(calcWayArea(ilons, ilats));
		if (way_area > 0) {
			reverse(xs);
			reverse(ys);
		} else {
			way_area = -way_area;
		}

//if (way_area > 0)        System.out.printf("%d %.1f\n", ids.length, way_area);
        //System.out.printf("%d %d %d %d\n", xmin, ymin, xmax, ymax);

        int head = 0x02;    // polygon
        head |= 0x20;       // Mapアプリ型データ

        ByteBuffer bb = ByteBuffer.wrap(ba);

        bb.putInt(xmin);
        bb.putInt(ymin);
        bb.putInt(xmax);
        bb.putInt(ymax);

        bb.putInt(cntPolygon);  // rid
        bb.putLong(0L);         // osm_id

        bb.putFloat(way_area);

        int key = Tag.Key.natural.ordinal();
        int val = Tag.Val.land.ordinal();
        bb.putInt(key);
        bb.putInt(val);

		SimplifySection(xs, ys, 0, xs.length-2, 10000);	// 100m
		int skip = 0;
		for (int i = 0; i < xs.length; i++) {
			if (xs[i] == Integer.MIN_VALUE) {
				skip++;
			}
		}


        bb.putInt(ids.length - skip);	// ノード数
//System.out.printf("%d - %d\n", ids.length, skip);
        for (int k = 0; k < ids.length; k++) {
			if (xs[k] > Integer.MIN_VALUE) {
            	bb.putInt(xs[k]);
           	 	bb.putInt(ys[k]);
			}
        }
        int rec_length = bb.position();			// バイト単位
        dos.writeInt(head);
        dos.writeInt(rec_length);

        dos.write(ba, 0, bb.position());
    }

    static void unclosedCoastlines() {
        HashSet<Long> setDone = new HashSet<>();
        for (long[] nids : mapCoastlines.values()) {
            if (setDone.contains(nids[0]) || setDone.contains(nids[nids.length-1])) continue;
            setDone.add(nids[0]);
            System.out.printf("%d ", nids.length);
            int ixHead = get(nids[0]);
            int ixTail = get(nids[nids.length-1]);
            System.out.printf("(%d %d) (%d %d)\n", 
                lons[ixHead], lats[ixHead], lons[ixTail], lats[ixTail]);
        }
        System.out.println();
    }

    static double toRadian(double deg) {
        return deg*Math.PI/180.0;   // ラジアンに変換
    }

    static double calcWayArea(int[] xs, int[] ys) {
        double Radius = 6378137 + 100;      // 長半径 + 楕円高（仮）
        double wayarea = 0;
        double x1 = xs[xs.length-2]/E7;
        double y1 = ys[ys.length-2]/E7;
        for (int n = 0; n < xs.length-1; n++) {
            double x2 = xs[n]/E7;
            double y2 = ys[n]/E7;
            wayarea += toRadian(x2-x1)*(2+Math.sin(toRadian(y1))+Math.sin(toRadian(y2)));
            x1 = x2;
            y1 = y2;
        }
        return wayarea * Radius * Radius / 2.0;
    }   // 反時計回りが正、時計回りは負となる


    public static void main(String[] args) throws Exception {
        long start = System.currentTimeMillis();

        Instant instant = Instant.ofEpochSecond(start/1000);
        System.out.println(ZonedDateTime.ofInstant(instant, ZoneId.systemDefault()));

        if (args.length == 2) {
            if (args[0].equals("-way")) {
                parseWay(args[1]);
            } else if (args[1].equals("-way")) {
                parseWay(args[0]);
            } else if (args[0].equals("-node")) {
                parseNode(args[1]);
            } else if (args[1].equals("-node")) {
                parseNode(args[0]);
            }
        } else {
            generateLandPolygon();
            System.out.println("ポリゴン数＝" + cntPolygon);
        }

        System.out.printf("実行時間＝%.2f分\n",
            (System.currentTimeMillis() - start)/60000.0 );
    }


    static void SimplifySection(int[] xs, int[] ys, int i, int j, double epsilon) {
        if ((i + 1) == j) return;
        double maxDistance = -1.0;
        int maxIndex = i;
        for (int k = i + 1; k < j; k++) {
            double distance = PerpendicularDistance(xs[k], ys[k], xs[i], ys[i], xs[j], ys[j]);
            if (distance > maxDistance) {
                maxDistance = distance;
                maxIndex = k;
            }
        }
        if (maxDistance <= epsilon) {
            for (int k = i + 1; k < j; k++) {
                xs[k] = Integer.MIN_VALUE;   // 間引く
                ys[k] = Integer.MIN_VALUE;   // 間引く
            }
        } else {
            SimplifySection(xs, ys, i, maxIndex, epsilon);
            SimplifySection(xs, ys, maxIndex, j, epsilon);
        }
    }

    // １度＝約100km ⇒ 1m＝約0.00001度
    static double PerpendicularDistance(double px, double py, double p1x, double p1y, double p2x, double p2y) {
        double dx = p2x - p1x;
        double dy = p2y - p1y;
        double d = Math.sqrt(dx*dx + dy*dy);
        return Math.abs(px*dy - py*dx + p2x*p1y - p2y*p1x)/d;
    }


}