text: /*
  	MIT License http://www.opensource.org/licenses/mit-license.php
  	Author Tobias Koppers @sokra
  */
  "use strict";
  
  const SortableSet = require("./util/SortableSet");
  const compareLocations = require("./compareLocations");
  
  /** @typedef {import("./Chunk")} Chunk */
  /** @typedef {import("./Module")} Module */
  /** @typedef {import("./ModuleReason")} ModuleReason */
  
  /** @typedef {{module: Module, loc: TODO, request: string}} OriginRecord */
  /** @typedef {string|{name: string}} ChunkGroupOptions */
  
  let debugId = 5000;
  
  /**
   * @template T
   * @param {SortableSet<T>} set set to convert to array.
   * @returns {T[]} the array format of existing set
   */
  const getArray = set => Array.from(set);
  
  /**
   * A convenience method used to sort chunks based on their id's
   * @param {ChunkGroup} a first sorting comparator
   * @param {ChunkGroup} b second sorting comparator
   * @returns {1|0|-1} a sorting index to determine order
   */
  const sortById = (a, b) => {
  	if (a.id < b.id) return -1;
  	if (b.id < a.id) return 1;
  	return 0;
  };
  
  /**
   * @param {OriginRecord} a the first comparator in sort
   * @param {OriginRecord} b the second comparator in sort
   * @returns {1|-1|0} returns sorting order as index
   */
  const sortOrigin = (a, b) => {
  	const aIdent = a.module ? a.module.identifier() : "";
  	const bIdent = b.module ? b.module.identifier() : "";
  	if (aIdent < bIdent) return -1;
  	if (aIdent > bIdent) return 1;
  	return compareLocations(a.loc, b.loc);
  };
  
  class ChunkGroup {
  	/**
  	 * Creates an instance of ChunkGroup.
  	 * @param {ChunkGroupOptions=} options chunk group options passed to chunkGroup
  	 */
  	constructor(options) {
  		if (typeof options === "string") {
  			options = { name: options };
  		} else if (!options) {
  			options = { name: undefined };
  		}
  		/** @type {number} */
  		this.groupDebugId = debugId++;
  		this.options = options;
  		/** @type {SortableSet<ChunkGroup>} */
  		this._children = new SortableSet(undefined, sortById);
  		this._parents = new SortableSet(undefined, sortById);
  		this._blocks = new SortableSet();
  		/** @type {Chunk[]} */
  		this.chunks = [];
  		/** @type {OriginRecord[]} */
  		this.origins = [];
  		/** Indicies in top-down order */
  		/** @private @type {Map<Module, number>} */
  		this._moduleIndicies = new Map();
  		/** Indicies in bottom-up order */
  		/** @private @type {Map<Module, number>} */
  		this._moduleIndicies2 = new Map();
  	}
  
  	/**
  	 * when a new chunk is added to a chunkGroup, addingOptions will occur.
  	 * @param {ChunkGroupOptions} options the chunkGroup options passed to addOptions
  	 * @returns {void}
  	 */
  	addOptions(options) {
  		for (const key of Object.keys(options)) {
  			if (this.options[key] === undefined) {
  				this.options[key] = options[key];
  			} else if (this.options[key] !== options[key]) {
  				if (key.endsWith("Order")) {
  					this.options[key] = Math.max(this.options[key], options[key]);
  				} else {
  					throw new Error(
  						`ChunkGroup.addOptions: No option merge strategy for ${key}`
  					);
  				}
  			}
  		}
  	}
  
  	/**
  	 * returns the name of current ChunkGroup
  	 * @returns {string|undefined} returns the ChunkGroup name
  	 */
  	get name() {
  		return this.options.name;
  	}
  
  	/**
  	 * sets a new name for current ChunkGroup
  	 * @param {string} value the new name for ChunkGroup
  	 * @returns {void}
  	 */
  	set name(value) {
  		this.options.name = value;
  	}
  
  	/**
  	 * get a uniqueId for ChunkGroup, made up of its member Chunk debugId's
  	 * @returns {string} a unique concatenation of chunk debugId's
  	 */
  	get debugId() {
  		return Array.from(this.chunks, x => x.debugId).join("+");
  	}
  
  	/**
  	 * get a unique id for ChunkGroup, made up of its member Chunk id's
  	 * @returns {string} a unique concatenation of chunk ids
  	 */
  	get id() {
  		return Array.from(this.chunks, x => x.id).join("+");
  	}
  
  	/**
  	 * Performs an unshift of a specific chunk
  	 * @param {Chunk} chunk chunk being unshifted
  	 * @returns {boolean} returns true if attempted chunk shift is accepted
  	 */
  	unshiftChunk(chunk) {
  		const oldIdx = this.chunks.indexOf(chunk);
  		if (oldIdx > 0) {
  			this.chunks.splice(oldIdx, 1);
  			this.chunks.unshift(chunk);
  		} else if (oldIdx < 0) {
  			this.chunks.unshift(chunk);
  			return true;
  		}
  		return false;
  	}
  
  	/**
  	 * inserts a chunk before another existing chunk in group
  	 * @param {Chunk} chunk Chunk being inserted
  	 * @param {Chunk} before Placeholder/target chunk marking new chunk insertion point
  	 * @returns {boolean} return true if insertion was successful
  	 */
  	insertChunk(chunk, before) {
  		const oldIdx = this.chunks.indexOf(chunk);
  		const idx = this.chunks.indexOf(before);
  		if (idx < 0) {
  			throw new Error("before chunk not found");
  		}
  		if (oldIdx >= 0 && oldIdx > idx) {
  			this.chunks.splice(oldIdx, 1);
  			this.chunks.splice(idx, 0, chunk);
  		} else if (oldIdx < 0) {
  			this.chunks.splice(idx, 0, chunk);
  			return true;
  		}
  		return false;
  	}
  
  	/**
  	 * add a chunk into ChunkGroup. Is pushed on or prepended
  	 * @param {Chunk} chunk chunk being pushed into ChunkGroupS
  	 * @returns {boolean} returns true if chunk addition was ssuccesful.
  	 */
  	pushChunk(chunk) {
  		const oldIdx = this.chunks.indexOf(chunk);
  		if (oldIdx >= 0) {
  			return false;
  		}
  		this.chunks.push(chunk);
  		return true;
  	}
  
  	/**
  	 * @param {Chunk} oldChunk chunk to be replaced
  	 * @param {Chunk} newChunk New chunkt that will be replaced
  	 * @returns {boolean} rerturns true for
  	 */
  	replaceChunk(oldChunk, newChunk) {
  		const oldIdx = this.chunks.indexOf(oldChunk);
  		if (oldIdx < 0) return false;
  		const newIdx = this.chunks.indexOf(newChunk);
  		if (newIdx < 0) {
  			this.chunks[oldIdx] = newChunk;
  			return true;
  		}
  		if (newIdx < oldIdx) {
  			this.chunks.splice(oldIdx, 1);
  			return true;
  		} else if (newIdx !== oldIdx) {
  			this.chunks[oldIdx] = newChunk;
  			this.chunks.splice(newIdx, 1);
  			return true;
  		}
  	}
  
  	removeChunk(chunk) {
  		const idx = this.chunks.indexOf(chunk);
  		if (idx >= 0) {
  			this.chunks.splice(idx, 1);
  			return true;
  		}
  		return false;
  	}
  
  	isInitial() {
  		return false;
  	}
  
  	addChild(chunk) {
  		if (this._children.has(chunk)) {
  			return false;
  		}
  		this._children.add(chunk);
  		return true;
  	}
  
  	getChildren() {
  		return this._children.getFromCache(getArray);
  	}
  
  	getNumberOfChildren() {
  		return this._children.size;
  	}
  
  	get childrenIterable() {
  		return this._children;
  	}
  
  	removeChild(chunk) {
  		if (!this._children.has(chunk)) {
  			return false;
  		}
  
  		this._children.delete(chunk);
  		chunk.removeParent(this);
  		return true;
  	}
  
  	addParent(parentChunk) {
  		if (!this._parents.has(parentChunk)) {
  			this._parents.add(parentChunk);
  			return true;
  		}
  		return false;
  	}
  
  	getParents() {
  		return this._parents.getFromCache(getArray);
  	}
  
  	setParents(newParents) {
  		this._parents.clear();
  		for (const p of newParents) {
  			this._parents.add(p);
  		}
  	}
  
  	getNumberOfParents() {
  		return this._parents.size;
  	}
  
  	hasParent(parent) {
  		return this._parents.has(parent);
  	}
  
  	get parentsIterable() {
  		return this._parents;
  	}
  
  	removeParent(chunk) {
  		if (this._parents.delete(chunk)) {
  			chunk.removeChunk(this);
  			return true;
  		}
  		return false;
  	}
  
  	/**
  	 * @returns {Array} - an array containing the blocks
  	 */
  	getBlocks() {
  		return this._blocks.getFromCache(getArray);
  	}
  
  	getNumberOfBlocks() {
  		return this._blocks.size;
  	}
  
  	hasBlock(block) {
  		return this._blocks.has(block);
  	}
  
  	get blocksIterable() {
  		return this._blocks;
  	}
  
  	addBlock(block) {
  		if (!this._blocks.has(block)) {
  			this._blocks.add(block);
  			return true;
  		}
  		return false;
  	}
  
  	addOrigin(module, loc, request) {
  		this.origins.push({
  			module,
  			loc,
  			request
  		});
  	}
  
  	containsModule(module) {
  		for (const chunk of this.chunks) {
  			if (chunk.containsModule(module)) return true;
  		}
  		return false;
  	}
  
  	getFiles() {
  		const files = new Set();
  
  		for (const chunk of this.chunks) {
  			for (const file of chunk.files) {
  				files.add(file);
  			}
  		}
  
  		return Array.from(files);
  	}
  
  	/**
  	 * @param {ModuleReason} reason reason for removing ChunkGroup
  	 * @returns {void}
  	 */
  	remove(reason) {
  		// cleanup parents
  		for (const parentChunkGroup of this._parents) {
  			// remove this chunk from its parents
  			parentChunkGroup._children.delete(this);
  
  			// cleanup "sub chunks"
  			for (const chunkGroup of this._children) {
  				/**
  				 * remove this chunk as "intermediary" and connect
  				 * it "sub chunks" and parents directly
  				 */
  				// add parent to each "sub chunk"
  				chunkGroup.addParent(parentChunkGroup);
  				// add "sub chunk" to parent
  				parentChunkGroup.addChild(chunkGroup);
  			}
  		}
  
  		/**
  		 * we need to iterate again over the children
  		 * to remove this from the childs parents.
  		 * This can not be done in the above loop
  		 * as it is not guaranteed that `this._parents` contains anything.
  		 */
  		for (const chunkGroup of this._children) {
  			// remove this as parent of every "sub chunk"
  			chunkGroup._parents.delete(this);
  		}
  
  		// cleanup blocks
  		for (const block of this._blocks) {
  			block.chunkGroup = null;
  		}
  
  		// remove chunks
  		for (const chunk of this.chunks) {
  			chunk.removeGroup(this);
  		}
  	}
  
  	sortItems() {
  		this.origins.sort(sortOrigin);
  		this._parents.sort();
  		this._children.sort();
  	}
  
  	/**
  	 * Sorting predicate which allows current ChunkGroup to be compared against another.
  	 * Sorting values are based off of number of chunks in ChunkGroup.
  	 *
  	 * @param {ChunkGroup} otherGroup the chunkGroup to compare this against
  	 * @returns {-1|0|1} sort position for comparison
  	 */
  	compareTo(otherGroup) {
  		if (this.chunks.length > otherGroup.chunks.length) return -1;
  		if (this.chunks.length < otherGroup.chunks.length) return 1;
  		const a = this.chunks[Symbol.iterator]();
  		const b = otherGroup.chunks[Symbol.iterator]();
  		// eslint-disable-next-line no-constant-condition
  		while (true) {
  			const aItem = a.next();
  			const bItem = b.next();
  			if (aItem.done) return 0;
  			const cmp = aItem.value.compareTo(bItem.value);
  			if (cmp !== 0) return cmp;
  		}
  	}
  
  	getChildrenByOrders() {
  		const lists = new Map();
  		for (const childGroup of this._children) {
  			// TODO webpack 5 remove this check for options
  			if (typeof childGroup.options === "object") {
  				for (const key of Object.keys(childGroup.options)) {
  					if (key.endsWith("Order")) {
  						const name = key.substr(0, key.length - "Order".length);
  						let list = lists.get(name);
  						if (list === undefined) {
  							lists.set(name, (list = []));
  						}
  						list.push({
  							order: childGroup.options[key],
  							group: childGroup
  						});
  					}
  				}
  			}
  		}
  		const result = Object.create(null);
  		for (const [name, list] of lists) {
  			list.sort((a, b) => {
  				const cmp = b.order - a.order;
  				if (cmp !== 0) return cmp;
  				// TODO webpack 5 remove this check of compareTo
  				if (a.group.compareTo) {
  					return a.group.compareTo(b.group);
  				}
  				return 0;
  			});
  			result[name] = list.map(i => i.group);
  		}
  		return result;
  	}
  
  	/**
  	 * Sets the top-down index of a module in this ChunkGroup
  	 * @param {Module} module module for which the index should be set
  	 * @param {number} index the index of the module
  	 * @returns {void}
  	 */
  	setModuleIndex(module, index) {
  		this._moduleIndicies.set(module, index);
  	}
  
  	/**
  	 * Gets the top-down index of a module in this ChunkGroup
  	 * @param {Module} module the module
  	 * @returns {number} index
  	 */
  	getModuleIndex(module) {
  		return this._moduleIndicies.get(module);
  	}
  
  	/**
  	 * Sets the bottom-up index of a module in this ChunkGroup
  	 * @param {Module} module module for which the index should be set
  	 * @param {number} index the index of the module
  	 * @returns {void}
  	 */
  	setModuleIndex2(module, index) {
  		this._moduleIndicies2.set(module, index);
  	}
  
  	/**
  	 * Gets the bottom-up index of a module in this ChunkGroup
  	 * @param {Module} module the module
  	 * @returns {number} index
  	 */
  	getModuleIndex2(module) {
  		return this._moduleIndicies2.get(module);
  	}
  
  	checkConstraints() {
  		const chunk = this;
  		for (const child of chunk._children) {
  			if (!child._parents.has(chunk)) {
  				throw new Error(
  					`checkConstraints: child missing parent ${chunk.debugId} -> ${
  						child.debugId
  					}`
  				);
  			}
  		}
  		for (const parentChunk of chunk._parents) {
  			if (!parentChunk._children.has(chunk)) {
  				throw new Error(
  					`checkConstraints: parent missing child ${parentChunk.debugId} <- ${
  						chunk.debugId
  					}`
  				);
  			}
  		}
  	}
  }
  
  module.exports = ChunkGroup;
  