/**
 * Takes a {@link LineString} and returns a {@link Point} at a specified distance along the line.
 *
 * @name along
 * @param {Feature<LineString>} line input line
 * @param {number} distance distance along the line
 * @param {Object} [options] Optional parameters
 * @param {string} [options.units="kilometers"] can be degrees, radians, miles, or kilometers
 * @returns {Feature<Point>} Point `distance` `units` along the line
 * @example
 * var line = turf.lineString([[-83, 30], [-84, 36], [-78, 41]]);
 * var options = {units: 'miles'};
 *
 * var along = turf.along(line, 200, options);
 *
 * //addToMap
 * var addToMap = [along, line]
 */
function along(line: Feature<LineString>| LineString, distance: number, options: {
    units?: Units
} = {}): Feature<Point> {
    // Optional parameters
    if (!isObject(options)) throw new Error('options is invalid');

    // Validation
    let coords;
    if (line.type === 'Feature') coords = line.geometry.coordinates;
    else if (line.type === 'LineString') coords = line.coordinates;
    else throw new Error('input must be a LineString Feature or Geometry');
    if (!isNumber(distance)) throw new Error('distance must be a number');

    let travelled = 0;
    for (let i = 0; i < coords.length; i++) {
        if (distance >= travelled && i === coords.length - 1) break;
        else if (travelled >= distance) {
            const overshot = distance - travelled;
            if (!overshot) return point(coords[i]);
            else {
                const direction = bearing(coords[i], coords[i - 1]) - 180;
                const interpolated = destination(coords[i], overshot, direction, options);
                return interpolated;
            }
        } else {
            travelled += measureDistance(coords[i], coords[i + 1], options);
        }
    }
    return point(coords[coords.length - 1]);
}

/**
 * Transform function: attempts to dissolve geojson objects where possible
 * [GeoJSON] -> GeoJSON geometry
 *
 * @private
 * @param {FeatureCollection<LineString|MultiLineString|Polygon|MultiPolygon>} geojson Features to dissolved
 * @param {Object} [options={}] Optional parameters
 * @param {boolean} [options.mutate=false] Prevent input mutation
 * @returns {Feature<MultiLineString|MultiPolygon>} Dissolved Features
 */
function dissolve(geojson: FeatureCollection<LineString|MultiLineString|Polygon|MultiPolygon>, options: {
    mutate?: boolean,
} = {}): Feature<LineString|MultiLineString|Polygon|MultiPolygon> | null {
    // Optional parameters
    options = options || {};
    if (!isObject(options)) { throw new Error("options is invalid"); }
    const mutate = options.mutate;

    // Validation
    if (getType(geojson) !== "FeatureCollection") { throw new Error("geojson must be a FeatureCollection"); }
    if (!geojson.features.length) { throw new Error("geojson is empty"); }

    // Clone geojson to avoid side effects
    // Topojson modifies in place, so we need to deep clone first
    if (mutate === false || mutate === undefined) { geojson = clone(geojson); }

    // Assert homogenity
    const type = getHomogenousType(geojson);
    if (!type) { throw new Error("geojson must be homogenous"); }

    // Data => Typescript hack
    const data: any = geojson;

    switch (type) {
    case "LineString":
        return lineDissolve(data, options);
    case "Polygon":
        return polygonDissolve(data, options);
    default:
        throw new Error(type + " is not supported");
    }
}

/**
 * Finds the angle formed by two adjacent segments defined by 3 points. The result will be the (positive clockwise)
 * angle with origin on the `startPoint-midPoint` segment, or its explementary angle if required.
 *
 * @name angle
 * @param {Coord} startPoint Start Point Coordinates
 * @param {Coord} midPoint Mid Point Coordinates
 * @param {Coord} endPoint End Point Coordinates
 * @param {Object} [options={}] Optional parameters
 * @param {boolean} [options.explementary=false] Returns the explementary angle instead (360 - angle)
 * @param {boolean} [options.mercator=false] if calculations should be performed over Mercator or WGS84 projection
 * @returns {number} Angle between the provided points, or its explementary.
 * @example
 * turf.angle([5, 5], [5, 6], [3, 4]);
 * //=45
 */
