function calculateLabelRelocation(labelWidths: number[], desiredCxs: number[], hostWidth: number, minSpaceBetween: number): number[] {
    if(labelWidths.length <= 0) return [];
    const leftOffset = labelWidths[0]/2;
    const rightOffset = labelWidths[labelWidths.length-1]/2;
    const maxValue = hostWidth - leftOffset - rightOffset;
    const aMinDistance: number[] = [];
    for(let i=0; i<labelWidths.length - 1; i++) {
        aMinDistance.push((labelWidths[i] + labelWidths[i+1])/2 + minSpaceBetween);
    }
    const aDesiredValue = desiredCxs.map(cx=>cx-leftOffset);
    const aRelocatedValue = compute(aDesiredValue, aMinDistance, maxValue);
    return aRelocatedValue.map(x=>x+leftOffset);
}
function compute(aDesiredValue: number[], aMinDistance: number[], maxValue: number) {
    if(aMinDistance.length < aDesiredValue.length) {
        aMinDistance = [0, ...aMinDistance];
    }
    const algorithm = new RelocationAlgorithm();
    for(let i=0; i<aDesiredValue.length; i++) {
        algorithm.addItem(aDesiredValue[i], aMinDistance[i]);
    }
    algorithm.setFinalBoundary(maxValue);
    return algorithm.getItemLocations();
}

class RelocationAlgorithm {
    desiredLocations: number[] = [];
    minDistanceWithPrevious: number[] = [];
    availableSpaceWithPrevious: number[] = [];
    addItem(desiredLocation: number, minDistanceWithPrevious: number): void {
        let toCompress =  this._getLastItemLocation() + minDistanceWithPrevious - desiredLocation;

        if(toCompress <= 0) {
            // new item can be placed perfectly, no need to move existing item
            this.availableSpaceWithPrevious.push(-toCompress);
            this.desiredLocations.push(desiredLocation);
            this.minDistanceWithPrevious.push(minDistanceWithPrevious);
            return;
        }

        let moveCoef = 2;
        for(let i=this.availableSpaceWithPrevious.length-1; i>=0; i--) {
            const availableSpace = this.availableSpaceWithPrevious[i];
            if(availableSpace <= 0) continue;
            const toMove = toCompress / moveCoef;
            if(availableSpace >= toMove) {
                this.availableSpaceWithPrevious[i] = availableSpace - toMove;
                break;
            }
            this.availableSpaceWithPrevious[i] = 0;
            toCompress -= availableSpace*moveCoef;
            moveCoef++;
        }
        this.availableSpaceWithPrevious.push(0);
        this.desiredLocations.push(desiredLocation);
        this.minDistanceWithPrevious.push(minDistanceWithPrevious);
    }
    setFinalBoundary(finalBoundaryLocation: number): void {
        let toMove = this._getLastItemLocation() - finalBoundaryLocation;
        if(toMove <= 0) return;
        for(let i=this.availableSpaceWithPrevious.length-1; i>=0; i--) {
            const availableSpace = this.availableSpaceWithPrevious[i];
            if(availableSpace <= 0) continue;
            if(availableSpace >= toMove) {
                this.availableSpaceWithPrevious[i] = availableSpace - toMove;
                break;
            }
            this.availableSpaceWithPrevious[i] = 0;
            toMove -= availableSpace;
        }
    }
    getItemLocations():number[] {
        const ret = [];
        let accumulatedDistance = 0;
        for(let i=0; i<this.minDistanceWithPrevious.length; i++) {
            accumulatedDistance += this.minDistanceWithPrevious[i] + this.availableSpaceWithPrevious[i];
            ret.push(accumulatedDistance);
        }
        return ret;
    }
    _getLastItemLocation():number {
        const s1 = this.minDistanceWithPrevious.reduce((s,x)=>s+x,0);
        const s2 = this.availableSpaceWithPrevious.reduce((s,x)=>s+x,0);
        return s1+s2;
    }
}

export default calculateLabelRelocation;