http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/e2cad6e6/externs/GCL/externs/goog/a11y/aria/attributes.js ---------------------------------------------------------------------- diff --git a/externs/GCL/externs/goog/a11y/aria/attributes.js b/externs/GCL/externs/goog/a11y/aria/attributes.js new file mode 100644 index 0000000..f4e0a3d --- /dev/null +++ b/externs/GCL/externs/goog/a11y/aria/attributes.js @@ -0,0 +1,389 @@ +// Copyright 2013 The Closure Library Authors. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS-IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + + +/** + * @fileoverview The file contains generated enumerations for ARIA states + * and properties as defined by W3C ARIA standard: + * http://www.w3.org/TR/wai-aria/. + * + * This is auto-generated code. Do not manually edit! For more details + * about how to edit it via the generator check go/closure-ariagen. + */ + +goog.provide('goog.a11y.aria.AutoCompleteValues'); +goog.provide('goog.a11y.aria.CheckedValues'); +goog.provide('goog.a11y.aria.DropEffectValues'); +goog.provide('goog.a11y.aria.ExpandedValues'); +goog.provide('goog.a11y.aria.GrabbedValues'); +goog.provide('goog.a11y.aria.InvalidValues'); +goog.provide('goog.a11y.aria.LivePriority'); +goog.provide('goog.a11y.aria.OrientationValues'); +goog.provide('goog.a11y.aria.PressedValues'); +goog.provide('goog.a11y.aria.RelevantValues'); +goog.provide('goog.a11y.aria.SelectedValues'); +goog.provide('goog.a11y.aria.SortValues'); +goog.provide('goog.a11y.aria.State'); + + +/** + * ARIA states and properties. + * @enum {string} + */ +goog.a11y.aria.State = { + // ARIA property for setting the currently active descendant of an element, + // for example the selected item in a list box. Value: ID of an element. + ACTIVEDESCENDANT: 'activedescendant', + + // ARIA property that, if true, indicates that all of a changed region should + // be presented, instead of only parts. Value: one of {true, false}. + ATOMIC: 'atomic', + + // ARIA property to specify that input completion is provided. Value: + // one of {'inline', 'list', 'both', 'none'}. + AUTOCOMPLETE: 'autocomplete', + + // ARIA state to indicate that an element and its subtree are being updated. + // Value: one of {true, false}. + BUSY: 'busy', + + // ARIA state for a checked item. Value: one of {'true', 'false', 'mixed', + // undefined}. + CHECKED: 'checked', + + // ARIA property that identifies the element or elements whose contents or + // presence are controlled by this element. + // Value: space-separated IDs of other elements. + CONTROLS: 'controls', + + // ARIA property that identifies the element or elements that describe + // this element. Value: space-separated IDs of other elements. + DESCRIBEDBY: 'describedby', + + // ARIA state for a disabled item. Value: one of {true, false}. + DISABLED: 'disabled', + + // ARIA property that indicates what functions can be performed when a + // dragged object is released on the drop target. Value: one of + // {'copy', 'move', 'link', 'execute', 'popup', 'none'}. + DROPEFFECT: 'dropeffect', + + // ARIA state for setting whether the element like a tree node is expanded. + // Value: one of {true, false, undefined}. + EXPANDED: 'expanded', + + // ARIA property that identifies the next element (or elements) in the + // recommended reading order of content. Value: space-separated ids of + // elements to flow to. + FLOWTO: 'flowto', + + // ARIA state that indicates an element's "grabbed" state in drag-and-drop. + // Value: one of {true, false, undefined}. + GRABBED: 'grabbed', + + // ARIA property indicating whether the element has a popup. + // Value: one of {true, false}. + HASPOPUP: 'haspopup', + + // ARIA state indicating that the element is not visible or perceivable + // to any user. Value: one of {true, false}. + HIDDEN: 'hidden', + + // ARIA state indicating that the entered value does not conform. Value: + // one of {false, true, 'grammar', 'spelling'} + INVALID: 'invalid', + + // ARIA property that provides a label to override any other text, value, or + // contents used to describe this element. Value: string. + LABEL: 'label', + + // ARIA property for setting the element which labels another element. + // Value: space-separated IDs of elements. + LABELLEDBY: 'labelledby', + + // ARIA property for setting the level of an element in the hierarchy. + // Value: integer. + LEVEL: 'level', + + // ARIA property indicating that an element will be updated, and + // describes the types of updates the user agents, assistive technologies, + // and user can expect from the live region. Value: one of {'off', 'polite', + // 'assertive'}. + LIVE: 'live', + + // ARIA property indicating whether a text box can accept multiline input. + // Value: one of {true, false}. + MULTILINE: 'multiline', + + // ARIA property indicating if the user may select more than one item. + // Value: one of {true, false}. + MULTISELECTABLE: 'multiselectable', + + // ARIA property indicating if the element is horizontal or vertical. + // Value: one of {'vertical', 'horizontal'}. + ORIENTATION: 'orientation', + + // ARIA property creating a visual, functional, or contextual parent/child + // relationship when the DOM hierarchy can't be used to represent it. + // Value: Space-separated IDs of elements. + OWNS: 'owns', + + // ARIA property that defines an element's number of position in a list. + // Value: integer. + POSINSET: 'posinset', + + // ARIA state for a pressed item. + // Value: one of {true, false, undefined, 'mixed'}. + PRESSED: 'pressed', + + // ARIA property indicating that an element is not editable. + // Value: one of {true, false}. + READONLY: 'readonly', + + // ARIA property indicating that change notifications within this subtree + // of a live region should be announced. Value: one of {'additions', + // 'removals', 'text', 'all', 'additions text'}. + RELEVANT: 'relevant', + + // ARIA property indicating that user input is required on this element + // before a form may be submitted. Value: one of {true, false}. + REQUIRED: 'required', + + // ARIA state for setting the currently selected item in the list. + // Value: one of {true, false, undefined}. + SELECTED: 'selected', + + // ARIA property defining the number of items in a list. Value: integer. + SETSIZE: 'setsize', + + // ARIA property indicating if items are sorted. Value: one of {'ascending', + // 'descending', 'none', 'other'}. + SORT: 'sort', + + // ARIA property for slider maximum value. Value: number. + VALUEMAX: 'valuemax', + + // ARIA property for slider minimum value. Value: number. + VALUEMIN: 'valuemin', + + // ARIA property for slider active value. Value: number. + VALUENOW: 'valuenow', + + // ARIA property for slider active value represented as text. + // Value: string. + VALUETEXT: 'valuetext' +}; + + +/** + * ARIA state values for AutoCompleteValues. + * @enum {string} + */ +goog.a11y.aria.AutoCompleteValues = { + // The system provides text after the caret as a suggestion + // for how to complete the field. + INLINE: 'inline', + // A list of choices appears from which the user can choose, + // but the edit box retains focus. + LIST: 'list', + // A list of choices appears and the currently selected suggestion + // also appears inline. + BOTH: 'both', + // No input completion suggestions are provided. + NONE: 'none' +}; + + +/** + * ARIA state values for DropEffectValues. + * @enum {string} + */ +goog.a11y.aria.DropEffectValues = { + // A duplicate of the source object will be dropped into the target. + COPY: 'copy', + // The source object will be removed from its current location + // and dropped into the target. + MOVE: 'move', + // A reference or shortcut to the dragged object + // will be created in the target object. + LINK: 'link', + // A function supported by the drop target is + // executed, using the drag source as an input. + EXECUTE: 'execute', + // There is a popup menu or dialog that allows the user to choose + // one of the drag operations (copy, move, link, execute) and any other + // drag functionality, such as cancel. + POPUP: 'popup', + // No operation can be performed; effectively + // cancels the drag operation if an attempt is made to drop on this object. + NONE: 'none' +}; + + +/** + * ARIA state values for LivePriority. + * @enum {string} + */ +goog.a11y.aria.LivePriority = { + // Updates to the region will not be presented to the user + // unless the assitive technology is currently focused on that region. + OFF: 'off', + // (Background change) Assistive technologies SHOULD announce + // updates at the next graceful opportunity, such as at the end of + // speaking the current sentence or when the user pauses typing. + POLITE: 'polite', + // This information has the highest priority and assistive + // technologies SHOULD notify the user immediately. + // Because an interruption may disorient users or cause them to not complete + // their current task, authors SHOULD NOT use the assertive value unless the + // interruption is imperative. + ASSERTIVE: 'assertive' +}; + + +/** + * ARIA state values for OrientationValues. + * @enum {string} + */ +goog.a11y.aria.OrientationValues = { + // The element is oriented vertically. + VERTICAL: 'vertical', + // The element is oriented horizontally. + HORIZONTAL: 'horizontal' +}; + + +/** + * ARIA state values for RelevantValues. + * @enum {string} + */ +goog.a11y.aria.RelevantValues = { + // Element nodes are added to the DOM within the live region. + ADDITIONS: 'additions', + // Text or element nodes within the live region are removed from the DOM. + REMOVALS: 'removals', + // Text is added to any DOM descendant nodes of the live region. + TEXT: 'text', + // Equivalent to the combination of all values, "additions removals text". + ALL: 'all' +}; + + +/** + * ARIA state values for SortValues. + * @enum {string} + */ +goog.a11y.aria.SortValues = { + // Items are sorted in ascending order by this column. + ASCENDING: 'ascending', + // Items are sorted in descending order by this column. + DESCENDING: 'descending', + // There is no defined sort applied to the column. + NONE: 'none', + // A sort algorithm other than ascending or descending has been applied. + OTHER: 'other' +}; + + +/** + * ARIA state values for CheckedValues. + * @enum {string} + */ +goog.a11y.aria.CheckedValues = { + // The selectable element is checked. + TRUE: 'true', + // The selectable element is not checked. + FALSE: 'false', + // Indicates a mixed mode value for a tri-state + // checkbox or menuitemcheckbox. + MIXED: 'mixed', + // The element does not support being checked. + UNDEFINED: 'undefined' +}; + + +/** + * ARIA state values for ExpandedValues. + * @enum {string} + */ +goog.a11y.aria.ExpandedValues = { + // The element, or another grouping element it controls, is expanded. + TRUE: 'true', + // The element, or another grouping element it controls, is collapsed. + FALSE: 'false', + // The element, or another grouping element + // it controls, is neither expandable nor collapsible; all its + // child elements are shown or there are no child elements. + UNDEFINED: 'undefined' +}; + + +/** + * ARIA state values for GrabbedValues. + * @enum {string} + */ +goog.a11y.aria.GrabbedValues = { + // Indicates that the element has been "grabbed" for dragging. + TRUE: 'true', + // Indicates that the element supports being dragged. + FALSE: 'false', + // Indicates that the element does not support being dragged. + UNDEFINED: 'undefined' +}; + + +/** + * ARIA state values for InvalidValues. + * @enum {string} + */ +goog.a11y.aria.InvalidValues = { + // There are no detected errors in the value. + FALSE: 'false', + // The value entered by the user has failed validation. + TRUE: 'true', + // A grammatical error was detected. + GRAMMAR: 'grammar', + // A spelling error was detected. + SPELLING: 'spelling' +}; + + +/** + * ARIA state values for PressedValues. + * @enum {string} + */ +goog.a11y.aria.PressedValues = { + // The element is pressed. + TRUE: 'true', + // The element supports being pressed but is not currently pressed. + FALSE: 'false', + // Indicates a mixed mode value for a tri-state toggle button. + MIXED: 'mixed', + // The element does not support being pressed. + UNDEFINED: 'undefined' +}; + + +/** + * ARIA state values for SelectedValues. + * @enum {string} + */ +goog.a11y.aria.SelectedValues = { + // The selectable element is selected. + TRUE: 'true', + // The selectable element is not selected. + FALSE: 'false', + // The element is not selectable. + UNDEFINED: 'undefined' +};
http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/e2cad6e6/externs/GCL/externs/goog/a11y/aria/datatables.js ---------------------------------------------------------------------- diff --git a/externs/GCL/externs/goog/a11y/aria/datatables.js b/externs/GCL/externs/goog/a11y/aria/datatables.js new file mode 100644 index 0000000..f1ba566 --- /dev/null +++ b/externs/GCL/externs/goog/a11y/aria/datatables.js @@ -0,0 +1,68 @@ +// Copyright 2013 The Closure Library Authors. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS-IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + + + +/** + * @fileoverview The file contains data tables generated from the ARIA + * standard schema http://www.w3.org/TR/wai-aria/. + * + * This is auto-generated code. Do not manually edit! + */ + +goog.provide('goog.a11y.aria.datatables'); + +goog.require('goog.a11y.aria.State'); +goog.require('goog.object'); + + +/** + * A map that contains mapping between an ARIA state and the default value + * for it. Note that not all ARIA states have default values. + * + * @type {Object<!(goog.a11y.aria.State|string), (string|boolean|number)>} + */ +goog.a11y.aria.DefaultStateValueMap_; + + +/** + * A method that creates a map that contains mapping between an ARIA state and + * the default value for it. Note that not all ARIA states have default values. + * + * @return {!Object<!(goog.a11y.aria.State|string), (string|boolean|number)>} + * The names for each of the notification methods. + */ +goog.a11y.aria.datatables.getDefaultValuesMap = function() { + if (!goog.a11y.aria.DefaultStateValueMap_) { + goog.a11y.aria.DefaultStateValueMap_ = goog.object.create( + goog.a11y.aria.State.ATOMIC, false, + goog.a11y.aria.State.AUTOCOMPLETE, 'none', + goog.a11y.aria.State.DROPEFFECT, 'none', + goog.a11y.aria.State.HASPOPUP, false, + goog.a11y.aria.State.LIVE, 'off', + goog.a11y.aria.State.MULTILINE, false, + goog.a11y.aria.State.MULTISELECTABLE, false, + goog.a11y.aria.State.ORIENTATION, 'vertical', + goog.a11y.aria.State.READONLY, false, + goog.a11y.aria.State.RELEVANT, 'additions text', + goog.a11y.aria.State.REQUIRED, false, + goog.a11y.aria.State.SORT, 'none', + goog.a11y.aria.State.BUSY, false, + goog.a11y.aria.State.DISABLED, false, + goog.a11y.aria.State.HIDDEN, false, + goog.a11y.aria.State.INVALID, 'false'); + } + + return goog.a11y.aria.DefaultStateValueMap_; +}; http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/e2cad6e6/externs/GCL/externs/goog/a11y/aria/roles.js ---------------------------------------------------------------------- diff --git a/externs/GCL/externs/goog/a11y/aria/roles.js b/externs/GCL/externs/goog/a11y/aria/roles.js new file mode 100644 index 0000000..a282cc2 --- /dev/null +++ b/externs/GCL/externs/goog/a11y/aria/roles.js @@ -0,0 +1,216 @@ +// Copyright 2013 The Closure Library Authors. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS-IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + + +/** + * @fileoverview The file contains generated enumerations for ARIA roles + * as defined by W3C ARIA standard: http://www.w3.org/TR/wai-aria/. + * + * This is auto-generated code. Do not manually edit! For more details + * about how to edit it via the generator check go/closure-ariagen. + */ + +goog.provide('goog.a11y.aria.Role'); + + +/** + * ARIA role values. + * @enum {string} + */ +goog.a11y.aria.Role = { + // ARIA role for an alert element that doesn't need to be explicitly closed. + ALERT: 'alert', + + // ARIA role for an alert dialog element that takes focus and must be closed. + ALERTDIALOG: 'alertdialog', + + // ARIA role for an application that implements its own keyboard navigation. + APPLICATION: 'application', + + // ARIA role for an article. + ARTICLE: 'article', + + // ARIA role for a banner containing mostly site content, not page content. + BANNER: 'banner', + + // ARIA role for a button element. + BUTTON: 'button', + + // ARIA role for a checkbox button element; use with the CHECKED state. + CHECKBOX: 'checkbox', + + // ARIA role for a column header of a table or grid. + COLUMNHEADER: 'columnheader', + + // ARIA role for a combo box element. + COMBOBOX: 'combobox', + + // ARIA role for a supporting section of the document. + COMPLEMENTARY: 'complementary', + + // ARIA role for a large perceivable region that contains information + // about the parent document. + CONTENTINFO: 'contentinfo', + + // ARIA role for a definition of a term or concept. + DEFINITION: 'definition', + + // ARIA role for a dialog, some descendant must take initial focus. + DIALOG: 'dialog', + + // ARIA role for a directory, like a table of contents. + DIRECTORY: 'directory', + + // ARIA role for a part of a page that's a document, not a web application. + DOCUMENT: 'document', + + // ARIA role for a landmark region logically considered one form. + FORM: 'form', + + // ARIA role for an interactive control of tabular data. + GRID: 'grid', + + // ARIA role for a cell in a grid. + GRIDCELL: 'gridcell', + + // ARIA role for a group of related elements like tree item siblings. + GROUP: 'group', + + // ARIA role for a heading element. + HEADING: 'heading', + + // ARIA role for a container of elements that together comprise one image. + IMG: 'img', + + // ARIA role for a link. + LINK: 'link', + + // ARIA role for a list of non-interactive list items. + LIST: 'list', + + // ARIA role for a listbox. + LISTBOX: 'listbox', + + // ARIA role for a list item. + LISTITEM: 'listitem', + + // ARIA role for a live region where new information is added. + LOG: 'log', + + // ARIA landmark role for the main content in a document. Use only once. + MAIN: 'main', + + // ARIA role for a live region of non-essential information that changes. + MARQUEE: 'marquee', + + // ARIA role for a mathematical expression. + MATH: 'math', + + // ARIA role for a popup menu. + MENU: 'menu', + + // ARIA role for a menubar element containing menu elements. + MENUBAR: 'menubar', + + // ARIA role for menu item elements. + MENU_ITEM: 'menuitem', + + // ARIA role for a checkbox box element inside a menu. + MENU_ITEM_CHECKBOX: 'menuitemcheckbox', + + // ARIA role for a radio button element inside a menu. + MENU_ITEM_RADIO: 'menuitemradio', + + // ARIA landmark role for a collection of navigation links. + NAVIGATION: 'navigation', + + // ARIA role for a section ancillary to the main content. + NOTE: 'note', + + // ARIA role for option items that are children of combobox, listbox, menu, + // radiogroup, or tree elements. + OPTION: 'option', + + // ARIA role for ignorable cosmetic elements with no semantic significance. + PRESENTATION: 'presentation', + + // ARIA role for a progress bar element. + PROGRESSBAR: 'progressbar', + + // ARIA role for a radio button element. + RADIO: 'radio', + + // ARIA role for a group of connected radio button elements. + RADIOGROUP: 'radiogroup', + + // ARIA role for an important region of the page. + REGION: 'region', + + // ARIA role for a row of cells in a grid. + ROW: 'row', + + // ARIA role for a group of one or more rows in a grid. + ROWGROUP: 'rowgroup', + + // ARIA role for a row header of a table or grid. + ROWHEADER: 'rowheader', + + // ARIA role for a scrollbar element. + SCROLLBAR: 'scrollbar', + + // ARIA landmark role for a part of the page providing search functionality. + SEARCH: 'search', + + // ARIA role for a menu separator. + SEPARATOR: 'separator', + + // ARIA role for a slider. + SLIDER: 'slider', + + // ARIA role for a spin button. + SPINBUTTON: 'spinbutton', + + // ARIA role for a live region with advisory info less severe than an alert. + STATUS: 'status', + + // ARIA role for a tab button. + TAB: 'tab', + + // ARIA role for a tab bar (i.e. a list of tab buttons). + TAB_LIST: 'tablist', + + // ARIA role for a tab page (i.e. the element holding tab contents). + TAB_PANEL: 'tabpanel', + + // ARIA role for a textbox element. + TEXTBOX: 'textbox', + + // ARIA role for an element displaying elapsed time or time remaining. + TIMER: 'timer', + + // ARIA role for a toolbar element. + TOOLBAR: 'toolbar', + + // ARIA role for a tooltip element. + TOOLTIP: 'tooltip', + + // ARIA role for a tree. + TREE: 'tree', + + // ARIA role for a grid whose rows can be expanded and collapsed like a tree. + TREEGRID: 'treegrid', + + // ARIA role for a tree item that sometimes may be expanded or collapsed. + TREEITEM: 'treeitem' +}; http://git-wip-us.apache.org/repos/asf/flex-falcon/blob/e2cad6e6/externs/GCL/externs/goog/array/array.js ---------------------------------------------------------------------- diff --git a/externs/GCL/externs/goog/array/array.js b/externs/GCL/externs/goog/array/array.js new file mode 100644 index 0000000..bd99626 --- /dev/null +++ b/externs/GCL/externs/goog/array/array.js @@ -0,0 +1,1655 @@ +// Copyright 2006 The Closure Library Authors. All Rights Reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS-IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +/** + * @fileoverview Utilities for manipulating arrays. + * + * @author [email protected] (Erik Arvidsson) + */ + + +goog.provide('goog.array'); +goog.provide('goog.array.ArrayLike'); + +goog.require('goog.asserts'); + + +/** + * @define {boolean} NATIVE_ARRAY_PROTOTYPES indicates whether the code should + * rely on Array.prototype functions, if available. + * + * The Array.prototype functions can be defined by external libraries like + * Prototype and setting this flag to false forces closure to use its own + * goog.array implementation. + * + * If your javascript can be loaded by a third party site and you are wary about + * relying on the prototype functions, specify + * "--define goog.NATIVE_ARRAY_PROTOTYPES=false" to the JSCompiler. + * + * Setting goog.TRUSTED_SITE to false will automatically set + * NATIVE_ARRAY_PROTOTYPES to false. + */ +goog.define('goog.NATIVE_ARRAY_PROTOTYPES', goog.TRUSTED_SITE); + + +/** + * @define {boolean} If true, JSCompiler will use the native implementation of + * array functions where appropriate (e.g., {@code Array#filter}) and remove the + * unused pure JS implementation. + */ +goog.define('goog.array.ASSUME_NATIVE_FUNCTIONS', false); + + +/** + * @typedef {Array|NodeList|Arguments|{length: number}} + */ +goog.array.ArrayLike; + + +/** + * Returns the last element in an array without removing it. + * Same as goog.array.last. + * @param {Array<T>|goog.array.ArrayLike} array The array. + * @return {T} Last item in array. + * @template T + */ +goog.array.peek = function(array) { + return array[array.length - 1]; +}; + + +/** + * Returns the last element in an array without removing it. + * Same as goog.array.peek. + * @param {Array<T>|goog.array.ArrayLike} array The array. + * @return {T} Last item in array. + * @template T + */ +goog.array.last = goog.array.peek; + + +/** + * Reference to the original {@code Array.prototype}. + * @private + */ +goog.array.ARRAY_PROTOTYPE_ = Array.prototype; + + +// NOTE(arv): Since most of the array functions are generic it allows you to +// pass an array-like object. Strings have a length and are considered array- +// like. However, the 'in' operator does not work on strings so we cannot just +// use the array path even if the browser supports indexing into strings. We +// therefore end up splitting the string. + + +/** + * Returns the index of the first element of an array with a specified value, or + * -1 if the element is not present in the array. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-indexof} + * + * @param {Array<T>|goog.array.ArrayLike} arr The array to be searched. + * @param {T} obj The object for which we are searching. + * @param {number=} opt_fromIndex The index at which to start the search. If + * omitted the search starts at index 0. + * @return {number} The index of the first matching array element. + * @template T + */ +goog.array.indexOf = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.indexOf) ? + function(arr, obj, opt_fromIndex) { + goog.asserts.assert(arr.length != null); + + return goog.array.ARRAY_PROTOTYPE_.indexOf.call(arr, obj, opt_fromIndex); + } : + function(arr, obj, opt_fromIndex) { + var fromIndex = opt_fromIndex == null ? + 0 : (opt_fromIndex < 0 ? + Math.max(0, arr.length + opt_fromIndex) : opt_fromIndex); + + if (goog.isString(arr)) { + // Array.prototype.indexOf uses === so only strings should be found. + if (!goog.isString(obj) || obj.length != 1) { + return -1; + } + return arr.indexOf(obj, fromIndex); + } + + for (var i = fromIndex; i < arr.length; i++) { + if (i in arr && arr[i] === obj) + return i; + } + return -1; + }; + + +/** + * Returns the index of the last element of an array with a specified value, or + * -1 if the element is not present in the array. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-lastindexof} + * + * @param {!Array<T>|!goog.array.ArrayLike} arr The array to be searched. + * @param {T} obj The object for which we are searching. + * @param {?number=} opt_fromIndex The index at which to start the search. If + * omitted the search starts at the end of the array. + * @return {number} The index of the last matching array element. + * @template T + */ +goog.array.lastIndexOf = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.lastIndexOf) ? + function(arr, obj, opt_fromIndex) { + goog.asserts.assert(arr.length != null); + + // Firefox treats undefined and null as 0 in the fromIndex argument which + // leads it to always return -1 + var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex; + return goog.array.ARRAY_PROTOTYPE_.lastIndexOf.call(arr, obj, fromIndex); + } : + function(arr, obj, opt_fromIndex) { + var fromIndex = opt_fromIndex == null ? arr.length - 1 : opt_fromIndex; + + if (fromIndex < 0) { + fromIndex = Math.max(0, arr.length + fromIndex); + } + + if (goog.isString(arr)) { + // Array.prototype.lastIndexOf uses === so only strings should be found. + if (!goog.isString(obj) || obj.length != 1) { + return -1; + } + return arr.lastIndexOf(obj, fromIndex); + } + + for (var i = fromIndex; i >= 0; i--) { + if (i in arr && arr[i] === obj) + return i; + } + return -1; + }; + + +/** + * Calls a function for each element in an array. Skips holes in the array. + * See {@link http://tinyurl.com/developer-mozilla-org-array-foreach} + * + * @param {Array<T>|goog.array.ArrayLike} arr Array or array like object over + * which to iterate. + * @param {?function(this: S, T, number, ?): ?} f The function to call for every + * element. This function takes 3 arguments (the element, the index and the + * array). The return value is ignored. + * @param {S=} opt_obj The object to be used as the value of 'this' within f. + * @template T,S + */ +goog.array.forEach = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.forEach) ? + function(arr, f, opt_obj) { + goog.asserts.assert(arr.length != null); + + goog.array.ARRAY_PROTOTYPE_.forEach.call(arr, f, opt_obj); + } : + function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = 0; i < l; i++) { + if (i in arr2) { + f.call(opt_obj, arr2[i], i, arr); + } + } + }; + + +/** + * Calls a function for each element in an array, starting from the last + * element rather than the first. + * + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this: S, T, number, ?): ?} f The function to call for every + * element. This function + * takes 3 arguments (the element, the index and the array). The return + * value is ignored. + * @param {S=} opt_obj The object to be used as the value of 'this' + * within f. + * @template T,S + */ +goog.array.forEachRight = function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = l - 1; i >= 0; --i) { + if (i in arr2) { + f.call(opt_obj, arr2[i], i, arr); + } + } +}; + + +/** + * Calls a function for each element in an array, and if the function returns + * true adds the element to a new array. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-filter} + * + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?):boolean} f The function to call for + * every element. This function + * takes 3 arguments (the element, the index and the array) and must + * return a Boolean. If the return value is true the element is added to the + * result array. If it is false the element is not included. + * @param {S=} opt_obj The object to be used as the value of 'this' + * within f. + * @return {!Array<T>} a new array in which only elements that passed the test + * are present. + * @template T,S + */ +goog.array.filter = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.filter) ? + function(arr, f, opt_obj) { + goog.asserts.assert(arr.length != null); + + return goog.array.ARRAY_PROTOTYPE_.filter.call(arr, f, opt_obj); + } : + function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var res = []; + var resLength = 0; + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = 0; i < l; i++) { + if (i in arr2) { + var val = arr2[i]; // in case f mutates arr2 + if (f.call(opt_obj, val, i, arr)) { + res[resLength++] = val; + } + } + } + return res; + }; + + +/** + * Calls a function for each element in an array and inserts the result into a + * new array. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-map} + * + * @param {Array<VALUE>|goog.array.ArrayLike} arr Array or array like object + * over which to iterate. + * @param {function(this:THIS, VALUE, number, ?): RESULT} f The function to call + * for every element. This function takes 3 arguments (the element, + * the index and the array) and should return something. The result will be + * inserted into a new array. + * @param {THIS=} opt_obj The object to be used as the value of 'this' within f. + * @return {!Array<RESULT>} a new array with the results from f. + * @template THIS, VALUE, RESULT + */ +goog.array.map = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.map) ? + function(arr, f, opt_obj) { + goog.asserts.assert(arr.length != null); + + return goog.array.ARRAY_PROTOTYPE_.map.call(arr, f, opt_obj); + } : + function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var res = new Array(l); + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = 0; i < l; i++) { + if (i in arr2) { + res[i] = f.call(opt_obj, arr2[i], i, arr); + } + } + return res; + }; + + +/** + * Passes every element of an array into a function and accumulates the result. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-reduce} + * + * For example: + * var a = [1, 2, 3, 4]; + * goog.array.reduce(a, function(r, v, i, arr) {return r + v;}, 0); + * returns 10 + * + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {function(this:S, R, T, number, ?) : R} f The function to call for + * every element. This function + * takes 4 arguments (the function's previous result or the initial value, + * the value of the current array element, the current array index, and the + * array itself) + * function(previousValue, currentValue, index, array). + * @param {?} val The initial value to pass into the function on the first call. + * @param {S=} opt_obj The object to be used as the value of 'this' + * within f. + * @return {R} Result of evaluating f repeatedly across the values of the array. + * @template T,S,R + */ +goog.array.reduce = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.reduce) ? + function(arr, f, val, opt_obj) { + goog.asserts.assert(arr.length != null); + if (opt_obj) { + f = goog.bind(f, opt_obj); + } + return goog.array.ARRAY_PROTOTYPE_.reduce.call(arr, f, val); + } : + function(arr, f, val, opt_obj) { + var rval = val; + goog.array.forEach(arr, function(val, index) { + rval = f.call(opt_obj, rval, val, index, arr); + }); + return rval; + }; + + +/** + * Passes every element of an array into a function and accumulates the result, + * starting from the last element and working towards the first. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-reduceright} + * + * For example: + * var a = ['a', 'b', 'c']; + * goog.array.reduceRight(a, function(r, v, i, arr) {return r + v;}, ''); + * returns 'cba' + * + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, R, T, number, ?) : R} f The function to call for + * every element. This function + * takes 4 arguments (the function's previous result or the initial value, + * the value of the current array element, the current array index, and the + * array itself) + * function(previousValue, currentValue, index, array). + * @param {?} val The initial value to pass into the function on the first call. + * @param {S=} opt_obj The object to be used as the value of 'this' + * within f. + * @return {R} Object returned as a result of evaluating f repeatedly across the + * values of the array. + * @template T,S,R + */ +goog.array.reduceRight = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.reduceRight) ? + function(arr, f, val, opt_obj) { + goog.asserts.assert(arr.length != null); + if (opt_obj) { + f = goog.bind(f, opt_obj); + } + return goog.array.ARRAY_PROTOTYPE_.reduceRight.call(arr, f, val); + } : + function(arr, f, val, opt_obj) { + var rval = val; + goog.array.forEachRight(arr, function(val, index) { + rval = f.call(opt_obj, rval, val, index, arr); + }); + return rval; + }; + + +/** + * Calls f for each element of an array. If any call returns true, some() + * returns true (without checking the remaining elements). If all calls + * return false, some() returns false. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-some} + * + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call for + * for every element. This function takes 3 arguments (the element, the + * index and the array) and should return a boolean. + * @param {S=} opt_obj The object to be used as the value of 'this' + * within f. + * @return {boolean} true if any element passes the test. + * @template T,S + */ +goog.array.some = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.some) ? + function(arr, f, opt_obj) { + goog.asserts.assert(arr.length != null); + + return goog.array.ARRAY_PROTOTYPE_.some.call(arr, f, opt_obj); + } : + function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = 0; i < l; i++) { + if (i in arr2 && f.call(opt_obj, arr2[i], i, arr)) { + return true; + } + } + return false; + }; + + +/** + * Call f for each element of an array. If all calls return true, every() + * returns true. If any call returns false, every() returns false and + * does not continue to check the remaining elements. + * + * See {@link http://tinyurl.com/developer-mozilla-org-array-every} + * + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call for + * for every element. This function takes 3 arguments (the element, the + * index and the array) and should return a boolean. + * @param {S=} opt_obj The object to be used as the value of 'this' + * within f. + * @return {boolean} false if any element fails the test. + * @template T,S + */ +goog.array.every = goog.NATIVE_ARRAY_PROTOTYPES && + (goog.array.ASSUME_NATIVE_FUNCTIONS || + goog.array.ARRAY_PROTOTYPE_.every) ? + function(arr, f, opt_obj) { + goog.asserts.assert(arr.length != null); + + return goog.array.ARRAY_PROTOTYPE_.every.call(arr, f, opt_obj); + } : + function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = 0; i < l; i++) { + if (i in arr2 && !f.call(opt_obj, arr2[i], i, arr)) { + return false; + } + } + return true; + }; + + +/** + * Counts the array elements that fulfill the predicate, i.e. for which the + * callback function returns true. Skips holes in the array. + * + * @param {!(Array<T>|goog.array.ArrayLike)} arr Array or array like object + * over which to iterate. + * @param {function(this: S, T, number, ?): boolean} f The function to call for + * every element. Takes 3 arguments (the element, the index and the array). + * @param {S=} opt_obj The object to be used as the value of 'this' within f. + * @return {number} The number of the matching elements. + * @template T,S + */ +goog.array.count = function(arr, f, opt_obj) { + var count = 0; + goog.array.forEach(arr, function(element, index, arr) { + if (f.call(opt_obj, element, index, arr)) { + ++count; + } + }, opt_obj); + return count; +}; + + +/** + * Search an array for the first element that satisfies a given condition and + * return that element. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call + * for every element. This function takes 3 arguments (the element, the + * index and the array) and should return a boolean. + * @param {S=} opt_obj An optional "this" context for the function. + * @return {T|null} The first array element that passes the test, or null if no + * element is found. + * @template T,S + */ +goog.array.find = function(arr, f, opt_obj) { + var i = goog.array.findIndex(arr, f, opt_obj); + return i < 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i]; +}; + + +/** + * Search an array for the first element that satisfies a given condition and + * return its index. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call for + * every element. This function + * takes 3 arguments (the element, the index and the array) and should + * return a boolean. + * @param {S=} opt_obj An optional "this" context for the function. + * @return {number} The index of the first array element that passes the test, + * or -1 if no element is found. + * @template T,S + */ +goog.array.findIndex = function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = 0; i < l; i++) { + if (i in arr2 && f.call(opt_obj, arr2[i], i, arr)) { + return i; + } + } + return -1; +}; + + +/** + * Search an array (in reverse order) for the last element that satisfies a + * given condition and return that element. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call + * for every element. This function + * takes 3 arguments (the element, the index and the array) and should + * return a boolean. + * @param {S=} opt_obj An optional "this" context for the function. + * @return {T|null} The last array element that passes the test, or null if no + * element is found. + * @template T,S + */ +goog.array.findRight = function(arr, f, opt_obj) { + var i = goog.array.findIndexRight(arr, f, opt_obj); + return i < 0 ? null : goog.isString(arr) ? arr.charAt(i) : arr[i]; +}; + + +/** + * Search an array (in reverse order) for the last element that satisfies a + * given condition and return its index. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call + * for every element. This function + * takes 3 arguments (the element, the index and the array) and should + * return a boolean. + * @param {S=} opt_obj An optional "this" context for the function. + * @return {number} The index of the last array element that passes the test, + * or -1 if no element is found. + * @template T,S + */ +goog.array.findIndexRight = function(arr, f, opt_obj) { + var l = arr.length; // must be fixed during loop... see docs + var arr2 = goog.isString(arr) ? arr.split('') : arr; + for (var i = l - 1; i >= 0; i--) { + if (i in arr2 && f.call(opt_obj, arr2[i], i, arr)) { + return i; + } + } + return -1; +}; + + +/** + * Whether the array contains the given object. + * @param {goog.array.ArrayLike} arr The array to test for the presence of the + * element. + * @param {*} obj The object for which to test. + * @return {boolean} true if obj is present. + */ +goog.array.contains = function(arr, obj) { + return goog.array.indexOf(arr, obj) >= 0; +}; + + +/** + * Whether the array is empty. + * @param {goog.array.ArrayLike} arr The array to test. + * @return {boolean} true if empty. + */ +goog.array.isEmpty = function(arr) { + return arr.length == 0; +}; + + +/** + * Clears the array. + * @param {goog.array.ArrayLike} arr Array or array like object to clear. + */ +goog.array.clear = function(arr) { + // For non real arrays we don't have the magic length so we delete the + // indices. + if (!goog.isArray(arr)) { + for (var i = arr.length - 1; i >= 0; i--) { + delete arr[i]; + } + } + arr.length = 0; +}; + + +/** + * Pushes an item into an array, if it's not already in the array. + * @param {Array<T>} arr Array into which to insert the item. + * @param {T} obj Value to add. + * @template T + */ +goog.array.insert = function(arr, obj) { + if (!goog.array.contains(arr, obj)) { + arr.push(obj); + } +}; + + +/** + * Inserts an object at the given index of the array. + * @param {goog.array.ArrayLike} arr The array to modify. + * @param {*} obj The object to insert. + * @param {number=} opt_i The index at which to insert the object. If omitted, + * treated as 0. A negative index is counted from the end of the array. + */ +goog.array.insertAt = function(arr, obj, opt_i) { + goog.array.splice(arr, opt_i, 0, obj); +}; + + +/** + * Inserts at the given index of the array, all elements of another array. + * @param {goog.array.ArrayLike} arr The array to modify. + * @param {goog.array.ArrayLike} elementsToAdd The array of elements to add. + * @param {number=} opt_i The index at which to insert the object. If omitted, + * treated as 0. A negative index is counted from the end of the array. + */ +goog.array.insertArrayAt = function(arr, elementsToAdd, opt_i) { + goog.partial(goog.array.splice, arr, opt_i, 0).apply(null, elementsToAdd); +}; + + +/** + * Inserts an object into an array before a specified object. + * @param {Array<T>} arr The array to modify. + * @param {T} obj The object to insert. + * @param {T=} opt_obj2 The object before which obj should be inserted. If obj2 + * is omitted or not found, obj is inserted at the end of the array. + * @template T + */ +goog.array.insertBefore = function(arr, obj, opt_obj2) { + var i; + if (arguments.length == 2 || (i = goog.array.indexOf(arr, opt_obj2)) < 0) { + arr.push(obj); + } else { + goog.array.insertAt(arr, obj, i); + } +}; + + +/** + * Removes the first occurrence of a particular value from an array. + * @param {Array<T>|goog.array.ArrayLike} arr Array from which to remove + * value. + * @param {T} obj Object to remove. + * @return {boolean} True if an element was removed. + * @template T + */ +goog.array.remove = function(arr, obj) { + var i = goog.array.indexOf(arr, obj); + var rv; + if ((rv = i >= 0)) { + goog.array.removeAt(arr, i); + } + return rv; +}; + + +/** + * Removes from an array the element at index i + * @param {goog.array.ArrayLike} arr Array or array like object from which to + * remove value. + * @param {number} i The index to remove. + * @return {boolean} True if an element was removed. + */ +goog.array.removeAt = function(arr, i) { + goog.asserts.assert(arr.length != null); + + // use generic form of splice + // splice returns the removed items and if successful the length of that + // will be 1 + return goog.array.ARRAY_PROTOTYPE_.splice.call(arr, i, 1).length == 1; +}; + + +/** + * Removes the first value that satisfies the given condition. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call + * for every element. This function + * takes 3 arguments (the element, the index and the array) and should + * return a boolean. + * @param {S=} opt_obj An optional "this" context for the function. + * @return {boolean} True if an element was removed. + * @template T,S + */ +goog.array.removeIf = function(arr, f, opt_obj) { + var i = goog.array.findIndex(arr, f, opt_obj); + if (i >= 0) { + goog.array.removeAt(arr, i); + return true; + } + return false; +}; + + +/** + * Removes all values that satisfy the given condition. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array + * like object over which to iterate. + * @param {?function(this:S, T, number, ?) : boolean} f The function to call + * for every element. This function + * takes 3 arguments (the element, the index and the array) and should + * return a boolean. + * @param {S=} opt_obj An optional "this" context for the function. + * @return {number} The number of items removed + * @template T,S + */ +goog.array.removeAllIf = function(arr, f, opt_obj) { + var removedCount = 0; + goog.array.forEachRight(arr, function(val, index) { + if (f.call(opt_obj, val, index, arr)) { + if (goog.array.removeAt(arr, index)) { + removedCount++; + } + } + }); + return removedCount; +}; + + +/** + * Returns a new array that is the result of joining the arguments. If arrays + * are passed then their items are added, however, if non-arrays are passed they + * will be added to the return array as is. + * + * Note that ArrayLike objects will be added as is, rather than having their + * items added. + * + * goog.array.concat([1, 2], [3, 4]) -> [1, 2, 3, 4] + * goog.array.concat(0, [1, 2]) -> [0, 1, 2] + * goog.array.concat([1, 2], null) -> [1, 2, null] + * + * There is bug in all current versions of IE (6, 7 and 8) where arrays created + * in an iframe become corrupted soon (not immediately) after the iframe is + * destroyed. This is common if loading data via goog.net.IframeIo, for example. + * This corruption only affects the concat method which will start throwing + * Catastrophic Errors (#-2147418113). + * + * See http://endoflow.com/scratch/corrupted-arrays.html for a test case. + * + * Internally goog.array should use this, so that all methods will continue to + * work on these broken array objects. + * + * @param {...*} var_args Items to concatenate. Arrays will have each item + * added, while primitives and objects will be added as is. + * @return {!Array<?>} The new resultant array. + */ +goog.array.concat = function(var_args) { + return goog.array.ARRAY_PROTOTYPE_.concat.apply( + goog.array.ARRAY_PROTOTYPE_, arguments); +}; + + +/** + * Returns a new array that contains the contents of all the arrays passed. + * @param {...!Array<T>} var_args + * @return {!Array<T>} + * @template T + */ +goog.array.join = function(var_args) { + return goog.array.ARRAY_PROTOTYPE_.concat.apply( + goog.array.ARRAY_PROTOTYPE_, arguments); +}; + + +/** + * Converts an object to an array. + * @param {Array<T>|goog.array.ArrayLike} object The object to convert to an + * array. + * @return {!Array<T>} The object converted into an array. If object has a + * length property, every property indexed with a non-negative number + * less than length will be included in the result. If object does not + * have a length property, an empty array will be returned. + * @template T + */ +goog.array.toArray = function(object) { + var length = object.length; + + // If length is not a number the following it false. This case is kept for + // backwards compatibility since there are callers that pass objects that are + // not array like. + if (length > 0) { + var rv = new Array(length); + for (var i = 0; i < length; i++) { + rv[i] = object[i]; + } + return rv; + } + return []; +}; + + +/** + * Does a shallow copy of an array. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array-like object to + * clone. + * @return {!Array<T>} Clone of the input array. + * @template T + */ +goog.array.clone = goog.array.toArray; + + +/** + * Extends an array with another array, element, or "array like" object. + * This function operates 'in-place', it does not create a new Array. + * + * Example: + * var a = []; + * goog.array.extend(a, [0, 1]); + * a; // [0, 1] + * goog.array.extend(a, 2); + * a; // [0, 1, 2] + * + * @param {Array<VALUE>} arr1 The array to modify. + * @param {...(Array<VALUE>|VALUE)} var_args The elements or arrays of elements + * to add to arr1. + * @template VALUE + */ +goog.array.extend = function(arr1, var_args) { + for (var i = 1; i < arguments.length; i++) { + var arr2 = arguments[i]; + if (goog.isArrayLike(arr2)) { + var len1 = arr1.length || 0; + var len2 = arr2.length || 0; + arr1.length = len1 + len2; + for (var j = 0; j < len2; j++) { + arr1[len1 + j] = arr2[j]; + } + } else { + arr1.push(arr2); + } + } +}; + + +/** + * Adds or removes elements from an array. This is a generic version of Array + * splice. This means that it might work on other objects similar to arrays, + * such as the arguments object. + * + * @param {Array<T>|goog.array.ArrayLike} arr The array to modify. + * @param {number|undefined} index The index at which to start changing the + * array. If not defined, treated as 0. + * @param {number} howMany How many elements to remove (0 means no removal. A + * value below 0 is treated as zero and so is any other non number. Numbers + * are floored). + * @param {...T} var_args Optional, additional elements to insert into the + * array. + * @return {!Array<T>} the removed elements. + * @template T + */ +goog.array.splice = function(arr, index, howMany, var_args) { + goog.asserts.assert(arr.length != null); + + return goog.array.ARRAY_PROTOTYPE_.splice.apply( + arr, goog.array.slice(arguments, 1)); +}; + + +/** + * Returns a new array from a segment of an array. This is a generic version of + * Array slice. This means that it might work on other objects similar to + * arrays, such as the arguments object. + * + * @param {Array<T>|goog.array.ArrayLike} arr The array from + * which to copy a segment. + * @param {number} start The index of the first element to copy. + * @param {number=} opt_end The index after the last element to copy. + * @return {!Array<T>} A new array containing the specified segment of the + * original array. + * @template T + */ +goog.array.slice = function(arr, start, opt_end) { + goog.asserts.assert(arr.length != null); + + // passing 1 arg to slice is not the same as passing 2 where the second is + // null or undefined (in that case the second argument is treated as 0). + // we could use slice on the arguments object and then use apply instead of + // testing the length + if (arguments.length <= 2) { + return goog.array.ARRAY_PROTOTYPE_.slice.call(arr, start); + } else { + return goog.array.ARRAY_PROTOTYPE_.slice.call(arr, start, opt_end); + } +}; + + +/** + * Removes all duplicates from an array (retaining only the first + * occurrence of each array element). This function modifies the + * array in place and doesn't change the order of the non-duplicate items. + * + * For objects, duplicates are identified as having the same unique ID as + * defined by {@link goog.getUid}. + * + * Alternatively you can specify a custom hash function that returns a unique + * value for each item in the array it should consider unique. + * + * Runtime: N, + * Worstcase space: 2N (no dupes) + * + * @param {Array<T>|goog.array.ArrayLike} arr The array from which to remove + * duplicates. + * @param {Array=} opt_rv An optional array in which to return the results, + * instead of performing the removal inplace. If specified, the original + * array will remain unchanged. + * @param {function(T):string=} opt_hashFn An optional function to use to + * apply to every item in the array. This function should return a unique + * value for each item in the array it should consider unique. + * @template T + */ +goog.array.removeDuplicates = function(arr, opt_rv, opt_hashFn) { + var returnArray = opt_rv || arr; + var defaultHashFn = function(item) { + // Prefix each type with a single character representing the type to + // prevent conflicting keys (e.g. true and 'true'). + return goog.isObject(current) ? 'o' + goog.getUid(current) : + (typeof current).charAt(0) + current; + }; + var hashFn = opt_hashFn || defaultHashFn; + + var seen = {}, cursorInsert = 0, cursorRead = 0; + while (cursorRead < arr.length) { + var current = arr[cursorRead++]; + var key = hashFn(current); + if (!Object.prototype.hasOwnProperty.call(seen, key)) { + seen[key] = true; + returnArray[cursorInsert++] = current; + } + } + returnArray.length = cursorInsert; +}; + + +/** + * Searches the specified array for the specified target using the binary + * search algorithm. If no opt_compareFn is specified, elements are compared + * using <code>goog.array.defaultCompare</code>, which compares the elements + * using the built in < and > operators. This will produce the expected + * behavior for homogeneous arrays of String(s) and Number(s). The array + * specified <b>must</b> be sorted in ascending order (as defined by the + * comparison function). If the array is not sorted, results are undefined. + * If the array contains multiple instances of the specified target value, any + * of these instances may be found. + * + * Runtime: O(log n) + * + * @param {Array<VALUE>|goog.array.ArrayLike} arr The array to be searched. + * @param {TARGET} target The sought value. + * @param {function(TARGET, VALUE): number=} opt_compareFn Optional comparison + * function by which the array is ordered. Should take 2 arguments to + * compare, and return a negative number, zero, or a positive number + * depending on whether the first argument is less than, equal to, or + * greater than the second. + * @return {number} Lowest index of the target value if found, otherwise + * (-(insertion point) - 1). The insertion point is where the value should + * be inserted into arr to preserve the sorted property. Return value >= 0 + * iff target is found. + * @template TARGET, VALUE + */ +goog.array.binarySearch = function(arr, target, opt_compareFn) { + return goog.array.binarySearch_(arr, + opt_compareFn || goog.array.defaultCompare, false /* isEvaluator */, + target); +}; + + +/** + * Selects an index in the specified array using the binary search algorithm. + * The evaluator receives an element and determines whether the desired index + * is before, at, or after it. The evaluator must be consistent (formally, + * goog.array.map(goog.array.map(arr, evaluator, opt_obj), goog.math.sign) + * must be monotonically non-increasing). + * + * Runtime: O(log n) + * + * @param {Array<VALUE>|goog.array.ArrayLike} arr The array to be searched. + * @param {function(this:THIS, VALUE, number, ?): number} evaluator + * Evaluator function that receives 3 arguments (the element, the index and + * the array). Should return a negative number, zero, or a positive number + * depending on whether the desired index is before, at, or after the + * element passed to it. + * @param {THIS=} opt_obj The object to be used as the value of 'this' + * within evaluator. + * @return {number} Index of the leftmost element matched by the evaluator, if + * such exists; otherwise (-(insertion point) - 1). The insertion point is + * the index of the first element for which the evaluator returns negative, + * or arr.length if no such element exists. The return value is non-negative + * iff a match is found. + * @template THIS, VALUE + */ +goog.array.binarySelect = function(arr, evaluator, opt_obj) { + return goog.array.binarySearch_(arr, evaluator, true /* isEvaluator */, + undefined /* opt_target */, opt_obj); +}; + + +/** + * Implementation of a binary search algorithm which knows how to use both + * comparison functions and evaluators. If an evaluator is provided, will call + * the evaluator with the given optional data object, conforming to the + * interface defined in binarySelect. Otherwise, if a comparison function is + * provided, will call the comparison function against the given data object. + * + * This implementation purposefully does not use goog.bind or goog.partial for + * performance reasons. + * + * Runtime: O(log n) + * + * @param {Array<VALUE>|goog.array.ArrayLike} arr The array to be searched. + * @param {function(TARGET, VALUE): number| + * function(this:THIS, VALUE, number, ?): number} compareFn Either an + * evaluator or a comparison function, as defined by binarySearch + * and binarySelect above. + * @param {boolean} isEvaluator Whether the function is an evaluator or a + * comparison function. + * @param {TARGET=} opt_target If the function is a comparison function, then + * this is the target to binary search for. + * @param {THIS=} opt_selfObj If the function is an evaluator, this is an + * optional this object for the evaluator. + * @return {number} Lowest index of the target value if found, otherwise + * (-(insertion point) - 1). The insertion point is where the value should + * be inserted into arr to preserve the sorted property. Return value >= 0 + * iff target is found. + * @template THIS, VALUE, TARGET + * @private + */ +goog.array.binarySearch_ = function(arr, compareFn, isEvaluator, opt_target, + opt_selfObj) { + var left = 0; // inclusive + var right = arr.length; // exclusive + var found; + while (left < right) { + var middle = (left + right) >> 1; + var compareResult; + if (isEvaluator) { + compareResult = compareFn.call(opt_selfObj, arr[middle], middle, arr); + } else { + compareResult = compareFn(opt_target, arr[middle]); + } + if (compareResult > 0) { + left = middle + 1; + } else { + right = middle; + // We are looking for the lowest index so we can't return immediately. + found = !compareResult; + } + } + // left is the index if found, or the insertion point otherwise. + // ~left is a shorthand for -left - 1. + return found ? left : ~left; +}; + + +/** + * Sorts the specified array into ascending order. If no opt_compareFn is + * specified, elements are compared using + * <code>goog.array.defaultCompare</code>, which compares the elements using + * the built in < and > operators. This will produce the expected behavior + * for homogeneous arrays of String(s) and Number(s), unlike the native sort, + * but will give unpredictable results for heterogenous lists of strings and + * numbers with different numbers of digits. + * + * This sort is not guaranteed to be stable. + * + * Runtime: Same as <code>Array.prototype.sort</code> + * + * @param {Array<T>} arr The array to be sorted. + * @param {?function(T,T):number=} opt_compareFn Optional comparison + * function by which the + * array is to be ordered. Should take 2 arguments to compare, and return a + * negative number, zero, or a positive number depending on whether the + * first argument is less than, equal to, or greater than the second. + * @template T + */ +goog.array.sort = function(arr, opt_compareFn) { + // TODO(arv): Update type annotation since null is not accepted. + arr.sort(opt_compareFn || goog.array.defaultCompare); +}; + + +/** + * Sorts the specified array into ascending order in a stable way. If no + * opt_compareFn is specified, elements are compared using + * <code>goog.array.defaultCompare</code>, which compares the elements using + * the built in < and > operators. This will produce the expected behavior + * for homogeneous arrays of String(s) and Number(s). + * + * Runtime: Same as <code>Array.prototype.sort</code>, plus an additional + * O(n) overhead of copying the array twice. + * + * @param {Array<T>} arr The array to be sorted. + * @param {?function(T, T): number=} opt_compareFn Optional comparison function + * by which the array is to be ordered. Should take 2 arguments to compare, + * and return a negative number, zero, or a positive number depending on + * whether the first argument is less than, equal to, or greater than the + * second. + * @template T + */ +goog.array.stableSort = function(arr, opt_compareFn) { + for (var i = 0; i < arr.length; i++) { + arr[i] = {index: i, value: arr[i]}; + } + var valueCompareFn = opt_compareFn || goog.array.defaultCompare; + function stableCompareFn(obj1, obj2) { + return valueCompareFn(obj1.value, obj2.value) || obj1.index - obj2.index; + }; + goog.array.sort(arr, stableCompareFn); + for (var i = 0; i < arr.length; i++) { + arr[i] = arr[i].value; + } +}; + + +/** + * Sort the specified array into ascending order based on item keys + * returned by the specified key function. + * If no opt_compareFn is specified, the keys are compared in ascending order + * using <code>goog.array.defaultCompare</code>. + * + * Runtime: O(S(f(n)), where S is runtime of <code>goog.array.sort</code> + * and f(n) is runtime of the key function. + * + * @param {Array<T>} arr The array to be sorted. + * @param {function(T): K} keyFn Function taking array element and returning + * a key used for sorting this element. + * @param {?function(K, K): number=} opt_compareFn Optional comparison function + * by which the keys are to be ordered. Should take 2 arguments to compare, + * and return a negative number, zero, or a positive number depending on + * whether the first argument is less than, equal to, or greater than the + * second. + * @template T + * @template K + */ +goog.array.sortByKey = function(arr, keyFn, opt_compareFn) { + var keyCompareFn = opt_compareFn || goog.array.defaultCompare; + goog.array.sort(arr, function(a, b) { + return keyCompareFn(keyFn(a), keyFn(b)); + }); +}; + + +/** + * Sorts an array of objects by the specified object key and compare + * function. If no compare function is provided, the key values are + * compared in ascending order using <code>goog.array.defaultCompare</code>. + * This won't work for keys that get renamed by the compiler. So use + * {'foo': 1, 'bar': 2} rather than {foo: 1, bar: 2}. + * @param {Array<Object>} arr An array of objects to sort. + * @param {string} key The object key to sort by. + * @param {Function=} opt_compareFn The function to use to compare key + * values. + */ +goog.array.sortObjectsByKey = function(arr, key, opt_compareFn) { + goog.array.sortByKey(arr, + function(obj) { return obj[key]; }, + opt_compareFn); +}; + + +/** + * Tells if the array is sorted. + * @param {!Array<T>} arr The array. + * @param {?function(T,T):number=} opt_compareFn Function to compare the + * array elements. + * Should take 2 arguments to compare, and return a negative number, zero, + * or a positive number depending on whether the first argument is less + * than, equal to, or greater than the second. + * @param {boolean=} opt_strict If true no equal elements are allowed. + * @return {boolean} Whether the array is sorted. + * @template T + */ +goog.array.isSorted = function(arr, opt_compareFn, opt_strict) { + var compare = opt_compareFn || goog.array.defaultCompare; + for (var i = 1; i < arr.length; i++) { + var compareResult = compare(arr[i - 1], arr[i]); + if (compareResult > 0 || compareResult == 0 && opt_strict) { + return false; + } + } + return true; +}; + + +/** + * Compares two arrays for equality. Two arrays are considered equal if they + * have the same length and their corresponding elements are equal according to + * the comparison function. + * + * @param {goog.array.ArrayLike} arr1 The first array to compare. + * @param {goog.array.ArrayLike} arr2 The second array to compare. + * @param {Function=} opt_equalsFn Optional comparison function. + * Should take 2 arguments to compare, and return true if the arguments + * are equal. Defaults to {@link goog.array.defaultCompareEquality} which + * compares the elements using the built-in '===' operator. + * @return {boolean} Whether the two arrays are equal. + */ +goog.array.equals = function(arr1, arr2, opt_equalsFn) { + if (!goog.isArrayLike(arr1) || !goog.isArrayLike(arr2) || + arr1.length != arr2.length) { + return false; + } + var l = arr1.length; + var equalsFn = opt_equalsFn || goog.array.defaultCompareEquality; + for (var i = 0; i < l; i++) { + if (!equalsFn(arr1[i], arr2[i])) { + return false; + } + } + return true; +}; + + +/** + * 3-way array compare function. + * @param {!Array<VALUE>|!goog.array.ArrayLike} arr1 The first array to + * compare. + * @param {!Array<VALUE>|!goog.array.ArrayLike} arr2 The second array to + * compare. + * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison + * function by which the array is to be ordered. Should take 2 arguments to + * compare, and return a negative number, zero, or a positive number + * depending on whether the first argument is less than, equal to, or + * greater than the second. + * @return {number} Negative number, zero, or a positive number depending on + * whether the first argument is less than, equal to, or greater than the + * second. + * @template VALUE + */ +goog.array.compare3 = function(arr1, arr2, opt_compareFn) { + var compare = opt_compareFn || goog.array.defaultCompare; + var l = Math.min(arr1.length, arr2.length); + for (var i = 0; i < l; i++) { + var result = compare(arr1[i], arr2[i]); + if (result != 0) { + return result; + } + } + return goog.array.defaultCompare(arr1.length, arr2.length); +}; + + +/** + * Compares its two arguments for order, using the built in < and > + * operators. + * @param {VALUE} a The first object to be compared. + * @param {VALUE} b The second object to be compared. + * @return {number} A negative number, zero, or a positive number as the first + * argument is less than, equal to, or greater than the second, + * respectively. + * @template VALUE + */ +goog.array.defaultCompare = function(a, b) { + return a > b ? 1 : a < b ? -1 : 0; +}; + + +/** + * Compares its two arguments for inverse order, using the built in < and > + * operators. + * @param {VALUE} a The first object to be compared. + * @param {VALUE} b The second object to be compared. + * @return {number} A negative number, zero, or a positive number as the first + * argument is greater than, equal to, or less than the second, + * respectively. + * @template VALUE + */ +goog.array.inverseDefaultCompare = function(a, b) { + return -goog.array.defaultCompare(a, b); +}; + + +/** + * Compares its two arguments for equality, using the built in === operator. + * @param {*} a The first object to compare. + * @param {*} b The second object to compare. + * @return {boolean} True if the two arguments are equal, false otherwise. + */ +goog.array.defaultCompareEquality = function(a, b) { + return a === b; +}; + + +/** + * Inserts a value into a sorted array. The array is not modified if the + * value is already present. + * @param {Array<VALUE>|goog.array.ArrayLike} array The array to modify. + * @param {VALUE} value The object to insert. + * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison + * function by which the array is ordered. Should take 2 arguments to + * compare, and return a negative number, zero, or a positive number + * depending on whether the first argument is less than, equal to, or + * greater than the second. + * @return {boolean} True if an element was inserted. + * @template VALUE + */ +goog.array.binaryInsert = function(array, value, opt_compareFn) { + var index = goog.array.binarySearch(array, value, opt_compareFn); + if (index < 0) { + goog.array.insertAt(array, value, -(index + 1)); + return true; + } + return false; +}; + + +/** + * Removes a value from a sorted array. + * @param {!Array<VALUE>|!goog.array.ArrayLike} array The array to modify. + * @param {VALUE} value The object to remove. + * @param {function(VALUE, VALUE): number=} opt_compareFn Optional comparison + * function by which the array is ordered. Should take 2 arguments to + * compare, and return a negative number, zero, or a positive number + * depending on whether the first argument is less than, equal to, or + * greater than the second. + * @return {boolean} True if an element was removed. + * @template VALUE + */ +goog.array.binaryRemove = function(array, value, opt_compareFn) { + var index = goog.array.binarySearch(array, value, opt_compareFn); + return (index >= 0) ? goog.array.removeAt(array, index) : false; +}; + + +/** + * Splits an array into disjoint buckets according to a splitting function. + * @param {Array<T>} array The array. + * @param {function(this:S, T,number,Array<T>):?} sorter Function to call for + * every element. This takes 3 arguments (the element, the index and the + * array) and must return a valid object key (a string, number, etc), or + * undefined, if that object should not be placed in a bucket. + * @param {S=} opt_obj The object to be used as the value of 'this' within + * sorter. + * @return {!Object} An object, with keys being all of the unique return values + * of sorter, and values being arrays containing the items for + * which the splitter returned that key. + * @template T,S + */ +goog.array.bucket = function(array, sorter, opt_obj) { + var buckets = {}; + + for (var i = 0; i < array.length; i++) { + var value = array[i]; + var key = sorter.call(opt_obj, value, i, array); + if (goog.isDef(key)) { + // Push the value to the right bucket, creating it if necessary. + var bucket = buckets[key] || (buckets[key] = []); + bucket.push(value); + } + } + + return buckets; +}; + + +/** + * Creates a new object built from the provided array and the key-generation + * function. + * @param {Array<T>|goog.array.ArrayLike} arr Array or array like object over + * which to iterate whose elements will be the values in the new object. + * @param {?function(this:S, T, number, ?) : string} keyFunc The function to + * call for every element. This function takes 3 arguments (the element, the + * index and the array) and should return a string that will be used as the + * key for the element in the new object. If the function returns the same + * key for more than one element, the value for that key is + * implementation-defined. + * @param {S=} opt_obj The object to be used as the value of 'this' + * within keyFunc. + * @return {!Object<T>} The new object. + * @template T,S + */ +goog.array.toObject = function(arr, keyFunc, opt_obj) { + var ret = {}; + goog.array.forEach(arr, function(element, index) { + ret[keyFunc.call(opt_obj, element, index, arr)] = element; + }); + return ret; +}; + + +/** + * Creates a range of numbers in an arithmetic progression. + * + * Range takes 1, 2, or 3 arguments: + * <pre> + * range(5) is the same as range(0, 5, 1) and produces [0, 1, 2, 3, 4] + * range(2, 5) is the same as range(2, 5, 1) and produces [2, 3, 4] + * range(-2, -5, -1) produces [-2, -3, -4] + * range(-2, -5, 1) produces [], since stepping by 1 wouldn't ever reach -5. + * </pre> + * + * @param {number} startOrEnd The starting value of the range if an end argument + * is provided. Otherwise, the start value is 0, and this is the end value. + * @param {number=} opt_end The optional end value of the range. + * @param {number=} opt_step The step size between range values. Defaults to 1 + * if opt_step is undefined or 0. + * @return {!Array<number>} An array of numbers for the requested range. May be + * an empty array if adding the step would not converge toward the end + * value. + */ +goog.array.range = function(startOrEnd, opt_end, opt_step) { + var array = []; + var start = 0; + var end = startOrEnd; + var step = opt_step || 1; + if (opt_end !== undefined) { + start = startOrEnd; + end = opt_end; + } + + if (step * (end - start) < 0) { + // Sign mismatch: start + step will never reach the end value. + return []; + } + + if (step > 0) { + for (var i = start; i < end; i += step) { + array.push(i); + } + } else { + for (var i = start; i > end; i += step) { + array.push(i); + } + } + return array; +}; + + +/** + * Returns an array consisting of the given value repeated N times. + * + * @param {VALUE} value The value to repeat. + * @param {number} n The repeat count. + * @return {!Array<VALUE>} An array with the repeated value. + * @template VALUE + */ +goog.array.repeat = function(value, n) { + var array = []; + for (var i = 0; i < n; i++) { + array[i] = value; + } + return array; +}; + + +/** + * Returns an array consisting of every argument with all arrays + * expanded in-place recursively. + * + * @param {...*} var_args The values to flatten. + * @return {!Array<?>} An array containing the flattened values. + */ +goog.array.flatten = function(var_args) { + var CHUNK_SIZE = 8192; + + var result = []; + for (var i = 0; i < arguments.length; i++) { + var element = arguments[i]; + if (goog.isArray(element)) { + for (var c = 0; c < element.length; c += CHUNK_SIZE) { + var chunk = goog.array.slice(element, c, c + CHUNK_SIZE); + var recurseResult = goog.array.flatten.apply(null, chunk); + for (var r = 0; r < recurseResult.length; r++) { + result.push(recurseResult[r]); + } + } + } else { + result.push(element); + } + } + return result; +}; + + +/** + * Rotates an array in-place. After calling this method, the element at + * index i will be the element previously at index (i - n) % + * array.length, for all values of i between 0 and array.length - 1, + * inclusive. + * + * For example, suppose list comprises [t, a, n, k, s]. After invoking + * rotate(array, 1) (or rotate(array, -4)), array will comprise [s, t, a, n, k]. + * + * @param {!Array<T>} array The array to rotate. + * @param {number} n The amount to rotate. + * @return {!Array<T>} The array. + * @template T + */ +goog.array.rotate = function(array, n) { + goog.asserts.assert(array.length != null); + + if (array.length) { + n %= array.length; + if (n > 0) { + goog.array.ARRAY_PROTOTYPE_.unshift.apply(array, array.splice(-n, n)); + } else if (n < 0) { + goog.array.ARRAY_PROTOTYPE_.push.apply(array, array.splice(0, -n)); + } + } + return array; +}; + + +/** + * Moves one item of an array to a new position keeping the order of the rest + * of the items. Example use case: keeping a list of JavaScript objects + * synchronized with the corresponding list of DOM elements after one of the + * elements has been dragged to a new position. + * @param {!(Array|Arguments|{length:number})} arr The array to modify. + * @param {number} fromIndex Index of the item to move between 0 and + * {@code arr.length - 1}. + * @param {number} toIndex Target index between 0 and {@code arr.length - 1}. + */ +goog.array.moveItem = function(arr, fromIndex, toIndex) { + goog.asserts.assert(fromIndex >= 0 && fromIndex < arr.length); + goog.asserts.assert(toIndex >= 0 && toIndex < arr.length); + // Remove 1 item at fromIndex. + var removedItems = goog.array.ARRAY_PROTOTYPE_.splice.call(arr, fromIndex, 1); + // Insert the removed item at toIndex. + goog.array.ARRAY_PROTOTYPE_.splice.call(arr, toIndex, 0, removedItems[0]); + // We don't use goog.array.insertAt and goog.array.removeAt, because they're + // significantly slower than splice. +}; + + +/** + * Creates a new array for which the element at position i is an array of the + * ith element of the provided arrays. The returned array will only be as long + * as the shortest array provided; additional values are ignored. For example, + * the result of zipping [1, 2] and [3, 4, 5] is [[1,3], [2, 4]]. + * + * This is similar to the zip() function in Python. See {@link + * http://docs.python.org/library/functions.html#zip} + * + * @param {...!goog.array.ArrayLike} var_args Arrays to be combined. + * @return {!Array<!Array<?>>} A new array of arrays created from + * provided arrays. + */ +goog.array.zip = function(var_args) { + if (!arguments.length) { + return []; + } + var result = []; + for (var i = 0; true; i++) { + var value = []; + for (var j = 0; j < arguments.length; j++) { + var arr = arguments[j]; + // If i is larger than the array length, this is the shortest array. + if (i >= arr.length) { + return result; + } + value.push(arr[i]); + } + result.push(value); + } +}; + + +/** + * Shuffles the values in the specified array using the Fisher-Yates in-place + * shuffle (also known as the Knuth Shuffle). By default, calls Math.random() + * and so resets the state of that random number generator. Similarly, may reset + * the state of the any other specified random number generator. + * + * Runtime: O(n) + * + * @param {!Array<?>} arr The array to be shuffled. + * @param {function():number=} opt_randFn Optional random function to use for + * shuffling. + * Takes no arguments, and returns a random number on the interval [0, 1). + * Defaults to Math.random() using JavaScript's built-in Math library. + */ +goog.array.shuffle = function(arr, opt_randFn) { + var randFn = opt_randFn || Math.random; + + for (var i = arr.length - 1; i > 0; i--) { + // Choose a random array index in [0, i] (inclusive with i). + var j = Math.floor(randFn() * (i + 1)); + + var tmp = arr[i]; + arr[i] = arr[j]; + arr[j] = tmp; + } +}; + + +/** + * Returns a new array of elements from arr, based on the indexes of elements + * provided by index_arr. For example, the result of index copying + * ['a', 'b', 'c'] with index_arr [1,0,0,2] is ['b', 'a', 'a', 'c']. + * + * @param {!Array<T>} arr The array to get a indexed copy from. + * @param {!Array<number>} index_arr An array of indexes to get from arr. + * @return {!Array<T>} A new array of elements from arr in index_arr order. + * @template T + */ +goog.array.copyByIndex = function(arr, index_arr) { + var result = []; + goog.array.forEach(index_arr, function(index) { + result.push(arr[index]); + }); + return result; +};