function angle(startPoint: Coord, midPoint: Coord, endPoint: Coord, options: {
    explementary?: boolean
    mercator?: boolean,
} = {}): number {
    // Optional Parameters
    if (!isObject(options)) { throw new Error("options is invalid"); }

    // Validation
    if (!startPoint) { throw new Error("startPoint is required"); }
    if (!midPoint) { throw new Error("midPoint is required"); }
    if (!endPoint) { throw new Error("endPoint is required"); }

    // Rename to shorter variables
    const A = startPoint;
    const O = midPoint;
    const B = endPoint;

    // Main
    const azimuthAO = bearingToAzimuth((options.mercator !== true) ? bearing(A, O) : rhumbBearing(A, O));
    const azimuthBO = bearingToAzimuth((options.mercator !== true) ? bearing(B, O) : rhumbBearing(B, O));
    const angleAO = Math.abs(azimuthAO - azimuthBO);

    // Explementary angle
    if (options.explementary === true) { return 360 - angleAO; }
    return angleAO;
}

/**
 * Takes a {@link FeatureCollection} of points and calculates the median center,
 * algorithimically. The median center is understood as the point that is
 * requires the least total travel from all other points.
 *
 * Turfjs has four different functions for calculating the center of a set of
 * data. Each is useful depending on circumstance.
 *
 * `@turf/center` finds the simple center of a dataset, by finding the
 * midpoint between the extents of the data. That is, it divides in half the
 * farthest east and farthest west point as well as the farthest north and
 * farthest south.
 *
 * `@turf/center-of-mass` imagines that the dataset is a sheet of paper.
 * The center of mass is where the sheet would balance on a fingertip.
 *
 * `@turf/center-mean` takes the averages of all the coordinates and
 * produces a value that respects that. Unlike `@turf/center`, it is
 * sensitive to clusters and outliers. It lands in the statistical middle of a
 * dataset, not the geographical. It can also be weighted, meaning certain
 * points are more important than others.
 *
 * `@turf/center-median` takes the mean center and tries to find, iteratively,
 * a new point that requires the least amount of travel from all the points in
 * the dataset. It is not as sensitive to outliers as `@turf/center-mean`, but it is
 * attracted to clustered data. It, too, can be weighted.
 *
 * **Bibliography**
 *
 * Harold W. Kuhn and Robert E. Kuenne, “An Efficient Algorithm for the
 * Numerical Solution of the Generalized Weber Problem in Spatial
 * Economics,” _Journal of Regional Science_ 4, no. 2 (1962): 21–33,
 * doi:{@link https://doi.org/10.1111/j.1467-9787.1962.tb00902.x}.
 *
 * James E. Burt, Gerald M. Barber, and David L. Rigby, _Elementary
 * Statistics for Geographers_, 3rd ed., New York: The Guilford
 * Press, 2009, 150–151.
 *
 * @name centerMedian
 * @param {FeatureCollection<any>} features Any GeoJSON Feature Collection
 * @param {Object} [options={}] Optional parameters
 * @param {string} [options.weight] the property name used to weight the center
 * @param {number} [options.tolerance=0.001] the difference in distance between candidate medians at which point the algorighim stops iterating.
 * @param {number} [options.counter=10] how many attempts to find the median, should the tolerance be insufficient.
 * @returns {Feature<Point>} The median center of the collection
 * @example
 * var points = turf.points([[0, 0], [1, 0], [0, 1], [5, 8]]);
 * var medianCenter = turf.centerMedian(points);
 *
 * //addToMap
 * var addToMap = [points, medianCenter]
 */
