1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
|
// 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 Datastructure: Set.
*
* @author arv@google.com (Erik Arvidsson)
*
* This class implements a set data structure. Adding and removing is O(1). It
* supports both object and primitive values. Be careful because you can add
* both 1 and new Number(1), because these are not the same. You can even add
* multiple new Number(1) because these are not equal.
*/
goog.provide('goog.structs.Set');
goog.require('goog.structs');
goog.require('goog.structs.Collection');
goog.require('goog.structs.Map');
/**
* A set that can contain both primitives and objects. Adding and removing
* elements is O(1). Primitives are treated as identical if they have the same
* type and convert to the same string. Objects are treated as identical only
* if they are references to the same object. WARNING: A goog.structs.Set can
* contain both 1 and (new Number(1)), because they are not the same. WARNING:
* Adding (new Number(1)) twice will yield two distinct elements, because they
* are two different objects. WARNING: Any object that is added to a
* goog.structs.Set will be modified! Because goog.getUid() is used to
* identify objects, every object in the set will be mutated.
* @param {Array<T>|Object<?,T>=} opt_values Initial values to start with.
* @constructor
* @implements {goog.structs.Collection<T>}
* @final
* @template T
* @deprecated This type is misleading: use ES6 Set instead.
*/
goog.structs.Set = function(opt_values) {
this.map_ = new goog.structs.Map;
if (opt_values) {
this.addAll(opt_values);
}
};
/**
* Obtains a unique key for an element of the set. Primitives will yield the
* same key if they have the same type and convert to the same string. Object
* references will yield the same key only if they refer to the same object.
* @param {*} val Object or primitive value to get a key for.
* @return {string} A unique key for this value/object.
* @private
*/
goog.structs.Set.getKey_ = function(val) {
var type = typeof val;
if (type == 'object' && val || type == 'function') {
return 'o' + goog.getUid(/** @type {Object} */ (val));
} else {
return type.substr(0, 1) + val;
}
};
/**
* @return {number} The number of elements in the set.
* @override
*/
goog.structs.Set.prototype.getCount = function() {
return this.map_.getCount();
};
/**
* Add a primitive or an object to the set.
* @param {T} element The primitive or object to add.
* @override
*/
goog.structs.Set.prototype.add = function(element) {
this.map_.set(goog.structs.Set.getKey_(element), element);
};
/**
* Adds all the values in the given collection to this set.
* @param {Array<T>|goog.structs.Collection<T>|Object<?,T>} col A collection
* containing the elements to add.
*/
goog.structs.Set.prototype.addAll = function(col) {
var values = goog.structs.getValues(col);
var l = values.length;
for (var i = 0; i < l; i++) {
this.add(values[i]);
}
};
/**
* Removes all values in the given collection from this set.
* @param {Array<T>|goog.structs.Collection<T>|Object<?,T>} col A collection
* containing the elements to remove.
*/
goog.structs.Set.prototype.removeAll = function(col) {
var values = goog.structs.getValues(col);
var l = values.length;
for (var i = 0; i < l; i++) {
this.remove(values[i]);
}
};
/**
* Removes the given element from this set.
* @param {T} element The primitive or object to remove.
* @return {boolean} Whether the element was found and removed.
* @override
*/
goog.structs.Set.prototype.remove = function(element) {
return this.map_.remove(goog.structs.Set.getKey_(element));
};
/**
* Removes all elements from this set.
*/
goog.structs.Set.prototype.clear = function() {
this.map_.clear();
};
/**
* Tests whether this set is empty.
* @return {boolean} True if there are no elements in this set.
*/
goog.structs.Set.prototype.isEmpty = function() {
return this.map_.isEmpty();
};
/**
* Tests whether this set contains the given element.
* @param {T} element The primitive or object to test for.
* @return {boolean} True if this set contains the given element.
* @override
*/
goog.structs.Set.prototype.contains = function(element) {
return this.map_.containsKey(goog.structs.Set.getKey_(element));
};
/**
* Tests whether this set contains all the values in a given collection.
* Repeated elements in the collection are ignored, e.g. (new
* goog.structs.Set([1, 2])).containsAll([1, 1]) is True.
* @param {goog.structs.Collection<T>|Object} col A collection-like object.
* @return {boolean} True if the set contains all elements.
*/
goog.structs.Set.prototype.containsAll = function(col) {
return goog.structs.every(col, this.contains, this);
};
/**
* Finds all values that are present in both this set and the given collection.
* @param {Array<S>|Object<?,S>} col A collection.
* @return {!goog.structs.Set<T|S>} A new set containing all the values
* (primitives or objects) present in both this set and the given
* collection.
* @template S
*/
goog.structs.Set.prototype.intersection = function(col) {
var result = new goog.structs.Set();
var values = goog.structs.getValues(col);
for (var i = 0; i < values.length; i++) {
var value = values[i];
if (this.contains(value)) {
result.add(value);
}
}
return result;
};
/**
* Finds all values that are present in this set and not in the given
* collection.
* @param {Array<T>|goog.structs.Collection<T>|Object<?,T>} col A collection.
* @return {!goog.structs.Set} A new set containing all the values
* (primitives or objects) present in this set but not in the given
* collection.
*/
goog.structs.Set.prototype.difference = function(col) {
var result = this.clone();
result.removeAll(col);
return result;
};
/**
* Returns an array containing all the elements in this set.
* @return {!Array<T>} An array containing all the elements in this set.
*/
goog.structs.Set.prototype.getValues = function() {
return this.map_.getValues();
};
/**
* Creates a shallow clone of this set.
* @return {!goog.structs.Set<T>} A new set containing all the same elements as
* this set.
*/
goog.structs.Set.prototype.clone = function() {
return new goog.structs.Set(this);
};
/**
* Tests whether the given collection consists of the same elements as this set,
* regardless of order, without repetition. Primitives are treated as equal if
* they have the same type and convert to the same string; objects are treated
* as equal if they are references to the same object. This operation is O(n).
* @param {goog.structs.Collection<T>|Object} col A collection.
* @return {boolean} True if the given collection consists of the same elements
* as this set, regardless of order, without repetition.
*/
goog.structs.Set.prototype.equals = function(col) {
return this.getCount() == goog.structs.getCount(col) && this.isSubsetOf(col);
};
/**
* Tests whether the given collection contains all the elements in this set.
* Primitives are treated as equal if they have the same type and convert to the
* same string; objects are treated as equal if they are references to the same
* object. This operation is O(n).
* @param {goog.structs.Collection<T>|Object} col A collection.
* @return {boolean} True if this set is a subset of the given collection.
*/
goog.structs.Set.prototype.isSubsetOf = function(col) {
var colCount = goog.structs.getCount(col);
if (this.getCount() > colCount) {
return false;
}
// TODO(user) Find the minimal collection size where the conversion makes
// the contains() method faster.
if (!(col instanceof goog.structs.Set) && colCount > 5) {
// Convert to a goog.structs.Set so that goog.structs.contains runs in
// O(1) time instead of O(n) time.
col = new goog.structs.Set(col);
}
return goog.structs.every(
this, function(value) { return goog.structs.contains(col, value); });
};
/**
* Returns an iterator that iterates over the elements in this set.
* @param {boolean=} opt_keys This argument is ignored.
* @return {!goog.iter.Iterator} An iterator over the elements in this set.
*/
goog.structs.Set.prototype.__iterator__ = function(opt_keys) {
return this.map_.__iterator__(false);
};
|