// Copyright 2012 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 A collection similar to
 * {@code goog.labs.structs.Map}, but also allows associating multiple
 * values with a single key.
 *
 * This implementation ensures that you can use any string keys.
 *
 * @author chrishenry@google.com (Chris Henry)
 */

goog.provide('goog.labs.structs.Multimap');

goog.require('goog.array');
goog.require('goog.labs.structs.Map');
goog.require('goog.object');



/**
 * Creates a new multimap.
 * @constructor
 * @struct
 * @final
 */
goog.labs.structs.Multimap = function() {
  this.clear();
};


/**
 * The backing map.
 * @type {!goog.labs.structs.Map}
 * @private
 */
goog.labs.structs.Multimap.prototype.map_;


/**
 * @type {number}
 * @private
 */
goog.labs.structs.Multimap.prototype.count_ = 0;


/**
 * Clears the multimap.
 */
goog.labs.structs.Multimap.prototype.clear = function() {
  this.count_ = 0;
  this.map_ = new goog.labs.structs.Map();
};


/**
 * Clones this multimap.
 * @return {!goog.labs.structs.Multimap} A multimap that contains all
 *     the mapping this multimap has.
 */
goog.labs.structs.Multimap.prototype.clone = function() {
  var map = new goog.labs.structs.Multimap();
  map.addAllFromMultimap(this);
  return map;
};


/**
 * Adds the given (key, value) pair to the map. The (key, value) pair
 * is guaranteed to be added.
 * @param {string} key The key to add.
 * @param {*} value The value to add.
 */
goog.labs.structs.Multimap.prototype.add = function(key, value) {
  var values = this.map_.get(key);
  if (!values) {
    this.map_.set(key, (values = []));
  }

  values.push(value);
  this.count_++;
};


/**
 * Stores a collection of values to the given key. Does not replace
 * existing (key, value) pairs.
 * @param {string} key The key to add.
 * @param {!Array<*>} values The values to add.
 */
goog.labs.structs.Multimap.prototype.addAllValues = function(key, values) {
  goog.array.forEach(values, function(v) { this.add(key, v); }, this);
};


/**
 * Adds the contents of the given map/multimap to this multimap.
 * @param {!(goog.labs.structs.Map|goog.labs.structs.Multimap)} map The
 *     map to add.
 */
goog.labs.structs.Multimap.prototype.addAllFromMultimap = function(map) {
  goog.array.forEach(map.getEntries(), function(entry) {
    this.add(entry[0], entry[1]);
  }, this);
};


/**
 * Replaces all the values for the given key with the given values.
 * @param {string} key The key whose values are to be replaced.
 * @param {!Array<*>} values The new values. If empty, this is
 *     equivalent to {@code removaAll(key)}.
 */
goog.labs.structs.Multimap.prototype.replaceValues = function(key, values) {
  this.removeAll(key);
  this.addAllValues(key, values);
};


/**
 * Gets the values correspond to the given key.
 * @param {string} key The key to retrieve.
 * @return {!Array<*>} An array of values corresponding to the given
 *     key. May be empty. Note that the ordering of values are not
 *     guaranteed to be consistent.
 */
goog.labs.structs.Multimap.prototype.get = function(key) {
  var values = /** @type {Array<*>} */ (this.map_.get(key));
  return values ? goog.array.clone(values) : [];
};


/**
 * Removes a single occurrence of (key, value) pair.
 * @param {string} key The key to remove.
 * @param {*} value The value to remove.
 * @return {boolean} Whether any matching (key, value) pair is removed.
 */
goog.labs.structs.Multimap.prototype.remove = function(key, value) {
  var values = /** @type {Array<*>} */ (this.map_.get(key));
  if (!values) {
    return false;
  }

  var removed = goog.array.removeIf(
      values, function(v) { return goog.object.is(value, v); });

  if (removed) {
    this.count_--;
    if (values.length == 0) {
      this.map_.remove(key);
    }
  }
  return removed;
};


/**
 * Removes all values corresponding to the given key.
 * @param {string} key The key whose values are to be removed.
 * @return {boolean} Whether any value is removed.
 */
goog.labs.structs.Multimap.prototype.removeAll = function(key) {
  // We have to first retrieve the values from the backing map because
  // we need to keep track of count (and correctly calculates the
  // return value). values may be undefined.
  var values = this.map_.get(key);
  if (this.map_.remove(key)) {
    this.count_ -= values.length;
    return true;
  }

  return false;
};


/**
 * @return {boolean} Whether the multimap is empty.
 */
goog.labs.structs.Multimap.prototype.isEmpty = function() {
  return !this.count_;
};


/**
 * @return {number} The count of (key, value) pairs in the map.
 */
goog.labs.structs.Multimap.prototype.getCount = function() {
  return this.count_;
};


/**
 * @param {string} key The key to check.
 * @param {*} value The value to check.
 * @return {boolean} Whether the (key, value) pair exists in the multimap.
 */
goog.labs.structs.Multimap.prototype.containsEntry = function(key, value) {
  var values = /** @type {Array<*>} */ (this.map_.get(key));
  if (!values) {
    return false;
  }

  var index = goog.array.findIndex(
      values, function(v) { return goog.object.is(v, value); });
  return index >= 0;
};


/**
 * @param {string} key The key to check.
 * @return {boolean} Whether the multimap contains at least one (key,
 *     value) pair with the given key.
 */
goog.labs.structs.Multimap.prototype.containsKey = function(key) {
  return this.map_.containsKey(key);
};


/**
 * @param {*} value The value to check.
 * @return {boolean} Whether the multimap contains at least one (key,
 *     value) pair with the given value.
 */
goog.labs.structs.Multimap.prototype.containsValue = function(value) {
  return goog.array.some(this.map_.getValues(), function(values) {
    return goog.array.some(/** @type {Array<?>} */ (values), function(v) {
      return goog.object.is(v, value);
    });
  });
};


/**
 * @return {!Array<string>} An array of unique keys.
 */
goog.labs.structs.Multimap.prototype.getKeys = function() {
  return this.map_.getKeys();
};


/**
 * @return {!Array<*>} An array of values. There may be duplicates.
 */
goog.labs.structs.Multimap.prototype.getValues = function() {
  return goog.array.flatten(this.map_.getValues());
};


/**
 * @return {!Array<!Array<?>>} An array of entries. Each entry is of the
 *     form [key, value].
 */
goog.labs.structs.Multimap.prototype.getEntries = function() {
  var keys = this.getKeys();
  var entries = [];
  for (var i = 0; i < keys.length; i++) {
    var key = keys[i];
    var values = this.get(key);
    for (var j = 0; j < values.length; j++) {
      entries.push([key, values[j]]);
    }
  }
  return entries;
};