function centerMedian(
    features: FeatureCollection<any>,
    options: { weight?: string, tolerance?: number, counter?: number} = {}
): Feature<Point, {
    medianCandidates: Array<Position>,
    [key: string]: any
}> {
    // Optional params
    options = options || {};
    if (!isObject(options)) throw new Error('options is invalid');
    var counter = options.counter || 10;
    if (!isNumber(counter)) throw new Error('counter must be a number');
    var weightTerm = options.weight;

    // Calculate mean center:
    var meanCenter = centerMean(features, {weight: options.weight});

    // Calculate center of every feature:
    var centroids: any = featureCollection([]);
    featureEach(features, function (feature) {
        centroids.features.push(centroid(feature, {properties: {weight: feature.properties[weightTerm]}}));
    });

    centroids.properties = {
        tolerance: options.tolerance,
        medianCandidates: []
    };
    return findMedian(meanCenter.geometry.coordinates, [0, 0], centroids, counter);
}

/**
 * Merges all connected (non-forking, non-junctioning) line strings into single lineStrings.
 * [LineString] -> LineString|MultiLineString
 *
 * @param {FeatureCollection<LineString|MultiLineString>} geojson Lines to dissolve
 * @param {Object} [options={}] Optional parameters
 * @param {boolean} [options.mutate=false] Prevent input mutation
 * @returns {Feature<LineString|MultiLineString>} Dissolved lines
 */
function lineDissolve(
    geojson: FeatureCollection<LineString|MultiLineString>,
    options: {mutate?: boolean} = {},
): Feature<LineString|MultiLineString> | null {
    // Optional parameters
    options = options || {};
    if (!isObject(options)) { throw new Error("options is invalid"); }
    const mutate = options.mutate;

    // Validation
    if (getType(geojson) !== "FeatureCollection") { throw new Error("geojson must be a FeatureCollection"); }
    if (!geojson.features.length) { throw new Error("geojson is empty"); }

    // Clone geojson to avoid side effects
    if (mutate === false || mutate === undefined) { geojson = clone(geojson); }

    const result: any[] = [];
    const lastLine = lineReduce(geojson, (previousLine: any, currentLine: any) => {
        // Attempt to merge this LineString with the other LineStrings, updating
        // the reference as it is merged with others and grows.
        const merged = mergeLineStrings(previousLine, currentLine);

        // Accumulate the merged LineString
        if (merged) { return merged;
        // Put the unmerged LineString back into the list
        } else {
            result.push(previousLine);
            return currentLine;
        }
    });
    // Append the last line
    if (lastLine) { result.push(lastLine); }

    // Return null if no lines were dissolved
    if (!result.length) {
        return null;
    // Return LineString if only 1 line was dissolved
    } else if (result.length === 1) {
        return result[0];
    // Return MultiLineString if multiple lines were dissolved with gaps
    } else { return multiLineString(result.map((line) => {
        return line.coordinates;
    })); }
}

export function randomLineString(count?: number, options: {
    bbox?: BBox,
    num_vertices?: number,
    max_length?: number,
    max_rotation?: number,
} = {}): FeatureCollection<LineString, any> {
    // Optional parameters
    options = options || {};
    if (!isObject(options)) { throw new Error("options is invalid"); }
    const bbox = options.bbox;
    let num_vertices = options.num_vertices;
    let max_length = options.max_length;
    let max_rotation = options.max_rotation;
    if (count === undefined || count === null) { count = 1; }

    // Default parameters
    if (!isNumber(num_vertices) || num_vertices === undefined || num_vertices < 2) { num_vertices = 10; }
    if (!isNumber(max_length) || max_length === undefined) { max_length = 0.0001; }
    if (!isNumber(max_rotation) || max_rotation === undefined) { max_rotation = Math.PI / 8; }

    const features = [];
    for (let i = 0; i < count; i++) {
        const startingPoint = randomPosition(bbox);
        const vertices = [startingPoint];
        for (let j = 0; j < num_vertices - 1; j++) {
            const priorAngle = (j === 0) ?
                Math.random() * 2 * Math.PI :
                Math.tan(
                    (vertices[j][1] - vertices[j - 1][1]) /
              (vertices[j][0] - vertices[j - 1][0]),
                );
            const angle = priorAngle + (Math.random() - 0.5) * max_rotation * 2;
            const distance = Math.random() * max_length;
            vertices.push([
                vertices[j][0] + distance * Math.cos(angle),
                vertices[j][1] + distance * Math.sin(angle),
            ]);
        }
        features.push(lineString(vertices));
    }

    return featureCollection(features);
}

