pMedian.ts

namespace pMedian {
    export class VNS<T> {
        private _demands: Map<string, number>
        public get demands(): Array<[T, number]> {
            let result = new Array<[T, number]>(this._demands.size);
            let idx = 0;
            this._demands.forEach((degeneracy, demandKey) => {
                result[idx] = [this.unhash(demandKey), degeneracy];
                idx++
            });
            return result;
        }

        private _facilities: Array<string>;
        public get facilities(): Array<T> {
            let result = new Array<T>();
            for (const [idx, facility] of this._facilities.entries()) {
                result[idx] = this.unhash(facility);
            }
            return result;
        }

        private _metricLookup: Map<string, number>;
        private metric(facilityKey: string, demandKey: string): number {
            return this._metricLookup.get(facilityKey + demandKey)
        }

        private _demandNeighbors: Map<string, Map<string, number>>;
        private _facilityNeighbors: Map<string, Map<string, number>>;

        /**
         * Creates an instance of GA_pMeanSolver.
         * @param {Array<T>} demands
         * @param {Array<T>} facilities
         * @param {Number} _n - number of facilities to be placed
         * @param {(arg0: T, arg1: T) => Number} metric: a function to measure the distance from a demand to some facility
         * @memberof GA
         */
        constructor(
            demands: Array<T>,
            facilities: Array<T>,
            private _n: number,
            metric: (facility: T, demand: T) => number,
            private hash: (t: T) => string,
            private unhash: (hash: string) => T
        ) {
            this._demands = new Map<string, number>();
            let demandsMap = new Map<string, number>();
            demands.forEach(demand => {
                let demandKey = this.hash(demand);
                if (this._demands.has(demandKey)) {
                    this._demands.set(demandKey, this._demands.get(demandKey) + 1);
                } 
                else {
                    this._demands.set(demandKey, 1);
                }
            });

            this._facilities = new Array<string>(facilities.length);
            this._metricLookup = new Map<string, number>();
            for (const [idx, facility] of facilities.entries()) {
                let facilityKey = this.hash(facility);
                this._facilities[idx] = facilityKey;
                for (const demandKey of this._demands.keys()) {
                    this._metricLookup.set(facilityKey + demandKey, this.metric(facilityKey, demandKey));
                }
            }
        }

