// 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.

goog.provide('goog.structs.SetTest');
goog.setTestOnly('goog.structs.SetTest');

goog.require('goog.iter');
goog.require('goog.structs');
goog.require('goog.structs.Set');
goog.require('goog.testing.jsunit');

var Set = goog.structs.Set;

function stringifySet(s) {
  return goog.structs.getValues(s).join('');
}

function testGetCount() {
  var s = new Set;
  var a = new String('a');
  s.add(a);
  var b = new String('b');
  s.add(b);
  var c = new String('c');
  s.add(c);
  assertEquals('count, should be 3', s.getCount(), 3);
  var d = new String('d');
  s.add(d);
  assertEquals('count, should be 4', s.getCount(), 4);
  s.remove(d);
  assertEquals('count, should be 3', s.getCount(), 3);

  s = new Set;
  s.add('a');
  s.add('b');
  s.add('c');
  assertEquals('count, should be 3', s.getCount(), 3);
  s.add('d');
  assertEquals('count, should be 4', s.getCount(), 4);
  s.remove('d');
  assertEquals('count, should be 3', s.getCount(), 3);
}

function testGetValues() {
  var s = new Set;
  var a = new String('a');
  s.add(a);
  var b = new String('b');
  s.add(b);
  var c = new String('c');
  s.add(c);
  var d = new String('d');
  s.add(d);
  assertEquals(s.getValues().join(''), 'abcd');

  var s = new Set;
  s.add('a');
  s.add('b');
  s.add('c');
  s.add('d');
  assertEquals(s.getValues().join(''), 'abcd');
}

function testContains() {
  var s = new Set;
  var a = new String('a');
  s.add(a);
  var b = new String('b');
  s.add(b);
  var c = new String('c');
  s.add(c);
  var d = new String('d');
  s.add(d);
  var e = new String('e');

  assertTrue("contains, Should contain 'a'", s.contains(a));
  assertFalse("contains, Should not contain 'e'", s.contains(e));

  s = new Set;
  s.add('a');
  s.add('b');
  s.add('c');
  s.add('d');

  assertTrue("contains, Should contain 'a'", s.contains('a'));
  assertFalse("contains, Should not contain 'e'", s.contains('e'));
}

function testContainsFunctionValue() {
  var s = new Set;

  var fn1 = function() {};

  assertFalse(s.contains(fn1));
  s.add(fn1);
  assertTrue(s.contains(fn1));

  var fn2 = function() {};

  assertFalse(s.contains(fn2));
  s.add(fn2);
  assertTrue(s.contains(fn2));

  assertEquals(s.getCount(), 2);
}

function testContainsAll() {
  var set = new Set([1, 2, 3]);

  assertTrue('{1, 2, 3} contains []', set.containsAll([]));
  assertTrue('{1, 2, 3} contains [1]', set.containsAll([1]));
  assertTrue('{1, 2, 3} contains [1, 1]', set.containsAll([1, 1]));
  assertTrue('{1, 2, 3} contains [3, 2, 1]', set.containsAll([3, 2, 1]));
  assertFalse("{1, 2, 3} doesn't contain [4]", set.containsAll([4]));
  assertFalse("{1, 2, 3} doesn't contain [1, 4]", set.containsAll([1, 4]));

  assertTrue('{1, 2, 3} contains {a: 1}', set.containsAll({a: 1}));
  assertFalse("{1, 2, 3} doesn't contain {a: 4}", set.containsAll({a: 4}));

  assertTrue('{1, 2, 3} contains {1}', set.containsAll(new Set([1])));
  assertFalse("{1, 2, 3} doesn't contain {4}", set.containsAll(new Set([4])));
}

function testIntersection() {
  var emptySet = new Set;

  assertTrue(
      'intersection of empty set and [] should be empty',
      emptySet.intersection([]).isEmpty());
  assertIntersection(
      'intersection of 2 empty sets should be empty', emptySet, new Set(),
      new Set());

  var abcdSet = new Set();
  abcdSet.add('a');
  abcdSet.add('b');
  abcdSet.add('c');
  abcdSet.add('d');

  assertTrue(
      'intersection of populated set and [] should be empty',
      abcdSet.intersection([]).isEmpty());
  assertIntersection(
      'intersection of populated set and empty set should be empty', abcdSet,
      new Set(), new Set());

  var bcSet = new Set(['b', 'c']);
  assertIntersection(
      'intersection of [a,b,c,d] and [b,c]', abcdSet, bcSet, bcSet);

  var bceSet = new Set(['b', 'c', 'e']);
  assertIntersection(
      'intersection of [a,b,c,d] and [b,c,e]', abcdSet, bceSet, bcSet);
}

