// (C) 2007-2019 GoodData Corporation
import { ExecuteAFM as AFM, Execution } from "@gooddata/typings";
import { zip } from "lodash";
import { IRandomDataResult } from "./dataResult";
import IAttributeLocatorItem = AFM.IAttributeLocatorItem;
import IAttributeSortItem = AFM.IAttributeSortItem;
import IMeasureLocatorItem = AFM.IMeasureLocatorItem;
import IMeasureSortItem = AFM.IMeasureSortItem;
import isAttributeSortItem = AFM.isAttributeSortItem;
import isMeasureLocatorItem = AFM.isMeasureLocatorItem;
import isMeasureSortItem = AFM.isMeasureSortItem;
import IResultAttributeHeaderItem = Execution.IResultAttributeHeaderItem;
import IResultDimension = Execution.IResultDimension;
import isAttributeHeader = Execution.isAttributeHeader;
import isAttributeHeaderItem = Execution.isAttributeHeaderItem;

const ROW_DIM = 0;
const COL_DIM = 1;

type ISortActions = ISortAction[][];

export interface ISortAction {
    sortIndex: number;
    direction: AFM.SortDirection;
    type: "headers" | "data";
}

export interface ISortEntry {
    originalIndex: number;
    values: any[];
}

interface ISortVector {
    from: number;
    to: number;
}

/**
 * This is thrown in case sort locators are not valid.
 */
export class SortDefinitionError {
    constructor(private readonly message: string) {
        this.message = message;
    }

    public getMessage() {
        return this.message;
    }
}

/**
 * Fun sort applies sortItems from resultSpec to headers and data. The sorting works as follows:
 *
 *   1. Create sort actions = definitions of what to sort on; these are derived from sort items and reflect
 *      multi-dimensional nature of sort. The actions specify index of row or column to sort on.
 *
 *   2. Sort actions are performed by dimension - row sorting is done first, then column sorting. The sort is done
 *      in multiple steps:
 *
 *      1.  Extract sort entries = values from result to sort by + original index of the values
 *      2.  Sort the entries
 *      4.  Obtain sort vectors = current entry index => original index in the entry
 *      5.  Apply sort vectors on both data and headers
 *
 * This sorting code seems to be able to deal with any combination that the real backend can accept.
 */
export class FunSort {
    constructor(private readonly result: IRandomDataResult) {
        this.result = result;
    }

    public run(sortItems: AFM.SortItem[]) {
        if (sortItems === undefined || sortItems.length === 0) {
            return;
        }

        const sortActions = this.createSortActions(sortItems);

        // Calculate sort vectors first => no chance indexes in sort actions will get hosed
        const rowVectors = this.sortVector(sortActions, ROW_DIM);
        const columnVectors = this.sortVector(sortActions, COL_DIM);

        // Finally do the sort
        this.sort([rowVectors, columnVectors]);
    }

    private createSortActions(sortItems: AFM.SortItem[]): ISortActions {
        const sortActions: ISortAction[][] = [[], []];
        const { dims, measureHeaderItems } = this.result;

        sortItems.forEach(item => {
            if (isAttributeSortItem(item)) {
                /*
                 * Attribute sorts are always done on the header items (since that's where attr elements are). The
                 * code needs to figure out on which dimension is the sort happening - to achieve this code looks
                 * at result dimensions
                 */

                const match = dims.map(dim =>
                    dim.headers.findIndex(header => {
                        return (
                            isAttributeHeader(header) &&
                            header.attributeHeader.localIdentifier ===
                                item.attributeSortItem.attributeIdentifier
                        );
                    }),
                );

                if (match[ROW_DIM] > -1) {
                    sortActions[ROW_DIM].push({
                        sortIndex: findHeaderGroupIndexForItem(item, dims[ROW_DIM]),
                        direction: item.attributeSortItem.direction,
                        type: "headers",
                    });
                } else if (match[COL_DIM] > -1) {
                    sortActions[COL_DIM].push({
                        sortIndex: findHeaderGroupIndexForItem(item, dims[1]),
                        direction: item.attributeSortItem.direction,
                        type: "headers",
                    });
                } else {
                    throw new SortDefinitionError(
                        `Bad sort - attribute ${item.attributeSortItem.attributeIdentifier} not in AFM`,
                    );
                }
            } else if (isMeasureSortItem(item)) {
                /*
                 * Measure sorts are done on the data itself. The code needs to figure out which dimension to
                 * sort on.
                 */
                if (measureHeaderItems[ROW_DIM] !== undefined) {
                    const sortIndex = this.findSortIndex(item, ROW_DIM);

                    sortActions[COL_DIM].push({
                        sortIndex,
                        direction: item.measureSortItem.direction,
                        type: "data",
                    });
                } else if (measureHeaderItems[COL_DIM] !== undefined) {
                    const sortIndex = this.findSortIndex(item, COL_DIM);

                    sortActions[ROW_DIM].push({
                        sortIndex,
                        direction: item.measureSortItem.direction,
                        type: "data",
                    });
                } else {
                    throw new SortDefinitionError("Bad sort - no measureGroup but have measureSortItem");
                }
            }
        });

        return sortActions;
    }

