import { UnboundedZone, Zone } from "../types/misc";
/**
 * ####################################################
 * # INTRODUCTION
 * ####################################################
 *
 * This file contain the function recomputeZones.
 * This function try to recompute in a performant way
 * an ensemble of zones possibly overlapping to avoid
 * overlapping and to reduce the number of zones.
 *
 * It also allows to remove some zones from the ensemble.
 *
 * In the following example, 2 zones are overlapping.
 * Applying recomputeZones will return zones without
 * overlapping:
 *
 * ["B3:D4", "D2:E3"]         ["B3:C4", "D2:D4", "E2:E3"]
 *
 *      A B C D E                    A B C D E
 *    1       ___                  1       ___
 *    2   ___|_  |                 2   ___| | |
 *    3  |   |_|_|      --->       3  |   | |_|
 *    4  |_____|                   4  |___|_|
 *    6                            6
 *    7                            7
 *
 *
 * In the following example, 2 zones are contiguous.
 * Applying recomputeZones will return only one zone:
 *
 *  ["B2:B3", "C2:D3"]               ["B2:D3"]
 *
 *       A B C D E                   A B C D E
 *     1   _ ___                   1   _____
 *     2  | |   |        --->      2  |     |
 *     3  |_|___|                  3  |_____|
 *     4                           4
 *
 *
 * In the following example, we want to remove a zone
 * from the ensemble. Applying recomputeZones will
 * return the ensemble without the zone to remove:
 *
 *    remove ["C3:D3"]           ["B2:B4", "C2:D2",
 *                                "C4:D4", "E2:E4"]
 *
 *       A B C D E F                 A B C D E F
 *     1   _______                 1   _______
 *     2  |       |       --->     2  | |___| |
 *     3  |  xxx  |                3  | |___| |
 *     4  |_______|                4  |_|___|_|
 *     5                           5
 *
 *
 * The exercise seems simple when we have only 2 zones.
 * But with n zones and in a performant way, we want to
 * avoid comparing each zone with all the others.
 *
 *
 * ####################################################
 * # Methodological approach
 * ####################################################
 *
 * The methodological approach to avoid comparing each
 * zone with all the others is to use a data structure
 * that allow to quickly find which zones are
 * overlapping with any other given zone.
 *
 * Here the idea is to profile the zones at the columns level.
 *
 * To do that, we propose to use a data structure
 * composed of 2 parts:
 * - profilesStartingPosition: a sorted number array
 * indicating on which columns a new profile begins.
 * - profiles: a map where the key is a column
 * position (from profilesStartingPosition) and the
 * value is a sorted number array representing a
 * profile.
 *
 *
 * See the following example:    here profileStartingPosition
 *                               corresponds to [A,C,E,G,K]
 *    A B C D E F G H I J K      so with number [0,2,4,6,10]
 *  1    '   '   '       '
 *  2    '   '   '_______'       here profile correspond
 *  3    '___'   |_______|       for A to []
 *  4    |   |                   for C to [3, 5]
 *  5    |___|                   for E to []
 *  6                            for G to [2, 3]
 *  7                            for K to []
 *
 *
 * Now we can easily find which zones are overlapping
 * with a given zone. Suppose we want to add a new zone
 * D5:H6 to the ensemble:
 *
 *                              With a binary search of left and right
 *    A B C D E F G H I J K     on profilesStartingPosition, we can
 *  1    '   '   '       '      find the indexes of the profiles on which
 *  2    '   '   '_______'      to apply a modification.
 *  3    '___'   |_______|
 *  4    |  _|_______           Here we will:
 *  5    |_|_|       |          - add a new profile in D   --> become [3, 6]
 *  6      |_________|          - modify the profile in E  --> become [4, 6]
 *  7                           - modify the profile in G  --> become [2, 3, 4, 6]
 *                              - add a new profile in I   --> become [8, 10]
 *
 *  See below the result:
 *
 *                              Note the particularity of the profile
 *    A B C D E F G H I J K     for G: it will correspond to [2, 3, 4, 6]
 *  1    ' ' '   '   '   '
 *  2    ' ' '   '___'___'      To know how to modify the profile (add a
 *  3    '_'_'   |___|___|      zone or remove it) we do a binary
 *  4    | | |___ ___           search of the top and bottom value on the
 *  5    |_| |   |   |          profile array. Depending on the result index
 *  6      |_|___|___|          parity (odd or even), because zone boundaries
 *  7                           go by pairs, we know if we are in a zone or
 *                              not and how operate.
 */
/**
 * Recompute the zone without the cells in toRemoveZones and avoid overlapping.
 * This compute is particularly useful because after this function:
 * - you will find coordinate of a cell only once among all the zones
 * - the number of zones will be reduced to the minimum
 */
export declare function recomputeZones<T extends UnboundedZone | Zone>(zones: T[], zonesToRemove?: (UnboundedZone | Zone)[]): T[];
export declare function modifyProfiles<T extends Zone | UnboundedZone>(// export for testing only
profilesStartingPosition: number[], profiles: Map<number, number[]>, zones: T[], toRemove?: boolean): void;
export declare function profilesContainsZone(profilesStartingPosition: number[], profiles: Map<number, number[]>, zone: Zone | UnboundedZone): boolean;
export declare function findIndexAndCreateProfile(profilesStartingPosition: number[], profiles: Map<number, number[]>, value: number | undefined, searchLeft: boolean, startIndex: number): number;
export declare function constructZonesFromProfiles<T extends UnboundedZone | Zone>(profilesStartingPosition: number[], profiles: Map<number, number[]>): T[];