{"version":3,"file":"Sort.js","sourceRoot":"","sources":["../src/Sort.ts"],"names":[],"mappings":";AAAA,4FAA4F;AAC5F,2DAA2D;;;AAE3D;;;;GAIG;AACH,MAAa,IAAI;IACf;;;;;;;;;;;;;;;;OAgBG;IACH,8DAA8D;IACvD,MAAM,CAAC,cAAc,CAAC,CAAM,EAAE,CAAM;QACzC,IAAI,CAAC,KAAK,CAAC,EAAE,CAAC;YACZ,OAAO,CAAC,CAAC;QACX,CAAC;QAED,0CAA0C;QAC1C,IAAI,CAAC,KAAK,SAAS,EAAE,CAAC;YACpB,OAAO,CAAC,CAAC,CAAC;QACZ,CAAC;QACD,IAAI,CAAC,KAAK,SAAS,EAAE,CAAC;YACpB,OAAO,CAAC,CAAC;QACX,CAAC;QAED,iDAAiD;QACjD,IAAI,CAAC,KAAK,IAAI,EAAE,CAAC;YACf,OAAO,CAAC,CAAC,CAAC;QACZ,CAAC;QACD,IAAI,CAAC,KAAK,IAAI,EAAE,CAAC;YACf,OAAO,CAAC,CAAC;QACX,CAAC;QAED,mFAAmF;QACnF,+GAA+G;QAC/G,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC;YACV,OAAO,CAAC,CAAC,CAAC;QACZ,CAAC;QACD,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC;YACV,OAAO,CAAC,CAAC;QACX,CAAC;QAED,OAAO,CAAC,CAAC;IACX,CAAC;IAED;;;;;;;;;;OAUG;IACI,MAAM,CAAC,MAAM,CAClB,KAAU;IACV,8DAA8D;IAC9D,WAAgC;IAChC,8DAA8D;IAC9D,WAAuC,IAAI,CAAC,cAAc;QAE1D,KAAK,CAAC,IAAI,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,EAAE,CAAC,QAAQ,CAAC,WAAW,CAAC,CAAC,CAAC,EAAE,WAAW,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;IACjE,CAAC;IAED;;OAEG;IACI,MAAM,CAAC,QAAQ,CACpB,UAAuB;IACvB,8DAA8D;IAC9D,WAAuC,IAAI,CAAC,cAAc;QAE1D,IAAI,OAAO,GAAY,IAAI,CAAC;QAC5B,IAAI,QAAQ,GAAkB,SAAS,CAAC;QACxC,KAAK,MAAM,OAAO,IAAI,UAAU,EAAE,CAAC;YACjC,IAAI,OAAO,EAAE,CAAC;gBACZ,8CAA8C;gBAC9C,OAAO,GAAG,KAAK,CAAC;YAClB,CAAC;iBAAM,IAAI,QAAQ,CAAC,QAAQ,EAAE,OAAO,CAAC,GAAG,CAAC,EAAE,CAAC;gBAC3C,OAAO,KAAK,CAAC;YACf,CAAC;YACD,QAAQ,GAAG,OAAO,CAAC;QACrB,CAAC;QACD,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;;;;;OASG;IACI,MAAM,CAAC,UAAU,CACtB,UAAuB;IACvB,8DAA8D;IAC9D,WAAgC;IAChC,8DAA8D;IAC9D,WAAuC,IAAI,CAAC,cAAc;QAE1D,IAAI,OAAO,GAAY,IAAI,CAAC;QAC5B,IAAI,WAAW,GAAkB,SAAS,CAAC;QAC3C,KAAK,MAAM,OAAO,IAAI,UAAU,EAAE,CAAC;YACjC,MAAM,GAAG,GAAM,WAAW,CAAC,OAAO,CAAC,CAAC;YACpC,IAAI,OAAO,EAAE,CAAC;gBACZ,8CAA8C;gBAC9C,OAAO,GAAG,KAAK,CAAC;YAClB,CAAC;iBAAM,IAAI,QAAQ,CAAC,WAAW,EAAE,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC;gBAC1C,OAAO,KAAK,CAAC;YACf,CAAC;YACD,WAAW,GAAG,GAAG,CAAC;QACpB,CAAC;QACD,OAAO,IAAI,CAAC;IACd,CAAC;IAED;;;;;;;;;;;;;;OAcG;IACH,8DAA8D;IACvD,MAAM,CAAC,WAAW,CACvB,GAAc,EACd,cAAsC,IAAI,CAAC,cAAc;QAEzD,0EAA0E;QAC1E,IAAI,IAAI,CAAC,QAAQ,CAAC,GAAG,CAAC,IAAI,EAAE,EAAE,WAAW,CAAC,EAAE,CAAC;YAC3C,OAAO;QACT,CAAC;QAED,MAAM,KAAK,GAAa,KAAK,CAAC,IAAI,CAAC,GAAG,CAAC,OAAO,EAAE,CAAC,CAAC;QAElD,IAAI,CAAC,MAAM,CAAC,KAAK,EAAE,CAAC,CAAC,EAAE,EAAE,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE,WAAW,CAAC,CAAC;QAC7C,GAAG,CAAC,KAAK,EAAE,CAAC;QACZ,KAAK,MAAM,IAAI,IAAI,KAAK,EAAE,CAAC;YACzB,GAAG,CAAC,GAAG,CAAC,IAAI,CAAC,CAAC,CAAC,EAAE,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC;QAC5B,CAAC;IACH,CAAC;IAED;;;;;;;;;;;;;;OAcG;IACI,MAAM,CAAC,SAAS,CACrB,GAAW;IACX,8DAA8D;IAC9D,WAAgC,EAChC,cAAsC,IAAI,CAAC,cAAc;QAEzD,0EAA0E;QAC1E,IAAI,IAAI,CAAC,UAAU,CAAC,GAAG,EAAE,WAAW,EAAE,WAAW,CAAC,EAAE,CAAC;YACnD,OAAO;QACT,CAAC;QAED,MAAM,KAAK,GAAQ,KAAK,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC;QACnC,KAAK,CAAC,IAAI,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,EAAE,CAAC,WAAW,CAAC,WAAW,CAAC,CAAC,CAAC,EAAE,WAAW,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;QAElE,GAAG,CAAC,KAAK,EAAE,CAAC;QACZ,KAAK,MAAM,IAAI,IAAI,KAAK,EAAE,CAAC;YACzB,GAAG,CAAC,GAAG,CAAC,IAAI,CAAC,CAAC;QAChB,CAAC;IACH,CAAC;IAED;;;;;;;;;;;;;OAaG;IACH,8DAA8D;IACvD,MAAM,CAAC,OAAO,CAAI,GAAW,EAAE,WAAmC,IAAI,CAAC,cAAc;QAC1F,0EAA0E;QAC1E,IAAI,IAAI,CAAC,QAAQ,CAAC,GAAG,EAAE,QAAQ,CAAC,EAAE,CAAC;YACjC,OAAO;QACT,CAAC;QAED,MAAM,KAAK,GAAQ,KAAK,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC;QACnC,KAAK,CAAC,IAAI,CAAC,CAAC,CAAC,EAAE,CAAC,EAAE,EAAE,CAAC,QAAQ,CAAC,CAAC,EAAE,CAAC,CAAC,CAAC,CAAC;QAErC,GAAG,CAAC,KAAK,EAAE,CAAC;QACZ,KAAK,MAAM,IAAI,IAAI,KAAK,EAAE,CAAC;YACzB,GAAG,CAAC,GAAG,CAAC,IAAI,CAAC,CAAC;QAChB,CAAC;IACH,CAAC;IAED;;;;;;;;;;;;OAYG;IACI,MAAM,CAAC,QAAQ,CAAyD,MAAS;QACtF,IAAI,CAAC,aAAa,CAAC,MAAM,CAAC,IAAI,CAAC,KAAK,CAAC,OAAO,CAAC,MAAM,CAAC,EAAE,CAAC;YACrD,MAAM,IAAI,SAAS,CAAC,0BAA0B,CAAC,CAAC;QAClD,CAAC;QAED,OAAO,KAAK,CAAC,OAAO,CAAC,MAAM,CAAC,CAAC,CAAC,CAAE,cAAc,CAAC,MAAM,CAAO,CAAC,CAAC,CAAE,aAAa,CAAC,MAAM,CAAO,CAAC;IAC9F,CAAC;CACF;AAtPD,oBAsPC;AAED,SAAS,aAAa,CAAC,GAAY;IACjC,OAAO,GAAG,KAAK,IAAI,IAAI,OAAO,GAAG,KAAK,QAAQ,CAAC;AACjD,CAAC;AAED,SAAS,cAAc,CAAC,GAAc;IACpC,MAAM,MAAM,GAAc,EAAE,CAAC;IAC7B,KAAK,MAAM,KAAK,IAAI,GAAG,EAAE,CAAC;QACxB,IAAI,KAAK,CAAC,OAAO,CAAC,KAAK,CAAC,EAAE,CAAC;YACzB,MAAM,CAAC,IAAI,CAAC,cAAc,CAAC,KAAK,CAAC,CAAC,CAAC;QACrC,CAAC;aAAM,IAAI,aAAa,CAAC,KAAK,CAAC,EAAE,CAAC;YAChC,MAAM,CAAC,IAAI,CAAC,aAAa,CAAC,KAAK,CAAC,CAAC,CAAC;QACpC,CAAC;aAAM,CAAC;YACN,MAAM,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;QACrB,CAAC;IACH,CAAC;IACD,OAAO,MAAM,CAAC;AAChB,CAAC;AAED,SAAS,aAAa,CAAC,GAAqC;IAC1D,MAAM,MAAM,GAAqC,EAAE,CAAC;IACpD,MAAM,IAAI,GAAa,MAAM,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC,IAAI,EAAE,CAAC;IAC/C,KAAK,MAAM,GAAG,IAAI,IAAI,EAAE,CAAC;QACvB,MAAM,KAAK,GAAY,GAAG,CAAC,GAAG,CAAC,CAAC;QAChC,IAAI,KAAK,CAAC,OAAO,CAAC,KAAK,CAAC,EAAE,CAAC;YACzB,MAAM,CAAC,GAAG,CAAC,GAAG,cAAc,CAAC,KAAK,CAAC,CAAC;QACtC,CAAC;aAAM,IAAI,aAAa,CAAC,KAAK,CAAC,EAAE,CAAC;YAChC,MAAM,CAAC,GAAG,CAAC,GAAG,aAAa,CAAC,KAAK,CAAC,CAAC;QACrC,CAAC;aAAM,CAAC;YACN,MAAM,CAAC,GAAG,CAAC,GAAG,KAAK,CAAC;QACtB,CAAC;IACH,CAAC;IAED,OAAO,MAAM,CAAC;AAChB,CAAC","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * Operations for sorting collections.\n *\n * @public\n */\nexport class Sort {\n  /**\n   * Compares `x` and `y` using the JavaScript `>` and `<` operators.  This function is suitable for usage as\n   * the callback for `array.sort()`.\n   *\n   * @remarks\n   *\n   * The JavaScript ordering is generalized so that `undefined` \\< `null` \\< all other values.\n   *\n   * @returns -1 if `x` is smaller than `y`, 1 if `x` is greater than `y`, or 0 if the values are equal.\n   *\n   * @example\n   *\n   * ```ts\n   * let array: number[] = [3, 6, 2];\n   * array.sort(Sort.compareByValue);  // [2, 3, 6]\n   * ```\n   */\n  // eslint-disable-next-line @typescript-eslint/no-explicit-any\n  public static compareByValue(x: any, y: any): number {\n    if (x === y) {\n      return 0;\n    }\n\n    // Undefined is smaller than anything else\n    if (x === undefined) {\n      return -1;\n    }\n    if (y === undefined) {\n      return 1;\n    }\n\n    // Null is smaller than anything except undefined\n    if (x === null) {\n      return -1;\n    }\n    if (y === null) {\n      return 1;\n    }\n\n    // These comparisons always return false if either of the arguments is \"undefined\".\n    // These comparisons return nonsense for \"null\" (true for \"null > -1\", but false for \"null < 0\" and \"null > 0\")\n    if (x < y) {\n      return -1;\n    }\n    if (x > y) {\n      return 1;\n    }\n\n    return 0;\n  }\n\n  /**\n   * Sorts the array according to a key which is obtained from the array elements.\n   * The result is guaranteed to be a stable sort.\n   *\n   * @example\n   *\n   * ```ts\n   * let array: string[] = [ 'aaa', 'bb', 'c' ];\n   * Sort.sortBy(array, x => x.length);  // [ 'c', 'bb', 'aaa' ]\n   * ```\n   */\n  public static sortBy<T>(\n    array: T[],\n    // eslint-disable-next-line @typescript-eslint/no-explicit-any\n    keySelector: (element: T) => any,\n    // eslint-disable-next-line @typescript-eslint/no-explicit-any\n    comparer: (x: any, y: any) => number = Sort.compareByValue\n  ): void {\n    array.sort((x, y) => comparer(keySelector(x), keySelector(y)));\n  }\n\n  /**\n   * Returns true if the collection is already sorted.\n   */\n  public static isSorted<T>(\n    collection: Iterable<T>,\n    // eslint-disable-next-line @typescript-eslint/no-explicit-any\n    comparer: (x: any, y: any) => number = Sort.compareByValue\n  ): boolean {\n    let isFirst: boolean = true;\n    let previous: T | undefined = undefined;\n    for (const element of collection) {\n      if (isFirst) {\n        // Don't start by comparing against undefined.\n        isFirst = false;\n      } else if (comparer(previous, element) > 0) {\n        return false;\n      }\n      previous = element;\n    }\n    return true;\n  }\n\n  /**\n   * Returns true if the collection is already sorted by the specified key.\n   *\n   * @example\n   *\n   * ```ts\n   * let array: string[] = [ 'a', 'bb', 'ccc' ];\n   * Sort.isSortedBy(array, x => x.length); // true\n   * ```\n   */\n  public static isSortedBy<T>(\n    collection: Iterable<T>,\n    // eslint-disable-next-line @typescript-eslint/no-explicit-any\n    keySelector: (element: T) => any,\n    // eslint-disable-next-line @typescript-eslint/no-explicit-any\n    comparer: (x: any, y: any) => number = Sort.compareByValue\n  ): boolean {\n    let isFirst: boolean = true;\n    let previousKey: T | undefined = undefined;\n    for (const element of collection) {\n      const key: T = keySelector(element);\n      if (isFirst) {\n        // Don't start by comparing against undefined.\n        isFirst = false;\n      } else if (comparer(previousKey, key) > 0) {\n        return false;\n      }\n      previousKey = key;\n    }\n    return true;\n  }\n\n  /**\n   * Sorts the entries in a Map object according to the map keys.\n   * The result is guaranteed to be a stable sort.\n   *\n   * @example\n   *\n   * ```ts\n   * let map: Map<string, number> = new Map<string, number>();\n   * map.set('zebra', 1);\n   * map.set('goose', 2);\n   * map.set('aardvark', 3);\n   * Sort.sortMapKeys(map);\n   * console.log(JSON.stringify(Array.from(map.keys()))); // [\"aardvark\",\"goose\",\"zebra\"]\n   * ```\n   */\n  // eslint-disable-next-line @typescript-eslint/no-explicit-any\n  public static sortMapKeys<K, V>(\n    map: Map<K, V>,\n    keyComparer: (x: K, y: K) => number = Sort.compareByValue\n  ): void {\n    // Sorting a map is expensive, so first check whether it's already sorted.\n    if (Sort.isSorted(map.keys(), keyComparer)) {\n      return;\n    }\n\n    const pairs: [K, V][] = Array.from(map.entries());\n\n    Sort.sortBy(pairs, (x) => x[0], keyComparer);\n    map.clear();\n    for (const pair of pairs) {\n      map.set(pair[0], pair[1]);\n    }\n  }\n\n  /**\n   * Sorts the entries in a Set object according to the specified keys.\n   * The result is guaranteed to be a stable sort.\n   *\n   * @example\n   *\n   * ```ts\n   * let set: Set<string> = new Set<string>();\n   * set.add('aaa');\n   * set.add('bb');\n   * set.add('c');\n   * Sort.sortSetBy(set, x => x.length);\n   * console.log(Array.from(set)); // ['c', 'bb', 'aaa']\n   * ```\n   */\n  public static sortSetBy<T>(\n    set: Set<T>,\n    // eslint-disable-next-line @typescript-eslint/no-explicit-any\n    keySelector: (element: T) => any,\n    keyComparer: (x: T, y: T) => number = Sort.compareByValue\n  ): void {\n    // Sorting a set is expensive, so first check whether it's already sorted.\n    if (Sort.isSortedBy(set, keySelector, keyComparer)) {\n      return;\n    }\n\n    const array: T[] = Array.from(set);\n    array.sort((x, y) => keyComparer(keySelector(x), keySelector(y)));\n\n    set.clear();\n    for (const item of array) {\n      set.add(item);\n    }\n  }\n\n  /**\n   * Sorts the entries in a Set object.  The result is guaranteed to be a stable sort.\n   *\n   * @example\n   *\n   * ```ts\n   * let set: Set<string> = new Set<string>();\n   * set.add('zebra');\n   * set.add('goose');\n   * set.add('aardvark');\n   * Sort.sortSet(set);\n   * console.log(Array.from(set)); // ['aardvark', 'goose', 'zebra']\n   * ```\n   */\n  // eslint-disable-next-line @typescript-eslint/no-explicit-any\n  public static sortSet<T>(set: Set<T>, comparer: (x: T, y: T) => number = Sort.compareByValue): void {\n    // Sorting a set is expensive, so first check whether it's already sorted.\n    if (Sort.isSorted(set, comparer)) {\n      return;\n    }\n\n    const array: T[] = Array.from(set);\n    array.sort((x, y) => comparer(x, y));\n\n    set.clear();\n    for (const item of array) {\n      set.add(item);\n    }\n  }\n\n  /**\n   * Sort the keys deeply given an object or an array.\n   *\n   * Doesn't handle cyclic reference.\n   *\n   * @param object - The object to be sorted\n   *\n   * @example\n   *\n   * ```ts\n   * console.log(Sort.sortKeys({ c: 3, b: 2, a: 1 })); // { a: 1, b: 2, c: 3}\n   * ```\n   */\n  public static sortKeys<T extends Partial<Record<string, unknown>> | unknown[]>(object: T): T {\n    if (!isPlainObject(object) && !Array.isArray(object)) {\n      throw new TypeError(`Expected object or array`);\n    }\n\n    return Array.isArray(object) ? (innerSortArray(object) as T) : (innerSortKeys(object) as T);\n  }\n}\n\nfunction isPlainObject(obj: unknown): obj is object {\n  return obj !== null && typeof obj === 'object';\n}\n\nfunction innerSortArray(arr: unknown[]): unknown[] {\n  const result: unknown[] = [];\n  for (const entry of arr) {\n    if (Array.isArray(entry)) {\n      result.push(innerSortArray(entry));\n    } else if (isPlainObject(entry)) {\n      result.push(innerSortKeys(entry));\n    } else {\n      result.push(entry);\n    }\n  }\n  return result;\n}\n\nfunction innerSortKeys(obj: Partial<Record<string, unknown>>): Partial<Record<string, unknown>> {\n  const result: Partial<Record<string, unknown>> = {};\n  const keys: string[] = Object.keys(obj).sort();\n  for (const key of keys) {\n    const value: unknown = obj[key];\n    if (Array.isArray(value)) {\n      result[key] = innerSortArray(value);\n    } else if (isPlainObject(value)) {\n      result[key] = innerSortKeys(value);\n    } else {\n      result[key] = value;\n    }\n  }\n\n  return result;\n}\n"]}