/*
  Copyright (c) 2021 Corinne Diakhoumpa et Erwan Iev-Le Tac

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/

const fs = require("fs");
const assert = require('assert').strict;
const utils = require('./utils');

// This program calculates the permutation associated to "Inversions" and
// generates the diagram to visualize the action of the permutation on the
// string of phonemes.
//
// To our knowledge, 229 is not involved here, but 42 is somewhat famous:
// https://en.wikipedia.org/wiki/42_(number)
//
// S_42 is of order 1405006117752879898543142606244511569936384000000000 =
// 2^39 * 3^19 * 5^9 * 7^6 * 11^3 * 13^3 * 17^2 * 19^2 * 23 * 29 * 31 * 37 * 41
//
// The permutation has one cycle of order 9, one cycle of order 6, two cycles of
// order 5, two cycles of order 3, three transpositions and five fixed points
// and 42 = 1*9 + 6 + 2*5 + 2*3 + 3*2 + 5
// Its order is lcm(9, 6, 5, 3, 2) = 90.

// Input and output of phonemes. API symbols ɛ̃ and ɑ̃ are represented by E and A
// so that they are encoded on one character.
const input = "lɛmjEnasyʁøsɛpaʁɔløpɔɛtlɔʁAsømAtalAɡølɛfɛt";
const output = "lɛpɔɛmøsatyʁnjElɛʁɔmAsøsApaʁɔlølɛfɛtøɡalAt";
function toAPI(s) {
    return s.replace("E", "ɛ̃").replace("A", "ɑ̃");
}

// Recursive function to generate a produce of transpositions that transforms
// the substring of B starting at start_index, to a substring of A stating at
// start_index.
// The result is an array [[i0, j0], [i1, j1], ... [iN, jN]] representing
// The product of transpositions (i0, j0)(i1, j1)...(iN, jN).
function GetInvertOfProductOfTranspositions(A, B, start_index) {
    start_index = start_index || 0;
    assert.strictEqual(A.length, B.length);

    // If start_index is the end of the string, nothing to permute.
    if (start_index >= A.length) {
        assert.strictEqual(A, B);
        return [];
    }

    // Find the position of A[start_index] in B.
    let i = B.indexOf(A[start_index], start_index);
    assert(i >= 0);

    // Apply a transposition (start_index, i) to the string B to ensure
    // B[start_index] becomes A[start_index].
    let tau;
    if (i != start_index) {
        B = B.substring(0, start_index) + B[i] +
            B.substring(start_index + 1, i) + B[start_index] +
            B.substring(i + 1);
        tau = [start_index, i];
    }

    // Call recursively on the rest of the string and append tau.
    let result = GetInvertOfProductOfTranspositions(A, B, start_index + 1);
    if (tau)
        result.push(tau);
    return result;
}

// Generate a product of disjoint cycles from a permutation represented as a
// product of transpositions.
// The result is of the form [c0, c1, c2, c3, ... ] where each ci is a cycle c
// represented as an array [ci[0], c(ci[0]), c^2(ci[0]), c^3(ci[0]), ...]. It is
// put in canonical form:
// https://en.wikipedia.org/wiki/Permutation#Canonical_cycle_notation_(a.k.a._standard_form)
function GetProductOfDisjointCyclesFromProductOfTranspositions(transpositions, N) {
    // First represent σ as an array [σ(0), σ(1), ... σ(N-1)].
    let elements = new Array(N);
    for (let i = 0; i < N; i++) {
        elements[i] = i;
        transpositions.forEach(tau => {
            if (elements[i] === tau[0])
                elements[i] = tau[1];
            else if (elements[i] === tau[1])
                elements[i] = tau[0];
        });
    }

    // Calculate the orbit of each element for the given σ to get cycles.
    let cycles = [];
    for (let i = 0; i < N; i++) {
        if (elements[i] === -1)
            continue; // already belongs to the orbit of a previous index.

        // Calculate i, σ(i), σ^2(i), σ^3(i), ..., until we go back to i.
        // Also determine the largest index found to put in normal form.
        let e = i;
        let cycle = [e];
        let indexLargest = 0;
        while (elements[e] != cycle[0]) {
            e = elements[e];
            cycle.push(e);
            if (e > cycle[indexLargest])
                indexLargest = cycle.length - 1;
        }
        
        // Rewrite that cycle in normal form i.e. start from the largest index.
        let normalCycle = [];
        for (let i = indexLargest; normalCycle.length < cycle.length;
             i = (i + 1) % cycle.length) {
            elements[cycle[i]] = -1; // Remember to skip this element next time.
            normalCycle.push(cycle[i]);
        }
        cycles.push(normalCycle);
    }
    
    // Put the array of cycles in normal form i.e. order cycles according to
    // their first items.
    cycles.sort((c1, c2) => {
        return c1[0] < c2[0] ? -1 : (c1[0] > c2[0] ? 1 : 0);
    });
    return cycles;
}

// Get the string B obtained by applying a product of cycles to a string A.
function ApplyProductOfDisjointCycles(cycles, A) {
    let B = "";
    for (let i = 0; i < A.length; i++) {
        let cycle = cycles.find(c => c.includes(i));
        B += A[cycle[(cycle.indexOf(i) + 1) % cycle.length]];
    }
    return B;
}

// Serialize the product of disjoint cycles.
// This converts to 1-based indexing and excludes cycle of length 1.
function SerializeProductOfDisjointCycles(cycles) {
    let output = "";
    cycles.forEach(cycle => {
        if (cycle.length === 1)
            return;
        output += `(${Array.from(cycle, n => n + 1)})`;
    });
    return output.replace(/,/g, " ");
}

console.log("Input:", toAPI(input));
console.log("Output:", toAPI(output));
console.log("Length:", input.length);

// Get the  permutation to transform from input to ouput. Note that reversing
// the order of transpositions really gives the invert of the permutation.
let transpositions =
    GetInvertOfProductOfTranspositions(input, output).reverse();

// Decompose the permutation as a product of disjoint cycles.
let cycles = GetProductOfDisjointCyclesFromProductOfTranspositions(
    transpositions, input.length);

// Ensure that the image of input by the permutation is output.
assert.strictEqual(ApplyProductOfDisjointCycles(cycles, input), output);
console.log(`σ = ${SerializeProductOfDisjointCycles(cycles)}`)

// Note that the strings contain repeated phonemes so there are more than one
// permutation possible. For example, an obvious option is the following which
// merges a 2-cycle, the 6-cycle and the 9-cycle into one big 17-cycle.
let otherCycles = GetProductOfDisjointCyclesFromProductOfTranspositions(
    GetInvertOfProductOfTranspositions(output, input), input.length);
assert.strictEqual(ApplyProductOfDisjointCycles(otherCycles, input), output);
assert.notStrictEqual(otherCycles, cycles);
console.log(`σ' = ${SerializeProductOfDisjointCycles(otherCycles)}`)

// More generally, by composition with a transposition that has trivial action
// on the phoneme string, one can get another permutation with the same action
// on the phoneme string but with one cycle splitted or two cycles merged. For
// example the 5-cycles containing the "l" phoneme could be splitted into a
// 2-cycle and a 3-cycle. We haven't tried to find a more optimal permutation
// but we like the visual rendering of the chosen one.

// Finally, generate the diagram. For convenience, the cycles are ordered by
// their lengths.
cycles.sort((c1, c2) => {
    return c1.length > c2.length ? -1 : (c1.length < c2.length ? 1 : 0);
});

// Draw the orbit of the action of the cycle as phonemes evenly positioned in
// the clockwise direction on the circle of center (x, y) and specified radius.
// For center of length 1, radius must be 0 and actually the unique phoneme is
// placed at position (x, y).
function DrawPhonemesOnCircle(x, y, radius, cycle, input) {
    assert(radius === 0 || cycle.length > 1);
    let s = `<g transform="translate(${x}, ${y})">`;
    for (let i = 0; i < cycle.length; i++) {
        let theta = 2 * Math.PI * i / cycle.length;
        s += `<g transform="translate(${radius * Math.cos(theta)}, ${radius * Math.sin(theta)})"><text style="font-weight: bold" dx="-5px" dy="5px">${toAPI(input[cycle[i]])}</text></g>`;
    }

    if (cycle.length > 1) {
        for (let i = 0; i < cycle.length; i++) {
            thetaS = 2 * Math.PI * (i + .1) / cycle.length;
            thetaM = 2 * Math.PI * ((2*i+1)/2) / cycle.length;
            thetaE = 2 * Math.PI * (i + 1 - .1) / cycle.length;
            s += `<path d="M${radius * Math.cos(thetaS)},${radius * Math.sin(thetaS)} Q${(radius+10) * Math.cos(thetaM)},${(radius+10) * Math.sin(thetaM)} ${radius * Math.cos(thetaE)},${radius * Math.sin(thetaE)}" fill="none" stroke="black"/>`;
        }
    }

    s += "</g>"
    return s;
}

// This serializes the orbits of the action of the cycle as phonemes, for use
// in the SVG description.
function SerializeActionOfProductOfDisjointCyclesOnPhonemes(cycles, input) {
    let output = "";
    for (let i = 0; i < cycles.length; i++) {
        if (i > 0)
            output += i < cycles.length - 1 ? ", " : " et ";
        output += "{";
        for (let j = 0; j < cycles[i].length; j++) {
            if (j > 0)
                output += ", ";
            output += `${toAPI(input[cycles[i][j]])}`;
        }
        output += "}";
    }
    return output;
}

// Now we call DrawPhonemesOnCircle on each cycle, with some clever layout,
// nesting orbits by increasing size and keeping some kind of symmetry.
// The choice is very specific to the calculated permutation!

const w = 400;
const h = 400;
const theta = 2 * Math.PI / 3;
const scale = .6;

const filename = "inversions.svg"
console.log(`Generate ${filename}...`)
let stream = fs.createWriteStream(filename);
stream.write(utils.svgProlog(`width="8.5cm" height="8.5cm" viewBox="0 0 ${w+10} ${h+10}"`));
stream.write(utils.svgHeaderWithCopyLeft("Inversion", `Un diagramme avec des ronds emboîtés. Le plus grand contient trois ronds de taille moyenne. Le premier de ces ronds contient lui même trois petits ronds tandis que les deux autres contiennent seulement un petit rond. Des lettres sont réparties régulièrement sur chacun des ronds, le nombre exacte de lettres dépendant de la taille du rond. Les cinq petits ronds ont de plus une lettre placée en leur centre. Cela donne les quatorze ensembles suivants: ${SerializeActionOfProductOfDisjointCyclesOnPhonemes(cycles, input)}`));
stream.write('<g style="font-family: DejaVu Sans; font-size: 12pt;" transform="translate(5, 5)">');

// Level 1
let r0 = w/2;
let x0 = w/2;
let y0 = h/2;
stream.write(DrawPhonemesOnCircle(x0, y0, r0, cycles[0], input));

// Level 2
let x1 = x0 + r0/2 * Math.cos(Math.PI + 0 * theta);
let y1 = y0 + r0/2 * Math.sin(Math.PI + 0 * theta);
let r1 = r0 * scale * cycles[1].length / cycles[0].length;
stream.write(DrawPhonemesOnCircle(x1, y1, r1, cycles[1], input));

let x2 = x0 + r0/2 * Math.cos(Math.PI + 1 * theta);
let y2 = y0 + r0/2 * Math.sin(Math.PI + 1 * theta);
let r2 = r0 * scale * cycles[2].length / cycles[0].length;
stream.write(DrawPhonemesOnCircle(x2, y2, r2, cycles[2], input));

let x3 = x0 + r0/2 * Math.cos(Math.PI + 2 * theta);
let y3 = x0 + r0/2 * Math.sin(Math.PI + 2 * theta);
let r3 = r0 * scale * cycles[3].length / cycles[0].length;
stream.write(DrawPhonemesOnCircle(x3, y3, r3, cycles[3], input));

// Level 3
let x4 = x1 + (r1/2) * Math.cos(1 * theta);
let y4 = y1 + (r1/2) * Math.sin(1 * theta);
let r4 = r1 * scale * cycles[4].length / cycles[1].length;
stream.write(DrawPhonemesOnCircle(x4, y4, r4, cycles[4], input));

let x5 = x1 + (r1/2) * Math.cos(2 * theta);
let y5 = y1 + (r1/2) * Math.sin(2 * theta);
let r5 = r1 * scale * cycles[5].length / cycles[1].length;
stream.write(DrawPhonemesOnCircle(x5, y5, r5, cycles[5], input));

let x6 = x1 + (r1/2) * Math.cos(3 * theta);
let y6 = y1 + (r1/2) * Math.sin(3 * theta);
let r6 = r1 * scale * cycles[6].length / cycles[1].length;
stream.write(DrawPhonemesOnCircle(x6, y6, r6, cycles[6], input));

let x7 = x2;
let y7 = y2;
let r7 = r2 * scale * cycles[7].length / cycles[2].length;
stream.write(DrawPhonemesOnCircle(x7, y7, r7, cycles[7], input));

let x8 = x3;
let y8 = y3;
let r8 = r3 * scale * cycles[8].length / cycles[3].length;
stream.write(DrawPhonemesOnCircle(x8, y8, r8, cycles[8], input));

// Level 4
stream.write(DrawPhonemesOnCircle(x4, y4, 0, cycles[9], input));
stream.write(DrawPhonemesOnCircle(x5, y5, 0, cycles[10], input));
stream.write(DrawPhonemesOnCircle(x6, y6, 0, cycles[11], input));
stream.write(DrawPhonemesOnCircle(x7, y7, 0, cycles[12], input));
stream.write(DrawPhonemesOnCircle(x8, y8, 0, cycles[13], input));

stream.write("</g>")
stream.write("</svg>")
stream.end();
console.log("done")