function testDifference() {
  var emptySet = new Set;

  assertTrue(
      'difference of empty set and [] should be empty',
      emptySet.difference([]).isEmpty());
  assertTrue(
      'difference of 2 empty sets should be empty',
      emptySet.difference(new Set()).isEmpty());

  var abcdSet = new Set(['a', 'b', 'c', 'd']);

  assertTrue(
      'difference of populated set and [] should be the populated set',
      abcdSet.difference([]).equals(abcdSet));
  assertTrue(
      'difference of populated set and empty set should be the populated set',
      abcdSet.difference(new Set()).equals(abcdSet));
  assertTrue(
      'difference of two identical sets should be the empty set',
      abcdSet.difference(abcdSet).equals(new Set()));

  var bcSet = new Set(['b', 'c']);
  assertTrue(
      'difference of [a,b,c,d] and [b,c] shoule be [a,d]',
      abcdSet.difference(bcSet).equals(new Set(['a', 'd'])));
  assertTrue(
      'difference of [b,c] and [a,b,c,d] should be the empty set',
      bcSet.difference(abcdSet).equals(new Set()));

  var xyzSet = new Set(['x', 'y', 'z']);
  assertTrue(
      'difference of [a,b,c,d] and [x,y,z] should be the [a,b,c,d]',
      abcdSet.difference(xyzSet).equals(abcdSet));
}


/**
 * Helper function to assert intersection is commutative.
 */
function assertIntersection(msg, set1, set2, expectedIntersection) {
  assertTrue(
      msg + ': set1->set2',
      set1.intersection(set2).equals(expectedIntersection));
  assertTrue(
      msg + ': set2->set1',
      set2.intersection(set1).equals(expectedIntersection));
}

function testRemoveAll() {
  assertRemoveAll('removeAll of empty set from empty set', [], [], []);
  assertRemoveAll(
      'removeAll of empty set from populated set', ['a', 'b', 'c', 'd'], [],
      ['a', 'b', 'c', 'd']);
  assertRemoveAll(
      'removeAll of [a,d] from [a,b,c,d]', ['a', 'b', 'c', 'd'], ['a', 'd'],
      ['b', 'c']);
  assertRemoveAll(
      'removeAll of [b,c] from [a,b,c,d]', ['a', 'b', 'c', 'd'], ['b', 'c'],
      ['a', 'd']);
  assertRemoveAll(
      'removeAll of [b,c,e] from [a,b,c,d]', ['a', 'b', 'c', 'd'],
      ['b', 'c', 'e'], ['a', 'd']);
  assertRemoveAll(
      'removeAll of [a,b,c,d] from [a,d]', ['a', 'd'], ['a', 'b', 'c', 'd'],
      []);
  assertRemoveAll(
      'removeAll of [a,b,c,d] from [b,c]', ['b', 'c'], ['a', 'b', 'c', 'd'],
      []);
  assertRemoveAll(
      'removeAll of [a,b,c,d] from [b,c,e]', ['b', 'c', 'e'],
      ['a', 'b', 'c', 'd'], ['e']);
}


/**
 * Helper function to test removeAll.
 */
function assertRemoveAll(msg, elements1, elements2, expectedResult) {
  var set1 = new Set(elements1);
  var set2 = new Set(elements2);
  set1.removeAll(set2);

  assertTrue(
      msg + ': set1 count increased after removeAll',
      elements1.length >= set1.getCount());
  assertEquals(
      msg + ': set2 count changed after removeAll', elements2.length,
      set2.getCount());
  assertTrue(msg + ': wrong set1 after removeAll', set1.equals(expectedResult));
  assertIntersection(
      msg + ': non-empty intersection after removeAll', set1, set2, []);
}

function testAdd() {
  var s = new Set;
  var a = new String('a');
  var b = new String('b');
  s.add(a);
  assertTrue(s.contains(a));
  s.add(b);
  assertTrue(s.contains(b));

  s = new Set;
  s.add('a');
  assertTrue(s.contains('a'));
  s.add('b');
  assertTrue(s.contains('b'));
  s.add(null);
  assertTrue('contains null', s.contains(null));
  assertFalse('does not contain "null"', s.contains('null'));
}


function testClear() {
  var s = new Set;
  var a = new String('a');
  s.add(a);
  var b = new String('b');
  s.add(b);
  var c = new String('c');
  s.add(c);
  var d = new String('d');
  s.add(d);
  s.clear();
  assertTrue('cleared so it should be empty', s.isEmpty());
  assertTrue("cleared so it should not contain 'a' key", !s.contains(a));

  s = new Set;
  s.add('a');
  s.add('b');
  s.add('c');
  s.add('d');
  s.clear();
  assertTrue('cleared so it should be empty', s.isEmpty());
  assertTrue("cleared so it should not contain 'a' key", !s.contains('a'));
}


