Debian Codegraph @

closure-library/closure/goog/labs/structs/multimap.js

raw
1 // Copyright 2012 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview A collection similar to
17 * {@code goog.labs.structs.Map}, but also allows associating multiple
18 * values with a single key.
19 *
20 * This implementation ensures that you can use any string keys.
21 *
22 * @author [email protected] (Chris Henry)
23 */
24
25 goog.provide('goog.labs.structs.Multimap');
26
27 goog.require('goog.array');
28 goog.require('goog.labs.structs.Map');
29 goog.require('goog.object');
30
31
32
33 /**
34 * Creates a new multimap.
35 * @constructor
36 * @struct
37 * @final
38 */
39 goog.labs.structs.Multimap = function() {
40 this.clear();
41 };
42
43
44 /**
45 * The backing map.
46 * @type {!goog.labs.structs.Map}
47 * @private
48 */
49 goog.labs.structs.Multimap.prototype.map_;
50
51
52 /**
53 * @type {number}
54 * @private
55 */
56 goog.labs.structs.Multimap.prototype.count_ = 0;
57
58
59 /**
60 * Clears the multimap.
61 */
62 goog.labs.structs.Multimap.prototype.clear = function() {
63 this.count_ = 0;
64 this.map_ = new goog.labs.structs.Map();
65 };
66
67
68 /**
69 * Clones this multimap.
70 * @return {!goog.labs.structs.Multimap} A multimap that contains all
71 * the mapping this multimap has.
72 */
73 goog.labs.structs.Multimap.prototype.clone = function() {
74 var map = new goog.labs.structs.Multimap();
75 map.addAllFromMultimap(this);
76 return map;
77 };
78
79
80 /**
81 * Adds the given (key, value) pair to the map. The (key, value) pair
82 * is guaranteed to be added.
83 * @param {string} key The key to add.
84 * @param {*} value The value to add.
85 */
86 goog.labs.structs.Multimap.prototype.add = function(key, value) {
87 var values = this.map_.get(key);
88 if (!values) {
89 this.map_.set(key, (values = []));
90 }
91
92 values.push(value);
93 this.count_++;
94 };
95
96
97 /**
98 * Stores a collection of values to the given key. Does not replace
99 * existing (key, value) pairs.
100 * @param {string} key The key to add.
101 * @param {!Array<*>} values The values to add.
102 */
103 goog.labs.structs.Multimap.prototype.addAllValues = function(key, values) {
104 goog.array.forEach(values, function(v) { this.add(key, v); }, this);
105 };
106
107
108 /**
109 * Adds the contents of the given map/multimap to this multimap.
110 * @param {!(goog.labs.structs.Map|goog.labs.structs.Multimap)} map The
111 * map to add.
112 */
113 goog.labs.structs.Multimap.prototype.addAllFromMultimap = function(map) {
114 goog.array.forEach(map.getEntries(), function(entry) {
115 this.add(entry[0], entry[1]);
116 }, this);
117 };
118
119
120 /**
121 * Replaces all the values for the given key with the given values.
122 * @param {string} key The key whose values are to be replaced.
123 * @param {!Array<*>} values The new values. If empty, this is
124 * equivalent to {@code removaAll(key)}.
125 */
126 goog.labs.structs.Multimap.prototype.replaceValues = function(key, values) {
127 this.removeAll(key);
128 this.addAllValues(key, values);
129 };
130
131
132 /**
133 * Gets the values correspond to the given key.
134 * @param {string} key The key to retrieve.
135 * @return {!Array<*>} An array of values corresponding to the given
136 * key. May be empty. Note that the ordering of values are not
137 * guaranteed to be consistent.
138 */
139 goog.labs.structs.Multimap.prototype.get = function(key) {
140 var values = /** @type {Array<*>} */ (this.map_.get(key));
141 return values ? goog.array.clone(values) : [];
142 };
143
144
145 /**
146 * Removes a single occurrence of (key, value) pair.
147 * @param {string} key The key to remove.
148 * @param {*} value The value to remove.
149 * @return {boolean} Whether any matching (key, value) pair is removed.
150 */
151 goog.labs.structs.Multimap.prototype.remove = function(key, value) {
152 var values = /** @type {Array<*>} */ (this.map_.get(key));
153 if (!values) {
154 return false;
155 }
156
157 var removed = goog.array.removeIf(
158 values, function(v) { return goog.object.is(value, v); });
159
160 if (removed) {
161 this.count_--;
162 if (values.length == 0) {
163 this.map_.remove(key);
164 }
165 }
166 return removed;
167 };
168
169
170 /**
171 * Removes all values corresponding to the given key.
172 * @param {string} key The key whose values are to be removed.
173 * @return {boolean} Whether any value is removed.
174 */
175 goog.labs.structs.Multimap.prototype.removeAll = function(key) {
176 // We have to first retrieve the values from the backing map because
177 // we need to keep track of count (and correctly calculates the
178 // return value). values may be undefined.
179 var values = this.map_.get(key);
180 if (this.map_.remove(key)) {
181 this.count_ -= values.length;
182 return true;
183 }
184
185 return false;
186 };
187
188
189 /**
190 * @return {boolean} Whether the multimap is empty.
191 */
192 goog.labs.structs.Multimap.prototype.isEmpty = function() {
193 return !this.count_;
194 };
195
196
197 /**
198 * @return {number} The count of (key, value) pairs in the map.
199 */
200 goog.labs.structs.Multimap.prototype.getCount = function() {
201 return this.count_;
202 };
203
204
205 /**
206 * @param {string} key The key to check.
207 * @param {*} value The value to check.
208 * @return {boolean} Whether the (key, value) pair exists in the multimap.
209 */
210 goog.labs.structs.Multimap.prototype.containsEntry = function(key, value) {
211 var values = /** @type {Array<*>} */ (this.map_.get(key));
212 if (!values) {
213 return false;
214 }
215
216 var index = goog.array.findIndex(
217 values, function(v) { return goog.object.is(v, value); });
218 return index >= 0;
219 };
220
221
222 /**
223 * @param {string} key The key to check.
224 * @return {boolean} Whether the multimap contains at least one (key,
225 * value) pair with the given key.
226 */
227 goog.labs.structs.Multimap.prototype.containsKey = function(key) {
228 return this.map_.containsKey(key);
229 };
230
231
232 /**
233 * @param {*} value The value to check.
234 * @return {boolean} Whether the multimap contains at least one (key,
235 * value) pair with the given value.
236 */
237 goog.labs.structs.Multimap.prototype.containsValue = function(value) {
238 return goog.array.some(this.map_.getValues(), function(values) {
239 return goog.array.some(/** @type {Array<?>} */ (values), function(v) {
240 return goog.object.is(v, value);
241 });
242 });
243 };
244
245
246 /**
247 * @return {!Array<string>} An array of unique keys.
248 */
249 goog.labs.structs.Multimap.prototype.getKeys = function() {
250 return this.map_.getKeys();
251 };
252
253
254 /**
255 * @return {!Array<*>} An array of values. There may be duplicates.
256 */
257 goog.labs.structs.Multimap.prototype.getValues = function() {
258 return goog.array.flatten(this.map_.getValues());
259 };
260
261
262 /**
263 * @return {!Array<!Array<?>>} An array of entries. Each entry is of the
264 * form [key, value].
265 */
266 goog.labs.structs.Multimap.prototype.getEntries = function() {
267 var keys = this.getKeys();
268 var entries = [];
269 for (var i = 0; i < keys.length; i++) {
270 var key = keys[i];
271 var values = this.get(key);
272 for (var j = 0; j < values.length; j++) {
273 entries.push([key, values[j]]);
274 }
275 }
276 return entries;
277 };