        public initialSolution(): void {
            // first facility to place: 1-median
            let candidates = this._facilities.slice(0);
            let minTotalCost = Number.MAX_VALUE;
            let firstFacility = candidates[0];
            let firstFacilityIdx = 0;
            let costs: Array<number>
            this._demandNeighbors = new Map<string, Map<string, number>>();
            for (const [i, facility] of candidates.entries()) {
                let totalCost = 0;
                let thisCosts = new Array<number>(this._demands.size);
                let idx = 0;
                this._demands.forEach((degeneracy, demand) => {
                    let cost = degeneracy * this.metric(facility, demand);
                    totalCost += cost;
                    thisCosts[idx] = cost;
                    idx++;
                });
                if (totalCost < minTotalCost) {
                    minTotalCost = totalCost;
                    firstFacility = facility;
                    firstFacilityIdx = i;
                    costs = thisCosts;
                }
            }
            candidates.splice(firstFacilityIdx, 1);
            let neighbor = new Map<string, number>();
            let idx = 0;
            for (const demand of this._demands.keys()) {
                neighbor.set(demand, costs[idx]);
                idx++;
            }
            this._demandNeighbors.set(firstFacility, neighbor);

            // greadily find the n - 1 left facilities to place
            for (let i = 1; i < this._n; i++) {
                let maxDecreasedCost = Number.MAX_VALUE;
                let facilityToPlace = candidates[0];
                let facilityToPlaceIdx = 0;
                let verticeToModify: Array<[string, Array<[string, number]>]>;
                for (const [i, facility] of candidates.entries()) {
                    let decreasedCost = 0;
                    let verticeToModifyCandidate = new Array<[string, Array<[string, number]>]>();
                    for (const [openedFacility, vertice] of this._demandNeighbors.entries()) {
                        let demandsToReplace = new Array<[string, number]>();
                        for (const [demand, cost] of vertice.entries()) {
                            let newCost = this._demands.get(demand) * this.metric(facility, demand);
                            if (newCost < cost) {
                                decreasedCost += cost - newCost;
                                demandsToReplace.push([demand, newCost]);
                            }
                        }
                        verticeToModifyCandidate.push([openedFacility, demandsToReplace]);
                    }
                    if (decreasedCost > maxDecreasedCost) {
                        facilityToPlace = facility;
                        facilityToPlaceIdx = i;
                        verticeToModify = verticeToModifyCandidate;
                    }
                }
                candidates.splice(facilityToPlaceIdx, 1);
                let newNeighbor = new Map<string, number>();
                verticeToModify.forEach(tuple0 => {
                    let openedFacilityKey = tuple0[0];
                    let thisNeighbor = this._demandNeighbors.get(openedFacilityKey);
                    tuple0[1].forEach(tuple1 => {
                        let demandKey = tuple1[0];
                        let newCost = tuple1[1];
                        thisNeighbor.delete(demandKey);
                        newNeighbor.set(demandKey, newCost);
                    });
                    this._demandNeighbors.set(openedFacilityKey, thisNeighbor);
                });
                this._demandNeighbors.set(facilityToPlace, newNeighbor);
            }
            
            this._facilityNeighbors = new Map<string, Map<string, number>>();
            for (const placedFacility of this._demandNeighbors.keys()) {
                this._facilityNeighbors.set(placedFacility, new Map<string, number>());
            }
            candidates.forEach(facility => {
                let minDistance = Number.MAX_VALUE;
                let closestFacility = facility;
                for (const placedFacility of this._demandNeighbors.keys()) {
                    let distance = this.metric(placedFacility, facility);
                    if (distance < minDistance) {
                        minDistance = distance;
                        closestFacility = placedFacility;
                    }
                }
                this._facilityNeighbors.get(closestFacility).set(facility, minDistance);
            });
        }

        public shake(k: number): string {
            let kthNeighbor = this._facilityNeighbors.get(Array.from(this._facilityNeighbors.keys())[k]);
            let closedFacilities = Array.from(kthNeighbor.keys());
            return closedFacilities[Math.floor(Math.random() * closedFacilities.length)]
        }

        private substitute(
            demandNeighbors: Map<string, Map<string, number>>, 
            facilityNeighbors: Map<string, Map<string, number>>, 
            openedFacility: string, 
            closedFacilities: string
            ): void {

            }

        public vns(): void {
            let k = 0;
            let placedFacilityKeys = new Array<string>(this._n)
            while (k < this._n) {

            }
        }
    }
    
    /**
     * P-median solver, an janky implementation of 
     * https://link.springer.com/content/pdf/10.1023/A:1026130003508.pdf
     *
     * @export
     * @class GA_pMedianSolver
     * @template T
     */
    export class GA<T> {
        private _demands: Map<string, number>
        public get demands(): Array<[T, number]> {
            let result = new Array<[T, number]>(this._demands.size);
            let idx = 0;
            for (const [demandKey, degeneracy] of this._demands.entries()) {
                result[idx] = [this.unhash(demandKey), degeneracy];
                idx++;
            }
            return result;
        }

        private _facilities: Array<string>;
        public get facilities(): Array<T> {
            let result = new Array<T>();
            for (const [idx, facility] of this._facilities.entries()) {
                result[idx] = this.unhash(facility);
            }
            return result;
        }

        private _density: number;
        public get density(): number {
            return this._density;
        }

        private _maxIter: number;
        public get maxIter(): number {
            return this._maxIter;
        }

        private _population: Array<Array<string>>;
        public get population(): Array<Array<string>> {
            return this._population;
        }

        private _populationSize: number;
        public get populationSize(): number {
            return this._populationSize;
        }

        private _metricLookup: Map<string, number>;
        private metric(facilityKey: string, demandKey: string): number {
            return this._metricLookup.get(facilityKey + demandKey)
        }
        