    /**
     * This method evaluates measure sort item locators.
     *
     * @param sortItem measure sort item to evaluate
     * @param dimension dimension in which to evaluate (ROW/COL)
     * @returns index within the dimension to sort by
     */
    private findSortIndex(sortItem: IMeasureSortItem, dimension: number) {
        const dim = this.result.dims[dimension];
        const headers = this.result.headerItems[dimension];
        const measureHeaders = this.result.measureHeaderItems[dimension];
        const locators = sortItem.measureSortItem.locators;

        // find measure item locator within locators
        const measureLocatorIdx = locators.findIndex(locator => isMeasureLocatorItem(locator));

        // it must be there, otherwise this is not measure sort item :/
        if (measureLocatorIdx === -1) {
            throw new SortDefinitionError("Bad sort - no measure locator");
        }

        // single out measure locator definition...
        const measureLocator = locators[measureLocatorIdx] as IMeasureLocatorItem;

        // ... and then all attribute locators
        const attributeLocators: IAttributeLocatorItem[] = locators.filter(
            (_, idx) => idx !== measureLocatorIdx,
        ) as IAttributeLocatorItem[];

        // go through measure headers and identify all indexes where measure with the desired locator exists
        const possibleMatches = measureHeaders
            .map((measure, idx) => {
                if (
                    measure.measureHeaderItem.localIdentifier ===
                    measureLocator.measureLocatorItem.measureIdentifier
                ) {
                    return idx;
                } else {
                    return -1;
                }
            })
            .filter(idx => idx > -1);

        if (possibleMatches.length === 0) {
            throw new SortDefinitionError(
                `Bad sort - measure locator "${
                    measureLocator.measureLocatorItem.measureIdentifier
                }" is invalid`,
            );
        }

        // find indexes of header groups for attributes used in locators
        const headerGroupIndexes = attributeLocators.map(locator =>
            findHeaderGroupIndexForLocator(locator, dim),
        );

        // evaluate all possible matches...
        const exactMatches = possibleMatches
            .map(headerIndex => {
                if (attributeLocators.length === 0) {
                    return { match: true, headerIndex };
                }

                // ... see whether all remaining locators match
                const match = attributeLocators.every((attributeLocator, locIdx) => {
                    // find header group index (== index to array with all headers for the attribute) for this locator
                    const headerGroupIndex = headerGroupIndexes[locIdx];

                    if (headerGroupIndex === -1) {
                        const id = attributeLocator.attributeLocatorItem.attributeIdentifier;

                        throw new SortDefinitionError(
                            `Bad sort - attribute "${id}" not in same dimension as measure`,
                        );
                    }

                    // check the item on the column
                    const headerItem = headers[headerGroupIndex][headerIndex];

                    return (
                        isAttributeHeaderItem(headerItem) &&
                        headerItem.attributeHeaderItem.uri === attributeLocator.attributeLocatorItem.element
                    );
                });

                return { match, headerIndex };
            })
            .filter(result => result.match);

        if (exactMatches.length > 1) {
            throw new SortDefinitionError("Bad sort - ambiguous locator");
        } else if (exactMatches.length === 0) {
            throw new SortDefinitionError("Bad sort - locator does not match a thing");
        }

        return exactMatches[0].headerIndex;
    }

