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
};
278

279