mini_cocopi/block/closure/goog/structs/heap_test.js

// 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.HeapTest');
goog.setTestOnly('goog.structs.HeapTest');

goog.require('goog.structs');
goog.require('goog.structs.Heap');
goog.require('goog.testing.jsunit');


/**
 * Constructs a heap from key-value pairs passed as arguments
 * @param {...!Array} var_args List of length-2 arrays [key, value]
 * @return {goog.structs.Heap} Heap constructed from passed in key-value pairs
 */
function makeHeap(var_args) {
  var h = new goog.structs.Heap();
  var key, value;

  for (var i = 0; i < arguments.length; i++) {
    key = arguments[i][0];
    value = arguments[i][1];
    h.insert(key, value);
  }

  return h;
}


function testGetCount1() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  assertEquals('count, should be 4', 4, h.getCount());
  h.remove();
  assertEquals('count, should be 3', 3, h.getCount());
}

function testGetCount2() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  h.remove();
  h.remove();
  h.remove();
  h.remove();
  assertEquals('count, should be 0', 0, h.getCount());
}


function testKeys() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  var keys = h.getKeys();
  for (var i = 0; i < 4; i++) {
    assertTrue('getKeys, key ' + i + ' found', goog.structs.contains(keys, i));
  }
  assertEquals('getKeys, Should be 4 keys', 4, goog.structs.getCount(keys));
}


function testValues() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  var values = h.getValues();

  assertTrue('getKeys, value "a" found', goog.structs.contains(values, 'a'));
  assertTrue('getKeys, value "b" found', goog.structs.contains(values, 'b'));
  assertTrue('getKeys, value "c" found', goog.structs.contains(values, 'c'));
  assertTrue('getKeys, value "d" found', goog.structs.contains(values, 'd'));
  assertEquals('getKeys, Should be 4 keys', 4, goog.structs.getCount(values));
}


function testContainsKey() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);

  for (var i = 0; i < 4; i++) {
    assertTrue('containsKey, key ' + i + ' found', h.containsKey(i));
  }
  assertFalse('containsKey, value 4 not found', h.containsKey(4));
}


function testContainsValue() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);

  assertTrue('containsValue, value "a" found', h.containsValue('a'));
  assertTrue('containsValue, value "b" found', h.containsValue('b'));
  assertTrue('containsValue, value "c" found', h.containsValue('c'));
  assertTrue('containsValue, value "d" found', h.containsValue('d'));
  assertFalse('containsValue, value "e" not found', h.containsValue('e'));
}


function testClone() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  var h2 = h.clone();
  assertTrue('clone so it should not be empty', !h2.isEmpty());
  assertTrue('clone so it should contain key 0', h2.containsKey(0));
  assertTrue('clone so it should contain value "a"', h2.containsValue('a'));
}


function testClear() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  h.clear();
  assertTrue('cleared so it should be empty', h.isEmpty());
}


function testIsEmpty() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  assertFalse('4 values so should not be empty', h.isEmpty());

  h.remove();
  h.remove();
  h.remove();
  assertFalse('1 values so should not be empty', h.isEmpty());

  h.remove();
  assertTrue('0 values so should be empty', h.isEmpty());
}


function testPeek1() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  assertEquals('peek, Should be "a"', 'a', h.peek());
}


function testPeek2() {
  var h = makeHeap([1, 'b'], [3, 'd'], [0, 'a'], [2, 'c']);
  assertEquals('peek, Should be "a"', 'a', h.peek());
}


function testPeek3() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  h.clear();
  assertEquals('peek, Should be "undefined"', undefined, h.peek());
}


function testPeekKey1() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  assertEquals('peekKey, Should be "0"', 0, h.peekKey());
}


function testPeekKey2() {
  var h = makeHeap([1, 'b'], [3, 'd'], [0, 'a'], [2, 'c']);
  assertEquals('peekKey, Should be "0"', 0, h.peekKey());
}


function testPeekKey3() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);
  h.clear();
  assertEquals('peekKey, Should be "undefined"', undefined, h.peekKey());
}


function testRemove1() {
  var h = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);

  assertEquals('remove, Should be "a"', 'a', h.remove());
  assertEquals('remove, Should be "b"', 'b', h.remove());
  assertEquals('remove, Should be "c"', 'c', h.remove());
  assertEquals('remove, Should be "d"', 'd', h.remove());
}


function testRemove2() {
  var h = makeHeap([1, 'b'], [3, 'd'], [0, 'a'], [2, 'c']);

  assertEquals('remove, Should be "a"', 'a', h.remove());
  assertEquals('remove, Should be "b"', 'b', h.remove());
  assertEquals('remove, Should be "c"', 'c', h.remove());
  assertEquals('remove, Should be "d"', 'd', h.remove());
}


function testInsertPeek1() {
  var h = makeHeap();

  h.insert(3, 'd');
  assertEquals('peek, Should be "d"', 'd', h.peek());
  h.insert(2, 'c');
  assertEquals('peek, Should be "c"', 'c', h.peek());
  h.insert(1, 'b');
  assertEquals('peek, Should be "b"', 'b', h.peek());
  h.insert(0, 'a');
  assertEquals('peek, Should be "a"', 'a', h.peek());
}


function testInsertPeek2() {
  var h = makeHeap();

  h.insert(1, 'b');
  assertEquals('peek, Should be "b"', 'b', h.peek());
  h.insert(3, 'd');
  assertEquals('peek, Should be "b"', 'b', h.peek());
  h.insert(0, 'a');
  assertEquals('peek, Should be "a"', 'a', h.peek());
  h.insert(2, 'c');
  assertEquals('peek, Should be "a"', 'a', h.peek());
}

function testInsertAllPeek1() {
  var h1 = makeHeap([1, 'e']);
  var h2 = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);

  h1.insertAll(h2);
  assertEquals('peek, should be "a"', 'a', h1.peek());
}

function testInsertAllPeek2() {
  var h1 = makeHeap([-1, 'z']);
  var h2 = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);

  h1.insertAll(h2);
  assertEquals('peek, should be "z"', 'z', h1.peek());
}

function testInsertAllPeek3() {
  var h1 = makeHeap();
  var h2 = makeHeap([0, 'a'], [1, 'b'], [2, 'c'], [3, 'd']);

  h1.insertAll(h2);
  assertEquals('peek, should be "a"', 'a', h1.peek());
}