    private sortVector(sortActions: ISortActions, dimension: number): ISortVector[] {
        const dimActions = sortActions[dimension];

        if (dimActions.length === 0) {
            return [];
        }

        const data: any[][] = this.result.data;

        const entries: ISortEntry[] = zip(
            ...dimActions.map(action => {
                if (action.type === "headers") {
                    /*
                     * Sorting by headers => values of the desired headers from the respective dimension
                     */
                    return this.result.headerItems[dimension][action.sortIndex].map(
                        hi => (hi as IResultAttributeHeaderItem).attributeHeaderItem.name,
                    );
                } else {
                    if (dimension === ROW_DIM) {
                        /*
                         * when sorting rows between each other, extract value from particular column in sheet of data
                         */

                        if (Array.isArray(data[0])) {
                            // two dim data => extract column from each row
                            return data.map(row => row[action.sortIndex]);
                        }

                        // one dim data => get value at index
                        return data[action.sortIndex];
                    } else {
                        if (Array.isArray(data[0])) {
                            // two dim data => extract entire row
                            return data[action.sortIndex];
                        }

                        // one dim data => get the whole row
                        return data;
                    }
                }
            }),
        ).map((values, originalIndex) => {
            return {
                values,
                originalIndex,
            };
        });

        // const sortedEntries = mergeSort(entries, createComparator(dimActions));
        entries.sort(createComparator(dimActions));

        return entries
            .map((entry, idx) => {
                return {
                    from: entry.originalIndex,
                    to: idx,
                };
            })
            .filter(vector => vector.from !== vector.to);
    }

    private sort(sortDims: ISortVector[][]) {
        sortDims.forEach((sort, dim) => {
            if (sort.length === 0) {
                return;
            }

            const headers = this.result.headerItems[dim];
            const data: any[][] = this.result.data;

            headers.forEach(header => {
                this.sortArray(sort, header);
            });

            this.sortArray(sort, this.result.measureHeaderItems[dim]);

            if (dim === ROW_DIM) {
                this.sortArray(sort, data);
            } else {
                data.forEach(row => {
                    this.sortArray(sort, row);
                });
            }
        });
    }

    private sortArray<T>(sort: ISortVector[], array: T[]) {
        if (array === undefined || array.length === 0) {
            return;
        }

        const stash = {};

        sort.forEach(vector => {
            // stash the element that will be replaced
            stash[vector.to] = array[vector.to];
            const stashed = stash[vector.from];

            // then replace the element
            array[vector.to] = stashed !== undefined ? stashed : array[vector.from];
        });
    }
}

export type SortEntryComparator = (a: ISortEntry, b: ISortEntry) => number;

export function createComparator(sortItems: ISortAction[]): SortEntryComparator {
    return (a: ISortEntry, b: ISortEntry): number => {
        let idx = 0;

        for (const item of sortItems) {
            let left;
            let right;

            if (item.type === "data") {
                left = parseFloat(a.values[idx]);
                right = parseFloat(b.values[idx]);
            } else {
                left = a.values[idx];
                right = b.values[idx];
            }

            if (left < right) {
                return -1 * (item.direction === "asc" ? 1 : -1);
            } else if (left > right) {
                return item.direction === "asc" ? 1 : -1;
            }

            idx++;
        }

        /*
         * Two items are never equal - tie-breakers are solved by comparing placement in the original
         * array. This leads to stable sorting - items with equal sort values are in the same order as
         * they were in the original array.
         */
        return a.originalIndex < b.originalIndex ? -1 : 1;
    };
}

function findHeaderGroupIndexForLocator(locator: IAttributeLocatorItem, dim: IResultDimension): number {
    return findHeaderById(locator.attributeLocatorItem.attributeIdentifier, dim);
}

function findHeaderGroupIndexForItem(sortItem: IAttributeSortItem, dim: IResultDimension): number {
    return findHeaderById(sortItem.attributeSortItem.attributeIdentifier, dim);
}

function findHeaderById(localIdentifier: string, dim: IResultDimension): number {
    return dim.headers.findIndex(header => {
        return isAttributeHeader(header) && header.attributeHeader.localIdentifier === localIdentifier;
    });
}