        /**
         * Creates an instance of GA_pMeanSolver.
         * @param {Array<T>} demands
         * @param {Array<T>} facilities
         * @param {Number} n - number of facilities to be placed
         * @param {(arg0: T, arg1: T) => Number} metic: a function to measure the distance from a demand to some facility
         * @memberof GA
         */
        constructor(
            demands: Array<T>,
            facilities: Array<T>,
            private n: number,
            metric: (facility: T, demand: T) => number,
            private hash: (t: T) => string,
            private unhash: (hash: string) => T,
            maxIter: number = 256
        ) {
            this._demands = new Map<string, number>();
            demands.forEach(demand => {
                let demandKey = this.hash(demand);
                if (this._demands.has(demandKey)) {
                    this._demands.set(demandKey, this._demands.get(demandKey) + 1);
                } 
                else {
                    this._demands.set(demandKey, 1);
                }
            });

            this._facilities = new Array<string>(facilities.length);
            this._metricLookup = new Map<string, number>();
            for (const [idx, facility] of facilities.entries()) {
                let facilityKey = this.hash(facility);
                this._facilities[idx] = facilityKey;
                for (const demandKey of this._demands.keys()) {
                    this._metricLookup.set(facilityKey + demandKey, metric(facility, this.unhash(demandKey)));
                }
            }

            this._density = Math.ceil(facilities.length / this.n);
            // this._maxIter = Math.ceil(this.demands.length * Math.sqrt(this.n));
            this._maxIter = maxIter;
            this._populationSize = this.calcPopulationSize();
        }

        private calcPopulationSize(): number {
            let s = this.combination(this.n, this._facilities.length);
            return Math.max(4, Math.ceil(this.n * Math.log(s) / 100 / this._density)) * this._density
        }

        public generatePopulations(size: number){
            let increment = Math.floor(size / this._density); // k
            this._population = new Array<Array<string>>(size);
            console.log(size, this._density, increment)

            let idx = 0;
            for (let i = 0; i < Math.floor(this._facilities.length / this.n); i++) {
                let pop = new Array<string>(this.n);
                for (let j = 0; j < this.n; j++) {
                    pop[j] = this._facilities[i * this.n + j]
                }
                this._population[idx] = pop;
                idx++;
            }

            // if n / p is not integer, fill the remaining slots with random facilities
            if (this._facilities.length % this.n > 0) {
                let pop = new Array<string>(this.n);
                let j = 0;
                for (let i = Math.floor(this._facilities.length / this.n) * this.n; i < this._facilities.length; i++) {
                    pop[j] = this._facilities[i];
                    j++;
                }
                pop = this.fillPopulation(pop, j);
                this._population[idx] = pop;
                idx++;
            }

            let pointer = 0;
            let cycleIdx = 0;
            while (cycleIdx < increment) {
                let pop = new Array<string>(this.n);
                for (let j = 0; j < this.n; j++) {
                    if (pointer >= this._facilities.length) {
                        cycleIdx++;
                        pointer = cycleIdx
                    }
                    pop[j] = this._facilities[pointer];
                    pointer += increment;
                }
                this._population[idx] = pop;
                idx++
            }

            while (idx < size) {
                let pop = new Array<string>(this.n);
                this.fillPopulation(pop, 0)
                this._population[idx] = pop;
                idx++;
            }
        }

        public isIdenticalPop(a: Array<string>, b: Array<string>): boolean {
            a.sort();
            b.sort();
            let result = true;
            for (const [idx, entry] of a.entries()) {
                if (!(b[idx] === entry)) {result = false; break}
            }
            return result
        }

        private fillPopulation(population: Array<string>, start: number): Array<string> {
            let remainingFacilities = new Array<string>();
            let excludes = new Set<string>();
            population.slice(0, start).forEach(pop=> {
                excludes.add(pop);
            });
            this._facilities.forEach(facility => {
                if (!excludes.has(facility)) {
                    remainingFacilities.push(facility)
                }
            });

            misc.shuffle(remainingFacilities)
            for (let i = start; i < population.length; i++) {
                population[i] = remainingFacilities[i];
            }
            return population
        }

