Whether an iterator is equal with the iterator.
\r\n *\r\n *Compare two iterators and returns whether they are equal or not.
\r\n *\r\n *Note
\r\n *Iterator's equal_to() only compare souce container and index number.
\r\n *\r\n *Although elements in a pair, key and value are equal_to, if the source map or\r\n * index number is different, then the {@link equal_to equal_to()} will return false. If you want to\r\n * compare the elements of a pair, compare them directly by yourself.
\r\n *\r\n * @param obj An iterator to compare\r\n * @return Indicates whether equal or not.\r\n */\r\n Iterator.prototype.equal_to = function (obj) {\r\n return this.source_ == obj.source_;\r\n };\r\n Object.defineProperty(Iterator.prototype, \"value\", {\r\n /**\r\n *Get value of the iterator is pointing.
\r\n *\r\n * @return A value of the iterator.\r\n */\r\n get: function () {\r\n throw new std.LogicError(\"Have to be overriden.\");\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n return Iterator;\r\n }());\r\n base.Iterator = Iterator;\r\n })(base = std.base || (std.base = {}));\r\n})(std || (std = {}));\r\n///Vector, the dynamic array.
\r\n *\r\n *{@link Vector}s are sequence containers representing arrays that can change in size.
\r\n *\r\n *Just like arrays, {@link Vector}s use contiguous storage locations for their elements, which means that\r\n * their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently\r\n * as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled\r\n * automatically by the
\r\n *\r\n *Internally, {@link Vector}s use a dynamically allocated array to store their elements. This array may need\r\n * to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new\r\n * array and moving all elements to it. This is a relatively expensive task in terms of processing time, and\r\n * thus, {@link Vector}s do not reallocate each time an element is added to the
\r\n *\r\n *Instead, {@link Vector} containers may allocate some extra storage to accommodate for possible growth, and\r\n * thus the container may have an actual {@link capacity} greater than the storage strictly needed to contain its\r\n * elements (i.e., its {@link size}). Libraries can implement different strategies for growth to balance between\r\n * memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing\r\n * intervals of {@link size} so that the insertion of individual elements at the end of the {@link Vector} can be\r\n * provided with amortized constant time complexity (see {@link push_back push_back()}).
\r\n *\r\n *Therefore, compared to arrays, {@link Vector}s consume more memory in exchange for the ability to manage\r\n * storage and grow dynamically in an efficient way.
\r\n *\r\n *Compared to the other dynamic sequence containers ({@link Deque}s, {@link List}s), {@link Vector Vectors}\r\n * are very efficient accessing its elements (just like arrays) and relatively efficient adding or removing\r\n * elements from its end. For operations that involve inserting or removing elements at positions other than the\r\n * end, they perform worse than the others, and have less consistent iterators and references than {@link List}s.\r\n *
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Sequence \r\n *\t
- \r\n *\t\tElements in sequence containers are ordered in a strict linear sequence. Individual elements are\r\n *\t\taccessed by their position in this sequence.\r\n *\t \r\n *\r\n *\t
- Dynamic array \r\n *\t
- \r\n *\t\tAllows direct access to any element in the sequence, even through pointer arithmetics, and provides\r\n *\t\trelatively fast addition/removal of elements at the end of the sequence.\r\n *\t \r\n *
- \r\n *
- Reference: http://www.cplusplus.com/reference/vector/vector/\r\n *
An iterator of Vector.
\r\n *\r\n * @paramConstruct from the source {@link Vector container}.
\r\n *\r\n *Note
\r\n *Do not create the iterator directly, by yourself.
\r\n *Use {@link Vector.begin begin()}, {@link Vector.end end()} in {@link Vector container} instead.
\r\n *\r\n * @param source The source {@link Vector container} to reference.\r\n * @param index Sequence number of the element in the source {@link Vector}.\r\n */\r\n function VectorIterator(source, index) {\r\n _super.call(this, source);\r\n this.index_ = index;\r\n }\r\n Object.defineProperty(VectorIterator.prototype, \"vector\", {\r\n /* ---------------------------------------------------------\r\n ACCESSORS\r\n --------------------------------------------------------- */\r\n /**\r\n * @hidden\r\n */\r\n get: function () {\r\n return this.source_;\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n Object.defineProperty(VectorIterator.prototype, \"value\", {\r\n /**\r\n * @inheritdoc\r\n */\r\n get: function () {\r\n return this.vector.at(this.index_);\r\n },\r\n /**\r\n * Set value.\r\n */\r\n set: function (val) {\r\n this.vector.set(this.index_, val);\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n /**\r\n *Whether an iterator is equal with the iterator.
\r\n *\r\n *Compare two iterators and returns whether they are equal or not.
\r\n *\r\n *Note
\r\n *Iterator's equal_to() only compare souce container and index number.
\r\n *\r\n *Although elements in a pair, key and value are equal_to, if the source map or\r\n * index number is different, then the {@link equal_to equal_to()} will return false. If you want to\r\n * compare the elements of a pair, compare them directly by yourself.
\r\n *\r\n * @param obj An iterator to compare\r\n * @return Indicates whether equal or not.\r\n */\r\n VectorIterator.prototype.equal_to = function (obj) {\r\n return _super.prototype.equal_to.call(this, obj) && this.index_ == obj.index_;\r\n };\r\n Object.defineProperty(VectorIterator.prototype, \"index\", {\r\n get: function () {\r\n return this.index_;\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n /* ---------------------------------------------------------\r\n MOVERS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n VectorIterator.prototype.prev = function () {\r\n if (this.index_ == -1)\r\n return new VectorIterator(this.vector, this.vector.size() - 1);\r\n else if (this.index_ - 1 < 0)\r\n return this.vector.end();\r\n else\r\n return new VectorIterator(this.vector, this.index_ - 1);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n VectorIterator.prototype.next = function () {\r\n if (this.index_ >= this.source_.size() - 1)\r\n return this.vector.end();\r\n else\r\n return new VectorIterator(this.vector, this.index_ + 1);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n VectorIterator.prototype.advance = function (n) {\r\n var newIndex = this.index_ + n;\r\n if (newIndex < 0 || newIndex >= this.vector.size())\r\n return this.vector.end();\r\n else\r\n return new VectorIterator(this.vector, newIndex);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n VectorIterator.prototype.swap = function (obj) {\r\n _a = [obj.value, this.value], this.value = _a[0], obj.value = _a[1];\r\n var _a;\r\n };\r\n return VectorIterator;\r\n }(std.base.Iterator));\r\n std.VectorIterator = VectorIterator;\r\n /**\r\n *A reverse-iterator of Vector.
\r\n *\r\n * @paramAn abstract
\r\n *\r\n *Container properties
\r\n *- \r\n * \t
- Sequence \r\n * \t
- Elements in sequence containers are ordered in a strict linear sequence. Individual elements are\r\n *\t\t accessed by their position in this sequence. \r\n *\r\n * \t
- Doubly-linked list \r\n *\t
- Each element keeps information on how to locate the next and the previous elements, allowing\r\n *\t\t constant time insert and erase operations before or after a specific element (even of entire ranges),\r\n *\t\t but no direct random access. \r\n *
Double ended queue.
\r\n *\r\n *{@link Deque} (usually pronounced like \"deck\") is an irregular acronym of\r\n * double-ended queue. Double-ended queues are sequence containers with dynamic\r\n * sizes that can be expanded or contracted on both ends (either its front or its back).
\r\n *\r\n *Specific libraries may implement deques in different ways, generally as some form of dynamic\r\n * array. But in any case, they allow for the individual elements to be accessed directly through\r\n * random access iterators, with storage handled automatically by expanding and contracting the\r\n * container as needed.
\r\n *\r\n *Therefore, they provide a functionality similar to vectors, but with efficient insertion and\r\n * deletion of elements also at the beginning of the sequence, and not only at its end. But, unlike\r\n * {@link Vector}s, {@link Deque}s are not guaranteed to store all its elements in contiguous storage\r\n * locations: accessing elements in a deque by offsetting a pointer to another element causes\r\n * undefined behavior.
\r\n *\r\n *Both {@link Vector}s and {@link Deque}s provide a very similar interface and can be used for\r\n * similar purposes, but internally both work in quite different ways: While {@link Vector}s use a\r\n * single array that needs to be occasionally reallocated for growth, the elements of a {@link Deque}\r\n * can be scattered in different chunks of storage, with the container keeping the necessary information\r\n * internally to provide direct access to any of its elements in constant time and with a uniform\r\n * sequential interface (through iterators). Therefore, {@link Deque}s are a little more complex\r\n * internally than {@link Vector}s, but this allows them to grow more efficiently under certain\r\n * circumstances, especially with very long sequences, where reallocations become more expensive.
\r\n *\r\n *For operations that involve frequent insertion or removals of elements at positions other than\r\n * the beginning or the end, {@link Deque}s perform worse and have less consistent iterators and\r\n * references than {@link List}s.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Sequence \r\n *\t
- Elements in sequence containers are ordered in a strict linear sequence. Individual elements\r\n *\t\t are accessed by their position in this sequence. \r\n *\r\n *\t
- Dynamic array \r\n *\t
- Generally implemented as a dynamic array, it allows direct access to any element in the\r\n *\t\t sequence and provides relatively fast addition/removal of elements at the beginning or the end\r\n *\t\t of the sequence. \r\n *
- \r\n *
- Reference: http://www.cplusplus.com/reference/deque/deque/ \r\n *
Row size of the {@link matrix_ matrix} which contains elements.
\r\n *\r\n *Note that the {@link ROW} affects on time complexity of accessing and inserting element.\r\n * Accessing element is {@link ROW} times slower than ordinary {@link Vector} and inserting element\r\n * in middle position is {@link ROW} times faster than ordinary {@link Vector}.
\r\n *\r\n *When the {@link ROW} returns 8, time complexity of accessing element is O(8) and inserting\r\n * element in middle position is O(N/8). ({@link Vector}'s time complexity of accessement is O(1)\r\n * and inserting element is O(N)).
\r\n */\r\n get: function () { return 8; },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n Object.defineProperty(Deque, \"MIN_CAPACITY\", {\r\n /**\r\n *Minimum {@link capacity}.
\r\n *\r\n *Although a {@link Deque} has few elements, even no element is belonged to, the {@link Deque}\r\n * keeps the minimum {@link capacity} at least.
\r\n */\r\n get: function () { return 100; },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n /**\r\n * Get column size; {@link capacity_ capacity} / {@link ROW row}.\r\n */\r\n Deque.prototype.get_col_size = function () {\r\n return Math.floor(this.capacity_ / Deque.ROW);\r\n };\r\n Deque.prototype.assign = function (first, second) {\r\n // CLEAR PREVIOUS CONTENTS\r\n this.clear();\r\n if (first instanceof std.base.Iterator && second instanceof std.base.Iterator) {\r\n var begin = first;\r\n var end = second;\r\n var size = 0;\r\n for (var it = begin; !it.equal_to(end); it = it.next())\r\n size++;\r\n // RESERVE\r\n this.reserve(size);\r\n this.size_ = size;\r\n // ASSIGN CONTENTS\r\n var array = this.matrix_[0];\r\n for (var it = begin; !it.equal_to(end); it = it.next()) {\r\n if (array.length >= this.get_col_size()) {\r\n array = new Array();\r\n this.matrix_.push(array);\r\n }\r\n array.push(it.value);\r\n }\r\n }\r\n else {\r\n var size = first;\r\n var val = second;\r\n // RESERVE\r\n this.reserve(size);\r\n this.size_ = size;\r\n // ASSIGN CONTENTS\r\n var array = this.matrix_[0];\r\n for (var i = 0; i < size; i++) {\r\n if (array.length >= this.get_col_size()) {\r\n array = new Array();\r\n this.matrix_.push(array);\r\n }\r\n array.push(val);\r\n }\r\n }\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.reserve = function (capacity) {\r\n var prevMatrix = this.matrix_;\r\n var prevSize = this.size_;\r\n this.clear();\r\n // RESERVE\r\n this.size_ = prevSize;\r\n var array = this.matrix_[0];\r\n for (var i = 0; i < prevMatrix.length; i++)\r\n for (var j = 0; j < prevMatrix[i].length; j++) {\r\n if (array.length >= this.get_col_size()) {\r\n array = new Array();\r\n this.matrix_.push(array);\r\n }\r\n array.push(prevMatrix[i][j]);\r\n }\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.clear = function () {\r\n this.matrix_ = new Array();\r\n this.matrix_.push(new Array());\r\n this.size_ = 0;\r\n this.capacity_ = Deque.MIN_CAPACITY;\r\n };\r\n /* =========================================================\r\n ACCESSORS\r\n - GETTERS & SETTERS\r\n - ITERATORS\r\n ========================================================= */\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.begin = function () {\r\n if (this.empty() == true)\r\n return this.end();\r\n else\r\n return new DequeIterator(this, 0);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.end = function () {\r\n return new DequeIterator(this, -1);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.rbegin = function () {\r\n if (this.empty() == true)\r\n return this.rend();\r\n else\r\n return new DequeReverseIterator(this.end().prev());\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.rend = function () {\r\n return new DequeReverseIterator(this.end());\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.size = function () {\r\n return this.size_;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.capacity = function () {\r\n return this.capacity_;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.at = function (index) {\r\n if (index > this.size())\r\n throw new std.OutOfRange(\"Target index is greater than Deque's size.\");\r\n var indexPair = this.fetch_index(index);\r\n return this.matrix_[indexPair.first][indexPair.second];\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.set = function (index, val) {\r\n if (index > this.size())\r\n throw new std.OutOfRange(\"Target index is greater than Deque's size.\");\r\n var indexPair = this.fetch_index(index);\r\n this.matrix_[indexPair.first][indexPair.second] = val;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.front = function () {\r\n return this.matrix_[0][0];\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.back = function () {\r\n var lastArray = this.matrix_[this.matrix_.length - 1];\r\n return lastArray[lastArray.length - 1];\r\n };\r\n /**\r\n *Fetch row and column's index.
\r\n *\r\n *Fetches index of row and column of {@link matrix_} from sequence number.
\r\n *\r\n * @param index Sequence number\r\n */\r\n Deque.prototype.fetch_index = function (index) {\r\n var row;\r\n for (row = 0; row < this.matrix_.length; row++) {\r\n var array = this.matrix_[row];\r\n if (index < array.length)\r\n break;\r\n index -= array.length;\r\n }\r\n if (row == this.matrix_.length)\r\n row--;\r\n return new std.Pair(row, index);\r\n };\r\n /* =========================================================\r\n ELEMENTS I/O\r\n - PUSH & POP\r\n - INSERT\r\n - ERASE\r\n ============================================================\r\n PUSH & POP\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.push = function () {\r\n var items = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n items[_i - 0] = arguments[_i];\r\n }\r\n if (this.size_ + items.length > this.capacity_)\r\n this.reserve(this.size_ + items.length);\r\n var array = this.matrix_[this.matrix_.length - 1];\r\n for (var i = 0; i < items.length; i++) {\r\n if (array.length >= this.get_col_size()) {\r\n array = new Array();\r\n this.matrix_.push(array);\r\n }\r\n array.push(items[i]);\r\n }\r\n this.size_ += items.length;\r\n return this.size_;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.push_front = function (val) {\r\n // INSERT TO THE FRONT\r\n this.matrix_[0].unshift(val);\r\n this.size_++;\r\n if (this.size_ > this.capacity_)\r\n this.reserve(this.size_ * 2);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.push_back = function (val) {\r\n var lastArray = this.matrix_[this.matrix_.length - 1];\r\n if (lastArray.length >= this.get_col_size() && this.matrix_.length < Deque.ROW) {\r\n lastArray = new Array();\r\n this.matrix_.push(lastArray);\r\n }\r\n lastArray.push(val);\r\n this.size_++;\r\n if (this.size_ > this.capacity_)\r\n this.reserve(this.size_ * 2);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.pop_front = function () {\r\n if (this.empty() == true)\r\n return; // SOMEWHERE PLACE TO THROW EXCEPTION\r\n this.matrix_[0].shift();\r\n this.size_--;\r\n if (this.matrix_[0].length == 0)\r\n this.matrix_.shift();\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.pop_back = function () {\r\n if (this.empty() == true)\r\n return; // SOMEWHERE PLACE TO THROW EXCEPTION\r\n var lastArray = this.matrix_[this.matrix_.length - 1];\r\n lastArray.splice(lastArray.length - 1, 1);\r\n this.size_--;\r\n if (lastArray.length == 0)\r\n this.matrix_.splice(this.matrix_.length - 1, 1);\r\n };\r\n Deque.prototype.insert = function (position) {\r\n var args = [];\r\n for (var _i = 1; _i < arguments.length; _i++) {\r\n args[_i - 1] = arguments[_i];\r\n }\r\n var items = [];\r\n if (args.length == 1) {\r\n var val = args[0];\r\n items.push(val);\r\n }\r\n else if (args.length == 2 && typeof args[0] == \"number\") {\r\n var n = args[0];\r\n var val = args[1];\r\n for (var i = 0; i < n; i++)\r\n items.push(val);\r\n }\r\n else if (args.length == 2 && args[0] instanceof std.base.Iterator && args[1] instanceof std.base.Iterator) {\r\n var begin = args[0];\r\n var end = args[1];\r\n for (var it = begin; !it.equal_to(end); it = it.next())\r\n items.push(it.value);\r\n }\r\n // -----------------------------------------------------\r\n // INSERT ITEMS\r\n // -----------------------------------------------------\r\n // INSERTS CAREFULLY\r\n if (position.equal_to(this.end()) == true) {\r\n // WHEN INSERTS TO THE BACK SIDE\r\n this.push.apply(this, items);\r\n return;\r\n }\r\n this.size_ += items.length;\r\n if (this.size_ <= this.capacity_) {\r\n // ------------------------------------------------------\r\n // WHEN FITTING INTO RESERVED CAPACITY IS POSSIBLE\r\n // ------------------------------------------------------\r\n // INSERTS CAREFULLY CONSIDERING THE COL_SIZE\r\n var indexPair = this.fetch_index(position.index);\r\n var index = indexPair.first;\r\n var splicedValues = this.matrix_[index].splice(indexPair.second);\r\n if (splicedValues.length != 0)\r\n items = items.concat.apply(items, splicedValues);\r\n if (this.matrix_[index].length < Deque.ROW) {\r\n this.matrix_[index] =\r\n (_a = this.matrix_[index]).concat.apply(_a, items.splice(0, Deque.ROW - this.matrix_[index].length));\r\n }\r\n var splicedArray = this.matrix_.splice(index + 1);\r\n // INSERTS\r\n while (items.length != 0)\r\n this.matrix_.push(items.splice(0, Math.min(Deque.ROW, items.length)));\r\n // CONCAT WITH BACKS\r\n this.matrix_ = (_b = this.matrix_).concat.apply(_b, splicedArray);\r\n }\r\n else {\r\n // -----------------------------------------------------\r\n // WHEN CANNOT BE FIT INTO THE RESERVED CAPACITY\r\n // -----------------------------------------------------\r\n // JUST INSERT CARELESSLY\r\n // AND KEEP BLANACE BY THE RESERVE() METHOD\r\n if (position.equal_to(this.end()) == true) {\r\n this.matrix_.push(items); // ALL TO THE LAST\r\n }\r\n else {\r\n var indexPair = this.fetch_index(position.index);\r\n var index = indexPair.first;\r\n var splicedValues = this.matrix_[index].splice(indexPair.second);\r\n if (splicedValues.length != 0)\r\n items = items.concat.apply(items, splicedValues);\r\n // ALL TO THE MIDDLE\r\n this.matrix_[index] = (_c = this.matrix_[index]).concat.apply(_c, items);\r\n }\r\n // AND KEEP BALANCE BY RESERVE()\r\n this.reserve(this.size_);\r\n }\r\n return position;\r\n var _a, _b, _c;\r\n };\r\n Deque.prototype.erase = function (begin, end) {\r\n if (end === void 0) { end = null; }\r\n if (end == null)\r\n end = begin.next();\r\n var index = begin.index;\r\n var size = end.index - index;\r\n this.size_ -= size;\r\n while (size != 0) {\r\n var indexPair = this.fetch_index(index);\r\n var array = this.matrix_[indexPair.first];\r\n var myDeleteSize = Math.min(size, array.length - indexPair.second);\r\n array.splice(indexPair.second, myDeleteSize);\r\n if (array.length == 0)\r\n this.matrix_.splice(indexPair.first, 1);\r\n size -= myDeleteSize;\r\n }\r\n return begin;\r\n };\r\n /* ===============================================================\r\n UTILITIES\r\n =============================================================== */\r\n /**\r\n * @inheritdoc\r\n */\r\n Deque.prototype.swap = function (obj) {\r\n if (obj instanceof Deque)\r\n this.swap_deque(obj);\r\n else\r\n _super.prototype.swap.call(this, obj);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n Deque.prototype.swap_deque = function (obj) {\r\n _a = [obj.matrix_, this.matrix_], this.matrix_ = _a[0], obj.matrix_ = _a[1];\r\n _b = [obj.size_, this.size_], this.size_ = _b[0], obj.size_ = _b[1];\r\n _c = [obj.capacity_, this.capacity_], this.capacity_ = _c[0], obj.capacity_ = _c[1];\r\n var _a, _b, _c;\r\n };\r\n return Deque;\r\n }(std.base.Container));\r\n std.Deque = Deque;\r\n /**\r\n * An iterator of {@link Deque}.\r\n *\r\n * @author Jeongho NamConstruct from the source {@link Deque container}.
\r\n *\r\n *Note
\r\n *Do not create the iterator directly, by yourself.
\r\n *Use {@link Deque.begin begin()}, {@link Deque.end end()} in {@link Deque container} instead.
\r\n *\r\n * @param source The source {@link Deque container} to reference.\r\n * @param index Sequence number of the element in the source {@link Deque}.\r\n */\r\n function DequeIterator(source, index) {\r\n _super.call(this, source);\r\n this.index_ = index;\r\n }\r\n Object.defineProperty(DequeIterator.prototype, \"deque\", {\r\n get: function () { return this.source_; },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n Object.defineProperty(DequeIterator.prototype, \"value\", {\r\n /* ---------------------------------------------------------\r\n ACCESSORS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n get: function () {\r\n return this.deque.at(this.index_);\r\n },\r\n set: function (val) {\r\n this.deque.set(this.index_, val);\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n /**\r\n *Whether an iterator is equal with the iterator.
\r\n *\r\n *Compare two iterators and returns whether they are equal or not.
\r\n *\r\n *Note
\r\n *Iterator's equal_to() only compare souce container and index number.
\r\n *\r\n *Although elements in a pair, key and value are equal_to, if the source map or\r\n * index number is different, then the {@link equal_to equal_to()} will return false. If you want to\r\n * compare the elements of a pair, compare them directly by yourself.
\r\n *\r\n * @param obj An iterator to compare\r\n * @return Indicates whether equal or not.\r\n */\r\n DequeIterator.prototype.equal_to = function (obj) {\r\n return _super.prototype.equal_to.call(this, obj) && this.index_ == obj.index_;\r\n };\r\n Object.defineProperty(DequeIterator.prototype, \"index\", {\r\n /**\r\n * @inheritdoc\r\n */\r\n get: function () {\r\n return this.index_;\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n /* ---------------------------------------------------------\r\n MOVERS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n DequeIterator.prototype.prev = function () {\r\n if (this.index_ == -1)\r\n return new DequeIterator(this.deque, this.deque.size() - 1);\r\n else if (this.index_ - 1 < 0)\r\n return this.deque.end();\r\n else\r\n return new DequeIterator(this.deque, this.index_ - 1);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n DequeIterator.prototype.next = function () {\r\n if (this.index_ >= this.source_.size() - 1)\r\n return this.deque.end();\r\n else\r\n return new DequeIterator(this.deque, this.index_ + 1);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n DequeIterator.prototype.advance = function (n) {\r\n var new_index = this.index_ + n;\r\n if (new_index < 0 || new_index >= this.deque.size())\r\n return this.deque.end();\r\n else\r\n return new DequeIterator(this.deque, new_index);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n DequeIterator.prototype.swap = function (obj) {\r\n _a = [obj.value, this.value], this.value = _a[0], obj.value = _a[1];\r\n var _a;\r\n };\r\n return DequeIterator;\r\n }(std.base.Iterator));\r\n std.DequeIterator = DequeIterator;\r\n /**\r\n *A reverse-iterator of Deque.
\r\n *\r\n * @paramDoubly linked list.
\r\n *\r\n *{@link List}s are sequence containers that allow constant time insert and erase operations anywhere\r\n * within the sequence, and iteration in both directions.
\r\n *\r\n *List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements\r\n * they contain in different and unrelated storage locations. The ordering is kept internally by the association\r\n * to each element of a link to the element preceding it and a link to the element following it.
\r\n *\r\n *They are very similar to forward_list: The main difference being that forward_list objects are\r\n * single-linked lists, and thus they can only be iterated forwards, in exchange for being somewhat smaller and\r\n * more efficient.
\r\n *\r\n *Compared to other base standard sequence containers (array, vector and deque), lists perform generally\r\n * better in inserting, extracting and moving elements in any position within the container for which an iterator\r\n * has already been obtained, and therefore also in algorithms that make intensive use of these, like sorting\r\n * algorithms.
\r\n *\r\n *The main drawback of lists and forward_lists compared to these other sequence containers is that they lack\r\n * direct access to the elements by their position; For example, to access the sixth element in a list, one has\r\n * to iterate from a known position (like the beginning or the end) to that position, which takes linear time in\r\n * the distance between these. They also consume some extra memory to keep the linking information associated to\r\n * each element (which may be an important factor for large lists of small-sized elements).
\r\n *\r\n *Container properties
\r\n *- \r\n * \t
- Sequence \r\n * \t
- Elements in sequence containers are ordered in a strict linear sequence. Individual elements are\r\n *\t\t accessed by their position in this sequence. \r\n *\r\n * \t
- Doubly-linked list \r\n *\t
- Each element keeps information on how to locate the next and the previous elements, allowing constant\r\n *\t\t time insert and erase operations before or after a specific element (even of entire ranges), but no\r\n *\t\t direct random access. \r\n *
- \r\n *
- Reference: http://www.cplusplus.com/reference/list/list/\r\n *
Remove elements with specific value.
\r\n *\r\n *Removes from the container all the elements that compare equal to val. This calls the\r\n * destructor of these objects and reduces the container {@link size} by the number of elements removed.
\r\n *\r\n *Unlike member function {@link List.erase}, which erases elements by their position (using an\r\n * iterator), this function ({@link List.remove}) removes elements by their value.
\r\n *\r\n *A similar function, {@link List.remove_if}, exists, which allows for a condition other than an\r\n * equality comparison to determine whether an element is removed.
\r\n *\r\n * @param val Value of the elements to be removed.\r\n */\r\n List.prototype.remove = function (val) {\r\n var it = this.begin();\r\n while (!it.equal_to(this.end())) {\r\n if (std.equal_to(it.value, val) == true)\r\n it = this.erase(it);\r\n else\r\n it = it.next();\r\n }\r\n };\r\n /**\r\n *Remove elements fulfilling condition.
\r\n *\r\n * Removes from the container all the elements for which pred returns true. This\r\n * calls the destructor of these objects and reduces the container {@link size} by the number of elements\r\n * removed.
The function calls pred(it.value) for each element (where it is an iterator\r\n * to that element). Any of the elements in the list for which this returns true, are removed\r\n * from the
true for those values to be removed from the container, and\r\n *\t\t\t false for those remaining. This can either be a function pointer or a function\r\n *\t\t\t object.\r\n */\r\n List.prototype.remove_if = function (pred) {\r\n var it = this.begin();\r\n while (!it.equal_to(this.end())) {\r\n if (pred(it.value) == true)\r\n it = this.erase(it);\r\n else\r\n it = it.next();\r\n }\r\n };\r\n List.prototype.merge = function (obj, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n if (this == obj)\r\n return;\r\n var it = this.begin();\r\n while (obj.empty() == false) {\r\n var begin = obj.begin();\r\n while (!it.equal_to(this.end()) && compare(it.value, begin.value) == true)\r\n it = it.next();\r\n this.splice(it, obj, begin);\r\n }\r\n };\r\n List.prototype.splice = function (position, obj, begin, end) {\r\n if (begin === void 0) { begin = null; }\r\n if (end === void 0) { end = null; }\r\n if (begin == null) {\r\n begin = obj.begin();\r\n end = obj.end();\r\n }\r\n else if (end == null) {\r\n end = begin.next();\r\n }\r\n this.insert(position, begin, end);\r\n obj.erase(begin, end);\r\n };\r\n List.prototype.sort = function (compare) {\r\n //let whole: VectorConstruct from the source {@link List container}.
\r\n *\r\n *Note
\r\n *Do not create the iterator directly, by yourself.
\r\n *Use {@link List.begin begin()}, {@link List.end end()} in {@link List container} instead.
\r\n *\r\n * @param source The source {@link List container} to reference.\r\n * @param prev A refenrece of previous node ({@link ListIterator iterator}).\r\n * @param next A refenrece of next node ({@link ListIterator iterator}).\r\n * @param value Value to be stored in the node (iterator).\r\n */\r\n function ListIterator(source, prev, next, value) {\r\n _super.call(this, source);\r\n this.prev_ = prev;\r\n this.next_ = next;\r\n this.value_ = value;\r\n }\r\n /**\r\n * @inheritdoc\r\n */\r\n ListIterator.prototype.setPrev = function (prev) {\r\n this.prev_ = prev;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n ListIterator.prototype.setNext = function (next) {\r\n this.next_ = next;\r\n };\r\n /* ---------------------------------------------------------------\r\n ACCESSORS\r\n --------------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n ListIterator.prototype.equal_to = function (obj) {\r\n return this == obj;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n ListIterator.prototype.prev = function () {\r\n return this.prev_;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n ListIterator.prototype.next = function () {\r\n return this.next_;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n ListIterator.prototype.advance = function (step) {\r\n var it = this;\r\n if (step >= 0) {\r\n for (var i = 0; i < step; i++) {\r\n it = it.next();\r\n if (it.equal_to(this.source_.end()))\r\n return it;\r\n }\r\n }\r\n else {\r\n for (var i = 0; i < step; i++) {\r\n it = it.prev();\r\n if (it.equal_to(this.source_.end()))\r\n return it;\r\n }\r\n }\r\n return it;\r\n };\r\n Object.defineProperty(ListIterator.prototype, \"value\", {\r\n /**\r\n * @inheritdoc\r\n */\r\n get: function () {\r\n return this.value_;\r\n },\r\n set: function (val) {\r\n this.value_ = val;\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n /**\r\n * @inheritdoc\r\n */\r\n ListIterator.prototype.swap = function (obj) {\r\n var supp_prev = this.prev_;\r\n var supp_next = this.next_;\r\n this.prev_ = obj.prev_;\r\n this.next_ = obj.next_;\r\n obj.prev_ = supp_prev;\r\n obj.next_ = supp_next;\r\n if (this.source_.end() == this)\r\n this.source_.end_ = obj;\r\n else if (this.source_.end() == obj)\r\n this.source_.end_ = this;\r\n if (this.source_.begin() == this)\r\n this.source_.begin_ = obj;\r\n else if (this.source_.begin() == obj)\r\n this.source_.begin_ = this;\r\n };\r\n return ListIterator;\r\n }(std.base.Iterator));\r\n std.ListIterator = ListIterator;\r\n /**\r\n *A reverse-iterator of List.
\r\n *\r\n * @paramFIFO queue.
\r\n *\r\n *{@link Queue}s are a type of container adaptor, specifically designed to operate in a FIFO context\r\n * (first-in first-out), where elements are inserted into one end of the container and extracted from the other.\r\n *
\r\n *\r\n *{@link Queue}s are implemented as containers adaptors, which are classes that use an encapsulated object of\r\n * a specific container class as its underlying container, providing a specific set of member functions to access\r\n * its elements. Elements are pushed into the {@link IDeque.back back()} of the specific container and popped from\r\n * its {@link IDeque.front front()}.
\r\n *\r\n *{@link container_ The underlying container} may be one of the standard container class template or some\r\n * other specifically designed container class. This underlying container shall support at least the following\r\n * operations:
\r\n *\r\n *- \r\n *\t
- empty \r\n *\t
- size \r\n *\t
- front \r\n *\t
- back \r\n *\t
- push_back \r\n *\t
- pop_front \r\n *
The standard container classes {@link Deque} and {@link List} fulfill these requirements.\r\n * By default, if no container class is specified for a particular {@link Queue} class instantiation, the standard\r\n * container {@link List} is used.
\r\n *\r\n *- \r\n *\t
- Reference: http://www.cplusplus.com/reference/queue/queue/ \r\n *
Return size.
\r\n *Returns the number of elements in the {@link Queue}.
\r\n *\r\n *This member function effectively calls member {@link IDeque.size size()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @return The number of elements in the {@link container_ underlying container}.\r\n */\r\n Queue.prototype.size = function () {\r\n return this.container_.size();\r\n };\r\n /**\r\n *Test whether container is empty.
\r\n *returns whether the {@link Queue} is empty: i.e. whether its size is zero.
\r\n *\r\n *This member function efeectively calls member {@link IDeque.empty empty()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @returntrue if the {@link container_ underlying container}'s size is 0,\r\n *\t\t false otherwise. \r\n */\r\n Queue.prototype.empty = function () {\r\n return this.container_.empty();\r\n };\r\n /**\r\n * Access next element.
\r\n *Returns a value of the next element in the {@link Queue}.
\r\n *\r\n *The next element is the \"oldest\" element in the {@link Queue} and the same element that is popped out\r\n * from the queue when {@link pop Queue.pop()} is called.
\r\n *\r\n *This member function effectively calls member {@link IDeque.front front()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @return A value of the next element in the {@link Queue}.\r\n */\r\n Queue.prototype.front = function () {\r\n return this.container_.front();\r\n };\r\n /**\r\n *Access last element.
\r\n *\r\n *Returns a vaue of the last element in the queue. This is the \"newest\" element in the queue (i.e. the\r\n * last element pushed into the queue).
\r\n *\r\n *This member function effectively calls the member function {@link IDeque.back back()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @return A value of the last element in the {@link Queue}.\r\n */\r\n Queue.prototype.back = function () {\r\n return this.container_.back();\r\n };\r\n /* ---------------------------------------------------------\r\n ELEMENTS I/O\r\n --------------------------------------------------------- */\r\n /**\r\n *Insert element.
\r\n *\r\n *Inserts a new element at the end of the {@link Queue}, after its current last element.\r\n * The content of this new element is initialized to val.
\r\n *\r\n *This member function effectively calls the member function {@link IDeque.push_back push_back()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @param val Value to which the inserted element is initialized.\r\n */\r\n Queue.prototype.push = function (val) {\r\n this.container_.push_back(val);\r\n };\r\n /**\r\n *Remove next element.
\r\n *\r\n *Removes the next element in the {@link Queue}, effectively reducing its size by one.
\r\n *\r\n *The element removed is the \"oldest\" element in the {@link Queue} whose value can be retrieved by calling\r\n * member {@link front Queue.front()}
.\r\n *\r\n *This member function effectively calls the member function {@link IDeque.pop_front pop_front()} of the\r\n * {@link container_ underlying container} object.
\r\n */\r\n Queue.prototype.pop = function () {\r\n this.container_.pop_front();\r\n };\r\n /**\r\n *Swap contents.
\r\n *\r\n *Exchanges the contents of the container adaptor (this) by those of obj.
\r\n *\r\n *This member function calls the non-member function {@link IContainer.swap swap} (unqualified) to swap\r\n * the {@link container_ underlying containers}.
\r\n *\r\n * @param obj Another {@link Queue} container adaptor of the same type (i.e., instantiated with the same\r\n *\t\t\t template parameter, T). Sizes may differ. \r\n */\r\n Queue.prototype.swap = function (obj) {\r\n this.container_.swap(obj.container_);\r\n };\r\n return Queue;\r\n }());\r\n std.Queue = Queue;\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n /**\r\n *LIFO stack.
\r\n *\r\n *{@link Stack}s are a type of container adaptor, specifically designed to operate in a LIFO context\r\n * (last-in first-out), where elements are inserted and extracted only from one end of the
\r\n *\r\n *{@link Stack}s are implemented as containers adaptors, which are classes that use an encapsulated object of\r\n * a specific container class as its underlying container, providing a specific set of member functions to\r\n * access its elements. Elements are pushed/popped from the {@link ILinearContainer.back back()} of the\r\n * {@link ILinearContainer specific container}, which is known as the top of the {@link Stack}.
\r\n *\r\n *{@link container_ The underlying container} may be any of the standard container class templates or some\r\n * other specifically designed container class. The container shall support the following operations:
\r\n *\r\n *- \r\n *\t
- empty \r\n *\t
- size \r\n *\t
- front \r\n *\t
- back \r\n *\t
- push_back \r\n *\t
- pop_back \r\n *
The standard container classes {@link Vector}, {@link Deque} and {@link List} fulfill these requirements.\r\n * By default, if no container class is specified for a particular {@link Stack} class instantiation, the standard\r\n * container {@link List} is used.
\r\n *\r\n *- \r\n *\t
- Reference: http://www.cplusplus.com/reference/stack/stack/ \r\n *
Return size.
\r\n *\r\n *Returns the number of elements in the {@link Stack}.
\r\n *\r\n *This member function effectively calls member {@link ILinearContainer.size size()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @return The number of elements in the {@link container_ underlying container}.\r\n */\r\n Stack.prototype.size = function () {\r\n return this.container_.size();\r\n };\r\n /**\r\n *Test whether container is empty.
\r\n *\r\n *returns whether the {@link Stack} is empty: i.e. whether its size is zero.
\r\n *\r\n *This member function effectively calls member {@link ILinearContainer.empty empty()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @returntrue if the underlying container's size is 0,\r\n *\t\t false otherwise. \r\n */\r\n Stack.prototype.empty = function () {\r\n return this.container_.empty();\r\n };\r\n /**\r\n * Access next element.
\r\n *\r\n *Returns a value of the top element in the {@link Stack}
.\r\n *\r\n *Since {@link Stack}s are last-in first-out containers, the top element is the last element inserted into\r\n * the {@link Stack}.
\r\n *\r\n *This member function effectively calls member {@link ILinearContainer.back back()} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @return A value of the top element in the {@link Stack}.\r\n */\r\n Stack.prototype.top = function () {\r\n return this.container_.back();\r\n };\r\n /* ---------------------------------------------------------\r\n ELEMENTS I/O\r\n --------------------------------------------------------- */\r\n /**\r\n *Insert element.
\r\n *\r\n *Inserts a new element at the top of the {@link Stack}, above its current top element.
\r\n *\r\n *This member function effectively calls the member function\r\n * {@link ILinearContainer.push_back push_back()} of the {@link container_ underlying container} object.
\r\n *\r\n * @param val Value to which the inserted element is initialized.\r\n */\r\n Stack.prototype.push = function (val) {\r\n this.container_.push_back(val);\r\n };\r\n /**\r\n *Remove top element.
\r\n *\r\n *Removes the element on top of the {@link Stack}, effectively reducing its size by one.
\r\n *\r\n *The element removed is the latest element inserted into the {@link Stack}, whose value can be retrieved\r\n * by calling member {@link top Stack.top()}
.\r\n *\r\n *This member function effectively calls the member function {@link ILinearContainer.pop_back pop_back()}\r\n * of the {@link container_ underlying container} object.
\r\n */\r\n Stack.prototype.pop = function () {\r\n this.container_.pop_back();\r\n };\r\n /**\r\n *Swap contents.
\r\n *\r\n *Exchanges the contents of the container adaptor (this) by those of obj.
\r\n *\r\n *This member function calls the non-member function {@link IContainer.swap swap} (unqualified) to swap\r\n * the {@link container_ underlying containers}.
\r\n *\r\n * @param obj Another {@link Stack} container adaptor of the same type (i.e., instantiated with the same\r\n *\t\t\t template parameter, T). Sizes may differ. \r\n */\r\n Stack.prototype.swap = function (obj) {\r\n this.container_.swap(obj.container_);\r\n };\r\n return Stack;\r\n }());\r\n std.Stack = Stack;\r\n})(std || (std = {}));\r\n///An abstract set.
\r\n *\r\n *{@link SetContainer SetContainers} are containers that store elements allowing fast retrieval of\r\n * individual elements based on their value.
\r\n *\r\n *In an {@link SetContainer}, the value of an element is at the same time its key, used to\r\n * identify it. Keys are immutable, therefore, the elements in an {@link SetContainer} cannot be\r\n * modified once in the container - they can be inserted and removed, though.
\r\n *\r\n *{@link SetContainer} stores elements, keeps sequence and enables indexing by inserting elements into a\r\n * {@link List} and registering {@link ListIterator iterators} of the {@link data_ list container} to an index\r\n * table like {@link RBTree tree} or {@link HashBuckets hash-table}.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute\r\n *\t\tposition in the\r\n *\t \r\n *\r\n *\t
- Set \r\n *\t
- The value of an element is also the key used to identify it. \r\n *
Whether have the item or not.
\r\n *\r\n *Indicates whether a set has an item having the specified identifier.
\r\n *\r\n * @param key Key value of the element whose mapped value is accessed.\r\n *\r\n * @return Whether the set has an item having the specified identifier.\r\n */\r\n SetContainer.prototype.has = function (val) {\r\n return this.count(val) != 0;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n SetContainer.prototype.size = function () {\r\n return this.data_.size();\r\n };\r\n /* =========================================================\r\n ELEMENTS I/O\r\n - INSERT\r\n - ERASE\r\n - POST-PROCESS\r\n ============================================================\r\n INSERT\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n SetContainer.prototype.push = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n for (var i = 0; i < args.length; i++)\r\n this.insert_by_val(args[i]);\r\n return this.size();\r\n };\r\n SetContainer.prototype.insert = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n if (args.length == 1)\r\n return this.insert_by_val(args[0]);\r\n else if (args.length == 2 && args[0] instanceof base.Iterator) {\r\n if (args[1] instanceof base.Iterator && args[0].get_source() != this && args[1].get_source() != this)\r\n return this.insert_by_range(args[0], args[1]);\r\n else\r\n return this.insert_by_hint(args[0], args[1]);\r\n }\r\n };\r\n /**\r\n * @hidden\r\n */\r\n SetContainer.prototype.insert_by_hint = function (hint, val) {\r\n // INSERT\r\n var list_iterator = this.data_.insert(hint.get_list_iterator(), val);\r\n // POST-PROCESS\r\n var it = new std.SetIterator(this, list_iterator);\r\n this.handle_insert(it);\r\n return it;\r\n };\r\n /**\r\n * @hidden\r\n */\r\n SetContainer.prototype.insert_by_range = function (begin, end) {\r\n for (var it = begin; it.equal_to(end) == false; it = it.next())\r\n this.insert_by_val(it.value);\r\n };\r\n SetContainer.prototype.erase = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n if (args.length == 1) {\r\n if (args[0] instanceof base.Iterator && args[0].get_source() == this)\r\n return this.erase_by_iterator(args[0]);\r\n else\r\n return this.erase_by_val(args[0]);\r\n }\r\n else if (args.length == 2 && args[0] instanceof base.Iterator && args[1] instanceof base.Iterator)\r\n return this.erase_by_range(args[0], args[1]);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n SetContainer.prototype.erase_by_val = function (val) {\r\n // TEST WHETHER EXISTS\r\n var it = this.find(val);\r\n if (it.equal_to(this.end()) == true)\r\n return 0;\r\n // ERASE\r\n this.erase_by_iterator(it);\r\n return 1;\r\n };\r\n /**\r\n * @hidden\r\n */\r\n SetContainer.prototype.erase_by_iterator = function (it) {\r\n // ERASE\r\n var list_iterator = this.data_.erase(it.get_list_iterator());\r\n // POST-PROCESS\r\n this.handle_erase(it);\r\n return new std.SetIterator(this, list_iterator);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n SetContainer.prototype.erase_by_range = function (begin, end) {\r\n // ERASE\r\n var list_iterator = this.data_.erase(begin.get_list_iterator(), end.get_list_iterator());\r\n // POST-PROCESS\r\n for (var it = begin; !it.equal_to(end); it = it.next())\r\n this.handle_erase(it);\r\n return new std.SetIterator(this, list_iterator); //begin.prev();\r\n };\r\n return SetContainer;\r\n }(base.Container));\r\n base.SetContainer = SetContainer;\r\n })(base = std.base || (std.base = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n /**\r\n *An iterator of a Set.
\r\n *\r\n * @author Jeongho NamConstruct from source and index number.
\r\n *\r\n *Note
\r\n *Do not create iterator directly.
\r\n *Use begin(), find() or end() in Map instead.
\r\n *\r\n * @param map The source Set to reference.\r\n * @param index Sequence number of the element in the source Set.\r\n */\r\n function SetIterator(source, it) {\r\n _super.call(this, source);\r\n this.list_iterator_ = it;\r\n }\r\n /* ---------------------------------------------------------\r\n MOVERS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n SetIterator.prototype.prev = function () {\r\n return new SetIterator(this.set, this.list_iterator_.prev());\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n SetIterator.prototype.next = function () {\r\n return new SetIterator(this.set, this.list_iterator_.next());\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n SetIterator.prototype.advance = function (size) {\r\n return new SetIterator(this.set, this.list_iterator_.advance(size));\r\n };\r\n Object.defineProperty(SetIterator.prototype, \"set\", {\r\n /* ---------------------------------------------------------\r\n ACCESSORS\r\n --------------------------------------------------------- */\r\n /**\r\n * @hidden\r\n */\r\n get: function () {\r\n return this.source_;\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n SetIterator.prototype.get_list_iterator = function () {\r\n return this.list_iterator_;\r\n };\r\n Object.defineProperty(SetIterator.prototype, \"value\", {\r\n /**\r\n * @inheritdoc\r\n */\r\n get: function () {\r\n return this.list_iterator_.value;\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n /* ---------------------------------------------------------\r\n COMPARISONS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n SetIterator.prototype.equal_to = function (obj) {\r\n return _super.prototype.equal_to.call(this, obj) && this.list_iterator_ == obj.list_iterator_;\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n SetIterator.prototype.less = function (obj) {\r\n return std.less(this.value, obj.value);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n SetIterator.prototype.hash = function () {\r\n return std.base.code(this.value);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n SetIterator.prototype.swap = function (obj) {\r\n this.list_iterator_.swap(obj.list_iterator_);\r\n };\r\n return SetIterator;\r\n }(std.base.Iterator));\r\n std.SetIterator = SetIterator;\r\n /**\r\n *A reverse-iterator of Set.
\r\n *\r\n * @paramAn abstract set.
\r\n *\r\n *{@link SetContainer SetContainers} are containers that store elements allowing fast retrieval of\r\n * individual elements based on their value.
\r\n *\r\n *In an {@link SetContainer}, the value of an element is at the same time its key, used to uniquely\r\n * identify it. Keys are immutable, therefore, the elements in an {@link SetContainer} cannot be modified\r\n * once in the container - they can be inserted and removed, though.
\r\n *\r\n *{@link SetContainer} stores elements, keeps sequence and enables indexing by inserting elements into a\r\n * {@link List} and registering {@link ListIterator iterators} of the {@link data_ list container} to an index\r\n * table like {@link RBTree tree} or {@link HashBuckets hash-table}.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute\r\n *\t\tposition in the\r\n *\t \r\n *\r\n *\t
- Set \r\n *\t
- The value of an element is also the key used to identify it. \r\n *\r\n *\t
- Unique keys \r\n *\t
- No two elements in the container can have equivalent keys. \r\n *
An abstract set.
\r\n *\r\n *{@link SetContainer SetContainers} are containers that store elements allowing fast retrieval of\r\n * individual elements based on their value.
\r\n *\r\n *In an {@link SetContainer}, the value of an element is at the same time its key, used to\r\n * identify it. Keys are immutable, therefore, the elements in an {@link SetContainer} cannot be\r\n * modified once in the container - they can be inserted and removed, though.
\r\n *\r\n *{@link SetContainer} stores elements, keeps sequence and enables indexing by inserting elements into a\r\n * {@link List} and registering {@link ListIterator iterators} of the {@link data_ list container} to an index\r\n * table like {@link RBTree tree} or {@link HashBuckets hash-table}.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute\r\n *\t\tposition in the\r\n *\t \r\n *\r\n *\t
- Set \r\n *\t
- The value of an element is also the key used to identify it. \r\n *\r\n *\t
- Multiple equivalent keys \r\n *\t
- Multiple elements in the container can have equivalent keys. \r\n *
Hashed, unordered set.
\r\n *\r\n *{@link HashSet}s are containers that store unique elements in no particular order, and which\r\n * allow for fast retrieval of individual elements based on their value.
\r\n *\r\n *In an {@link HashSet}, the value of an element is at the same time its key, that\r\n * identifies it uniquely. Keys are immutable, therefore, the elements in an {@link HashSet} cannot be\r\n * modified once in the container - they can be inserted and removed, though.
\r\n *\r\n *Internally, the elements in the {@link HashSet} are not sorted in any particular order, but\r\n * organized into buckets depending on their hash values to allow for fast access to individual elements\r\n * directly by their values (with a constant average time complexity on average).
\r\n *\r\n *{@link HashSet} containers are faster than {@link TreeSet} containers to access individual\r\n * elements by their key, although they are generally less efficient for range iteration through a\r\n * subset of their elements.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- Elements in associative containers are referenced by their key and not by their absolute\r\n *\t\t position in the \r\n *\r\n *\t
- Hashed \r\n *\t
- Hashed containers organize their elements using hash tables that allow for fast access to elements\r\n *\t\t by their key. \r\n *\r\n *\t
- Set \r\n *\t
- The value of an element is also the key used to identify it. \r\n *\r\n *\t
- Unique keys \r\n *\t
- No two elements in the container can have equivalent keys. \r\n *
- \r\n *
- Reference: http://www.cplusplus.com/reference/unordered_set/unordered_set/ \r\n *
Hashed, unordered Multiset.
\r\n *\r\n *{@link HashMultiSet HashMultiSets} are containers that store elements in no particular order, allowing fast\r\n * retrieval of individual elements based on their value, much like {@link HashSet} containers,\r\n * but allowing different elements to have equivalent values.
\r\n *\r\n *In an {@link HashMultiSet}, the value of an element is at the same time its key, used to\r\n * identify it. Keys are immutable, therefore, the elements in an {@link HashMultiSet} cannot be\r\n * modified once in the container - they can be inserted and removed, though.
\r\n *\r\n *Internally, the elements in the {@link HashMultiSet} are not sorted in any particular, but\r\n * organized into buckets depending on their hash values to allow for fast access to individual\r\n * elements directly by their values (with a constant average time complexity on average).
\r\n *\r\n *Elements with equivalent values are grouped together in the same bucket and in such a way that an\r\n * iterator can iterate through all of them. Iterators in the container are doubly linked iterators.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- Elements in associative containers are referenced by their key and not by their absolute\r\n *\t\t position in the \r\n *\r\n *\t
- Hashed \r\n *\t
- Hashed containers organize their elements using hash tables that allow for fast access to elements\r\n *\t\t by their key. \r\n *\r\n *\t
- Set \r\n *\t
- The value of an element is also the key used to identify it. \r\n *\r\n *\t
- Multiple equivalent keys \r\n *\t
- The container can hold multiple elements with equivalent keys. \r\n *
- \r\n *
- Reference: http://www.cplusplus.com/reference/unordered_set/unordered_multiset/ \r\n *
An abstract map.
\r\n *\r\n *{@link MapContainer MapContainers} are associative containers that store elements formed by a combination\r\n * of a key value (Key) and a mapped value (T), and which allows for fast retrieval\r\n * of individual elements based on their keys.
\r\n *\r\n *In a {@link MapContainer}, the key values are generally used to identify the elements, while the\r\n * mapped values store the content associated to this key. The types of key and\r\n * mapped value may differ, and are grouped together in member type value_type, which is a\r\n * {@link Pair} type combining both:
\r\n *\r\n * typedef pair
{@link MapContainer} stores elements, keeps sequence and enables indexing by inserting elements into a\r\n * {@link List} and registering {@link ListIterator iterators} of the {@link data_ list container} to an index\r\n * table like {@link RBTree tree} or {@link HashBuckets hash-table}.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute position\r\n *\t\tin the\r\n *\t \r\n *\r\n *\t
- Map \r\n *\t
- \r\n *\t\tEach element associates a key to a mapped value:\r\n *\t\tKeys are meant to identify the elements whose main content is the mapped value.\r\n *\t \r\n *
Assign new content to content.
\r\n *\r\n *Assigns new contents to the container, replacing its current contents, and modifying its {@link size}\r\n * accordingly.
\r\n *\r\n * @param begin Input interator of the initial position in a sequence.\r\n * @param end Input interator of the final position in a sequence.\r\n */\r\n MapContainer.prototype.assign = function (begin, end) {\r\n // INSERT\r\n for (var it = begin; it.equal_to(end) == false; it = it.next())\r\n this.insert_by_pair(new std.Pair(it.first, it.second));\r\n };\r\n /**\r\n *Clear content.
\r\n *\r\n *Removes all elements from the container, leaving the container with a size of 0.
\r\n */\r\n MapContainer.prototype.clear = function () {\r\n this.data_.clear();\r\n };\r\n /**\r\n *Return iterator to beginning.
\r\n *\r\n *Returns an iterator referring the first element in the
\r\n *\r\n *Note
\r\n *If the container is {@link empty}, the returned iterator is same with {@link end end()}.
\r\n *\r\n * @return An iterator to the first element in the The iterator containes the first element's value.\r\n */\r\n MapContainer.prototype.begin = function () {\r\n return new std.MapIterator(this, this.data_.begin());\r\n };\r\n /**\r\n *Return iterator to end.
\r\n *Returns an iterator referring to the past-the-end element in the
\r\n *\r\n *The past-the-end element is the theoretical element that would follow the last element in the\r\n * It does not point to any element, and thus shall not be dereferenced.
\r\n *\r\n *Because the ranges used by functions of the container do not include the element reference by their\r\n * closing iterator, this function is often used in combination with {@link MapContainer}.{@link begin} to\r\n * specify a range including all the elements in the
\r\n *\r\n *Note
\r\n *Returned iterator from {@link MapContainer}.{@link end} does not refer any element. Trying to accessing\r\n * element by the iterator will cause throwing exception ({@link OutOfRange}).
\r\n *\r\n *If the container is {@link empty}, this function returns the same as {@link begin}.
\r\n *\r\n * @return An iterator to the end element in the\r\n */\r\n MapContainer.prototype.end = function () {\r\n return new std.MapIterator(this, this.data_.end());\r\n };\r\n /**\r\n *Return {@link MapReverseIterator reverse iterator} to reverse beginning.
\r\n *\r\n *Returns a {@link MapReverseIterator reverse iterator} pointing to the last element in the container\r\n * (i.e., its reverse beginning).
\r\n *\r\n * {@link MapReverseIterator Reverse iterators} iterate backwards: increasing them moves them towards the\r\n * beginning of the \r\n *\r\n *{@link rbegin} points to the element preceding the one that would be pointed to by member {@link end}.\r\n *
\r\n *\r\n * @return A {@link MapReverseIterator reverse iterator} to the reverse beginning of the sequence\r\n *\r\n */\r\n MapContainer.prototype.rbegin = function () {\r\n if (this.empty() == true)\r\n return this.rend();\r\n else\r\n return new std.MapReverseIterator(this, this.data_.end().prev());\r\n };\r\n /**\r\n *Return {@link MapReverseIterator reverse iterator} to reverse end.
\r\n *\r\n *Returns a {@link MapReverseIterator reverse iterator} pointing to the theoretical element right before\r\n * the first element in the {@link MapContainer map container} (which is considered its reverse end).\r\n *
\r\n *\r\n *The range between {@link MapContainer}.{@link rbegin} and {@link MapContainer}.{@link rend} contains\r\n * all the elements of the container (in reverse order).
\r\n *\r\n * @return A {@link MapReverseIterator reverse iterator} to the reverse end of the sequence\r\n */\r\n MapContainer.prototype.rend = function () {\r\n return new std.MapReverseIterator(this, this.data_.end());\r\n };\r\n /* ---------------------------------------------------------\r\n ELEMENTS\r\n --------------------------------------------------------- */\r\n /**\r\n *Whether have the item or not.
\r\n *\r\n *Indicates whether a map has an item having the specified identifier.
\r\n *\r\n * @param key Key value of the element whose mapped value is accessed.\r\n *\r\n * @return Whether the map has an item having the specified identifier.\r\n */\r\n MapContainer.prototype.has = function (key) {\r\n return this.count(key) != 0;\r\n };\r\n /**\r\n * Return the number of elements in the map.\r\n */\r\n MapContainer.prototype.size = function () {\r\n return this.data_.size();\r\n };\r\n /**\r\n * Test whether the container is empty.\r\n */\r\n MapContainer.prototype.empty = function () {\r\n return this.size() == 0;\r\n };\r\n MapContainer.prototype.insert = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n if (args.length == 1 && args[0] instanceof std.Pair) {\r\n return this.insert_by_pair(args[0]);\r\n }\r\n else if (args.length == 1 && args[0] instanceof Array) {\r\n return this.insert_by_tuple(args[0]);\r\n }\r\n else if (args.length == 2 && args[0] instanceof std.MapIterator && args[1] instanceof std.Pair) {\r\n return this.insert_by_hint(args[0], args[1]);\r\n }\r\n else if (args.length == 2 && args[0] instanceof std.MapIterator && args[1] instanceof Array) {\r\n return this.insert_by_hint_with_tuple(args[0], args[1]);\r\n }\r\n else if (args.length == 2 && args[0] instanceof std.MapIterator && args[1] instanceof std.MapIterator) {\r\n return this.insert_by_range(args[0], args[1]);\r\n }\r\n };\r\n /**\r\n * @hidden\r\n */\r\n MapContainer.prototype.insert_by_tuple = function (tuple) {\r\n return this.insert_by_pair(new std.Pair(tuple[0], tuple[1]));\r\n };\r\n /**\r\n * @hidden\r\n */\r\n MapContainer.prototype.insert_by_hint = function (hint, pair) {\r\n // INSERT\r\n var list_it = this.data_.insert(hint.get_list_iterator(), pair);\r\n // POST-PROCESS\r\n var it = new std.MapIterator(this, list_it);\r\n this.handle_insert(it);\r\n return it;\r\n };\r\n /**\r\n * @hidden\r\n */\r\n MapContainer.prototype.insert_by_hint_with_tuple = function (hint, tuple) {\r\n return this.insert_by_hint(hint, new std.Pair(tuple[0], tuple[1]));\r\n };\r\n /**\r\n * @hidden\r\n */\r\n MapContainer.prototype.insert_by_range = function (begin, end) {\r\n for (var it = begin; it.equal_to(end) == false; it = it.next())\r\n this.insert_by_pair(new std.Pair(it.first, it.second));\r\n };\r\n MapContainer.prototype.erase = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n if (args.length == 1) {\r\n if (args[0] instanceof std.MapIterator && args[0].get_source() == this)\r\n return this.erase_by_iterator(args[0]);\r\n else\r\n return this.erase_by_key(args[0]);\r\n }\r\n else if (args.length == 2 && args[0] instanceof std.MapIterator && args[1] instanceof std.MapIterator)\r\n return this.erase_by_range(args[0], args[1]);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n MapContainer.prototype.erase_by_key = function (key) {\r\n var it = this.find(key);\r\n if (it.equal_to(this.end()) == true)\r\n return 0;\r\n this.erase_by_iterator(it);\r\n return 1;\r\n };\r\n /**\r\n * @hidden\r\n */\r\n MapContainer.prototype.erase_by_iterator = function (it) {\r\n // ERASE\r\n var listIterator = this.data_.erase(it.get_list_iterator());\r\n // POST-PROCESS\r\n this.handle_erase(it);\r\n return new std.MapIterator(this, listIterator);\r\n ;\r\n };\r\n /**\r\n * @hidden\r\n */\r\n MapContainer.prototype.erase_by_range = function (begin, end) {\r\n // ERASE\r\n var listIterator = this.data_.erase(begin.get_list_iterator(), end.get_list_iterator());\r\n // POST-PROCESS\r\n for (var it = begin; !it.equal_to(end); it = it.next())\r\n this.handle_erase(it);\r\n return new std.MapIterator(this, listIterator);\r\n };\r\n /* ===============================================================\r\n UTILITIES\r\n =============================================================== */\r\n /**\r\n *Swap content.
\r\n *\r\n *Exchanges the content of the container by the content of obj, which is another\r\n * {@link MapContainer map} of the same type. Sizes abd container type may differ.
\r\n *\r\n *After the call to this member function, the elements in this container are those which were\r\n * in obj before the call, and the elements of obj are those which were in this. All\r\n * iterators, references and pointers remain valid for the swapped objects.
\r\n *\r\n *Notice that a non-member function exists with the same name, {@link std.swap swap}, overloading that\r\n * algorithm with an optimization that behaves like this member function.
\r\n *\r\n * @param obj Another {@link MapContainer map container} of the same type of elements as this (i.e.,\r\n *\t\t\t with the same template parameters, Key and T) whose content is swapped\r\n *\t\t\t with that of this {@link MapContaier container}.\r\n */\r\n MapContainer.prototype.swap = function (obj) {\r\n var supplement = new std.HashMultiMap(this.begin(), this.end());\r\n this.assign(obj.begin(), obj.end());\r\n obj.assign(supplement.begin(), supplement.end());\r\n };\r\n return MapContainer;\r\n }());\r\n base.MapContainer = MapContainer;\r\n })(base = std.base || (std.base = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n /**\r\n * An iterator of {@link MapColntainer map container}.\r\n *\r\n * @author Jeongho NamWhether an iterator is equal with the iterator.
\r\n *\r\n *Compare two iterators and returns whether they are equal or not.
\r\n *\r\n * @param obj An iterator to compare\r\n * @return Indicates whether equal or not.\r\n */\r\n MapIterator.prototype.equal_to = function (obj) {\r\n return this.source_ == obj.source_ && this.list_iterator_.equal_to(obj.list_iterator_);\r\n };\r\n MapIterator.prototype.less = function (obj) {\r\n return std.less(this.first, obj.first);\r\n };\r\n MapIterator.prototype.hash = function () {\r\n return std.hash(this.first);\r\n };\r\n MapIterator.prototype.swap = function (obj) {\r\n this.list_iterator_.swap(obj.list_iterator_);\r\n };\r\n return MapIterator;\r\n }());\r\n std.MapIterator = MapIterator;\r\n /**\r\n * A reverse-iterator of {@link MapColntainer map container}.\r\n *\r\n * @author Jeongho NamAn abstract unique-map.
\r\n *\r\n *{@link UniqueMap UniqueMaps} are associative containers that store elements formed by a combination of a\r\n * key value (Key) and a mapped value (T), and which allows for fast retrieval of\r\n * individual elements based on their keys.
\r\n *\r\n *In a {@link MapContainer}, the key values are generally used to uniquely identify the elements,\r\n * while the mapped values store the content associated to this key. The types of key and\r\n * mapped value may differ, and are grouped together in member type value_type, which is a\r\n * {@link Pair} type combining both:
\r\n *\r\n * typedef pair
{@link UniqueMap} stores elements, keeps sequence and enables indexing by inserting elements into a\r\n * {@link List} and registering {@link ListIterator iterators} of the {@link data_ list container} to an index\r\n * table like {@link RBTree tree} or {@link HashBuckets hash-table}.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute position\r\n *\t\tin the\r\n *\t \r\n *\r\n *\t
- Map \r\n *\t
- \r\n *\t\tEach element associates a key to a mapped value:\r\n *\t\tKeys are meant to identify the elements whose main content is the mapped value.\r\n *\t \r\n *\r\n *\t
- Unique keys \r\n *\t
- No two elements in the container can have equivalent keys. \r\n *
Get an element
\r\n *\r\n *Returns a reference to the mapped value of the element identified with key.
\r\n *\r\n * @param key Key value of the element whose mapped value is accessed.\r\n *\r\n * @throw exception out of range\r\n *\r\n * @return A reference object of the mapped value (_Ty)\r\n */\r\n UniqueMap.prototype.get = function (key) {\r\n var it = this.find(key);\r\n if (it.equal_to(this.end()) == true)\r\n throw new std.OutOfRange(\"unable to find the matched key.\");\r\n return it.second;\r\n };\r\n /**\r\n *Set an item as the specified identifier.
\r\n *\r\n *If the identifier is already in map, change value of the identifier. If not, then insert the object\r\n * with the identifier.
\r\n *\r\n * @param key Key value of the element whose mapped value is accessed.\r\n * @param val Value, the item.\r\n */\r\n UniqueMap.prototype.set = function (key, val) {\r\n var it = this.find(key);\r\n if (it.equal_to(this.end()) == true)\r\n this.insert(new std.Pair(key, val));\r\n else\r\n it.second = val;\r\n };\r\n UniqueMap.prototype.insert = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n return _super.prototype.insert.apply(this, args);\r\n };\r\n return UniqueMap;\r\n }(base.MapContainer));\r\n base.UniqueMap = UniqueMap;\r\n })(base = std.base || (std.base = {}));\r\n})(std || (std = {}));\r\n///An abstract multi-map.
\r\n *\r\n *{@link MultiMap MultiMaps} are associative containers that store elements formed by a combination of a\r\n * key value (Key) and a mapped value (T), and which allows for fast retrieval of\r\n * individual elements based on their keys.
\r\n *\r\n *In a {@link MapContainer}, the key values are generally used to identify the elements, while the\r\n * mapped values store the content associated to this key. The types of key and\r\n * mapped value may differ, and are grouped together in member type value_type, which is a\r\n * {@link Pair} type combining both:
\r\n *\r\n * typedef pair
{@link UniqueMap} stores elements, keeps sequence and enables indexing by inserting elements into a\r\n * {@link List} and registering {@link ListIterator iterators} of the {@link data_ list container} to an index\r\n * table like {@link RBTree tree} or {@link HashBuckets hash-table}.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute position\r\n *\t\tin the\r\n *\t \r\n *\r\n *\t
- Map \r\n *\t
- \r\n *\t\tEach element associates a key to a mapped value:\r\n *\t\tKeys are meant to identify the elements whose main content is the mapped value.\r\n *\t \r\n *\r\n *\t
- Multiple equivalent keys \r\n *\t
- Multiple elements in the container can have equivalent keys. \r\n *
Hashed, unordered map.
\r\n *\r\n *{@link HashMap}s are associative containers that store elements formed by the\r\n * combination of a key value and a mapped value, and which allows for fast\r\n * retrieval of individual elements based on their keys.
\r\n *\r\n *In an {@link HashMap}, the key value is generally used to uniquely identify\r\n * the element, while the mapped value is an object with the content associated to this\r\n * key. Types of key and mapped value may differ.
\r\n *\r\n *Internally, the elements in the {@link HashMap} are not sorted in any particular order\r\n * with respect to either their key or mapped values, but organized into buckets\r\n * depending on their hash values to allow for fast access to individual elements directly by\r\n * their key values (with a constant average time complexity on average).
\r\n *\r\n *{@link HashMap} containers are faster than {@link TreeMap} containers to access\r\n * individual elements by their key, although they are generally less efficient for range\r\n * iteration through a subset of their elements.
\r\n *\r\n *Container properties
\r\n *- \r\n * \t
- Associative \r\n * \t
- Elements in associative containers are referenced by their key and not by their absolute\r\n *\t\t position in the \r\n *\r\n * \t
- Hashed \r\n * \t
- Hashed containers organize their elements using hash tables that allow for fast access to elements\r\n *\t\t by their key. \r\n *\r\n * \t
- Map \r\n * \t
- Each element associates a key to a mapped value:\r\n *\t\t Keys are meant to identify the elements whose main content is the mapped value. \r\n *\r\n * \t
- Unique keys \r\n * \t
- No two elements in the container can have equivalent keys. \r\n *
- \r\n *
- Reference: http://www.cplusplus.com/reference/unordered_map/unordered_map/ \r\n *
Hashed, unordered Multimap.
\r\n *\r\n *{@link HashMap}s are associative containers that store elements formed by the combination of\r\n * a key value and a mapped value, much like {@link HashMap} containers, but allowing\r\n * different elements to have equivalent keys.
\r\n *\r\n *In an {@link HashMap}, the key value is generally used to uniquely identify the\r\n * element, while the mapped value is an object with the content associated to this key.\r\n * Types of key and mapped value may differ.
\r\n *\r\n *Internally, the elements in the {@link HashMap} are not sorted in any particular order with\r\n * respect to either their key or mapped values, but organized into buckets depending on\r\n * their hash values to allow for fast access to individual elements directly by their key values\r\n * (with a constant average time complexity on average).
\r\n *\r\n *Elements with equivalent keys are grouped together in the same bucket and in such a way that\r\n * an iterator can iterate through all of them. Iterators in the container are doubly linked iterators.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- Elements in associative containers are referenced by their key and not by their absolute\r\n *\t\t position in the \r\n *\r\n *\t
- Hashed \r\n *\t
- Hashed containers organize their elements using hash tables that allow for fast access to elements\r\n *\t\t by their key. \r\n *\r\n *\t
- Map \r\n *\t
- Each element associates a key to a mapped value:\r\n *\t\t Keys are meant to identify the elements whose main content is the mapped value. \r\n *\r\n *\t
- Multiple equivalent keys \r\n *\t
- The container can hold multiple elements with equivalent keys. \r\n *
- \r\n *
- Reference: http://www.cplusplus.com/reference/unordered_map/unordered_multimap/ \r\n *
Tree-structured set, std::set of STL.
{@link TreeSet}s are containers that store unique elements following a specific order.
\r\n *\r\n *In a {@link TreeSet}, the value of an element also identifies it (the value is itself the\r\n * key, of type T), and each value must be unique. The value of the elements in a\r\n * {@link TreeSet} cannot be modified once in the container (the elements are always const), but they\r\n * can be inserted or removed from the
\r\n *\r\n *Internally, the elements in a {@link TreeSet} are always sorted following a specific strict weak\r\n * ordering criterion indicated by its internal comparison method (of {@link less}).
\r\n *\r\n *{@link TreeSet} containers are generally slower than {@link HashSet} containers to access\r\n * individual elements by their key, but they allow the direct iteration on subsets based on their\r\n * order.
\r\n *\r\n *{@link TreeSet}s are typically implemented as binary search trees.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute\r\n *\t\tposition in the\r\n *\t \r\n *\r\n *\t
- Ordered \r\n *\t
- \r\n *\t\tThe elements in the container follow a strict order at all times. All inserted elements are\r\n *\t\tgiven a position in this order.\r\n *\t \r\n *\r\n *\t
- Set \r\n *\t
- The value of an element is also the key used to identify it. \r\n *\r\n *\t
- Unique keys \r\n *\t
- No two elements in the container can have equivalent keys. \r\n *
- \r\n *\t
- Reference: http://www.cplusplus.com/reference/set/set/ \r\n *
Return iterator to lower bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container which is not considered to go\r\n * before val (i.e., either it is equivalent or goes after).
\r\n *\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(element, val) would return false.
\r\n *\r\n *If the {@link Set} class is instantiated with the default comparison type ({@link less}), the\r\n * function returns an iterator to the first element that is not less than val.
\r\n *\r\n *A similar member function, {@link upper_bound}, has the same behavior as {@link lower_bound},\r\n * except in the case that the {@link Set} contains an element equivalent to val: In this case\r\n * {@link lower_bound} returns an iterator pointing to that element, whereas {@link upper_bound} returns\r\n * an iterator pointing to the next element.
\r\n *\r\n * @param val Value to compare.\r\n *\r\n * @return An iterator to the the first element in the container which is not considered to go before\r\n *\t\t val, or {@link Set.end} if all elements are considered to go before val.\r\n */\r\n TreeSet.prototype.lower_bound = function (val) {\r\n var node = this.tree_.find(val);\r\n if (node == null)\r\n return this.end();\r\n else if (std.less(node.value.value, val))\r\n return node.value.next();\r\n else\r\n return node.value;\r\n };\r\n /**\r\n *Return iterator to upper bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container which is not considered to go\r\n * after val.
\r\n *\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(element, val) would return true.
\r\n *\r\n *If the {@link Set} class is instantiated with the default comparison type ({@link less}), the\r\n * function returns an iterator to the first element that is greater than val.
\r\n *\r\n *A similar member function, {@link lower_bound}, has the same behavior as {@link upper_bound}, except\r\n * in the case that the {@link Set} contains an element equivalent to val: In this case\r\n * {@link lower_bound} returns an iterator pointing to that element, whereas {@link upper_bound} returns\r\n * an iterator pointing to the next element.
\r\n *\r\n * @param val Value to compare.\r\n *\r\n * @return An iterator to the the first element in the container which is not considered to go before\r\n *\t\t val, or {@link Set.end} if all elements are considered to go after val.\r\n */\r\n TreeSet.prototype.upper_bound = function (val) {\r\n var node = this.tree_.find(val);\r\n if (node == null)\r\n return this.end();\r\n else if (!std.equal_to(node.value.value, val) && !std.less(node.value.value, val))\r\n return node.value;\r\n else\r\n return node.value.next();\r\n };\r\n /**\r\n *Get range of equal elements.
\r\n *\r\n *Because all elements in a {@link Set} container are unique, the range returned will contain a\r\n * single element at most.
\r\n *\r\n *If no matches are found, the range returned has a length of zero, with both iterators pointing to\r\n * the first element that is considered to go after val according to the container's\r\n * internal comparison object (key_comp).
\r\n *\r\n *Two elements of a {@link Set} are considered equivalent if the container's comparison object\r\n * returns false reflexively (i.e., no matter the order in which the elements are passed as arguments).\r\n *
\r\n *\r\n * @param val Value to search for.\r\n *\r\n * @return The function returns a {@link Pair}, whose member {@link Pair.first} is the lower bound of\r\n *\t\t the range (the same as {@link lower_bound}), and {@link Pair.second} is the upper bound\r\n *\t\t (the same as {@link upper_bound}).\r\n */\r\n TreeSet.prototype.equal_range = function (val) {\r\n return new std.Pair(this.lower_bound(val), this.upper_bound(val));\r\n };\r\n /* =========================================================\r\n ELEMENTS I/O\r\n - INSERT\r\n - POST-PROCESS\r\n ============================================================\r\n INSERT\r\n --------------------------------------------------------- */\r\n /**\r\n * @hidden\r\n */\r\n TreeSet.prototype.insert_by_val = function (val) {\r\n var node = this.tree_.find(val);\r\n // IF EQUALS, THEN RETURN FALSE\r\n if (node != null && std.equal_to(node.value.value, val) == true)\r\n return new std.Pair(node.value, false);\r\n // INSERTS\r\n var it;\r\n if (node == null)\r\n it = this.end();\r\n else if (std.less(node.value.value, val) == true)\r\n it = node.value.next();\r\n else\r\n it = node.value;\r\n // ITERATOR TO RETURN\r\n it = this.insert(it, val);\r\n return new std.Pair(it, true);\r\n };\r\n /* ---------------------------------------------------------\r\n POST-PROCESS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeSet.prototype.handle_insert = function (item) {\r\n this.tree_.insert(item);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeSet.prototype.handle_erase = function (item) {\r\n this.tree_.erase(item);\r\n };\r\n /* ===============================================================\r\n UTILITIES\r\n =============================================================== */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeSet.prototype.swap = function (obj) {\r\n if (obj instanceof TreeSet)\r\n this.swap_tree_set(obj);\r\n else\r\n _super.prototype.swap.call(this, obj);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n TreeSet.prototype.swap_tree_set = function (obj) {\r\n _a = [obj.data_, this.data_], this.data_ = _a[0], obj.data_ = _a[1];\r\n _b = [obj.tree_, this.tree_], this.tree_ = _b[0], obj.tree_ = _b[1];\r\n var _a, _b;\r\n };\r\n return TreeSet;\r\n }(std.base.UniqueSet));\r\n std.TreeSet = TreeSet;\r\n /**\r\n *Tree-structured multiple-key set.
\r\n *\r\n *{@link TreeMultiSet TreeMultiSets} are containers that store elements following a specific order, and\r\n * where multiple elements can have equivalent values.
\r\n *\r\n *In a {@link TreeMultiSet}, the value of an element also identifies it (the value is itself\r\n * the key, of type T). The value of the elements in a {@link TreeMultiSet} cannot\r\n * be modified once in the container (the elements are always const), but they can be inserted or removed\r\n * from the
\r\n *\r\n *Internally, the elements in a {@link TreeMultiSet TreeMultiSets} are always sorted following a strict\r\n * weak ordering criterion indicated by its internal comparison method (of {@link IComparable.less less}).
\r\n *\r\n *{@link TreeMultiSet} containers are generally slower than {@link HashMultiSet} containers\r\n * to access individual elements by their key, but they allow the direct iteration on subsets based on\r\n * their order.
\r\n *\r\n *{@link TreeMultiSet TreeMultiSets} are typically implemented as binary search trees.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute\r\n *\t\tposition in the\r\n *\t \r\n *\r\n *\t
- Ordered \r\n *\t
- \r\n *\t\tThe elements in the container follow a strict order at all times. All inserted elements are\r\n *\t\tgiven a position in this order.\r\n *\t \r\n *\r\n *\t
- Set \r\n *\t
- The value of an element is also the key used to identify it. \r\n *\r\n *\t
- Multiple equivalent keys \r\n *\t
- Multiple elements in the container can have equivalent keys. \r\n *
- \r\n *\t
- Reference: http://www.cplusplus.com/reference/set/multiset/ \r\n *
Return iterator to lower bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container which is not considered to\r\n * go before val (i.e., either it is equivalent or goes after).
\r\n *\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(element,val) would return false.
\r\n *\r\n *If the {@link TreeMultiSet} class is instantiated with the default comparison type ({@link less}),\r\n * the function returns an iterator to the first element that is not less than val.
\r\n\r\n *A similar member function, {@link upper_bound}, has the same behavior as {@link lower_bound}, except\r\n * in the case that the {@link TreeMultiSet} contains elements equivalent to val: In this case\r\n * {@link lower_bound} returns an iterator pointing to the first of such elements, whereas\r\n * {@link upper_bound} returns an iterator pointing to the element following the last.
\r\n *\r\n * @param val Value to compare.\r\n *\r\n * @return An iterator to the the first element in the container which is not considered to go before\r\n *\t\t val, or {@link TreeMultiSet.end} if all elements are considered to go before val.\r\n */\r\n TreeMultiSet.prototype.lower_bound = function (val) {\r\n var node = this.tree_.find(val);\r\n if (node == null)\r\n return this.end();\r\n else if (std.equal_to(node.value.value, val))\r\n return node.value;\r\n else {\r\n var it = node.value;\r\n while (!std.equal_to(it, this.end()) && std.less(it.value, val))\r\n it = it.next();\r\n return it;\r\n }\r\n };\r\n /**\r\n *Return iterator to upper bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container which is considered to go after\r\n * val.
\r\n\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(val,element) would return true.
\r\n\r\n *If the {@code TreeMultiSet} class is instantiated with the default comparison type (less), the\r\n * function returns an iterator to the first element that is greater than val.
\r\n *\r\n *A similar member function, {@link lower_bound}, has the same behavior as {@link upper_bound}, except\r\n * in the case that the {@TreeMultiSet} contains elements equivalent to val: In this case\r\n * {@link lower_bound} returns an iterator pointing to the first of such elements, whereas\r\n * {@link upper_bound} returns an iterator pointing to the element following the last.
\r\n *\r\n * @param val Value to compare.\r\n *\r\n * @return An iterator to the the first element in the container which is considered to go after\r\n *\t\t val, or {@link TreeMultiSet.end} if no elements are considered to go after val.\r\n */\r\n TreeMultiSet.prototype.upper_bound = function (val) {\r\n var node = this.tree_.find(val);\r\n if (node == null)\r\n return this.end();\r\n else {\r\n var it = node.value;\r\n while (!std.equal_to(it, this.end()) && (std.equal_to(it.value, val) || std.less(it.value, val)))\r\n it = it.next();\r\n return it;\r\n }\r\n };\r\n /**\r\n *Get range of equal elements.
\r\n *\r\n *Returns the bounds of a range that includes all the elements in the container that are equivalent\r\n * to val.
\r\n *\r\n *If no matches are found, the range returned has a length of zero, with both iterators pointing to\r\n * the first element that is considered to go after val according to the container's\r\n * internal comparison object (key_comp).
\r\n *\r\n *Two elements of a multiset are considered equivalent if the container's comparison object returns\r\n * false reflexively (i.e., no matter the order in which the elements are passed as arguments).
\r\n *\r\n * @param key Value to search for.\r\n *\r\n * @return The function returns a {@link Pair}, whose member {@link Pair.first} is the lower bound of\r\n *\t\t the range (the same as {@link lower_bound}), and {@link Pair.second} is the upper bound\r\n *\t\t (the same as {@link upper_bound}).\r\n */\r\n TreeMultiSet.prototype.equal_range = function (val) {\r\n return new std.Pair(this.lower_bound(val), this.upper_bound(val));\r\n };\r\n /* =========================================================\r\n ELEMENTS I/O\r\n - INSERT\r\n - POST-PROCESS\r\n ============================================================\r\n INSERT\r\n --------------------------------------------------------- */\r\n /**\r\n * @hidden\r\n */\r\n TreeMultiSet.prototype.insert_by_val = function (val) {\r\n var node = this.tree_.find(val);\r\n var it;\r\n if (node == null) {\r\n it = this.end();\r\n }\r\n else if (std.equal_to(node.value.value, val) == true) {\r\n it = node.value.next();\r\n }\r\n else if (std.less(node.value.value, val) == true) {\r\n it = node.value.next();\r\n while (it.equal_to(this.end()) == false && std.less(it.value, val))\r\n it = it.next();\r\n }\r\n else {\r\n it = node.value;\r\n }\r\n // ITERATOR TO RETURN\r\n return this.insert(it, val);\r\n };\r\n /* ---------------------------------------------------------\r\n POST-PROCESS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMultiSet.prototype.handle_insert = function (item) {\r\n this.tree_.insert(item);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMultiSet.prototype.handle_erase = function (item) {\r\n this.tree_.erase(item);\r\n };\r\n /* ===============================================================\r\n UTILITIES\r\n =============================================================== */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMultiSet.prototype.swap = function (obj) {\r\n if (obj instanceof TreeMultiSet)\r\n this.swap_tree_set(obj);\r\n else\r\n _super.prototype.swap.call(this, obj);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n TreeMultiSet.prototype.swap_tree_set = function (obj) {\r\n _a = [obj.data_, this.data_], this.data_ = _a[0], obj.data_ = _a[1];\r\n _b = [obj.tree_, this.tree_], this.tree_ = _b[0], obj.tree_ = _b[1];\r\n var _a, _b;\r\n };\r\n return TreeMultiSet;\r\n }(std.base.MultiSet));\r\n std.TreeMultiSet = TreeMultiSet;\r\n})(std || (std = {}));\r\n/// Tree-structured map, std::map of STL.
{@link TreeMap TreeMaps} are associative containers that store elements formed by a combination of a\r\n * key value (Key) and a mapped value (T), following order.
\r\n *\r\n *In a {@link TreeMap}, the key values are generally used to sort and uniquely identify\r\n * the elements, while the mapped values store the content associated to this key. The types of\r\n * key and mapped value may differ, and are grouped together in member type value_type,\r\n * which is a {@link Pair} type combining both:
\r\n *\r\n * typedef Pair
Internally, the elements in a {@link TreeMap} are always sorted by its key following\r\n * a strict weak ordering criterion indicated by its internal comparison method {@link less}.\r\n *\r\n *
{@link TreeMap} containers are generally slower than {@link HashMap HashMap} containers to\r\n * access individual elements by their key, but they allow the direct iteration on subsets based on\r\n * their order.
\r\n *\r\n *{@link TreeMap}s are typically implemented as binary search trees.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- Elements in associative containers are referenced by their key and not by their absolute\r\n *\t\t position in the \r\n *\r\n *\t
- Ordered \r\n *\t
- The elements in the container follow a strict order at all times. All inserted elements are\r\n *\t\t given a position in this order. \r\n *\r\n *\t
- Map \r\n *\t
- Each element associates a key to a mapped value:\r\n *\t\t Keys are meant to identify the elements whose main content is the mapped value. \r\n *\r\n *\t
- Unique keys \r\n *\t
- No two elements in the container can have equivalent keys. \r\n *
- \r\n *\t
- Reference: http://www.cplusplus.com/reference/map/map/ \r\n *
Return iterator to lower bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container whose key is not considered to\r\n * go before k (i.e., either it is equivalent or goes after).
\r\n *\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(k, element_key) would return false.
\r\n *\r\n *If the {@link TreeMap} class is instantiated with the default comparison type ({@link less}),\r\n * the function returns an iterator to the first element whose key is not less than k
.\r\n *\r\n *A similar member function, {@link upper_bound}, has the same behavior as {@link lower_bound}, except\r\n * in the case that the {@link TreeMap} contains an element with a key equivalent to k: In this\r\n * case, {@link lower_bound} returns an iterator pointing to that element, whereas {@link upper_bound}\r\n * returns an iterator pointing to the next element.
\r\n *\r\n * @param k Key to search for.\r\n *\r\n * @return An iterator to the the first element in the container whose key is not considered to go before\r\n *\t\t k, or {@link TreeMap.end} if all keys are considered to go before k.\r\n */\r\n TreeMap.prototype.lower_bound = function (key) {\r\n var node = this.tree_.find(key);\r\n if (node == null)\r\n return this.end();\r\n else if (std.less(node.value.first, key))\r\n return node.value.next();\r\n else\r\n return node.value;\r\n };\r\n /**\r\n *Return iterator to upper bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container whose key is considered to\r\n * go after k
.\r\n *\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(k, element_key) would return true.
\r\n *\r\n *If the {@link TreeMap} class is instantiated with the default comparison type ({@link less}),\r\n * the function returns an iterator to the first element whose key is greater than k
.\r\n *\r\n *A similar member function, {@link lower_bound}, has the same behavior as {@link upper_bound}, except\r\n * in the case that the map contains an element with a key equivalent to k: In this case\r\n * {@link lower_bound} returns an iterator pointing to that element, whereas {@link upper_bound} returns an\r\n * iterator pointing to the next element.
\r\n *\r\n * @param k Key to search for.\r\n *\r\n * @return An iterator to the the first element in the container whose key is considered to go after\r\n *\t\t k, or {@link TreeMap.end} if no keys are considered to go after k.\r\n */\r\n TreeMap.prototype.upper_bound = function (key) {\r\n var node = this.tree_.find(key);\r\n if (node == null)\r\n return this.end();\r\n else if (!std.equal_to(node.value.first, key) && !std.less(node.value.first, key))\r\n return node.value;\r\n else\r\n return node.value.next();\r\n };\r\n /**\r\n *Get range of equal elements.
\r\n *\r\n *Returns the bounds of a range that includes all the elements in the container which have a key\r\n * equivalent to k
.\r\n *\r\n *Because the elements in a {@link TreeMap} container have unique keys, the range returned will\r\n * contain a single element at most.
\r\n *\r\n *If no matches are found, the range returned has a length of zero, with both iterators pointing to\r\n * the first element that has a key considered to go after k according to the container's internal\r\n * comparison object (key_comp).
\r\n *\r\n *Two keys are considered equivalent if the container's comparison object returns false reflexively\r\n * (i.e., no matter the order in which the keys are passed as arguments).
\r\n *\r\n * @param k Key to search for.\r\n *\r\n * @return The function returns a {@link Pair}, whose member {@link Pair.first} is the lower bound of\r\n *\t\t the range (the same as {@link lower_bound}), and {@link Pair.second} is the upper bound\r\n *\t\t (the same as {@link upper_bound}).\r\n */\r\n TreeMap.prototype.equal_range = function (key) {\r\n return new std.Pair(this.lower_bound(key), this.upper_bound(key));\r\n };\r\n /* =========================================================\r\n ELEMENTS I/O\r\n - INSERT\r\n - POST-PROCESS\r\n ============================================================\r\n INSERT\r\n --------------------------------------------------------- */\r\n /**\r\n * @hidden\r\n */\r\n TreeMap.prototype.insert_by_pair = function (pair) {\r\n var node = this.tree_.find(pair.first);\r\n // IF EQUALS, THEN RETURN FALSE\r\n if (node != null && std.equal_to(node.value.first, pair.first) == true)\r\n return new std.Pair(node.value, false);\r\n // INSERTS\r\n var it;\r\n if (node == null)\r\n it = this.end();\r\n else if (std.less(node.value.first, pair.first) == true)\r\n it = node.value.next();\r\n else\r\n it = node.value;\r\n // ITERATOR TO RETURN\r\n it = this.insert(it, pair);\r\n return new std.Pair(it, true);\r\n };\r\n /* ---------------------------------------------------------\r\n POST-PROCESS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMap.prototype.handle_insert = function (item) {\r\n this.tree_.insert(item);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMap.prototype.handle_erase = function (item) {\r\n this.tree_.erase(item);\r\n };\r\n /* ===============================================================\r\n UTILITIES\r\n =============================================================== */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMap.prototype.swap = function (obj) {\r\n if (obj instanceof TreeMap)\r\n this.swap_tree_map(obj);\r\n else\r\n _super.prototype.swap.call(this, obj);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n TreeMap.prototype.swap_tree_map = function (obj) {\r\n _a = [obj.data_, this.data_], this.data_ = _a[0], obj.data_ = _a[1];\r\n _b = [obj.tree_, this.tree_], this.tree_ = _b[0], obj.tree_ = _b[1];\r\n var _a, _b;\r\n };\r\n return TreeMap;\r\n }(std.base.UniqueMap));\r\n std.TreeMap = TreeMap;\r\n /**\r\n *Tree-structured multiple-key map.
\r\n *\r\n *{@link TreeMultiMap TreeMultiMaps} are associative containers that store elements formed by a combination of\r\n * a key value and a mapped value, following a specific order, and where multiple elements can\r\n * have equivalent keys.
\r\n *\r\n * In a {@link TreeMultiMap}, the key values are generally used to sort and uniquely identify\r\n * the elements, while the mapped values store the content associated to this key. The types of\r\n * key and mapped value may differ, and are grouped together in member type\r\n * value_type, which is a {@link Pair} type combining both:
typedef Pair
Internally, the elements in a {@link TreeMultiMap}are always sorted by its key following a\r\n * strict weak ordering criterion indicated by its internal comparison method (of {@link less}).
\r\n *\r\n *{@link TreeMultiMap}containers are generally slower than {@link HashMap} containers\r\n * to access individual elements by their key, but they allow the direct iteration on subsets based\r\n * on their order.
\r\n *\r\n *{@link TreeMultiMap TreeMultiMaps} are typically implemented as binary search trees.
\r\n *\r\n *Container properties
\r\n *- \r\n *\t
- Associative \r\n *\t
- \r\n *\t\tElements in associative containers are referenced by their key and not by their absolute\r\n *\t\tposition in the\r\n *\t \r\n *\r\n *\t
- Ordered \r\n *\t
- \r\n *\t\tThe elements in the container follow a strict order at all times. All inserted elements are\r\n *\t\tgiven a position in this order.\r\n *\t \r\n *\r\n *\t
- Map \r\n *\t
- \r\n *\t\tEach element associates a key to a mapped value:\r\n *\t\tKeys are meant to identify the elements whose main content is the mapped value.\r\n *\t \r\n *\r\n *\t
- Multiple equivalent keys \r\n *\t
- Multiple elements in the container can have equivalent keys. \r\n *
- \r\n *\t
- Reference: http://www.cplusplus.com/reference/map/multimap/ \r\n *
Return iterator to lower bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container whose key is not considered to\r\n * go before k (i.e., either it is equivalent or goes after).
\r\n *\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(k, element_key) would return false.
\r\n *\r\n *If the {@link TreeMultiMap} class is instantiated with the default comparison type ({@link less}),\r\n * the function returns an iterator to the first element whose key is not less than k
.\r\n *\r\n *A similar member function, {@link upper_bound}, has the same behavior as {@link lower_bound}, except\r\n * in the case that the {@link TreeMultiMap} contains an element with keys equivalent to k:\r\n * In this case, {@link lower_bound} returns an iterator pointing to the first of such elements,\r\n * whereas {@link upper_bound} returns an iterator pointing to the element following the last.
\r\n *\r\n * @param k Key to search for.\r\n *\r\n * @return An iterator to the the first element in the container whose key is not considered to go before\r\n *\t\t k, or {@link TreeMultiMap.end} if all keys are considered to go before k.\r\n */\r\n TreeMultiMap.prototype.lower_bound = function (key) {\r\n var node = this.tree_.find(key);\r\n if (node == null)\r\n return this.end();\r\n else if (std.equal_to(node.value.first, key))\r\n return node.value;\r\n else {\r\n var it = node.value;\r\n while (!std.equal_to(it, this.end()) && std.less(it.first, key))\r\n it = it.next();\r\n return it;\r\n }\r\n };\r\n /**\r\n *Return iterator to upper bound.
\r\n *\r\n *Returns an iterator pointing to the first element in the container whose key is considered to\r\n * go after k
.\r\n *\r\n *The function uses its internal comparison object (key_comp) to determine this, returning an\r\n * iterator to the first element for which key_comp(k, element_key) would return true.
\r\n *\r\n *If the {@link TreeMultiMap} class is instantiated with the default comparison type ({@link less}),\r\n * the function returns an iterator to the first element whose key is greater than k
.\r\n *\r\n *A similar member function, {@link lower_bound}, has the same behavior as {@link upper_bound}, except\r\n * in the case that the {@link TreeMultiMap} contains an element with keys equivalent to k:\r\n * In this case {@link lower_bound} returns an iterator pointing to first of such element, whereas\r\n * {@link upper_bound} returns an iterator pointing to the element following the last.
\r\n *\r\n * @param k Key to search for.\r\n *\r\n * @return An iterator to the the first element in the container whose key is considered to go after\r\n *\t\t k, or {@link TreeMultiMap.end} if no keys are considered to go after k.\r\n */\r\n TreeMultiMap.prototype.upper_bound = function (key) {\r\n var node = this.tree_.find(key);\r\n if (node == null)\r\n return this.end();\r\n else {\r\n var it = node.value;\r\n while (!std.equal_to(it, this.end()) && (std.equal_to(it.first, key) || std.less(it.first, key)))\r\n it = it.next();\r\n return it;\r\n }\r\n };\r\n /**\r\n *Get range of equal elements.
\r\n *\r\n *Returns the bounds of a range that includes all the elements in the container which have a key\r\n * equivalent to k
.\r\n *\r\n *If no matches are found, the range returned has a length of zero, with both iterators pointing to\r\n * the first element that has a key considered to go after k according to the container's internal\r\n * comparison object (key_comp).
\r\n *\r\n *Two keys are considered equivalent if the container's comparison object returns false reflexively\r\n * (i.e., no matter the order in which the keys are passed as arguments).
\r\n *\r\n * @param k Key to search for.\r\n *\r\n * @return The function returns a {@link Pair}, whose member {@link Pair.first} is the lower bound of\r\n *\t\t the range (the same as {@link lower_bound}), and {@link Pair.second} is the upper bound\r\n *\t\t (the same as {@link upper_bound}).\r\n */\r\n TreeMultiMap.prototype.equal_range = function (key) {\r\n return new std.Pair(this.lower_bound(key), this.upper_bound(key));\r\n };\r\n /* =========================================================\r\n ELEMENTS I/O\r\n - INSERT\r\n - POST-PROCESS\r\n ============================================================\r\n INSERT\r\n --------------------------------------------------------- */\r\n /**\r\n * @hidden\r\n */\r\n TreeMultiMap.prototype.insert_by_pair = function (pair) {\r\n var node = this.tree_.find(pair.first);\r\n var it;\r\n if (node == null) {\r\n it = this.end();\r\n }\r\n else if (std.equal_to(node.value.first, pair.first) == true) {\r\n it = node.value.next();\r\n }\r\n else if (std.less(node.value.first, pair.first) == true) {\r\n it = node.value.next();\r\n while (it.equal_to(this.end()) == false && std.less(it.first, pair.first))\r\n it = it.next();\r\n }\r\n else\r\n it = node.value;\r\n // ITERATOR TO RETURN\r\n return this.insert(it, pair);\r\n };\r\n /* ---------------------------------------------------------\r\n POST-PROCESS\r\n --------------------------------------------------------- */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMultiMap.prototype.handle_insert = function (item) {\r\n this.tree_.insert(item);\r\n };\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMultiMap.prototype.handle_erase = function (item) {\r\n this.tree_.erase(item);\r\n };\r\n /* ===============================================================\r\n UTILITIES\r\n =============================================================== */\r\n /**\r\n * @inheritdoc\r\n */\r\n TreeMultiMap.prototype.swap = function (obj) {\r\n if (obj instanceof TreeMultiMap)\r\n this.swap_tree_multimap(obj);\r\n else\r\n _super.prototype.swap.call(this, obj);\r\n };\r\n /**\r\n * @hidden\r\n */\r\n TreeMultiMap.prototype.swap_tree_multimap = function (obj) {\r\n _a = [obj.data_, this.data_], this.data_ = _a[0], obj.data_ = _a[1];\r\n _b = [obj.tree_, this.tree_], this.tree_ = _b[0], obj.tree_ = _b[1];\r\n var _a, _b;\r\n };\r\n return TreeMultiMap;\r\n }(std.base.MultiMap));\r\n std.TreeMultiMap = TreeMultiMap;\r\n})(std || (std = {}));\r\n// Standard Template Library: Algorithms\r\n// The headerApply function to range.
\r\n *\r\n *Applies function fn to each of the elements in the range [first, last).
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n * @param fn Unary function that accepts an element in the range as argument. This can either be a function p\r\n *\t\t\t ointer or a move constructible function object. Its return value, if any, is ignored.\r\n *\r\n * @return Returns fn.\r\n */\r\n function for_each(first, last, fn) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n fn(it.value);\r\n return fn;\r\n }\r\n std.for_each = for_each;\r\n /* ---------------------------------------------------------\r\n AGGREGATE CONDITIONS\r\n --------------------------------------------------------- */\r\n /**\r\n *Test condition on all elements in range.
\r\n *\r\n * Returns true if pred returns true for all the elements in the range\r\n * [first, last) or if the range is {@link IContainer.empty empty}, and false otherwise.\r\n *
boolean. The value returned indicates whether the element fulfills the condition\r\n *\t\t\t checked by this function. The function shall not modify its argument.\r\n *\r\n * @return true if pred returns true for all the elements in the range or if the range is\r\n *\t\t {@link IContainer.empty empty}, and false otherwise.\r\n */\r\n function all_of(first, last, pred) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (pred(it.value) == false)\r\n return false;\r\n return true;\r\n }\r\n std.all_of = all_of;\r\n /**\r\n * Test if any element in range fulfills condition.
\r\n *\r\n * Returns true if pred returns true for any of the elements in the range\r\n * [first, last), and false otherwise.
If [first, last) is an {@link IContainer.empty empty} range, the function returns\r\n * false.
boolean. The value returned indicates whether the element fulfills the condition\r\n *\t\t\t checked by this function. The function shall not modify its argument.\r\n *\r\n * @return true if pred returns true for any of the elements in the range\r\n *\t\t [first, last), and false otherwise. If [first, last) is an\r\n *\t\t {@link IContainer.empty empty} range, the function returns false.\r\n */\r\n function any_of(first, last, pred) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (pred(it.value) == true)\r\n return true;\r\n return false;\r\n }\r\n std.any_of = any_of;\r\n /**\r\n * Test if no elements fulfill condition.
\r\n *\r\n * Returns true if pred returns false for all the elements in the range\r\n * [first, last) or if the range is {@link IContainer.empty empty}, and false otherwise.\r\n *
boolean. The value returned indicates whether the element fulfills the condition\r\n *\t\t\t checked by this function. The function shall not modify its argument.\r\n *\r\n * @return true if pred returns false for all the elements in the range\r\n *\t\t [first, last) or if the range is {@link IContainer.empty empty}, and false\r\n *\t\t otherwise.\r\n */\r\n function none_of(first, last, pred) {\r\n return !any_of(first, last, pred);\r\n }\r\n std.none_of = none_of;\r\n function equal(first1, last1, first2, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n while (!first1.equal_to(last1))\r\n if (first2.equal_to(first2.get_source().end()) || !pred(first1.value, first2.value))\r\n return false;\r\n else {\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n }\r\n return true;\r\n }\r\n std.equal = equal;\r\n function is_permutation(first1, last1, first2, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n // find the mismatched\r\n var pair = mismatch(first1, last1, first2);\r\n first1 = pair.first;\r\n first2 = pair.second;\r\n if (first1.equal_to(last1))\r\n return true;\r\n var last2 = first2.advance(std.distance(first1, last1));\r\n for (var it = first1; !it.equal_to(last1); it = it.next())\r\n if (find(first1, it, it.value).equal_to(it)) {\r\n var n = count(first2, last2, it.value);\r\n if (n == 0 || count(it, last1, it.value) != n)\r\n return false;\r\n }\r\n return true;\r\n }\r\n std.is_permutation = is_permutation;\r\n function lexicographical_compare(first1, last1, first2, last2, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n while (!first1.equal_to(last1))\r\n if (first2.equal_to(last2) || !compare(first1.value, first2.value))\r\n return false;\r\n else if (compare(first1.value, first2.value))\r\n return true;\r\n else {\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n }\r\n return !std.equal_to(last2, last2.get_source().end()) && !std.equal_to(first2.value, last2.value);\r\n }\r\n std.lexicographical_compare = lexicographical_compare;\r\n /* ---------------------------------------------------------\r\n FINDERS\r\n --------------------------------------------------------- */\r\n /**\r\n * Find value in range.
\r\n *\r\n *Returns an iterator to the first element in the range [first, last) that compares equal to\r\n * val. If no such element is found, the function returns last.
\r\n *\r\n *The function uses {@link equal_to equal_to} to compare the individual elements to val.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n * @param val Value to search for in the range.\r\n *\r\n * @return An {@link Iterator} to the first element in the range that compares equal to val. If no elements\r\n *\t\t match, the function returns last.\r\n */\r\n function find(first, last, val) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (std.equal_to(it.value, val))\r\n return it;\r\n return last;\r\n }\r\n std.find = find;\r\n /**\r\n *Find element in range.
\r\n *\r\n * Returns an iterator to the first element in the range [first, last) for which pred returns\r\n * true. If no such element is found, the function returns last.
bool. The value returned indicates whether the element is considered a match in\r\n *\t\t\t the context of this function. The function shall not modify its argument.\r\n *\r\n * @return An {@link Iterator} to the first element in the range for which pred does not return\r\n *\t\t false. If pred is false for all elements, the function returns\r\n *\t\t last.\r\n */\r\n function find_if(first, last, pred) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (pred(it.value))\r\n return it;\r\n return last;\r\n }\r\n std.find_if = find_if;\r\n /**\r\n * Find element in range.
\r\n *\r\n * Returns an iterator to the first element in the range [first, last) for which pred returns\r\n * true. If no such element is found, the function returns last.
bool. The value returned indicates whether the element is considered a match in\r\n *\t\t\t the context of this function. The function shall not modify its argument.\r\n *\r\n * @return An {@link Iterator} to the first element in the range for which pred returns false.\r\n *\t\t If pred is true for all elements, the function returns last.\r\n */\r\n function find_if_not(first, last, pred) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (pred(it.value) == false)\r\n return it;\r\n return last;\r\n }\r\n std.find_if_not = find_if_not;\r\n function find_end(first1, last1, first2, last2, compare) {\r\n if (compare === void 0) { compare = std.equal_to; }\r\n if (first2.equal_to(last2))\r\n return last1;\r\n var ret = last1;\r\n for (; !first1.equal_to(last1); first1 = first1.next()) {\r\n var it1 = first1;\r\n var it2 = first2;\r\n while (std.equal_to(it1.value, it2.value)) {\r\n it1 = it1.next();\r\n it2 = it2.next();\r\n if (it2.equal_to(last2)) {\r\n ret = first1;\r\n break;\r\n }\r\n else if (it1.equal_to(last1))\r\n return ret;\r\n }\r\n }\r\n return ret;\r\n }\r\n std.find_end = find_end;\r\n function find_first_of(first1, last1, first2, last2, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n for (; !first1.equal_to(last1); first1 = first1.next())\r\n for (var it = first2; !it.equal_to(last2); it = it.next())\r\n if (pred(it.value, first1.value))\r\n return first1;\r\n return last1;\r\n }\r\n std.find_first_of = find_first_of;\r\n function adjacent_find(first, last, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n if (!first.equal_to(last)) {\r\n var next = first.next();\r\n while (!next.equal_to(last)) {\r\n if (std.equal_to(first.value, last.value))\r\n return first;\r\n first = first.next();\r\n next = next.next();\r\n }\r\n }\r\n return last;\r\n }\r\n std.adjacent_find = adjacent_find;\r\n function search(first1, last1, first2, last2, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n if (first2.equal_to(last2))\r\n return first1;\r\n for (; !first1.equal_to(last1); first1 = first1.next()) {\r\n var it1 = first1;\r\n var it2 = first2;\r\n while (std.equal_to(it1.value, it2.value)) {\r\n it1 = it1.next();\r\n it2 = it2.next();\r\n if (it2.equal_to(last2))\r\n return first1;\r\n else if (it1.equal_to(last1))\r\n return last1;\r\n }\r\n }\r\n return last1;\r\n }\r\n std.search = search;\r\n function search_n(first, last, count, val, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n var limit = first.advance(std.distance(first, last) - count);\r\n for (; !first.equal_to(limit); first = first.next()) {\r\n var it = first;\r\n var i = 0;\r\n while (std.equal_to(it.value, val)) {\r\n it = it.next();\r\n if (++i == count)\r\n return first;\r\n }\r\n }\r\n return last;\r\n }\r\n std.search_n = search_n;\r\n function mismatch(first1, last1, first2, compare) {\r\n if (compare === void 0) { compare = std.equal_to; }\r\n while (!first1.equal_to(last1) && !first2.equal_to(first2.get_source().end())\r\n && std.equal_to(first1.value, first2.value)) {\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n }\r\n return std.make_pair(first1, first2);\r\n }\r\n std.mismatch = mismatch;\r\n /* ---------------------------------------------------------\r\n COUNTERS\r\n --------------------------------------------------------- */\r\n /**\r\n * Count appearances of value in range.
\r\n *\r\n *Returns the number of elements in the range [first, last) that compare equal to val.
\r\n *\r\n *The function uses {@link equal_to} to compare the individual elements to val.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n * @param val Value to match.\r\n *\r\n * @return The number of elements in the range [first, last) that compare equal to val.\r\n */\r\n function count(first, last, val) {\r\n var cnt = 0;\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (std.equal_to(it.value, val))\r\n cnt++;\r\n return cnt;\r\n }\r\n std.count = count;\r\n /**\r\n *Return number of elements in range satisfying condition.
\r\n *\r\n * Returns the number of elements in the range [first, last) for which pred is true.\r\n *
bool. The value returned indicates whether the element is counted by this function.\r\n *\t\t\t The function shall not modify its argument. This can either be a function pointer or a function\r\n *\t\t\t object.\r\n */\r\n function count_if(first, last, pred) {\r\n var cnt = 0;\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (pred(it.value))\r\n cnt++;\r\n return cnt;\r\n }\r\n std.count_if = count_if;\r\n /* =========================================================\r\n MODIFIERS (MODIFYING SEQUENCE)\r\n - FILL\r\n - REMOVE\r\n - REPLACE & SWAP\r\n - RE-ARRANGEMENT\r\n ============================================================\r\n FILL\r\n --------------------------------------------------------- */\r\n /**\r\n * Copy range of elements.
\r\n *\r\n *Copies the elements in the range [first, last) into the range beginning at result.
\r\n *\r\n *The function returns an iterator to the end of the destination range (which points to the element following the\r\n * last element copied).
\r\n *\r\n *The ranges shall not overlap in such a way that result points to an element in the range\r\n * [first, last). For such cases, see {@link copy_backward}.
\r\n *\r\n * @param first {@link Iterator Input iterator} to the initial position in a sequence to be copied.\r\n * @param last {@link Iterator Input iterator} to the initial position in a sequence to be copied. The range used is\r\n *\t\t\t [first, last), which contains all the elements between first and last,\r\n *\t\t\t including the element pointed by first but not the element pointed by last.\r\n * @param result {@link Iterator Output iterator} to the initial position in the destination sequence. This shall not\r\n *\t\t\t\t point to any element in the range [first, last).\r\n *\r\n * @return An iterator to the end of the destination range where elements have been copied.\r\n */\r\n function copy(first, last, result) {\r\n for (; !first.equal_to(last); first = first.next()) {\r\n result.value = first.value;\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.copy = copy;\r\n /**\r\n *Copy elements.
\r\n *\r\n *Copies the first n elements from the range beginning at first into the range beginning at\r\n * result.
\r\n *\r\n *The function returns an iterator to the end of the destination range (which points to one past the last element\r\n * copied).
\r\n *\r\n *If n is negative, the function does nothing.
\r\n *\r\n *If the ranges overlap, some of the elements in the range pointed by result may have undefined but valid values.\r\n *
\r\n *\r\n * @param first {@link Iterator Input iterator} to the initial position in a sequence of at least n elements to\r\n *\t\t\t\tbe copied. InputIterator shall point to a type assignable to the elements pointed by\r\n *\t\t\t\tOutputIterator.\r\n * @param n Number of elements to copy. If this value is negative, the function does nothing.\r\n * @param result {@link Iterator Output iterator} to the initial position in the destination sequence of at least\r\n *\t\t\t\t n elements. This shall not point to any element in the range [first, last].\r\n *\r\n * @return An iterator to the end of the destination range where elements have been copied.\r\n */\r\n function copy_n(first, n, result) {\r\n for (var i = 0; i < n; i++) {\r\n result.value = first.value;\r\n first = first.next();\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.copy_n = copy_n;\r\n /**\r\n *Copy certain elements of range.
\r\n *\r\n * Copies the elements in the range [first, last) for which pred returns true to the\r\n * range beginning at result.
bool. The value returned indicates whether the element is to be copied (if\r\n *\t\t\t true, it is copied). The function shall not modify any of its arguments.\r\n *\r\n * @return An iterator to the end of the destination range where elements have been copied.\r\n */\r\n function copy_if(first, last, result, pred) {\r\n for (; !first.equal_to(last); first = first.next()) {\r\n if (!pred(first.value))\r\n continue;\r\n result.value = first.value;\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.copy_if = copy_if;\r\n /**\r\n * Copy range of elements backward.
\r\n *\r\n *Copies the elements in the range [first, last) starting from the end into the range terminating\r\n * at result.
\r\n *\r\n *The function returns an iterator to the first element in the destination range.
\r\n *\r\n *The resulting range has the elements in the exact same order as [first, last). To reverse their\r\n * order, see {@link reverse_copy}.
\r\n *\r\n * The function begins by copying *(last-1) into *(result-1), and then follows backward\r\n * by the elements preceding these, until first is reached (and including it).
The ranges shall not overlap in such a way that result (which is the past-the-end element in the\r\n * destination range) points to an element in the range (first,last]. For such cases, see {@link copy}.
\r\n *\r\n * @param first {@link Iterator Bidirectional iterator} to the initial position in a sequence to be copied.\r\n * @param last {@link Iterator Bidirectional iterator} to the initial position in a sequence to be copied. The range\r\n *\t\t\t used is [first, last), which contains all the elements between first and\r\n *\t\t\t last, including the element pointed by first but not the element pointed by last.\r\n * @param result {@link Iterator Bidirectional iterator} to the initial position in the destination sequence. This\r\n *\t\t\t\t shall not point to any element in the range [first, last).\r\n *\r\n * @return An iterator to the first element of the destination sequence where elements have been copied.\r\n */\r\n function copy_backward(first, last, result) {\r\n last = last.prev();\r\n for (; !last.equal_to(first); last = last.prev()) {\r\n result.value = last.value;\r\n result = result.prev();\r\n }\r\n return result;\r\n }\r\n std.copy_backward = copy_backward;\r\n /**\r\n *Fill range with value.
\r\n *\r\n *Assigns val to all the elements in the range [first, last).
\r\n *\r\n * @param first {@link Iterator Forward iterator} to the initial position in a sequence of elements that support being\r\n *\t\t\t\tassigned a value of type T.\r\n * @param last {@link Iterator Forward iterator} to the final position in a sequence of elements that support being\r\n *\t\t\t\tassigned a value of type T.. The range filled is [first, last), which contains\r\n *\t\t\t\tall the elements between first and last, including the element pointed by first\r\n *\t\t\t\tbut not the element pointed by last.\r\n * @param val Value to assign to the elements in the filled range.\r\n */\r\n function fill(first, last, val) {\r\n for (; !first.equal_to(last); first = first.next())\r\n first.value = val;\r\n }\r\n std.fill = fill;\r\n /**\r\n *Fill sequence with value.
\r\n *\r\n *Assigns val to the first n elements of the sequence pointed by first.
\r\n *\r\n * @param first {@link Iterator Output iterator} to the initial position in a sequence of elements that support being\r\n *\t\t\t\tassigned a value of type T.\r\n * @param n Number of elements to fill. If negative, the function does nothing.\r\n * @param val Value to be used to fill the range.\r\n *\r\n * @return An iterator pointing to the element that follows the last element filled.\r\n */\r\n function fill_n(first, n, val) {\r\n for (var i = 0; i < n; i++) {\r\n first.value = val;\r\n first = first.next();\r\n }\r\n return first;\r\n }\r\n std.fill_n = fill_n;\r\n function transform() {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n if (args.length == 4)\r\n return unary_transform.apply(null, args);\r\n else\r\n return binary_transform.apply(null, args);\r\n }\r\n std.transform = transform;\r\n /**\r\n * @hidden\r\n */\r\n function unary_transform(first, last, result, op) {\r\n for (; !first.equal_to(last); first = first.next()) {\r\n result.value = op(first.value);\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n /**\r\n * @hidden\r\n */\r\n function binary_transform(first1, last1, first2, result, binary_op) {\r\n while (!first1.equal_to(last1)) {\r\n result.value = binary_op(first1.value, first2.value);\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n /**\r\n *Generate values for range with function.
\r\n *\r\n *Assigns the value returned by successive calls to gen to the elements in the range [first, last).\r\n *
\r\n *\r\n * @param first {@link Iterator Forward iterator} to the initial position in a sequence.\r\n * @param last {@link Iterator Forward iterator} to the final position in a sequence. The range affected is\r\n *\t\t\t [first, last), which contains all the elements between first and last,\r\n *\t\t\t including the element pointed by first but not the element pointed by last.\r\n * @param gen Generator function that is called with no arguments and returns some value of a type convertible to\r\n *\t\t\t those pointed by the iterators.\r\n */\r\n function generate(first, last, gen) {\r\n for (; !first.equal_to(last); first = first.next())\r\n first.value = gen();\r\n }\r\n std.generate = generate;\r\n /**\r\n *Generate values for sequence with function.
\r\n *\r\n *Assigns the value returned by successive calls to gen to the first n elements of the sequence\r\n * pointed by first.
\r\n *\r\n * @param first {@link Iterator Output iterator} to the initial position in a sequence of at least n elements\r\n *\t\t\t\tthat support being assigned a value of the type returned by gen.\r\n * @param n Number of values to generate. If negative, the function does nothing.\r\n * @param gen Generator function that is called with no arguments and returns some value of a type convertible to\r\n *\t\t\t those pointed by the iterators.\r\n *\r\n * @return An iterator pointing to the element that follows the last element whose value has been generated.\r\n */\r\n function generate_n(first, n, gen) {\r\n for (var i = 0; i < n; i++) {\r\n first.value = gen();\r\n first = first.next();\r\n }\r\n return first;\r\n }\r\n std.generate_n = generate_n;\r\n function unique(first, last, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n var ret = first;\r\n for (var it = first.next(); !it.equal_to(last);) {\r\n if (std.equal_to(it.value, it.prev().value) == true)\r\n it = it.get_source().erase(it);\r\n else {\r\n ret = it;\r\n it = it.next();\r\n }\r\n }\r\n return ret;\r\n }\r\n std.unique = unique;\r\n function unique_copy(first, last, result, pred) {\r\n if (pred === void 0) { pred = std.equal_to; }\r\n if (first.equal_to(last))\r\n return result;\r\n result.value = first.value;\r\n first = first.next();\r\n for (; !first.equal_to(last); first = first.next())\r\n if (!pred(first.value, result.value)) {\r\n result = result.next();\r\n result.value = first.value;\r\n }\r\n return result;\r\n }\r\n std.unique_copy = unique_copy;\r\n /**\r\n *Remove value from range.
\r\n *\r\n *Transforms the range [first, last) into a range with all the elements that compare equal to\r\n * val removed, and returns an iterator to the new last of that range.
\r\n *\r\n *The function cannot alter the properties of the object containing the range of elements (i.e., it cannot alter\r\n * the size of an array or a container): The removal is done by replacing the elements that compare equal to\r\n * val by the next element that does not, and signaling the new size of the shortened range by returning an\r\n * iterator to the element that should be considered its new past-the-last element.
\r\n *\r\n *The relative order of the elements not removed is preserved, while the elements between the returned iterator\r\n * and last are left in a valid but unspecified state.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n * @param val Value to be removed.\r\n */\r\n function remove(first, last, val) {\r\n var ret = last;\r\n for (var it = first; !it.equal_to(last);) {\r\n if (std.equal_to(it.value, val) == true)\r\n it = it.get_source().erase(it);\r\n else {\r\n ret = it;\r\n it = it.next();\r\n }\r\n }\r\n return ret;\r\n }\r\n std.remove = remove;\r\n /**\r\n *Remove elements from range.
\r\n *\r\n * Transforms the range [first, last) into a range with all the elements for which pred returns\r\n * true removed, and returns an iterator to the new last of that range.
The function cannot alter the properties of the object containing the range of elements (i.e., it cannot\r\n * alter the size of an array or a container): The removal is done by replacing the elements for which pred returns\r\n * true by the next element for which it does not, and signaling the new size of the shortened range\r\n * by returning an iterator to the element that should be considered its new past-the-last element.
The relative order of the elements not removed is preserved, while the elements between the returned\r\n * iterator and last are left in a valid but unspecified state.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n * @param pred Unary function that accepts an element in the range as argument, and returns a value convertible to\r\n *\t\t\tbool. The value returned indicates whether the element is to be removed (if\r\n *\t\t\t true, it is removed). The function shall not modify its argument.\r\n */\r\n function remove_if(first, last, pred) {\r\n var ret = last;\r\n for (var it = first; !it.equal_to(last);) {\r\n if (pred(it.value) == true)\r\n it = it.get_source().erase(it);\r\n else {\r\n ret = it;\r\n it = it.next();\r\n }\r\n }\r\n return ret;\r\n }\r\n std.remove_if = remove_if;\r\n /**\r\n * Copy range removing value.
\r\n *\r\n *Copies the elements in the range [first, last) to the range beginning at result, except\r\n * those elements that compare equal to val.
\r\n *\r\n *The resulting range is shorter than [first, last) by as many elements as matches in the sequence,\r\n * which are \"removed\".
\r\n *\r\n *The function uses {@link equal_to} to compare the individual elements to val.
\r\n *\r\n * @param first {@link Iterator InputIterator} to the initial position in a sequence.\r\n * @param last {@link Iterator InputIterator} to the final position in a sequence. The range used is\r\n *\t\t\t [first, last), which contains all the elements between first and last,\r\n *\t\t\t including the element pointed by first but not the element pointed by last.\r\n * @param result {@link Iterator Output iterator} to the initial position of the range where the resulting sequence is\r\n *\t\t\t\t stored. The pointed type shall support being assigned the value of an element in the range\r\n *\t\t\t\t [first, last).\r\n * @param val Value to be removed.\r\n *\r\n * @return An iterator pointing to the end of the copied range, which includes all the elements in\r\n *\t\t [first, last) except those that compare equal to val.\r\n */\r\n function remove_copy(first, last, result, val) {\r\n for (; !first.equal_to(last); first = first.next()) {\r\n if (std.equal_to(first.value, val))\r\n continue;\r\n result.value = first.value;\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.remove_copy = remove_copy;\r\n /**\r\n *Copy range removing values.
\r\n *\r\n * Copies the elements in the range [first, last) to the range beginning at result, except\r\n * those elements for which pred returns true.
The resulting range is shorter than [first, last) by as many elements as matches, which are\r\n * \"removed\".
\r\n *\r\n * @param first {@link Iterator InputIterator} to the initial position in a sequence.\r\n * @param last {@link Iterator InputIterator} to the final position in a sequence. The range used is\r\n *\t\t\t [first, last), which contains all the elements between first and last,\r\n *\t\t\t including the element pointed by first but not the element pointed by last.\r\n * @param result {@link Iterator Output iterator} to the initial position of the range where the resulting sequence is\r\n *\t\t\t\t stored. The pointed type shall support being assigned the value of an element in the range\r\n *\t\t\t\t [first, last).\r\n * @param pred Unary function that accepts an element in the range as argument, and returns a value convertible to\r\n *\t\t\tbool. The value returned indicates whether the element is to be removed from the copy (if\r\n *\t\t\t true, it is not copied). The function shall not modify its argument.\r\n *\r\n * @return An iterator pointing to the end of the copied range, which includes all the elements in\r\n *\t\t [first, last) except those for which pred returns true.\r\n */\r\n function remove_copy_if(first, last, result, pred) {\r\n for (; !first.equal_to(last); first = first.next()) {\r\n if (pred(first.value))\r\n continue;\r\n result.value = first.value;\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.remove_copy_if = remove_copy_if;\r\n /* ---------------------------------------------------------\r\n REPLACE & SWAP\r\n --------------------------------------------------------- */\r\n /**\r\n * Replace value in range.
\r\n *\r\n *Assigns new_val to all the elements in the range [first, last) that compare equal to\r\n * old_val.
\r\n *\r\n *The function uses {@link equal_to} to compare the individual elements to old_val.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n * @param old_val Value to be replaced.\r\n * @param new_val Replacement value.\r\n */\r\n function replace(first, last, old_val, new_val) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (std.equal_to(it.value, old_val))\r\n it.value = new_val;\r\n }\r\n std.replace = replace;\r\n /**\r\n *Replace value in range.
\r\n *\r\n * Assigns new_val to all the elements in the range [first, last) for which pred returns\r\n * true.
bool. The value returned indicates whether the element is to be replaced (if\r\n *\t\t\t true, it is replaced). The function shall not modify its argument.\r\n * @param new_val Value to assign to replaced elements.\r\n */\r\n function replace_if(first, last, pred, new_val) {\r\n for (var it = first; !it.equal_to(last); it = it.next())\r\n if (pred(it.value) == true)\r\n it.value = new_val;\r\n }\r\n std.replace_if = replace_if;\r\n /**\r\n * Copy range replacing value.
\r\n *\r\n *Copies the elements in the range [first, last) to the range beginning at result, replacing\r\n * the appearances of old_value by new_value.
\r\n *\r\n *The function uses {@link std.equal_to} to compare the individual elements to old_value.
\r\n *\r\n *The ranges shall not overlap in such a way that result points to an element in the range\r\n * [first, last).
\r\n *\r\n * @param first {@link Iterator InputIterator} to the initial position in a sequence.\r\n * @param last {@link Iterator InputIterator} to the final position in a sequence. The range used is\r\n *\t\t\t [first, last), which contains all the elements between first and last,\r\n *\t\t\t including the element pointed by first but not the element pointed by last.\r\n * @param result {@link Iterator Output iterator} to the initial position of the range where the resulting sequence is\r\n *\t\t\t\t stored. The pointed type shall support being assigned the value of an element in the range\r\n *\t\t\t\t [first, last).\r\n * @param old_val Value to be replaced.\r\n * @param new_val Replacement value.\r\n *\r\n * @return An iterator pointing to the element that follows the last element written in the result sequence.\r\n */\r\n function replace_copy(first, last, result, old_val, new_val) {\r\n for (; !first.equal_to(last); first = first.next()) {\r\n if (std.equal_to(first.value, old_val))\r\n result.value = new_val;\r\n else\r\n result.value = first.value;\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.replace_copy = replace_copy;\r\n /**\r\n *Copy range replacing value.
\r\n *\r\n * Copies the elements in the range [first, last) to the range beginning at result, replacing\r\n * those for which pred returns true by new_value.
bool. The value returned indicates whether the element is to be removed from the copy (if\r\n *\t\t\t true, it is not copied). The function shall not modify its argument.\r\n * @param new_val Value to assign to replaced values.\r\n *\r\n * @return An iterator pointing to the element that follows the last element written in the result sequence.\r\n */\r\n function replace_copy_if(first, last, result, pred, new_val) {\r\n for (; !first.equal_to(last); first = first.next()) {\r\n if (pred(first.value))\r\n result.value = new_val;\r\n else\r\n result.value = first.value;\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.replace_copy_if = replace_copy_if;\r\n /**\r\n * Exchange values of objects pointed to by two iterators.
\r\n *\r\n *Swaps the elements pointed to by x and y.
\r\n *\r\n *The function calls {@link Iterator.swap} to exchange the elements.
\r\n *\r\n * @param x {@link Iterator Forward iterator} to the objects to swap.\r\n * @param y {@link Iterator Forward iterator} to the objects to swap.\r\n */\r\n function iter_swap(x, y) {\r\n x.swap(y);\r\n }\r\n std.iter_swap = iter_swap;\r\n /**\r\n *Exchange values of two ranges.
\r\n *\r\n *Exchanges the values of each of the elements in the range [first1, last1) with those of their\r\n * respective elements in the range beginning at first2.
\r\n *\r\n *The function calls {@link Iterator.swap} to exchange the elements.
\r\n *\r\n * @param first1 {@link Iterator Forward iterator} to the initial position of the first sequence.\r\n * @param last1 {@link Iterator Forward iterator} to the final position of the first sequence. The range used is\r\n *\t\t\t\t[first1, last1), including the element pointed by first1, but not the element\r\n *\t\t\t\tpointed by last1.\r\n * @param first2 {@link Iterator Forward iterator} to the initial position of the second range. The range includes as\r\n *\t\t\t\t many elements as [first1, last1). The two ranges shall not overlap.\r\n *\r\n * @return An iterator to the last element swapped in the second sequence.\r\n */\r\n function swap_ranges(first1, last1, first2) {\r\n for (; !first1.equal_to(last1); first1 = first1.next()) {\r\n first1.swap(first2);\r\n first2 = first2.next();\r\n }\r\n return first2;\r\n }\r\n std.swap_ranges = swap_ranges;\r\n /* ---------------------------------------------------------\r\n RE-ARRANGEMENT\r\n --------------------------------------------------------- */\r\n /**\r\n *Reverse range.
\r\n *\r\n *Reverses the order of the elements in the range [first, last).
\r\n *\r\n *The function calls {@link iter_swap} to swap the elements to their new locations.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n */\r\n function reverse(first, last) {\r\n // first != last && first != --last\r\n while (first.equal_to(last) == false && !first.equal_to((last = last.prev())) == false) {\r\n first.swap(last);\r\n first = first.next();\r\n }\r\n }\r\n std.reverse = reverse;\r\n /**\r\n *Copy range reversed.
\r\n *\r\n *Copies the elements in the range [first, last) to the range beginning at result, but in\r\n * reverse order.
\r\n *\r\n * @param first {@link Iterator Bidirectional iterator} to the initial position in a sequence to be copied.\r\n * @param last {@link Iterator Bidirectional iterator} to the initial position in a sequence to be copied. The range\r\n *\t\t\t used is [first, last), which contains all the elements between first and\r\n *\t\t\t last, including the element pointed by first but not the element pointed by last.\r\n * @param result {@link Iterator Output iterator} to the initial position of the range where the reserved range is\r\n *\t\t\t\t stored. The pointed type shall support being assigned the value of an element in the range\r\n *\t\t\t\t [first, last).\r\n *\r\n * @return An output iterator pointing to the end of the copied range, which contains the same elements in reverse\r\n *\t\t order.\r\n */\r\n function reverse_copy(first, last, result) {\r\n while (!last.equal_to(first)) {\r\n last = last.prev();\r\n result.value = last.value;\r\n result = result.next();\r\n }\r\n return result;\r\n }\r\n std.reverse_copy = reverse_copy;\r\n /**\r\n *Rotate left the elements in range.
\r\n *\r\n *Rotates the order of the elements in the range [first, last), in such a way that the element\r\n * pointed by middle becomes the new first element.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param middle An {@link Iterator} pointing to the element within the range [first, last) that is\r\n *\t\t\t\t moved to the first position in the range.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n *\r\n * @return An iterator pointing to the element that now contains the value previously pointed by first.\r\n */\r\n function rotate(first, middle, last) {\r\n var next = middle;\r\n while (next.equal_to(last) == false) {\r\n first.swap(next);\r\n first = first.next();\r\n next = next.next();\r\n if (first.equal_to(middle))\r\n break;\r\n }\r\n return first;\r\n }\r\n std.rotate = rotate;\r\n /**\r\n *Copy range rotated left.
\r\n *\r\n *Copies the elements in the range [first, last) to the range beginning at result, but\r\n * rotating the order of the elements in such a way that the element pointed by middle becomes the first\r\n * element in the resulting range.
\r\n *\r\n * @param first {@link Iterator Forward iterator} to the initial position of the range to be copy-rotated.\r\n * @param middle Forward iterator pointing to the element within the range [first, last) that is copied as the first element in the resulting range.\r\n * @param last {@link Iterator Forward iterator} to the final positions of the range to be copy-rotated. The range\r\n *\t\t\t used is [first, last), which contains all the elements between first and\r\n *\t\t\t last, including the element pointed by first but not the element pointed by last.\r\n *\t\t\t Notice that in this function, these are not consecutive parameters, but the first and third ones.\r\n * @param result {@link Iterator Output iterator} to the initial position of the range where the reserved range is\r\n *\t\t\t\t stored. The pointed type shall support being assigned the value of an element in the range\r\n *\t\t\t\t [first, last).\r\n *\r\n * @return An output iterator pointing to the end of the copied range.\r\n */\r\n function rotate_copy(first, middle, last, result) {\r\n result = copy(middle, last, result);\r\n return copy(first, middle, result);\r\n }\r\n std.rotate_copy = rotate_copy;\r\n /**\r\n *Randomly rearrange elements in range.
\r\n *\r\n *Rearranges the elements in the range [first, last) randomly.
\r\n *\r\n *The function swaps the value of each element with that of some other randomly picked element. When provided,\r\n * the function gen determines which element is picked in every case. Otherwise, the function uses some unspecified\r\n * source of randomness.
\r\n *\r\n *To specify a uniform random generator, see {@link shuffle}.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n */\r\n function random_shuffle(first, last) {\r\n return std.shuffle(first, last);\r\n }\r\n std.random_shuffle = random_shuffle;\r\n /**\r\n *Randomly rearrange elements in range using generator.
\r\n *\r\n *Rearranges the elements in the range [first, last) randomly, using g as uniform random\r\n * number generator.
\r\n *\r\n *The function swaps the value of each element with that of some other randomly picked element. The function\r\n * determines the element picked by calling g().
\r\n *\r\n *To shuffle the elements of the range without such a generator, see {@link random_shuffle} instead.
\r\n *\r\n *Note
\r\n *Using random generator engine is not implemented yet.
\r\n *\r\n * @param first An {@link Iterator} to the initial position in a sequence.\r\n * @param last An {@link Iterator} to the final position in a sequence. The range used is [first, last),\r\n *\t\t\t which contains all the elements between first and last, including the element pointed by\r\n *\t\t\t first but not the element pointed by last.\r\n */\r\n function shuffle(first, last) {\r\n for (var it = first; !it.equal_to(last); it = it.next()) {\r\n var rand_index = Math.floor(Math.random() * (last.index - first.index));\r\n it.swap(first.advance(rand_index));\r\n }\r\n }\r\n std.shuffle = shuffle;\r\n function sort(first, last, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n qsort(first.get_source(), first.index, last.index, compare);\r\n }\r\n std.sort = sort;\r\n function partial_sort(first, middle, last, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n selection_sort(first.get_source(), first.index, middle.index, last.index, compare);\r\n }\r\n std.partial_sort = partial_sort;\r\n function partial_sort_copy(first, last, result_first, result_last, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n var input_size = std.distance(first, last);\r\n var result_size = std.distance(result_first, result_last);\r\n var vector = new std.Vector(first, last);\r\n sort(vector.begin(), vector.end());\r\n if (input_size > result_size)\r\n result_first = copy(vector.begin(), vector.begin().advance(result_size), result_first);\r\n else\r\n result_first = copy(vector.begin(), vector.end(), result_first);\r\n return result_first;\r\n }\r\n std.partial_sort_copy = partial_sort_copy;\r\n function is_sorted(first, last, compare) {\r\n if (compare === void 0) { compare = std.equal_to; }\r\n if (first.equal_to(last))\r\n return true;\r\n for (var next = first.next(); !next.equal_to(last); next = next.next()) {\r\n if (std.less(next.value, first.value))\r\n return false;\r\n first = first.next();\r\n }\r\n return true;\r\n }\r\n std.is_sorted = is_sorted;\r\n function is_sorted_until(first, last, compare) {\r\n if (compare === void 0) { compare = std.equal_to; }\r\n if (first.equal_to(last))\r\n return first;\r\n for (var next = first.next(); !next.equal_to(last); next = next.next()) {\r\n if (std.less(next.value, first.value))\r\n return next;\r\n first = first.next();\r\n }\r\n return last;\r\n }\r\n std.is_sorted_until = is_sorted_until;\r\n /* ---------------------------------------------------------\r\n BACKGROUND\r\n --------------------------------------------------------- */\r\n /**\r\n * @hidden\r\n */\r\n function qsort(container, first, last, compare) {\r\n if (first > last)\r\n _a = [last, first], first = _a[0], last = _a[1];\r\n if (last == -1)\r\n last = container.size();\r\n var index = qsort_partition(container, first, last, compare);\r\n qsort(container, first, index, compare);\r\n qsort(container, index, last, compare);\r\n var _a;\r\n }\r\n /**\r\n * @hidden\r\n */\r\n function qsort_partition(container, first, last, compare) {\r\n var val = container.at(first);\r\n var i = first;\r\n var j = last;\r\n while (true) {\r\n while (compare(container.at(++i), val))\r\n if (i == last - 1)\r\n break;\r\n while (compare(val, container.at(--j)))\r\n if (j == first)\r\n break;\r\n if (i >= j)\r\n break;\r\n // SWAP; AT(I) WITH AT(J)\r\n var supplement_1 = container.at(i);\r\n container.set(i, container.at(j));\r\n container.set(j, supplement_1);\r\n }\r\n // SWAP; AT(BEGIN) WITH AT(J)\r\n var supplement = container.at(first);\r\n container.set(first, container.at(j));\r\n container.set(j, supplement);\r\n return j;\r\n }\r\n /**\r\n * @hidden\r\n */\r\n function stable_qsort(container, first, last, compare) {\r\n // QUICK SORT\r\n if (first > last)\r\n _a = [last, first], first = _a[0], last = _a[1];\r\n var index = stable_qsort_partition(container, first, last, compare);\r\n stable_qsort(container, first, index, compare);\r\n stable_qsort(container, index, last, compare);\r\n var _a;\r\n }\r\n /**\r\n * @hidden\r\n */\r\n function stable_qsort_partition(container, first, last, compare) {\r\n var val = container.at(first);\r\n var i = first;\r\n var j = last;\r\n while (true) {\r\n while (!std.equal_to(container.at(++i), val) && compare(container.at(i), val))\r\n if (i == last - 1)\r\n break;\r\n while (!std.equal_to(val, container.at(--j)) && compare(val, container.at(j)))\r\n if (j == first)\r\n break;\r\n if (i >= j)\r\n break;\r\n // SWAP; AT(I) WITH AT(J)\r\n var supplement_2 = container.at(i);\r\n container.set(i, container.at(j));\r\n container.set(j, supplement_2);\r\n }\r\n // SWAP; AT(BEGIN) WITH AT(J)\r\n var supplement = container.at(first);\r\n container.set(first, container.at(j));\r\n container.set(j, supplement);\r\n return j;\r\n }\r\n /**\r\n * @hidden\r\n */\r\n function selection_sort(container, first, middle, last, compare) {\r\n if (last == -1)\r\n last = container.size();\r\n for (var i = first; i < middle; i++) {\r\n var min_index = i;\r\n for (var j = i + 1; j < last; j++)\r\n if (compare(container.at(j), container.at(min_index)))\r\n min_index = j;\r\n if (i != min_index) {\r\n var supplement = container.at(i);\r\n container.set(i, container.at(min_index));\r\n container.set(min_index, supplement);\r\n }\r\n }\r\n }\r\n function lower_bound(first, last, val, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n var count = std.distance(first, last);\r\n while (count > 0) {\r\n var step = Math.floor(count / 2);\r\n var it = first.advance(step);\r\n if (!compare(it.value, val)) {\r\n first = it.next();\r\n count -= step + 1;\r\n }\r\n else\r\n count = step;\r\n }\r\n return first;\r\n }\r\n std.lower_bound = lower_bound;\r\n function upper_bound(first, last, val, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n var count = std.distance(first, last);\r\n while (count > 0) {\r\n var step = Math.floor(count / 2);\r\n var it = first.advance(step);\r\n if (!compare(val, it.value)) {\r\n first = it.next();\r\n count -= step + 1;\r\n }\r\n else\r\n count = step;\r\n }\r\n return first;\r\n }\r\n std.upper_bound = upper_bound;\r\n function equal_range(first, last, val, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n var it = lower_bound(first, last, val, compare);\r\n return std.make_pair(it, upper_bound(it, last, val, compare));\r\n }\r\n std.equal_range = equal_range;\r\n function binary_search(first, last, val, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n first = lower_bound(first, last, val, compare);\r\n return !first.equal_to(last) && !compare(val, first.value);\r\n }\r\n std.binary_search = binary_search;\r\n /* =========================================================\r\n PARTITION\r\n ========================================================= */\r\n /**\r\n *Test whether range is partitioned.
\r\n *\r\n * Returns true if all the elements in the range [first, last) for which pred\r\n * returns true precede those for which it returns false.
If the range is {@link IContainer.empty empty}, the function returns true.
bool. The value returned indicates whether the element belongs to the first group (if\r\n *\t\t\t true, the element is expected before all the elements for which it returns\r\n *\t\t\t false). The function shall not modify its argument.\r\n *\r\n * @return true if all the elements in the range [first, last) for which pred returns\r\n *\t\t true precede those for which it returns false. Otherwise it returns\r\n *\t\t false. If the range is {@link IContainer.empty empty}, the function returns true.\r\n */\r\n function is_partitioned(first, last, pred) {\r\n while (!first.equal_to(last) && pred(first.value))\r\n first = first.next();\r\n for (; !first.equal_to(last); first = first.next())\r\n if (pred(first.value))\r\n return false;\r\n return true;\r\n }\r\n std.is_partitioned = is_partitioned;\r\n /**\r\n * Partition range in two.
\r\n *\r\n * Rearranges the elements from the range [first, last), in such a way that all the elements for\r\n * which pred returns true precede all those for which it returns false. The iterator\r\n * returned points to the first element of the second group.
The relative ordering within each group is not necessarily the same as before the call. See\r\n * {@link stable_partition} for a function with a similar behavior but with stable ordering within each group.
\r\n *\r\n * @param first {@link Iterator Forward iterator} to the initial position of the sequence to partition.\r\n * @param last {@link Iterator Forward iterator} to the final position of the sequence to partition. The range used is\r\n *\t\t\t [first, last), which contains all the elements between first and last,\r\n *\t\t\t including the element pointed by first but not the element pointed by last.\r\n * @param pred Unary function that accepts an element in the range as argument, and returns a value convertible to\r\n *\t\t\tbool. The value returned indicates whether the element belongs to the first group (if\r\n *\t\t\t true, the element is expected before all the elements for which it returns\r\n *\t\t\t false). The function shall not modify its argument.\r\n *\r\n * @return An iterator that points to the first element of the second group of elements (those for which pred\r\n *\t\t returns false), or last if this group is {@link IContainer.empty empty}.\r\n */\r\n function partition(first, last, pred) {\r\n while (!first.equal_to(last)) {\r\n while (pred(first.value)) {\r\n first = first.next();\r\n if (first.equal_to(last))\r\n return first;\r\n }\r\n do {\r\n last = last.prev();\r\n if (first.equal_to(last))\r\n return first;\r\n } while (!pred(last.value));\r\n first.swap(last);\r\n first = first.next();\r\n }\r\n return last;\r\n }\r\n std.partition = partition;\r\n /**\r\n * Partition range in two - stable ordering.
\r\n *\r\n * Rearranges the elements in the range [first, last), in such a way that all the elements for which\r\n * pred returns true precede all those for which it returns false, and, unlike\r\n * function {@link partition}, the relative order of elements within each group is preserved.
This is generally implemented using an internal temporary buffer.
\r\n *\r\n * @param first {@link Iterator Bidirectional iterator} to the initial position of the sequence to partition.\r\n * @param last {@link Iterator Bidirectional iterator} to the final position of the sequence to partition. The range\r\n *\t\t\t used is [first, last), which contains all the elements between first and\r\n *\t\t\t last, including the element pointed by first but not the element pointed by last.\r\n * @param pred Unary function that accepts an element in the range as argument, and returns a value convertible to\r\n *\t\t\tbool. The value returned indicates whether the element belongs to the first group (if\r\n *\t\t\t true, the element is expected before all the elements for which it returns\r\n *\t\t\t false). The function shall not modify its argument.\r\n *\r\n * @return An iterator that points to the first element of the second group of elements (those for which pred\r\n *\t\t returns false), or last if this group is {@link IContainer.empty empty}.\r\n */\r\n function stable_partition(first, last, pred) {\r\n return partition(first, last, pred);\r\n }\r\n std.stable_partition = stable_partition;\r\n /**\r\n * Partition range into two.
\r\n *\r\n * Copies the elements in the range [first, last) for which pred returns true\r\n * into the range pointed by result_true, and those for which it does not into the range pointed by\r\n * result_false.
true are stored.\r\n * @param result_false {@link Iterator Output iterator} to the initial position of the range where the elements for\r\n *\t\t\t\t\t which pred returns false are stored.\r\n * @param pred Unary function that accepts an element pointed by InputIterator as argument, and returns a value\r\n *\t\t\t convertible to bool. The value returned indicates on which result range the element is\r\n *\t\t\t copied. The function shall not modify its argument.\r\n *\r\n * @return A {@link Pair} of iterators with the end of the generated sequences pointed by result_true and\r\n *\t\t result_false, respectivelly. Its member {@link Pair.first first} points to the element that follows\r\n *\t\t the last element copied to the sequence of elements for which pred returned true. Its\r\n *\t\t member {@link Pair.second second} points to the element that follows the last element copied to the sequence\r\n *\t\t of elements for which pred returned false.\r\n */\r\n function partition_copy(first, last, result_true, result_false, pred) {\r\n for (; !first.equal_to(last); first = first.next())\r\n if (pred(first.value)) {\r\n result_true.value = first.value;\r\n result_true = result_true.next();\r\n }\r\n else {\r\n result_false.value = first.value;\r\n result_false = result_false.next();\r\n }\r\n return std.make_pair(result_true, result_false);\r\n }\r\n std.partition_copy = partition_copy;\r\n /**\r\n * Get partition point.
\r\n *\r\n * Returns an iterator to the first element in the partitioned range [first, last) for which\r\n * pred is not true, indicating its partition point.
The elements in the range shall already {@link is_partitioned be partitioned}, as if {@link partition} had been\r\n * called with the same arguments.
\r\n *\r\n *The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted\r\n * range, which is specially efficient for {@link Iteartor random-access iterators}.
\r\n *\r\n * @param first {@link Iterator Forward iterator} to the initial position of the partitioned sequence.\r\n * @param last {@link Iterator Forward iterator} to the final position of the partitioned sequence. The range checked\r\n *\t\t is [first, last), which contains all the elements between first an last,\r\n *\t\t including the element pointed by first but not the element pointed by last.\r\n * @param pred Unary function that accepts an element in the range as argument, and returns a value convertible to\r\n *\t\t\tbool. The value returned indicates whether the element goes before the partition point (if\r\n *\t\t\t true, it goes before; if false goes at or after it). The function shall not\r\n *\t\t\t modify its argument.\r\n *\r\n * @return An iterator to the first element in the partitioned range [first, last) for which pred\r\n *\t\t is not true, or last if it is not true for any element.\r\n */\r\n function partition_point(first, last, pred) {\r\n var n = std.distance(first, last);\r\n while (n > 0) {\r\n var step = Math.floor(n / 2);\r\n var it = first.advance(step);\r\n if (pred(it.value)) {\r\n first = it.next();\r\n n -= step + 1;\r\n }\r\n else\r\n n = step;\r\n }\r\n return first;\r\n }\r\n std.partition_point = partition_point;\r\n function merge(first1, last1, first2, last2, result, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n while (true) {\r\n if (first1.equal_to(last1))\r\n return copy(first2, last2, result);\r\n else if (first2.equal_to(last2))\r\n return copy(first1, last1, result);\r\n if (compare(first1.value, first2.value)) {\r\n result.value = first1.value;\r\n first1 = first1.next();\r\n }\r\n else {\r\n result.value = first2.value;\r\n first2 = first2.next();\r\n }\r\n result = result.next();\r\n }\r\n }\r\n std.merge = merge;\r\n function inplace_merge(first, middle, last, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n var vector = new std.Vector(std.distance(first, last), null);\r\n merge(first, middle, middle, last, vector.begin());\r\n copy(vector.begin(), vector.end(), first);\r\n }\r\n std.inplace_merge = inplace_merge;\r\n function includes(first1, last1, first2, last2, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n while (!first2.equal_to(last2)) {\r\n if (first1.equal_to(last2) || compare(first2.value, first1.value))\r\n return false;\r\n else if (!compare(first1.value, first2.value))\r\n first2 = first2.next();\r\n first1 = first1.next();\r\n }\r\n return true;\r\n }\r\n std.includes = includes;\r\n function set_union(first1, last1, first2, last2, result, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n while (true) {\r\n if (first1.equal_to(last1))\r\n return copy(first2, last2, result);\r\n else if (first2.equal_to(last2))\r\n return copy(first1, last1, result);\r\n if (compare(first1.value, first2.value)) {\r\n result.value = first1.value;\r\n first1 = first1.next();\r\n }\r\n else if (compare(first2.value, first1.value)) {\r\n result.value = first2.value;\r\n first2 = first2.next();\r\n }\r\n else {\r\n result.value = first1.value;\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n }\r\n result = result.next();\r\n }\r\n }\r\n std.set_union = set_union;\r\n function set_intersection(first1, last1, first2, last2, result, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n while (true) {\r\n if (first1.equal_to(last1))\r\n return copy(first2, last2, result);\r\n else if (first2.equal_to(last2))\r\n return copy(first1, last1, result);\r\n if (compare(first1.value, first2.value))\r\n first1 = first1.next();\r\n else if (compare(first2.value, first1.value))\r\n first2 = first2.next();\r\n else {\r\n result.value = first1.value;\r\n result = result.next();\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n }\r\n }\r\n }\r\n std.set_intersection = set_intersection;\r\n function set_difference(first1, last1, first2, last2, result, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n while (!first1.equal_to(last1) && !first2.equal_to(last2))\r\n if (std.less(first1.value, first2.value)) {\r\n result.value = first1.value;\r\n result = result.next();\r\n first1 = first1.next();\r\n }\r\n else if (std.less(first2.value, first1.value))\r\n first2 = first2.next();\r\n else {\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n }\r\n return copy(first1, last1, result);\r\n }\r\n std.set_difference = set_difference;\r\n function set_symmetric_difference(first1, last1, first2, last2, result, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n while (true) {\r\n if (first1.equal_to(last1))\r\n return copy(first2, last2, result);\r\n else if (first2.equal_to(last2))\r\n return copy(first1, last1, result);\r\n if (compare(first1.value, first2.value)) {\r\n result.value = first1.value;\r\n result = result.next();\r\n first1 = first1.next();\r\n }\r\n else if (compare(first2.value, first1.value)) {\r\n result.value = first2.value;\r\n result = result.next();\r\n first2 = first2.next();\r\n }\r\n else {\r\n first1 = first1.next();\r\n first2 = first2.next();\r\n }\r\n }\r\n }\r\n std.set_symmetric_difference = set_symmetric_difference;\r\n /* =========================================================\r\n MIN & MAX\r\n - VARADIC PARAMETERS\r\n - ITERATORS\r\n ============================================================\r\n VARADIC PARAMETERS\r\n --------------------------------------------------------- */\r\n /**\r\n * Return the smallest.
\r\n *\r\n *Returns the smallest of all the elements in the args.
\r\n *\r\n * @param args Values to compare.\r\n *\r\n * @return The lesser of the values passed as arguments.\r\n */\r\n function min() {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n var minimum = args[0];\r\n for (var i = 1; i < args.length; i++)\r\n if (std.less(args[i], minimum))\r\n minimum = args[i];\r\n return minimum;\r\n }\r\n std.min = min;\r\n /**\r\n *Return the largest.
\r\n *\r\n *Returns the largest of all the elements in the args.
\r\n *\r\n * @param args Values to compare.\r\n *\r\n * @return The largest of the values passed as arguments.\r\n */\r\n function max() {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n var maximum = args[0];\r\n for (var i = 1; i < args.length; i++)\r\n if (std.greater(args[i], maximum))\r\n maximum = args[i];\r\n return maximum;\r\n }\r\n std.max = max;\r\n /**\r\n *Return smallest and largest elements.
\r\n *\r\n *Returns a {@link Pair} with the smallest of all the elements in the args as first element (the first of\r\n * them, if there are more than one), and the largest as second (the last of them, if there are more than one).
\r\n *\r\n * @param args Values to compare.\r\n *\r\n * @return The lesser and greatest of the values passed as arguments.\r\n */\r\n function minmax() {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n var minimum = args[0];\r\n var maximum = args[0];\r\n for (var i = 1; i < args.length; i++) {\r\n if (std.less(args[i], minimum))\r\n minimum = args[i];\r\n if (std.greater(args[i], maximum))\r\n maximum = args[i];\r\n }\r\n return std.make_pair(minimum, maximum);\r\n }\r\n std.minmax = minmax;\r\n function min_element(first, last, compare) {\r\n if (compare === void 0) { compare = std.less; }\r\n var smallest = first;\r\n first = first.next();\r\n for (; !first.equal_to(last); first = first.next())\r\n if (compare(first.value, smallest.value))\r\n smallest = first;\r\n return smallest;\r\n }\r\n std.min_element = min_element;\r\n function max_element(first, last, compare) {\r\n if (compare === void 0) { compare = std.greater; }\r\n var largest = first;\r\n first = first.next();\r\n for (; !first.equal_to(last); first = first.next())\r\n if (compare(first.value, largest.value))\r\n largest = first;\r\n return largest;\r\n }\r\n std.max_element = max_element;\r\n function minmax_element(first, last, compare) {\r\n if (compare === void 0) { compare = std.greater; }\r\n var smallest = first;\r\n var largest = first;\r\n first = first.next();\r\n for (; !first.equal_to(last); first = first.next()) {\r\n if (compare(first.value, smallest.value))\r\n smallest = first;\r\n if (!compare(first.value, largest.value))\r\n largest = first;\r\n }\r\n return std.make_pair(smallest, largest);\r\n }\r\n std.minmax_element = minmax_element;\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n /* =========================================================\r\n + EXCEPTION\r\n + LOGIC_ERROR\r\n - DOMAIN_ERROR\r\n - INVALID_ARGUMENT\r\n - LENGTH_ERROR\r\n - OUT_OF_RANGE\r\n + RUNTIME_ERROR\r\n - OVERFLOW_ERROR\r\n - RANGE_ERROR\r\n - SYSTEM_ERROR\r\n - UNDERFLOW_ERROR\r\n ========================================================= */\r\n /**\r\n *Standard exception class.
\r\n *\r\n *Base class for standard exceptions.
\r\n *\r\n *All objects thrown by components of the standard library are derived from this class.\r\n * Therefore, all standard exceptions can be caught by catching this type by reference.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/exception/exception/\r\n *
Get string identifying exception.
\r\n *Returns a string that may be used to identify the exception.
\r\n *\r\n *The particular representation pointed by the returned value is implementation-defined.\r\n * As a virtual function, derived classes may redefine this function so that specify value are\r\n * returned.
\r\n */\r\n Exception.prototype.what = function () {\r\n return this.message;\r\n };\r\n return Exception;\r\n }());\r\n std.Exception = Exception;\r\n /* =========================================================\r\n + LOGIC_ERROR\r\n - DOMAIN_ERROR\r\n - INVALID_ARGUMENT\r\n - LENGTH_ERROR\r\n - OUT_OF_RANGE\r\n ========================================================= */\r\n /**\r\n *Logic error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report errors in the internal\r\n * logical of the program, such as violation of logical preconditions or class invariants.
\r\n *\r\n *These errors are presumably detectable before the program executes.
\r\n *\r\n *It is used as a base class for several logical error exceptions.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/logic_error/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function LogicError(what) {\r\n _super.call(this, what);\r\n }\r\n return LogicError;\r\n }(Exception));\r\n std.LogicError = LogicError;\r\n /**\r\n *Domain error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report domain errors.
\r\n *\r\n *Generally, the domain of a mathematical function is the subset of values that it is defined for.\r\n * For example, the square root function is only defined for non-negative numbers. Thus, a negative number\r\n * for such a function would qualify as a domain error.
\r\n *\r\n *No component of the standard library throws exceptions of this type. It is designed as a standard\r\n * exception to be thrown by programs.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/domain_error/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function DomainError(what) {\r\n _super.call(this, what);\r\n }\r\n return DomainError;\r\n }(LogicError));\r\n std.DomainError = DomainError;\r\n /**\r\n *Invalid argument exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report an invalid argument.
\r\n *\r\n *It is a standard exception that can be thrown by programs. Some components of the standard library\r\n * also throw exceptions of this type to signal invalid arguments.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/invalid_argument/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function InvalidArgument(what) {\r\n _super.call(this, what);\r\n }\r\n return InvalidArgument;\r\n }(LogicError));\r\n std.InvalidArgument = InvalidArgument;\r\n /**\r\n *Length error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report a length error.
\r\n *\r\n *It is a standard exception that can be thrown by programs. Some components of the standard library,\r\n * such as vector and string also throw exceptions of this type to signal errors resizing.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/length_error/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function LengthError(what) {\r\n _super.call(this, what);\r\n }\r\n return LengthError;\r\n }(LogicError));\r\n std.LengthError = LengthError;\r\n /**\r\n *Out-of-range exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report an out-of-range error.
\r\n *\r\n *It is a standard exception that can be thrown by programs. Some components of the standard library,\r\n * such as vector, deque, string and bitset also throw exceptions of this type to signal arguments\r\n * out of range.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/out_of_range/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function OutOfRange(what) {\r\n _super.call(this, what);\r\n }\r\n return OutOfRange;\r\n }(LogicError));\r\n std.OutOfRange = OutOfRange;\r\n /* =========================================================\r\n + RUNTIME_ERROR\r\n - OVERFLOW_ERROR\r\n - RANGE_ERROR\r\n - SYSTEM_ERROR\r\n - UNDERFLOW_ERROR\r\n ========================================================= */\r\n /**\r\n *Runtime error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report errors that can only be\r\n * detected during runtime.
\r\n *\r\n *It is used as a base class for several runtime error exceptions.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/runtime_error/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function RuntimeError(what) {\r\n _super.call(this, what);\r\n }\r\n return RuntimeError;\r\n }(Exception));\r\n std.RuntimeError = RuntimeError;\r\n /**\r\n *Overflow error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to arithmetic overflow errors.
\r\n *\r\n *It is a standard exception that can be thrown by programs. Some components of the standard library\r\n * also throw exceptions of this type to signal range errors.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/outflow_error/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function OverflowError(what) {\r\n _super.call(this, what);\r\n }\r\n return OverflowError;\r\n }(RuntimeError));\r\n std.OverflowError = OverflowError;\r\n /**\r\n *Underflow error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to arithmetic underflow errors.
\r\n *\r\n *No component of the standard library throws exceptions of this type. It is designed as a standard\r\n * exception to be thrown by programs.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/underflow_error/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function UnderflowError(what) {\r\n _super.call(this, what);\r\n }\r\n return UnderflowError;\r\n }(RuntimeError));\r\n std.UnderflowError = UnderflowError;\r\n /**\r\n *Range error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report range errors in internal\r\n * computations.
\r\n *\r\n *It is a standard exception that can be thrown by programs. Some components of the standard library\r\n * also throw exceptions of this type to signal range errors.
\r\n *\r\n *- \r\n *
- Reference: http://www.cplusplus.com/reference/stdexcept/range_error/\r\n *
Construct from a message.
\r\n *\r\n * @param message A message representing specification about the Exception.\r\n */\r\n function RangeError(what) {\r\n _super.call(this, what);\r\n }\r\n return RangeError;\r\n }(RuntimeError));\r\n std.RangeError = RangeError;\r\n})(std || (std = {}));\r\n// Standard Template Library: Function objects\r\n// Function objects are objects specifically designed to be used with a syntax similar to that of functions.\r\n//\r\n// They are typically used as arguments to functions, such as predicates or comparison functions passed to standard algorithms.\r\n//\r\n// @reference http://www.cplusplus.com/reference/functional/\r\n// @author Jeongho NamFunction object class for equality comparison.
\r\n *\r\n *Binary function object class whose call returns whether its two arguments compare equal (as returned by\r\n * operator ==).
\r\n *\r\n *Generically, function objects are instances of a class with member function {@link IComparable.equal_to equal_to}\r\n * defined. This member function allows the object to be used with the same syntax as a function call.
\r\n *\r\n * @param x First element to compare.\r\n * @param y Second element to compare.\r\n *\r\n * @return Whether the arguments are equal.\r\n */\r\n function equal_to(x, y) {\r\n if (x instanceof Object && x.equal_to != undefined)\r\n return x.equal_to(y);\r\n else\r\n return x == y;\r\n }\r\n std.equal_to = equal_to;\r\n /**\r\n *Function object class for non-equality comparison.
\r\n *\r\n *Binary function object class whose call returns whether its two arguments compare not equal (as returned\r\n * by operator operator!=).
\r\n *\r\n *Generically, function objects are instances of a class with member function {@link IComparable.equal_to equal_to}\r\n * defined. This member function allows the object to be used with the same syntax as a function call.
\r\n *\r\n * @param x First element to compare.\r\n * @param y Second element to compare.\r\n *\r\n * @return Whether the arguments are not equal.\r\n */\r\n function not_equal_to(x, y) {\r\n return !std.equal_to(x, y);\r\n }\r\n std.not_equal_to = not_equal_to;\r\n /**\r\n *Function for less-than inequality comparison.
\r\n *\r\n *Binary function returns whether the its first argument compares less than the second.
\r\n *\r\n *Generically, function objects are instances of a class with member function {@link IComparable.less less}\r\n * defined. If an object doesn't have the method, then its own uid will be used to compare insteadly.\r\n * This member function allows the object to be used with the same syntax as a function call.
\r\n *\r\n *Objects of this class can be used on standard algorithms such as {@link sort sort()},\r\n * {@link merge merge()} or {@link TreeMap.lower_bound lower_bound()}.
\r\n *\r\n * @paramFunction object class for less-than-or-equal-to comparison.
\r\n *\r\n *Binary function object class whose call returns whether the its first argument compares {@link less less than} or\r\n * {@link equal_to equal to} the second (as returned by operator <=).
\r\n *\r\n *Generically, function objects are instances of a class with member function {@link IComparable.less less}\r\n * and {@link IComparable.equal_to equal_to} defined. This member function allows the object to be used with the same\r\n * syntax as a function call.
\r\n *\r\n * @param x First element, the standard of comparison.\r\n * @param y Second element compare with the first.\r\n *\r\n * @return Whether the x is {@link less less than} or {@link equal_to equal to} the y.\r\n */\r\n function less_equal(x, y) {\r\n return std.less(x, y) || std.equal_to(x, y);\r\n }\r\n std.less_equal = less_equal;\r\n /**\r\n *Function for greater-than inequality comparison.
\r\n *\r\n *Binary function returns whether the its first argument compares greater than the second.
\r\n *\r\n *Generically, function objects are instances of a class with member function {@link less} and\r\n * {@link equal_to equal_to()} defined. If an object doesn't have those methods, then its own uid will be used\r\n * to compare insteadly. This member function allows the object to be used with the same syntax as a function\r\n * call.
\r\n *\r\n *Objects of this class can be used on standard algorithms such as {@link sort sort()},\r\n * {@link merge merge()} or {@link TreeMap.lower_bound lower_bound()}.
\r\n *\r\n * @paramFunction object class for greater-than-or-equal-to comparison.
\r\n *\r\n *Binary function object class whose call returns whether the its first argument compares\r\n * {@link greater greater than} or {@link equal_to equal to} the second (as returned by operator >=).
\r\n *\r\n *Generically, function objects are instances of a class with member function {@link IComparable.less less}\r\n * defined. If an object doesn't have the method, then its own uid will be used to compare insteadly.\r\n * This member function allows the object to be used with the same syntax as a function call.
\r\n *\r\n * @param x First element, the standard of comparison.\r\n * @param y Second element compare with the first.\r\n *\r\n * @return Whether the x is {@link greater greater than} or {@link equal_to equal to} the y.\r\n */\r\n function greater_equal(x, y) {\r\n return !std.less(x, y);\r\n }\r\n std.greater_equal = greater_equal;\r\n /**\r\n *Logical AND function object class.
\r\n *\r\n *Binary function object class whose call returns the result of the logical \"and\" operation between its two\r\n * arguments (as returned by operator &&).
\r\n *\r\n *Generically, function objects are instances of a class with member function operator() defined. This member\r\n * function allows the object to be used with the same syntax as a function call.
\r\n *\r\n * @param x First element.\r\n * @param y Second element.\r\n *\r\n * @return Result of logical AND operation.\r\n */\r\n function logical_and(x, y) {\r\n return x && y;\r\n }\r\n std.logical_and = logical_and;\r\n /**\r\n *Logical OR function object class.
\r\n *\r\n *Binary function object class whose call returns the result of the logical \"or\" operation between its two\r\n * arguments (as returned by operator ||).
\r\n *\r\n *Generically, function objects are instances of a class with member function operator() defined. This member\r\n * function allows the object to be used with the same syntax as a function call.
\r\n *\r\n * @param x First element.\r\n * @param y Second element.\r\n *\r\n * @return Result of logical OR operation.\r\n */\r\n function logical_or(x, y) {\r\n return x || y;\r\n }\r\n std.logical_or = logical_or;\r\n /**\r\n *Logical NOT function object class.
\r\n *\r\n *Unary function object class whose call returns the result of the logical \"not\" operation on its argument\r\n * (as returned by operator !).
\r\n *\r\n *Generically, function objects are instances of a class with member function operator() defined. This member\r\n * function allows the object to be used with the same syntax as a function call.
\r\n *\r\n * @param x Target element.\r\n *\r\n * @return Result of logical NOT operation.\r\n */\r\n function logical_not(x) {\r\n return !x;\r\n }\r\n std.logical_not = logical_not;\r\n /**\r\n *Bitwise AND function object class.
\r\n *\r\n *Binary function object class whose call returns the result of applying the bitwise \"and\" operation between\r\n * its two arguments (as returned by operator &).
\r\n *\r\n * @param x First element.\r\n * @param y Second element.\r\n *\r\n * @return Result of bitwise AND operation.\r\n */\r\n function bit_and(x, y) {\r\n return x & y;\r\n }\r\n std.bit_and = bit_and;\r\n /**\r\n *Bitwise OR function object class.
\r\n *\r\n *Binary function object class whose call returns the result of applying the bitwise \"and\" operation between\r\n * its two arguments (as returned by operator &).
\r\n *\r\n * @param x First element.\r\n * @param y Second element.\r\n *\r\n * @return Result of bitwise OR operation.\r\n */\r\n function bit_or(x, y) {\r\n return x | y;\r\n }\r\n std.bit_or = bit_or;\r\n /**\r\n *Bitwise XOR function object class.
\r\n *\r\n *Binary function object class whose call returns the result of applying the bitwise \"exclusive or\"\r\n * operation between its two arguments (as returned by operator ^).
\r\n *\r\n * @param x First element.\r\n * @param y Second element.\r\n *\r\n * @return Result of bitwise XOR operation.\r\n */\r\n function bit_xor(x, y) {\r\n return x ^ y;\r\n }\r\n std.bit_xor = bit_xor;\r\n function swap(left, right) {\r\n left.swap(right);\r\n }\r\n std.swap = swap;\r\n function bind(fn) {\r\n var args = [];\r\n for (var _i = 1; _i < arguments.length; _i++) {\r\n args[_i - 1] = arguments[_i];\r\n }\r\n var this_arg = null;\r\n var parameters = [];\r\n var placeholder_count = 0;\r\n for (var i = 0; i < args.length; i++) {\r\n if (i == 0 && args[0] instanceof Object && args[0] instanceof placeholders.PlaceHolder == false) {\r\n // retrieve the object; items[0]\r\n for (var key in args[0])\r\n if (args[0][key] == fn) {\r\n // found the this_arg\r\n this_arg = args[0];\r\n break;\r\n }\r\n if (this_arg != null)\r\n continue;\r\n }\r\n // the placeholder also fills parameters\r\n if (args[i] instanceof placeholders.PlaceHolder)\r\n placeholder_count++;\r\n parameters.push(args[i]);\r\n }\r\n ////////////////////\r\n // FUNCTION TO BE RETURNED\r\n ////////////////////\r\n var ret = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n if (args.length == 0)\r\n return fn.apply(this_arg, parameters);\r\n var thisArg = this_arg;\r\n var argArray = parameters.slice();\r\n // 1st argument is thisArg?\r\n if (thisArg == null && (parameters.length == 0 || parameters[0] instanceof placeholders.PlaceHolder) && args[0] instanceof Object)\r\n for (var key in args[0])\r\n if (args[0][key] == fn) {\r\n thisArg = args[0];\r\n argArray.splice(0, 1);\r\n //lastIndex++;\r\n break;\r\n }\r\n // fill argArray from placeholders\r\n for (var i = 0; i < argArray.length; i++)\r\n if (argArray[i] instanceof placeholders.PlaceHolder)\r\n argArray[i] = args[argArray[i].index - 1];\r\n // arguments are over the placeholder_count \r\n if (args.length > placeholder_count)\r\n for (var i = placeholder_count; i < args.length; i++)\r\n if (i == 0 && (this_arg == null && thisArg != null))\r\n continue; // thisArg\r\n else\r\n argArray.push(args[i]);\r\n return fn.apply(thisArg, argArray);\r\n };\r\n return ret;\r\n }\r\n std.bind = bind;\r\n /**\r\n *Bind argument placeholders.
\r\n *\r\n *This namespace declares an unspecified number of objects: _1, _2, _3, ..., which are\r\n * used to specify placeholders in calls to function {@link std.bind}.
\r\n *\r\n *When the function object returned by bind is called, an argument with placeholder {@link _1} is replaced by the\r\n * first argument in the call, {@link _2} is replaced by the second argument in the call, and so on... For example:
\r\n *\r\n *\r\n let vec: Vector = new Vector();\r\n\r\n let bind = std.bind(Vector.insert, _1, vec.end(), _2, _3);\r\n bind.apply(vec, 5, 1); // vec.insert(vec.end(), 5, 1);\r\n // [1, 1, 1, 1, 1]\r\n * \r\n *\r\n * When a call to {@link bind} is used as a subexpression in another call to bind, the {@link placeholders}\r\n * are relative to the outermost {@link bind} expression.
\r\n *\r\n * @reference http://www.cplusplus.com/reference/functional/placeholders/\r\n * @author Jeongho NamReturn distance between {@link Iterator iterators}.
\r\n *\r\n *Calculates the number of elements between first and last.
\r\n *\r\n *If it is a {@link IArrayIterator random-access iterator}, the function uses operator- to calculate this.\r\n * Otherwise, the function uses the increase operator {@link Iterator.next next()} repeatedly.
\r\n *\r\n * @param first Iterator pointing to the initial element.\r\n * @param last Iterator pointing to the final element. This must be reachable from first.\r\n *\r\n * @return The number of elements between first and last.\r\n */\r\n function distance(first, last) {\r\n if (first instanceof std.VectorIterator || first instanceof std.DequeIterator)\r\n return last.index - first.index;\r\n var length = 0;\r\n for (; !first.equal_to(last); first = first.next())\r\n length++;\r\n return length;\r\n }\r\n std.distance = distance;\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n /**\r\n *Pair of values.
\r\n *\r\n *This class couples together a pair of values, which may be of different types (T1 and\r\n * T2). The individual values can be accessed through its public members {@link first} and\r\n * {@link second}.
\r\n *\r\n *- \r\n *\t
- Reference: http://www.cplusplus.com/reference/utility/pair/ \r\n *
Construct from pair values.
\r\n *\r\n * @param first The first value of the Pair\r\n * @param second The second value of the Pair\r\n */\r\n function Pair(first, second) {\r\n this.first = first;\r\n this.second = second;\r\n }\r\n /* ---------------------------------------------------------\r\n COMPARISON\r\n --------------------------------------------------------- */\r\n /**\r\n *Whether a Pair is equal with the Pair.
\r\n *
Compare each first and second value of two Pair(s) and returns whether they are equal or not.
\r\n *\r\n *If stored key and value in a Pair are not number or string but an object like a class or struct,\r\n * the comparison will be executed by a member method (SomeObject)::equal_to(). If the object does not have\r\n * the member method equal_to(), only address of pointer will be compared.
\r\n *\r\n * @param obj A Map to compare\r\n * @return Indicates whether equal or not.\r\n */\r\n Pair.prototype.equal_to = function (pair) {\r\n return std.equal_to(this.first, pair.first) && std.equal_to(this.second, pair.second);\r\n };\r\n Pair.prototype.less = function (pair) {\r\n if (std.equal_to(this.first, pair.first) == false)\r\n return std.less(this.first, pair.first);\r\n else\r\n return std.less(this.second, pair.second);\r\n };\r\n return Pair;\r\n }());\r\n std.Pair = Pair;\r\n /**\r\n *Construct {@link Pair} object.
\r\n *\r\n *Constructs a {@link Pair} object with its {@link Pair.first first} element set to x and its\r\n * {@link Pair.second second} element set to y.
\r\n *\r\n *The template types can be implicitly deduced from the arguments passed to {@link make_pair}.
\r\n *\r\n *{@link Pair} objects can be constructed from other {@link Pair} objects containing different types, if the\r\n * respective types are implicitly convertible.
\r\n *\r\n * @param x Value for member {@link Pair.first first}.\r\n * @param y Value for member {@link Pair.second second}.\r\n *\r\n * @return A {@link Pair} object whose elements {@link Pair.first first} and {@link Pair.second second} are set to\r\n *\t\t x and y respectivelly.\r\n */\r\n function make_pair(x, y) {\r\n return new Pair(x, y);\r\n }\r\n std.make_pair = make_pair;\r\n})(std || (std = {}));\r\n///Red-black Tree.
\r\n *\r\n *A red-black tree is a kind of self-balancing\r\n * binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the\r\n * color (red or black) of the node. These color bits\r\n * are used to ensure the tree remains approximately balanced during insertions and deletions.
\r\n *\r\n *Balance is preserved by painting each node of the tree with one of two colors (typically called\r\n * 'red' and 'black') in a way that satisfies certain\r\n * properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree\r\n * is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The\r\n * properties are designed in such a way that this rearranging and recoloring can be performed efficiently.
\r\n *\r\n *The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in\r\n * O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations,\r\n * along with the tree rearrangement and recoloring, are also performed in O(log n) time.
\r\n *\r\n *Tracking the color of each node requires only 1 bit of information per node because there are only two\r\n * colors. The tree does not contain any other data specific to its being a\r\n * red-black tree so its memory footprint is almost\r\n * identical to a classic (uncolored) binary search tree. In many cases the additional bit of information can\r\n * be stored at no additional memory cost.
\r\n *\r\n *Properties
\r\n *In addition to the requirements imposed on a binary search tree the following must be satisfied by a\r\n * red-black tree:
\r\n *\r\n *- \r\n *\t
- A node is either red or black. \r\n *\t
- \r\n *\t\tThe root is black. This rule is sometimes omitted. Since the root can\r\n *\t\talways be changed from red to black, but not\r\n *\t\tnecessarily vice versa, this rule has little effect on analysis.\r\n *\t \r\n *\t
- All leaves (NIL;
null) are black. \r\n * - \r\n *\t\tIf a node is red, then both its children are\r\n *\t\tblack.\r\n *\t \r\n *
- \r\n *\t\tEvery path from a given node to any of its descendant NIL nodes contains the same number of\r\n *\t\tblack nodes. Some definitions: the number of\r\n *\t\tblack nodes from the root to a node is the node's\r\n *\t\tblack depth; the uniform number of black\r\n *\t\tnodes in all paths from root to the leaves is called the black-height of\r\n *\t\tthe red-black tree.\r\n *\t \r\n *
![](\"../assets/images/tree/Red-black_tree_example.svg\")
These constraints enforce a critical property of red-black trees: the path from the root to the farthest\r\n * leaf is no more than twice as long as the path from the root to the nearest leaf. The result is that the tree\r\n * is roughly height-balanced. Since operations such as inserting, deleting, and finding values require\r\n * worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows\r\n * red-black trees to be efficient in the worst case, unlike ordinary binary search trees.
\r\n *\r\n *To see why this is guaranteed, it suffices to consider the effect of properties 4 and 5 together. For a\r\n * red-black tree T, let B be the number of black nodes in property 5. Let the\r\n * shortest possible path from the root of T to any leaf consist of B black nodes.\r\n * Longer possible paths may be constructed by inserting red nodes. However, property 4\r\n * makes it impossible to insert more than one consecutive red node. Therefore,\r\n * ignoring any black NIL leaves, the longest possible path consists of 2*B nodes,\r\n * alternating black and red (this is the worst case).\r\n * Counting the black NIL leaves, the longest possible path consists of 2*B-1\r\n * nodes.
\r\n *\r\n *The shortest possible path has all black nodes, and the longest possible\r\n * path alternates between red and black nodes. Since all\r\n * maximal paths have the same number of black nodes, by property 5, this shows\r\n * that no path is more than twice as long as any other path.
\r\n *\r\n *- \r\n *\t
- Reference: https://en.wikipedia.org/w/index.php?title=Red%E2%80%93black_tree&redirect=no \r\n *
Insert an element with a new node.
\r\n *\r\n *Insertion begins by adding the node as any binary search tree insertion does and by coloring it\r\n * red. Whereas in the binary search tree, we always add a leaf, in the red-black\r\n * tree, leaves contain no information, so instead we add a red interior node, with\r\n * two black leaves, in place of an existing\r\n * black leaf.
\r\n *\r\n *What happens next depends on the color of other nearby nodes. The term uncle node will be used to\r\n * refer to the sibling of a node's parent, as in human family trees. Note that:
\r\n *\r\n *- \r\n *\t
- property 3 (all leaves are black) always holds. \r\n *\t
- \r\n *\t\tproperty 4 (both children of every red node are\r\n *\t\tblack) is threatened only by adding a red\r\n *\t\tnode, repainting a black node red, or a\r\n *\t\trotation.\r\n *\t \r\n *\t
- \r\n *\t\tproperty 5 (all paths from any given node to its leaf nodes contain the same number of\r\n *\t\tblack nodes) is threatened only by adding a\r\n *\t\tblack node, repainting a red node\r\n *\t\tblack (or vice versa), or a rotation.\r\n *\t \r\n *
Notes
\r\n *- \r\n *\t
- \r\n *\t\tThe label N will be used to denote the current node (colored\r\n *\t\tred). In the diagrams N carries a blue contour. At the\r\n *\t\tbeginning, this is the new node being inserted, but the entire procedure may also be applied\r\n *\t\trecursively to other nodes (see case 3). {@link XTreeNode.parent P} will denote\r\n *\t\tN's parent node, {@link XTreeNode.grand_parent G} will denote N's\r\n *\t\tgrandparent, and {@link XTreeNode.uncle U} will denote N's uncle. In between\r\n *\t\tsome cases, the roles and labels of the nodes are exchanged, but in each case, every label continues\r\n *\t\tto represent the same node it represented at the beginning of the case.\r\n *\t \r\n *\t
- \r\n *\t\tIf a node in the right (target) half of a diagram carries a blue contour it will become the current\r\n *\t\tnode in the next iteration and there the other nodes will be newly assigned relative to it. Any\r\n *\t\tcolor shown in the diagram is either assumed in its case or implied by those assumptions.\r\n *\t \r\n *\t
- \r\n *\t\tA numbered triangle represents a subtree of unspecified depth. A black\r\n *\t\tcircle atop a triangle means that black-height of subtree is greater\r\n *\t\tby one compared to subtree without this circle. \r\n *
There are several cases of red-black tree insertion to handle:
\r\n *\r\n *- \r\n *\t
- N is the root node, i.e., first node of red-black tree. \r\n *\t
- \r\n *\t\tN's parent ({@link XTreeNode.parent P}) is black.\r\n *\t \r\n *\t
- \r\n *\t\tN's parent ({@link XTreeNode.parent P}) and uncle\r\n *\t\t({@link XTreeNode.uncle U}) are red.\r\n *\t \r\n *\t
- \r\n *\t\tN is added to right of left child of grandparent, or N is added to left\r\n *\t\tof right child of grandparent ({@link XTreeNode.parent P} is red and\r\n *\t\t{@link XTreeNode.uncle U} is black).\r\n *\t \r\n *\t
- \r\n *\t\tN is added to left of left child of grandparent, or N is added to right\r\n *\t\tof right child of grandparent ({@link XTreeNode.parent P} is red and\r\n *\t\t{@link XTreeNode.uncle U} is black).\r\n *\t \r\n *
Note
\r\n *Note that inserting is actually in-place, since all the calls above use tail recursion.
\r\n *\r\n *In the algorithm above, all cases are chained in order, except in insert case 3 where it can recurse\r\n * to case 1 back to the grandparent node: this is the only case where an iterative implementation will\r\n * effectively loop. Because the problem of repair is escalated to the next higher level but one, it takes\r\n * maximally h⁄2 iterations to repair the tree (where h is the height of the tree). Because the probability\r\n * for escalation decreases exponentially with each iteration the average insertion cost is constant.
\r\n *\r\n * @param val An element to insert.\r\n */\r\n XTree.prototype.insert = function (val) {\r\n var parent = this.find(val);\r\n var node = new base.XTreeNode(val, base.Color.RED);\r\n if (parent == null)\r\n this.root_ = node;\r\n else {\r\n node.parent = parent;\r\n if (this.is_less(node.value, parent.value))\r\n parent.left = node;\r\n else\r\n parent.right = node;\r\n }\r\n this.insert_case1(node);\r\n };\r\n /**\r\n *N is the root node, i.e., first node of red-black tree.
\r\n *\r\n *The current node N is at the {@link root_ root} of the tree.
\r\n *\r\n *In this case, it is repainted black to satisfy property 2 (the root is\r\n * black). Since this adds one black node to\r\n * every path at once, property 5 (all paths from any given node to its leaf nodes contain the same number\r\n * of black nodes) is not violated.
\r\n *\r\n * @param N A node to be inserted or swapped.\r\n */\r\n XTree.prototype.insert_case1 = function (N) {\r\n if (N.parent == null)\r\n N.color = base.Color.BLACK;\r\n else\r\n this.insert_case2(N);\r\n };\r\n /**\r\n *N's parent ({@link XTreeNode.parent P}) is black.
\r\n *\r\n *The current node's parent {@link XTreeNode.parent P} is black,\r\n * so property 4 (both children of every red node are\r\n * black) is not invalidated.
\r\n *\r\n *In this case, the tree is still valid. Property 5 (all paths from any given node to its leaf nodes\r\n * contain the same number of black nodes) is not threatened, because the\r\n * current node N has two black leaf children, but because\r\n * N is red, the paths through each of its children have the same\r\n * number of black nodes as the path through the leaf it replaced, which was\r\n * black, and so this property remains satisfied.
\r\n *\r\n * @param N A node to be inserted or swapped.\r\n */\r\n XTree.prototype.insert_case2 = function (N) {\r\n if (this.fetch_color(N.parent) == base.Color.BLACK)\r\n return;\r\n else\r\n this.insert_case3(N);\r\n };\r\n /**\r\n *N's parent ({@link XTreeNode.parent P}) and uncle\r\n * ({@link XTreeNode.uncle U}) are red.
\r\n *\r\n *If both the parent {@link XTreeNode.parent P} and the uncle {@link XTreeNode.uncle U}\r\n * are red, then both of them can be repainted black\r\n * and the grandparent {@link XTreeNode.grand_parent G} becomes red (to\r\n * maintain property 5 (all paths from any given node to its leaf nodes contain the same number of\r\n * black nodes)).
\r\n *\r\n *Now, the current red node N has a\r\n * black parent. Since any path through the parent or uncle must pass through\r\n * the grandparent, the number of black nodes on these paths has not changed.\r\n *\r\n *
However, the grandparent {@link XTreeNode.grand_parent G} may now violate properties 2 (The\r\n * root is black) or 4 (Both children of every red\r\n * node are black) (property 4 possibly being violated since\r\n * {@link XTreeNode.grand_parent G} may have a red parent).
\r\n *\r\n *To fix this, the entire procedure is recursively performed on {@link XTreeNode.grand_parent G}\r\n * from case 1. Note that this is a tail-recursive call, so it could be rewritten as a loop; since this is\r\n * the only loop, and any rotations occur after this loop, this proves that a constant number of rotations\r\n * occur.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_insert_case_3.svg\")
N is added to right of left child of grandparent, or N is added to left\r\n * of right child of grandparent ({@link XTreeNode.parent P} is red and\r\n * {@link XTreeNode.uncle U} is black).
\r\n *\r\n *The parent {@link XTreeNode.parent P} is red but the uncle\r\n * {@link XTreeNode.uncle U} is black; also, the current node\r\n * N is the right child of {@link XTreeNode.parent P}, and\r\n * {@link XTreeNode.parent P} in turn is the left child of its parent\r\n * {@link XTreeNode.grand_parent G}.
\r\n *\r\n *In this case, a left rotation on {@link XTreeNode.parent P} that switches the roles of the\r\n * current node N and its parent {@link XTreeNode.parent P} can be performed; then,\r\n * the former parent node {@link XTreeNode.parent P} is dealt with using case 5\r\n * (relabeling N and {@link XTreeNode.parent P}) because property 4 (both children of\r\n * every red node are black) is still violated.
\r\n *\r\n *The rotation causes some paths (those in the sub-tree labelled \"1\") to pass through the node\r\n * N where they did not before. It also causes some paths (those in the sub-tree labelled \"3\")\r\n * not to pass through the node {@link XTreeNode.parent P} where they did before. However, both of\r\n * these nodes are red, so property 5 (all paths from any given node to its leaf\r\n * nodes contain the same number of black nodes) is not violated by the\r\n * rotation.
\r\n *\r\n *After this case has been completed, property 4 (both children of every red\r\n * node are black) is still violated, but now we can resolve this by\r\n * continuing to case 5.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_insert_case_4.svg\")
N is added to left of left child of grandparent, or N is added to right\r\n * of right child of grandparent ({@link XTreeNode.parent P} is red and\r\n * {@link XTreeNode.uncle U} is black).
\r\n *\r\n *The parent {@link XTreeNode.parent P} is red but the uncle\r\n * {@link XTreeNode.uncle U} is black, the current node N\r\n * is the left child of {@link XTreeNode.parent P}, and {@link XTreeNode.parent P} is the left\r\n * child of its parent {@link XTreeNode.grand_parent G}.
\r\n *\r\n *In this case, a right rotation on {@link XTreeNode.grand_parent G} is performed; the result is a\r\n * tree where the former parent {@link XTreeNode.parent P} is now the parent of both the current node\r\n * N and the former grandparent {@link XTreeNode.grand_parent G}.
\r\n *\r\n *{@link XTreeNode.grand_parent G} is known to be black, since its\r\n * former child {@link XTreeNode.parent P} could not have been red otherwise\r\n * (without violating property 4). Then, the colors of {@link XTreeNode.parent P} and\r\n * {@link XTreeNode.grand_parent G} are switched, and the resulting tree satisfies property 4 (both\r\n * children of every red node are black). Property 5\r\n * (all paths from any given node to its leaf nodes contain the same number of\r\n * black nodes) also remains satisfied, since all paths that went through any\r\n * of these three nodes went through {@link XTreeNode.grand_parent G} before, and now they all go\r\n * through {@link XTreeNode.parent P}. In each case, this is the only\r\n * black node of the three.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_insert_case_5.svg\")
Erase an element with its node.
\r\n *\r\n *In a regular binary search tree when deleting a node with two non-leaf children, we find either the\r\n * maximum element in its left subtree (which is the in-order predecessor) or the minimum element in its\r\n * right subtree (which is the in-order successor) and move its value into the node being deleted (as shown\r\n * here). We then delete the node we copied the value from, which must have fewer than two non-leaf children.\r\n * (Non-leaf children, rather than all children, are specified here because unlike normal binary search\r\n * trees, red-black trees can have leaf nodes anywhere, so that all nodes are either internal nodes with\r\n * two children or leaf nodes with, by definition, zero children. In effect, internal nodes having two leaf\r\n * children in a red-black tree are like the leaf nodes in a regular binary search tree.) Because merely\r\n * copying a value does not violate any red-black properties, this reduces to the problem of deleting a node\r\n * with at most one non-leaf child. Once we have solved that problem, the solution applies equally to the\r\n * case where the node we originally want to delete has at most one non-leaf child as to the case just\r\n * considered where it has two non-leaf children.
\r\n *\r\n *Therefore, for the remainder of this discussion we address the deletion of a node with at most one\r\n * non-leaf child. We use the label M to denote the node to be deleted; C will denote a\r\n * selected child of M, which we will also call \"its child\". If M does have a non-leaf child,\r\n * call that its child, C; otherwise, choose either leaf as its child, C.
\r\n *\r\n *If M is a red node, we simply replace it with its child C,\r\n * which must be black by property 4. (This can only occur when M has\r\n * two leaf children, because if the red node M had a\r\n * black non-leaf child on one side but just a leaf child on the other side,\r\n * then the count of black nodes on both sides would be different, thus the\r\n * tree would violate property 5.) All paths through the deleted node will simply pass through one fewer\r\n * red node, and both the deleted node's parent and child must be\r\n * black, so property 3 (all leaves are black)\r\n * and property 4 (both children of every red node are\r\n * black) still hold.
\r\n *\r\n *Another simple case is when M is black and C is\r\n * red. Simply removing a black node could break\r\n * Properties 4 (“Both children of every red node are\r\n * black”) and 5 (“All paths from any given node to its leaf nodes contain the\r\n * same number of black nodes”), but if we repaint C\r\n * black, both of these properties are preserved.
\r\n *\r\n *The complex case is when both M and C are black. (This\r\n * can only occur when deleting a black node which has two leaf children,\r\n * because if the black node M had a black\r\n * non-leaf child on one side but just a leaf child on the other side, then the count of\r\n * black nodes on both sides would be different, thus the tree would have been\r\n * an invalid red-black tree by violation of property 5.) We begin by replacing M with its child\r\n * C. We will relabel this child C (in its new position) N, and its sibling (its\r\n * new parent's other child) {@link XTreeNode.sibling S}. ({@link XTreeNode.sibling S} was\r\n * previously the sibling of M.)
\r\n *\r\n *In the diagrams below, we will also use {@link XTreeNode.parent P} for N's new\r\n * parent (M's old parent), SL for {@link XTreeNode.sibling S}'s left child, and\r\n * SR for {@link XTreeNode.sibling S}'s right child ({@link XTreeNode.sibling S} cannot\r\n * be a leaf because if M and C were black, then\r\n * {@link XTreeNode.parent P}'s one subtree which included M counted two\r\n * black-height and thus {@link XTreeNode.parent P}'s other subtree\r\n * which includes {@link XTreeNode.sibling S} must also count two\r\n * black-height, which cannot be the case if {@link XTreeNode.sibling S}\r\n * is a leaf node).
\r\n *\r\n *Notes
\r\n *- \r\n *\t
- \r\n *\t\tThe label N will be used to denote the current node (colored\r\n *\t\tblack). In the diagrams N carries a blue contour. At the\r\n *\t\tbeginning, this is the replacement node and a leaf, but the entire procedure may also be applied\r\n *\t\trecursively to other nodes (see case 3). In between some cases, the roles and labels of the nodes\r\n *\t\tare exchanged, but in each case, every label continues to represent the same node it represented at\r\n *\t\tthe beginning of the case.\r\n *\t \r\n *\t
- \r\n *\t\tIf a node in the right (target) half of a diagram carries a blue contour it will become the current\r\n *\t\tnode in the next iteration and there the other nodes will be newly assigned relative to it. Any\r\n *\t\tcolor shown in the diagram is either assumed in its case or implied by those assumptions.\r\n *\t\tWhite represents an arbitrary color (either red or\r\n *\t\tblack), but the same in both halves of the diagram.\r\n *\t \r\n *\t
- \r\n *\t\tA numbered triangle represents a subtree of unspecified depth. A black\r\n *\t\tcircle atop a triangle means that black-height of subtree is greater\r\n *\t\tby one compared to subtree without this circle.\r\n *\t \r\n *
If both N and its original parent are black, then\r\n * deleting this original parent causes paths which proceed through N to have one fewer\r\n * black node than paths that do not. As this violates property 5 (all paths\r\n * from any given node to its leaf nodes contain the same number of black\r\n * nodes), the tree must be rebalanced. There are several cases to consider:
\r\n *\r\n *- \r\n *\t
- N is the new root. \r\n *\t
- {@link XTreeNode.sibling S} is red. \r\n *\t
- \r\n *\t\t{@link XTreeNode.parent P}, {@link XTreeNode.sibling S}, and\r\n *\t\t{@link XTreeNode.sibling S}'s children are black. \r\n *\t
- \r\n *\t\t{@link XTreeNode.sibling S} and {@link XTreeNode.sibling S}'s children are\r\n *\t\tblack, but {@link XTreeNode.parent P} is\r\n *\t\tred.\r\n *\t \r\n *\t
- \r\n *\t\t{@link XTreeNode.sibling S} is black,\r\n *\t\t{@link XTreeNode.sibling S}'s left child is red,\r\n *\t\t{@link XTreeNode.sibling S}'s right child is black, and\r\n *\t\tN is the left child of its parent.\r\n *\t \r\n *\t
- \r\n *\t\t{@link XTreeNode.sibling S} is black,\r\n *\t\t{@link XTreeNode.sibling S}'s right child is red, and\r\n *\t\tN is the left child of its parent {@link XTreeNode.parent P}.\r\n *\t \r\n *
Again, the function calls all use tail recursion, so the algorithm is in-place.
\r\n *\r\n *In the algorithm above, all cases are chained in order, except in delete case 3 where it can recurse\r\n * to case 1 back to the parent node: this is the only case where an iterative implementation will\r\n * effectively loop. No more than h loops back to case 1 will occur (where h is the height of the tree).\r\n * And because the probability for escalation decreases exponentially with each iteration the average\r\n * removal cost is constant.
\r\n *\r\n *Additionally, no tail recursion ever occurs on a child node, so the tail recursion loop can only\r\n * move from a child back to its successive ancestors. If a rotation occurs in case 2 (which is the only\r\n * possibility of rotation within the loop of cases 1–3), then the parent of the node N\r\n * becomes red after the rotation and we will exit the loop. Therefore, at most one\r\n * rotation will occur within this loop. Since no more than two additional rotations will occur after\r\n * exiting the loop, at most three rotations occur in total.
\r\n *\r\n * @param val An element to erase.\r\n */\r\n XTree.prototype.erase = function (val) {\r\n var node = this.find(val);\r\n if (node == null || this.is_equals(val, node.value) == false)\r\n return;\r\n if (node.left != null && node.right != null) {\r\n var pred = this.fetch_maximum(node.left);\r\n node.value = pred.value;\r\n node = pred;\r\n }\r\n var child = (node.right == null) ? node.left : node.right;\r\n if (this.fetch_color(node) == base.Color.BLACK) {\r\n node.color = this.fetch_color(child);\r\n this.erase_case1(node);\r\n }\r\n this.replace_node(node, child);\r\n };\r\n /**\r\n *N is the new root.
\r\n *\r\n *In this case, we are done. We removed one black node from every path,\r\n * and the new root is black, so the properties are preserved.
\r\n *\r\n *Note
\r\n *In cases 2, 5, and 6, we assume N is the left child of its parent\r\n * {@link XTreeNode.parent P}. If it is the right child, left and right should be reversed throughout\r\n * these three cases. Again, the code examples take both cases into account.
\r\n *\r\n * @param N A node to be erased or swapped.\r\n */\r\n XTree.prototype.erase_case1 = function (N) {\r\n if (N.parent == null)\r\n return;\r\n else\r\n this.erase_case2(N);\r\n };\r\n /**\r\n *{@link XTreeNode.sibling S} is red.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_delete_case_2.svg\")
In this case we reverse the colors of {@link XTreeNode.parent P} and\r\n * {@link XTreeNode.sibling S}, and then rotate left at {@link XTreeNode.parent P}, turning\r\n * {@link XTreeNode.sibling S} into N's grandparent.
\r\n *\r\n *Note that {@link XTreeNode.parent P} has to be black as it had a\r\n * red child. The resulting subtree has a path short one\r\n * black node so we are not done. Now N has a\r\n * black sibling and a red parent, so we can proceed\r\n * to step 4, 5, or 6. (Its new sibling is black because it was once the child\r\n * of the red {@link XTreeNode.sibling S}.) In later cases, we will re-label\r\n * N's new sibling as {@link XTreeNode.sibling S}.
\r\n *\r\n * @param N A node to be erased or swapped.\r\n */\r\n XTree.prototype.erase_case2 = function (N) {\r\n if (this.fetch_color(N.sibling) == base.Color.RED) {\r\n N.parent.color = base.Color.RED;\r\n N.sibling.color = base.Color.BLACK;\r\n if (N == N.parent.left)\r\n this.rotate_left(N.parent);\r\n else\r\n this.rotate_right(N.parent);\r\n }\r\n this.erase_case3(N);\r\n };\r\n /**\r\n *{@link XTreeNode.parent P}, {@link XTreeNode.sibling S}, and {@link XTreeNode.sibling\r\n * S}'s children are black.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_delete_case_3.svg\")
In this case, we simply repaint {@link XTreeNode.sibling S} red. The\r\n * result is that all paths passing through {@link XTreeNode.sibling S}, which are precisely those\r\n * paths not passing through N, have one less black node.\r\n * Because deleting N's original parent made all paths passing through N have\r\n * one less black node, this evens things up.
\r\n *\r\n *However, all paths through {@link XTreeNode.parent P} now have one fewer\r\n * black node than paths that do not pass through\r\n * {@link XTreeNode.parent P}, so property 5 (all paths from any given node to its leaf nodes contain\r\n * the same number of black nodes) is still violated.
\r\n *\r\n *To correct this, we perform the rebalancing procedure on {@link XTreeNode.parent P}, starting\r\n * at case 1.
\r\n *\r\n * @param N A node to be erased or swapped.\r\n */\r\n XTree.prototype.erase_case3 = function (N) {\r\n if (this.fetch_color(N.parent) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling.left) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling.right) == base.Color.BLACK) {\r\n N.sibling.color = base.Color.RED;\r\n this.erase_case1(N.parent);\r\n }\r\n else\r\n this.erase_case4(N);\r\n };\r\n /**\r\n *{@link XTreeNode.sibling S} and {@link XTreeNode.sibling S}'s children are\r\n * black, but {@link XTreeNode.parent P} is red.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_delete_case_4.svg\")
In this case, we simply exchange the colors of {@link XTreeNode.sibling S} and\r\n * {@link XTreeNode.parent P}. This does not affect the number of black\r\n * nodes on paths going through {@link XTreeNode.sibling S}, but it does add one to the number of\r\n * black nodes on paths going through N, making up for the\r\n * deleted black node on those paths.
\r\n *\r\n * @param N A node to be erased or swapped.\r\n */\r\n XTree.prototype.erase_case4 = function (N) {\r\n if (this.fetch_color(N.parent) == base.Color.RED &&\r\n N.sibling != null &&\r\n this.fetch_color(N.sibling) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling.left) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling.right) == base.Color.BLACK) {\r\n N.sibling.color = base.Color.RED;\r\n N.parent.color = base.Color.BLACK;\r\n }\r\n else\r\n this.erase_case5(N);\r\n };\r\n /**\r\n *{@link XTreeNode.sibling S} is black, {@link XTreeNode.sibling S}'s\r\n * left child is red, {@link XTreeNode.sibling S}'s right child is\r\n * black, and N is the left child of its parent.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_delete_case_5.svg\")
In this case we rotate right at {@link XTreeNode.sibling S}, so that\r\n * {@link XTreeNode.sibling S}'s left child becomes {@link XTreeNode.sibling S}'s parent and\r\n * N's new sibling. We then exchange the colors of {@link XTreeNode.sibling S} and its\r\n * new parent.
\r\n *\r\n *All paths still have the same number of black nodes, but now\r\n * N has a black sibling whose right child is\r\n * red, so we fall into case 6. Neither N nor its parent are affected\r\n * by this transformation. (Again, for case 6, we relabel N's new sibling as\r\n * {@link XTreeNode.sibling S}.)
\r\n *\r\n * @param N A node to be erased or swapped.\r\n */\r\n XTree.prototype.erase_case5 = function (N) {\r\n if (N == N.parent.left &&\r\n N.sibling != null &&\r\n this.fetch_color(N.sibling) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling.left) == base.Color.RED &&\r\n this.fetch_color(N.sibling.right) == base.Color.BLACK) {\r\n N.sibling.color = base.Color.RED;\r\n N.sibling.left.color = base.Color.BLACK;\r\n this.rotate_right(N.sibling);\r\n }\r\n else if (N == N.parent.right &&\r\n N.sibling != null &&\r\n this.fetch_color(N.sibling) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling.left) == base.Color.BLACK &&\r\n this.fetch_color(N.sibling.right) == base.Color.RED) {\r\n N.sibling.color = base.Color.RED;\r\n N.sibling.right.color = base.Color.BLACK;\r\n this.rotate_left(N.sibling);\r\n }\r\n };\r\n /**\r\n *{@link XTreeNode.sibling S} is black,\r\n * {@link XTreeNode.sibling S}'s right child is red, and N is\r\n * the left child of its parent {@link XTreeNode.parent P}.
\r\n *\r\n *In this case we rotate left at {@link XTreeNode.parent P}, so that\r\n * {@link XTreeNode.sibling S} becomes the parent of {@link XTreeNode.parent P} and\r\n * {@link XTreeNode.sibling S}'s right child. We then exchange the colors of\r\n * {@link XTreeNode.parent P} and {@link XTreeNode.sibling S}, and make\r\n * {@link XTreeNode.sibling S}'s right child black.
\r\n *\r\n *The subtree still has the same color at its root, so Properties 4 (Both children of every\r\n * red node are black) and 5 (All paths from any\r\n * given node to its leaf nodes contain the same number of black nodes) are\r\n * not violated. However, N now has one additional black\r\n * ancestor: either {@link XTreeNode.parent P} has become black, or it\r\n * was black and {@link XTreeNode.sibling S} was added as a\r\n * black grandparent.
\r\n *\r\n *Thus, the paths passing through N pass through one additional\r\n * black node.
\r\n *\r\n * ![](\"../assets/images/tree/Red-black_tree_delete_case_6.svg\")
Meanwhile, if a path does not go through N, then there are two possibilities:
\r\n *- \r\n *\t
- \r\n *\t\tIt goes through N's new sibling SL, a node with arbitrary color and the root of\r\n *\t\tthe subtree labeled 3 (s. diagram). Then, it must go through {@link XTreeNode.sibling S} and\r\n *\t\t{@link XTreeNode.parent P}, both formerly and currently, as they have only exchanged colors\r\n *\t\tand places. Thus the path contains the same number of black nodes.\r\n *\t \r\n *\t
- \r\n *\t\tIt goes through N's new uncle, {@link XTreeNode.sibling S}'s right child. Then,\r\n *\t\tit formerly went through {@link XTreeNode.sibling S}, {@link XTreeNode.sibling S}'s\r\n *\t\tparent, and {@link XTreeNode.sibling S}'s right child SR (which was\r\n *\t\tred), but now only goes through {@link XTreeNode.sibling S}, which\r\n *\t\thas assumed the color of its former parent, and {@link XTreeNode.sibling S}'s right child,\r\n *\t\twhich has changed from red to black (assuming\r\n *\t\t{@link XTreeNode.sibling S}'s color: black). The net effect is\r\n *\t\tthat this path goes through the same number of black nodes.\r\n *\t \r\n *
Either way, the number of black nodes on these paths does not change.\r\n * Thus, we have restored Properties 4 (Both children of every red node are\r\n * black) and 5 (All paths from any given node to its leaf nodes contain the\r\n * same number of black nodes). The white node in the diagram can be either\r\n * red or black, but must refer to the same color\r\n * both before and after the transformation.
\r\n *\r\n * @param N A node to be erased or swapped.\r\n */\r\n XTree.prototype.erase_case6 = function (node) {\r\n node.sibling.color = this.fetch_color(node.parent);\r\n node.parent.color = base.Color.BLACK;\r\n if (node == node.parent.left) {\r\n node.sibling.right.color = base.Color.BLACK;\r\n this.rotate_left(node.parent);\r\n }\r\n else {\r\n node.sibling.left.color = base.Color.BLACK;\r\n this.rotate_right(node.parent);\r\n }\r\n };\r\n /* ---------------------------------------------------------\r\n ROTATION\r\n --------------------------------------------------------- */\r\n /**\r\n * Rotate a node left.\r\n *\r\n * @param node Node to rotate left.\r\n */\r\n XTree.prototype.rotate_left = function (node) {\r\n var right = node.right;\r\n this.replace_node(node, right);\r\n node.right = right.left;\r\n if (right.left != null)\r\n right.left.parent = node;\r\n right.left = node;\r\n node.parent = right;\r\n };\r\n /**\r\n * Rotate a node to right.\r\n *\r\n * @param node A node to rotate right.\r\n */\r\n XTree.prototype.rotate_right = function (node) {\r\n var left = node.left;\r\n this.replace_node(node, left);\r\n node.left = left.right;\r\n if (left.right != null)\r\n left.right.parent = node;\r\n left.right = node;\r\n node.parent = left;\r\n };\r\n /**\r\n * Replace a node.\r\n *\r\n * @param oldNode Ordinary node to be replaced.\r\n * @param newNode Target node to replace.\r\n */\r\n XTree.prototype.replace_node = function (oldNode, newNode) {\r\n if (oldNode.parent == null)\r\n this.root_ = newNode;\r\n else {\r\n if (oldNode == oldNode.parent.left)\r\n oldNode.parent.left = newNode;\r\n else\r\n oldNode.parent.right = newNode;\r\n }\r\n if (newNode != null)\r\n newNode.parent = oldNode.parent;\r\n };\r\n /* ---------------------------------------------------------\r\n COLOR\r\n --------------------------------------------------------- */\r\n /**\r\n * Fetch color from a node.\r\n *\r\n * @param node A node to fetch color.\r\n * @retur color.\r\n */\r\n XTree.prototype.fetch_color = function (node) {\r\n if (node == null)\r\n return base.Color.BLACK;\r\n else\r\n return node.color;\r\n };\r\n return XTree;\r\n }());\r\n base.XTree = XTree;\r\n })(base = std.base || (std.base = {}));\r\n})(std || (std = {}));\r\n///Static class holding enumeration codes of color of Red-black tree.
\r\n *\r\n *Color codes imposed to nodes of RB-Tree are following those rules:
\r\n *\r\n *- \r\n *\t
- A node is either red or black. \r\n *\t
- The root is black. This rule is sometimes omitted. Since the root can\r\n *\t\t always be changed from red to black, but not\r\n *\t\t necessarily vice versa, this rule has little effect on analysis. \r\n *\t
- All leaves (NIL;
null) are black. \r\n * - If a node is red, then both its children are\r\n *\t\t black. \r\n *
- Every path from a given node to any of its descendant NIL nodes contains the same number of\r\n *\t\t black nodes. Some definitions: the number of\r\n *\t\t black nodes from the root to a node is the node's\r\n *\t\t black depth; the uniform number of black\r\n *\t\t nodes in all paths from root to the leaves is called the black-height of\r\n *\t\t the red-black tree. \r\n *
Code of color black.
\r\n *\r\n *- \r\n *\t
- Those are clearly black: root, leaf nodes or children nodes of red. \r\n *\t
- Every path from a given nodes containes the same number of black nodes exclude NIL(s). \r\n *
Code of color red.
\r\n */\r\n Color[Color[\"RED\"] = 1] = \"RED\";\r\n })(base.Color || (base.Color = {}));\r\n var Color = base.Color;\r\n })(base = std.base || (std.base = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var base;\r\n (function (base) {\r\n /**\r\n *An abstract error instance.
\r\n *\r\n *{@link ErrorInstance} is an abstract class of {@link ErrorCode} and {@link ErrorCondition}\r\n * holding an error instance's identifier {@link value}, associated with a {@link category}.
\r\n *\r\n *The operating system and other low-level applications and libraries generate numerical error codes to\r\n * represent possible results. These numerical values may carry essential information for a specific platform,\r\n * but be non-portable from one platform to another.
\r\n *\r\n *Objects of this class associate such numerical codes to {@link ErrorCategory error categories},\r\n * so that they can be interpreted when needed as more abstract (and portable)\r\n * {@link ErrorCondition error conditions}.
\r\n *\r\n * @author Jeongho NamAssign error instance.
\r\n *\r\n *Assigns the {@link ErrorCode} object a value of val associated with the {@link ErrorCategory}.
\r\n *\r\n * @param val A numerical value identifying an error instance.\r\n * @param category A reference to an {@link ErrorCategory} object.\r\n */\r\n ErrorInstance.prototype.assign = function (val, category) {\r\n this.category_ = category;\r\n this.value_ = val;\r\n };\r\n /**\r\n *Clear error instance.
\r\n *\r\n *Clears the value in the {@link ErrorCode} object so that it is set to a value of 0 of the\r\n * {@link ErrorCategory.systemCategory ErrorCategory.systemCategory()} (indicating no error).
\r\n */\r\n ErrorInstance.prototype.clear = function () {\r\n this.value_ = 0;\r\n };\r\n /* ---------------------------------------------------------\r\n ACCESSORS\r\n --------------------------------------------------------- */\r\n /**\r\n *Get category.
\r\n *\r\n *Returns a reference to the {@link ErrorCategory} associated with the {@link ErrorCode} object.
\r\n *\r\n * @return A reference to a non-copyable object of a type derived from {@link ErrorCategory}.\r\n */\r\n ErrorInstance.prototype.category = function () {\r\n return this.category_;\r\n };\r\n /**\r\n *Error value.
\r\n *\r\n *Returns the error value associated with the {@link ErrorCode} object.
\r\n *\r\n * @return The error value.\r\n */\r\n ErrorInstance.prototype.value = function () {\r\n return this.value_;\r\n };\r\n /**\r\n *Get message.
\r\n *\r\n *Returns the message associated with the error instance.
\r\n *\r\n *Error messages are defined by the {@link category} the error instance belongs to.
\r\n *\r\n *This function returns the same as if the following member was called:
\r\n *\r\n * category().message(value())
Default error condition.
\r\n *\r\n *Returns the default {@link ErrorCondition}object associated with the {@link ErrorCode} object.
\r\n *\r\n *This function returns the same as if the following member was called:
\r\n *\r\n * category().default_error_condition(value())
{@link ErrorCategory.default_error_condition ErrorCategory.default_error_condition()}\r\n * is a virtual member function, that can operate differently for each category.
\r\n *\r\n * @return An {@link ErrorCondition}object that corresponds to the {@link ErrorCode} object.\r\n */\r\n ErrorInstance.prototype.default_error_condition = function () {\r\n if (this.category_ == null || this.value_ == 0)\r\n return null;\r\n else\r\n return this.category_.default_error_condition(this.value_);\r\n };\r\n /* ---------------------------------------------------------\r\n OPERATORS\r\n --------------------------------------------------------- */\r\n /**\r\n *Convert to bool.
\r\n *\r\n *Returns whether the error instance has a numerical {@link value} other than 0.
\r\n *\r\n *If it is zero (which is generally used to represent no error), the function returns false, otherwise it returns true.
\r\n *\r\n * @returntrue if the error's numerical value is not zero.\r\n *\t\t false otherwise.\r\n */\r\n ErrorInstance.prototype.to_bool = function () {\r\n return this.value_ != 0;\r\n };\r\n return ErrorInstance;\r\n }());\r\n base.ErrorInstance = ErrorInstance;\r\n })(base = std.base || (std.base = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var base;\r\n (function (base) {\r\n base.MIN_SIZE = 10;\r\n base.RATIO = 0.8;\r\n base.MAX_RATIO = 2.0;\r\n function code(par) {\r\n var type = typeof par;\r\n if (type == \"number\")\r\n return code_of_number(par);\r\n else if (type == \"string\")\r\n return code_of_string(par);\r\n else\r\n return code_of_object(par);\r\n }\r\n base.code = code;\r\n /**\r\n * @hidden\r\n */\r\n function code_of_number(val) {\r\n // ------------------------------------------\r\n //\tIN C++\r\n //\t\tCONSIDER A NUMBER AS A STRING\r\n //\t\tHASHHask buckets.
\r\n *\r\n * @author Jeongho NamA node in an XTree.
\r\n *\r\n * @param- ???.insert(...)\r\n // list.insert(list.end(), 5, 1)\r\n var fn = std.bind(std.List.prototype.insert);\r\n fn(list, list.end(), 5, 1);\r\n debug_list();\r\n var fn2 = std.bind(std.List.prototype.clear);\r\n fn2(list);\r\n debug_list();\r\n //
- empty() \r\n *\t
- size() \r\n *\t
- front() \r\n *\t
- push_back() \r\n *\t
- pop_back() \r\n *
- Reference: http://www.cplusplus.com/reference/system_error/system_error/\r\n *
- Reference: http://www.cplusplus.com/reference/system_error/error_category/ \r\n *
- Reference: http://www.cplusplus.com/reference/system_error/error_condition/ \r\n *
- Reference: http://www.cplusplus.com/reference/system_error/error_code/ \r\n *
- ???.insert(_1, _2, 5, _3)\r\n // list.insert(list.end(), 5, 2)\r\n var fn3 = std.bind(list.insert, std.placeholders._1, std.placeholders._2, 5, std.placeholders._3);\r\n fn3(list, list.end(), 2);\r\n debug_list();\r\n function debug_list() {\r\n console.log(\"#\" + list.size());\r\n for (var it = list.begin(); !it.equal_to(list.end()); it = it.next())\r\n console.log(it.value);\r\n console.log(\"----------------------------------------------------------\");\r\n }\r\n }\r\n example.test_bind = test_bind;\r\n })(example = std.example || (std.example = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var example;\r\n (function (example) {\r\n function test_deque() {\r\n var deque = new std.Deque();\r\n for (var i = 0; i < 10; i++)\r\n deque.push_back(i);\r\n var it = deque.begin().advance(3);\r\n it = deque.erase(it); // erase 3\r\n console.log(it.value); // print 4\r\n it = deque.begin().advance(2);\r\n it = deque.insert(it, -1); // insert -1\r\n console.log(it.next().value); // print 2\r\n it = deque.begin().advance(6);\r\n it = deque.erase(it, it.advance(3)); // erase from 6 to 9\r\n //console.log(it.value); // print 9\r\n console.log(it.equal_to(deque.end()));\r\n console.log(\"-------------------------------------\");\r\n for (var it_1 = deque.begin(); !it_1.equal_to(deque.end()); it_1 = it_1.next())\r\n console.log(it_1.value);\r\n }\r\n example.test_deque = test_deque;\r\n })(example = std.example || (std.example = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var example;\r\n (function (example) {\r\n function test_for_each() {\r\n var array = new std.Vector();\r\n for (var i = 0; i < 20; i++)\r\n array.push_back(i);\r\n var fn = std.for_each(array.begin(), array.end(), function (val) { console.log(val); });\r\n }\r\n example.test_for_each = test_for_each;\r\n })(example = std.example || (std.example = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var example;\r\n (function (example) {\r\n function test_hash_map() {\r\n /////////////////////////////////////\r\n // CONSTRUCT DATA FROM 1 TO 10\r\n /////////////////////////////////////\r\n var map = new std.HashMap();\r\n for (var i = 0; i < 10; i++)\r\n map.insert([i, \"Its key is \" + i]);\r\n /////////////////////////////////////\r\n // ELEMENT I/O\r\n /////////////////////////////////////\r\n //// ERASE AN ELEMENT\r\n var it = map.find(3); // find 3.\r\n it = map.erase(it); // erase 3. [it] points key 4.\r\n console.log(it.first); // prints key 4.\r\n // INSERT AN ELEMENT\r\n it = map.begin().advance(2); // [it] points key 2 (0 ----> 2)\r\n it = map.insert(it, [-1, \"Its key is -1\"]);\r\n // [it] points key -1=\r\n // key list: [0, 1, -1, 2, 4, 5, 6, 7, 8, 9]\r\n console.log(it.next().first); // prints 2, next of [it] (-1 -> 2)\r\n // RANGE ERASER\r\n var px = map.begin().advance(6);\r\n var py = map.begin().advance(9);\r\n it = map.erase(map.begin().advance(6), map.begin().advance(9));\r\n // erase elements from 6th until 9th.\r\n // INSPECT ELEMENTS BY THEIR KEY\r\n // key list: [0, 1, -1, 2, 4, 5, 9]\r\n console.log(\"has 7:\", map.has(7));\r\n console.log(\"count 5:\", map.count(5));\r\n console.log(\"it is end():\", it.equal_to(map.end()));\r\n /////////////////////////////////////\r\n // PRINT ALL ELEMENTS\r\n /////////////////////////////////////\r\n console.log(\"------------------------------\");\r\n // key list: [0, 1, -1, 2, 4, 5, 9]\r\n for (var it_2 = map.begin(); !it_2.equal_to(map.end()); it_2 = it_2.next())\r\n console.log(it_2.second);\r\n /* OUTPUT\r\n =========================================\r\n 4\r\n 2\r\n has 7: true\r\n count 5: 1\r\n it is end(): false\r\n ------------------------------\r\n Its key is 0\r\n Its key is 1\r\n Its key is -1\r\n Its key is 2\r\n Its key is 4\r\n Its key is 5\r\n Its key is 9\r\n =========================================\r\n */\r\n }\r\n example.test_hash_map = test_hash_map;\r\n })(example = std.example || (std.example = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var example;\r\n (function (example) {\r\n function test_list() {\r\n var list = new std.List();\r\n for (var i = 0; i < 10; i++)\r\n list.push_back(i);\r\n var it = list.begin().advance(3);\r\n it = list.erase(it); // erase 3\r\n console.log(it.value); // print 4\r\n it = list.begin().advance(2);\r\n it = list.insert(it, -1); // insert -1\r\n console.log(it.next().value); // print 2\r\n it = list.begin().advance(6);\r\n it = list.erase(it, it.advance(3)); // erase from 6 to 9\r\n //console.log(it.value); // print 9\r\n console.log(it.equal_to(list.end()));\r\n console.log(\"-------------------------------------\");\r\n for (var it_3 = list.begin(); !it_3.equal_to(list.end()); it_3 = it_3.next())\r\n console.log(it_3.value);\r\n }\r\n example.test_list = test_list;\r\n })(example = std.example || (std.example = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var example;\r\n (function (example) {\r\n function sorting() {\r\n var cubes = new std.Deque();\r\n for (var i = 0; i < 10; i++)\r\n cubes.push_back(new Cube());\r\n ///////////////////////////////\r\n // SORT BY Cube.less()\r\n ///////////////////////////////\r\n std.sort(cubes.begin(), cubes.end());\r\n for (var it = cubes.begin(); !it.equal_to(cubes.end()); it = it.next())\r\n it.value.debug_size();\r\n console.log(\"------------------------------\");\r\n ///////////////////////////////\r\n // SORT BY inline function\r\n ///////////////////////////////\r\n std.sort(cubes.begin(), cubes.end(), function (left, right) {\r\n if (left.x != right.x)\r\n return left.x < right.x;\r\n else if (left.y != right.y)\r\n return left.y < right.y;\r\n else\r\n return left.z < right.z;\r\n });\r\n for (var it = cubes.begin(); !it.equal_to(cubes.end()); it = it.next())\r\n it.value.debug_position();\r\n }\r\n example.sorting = sorting;\r\n var Cube = (function () {\r\n function Cube() {\r\n this.width = Math.random() * 10;\r\n this.height = Math.random() * 10;\r\n this.length = Math.random() * 10;\r\n this.x = Math.random() * 100 - 50;\r\n this.y = Math.random() * 100 - 50;\r\n this.z = Math.random() * 100 - 50;\r\n }\r\n Object.defineProperty(Cube.prototype, \"volume\", {\r\n get: function () {\r\n return this.width * this.height * this.length;\r\n },\r\n enumerable: true,\r\n configurable: true\r\n });\r\n Cube.prototype.less = function (obj) {\r\n return this.volume < obj.volume;\r\n };\r\n Cube.prototype.debug_size = function () {\r\n console.log(this.width, this.height, this.length + \" => \" + this.volume);\r\n };\r\n Cube.prototype.debug_position = function () {\r\n console.log(this.x, this.y, this.z);\r\n };\r\n return Cube;\r\n }());\r\n })(example = std.example || (std.example = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n var example;\r\n (function (example) {\r\n function tree_set() {\r\n var set = new std.TreeMultiSet();\r\n // INSERTS EVEN NUMBERS\r\n for (var i = 0; i <= 10; i += 2)\r\n for (var j = 0; j < 3; j++)\r\n set.insert(i);\r\n // FIND 4 -> HAS\r\n console.log(\"Matched node: 4\");\r\n console.log(\"\tlower bound: \" + set.lower_bound(4).value);\r\n console.log(\"\tupper bound: \" + set.upper_bound(4).value);\r\n console.log(\" \");\r\n // FIND ODD NUMBERS -> NOT EXIST\r\n for (var i = 1; i <= 10; i += 2) {\r\n console.log(\"Mis-matched node: \" + i);\r\n console.log(\"\tlower bound: \" + set.lower_bound(i).value);\r\n console.log(\"\tupper bound: \" + set.upper_bound(i).value);\r\n console.log(\" \");\r\n }\r\n }\r\n example.tree_set = tree_set;\r\n })(example = std.example || (std.example = {}));\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n /**\r\n * Default hash function.\r\n *\r\n * @param obj\r\n */\r\n function hash(obj) {\r\n return std.base.code(obj);\r\n }\r\n std.hash = hash;\r\n /**\r\n * Incremental sequence of unique id for objects.\r\n */\r\n var __s_iUID = 0;\r\n Object.defineProperties(Object.prototype, {\r\n \"__getUID\": {\r\n value: function () {\r\n if (this.hasOwnProperty(\"__m_iUID\") == false) {\r\n var uid = ++__s_iUID;\r\n Object.defineProperty(this, \"__m_iUID\", {\r\n \"get\": function () {\r\n return uid;\r\n }\r\n });\r\n }\r\n return this.__m_iUID;\r\n }\r\n }\r\n });\r\n})(std || (std = {}));\r\nvar std;\r\n(function (std) {\r\n /**\r\n *
Priority queue.
\r\n *\r\n *{@link PriorityQueue Priority queues} are a type of container adaptors, specifically designed such that its\r\n * first element is always the greatest of the elements it contains, according to some strict weak ordering\r\n * criterion.
\r\n *\r\n *This context is similar to a heap, where elements can be inserted at any moment, and only the\r\n * max heap element can be retrieved (the one at the top in the {@link PriorityQueue priority queue}).
\r\n *\r\n *{@link PriorityQueue Priority queues} are implemented as container adaptors, which are classes that\r\n * use an encapsulated object of a specific container class as its {@link container_ underlying container},\r\n * providing a specific set of member functions to access its elements. Elements are popped from the \"back\"\r\n * of the specific container, which is known as the top of the {@link PriorityQueue Priority queue}.
\r\n *\r\n *The {@link container_ underlying container} may be any of the standard container class templates or some\r\n * other specifically designed container class. The container shall be accessible through\r\n * {@link IArrayIterator random access iterators} and support the following operations:
\r\n *\r\n *- \r\n *\t
The standard container classes {@link Vector} and {@link Deque} fulfill these requirements. By default, if\r\n * no container class is specified for a particular {@link PriorityQueue} class instantiation, the standard\r\n * container {@link Vector} is used.
\r\n *\r\n *Support of {@link IArrayIterator random access iterators} is required to keep a heap structure internally\r\n * at all times. This is done automatically by the container adaptor by automatically calling the algorithm\r\n * functions make_heap, push_heap and pop_heap when needed.
\r\n *\r\n * @paramReturn size.
\r\n *\r\n *Returns the number of elements in the {@link PriorityQueue}.
\r\n *\r\n *This member function effectively calls member {@link IArray.size size} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @return The number of elements in the underlying\r\n */\r\n PriorityQueue.prototype.size = function () {\r\n return this.container_.size();\r\n };\r\n /**\r\n *Test whether container is empty.
\r\n *\r\n *Returns whether the {@link PriorityQueue} is empty: i.e. whether its {@link size} is zero.
\r\n *\r\n *This member function effectively calls member {@link IARray.empty empty} of the\r\n * {@link container_ underlying container} object.
\r\n */\r\n PriorityQueue.prototype.empty = function () {\r\n return this.container_.empty();\r\n };\r\n /* ---------------------------------------------------------\r\n ELEMENTS I/O\r\n --------------------------------------------------------- */\r\n /**\r\n *Access top element.
\r\n *\r\n *Returns a constant reference to the top element in the {@link PriorityQueue}.
\r\n *\r\n *The top element is the element that compares higher in the {@link PriorityQueue}, and the next that is\r\n * removed from the container when {@link PriorityQueue.pop} is called.
\r\n *\r\n *This member function effectively calls member {@link IArray.front front} of the\r\n * {@link container_ underlying container} object.
\r\n *\r\n * @return A reference to the top element in the {@link PriorityQueue}.\r\n */\r\n PriorityQueue.prototype.top = function () {\r\n return this.container_.begin().value;\r\n };\r\n /**\r\n *Insert element.
\r\n *\r\n *Inserts a new element in the {@link PriorityQueue}. The content of this new element is initialized to\r\n * val.\r\n *\r\n *
This member function effectively calls the member function {@link IArray.push_back push_back} of the\r\n * {@link container_ underlying container} object, and then reorders it to its location in the heap by calling\r\n * the push_heap algorithm on the range that includes all the elements of the
\r\n *\r\n * @param val Value to which the inserted element is initialized.\r\n */\r\n PriorityQueue.prototype.push = function (val) {\r\n this.container_.insert(val);\r\n };\r\n /**\r\n *Remove top element.
\r\n *\r\n *Removes the element on top of the {@link PriorityQueue}, effectively reducing its {@link size} by one.\r\n * The element removed is the one with the highest (or lowest) value.
\r\n *\r\n *The value of this element can be retrieved before being popped by calling member\r\n * {@link PriorityQueue.top}.
\r\n *\r\n *This member function effectively calls the pop_heap algorithm to keep the heap property of\r\n * {@link PriorityQueue PriorityQueues} and then calls the member function {@link IArray.pop_back pop_back} of\r\n * the {@link container_ underlying container} object to remove the element.
\r\n */\r\n PriorityQueue.prototype.pop = function () {\r\n this.container_.erase(this.container_.begin());\r\n };\r\n /**\r\n *Swap contents.
\r\n *\r\n *Exchanges the contents of the container adaptor by those of obj, swapping both the\r\n * {@link container_ underlying container} value and their comparison function using the corresponding\r\n * {@link std.swap swap} non-member functions (unqualified).
\r\n *\r\n *This member function has a noexcept specifier that matches the combined noexcept of the\r\n * {@link IArray.swap swap} operations on the {@link container_ underlying container} and the comparison\r\n * functions.
\r\n *\r\n * @param obj {@link PriorityQueue} container adaptor of the same type (i.e., instantiated with the same\r\n *\t\t\t template parameters, T). Sizes may differ.\r\n */\r\n PriorityQueue.prototype.swap = function (obj) {\r\n this.container_.swap(obj.container_);\r\n };\r\n return PriorityQueue;\r\n }());\r\n std.PriorityQueue = PriorityQueue;\r\n})(std || (std = {}));\r\n///System error exception.
\r\n *\r\n *This class defines the type of objects thrown as exceptions to report conditions originating during\r\n * runtime from the operating system or other low-level application program interfaces which have an\r\n * associated {@link ErrorCode}.
\r\n *\r\n *The class inherits from {@link RuntimeError}, to which it adds an {@link ErrorCode} as\r\n * member code (and defines a specialized what member).
\r\n *\r\n *- \r\n *
Get error code.
\r\n *\r\n *Returns the {@link ErrorCode} object associated with the exception.
\r\n *\r\n *This value is either the {@link ErrorCode} passed to the construction or its equivalent\r\n * (if constructed with a value and a {@link category}.
\r\n *\r\n * @return The {@link ErrorCode} associated with the object.\r\n */\r\n SystemError.prototype.code = function () {\r\n return this.code_;\r\n };\r\n return SystemError;\r\n }(std.RuntimeError));\r\n std.SystemError = SystemError;\r\n /**\r\n *Error category.
\r\n *\r\n *This type serves as a base class for specific category types.
\r\n *\r\n *Category types are used to identify the source of an error. They also define the relation between\r\n * {@link ErrorCode} and {@link ErrorCondition}objects of its category, as well as the message set for {@link ErrorCode}\r\n * objects.\r\n *\r\n *
Objects of these types have no distinct values and are not-copyable and not-assignable, and thus can only be\r\n * passed by reference. As such, only one object of each of these types shall exist, each uniquely identifying its own\r\n * category: all error codes and conditions of a same category shall return a reference to same object.
\r\n *\r\n *- \r\n *\t
Default error condition.
\r\n *\r\n *Returns the default {@link ErrorCondition}object of this category that is associated with the\r\n * {@link ErrorCode} identified by a value of val.
\r\n *\r\n *Its definition in the base class {@link ErrorCategory} returns the same as constructing an\r\n * {@link ErrorCondition} object with:\r\n *\r\n *
new ErrorCondition(val, *this);
As a virtual member function, this behavior can be overriden in derived classes.
\r\n *\r\n *This function is called by the default definition of member {@link equivalent equivalent()}, which is used to\r\n * compare {@link ErrorCondition error conditions} with error codes.
\r\n *\r\n * @param val A numerical value identifying an error condition.\r\n *\r\n * @return The default {@link ErrorCondition}object associated with condition value val for this category.\r\n */\r\n ErrorCategory.prototype.default_error_condition = function (val) {\r\n return null;\r\n };\r\n ErrorCategory.prototype.equivalent = function () {\r\n var args = [];\r\n for (var _i = 0; _i < arguments.length; _i++) {\r\n args[_i - 0] = arguments[_i];\r\n }\r\n if (args[1] instanceof ErrorCondition) {\r\n var val_code = args[0];\r\n var cond = args[1];\r\n return std.equal_to(this.default_error_condition(val_code), cond);\r\n }\r\n else {\r\n var code = args[0];\r\n var valcond = args[1];\r\n return std.equal_to(this, code.category()) && code.value() == valcond;\r\n }\r\n };\r\n return ErrorCategory;\r\n }());\r\n std.ErrorCategory = ErrorCategory;\r\n /**\r\n *Error condition.
\r\n *\r\n *Objects of this type hold a condition {@link value} associated with a {@link category}.
\r\n *\r\n *Objects of this type describe errors in a generic way so that they may be portable across different\r\n * systems. This is in contrast with {@link ErrorCode} objects, that may contain system-specific\r\n * information.
\r\n *\r\n * Because {@link ErrorCondition}objects can be compared with error_code objects directly by using\r\n * relational operators, {@link ErrorCondition}objects are generally used to check whether\r\n * a particular {@link ErrorCode} obtained from the system matches a specific error condition no matter\r\n * the system.
The {@link ErrorCategory categories} associated with the {@link ErrorCondition} and the\r\n * {@link ErrorCode} define the equivalences between them.
\r\n *\r\n *- \r\n *\t
Error code.
\r\n *\r\n *Objects of this type hold an error code {@link value} associated with a {@link category}.
\r\n *\r\n *The operating system and other low-level applications and libraries generate numerical error codes to\r\n * represent possible results. These numerical values may carry essential information for a specific platform,\r\n * but be non-portable from one platform to another.
\r\n *\r\n *Objects of this class associate such numerical codes to {@link ErrorCategory error categories}, so that they\r\n * can be interpreted when needed as more abstract (and portable) {@link ErrorCondition error conditions}.
\r\n *\r\n *- \r\n *\t