/*******************************************************************************
    * Copyright (c) 2015 ElasticSearch and MITRE, and others
    * All rights reserved. This program and the accompanying materials
    * are made available under the terms of the Apache License, Version 2.0 which
    * accompanies this distribution and is available at
    *    http://www.apache.org/licenses/LICENSE-2.0.txt
    ******************************************************************************/
   
   // A derivative of commit 14bc4dee08355048d6a94e33834b919a3999a06e
  //  at https://github.com/chrismale/elasticsearch
  
  package org.locationtech.spatial4j.io;
  
  
  import org.locationtech.spatial4j.context.SpatialContext;
  import org.locationtech.spatial4j.context.SpatialContextFactory;
  import org.locationtech.spatial4j.exception.InvalidShapeException;
  import org.locationtech.spatial4j.shape.Shape;
  import org.locationtech.spatial4j.shape.ShapeFactory;
  
  import java.io.IOException;
  import java.io.Reader;
  import java.text.ParseException;
  
  /**
   * An extensible parser for <a href="http://en.wikipedia.org/wiki/Well-known_text"> Well Known Text
   * (WKT)</a>. The shapes supported by this class are:
   * <ul>
   * <li>POINT</li>
   * <li>MULTIPOINT</li>
   * <li>ENVELOPE (strictly isn't WKT but is defined by OGC's <a
   * href="http://docs.geoserver.org/stable/en/user/tutorials/cql/cql_tutorial.html">Common Query
   * Language (CQL)</a>)</li>
   * <li>LINESTRING</li>
   * <li>MULTILINESTRING</li>
   * <LI>POLYGON</LI>
   * <LI>MULTIPOLYGON</LI>
   * <li>GEOMETRYCOLLECTION</li>
   * <li>BUFFER (non-standard Spatial4j operation)</li>
   * </ul>
   * 'EMPTY' is supported. Specifying 'Z', 'M', or any other dimensionality in the WKT is effectively
   * ignored. Thus, you can specify any number of numbers in the coordinate points but only the first
   * two take effect. The javadocs for the <code>parse___Shape</code> methods further describe these
   * shapes, or you
   *
   * <p>
   * Most users of this class will call just one method: {@link #parse(String)}, or
   * {@link #parseIfSupported(String)} to not fail if it isn't parse-able.
   *
   * <p>
   * To support more shapes, extend this class and override
   * {@link #parseShapeByType(WKTReader.State, String)}. It's also possible to delegate to a WKTParser
   * by also delegating {@link #newState(String)}.
   *
   * <p>
   * Note, instances of this base class are threadsafe.
   */
  public class WKTReader implements ShapeReader {
    protected final SpatialContext ctx;
    protected final ShapeFactory shapeFactory;
  
    // TODO support SRID: "SRID=4326;POINT(1,2)
  
    /**
     * This constructor is required by
     * {@link org.locationtech.spatial4j.context.SpatialContextFactory#makeFormats(SpatialContext)}.
     */
    public WKTReader(SpatialContext ctx, SpatialContextFactory factory) {
      this.ctx = ctx;
      this.shapeFactory = ctx.getShapeFactory();
    }
  
  
    /**
     * Parses the wktString, returning the defined Shape.
     *
     * @return Non-null Shape defined in the String
     * @throws ParseException Thrown if there is an error in the Shape definition
     */
    public Shape parse(String wktString) throws ParseException, InvalidShapeException {
      Shape shape = parseIfSupported(wktString);// sets rawString & offset
      if (shape != null)
        return shape;
      String shortenedString =
          (wktString.length() <= 128 ? wktString : wktString.substring(0, 128 - 3) + "...");
      throw new ParseException("Unknown Shape definition [" + shortenedString + "]", 0);
    }
  
    /**
     * Parses the wktString, returning the defined Shape. If it can't because the shape name is
     * unknown or an empty or blank string was passed, then it returns null. If the WKT starts with a
     * supported shape but contains an inner unsupported shape then it will result in a
     * {@link ParseException}.
     *
     * @param wktString non-null, can be empty or have surrounding whitespace
     * @return Shape, null if unknown / unsupported shape.
     * @throws ParseException Thrown if there is an error in the Shape definition
     */
    public Shape parseIfSupported(String wktString) throws ParseException, InvalidShapeException {
     State state = newState(wktString);
     state.nextIfWhitespace();// leading
     if (state.eof())
       return null;
     // shape types must start with a letter
     if (!Character.isLetter(state.rawString.charAt(state.offset)))
       return null;
     String shapeType = state.nextWord();
     Shape result = null;
     try {
       result = parseShapeByType(state, shapeType);
     } catch (ParseException | InvalidShapeException e) {
       throw e;
     } catch (IllegalArgumentException e) { // NOTE: JTS Throws IAE for bad WKT
       throw new InvalidShapeException(e.getMessage(), e);
     } catch (Exception e) {
       ParseException pe = new ParseException(e.toString(), state.offset);
       pe.initCause(e);
       throw pe;
     }
     if (result != null && !state.eof())
       throw new ParseException("end of shape expected", state.offset);
     return result;
   }
 
   /**
    * (internal) Creates a new State with the given String. It's only called by
    * {@link #parseIfSupported(String)}. This is an extension point for subclassing.
    */
   protected State newState(String wktString) {
     // NOTE: if we wanted to re-use old States to reduce object allocation, we might do that
     // here. But in the scheme of things, it doesn't seem worth the bother as it complicates the
     // thread-safety story of the API for too little of a gain.
     return new State(wktString);
   }
 
   /**
    * (internal) Parses the remainder of a shape definition following the shape's name given as
    * {@code shapeType} already consumed via {@link State#nextWord()}. If it's able to parse the
    * shape, {@link WKTReader.State#offset} should be advanced beyond it (e.g. to the ',' or ')' or
    * EOF in general). The default implementation checks the name against some predefined names and
    * calls corresponding parse methods to handle the rest. Overriding this method is an excellent
    * extension point for additional shape types. Or, use this class by delegation to this method.
    * <p>
    * When writing a parse method that reacts to a specific shape type, remember to handle the
    * dimension and EMPTY token via
    * {@link org.locationtech.spatial4j.io.WKTReader.State#nextIfEmptyAndSkipZM()}.
    *
    * @param shapeType Non-Null string; could have mixed case. The first character is a letter.
    * @return The shape or null if not supported / unknown.
    */
   protected Shape parseShapeByType(State state, String shapeType) throws ParseException {
     assert Character.isLetter(shapeType.charAt(0)) : "Shape must start with letter: " + shapeType;
 
     if (shapeType.equalsIgnoreCase("POINT")) {
       return parsePointShape(state);
     } else if (shapeType.equalsIgnoreCase("MULTIPOINT")) {
       return parseMultiPointShape(state);
     } else if (shapeType.equalsIgnoreCase("ENVELOPE")) {
       return parseEnvelopeShape(state);
     } else if (shapeType.equalsIgnoreCase("LINESTRING")) {
       return parseLineStringShape(state);
     } else if (shapeType.equalsIgnoreCase("POLYGON")) {
       return parsePolygonShape(state);
     } else if (shapeType.equalsIgnoreCase("GEOMETRYCOLLECTION")) {
       return parseGeometryCollectionShape(state);
     } else if (shapeType.equalsIgnoreCase("MULTILINESTRING")) {
       return parseMultiLineStringShape(state);
     } else if (shapeType.equalsIgnoreCase("MULTIPOLYGON")) {
       return parseMulitPolygonShape(state);
     }
     // extension
     if (shapeType.equalsIgnoreCase("BUFFER")) {
       return parseBufferShape(state);
     }
 
     // HEY! Update class Javadocs if add more shapes
     return null;
   }
 
   /**
    * Parses the BUFFER operation applied to a parsed shape.
    * 
    * <pre>
    *   '(' shape ',' number ')'
    * </pre>
    * 
    * Whereas 'number' is the distance to buffer the shape by.
    */
   protected Shape parseBufferShape(State state) throws ParseException {
     state.nextExpect('(');
     Shape shape = shape(state);
     state.nextExpect(',');
     double distance = shapeFactory.normDist(state.nextDouble());
     state.nextExpect(')');
     return shape.getBuffered(distance, ctx);
   }
 
   /**
    * Parses a POINT shape from the raw string.
    * 
    * <pre>
    *   '(' coordinate ')'
    * </pre>
    *
    * @see #point(State, ShapeFactory.PointsBuilder)
    */
   protected Shape parsePointShape(State state) throws ParseException {
     if (state.nextIfEmptyAndSkipZM())
       return shapeFactory.pointXY(Double.NaN, Double.NaN);
     state.nextExpect('(');
     OnePointsBuilder onePointsBuilder = new OnePointsBuilder(shapeFactory);
     point(state, onePointsBuilder);
     state.nextExpect(')');
     return onePointsBuilder.getPoint();
   }
 
   /**
    * Parses a MULTIPOINT shape from the raw string -- a collection of points.
    * 
    * <pre>
    *   '(' coordinate (',' coordinate )* ')'
    * </pre>
    * 
    * Furthermore, coordinate can optionally be wrapped in parenthesis.
    *
    * @see #point(State, ShapeFactory.PointsBuilder)
    */
   protected Shape parseMultiPointShape(State state) throws ParseException {
     ShapeFactory.MultiPointBuilder builder = shapeFactory.multiPoint();
     if (state.nextIfEmptyAndSkipZM())
       return builder.build();
     state.nextExpect('(');
     do {
       boolean openParen = state.nextIf('(');
       point(state, builder);
       if (openParen)
         state.nextExpect(')');
     } while (state.nextIf(','));
     state.nextExpect(')');
     return builder.build();
   }
 
   /**
    * Parses an ENVELOPE (aka Rectangle) shape from the raw string. The values are normalized.
    * <p>
    * Source: OGC "Catalogue Services Specification", the "CQL" (Common Query Language) sub-spec.
    * <em>Note the inconsistent order of the min &amp; max values between x &amp; y!</em>
    * 
    * <pre>
    *   '(' x1 ',' x2 ',' y2 ',' y1 ')'
    * </pre>
    */
   protected Shape parseEnvelopeShape(State state) throws ParseException {
     // FYI no dimension or EMPTY
     state.nextExpect('(');
     double x1 = state.nextDouble();
     state.nextExpect(',');
     double x2 = state.nextDouble();
     state.nextExpect(',');
     double y2 = state.nextDouble();
     state.nextExpect(',');
     double y1 = state.nextDouble();
     state.nextExpect(')');
     return shapeFactory.rect(shapeFactory.normX(x1), shapeFactory.normX(x2),
             shapeFactory.normY(y1), shapeFactory.normY(y2));
   }
 
   /**
    * Parses a LINESTRING shape from the raw string -- an ordered sequence of points.
    * 
    * <pre>
    * coordinateSequence
    * </pre>
    *
    * @see #pointList(State, ShapeFactory.PointsBuilder)
    */
   protected Shape parseLineStringShape(State state) throws ParseException {
     ShapeFactory.LineStringBuilder lineStringBuilder = shapeFactory.lineString();
     if (state.nextIfEmptyAndSkipZM())
       return lineStringBuilder.build();
     return pointList(state, lineStringBuilder).build();
   }
 
   /**
    * Parses a MULTILINESTRING shape from the raw string -- a collection of line strings.
    * 
    * <pre>
    *   '(' coordinateSequence (',' coordinateSequence )* ')'
    * </pre>
    *
    * @see #parseLineStringShape(org.locationtech.spatial4j.io.WKTReader.State)
    */
   protected Shape parseMultiLineStringShape(State state) throws ParseException {
     ShapeFactory.MultiLineStringBuilder multiLineStringBuilder = shapeFactory.multiLineString();
     if (!state.nextIfEmptyAndSkipZM()) {
       state.nextExpect('(');
       do {
         multiLineStringBuilder.add(pointList(state, multiLineStringBuilder.lineString()));
       } while (state.nextIf(','));
       state.nextExpect(')');
     }
     return multiLineStringBuilder.build();
   }
 
   /**
    * Parses a POLYGON shape from the raw string. It might return a
    * {@link org.locationtech.spatial4j.shape.Rectangle} if the polygon is one.
    *
    * <pre>
    * coordinateSequenceList
    * </pre>
    */
   protected Shape parsePolygonShape(WKTReader.State state) throws ParseException {
     ShapeFactory.PolygonBuilder polygonBuilder = shapeFactory.polygon();
     if (!state.nextIfEmptyAndSkipZM()) {
       polygonBuilder = polygon(state, polygonBuilder);
     }
     return polygonBuilder.buildOrRect();
   }
 
   /**
    * Parses a MULTIPOLYGON shape from the raw string.
    *
    * <pre>
    *   '(' polygon (',' polygon )* ')'
    * </pre>
    */
   protected Shape parseMulitPolygonShape(WKTReader.State state) throws ParseException {
     ShapeFactory.MultiPolygonBuilder multiPolygonBuilder = shapeFactory.multiPolygon();
     if (!state.nextIfEmptyAndSkipZM()) {
       state.nextExpect('(');
       do {
         multiPolygonBuilder.add(polygon(state, multiPolygonBuilder.polygon()));
       } while (state.nextIf(','));
       state.nextExpect(')');
     }
     return multiPolygonBuilder.build();
   }
 
   /**
    * Parses a GEOMETRYCOLLECTION shape from the raw string.
    * 
    * <pre>
    *   '(' shape (',' shape )* ')'
    * </pre>
    */
   protected Shape parseGeometryCollectionShape(State state) throws ParseException {
     ShapeFactory.MultiShapeBuilder<Shape> multiShapeBuilder = shapeFactory.multiShape(Shape.class);
     if (state.nextIfEmptyAndSkipZM())
       return multiShapeBuilder.build();
     state.nextExpect('(');
     do {
       multiShapeBuilder.add(shape(state));
     } while (state.nextIf(','));
     state.nextExpect(')');
     return multiShapeBuilder.build();
   }
 
   /**
    * Reads a shape from the current position, starting with the name of the shape. It calls
    * {@link #parseShapeByType(org.locationtech.spatial4j.io.WKTReader.State, String)} and throws an
    * exception if the shape wasn't supported.
    */
   protected Shape shape(State state) throws ParseException {
     String type = state.nextWord();
     Shape shape = parseShapeByType(state, type);
     if (shape == null)
       throw new ParseException("Shape of type " + type + " is unknown", state.offset);
     return shape;
   }
 
   /**
    * Reads a list of Points (AKA CoordinateSequence) from the current position.
    * 
    * <pre>
    *   '(' coordinate (',' coordinate )* ')'
    * </pre>
    *
    * @see #point(State, ShapeFactory.PointsBuilder)
    */
   protected <B extends ShapeFactory.PointsBuilder> B pointList(State state, B pointsBuilder) throws ParseException {
     state.nextExpect('(');
     do {
       point(state, pointsBuilder);
     } while (state.nextIf(','));
     state.nextExpect(')');
     return pointsBuilder;
   }
 
   /**
    * Reads a raw Point (AKA Coordinate) from the current position. Only the first 2 numbers are
    * used. The values are normalized.
    * 
    * <pre>
    *   number number number*
    * </pre>
    */
   protected ShapeFactory.PointsBuilder point(State state, ShapeFactory.PointsBuilder pointsBuilder) throws ParseException {
     double x = state.nextDouble();
     double y = state.nextDouble();
     state.skipNextDoubles();//TODO capture to call pointXYZ
     pointsBuilder.pointXY(shapeFactory.normX(x), shapeFactory.normY(y));
     return pointsBuilder;
   }
 
   /**
    * Reads a polygon
    */
   protected ShapeFactory.PolygonBuilder polygon(WKTReader.State state, ShapeFactory.PolygonBuilder polygonBuilder) throws ParseException {
     state.nextExpect('(');
     pointList(state, polygonBuilder); // outer ring
     while (state.nextIf(',')) {
       ShapeFactory.PolygonBuilder.HoleBuilder holeBuilder = polygonBuilder.hole();
       pointList(state, holeBuilder);
       holeBuilder.endHole();
     }
     state.nextExpect(')');
     return polygonBuilder;
   }
 
   /** The parse state. */
   public class State {
     /** Set in {@link #parseIfSupported(String)}. */
     public String rawString;
     /** Offset of the next char in {@link #rawString} to be read. */
     public int offset;
     /** Dimensionality specifier (e.g. 'Z', or 'M') following a shape type name. */
     public String dimension;
 
     public State(String rawString) {
       this.rawString = rawString;
     }
 
     public SpatialContext getCtx() {
       return ctx;
     }
 
     public WKTReader getParser() {
       return WKTReader.this;
     }
 
     /**
      * Reads the word starting at the current character position. The word terminates once
      * {@link Character#isJavaIdentifierPart(char)} returns false (or EOF). {@link #offset} is
      * advanced past whitespace.
      *
      * @return Non-null non-empty String.
      */
     public String nextWord() throws ParseException {
       int startOffset = offset;
       while (offset < rawString.length()
           && Character.isJavaIdentifierPart(rawString.charAt(offset))) {
         offset++;
       }
       if (startOffset == offset)
         throw new ParseException("Word expected", startOffset);
       String result = rawString.substring(startOffset, offset);
       nextIfWhitespace();
       return result;
     }
 
     /**
      * Skips over a dimensionality token (e.g. 'Z' or 'M') if found, storing in {@link #dimension},
      * and then looks for EMPTY, consuming that and whitespace.
      * 
      * <pre>
      *   dimensionToken? 'EMPTY'?
      * </pre>
      * 
      * @return True if EMPTY was found.
      */
     public boolean nextIfEmptyAndSkipZM() throws ParseException {
       if (eof())
         return false;
       char c = rawString.charAt(offset);
       if (c == '(' || !Character.isJavaIdentifierPart(c))
         return false;
       String word = nextWord();
       if (word.equalsIgnoreCase("EMPTY"))
         return true;
       // we figure this word is Z or ZM or some other dimensionality signifier. We skip it.
       this.dimension = word;
 
       if (eof())
         return false;
       c = rawString.charAt(offset);
       if (c == '(' || !Character.isJavaIdentifierPart(c))
         return false;
       word = nextWord();
       if (word.equalsIgnoreCase("EMPTY"))
         return true;
       throw new ParseException("Expected EMPTY because found dimension; but got [" + word + "]",
           offset);
     }
 
     /**
      * Reads in a double from the String. Parses digits with an optional decimal, sign, or exponent.
      * NaN and Infinity are not supported. {@link #offset} is advanced past whitespace.
      *
      * @return Double value
      */
     public double nextDouble() throws ParseException {
       int startOffset = offset;
       skipDouble();
       if (startOffset == offset)
         throw new ParseException("Expected a number", offset);
       double result;
       try {
         result = Double.parseDouble(rawString.substring(startOffset, offset));
       } catch (Exception e) {
         throw new ParseException(e.toString(), offset);
       }
       nextIfWhitespace();
       return result;
     }
 
     /** Advances offset forward until it points to a character that isn't part of a number. */
     public void skipDouble() {
       int startOffset = offset;
       for (; offset < rawString.length(); offset++) {
         char c = rawString.charAt(offset);
         if (!(Character.isDigit(c) || c == '.' || c == '-' || c == '+')) {
           // 'e' is okay as long as it isn't first
           if (offset != startOffset && (c == 'e' || c == 'E'))
             continue;
           break;
         }
       }
     }
 
     /** Advances past as many doubles as there are, with intervening whitespace. */
     public void skipNextDoubles() {
       while (!eof()) {
         int startOffset = offset;
         skipDouble();
         if (startOffset == offset)
           return;
         nextIfWhitespace();
       }
     }
 
     /**
      * Verifies that the current character is of the expected value. If the character is the
      * expected value, then it is consumed and {@link #offset} is advanced past whitespace.
      *
      * @param expected The expected char.
      */
     public void nextExpect(char expected) throws ParseException {
       if (eof())
         throw new ParseException("Expected [" + expected + "] found EOF", offset);
       char c = rawString.charAt(offset);
       if (c != expected)
         throw new ParseException("Expected [" + expected + "] found [" + c + "]", offset);
       offset++;
       nextIfWhitespace();
     }
 
     /** If the string is consumed, i.e. at end-of-file. */
     public final boolean eof() {
       return offset >= rawString.length();
     }
 
     /**
      * If the current character is {@code expected}, then offset is advanced after it and any
      * subsequent whitespace. Otherwise, false is returned.
      *
      * @param expected The expected char
      * @return true if consumed
      */
     public boolean nextIf(char expected) {
       if (!eof() && rawString.charAt(offset) == expected) {
         offset++;
         nextIfWhitespace();
         return true;
       }
       return false;
     }
 
     /**
      * Moves offset to next non-whitespace character. Doesn't move if the offset is already at
      * non-whitespace. <em>There is very little reason for subclasses to call this because
      * most other parsing methods call it.</em>
      */
     public void nextIfWhitespace() {
       for (; offset < rawString.length(); offset++) {
         if (!Character.isWhitespace(rawString.charAt(offset))) {
           return;
         }
       }
     }
 
     /**
      * Returns the next chunk of text till the next ',' or ')' (non-inclusive) or EOF. If a '(' is
      * encountered, then it looks past its matching ')', taking care to handle nested matching
      * parenthesis too. It's designed to be of use to subclasses that wish to get the entire
      * subshape at the current position as a string so that it might be passed to other software
      * that will parse it.
      * <p>
      * Example:
      * 
      * <pre>
      * OUTER(INNER(3, 5))
      * </pre>
      * 
      * If this is called when offset is at the first character, then it will return this whole
      * string. If called at the "I" then it will return "INNER(3, 5)". If called at "3", then it
      * will return "3". In all cases, offset will be positioned at the next position following the
      * returned substring.
      *
      * @return non-null substring.
      */
     public String nextSubShapeString() throws ParseException {
       int startOffset = offset;
       int parenStack = 0;// how many parenthesis levels are we in?
       for (; offset < rawString.length(); offset++) {
         char c = rawString.charAt(offset);
         if (c == ',') {
           if (parenStack == 0)
             break;
         } else if (c == ')') {
           if (parenStack == 0)
             break;
           parenStack--;
         } else if (c == '(') {
           parenStack++;
         }
       }
       if (parenStack != 0)
         throw new ParseException("Unbalanced parenthesis", startOffset);
       return rawString.substring(startOffset, offset);
     }
 
   }// class State
 
   @Override
   public String getFormatName() {
     return ShapeIO.WKT;
   }
   
   static String readString(Reader reader) throws IOException {
     char[] arr = new char[1024];
     StringBuilder buffer = new StringBuilder();
     int numCharsRead;
     while ((numCharsRead = reader.read(arr, 0, arr.length)) != -1) {
       buffer.append(arr, 0, numCharsRead);
     }
     return buffer.toString();
   }
 
   @Override
   public Shape read(Reader reader) throws IOException, ParseException {
     return parse(readString(reader));
   }
 
   @Override
   public Shape read(Object value) throws IOException, ParseException, InvalidShapeException {
     return parse(value.toString());
   }
 
   @Override
   public Shape readIfSupported(Object value) throws InvalidShapeException {
     try {
       return parseIfSupported(value.toString());
     } catch (ParseException e) {
     }
     return null;
   }
 }