class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }

    translate(dx, dy) {
        return new Point(this.x + dx, this.y + dy);
    }

    eq(other) {
        return ((this.x == other.x) && (this.y == other.y));
    }

    toArray() {
        return [this.x, this.y];
    }

    toString() {
        return `Point(${this.x}, ${this.y})`;
    }
}

class LineSegment {
    constructor(p1, p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    translate(dx, dy) {
        return new LineSegment(this.p1.translate(dx, dy), this.p2.translate(dx, dy));
    }

    eq(other) {
        if ((this.p1.eq(other.p1)) && (this.p2.eq(other.p2))) { return true; }
        if ((this.p1.eq(other.p2)) && (this.p2.eq(other.p1))) { return true; }
        return false;
    }

    draw() {
        turtle.goto(this.p1.toArray());
        turtle.pendown();
        turtle.goto(this.p2.toArray());
        turtle.penup();
    }

    toString() {
        return `LineSegment(${this.p1.toString()}, ${this.p2.toString()})`;
    }
}

// Just a list of line segments for now
// This will be slow (TODO: make less slow)
class Polygon {
    constructor(edges) {
        this.edges = edges;
    }

    translate(dx, dy) {
        return new Polygon(this.edges.map(edge => edge.translate(dx, dy)));
    }

    // In this case, two polygons are adjacent if they share any whole edge
    adjacent(other) {
        for (var i = 0; i < this.edges.length; i++) {
            let thisEdge = this.edges[i];
            for (var j = 0; j < other.edges.length; j++) {
                let otherEdge = other.edges[j];

                if (thisEdge.eq(otherEdge)) {
                    return true;
                }
            }
        }

        return false;
    }

    // Returns a new polygon with edges that are in both this and other
    intersection(other) {
        let commonEdges = [];

        for (var i = 0; i < this.edges.length; i++) {
            let thisEdge = this.edges[i];
            for (var j = 0; j < other.edges.length; j++) {
                let otherEdge = other.edges[j];
                if (thisEdge.eq(otherEdge)) {
                    commonEdges.push(thisEdge);
                }
            }
        }

        return new Polygon(commonEdges);
    }

    // Returns a new polygon with edges that are in either this or other
    union(other) {
        return new Polygon(this.edges.concat(other.edges));
    }

    // Returns a new polygon with only those edges in exactly one of this or other
    merge(other) {
        let unionEdges = this.union(other).edges;
        let intersectionEdges = this.intersection(other).edges;
        let mergedEdges = [];

        for (var i = 0; i < unionEdges.length; i++) {
            let unionEdge = unionEdges[i];
            let unique = true;

            for (var j = 0; j < intersectionEdges.length; j++) {
                let intersectionEdge = intersectionEdges[j];
                if (unionEdge.eq(intersectionEdge)) {
                    unique = false;
                    break;
                }
            }

            if (unique) {
                mergedEdges.push(unionEdge);
            }
        }

        return new Polygon(mergedEdges);
    }

    draw() {
        this.edges.map(edge => edge.draw());
    }

    toString() {
        return `Polygon[${this.edges.map(edge => edge.toString())}]`;
    }
}

class Vector2d {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }

    scale(n) {
        return new Vector2d(this.x * n, this.y * n);
    }

    add(other) {
        return new Vector2d(this.x + other.x, this.y + other.y);
    }

    subtract(other) {
        return new Vector2d(this.x - other.x, this.y - other.y);
    }
}

function randomIndex(list) {
    return Math.floor(list.length * Math.random());
}

function randomIndexList(list) {
    let indexList = [];
    for (var n = 0; n < list.length; n++) {
        indexList.push(n);
    }

    let i = 0;
    let j = 0;
    let temp;

    for (i = indexList.length - 1; i > 0; i-=1) {
        j = Math.floor(Math.random() * (i + 1));
        temp = indexList[i];
        indexList[i] = indexList[j];
        indexList[j] = temp;
    }

    return indexList;
}

function weightedRandomIndex(list, f) {
    let total = 0;
    let cumulativeSums = [];

    for (var i = 0; i < list.length; i++) {
        total += f(list[i]);
        cumulativeSums.push(total);
    }

    let rand = Math.random() * total;
    let idx = 0;
    while (cumulativeSums[idx] < rand) {
        idx++;
    }

    return idx;
}

function makeTriangle(startX, startY, inverted) {
    let vertices = [];

    vertices.push(new Point(startX, startY));
    vertices.push(new Point(startX + edgeLength, startY));

    if (inverted) {
        vertices.push(new Point(startX + edgeLength / 2, startY - edgeLength * sqrt3 / 2));
    } else {
        vertices.push(new Point(startX + edgeLength / 2, startY + edgeLength * sqrt3 / 2));
    }

    let lineSegments = [
        new LineSegment(vertices[0], vertices[1]),
        new LineSegment(vertices[1], vertices[2]),
        new LineSegment(vertices[2], vertices[0])
    ];

    return new Polygon(lineSegments);
}

function makePolygons() {
    let minIndex = Math.floor(-canvasSize * sqrt3 / edgeLength);
    let maxIndex = Math.ceil(canvasSize * sqrt3 / edgeLength);

    // Create all of the triangles
    let polygons = [];
    for (var i = minIndex; i < maxIndex; i++) {
        for (var j = minIndex; j < maxIndex; j++) {
            let start = horizontalVector.scale(i).add(diagonalVector.scale(j));   
            polygons.push(makeTriangle(start.x, start.y, false));
            polygons.push(makeTriangle(start.x, start.y, true));
        }
    }

    return polygons;
}

function mergePolygons(polygons) {
    // Merge some of the triangles
    let numMerges = polygons.length * fractionToMerge;
    for (var m = 0; m < numMerges; m++) {
        let i = weightedRandomIndex(polygons, weightFunction);
        let polygonToMerge = polygons[i];

        let mergeOrder = randomIndexList(polygons);
        for (var n = 0; n < mergeOrder.length; n++) {
            j = mergeOrder[n];
            if (i != j) {
                let otherPolygon = polygons[j];
                if (polygonToMerge.adjacent(otherPolygon)) {
                    let mergedPolygon = polygonToMerge.merge(otherPolygon);
                    polygons.splice(Math.max(i, j), 1);
                    polygons.splice(Math.min(i, j), 1);
                    polygons.push(mergedPolygon);
                    break;
                }
            }
        }
    }

    return polygons;
}

function translatePolygons(polygons) {
    return polygons.map(poly => poly.translate(dx, dy));
}

const sqrt3 = Math.sqrt(3);
const canvasSize = 100;

// Parameters
Canvas.setpenopacity(1);
const edgeLength = 6;
const fractionToMerge = 0.85;
const weightFunction = function(p) { return p.edges.length ** -2; }
const dx = edgeLength / 2;
const dy = edgeLength / (2 * sqrt3);

const turtle = new Turtle();
turtle.penup();

const horizontalVector = new Vector2d(edgeLength, 0);
const diagonalVector = new Vector2d(edgeLength / 2, edgeLength * sqrt3 / 2);

function walk(i) {
    let polygons = makePolygons();
    polygons = mergePolygons(polygons);
    polygons.map(p => p.draw());
    
    polygons = makePolygons();
    polygons = mergePolygons(polygons);
    polygons = translatePolygons(polygons);
    polygons.map(p => p.draw());

    return false;
}