        public selectParents(): [Array<string>, Array<string>] {
            let idxes = new Array<number>(this._populationSize);
            for (let idx = 0; idx < this._populationSize; idx++) {
                idxes[idx] = idx;
            }
            let parentsIdx = misc.shuffle(idxes).slice(0, 2);
            return [this._population[parentsIdx[0]], this._population[parentsIdx[1]]]
        }

        public generationOp(
            parents: [Array<string>, Array<string>]
        ): [Array<string>, number] {
            // let genes0 = new misc.ObjectSet(parents[0], this.isEqual, this.hash);
            // let genes1 = new misc.ObjectSet(parents[1], this.isEqual, this.hash);
            let genes0 = new Set<string>();
            parents[0].forEach(gene => {
                genes0.add(gene);
            });
            let genes1 = new Set<string>();
            parents[1].forEach(gene => {
                genes0.add(gene);
            });

            // Step 1. Take the union of the input members’ genes to obtain a draft member
            let draftMemberSet = misc.union(genes0, genes1);

            /* Step 2. Let the total number of genes in this draft member be m. Call the genes that are 
            * present in both parents fixed genes and the rest free genes.
            */
            let fixedGenes = misc.intersection(genes0, genes1);
            let freeGeneSet = misc.difference(draftMemberSet, fixedGenes);
            let freeGenes = Array.from(freeGeneSet);

            // Step 3. Compute the fitness value of this draft member.
            let distances = new Map<string, Map<string, number>>();
            freeGenes.forEach(gene => {
                distances.set(gene, new Map());
            });

            for (const demand of this._demands.keys()) {
                let minDistance = Number.MAX_VALUE;
                let closestFacility = freeGenes[0];
                freeGenes.forEach(facility => {
                    let distance = this.metric(facility, demand);
                    if (distance < minDistance) {
                        minDistance = distance;
                        closestFacility = facility;
                    }
                });
                let distance = distances.get(closestFacility);
                distance.set(demand, minDistance);
                distances.set(closestFacility, distance);
            }
            
            
            /* Step 4. Find the free gene that produces the minimum increase in the current fitness
            * value when deleted from the draft member, and delete it. Repeat this step until
            * freeGenes.length = n. Let this final solution be a candidate member.
            */
            while (freeGenes.length > this.n) {
                let minIncreasedFitness = Number.MAX_VALUE;
                let idxOfGeneToRemove = 0;
                let distancesUpdate = new Map<string, Map<string, number>>();

                // try to delete one gene(facility), calculate how much the total fitness increases
                for (const [idx, gene] of freeGenes.entries()) {
                    let demandsToReallocate = distances.get(gene);
                    let increasedFitness = 0;
                    let update = new Map();
                    
                    demandsToReallocate.forEach((_, demand) => {
                        let minDistance = Number.MAX_VALUE;
                        let closestFacility = gene;
                        for (const [idx1, gene1] of freeGenes.entries()) {
                            // skip the deleted gene
                            if (idx1 == idx) {continue};
                            let distance = this.metric(gene1, demand);
                            if (distance < minDistance) {
                                minDistance = distance;
                                closestFacility = gene1;
                            };
                        };

                        let degeneracy = this._demands.get(demand);
                        increasedFitness += degeneracy * (minDistance - distances.get(gene).get(demand));
                        if (!update.has(closestFacility)) {update.set(closestFacility, new Map());}
                        let distance = update.get(closestFacility);
                        distance.set(demand, minDistance);
                        update.set(closestFacility, distance);
                    });

                    if (increasedFitness < minIncreasedFitness) {
                        minIncreasedFitness = increasedFitness;
                        idxOfGeneToRemove = idx;
                        distancesUpdate = update;
                    };
                }

                // the gene to remove is found, remove it
                distances.delete(freeGenes[idxOfGeneToRemove]);
                distancesUpdate.forEach((map, gene) => {
                    let facility = distances.get(gene);
                    map.forEach((distance, demand) => {
                        facility.set(demand, distance);
                    });
                    distances.set(gene, facility);
                });
                freeGenes.splice(idxOfGeneToRemove, 1);
            }

            let fitness = 0;
            distances.forEach((facility, _) => {
                facility.forEach((distance, demandKey) => {
                    let degeneracy = this._demands.get(demandKey);
                    fitness += distance * degeneracy;
                });
            });

            return [freeGenes, fitness]
        }