function testAddAll() {
  var s = new Set;
  var a = new String('a');
  var b = new String('b');
  var c = new String('c');
  var d = new String('d');
  s.addAll([a, b, c, d]);
  assertTrue('addAll so it should not be empty', !s.isEmpty());
  assertTrue("addAll so it should contain 'c' key", s.contains(c));

  var s2 = new Set;
  s2.addAll(s);
  assertTrue('addAll so it should not be empty', !s2.isEmpty());
  assertTrue("addAll so it should contain 'c' key", s2.contains(c));


  s = new Set;
  s.addAll(['a', 'b', 'c', 'd']);
  assertTrue('addAll so it should not be empty', !s.isEmpty());
  assertTrue("addAll so it should contain 'c' key", s.contains('c'));

  s2 = new Set;
  s2.addAll(s);
  assertTrue('addAll so it should not be empty', !s2.isEmpty());
  assertTrue("addAll so it should contain 'c' key", s2.contains('c'));
}


function testConstructor() {
  var s = new Set;
  var a = new String('a');
  s.add(a);
  var b = new String('b');
  s.add(b);
  var c = new String('c');
  s.add(c);
  var d = new String('d');
  s.add(d);
  var s2 = new Set(s);
  assertFalse('constr with Set so it should not be empty', s2.isEmpty());
  assertTrue('constr with Set so it should contain c', s2.contains(c));

  s = new Set;
  s.add('a');
  s.add('b');
  s.add('c');
  s.add('d');
  s2 = new Set(s);
  assertFalse('constr with Set so it should not be empty', s2.isEmpty());
  assertTrue('constr with Set so it should contain c', s2.contains('c'));
}


function testClone() {
  var s = new Set;
  var a = new String('a');
  s.add(a);
  var b = new String('b');
  s.add(b);
  var c = new String('c');
  s.add(c);
  var d = new String('d');
  s.add(d);

  var s2 = s.clone();
  assertFalse('clone so it should not be empty', s2.isEmpty());
  assertTrue("clone so it should contain 'c' key", s2.contains(c));

  var s = new Set;
  s.add('a');
  s.add('b');
  s.add('c');
  s.add('d');

  s2 = s.clone();
  assertFalse('clone so it should not be empty', s2.isEmpty());
  assertTrue("clone so it should contain 'c' key", s2.contains('c'));
}


/**
 * Helper method for testEquals().
 * @param {Object} a First element to use in the tests.
 * @param {Object} b Second element to use in the tests.
 * @param {Object} c Third element to use in the tests.
 * @param {Object} d Fourth element to use in the tests.
 */
function helperForTestEquals(a, b, c, d) {
  var s = new Set([a, b, c]);

  assertTrue('set == itself', s.equals(s));
  assertTrue('set == same set', s.equals(new Set([a, b, c])));
  assertTrue('set == its clone', s.equals(s.clone()));
  assertTrue('set == array of same elements', s.equals([a, b, c]));
  assertTrue(
      'set == array of same elements in different order', s.equals([c, b, a]));

  assertFalse('set != empty set', s.equals(new Set));
  assertFalse('set != its subset', s.equals(new Set([a, c])));
  assertFalse('set != its superset', s.equals(new Set([a, b, c, d])));
  assertFalse('set != different set', s.equals(new Set([b, c, d])));
  assertFalse('set != its subset as array', s.equals([a, c]));
  assertFalse('set != its superset as array', s.equals([a, b, c, d]));
  assertFalse('set != different set as array', s.equals([b, c, d]));
  assertFalse('set != [a, b, c, c]', s.equals([a, b, c, c]));
  assertFalse('set != [a, b, b]', s.equals([a, b, b]));
  assertFalse('set != [a, a]', s.equals([a, a]));
}


function testEquals() {
  helperForTestEquals(1, 2, 3, 4);
  helperForTestEquals('a', 'b', 'c', 'd');
  helperForTestEquals(
      new String('a'), new String('b'), new String('c'), new String('d'));
}


/**
 * Helper method for testIsSubsetOf().
 * @param {Object} a First element to use in the tests.
 * @param {Object} b Second element to use in the tests.
 * @param {Object} c Third element to use in the tests.
 * @param {Object} d Fourth element to use in the tests.
 */
