/*******************************************************************************
    * Copyright (c) 2015 Voyager Search and MITRE
    * 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
    ******************************************************************************/
   
   package org.locationtech.spatial4j.shape;
  
  import org.locationtech.spatial4j.context.SpatialContext;
  import org.locationtech.spatial4j.shape.impl.BBoxCalculator;
  
  import java.util.*;
  
  import static org.locationtech.spatial4j.shape.SpatialRelation.CONTAINS;
  import static org.locationtech.spatial4j.shape.SpatialRelation.INTERSECTS;
  
  /**
   * A collection of Shape objects, analogous to an OGC GeometryCollection. The
   * implementation demands a List (with random access) so that the order can be
   * retained if an application requires it, although logically it's treated as an
   * unordered Set, mostly.
   * <p>
   * Ideally, {@link #relate(Shape)} should return the same result no matter what
   * the shape order is, although the default implementation can be order
   * dependent when the shapes overlap; see {@link #relateContainsShortCircuits()}.
   *  To improve performance slightly, the caller could order the shapes by
   * largest first so that relate() will have a greater chance of
   * short-circuit'ing sooner.  As the Shape contract states; it may return
   * intersects when the best answer is actually contains or within. If any shape
   * intersects the provided shape then that is the answer.
   * <p>
   * This implementation is not optimized for a large number of shapes; relate is
   * O(N).  A more sophisticated implementation might do an R-Tree based on
   * bbox'es, for example.
   */
  public class ShapeCollection<S extends Shape> extends AbstractList<S> implements Shape {
  
    protected final SpatialContext ctx;
    protected final List<S> shapes;
    protected final Rectangle bbox;
  
    /**
     * WARNING: {@code shapes} is copied by reference.
     * @param shapes Copied by reference! (make a defensive copy if caller modifies)
     */
    public ShapeCollection(List<S> shapes, SpatialContext ctx) {
      if (!(shapes instanceof RandomAccess))
        throw new IllegalArgumentException("Shapes arg must implement RandomAccess: "+shapes.getClass());
      this.shapes = shapes;
      this.ctx = ctx;
      this.bbox = computeBoundingBox(shapes, ctx);
    }
  
    protected Rectangle computeBoundingBox(Collection<? extends Shape> shapes, SpatialContext ctx) {
      if (shapes.isEmpty())
        return ctx.makeRectangle(Double.NaN, Double.NaN, Double.NaN, Double.NaN);
      BBoxCalculator bboxCalc = new BBoxCalculator(ctx);
      for (Shape geom : shapes) {
        bboxCalc.expandRange(geom.getBoundingBox());
      }
      return bboxCalc.getBoundary();
    }
  
    public List<S> getShapes() {
      return shapes;
    }
  
    @Override
    public S get(int index) {
      return shapes.get(index);
    }
  
    @Override
    public int size() {
      return shapes.size();
    }
  
    @Override
    public Rectangle getBoundingBox() {
      return bbox;
    }
  
    @Override
    public Point getCenter() {
      return bbox.getCenter();
    }
  
    @Override
    public boolean hasArea() {
      for (Shape geom : shapes) {
        if( geom.hasArea() ) {
          return true;
        }
      }
      return false;
    }
  
   @Override
   public ShapeCollection getBuffered(double distance, SpatialContext ctx) {
     List<Shape> bufColl = new ArrayList<>(size());
     for (Shape shape : shapes) {
       bufColl.add(shape.getBuffered(distance, ctx));
     }
     return ctx.makeCollection(bufColl);
   }
 
   @Override
   public SpatialRelation relate(Shape other) {
     final SpatialRelation bboxSect = bbox.relate(other);
     if (bboxSect == SpatialRelation.DISJOINT || bboxSect == SpatialRelation.WITHIN)
       return bboxSect;
 
     final boolean containsWillShortCircuit = (other instanceof Point) ||
         relateContainsShortCircuits();
     SpatialRelation sect = null;
     for (Shape shape : shapes) {
       SpatialRelation nextSect = shape.relate(other);
 
       if (sect == null) {//first pass
         sect = nextSect;
       } else {
         sect = sect.combine(nextSect);
       }
 
       if (sect == INTERSECTS)
         return INTERSECTS;
 
       if (sect == CONTAINS && containsWillShortCircuit)
         return CONTAINS;
     }
     return sect;
   }
 
   /**
    * Called by relate() to determine whether to return early if it finds
    * CONTAINS, instead of checking the remaining shapes. It will do so without
    * calling this method if the "other" shape is a Point.  If a remaining shape
    * finds INTERSECTS, then INTERSECTS will be returned.  The only problem with
    * this returning true is that if some of the shapes overlap, it's possible
    * that the result of relate() could be dependent on the order of the shapes,
    * which could be unexpected / wrong depending on the application. The default
    * implementation returns true because it probably doesn't matter.  If it
    * does, a subclass could add a boolean flag that this method could return.
    * That flag could be initialized to true only if the shapes are mutually
    * disjoint.
    *
    * @see #computeMutualDisjoint(java.util.List) .
    */
   protected boolean relateContainsShortCircuits() {
     return true;
   }
 
   /**
    * Computes whether the shapes are mutually disjoint. This is a utility method
    * offered for use by a subclass implementing {@link #relateContainsShortCircuits()}.
    * <b>Beware: this is an O(N^2) algorithm.</b>.  Consequently, consider safely
    * assuming non-disjoint if shapes.size() &gt; 10 or something.  And if all shapes
    * are a Point then the result of this method doesn't ultimately matter.
    */
   protected static boolean computeMutualDisjoint(List<? extends Shape> shapes) {
     //WARNING: this is an O(n^2) algorithm.
     //loop through each shape and see if it intersects any shape before it
     for (int i = 1; i < shapes.size(); i++) {
       Shape shapeI = shapes.get(i);
       for (int j = 0; j < i; j++) {
         Shape shapeJ = shapes.get(j);
         if (shapeJ.relate(shapeI).intersects())
           return false;
       }
     }
     return true;
   }
 
   @Override
   public double getArea(SpatialContext ctx) {
     double MAX_AREA = bbox.getArea(ctx);
     double sum = 0;
     for (Shape geom : shapes) {
       sum += geom.getArea(ctx);
       if (sum >= MAX_AREA)
         return MAX_AREA;
     }
 
     return sum;
   }
 
   @Override
   public String toString() {
     StringBuilder buf = new StringBuilder(100);
     buf.append("ShapeCollection(");
     int i = 0;
     for (Shape shape : shapes) {
       if (i++ > 0)
         buf.append(", ");
       buf.append(shape);
       if (buf.length() > 150) {
         buf.append(" ...").append(shapes.size());
         break;
       }
     }
     buf.append(")");
     return buf.toString();
   }
 
   @Override
   public boolean equals(Object o) {
     if (this == o) return true;
     if (o == null || getClass() != o.getClass()) return false;
 
     ShapeCollection that = (ShapeCollection) o;
 
     if (!shapes.equals(that.shapes)) return false;
 
     return true;
   }
 
   @Override
   public int hashCode() {
     return shapes.hashCode();
   }
 
   @Override
   public SpatialContext getContext() {
     return ctx;
   }
 }