        public fitness(genes: Array<string>): number {
            let fitness = 0;
            this._demands.forEach((degeneracy, demand) => {
                let minDistance = Number.MAX_VALUE;
                genes.forEach(facility => {
                    let distance = this.metric(facility, demand);
                    if (distance < minDistance) {minDistance = distance;}
                });
                fitness += degeneracy * minDistance;
            });
            return fitness
        }

    public replacementOp(
        candidate: Array<string>, 
        candidateFitness: number, 
        fitnessEnum: Array<[number, number]>,
        comparator: (a: [number, number], b: [number, number]) => number
        ) {
        let idx = 0;
        let maxFitness = 0;
        [idx, maxFitness] = fitnessEnum[0];

        /**
         * Step 1. If fitness value of the input candidate member is higher than the maximum fitness
         * value in the population, then discard this candidate member and terminate this
         * operator
         */
        if (candidateFitness >= maxFitness) {return}

        /**
         * Step 2. If the candidate member is identical to an existing member of the current popu-
         * lation, then discard this candidate member and terminate this operator.
         */
        for (const [_, pop] of this._population.entries()) {
            if (this.isIdenticalPop(candidate, pop)) {return}
        }

        // Step 3. Replace the worst member and update population
        // fitnessEnum.shift();
        fitnessEnum.splice(0, 1, [idx, candidateFitness])
        fitnessEnum.sort(comparator)
        this._population.splice(idx, 1, candidate);
        // misc.binaryInsert([idx, candidateFitness], fitnessEnum, comparator);
    }

        /**
         * Combination (n, k)
         * @private
         * @param {number} n
         * @param {number} k
         * @returns {number}
         * @memberof GA_pMeanSolver
         */
        private combination(n: number, k: number): number{
            if (n > Math.floor(k / 2)) {
                n = k - n;
            }

            let result: number = 1;
            for (let i = 0; i < n; i++) {
                result *= (k - i) / (n - i)
            }

            return result
        }

        public pMedian(log: (entry: string) => void): Array<T> {
            this.generatePopulations(this._populationSize);

            let comparator = function (a: [number, number], b: [number, number]): number {
                if (a[1] > b[1]) {return -1}
                if (a[1] == b[1]) {return 0}
                return 1
            };
            
            let fitnessEnum = new Array<[number, number]>();
            for (const [idx, pop] of this._population.entries()) {
                let fitness = this.fitness(pop);
                fitnessEnum.push([idx, fitness])
            };
            fitnessEnum.sort(comparator);

            let iter = 0;
            let best = this._population[fitnessEnum[fitnessEnum.length - 1][0]];
            while (iter < this._maxIter) {
                // Randomly select two members from the current population.
                let parents = this.selectParents();

                // Run the Generation Operator
                let candidate: Array<string>;
                let candidateFitness: number;
                [candidate, candidateFitness] = this.generationOp(parents);

                // Run the Replacement Operator
                this.replacementOp(candidate, candidateFitness, fitnessEnum, comparator);
                // console.log(fitnessEnum)

                // If the best solution found so far has not changed, then increment MaxIter
                let bestThisIter = this._population[fitnessEnum[fitnessEnum.length - 1][0]];
                // console.log('iter:', iter, '/', this.maxIter, fitnessEnum[fitnessEnum.length - 1][1], fitnessEnum[0][1], candidateFitness)
                log('iter: ' + ' ' + iter + ' ' + '/' + ' ' + 
                this.maxIter + ' ' + fitnessEnum[fitnessEnum.length - 1][1]
                 + ' ' + fitnessEnum[0][1] + ' ' + candidateFitness);
                if (this.isIdenticalPop(bestThisIter, best)) {
                    iter++;
                }
                else {
                    best = bestThisIter;
                }
            }
            return best.map(this.unhash)
        }
    }
}