function helperForTestIsSubsetOf(a, b, c, d) {
  var s = new Set([a, b, c]);

  assertTrue('set <= itself', s.isSubsetOf(s));
  assertTrue('set <= same set', s.isSubsetOf(new Set([a, b, c])));
  assertTrue('set <= its clone', s.isSubsetOf(s.clone()));
  assertTrue('set <= array of same elements', s.isSubsetOf([a, b, c]));
  assertTrue(
      'set <= array of same elements in different order', s.equals([c, b, a]));

  assertTrue('set <= Set([a, b, c, d])', s.isSubsetOf(new Set([a, b, c, d])));
  assertTrue('set <= [a, b, c, d]', s.isSubsetOf([a, b, c, d]));
  assertTrue('set <= [a, b, c, c]', s.isSubsetOf([a, b, c, c]));

  assertFalse('set !<= Set([a, b])', s.isSubsetOf(new Set([a, b])));
  assertFalse('set !<= [a, b]', s.isSubsetOf([a, b]));
  assertFalse('set !<= Set([c, d])', s.isSubsetOf(new Set([c, d])));
  assertFalse('set !<= [c, d]', s.isSubsetOf([c, d]));
  assertFalse('set !<= Set([a, c, d])', s.isSubsetOf(new Set([a, c, d])));
  assertFalse('set !<= [a, c, d]', s.isSubsetOf([a, c, d]));
  assertFalse('set !<= [a, a, b]', s.isSubsetOf([a, a, b]));
  assertFalse('set !<= [a, a, b, b]', s.isSubsetOf([a, a, b, b]));
}


function testIsSubsetOf() {
  helperForTestIsSubsetOf(1, 2, 3, 4);
  helperForTestIsSubsetOf('a', 'b', 'c', 'd');
  helperForTestIsSubsetOf(
      new String('a'), new String('b'), new String('c'), new String('d'));
}


function testForEach() {
  var s = new Set;
  var a = new String('a');
  s.add(a);
  var b = new String('b');
  s.add(b);
  var c = new String('c');
  s.add(c);
  var d = new String('d');
  s.add(d);
  var str = '';
  goog.structs.forEach(s, function(val, key, set) {
    assertUndefined(key);
    assertEquals(s, set);
    str += val;
  });
  assertEquals(str, 'abcd');

  s = new Set;
  s.add('a');
  s.add('b');
  s.add('c');
  s.add('d');
  str = '';
  goog.structs.forEach(s, function(val, key, set) {
    assertUndefined(key);
    assertEquals(s, set);
    str += val;
  });
  assertEquals(str, 'abcd');
}


function testFilter() {
  var s = new Set;
  var a = new Number(0);
  s.add(a);
  var b = new Number(1);
  s.add(b);
  var c = new Number(2);
  s.add(c);
  var d = new Number(3);
  s.add(d);

  var s2 = goog.structs.filter(s, function(val, key, set) {
    assertUndefined(key);
    assertEquals(s, set);
    return val > 1;
  });
  assertEquals(stringifySet(s2), '23');

  s = new Set;
  s.add(0);
  s.add(1);
  s.add(2);
  s.add(3);

  s2 = goog.structs.filter(s, function(val, key, set) {
    assertUndefined(key);
    assertEquals(s, set);
    return val > 1;
  });
  assertEquals(stringifySet(s2), '23');
}


function testSome() {
  var s = new Set;
  var a = new Number(0);
  s.add(a);
  var b = new Number(1);
  s.add(b);
  var c = new Number(2);
  s.add(c);
  var d = new Number(3);
  s.add(d);

  var b = goog.structs.some(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val > 1;
  });
  assertTrue(b);
  var b = goog.structs.some(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val > 100;
  });
  assertFalse(b);

  s = new Set;
  s.add(0);
  s.add(1);
  s.add(2);
  s.add(3);

  b = goog.structs.some(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val > 1;
  });
  assertTrue(b);
  b = goog.structs.some(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val > 100;
  });
  assertFalse(b);
}


function testEvery() {
  var s = new Set;
  var a = new Number(0);
  s.add(a);
  var b = new Number(1);
  s.add(b);
  var c = new Number(2);
  s.add(c);
  var d = new Number(3);
  s.add(d);

  var b = goog.structs.every(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val >= 0;
  });
  assertTrue(b);
  b = goog.structs.every(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val > 1;
  });
  assertFalse(b);

  s = new Set;
  s.add(0);
  s.add(1);
  s.add(2);
  s.add(3);

  b = goog.structs.every(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val >= 0;
  });
  assertTrue(b);
  b = goog.structs.every(s, function(val, key, s2) {
    assertUndefined(key);
    assertEquals(s, s2);
    return val > 1;
  });
  assertFalse(b);
}

function testIterator() {
  var s = new Set;
  s.add(0);
  s.add(1);
  s.add(2);
  s.add(3);
  s.add(4);

  assertEquals('01234', goog.iter.join(s, ''));

  s.remove(1);
  s.remove(3);

  assertEquals('024', goog.iter.join(s, ''));
}