/**
 * Takes any LineString or Polygon and returns the overlapping lines between both features.
 *
 * @name lineOverlap
 * @param {Geometry|Feature<LineString|MultiLineString|Polygon|MultiPolygon>} line1 any LineString or Polygon
 * @param {Geometry|Feature<LineString|MultiLineString|Polygon|MultiPolygon>} line2 any LineString or Polygon
 * @param {Object} [options={}] Optional parameters
 * @param {number} [options.tolerance=0] Tolerance distance to match overlapping line segments (in kilometers)
 * @returns {FeatureCollection<LineString>} lines(s) that are overlapping between both features
 * @example
 * var line1 = turf.lineString([[115, -35], [125, -30], [135, -30], [145, -35]]);
 * var line2 = turf.lineString([[115, -25], [125, -30], [135, -30], [145, -25]]);
 *
 * var overlapping = turf.lineOverlap(line1, line2);
 *
 * //addToMap
 * var addToMap = [line1, line2, overlapping]
 */
function lineOverlap<G1 extends LineString|MultiLineString|Polygon|MultiPolygon, G2 extends LineString|MultiLineString|Polygon|MultiPolygon>(
    line1: Feature<G1> | G1,
    line2: Feature<G2> | G2,
    options: {tolerance?: number}={}
): FeatureCollection<LineString> {
    // Optional parameters
    options = options || {};
    if (!isObject(options)) throw new Error('options is invalid');
    var tolerance = options.tolerance || 0;

    // Containers
    var features = [];

    // Create Spatial Index
    var tree = rbush();

    // To-Do -- HACK way to support typescript
    const line: any = lineSegment(line1);
    tree.load(line);
    var overlapSegment;

    // Line Intersection

    // Iterate over line segments
    segmentEach(line2, function (segment) {
        var doesOverlaps = false;

        // Iterate over each segments which falls within the same bounds
        featureEach(tree.search(segment), function (match) {
            if (doesOverlaps === false) {
                var coordsSegment = getCoords(segment).sort();
                var coordsMatch: any = getCoords(match).sort();

                // Segment overlaps feature
                if (equal(coordsSegment, coordsMatch)) {
                    doesOverlaps = true;
                    // Overlaps already exists - only append last coordinate of segment
                    if (overlapSegment) overlapSegment = concatSegment(overlapSegment, segment);
                    else overlapSegment = segment;
                // Match segments which don't share nodes (Issue #901)
                } else if (
                    (tolerance === 0) ?
                        booleanPointOnLine(coordsSegment[0], match) && booleanPointOnLine(coordsSegment[1], match) :
                        nearestPointOnLine(match, coordsSegment[0]).properties.dist <= tolerance &&
                        nearestPointOnLine(match, coordsSegment[1]).properties.dist <= tolerance) {
                    doesOverlaps = true;
                    if (overlapSegment) overlapSegment = concatSegment(overlapSegment, segment);
                    else overlapSegment = segment;
                } else if (
                    (tolerance === 0) ?
                        booleanPointOnLine(coordsMatch[0], segment) && booleanPointOnLine(coordsMatch[1], segment) :
                        nearestPointOnLine(segment, coordsMatch[0]).properties.dist <= tolerance &&
                        nearestPointOnLine(segment, coordsMatch[1]).properties.dist <= tolerance) {
                    // Do not define (doesOverlap = true) since more matches can occur within the same segment
                    // doesOverlaps = true;
                    if (overlapSegment) overlapSegment = concatSegment(overlapSegment, match);
                    else overlapSegment = match;
                }
            }
        });

        // Segment doesn't overlap - add overlaps to results & reset
        if (doesOverlaps === false && overlapSegment) {
            features.push(overlapSegment);
            overlapSegment = undefined;
        }
    });
    // Add last segment if exists
    if (overlapSegment) features.push(overlapSegment);

    return featureCollection(features);
}