603 lines
16 KiB
JavaScript
603 lines
16 KiB
JavaScript
//@ runDefault
|
|
|
|
/*
|
|
* Licensed to the Apache Software Foundation (ASF) under one or more
|
|
* contributor license agreements. See the NOTICE below for additional
|
|
* information regarding copyright ownership.
|
|
* The ASF licenses this file to You 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.
|
|
*/
|
|
|
|
/******* NOTICE *********
|
|
|
|
Apache Harmony
|
|
Copyright 2006, 2010 The Apache Software Foundation.
|
|
|
|
This product includes software developed at
|
|
The Apache Software Foundation (http://www.apache.org/).
|
|
|
|
Portions of Apache Harmony were originally developed by
|
|
Intel Corporation and are licensed to the Apache Software
|
|
Foundation under the "Software Grant and Corporate Contribution
|
|
License Agreement" and for which the following copyright notices
|
|
apply
|
|
(C) Copyright 2005 Intel Corporation
|
|
(C) Copyright 2005-2006 Intel Corporation
|
|
(C) Copyright 2006 Intel Corporation
|
|
|
|
|
|
The following copyright notice(s) were affixed to portions of the code
|
|
with which this file is now or was at one time distributed
|
|
and are placed here unaltered.
|
|
|
|
(C) Copyright 1997,2004 International Business Machines Corporation.
|
|
All rights reserved.
|
|
|
|
(C) Copyright IBM Corp. 2003.
|
|
|
|
|
|
This software contains code derived from UNIX V7, Copyright(C)
|
|
Caldera International Inc.
|
|
|
|
************************/
|
|
|
|
// This code is a manual translation of Apache Harmony's HashMap class to
|
|
// JavaScript.
|
|
|
|
var HashMap = (function() {
|
|
var DEFAULT_SIZE = 16;
|
|
|
|
function calculateCapacity(x)
|
|
{
|
|
if (x >= 1 << 30)
|
|
return 1 << 30;
|
|
if (x == 0)
|
|
return 16;
|
|
x = x - 1;
|
|
x |= x >> 1;
|
|
x |= x >> 2;
|
|
x |= x >> 4;
|
|
x |= x >> 8;
|
|
x |= x >> 16;
|
|
return x + 1;
|
|
}
|
|
|
|
function computeHashCode(key)
|
|
{
|
|
switch (typeof key) {
|
|
case "undefined":
|
|
return 0;
|
|
case "object":
|
|
if (!key)
|
|
return 0;
|
|
case "function":
|
|
return key.hashCode();
|
|
case "boolean":
|
|
return key | 0;
|
|
case "number":
|
|
if ((key | 0) == key)
|
|
return key;
|
|
key = "" + key; // Compute string hash of the double. It's the best we can do.
|
|
case "string":
|
|
// source: http://en.wikipedia.org/wiki/Java_hashCode()#Sample_implementations_of_the_java.lang.String_algorithm
|
|
var h = 0;
|
|
var len = key.length;
|
|
for (var index = 0; index < len; index++) {
|
|
h = (((31 * h) | 0) + key.charCodeAt(index)) | 0;
|
|
}
|
|
return h;
|
|
default:
|
|
throw new Error("Internal error: Bad JavaScript value type");
|
|
}
|
|
}
|
|
|
|
function equals(a, b)
|
|
{
|
|
if (typeof a != typeof b)
|
|
return false;
|
|
switch (typeof a) {
|
|
case "object":
|
|
if (!a)
|
|
return !b;
|
|
case "function":
|
|
switch (typeof b) {
|
|
case "object":
|
|
case "function":
|
|
return a.equals(b);
|
|
default:
|
|
return false;
|
|
}
|
|
default:
|
|
return a == b;
|
|
}
|
|
}
|
|
|
|
function Entry(key, hash, value)
|
|
{
|
|
this._key = key;
|
|
this._value = value;
|
|
this._origKeyHash = hash;
|
|
this._next = null;
|
|
}
|
|
|
|
Entry.prototype = {
|
|
clone: function()
|
|
{
|
|
var result = new Entry(this._key, this._hash, this._value);
|
|
if (this._next)
|
|
result._next = this._next.clone();
|
|
return result;
|
|
},
|
|
|
|
toString: function()
|
|
{
|
|
return this._key + "=" + this._value;
|
|
},
|
|
|
|
get key()
|
|
{
|
|
return this._key;
|
|
},
|
|
|
|
get value()
|
|
{
|
|
return this._value;
|
|
}
|
|
};
|
|
|
|
function AbstractMapIterator(map)
|
|
{
|
|
this._associatedMap = map;
|
|
this._expectedModCount = map._modCount;
|
|
this._futureEntry = null;
|
|
this._currentEntry = null;
|
|
this._prevEntry = null;
|
|
this._position = 0;
|
|
}
|
|
|
|
AbstractMapIterator.prototype = {
|
|
hasNext: function()
|
|
{
|
|
if (this._futureEntry)
|
|
return true;
|
|
while (this._position < this._associatedMap._elementData.length) {
|
|
if (!this._associatedMap._elementData[this._position])
|
|
this._position++;
|
|
else
|
|
return true;
|
|
}
|
|
return false;
|
|
},
|
|
|
|
_checkConcurrentMod: function()
|
|
{
|
|
if (this._expectedModCount != this._associatedMap._modCount)
|
|
throw new Error("Concurrent HashMap modification detected");
|
|
},
|
|
|
|
_makeNext: function()
|
|
{
|
|
this._checkConcurrentMod();
|
|
if (!this.hasNext())
|
|
throw new Error("No such element");
|
|
if (!this._futureEntry) {
|
|
this._currentEntry = this._associatedMap._elementData[this._position++];
|
|
this._futureEntry = this._currentEntry._next;
|
|
this._prevEntry = null;
|
|
return;
|
|
}
|
|
if (this._currentEntry)
|
|
this._prevEntry = this._currentEntry;
|
|
this._currentEntry = this._futureEntry;
|
|
this._futureEntry = this._futureEntry._next;
|
|
},
|
|
|
|
remove: function()
|
|
{
|
|
this._checkConcurrentMod();
|
|
if (!this._currentEntry)
|
|
throw new Error("Illegal state");
|
|
if (!this._prevEntry) {
|
|
var index = this._currentEntry._origKeyHash & (this._associatedMap._elementData.length - 1);
|
|
this._associatedMap._elementData[index] = this._associatedMap._elementData[index]._next;
|
|
} else
|
|
this._prevEntry._next = this._currentEntry._next;
|
|
this._currentEntry = null;
|
|
this._expectedModCount++;
|
|
this._associatedMap._modCount++;
|
|
this._associatedMap._elementCount--;
|
|
}
|
|
};
|
|
|
|
function EntryIterator(map)
|
|
{
|
|
AbstractMapIterator.call(this, map);
|
|
}
|
|
|
|
EntryIterator.prototype = {
|
|
next: function()
|
|
{
|
|
this._makeNext();
|
|
return this._currentEntry;
|
|
}
|
|
};
|
|
EntryIterator.prototype.__proto__ = AbstractMapIterator.prototype;
|
|
|
|
function KeyIterator(map)
|
|
{
|
|
AbstractMapIterator.call(this, map);
|
|
}
|
|
|
|
KeyIterator.prototype = {
|
|
next: function()
|
|
{
|
|
this.makeNext();
|
|
return this._currentEntry._key;
|
|
}
|
|
};
|
|
KeyIterator.prototype.__proto__ = AbstractMapIterator.prototype;
|
|
|
|
function ValueIterator(map)
|
|
{
|
|
AbstractMapIterator.call(this, map);
|
|
}
|
|
|
|
ValueIterator.prototype = {
|
|
next: function()
|
|
{
|
|
this.makeNext();
|
|
return this._currentEntry._value;
|
|
}
|
|
};
|
|
ValueIterator.prototype.__proto__ = AbstractMapIterator.prototype;
|
|
|
|
function EntrySet(map)
|
|
{
|
|
this._associatedMap = map;
|
|
}
|
|
|
|
EntrySet.prototype = {
|
|
size: function()
|
|
{
|
|
return this._associatedMap._elementCount;
|
|
},
|
|
|
|
clear: function()
|
|
{
|
|
this._associatedMap.clear();
|
|
},
|
|
|
|
remove: function(object)
|
|
{
|
|
var entry = this._associatedMap._getEntry(object.key);
|
|
if (!entry)
|
|
return false;
|
|
if (!equals(entry._value, object.value))
|
|
return false;
|
|
this._associatedMap._removeEntry(entry);
|
|
return true;
|
|
},
|
|
|
|
contains: function(object)
|
|
{
|
|
var entry = this._associatedMap._getEntry(object.key);
|
|
if (!entry)
|
|
return false;
|
|
return equals(entry._value, object.value);
|
|
},
|
|
|
|
iterator: function()
|
|
{
|
|
return new EntryIterator(this._associatedMap);
|
|
}
|
|
};
|
|
|
|
function KeySet(map)
|
|
{
|
|
this._associatedMap = map;
|
|
}
|
|
|
|
KeySet.prototype = {
|
|
contains: function(object)
|
|
{
|
|
return this._associatedMap.contains(object);
|
|
},
|
|
|
|
size: function()
|
|
{
|
|
return this._associatedMap._elementCount;
|
|
},
|
|
|
|
clear: function()
|
|
{
|
|
this._associatedMap.clear();
|
|
},
|
|
|
|
remove: function(key)
|
|
{
|
|
return !!this._associatedMap.remove(key);
|
|
},
|
|
|
|
iterator: function()
|
|
{
|
|
return new KeyIterator(this._associatedMap);
|
|
}
|
|
};
|
|
|
|
function ValueCollection(map)
|
|
{
|
|
this._associatedMap = map;
|
|
}
|
|
|
|
ValueCollection.prototype = {
|
|
contains: function(object)
|
|
{
|
|
return this._associatedMap.containsValue(object);
|
|
},
|
|
|
|
size: function()
|
|
{
|
|
return this._associatedMap._elementCount;
|
|
},
|
|
|
|
clear: function()
|
|
{
|
|
this._associatedMap.clear();
|
|
},
|
|
|
|
iterator: function()
|
|
{
|
|
return new ValueIterator(this._associatedMap);
|
|
}
|
|
};
|
|
|
|
function HashMap(capacity, loadFactor)
|
|
{
|
|
if (capacity == null)
|
|
capacity = DEFAULT_SIZE;
|
|
if (loadFactor == null)
|
|
loadFactor = 0.75;
|
|
|
|
if (capacity < 0)
|
|
throw new Error("Invalid argument to HashMap constructor: capacity is negative");
|
|
if (loadFactor <= 0)
|
|
throw new Error("Invalid argument to HashMap constructor: loadFactor is not positive");
|
|
|
|
this._capacity = calculateCapacity(capacity);
|
|
this._elementCount = 0;
|
|
this._elementData = new Array(this.capacity);
|
|
this._loadFactor = loadFactor;
|
|
this._modCount = 0;
|
|
this._computeThreshold();
|
|
}
|
|
|
|
HashMap.prototype = {
|
|
_computeThreshold: function()
|
|
{
|
|
this._threshold = (this._elementData.length * this._loadFactor) | 0;
|
|
},
|
|
|
|
clear: function()
|
|
{
|
|
if (!this._elementCount)
|
|
return;
|
|
|
|
this._elementCount = 0;
|
|
for (var i = this._elementData.length; i--;)
|
|
this._elementData[i] = null;
|
|
this._modCount++;
|
|
},
|
|
|
|
clone: function()
|
|
{
|
|
var result = new HashMap(this._elementData.length, this._loadFactor);
|
|
result.putAll(this);
|
|
return result;
|
|
},
|
|
|
|
containsKey: function(key)
|
|
{
|
|
return !!this._getEntry(key);
|
|
},
|
|
|
|
containsValue: function(value)
|
|
{
|
|
for (var i = this._elementData.length; i--;) {
|
|
for (var entry = this._elementData[i]; entry; entry = entry._next) {
|
|
if (equals(value, entry._value))
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
},
|
|
|
|
entrySet: function()
|
|
{
|
|
return new EntrySet(this);
|
|
},
|
|
|
|
get: function(key)
|
|
{
|
|
var entry = this._getEntry(key);
|
|
if (entry)
|
|
return entry._value;
|
|
return null;
|
|
},
|
|
|
|
_getEntry: function(key)
|
|
{
|
|
var hash = computeHashCode(key);
|
|
var index = hash & (this._elementData.length - 1);
|
|
return this._findKeyEntry(key, index, hash);
|
|
},
|
|
|
|
_findKeyEntry: function(key, index, keyHash)
|
|
{
|
|
var entry = this._elementData[index];
|
|
while (entry && (entry._origKeyHash != keyHash || !equals(key, entry._key)))
|
|
entry = entry._next;
|
|
return entry;
|
|
},
|
|
|
|
isEmpty: function()
|
|
{
|
|
return !this._elementCount;
|
|
},
|
|
|
|
keySet: function()
|
|
{
|
|
return new KeySet(this);
|
|
},
|
|
|
|
put: function(key, value)
|
|
{
|
|
var hash = computeHashCode(key);
|
|
var index = hash & (this._elementData.length - 1);
|
|
var entry = this._findKeyEntry(key, index, hash);
|
|
if (!entry) {
|
|
this._modCount++;
|
|
entry = this._createHashedEntry(key, index, hash);
|
|
if (++this._elementCount > this._threshold)
|
|
this._rehash();
|
|
}
|
|
|
|
var result = entry._value;
|
|
entry._value = value;
|
|
return result;
|
|
},
|
|
|
|
_createHashedEntry: function(key, index, hash)
|
|
{
|
|
var entry = new Entry(key, hash, null);
|
|
entry._next = this._elementData[index];
|
|
this._elementData[index] = entry;
|
|
return entry;
|
|
},
|
|
|
|
putAll: function(map)
|
|
{
|
|
if (map.isEmpty())
|
|
return;
|
|
for (var iter = map.entrySet().iterator(); iter.hasNext();) {
|
|
var entry = iter.next();
|
|
put(entry.key, entry.value);
|
|
}
|
|
},
|
|
|
|
_rehash: function(capacity)
|
|
{
|
|
if (capacity == null)
|
|
capacity = this._elementData.length;
|
|
|
|
var length = calculateCapacity(!capacity ? 1 : capacity << 1);
|
|
var newData = new Array(length);
|
|
for (var i = 0; i < this._elementData.length; ++i) {
|
|
var entry = this._elementData[i];
|
|
this._elementData[i] = null;
|
|
while (entry) {
|
|
var index = entry._origKeyHash & (length - 1);
|
|
var next = entry._next;
|
|
entry._next = newData[index];
|
|
newData[index] = entry;
|
|
entry = next;
|
|
}
|
|
}
|
|
this._elementData = newData;
|
|
this._computeThreshold();
|
|
},
|
|
|
|
remove: function(key)
|
|
{
|
|
var entry = this._removeEntryForKey(key);
|
|
if (!entry)
|
|
return null;
|
|
return entry._value;
|
|
},
|
|
|
|
_removeEntry: function(entry)
|
|
{
|
|
var index = entry._origKeyHash & (this._elementData.length - 1);
|
|
var current = this._elementData[index];
|
|
if (current == entry)
|
|
this._elementData[index] = entry._next;
|
|
else {
|
|
while (current._next != entry)
|
|
current = current._next;
|
|
current._next = entry._next;
|
|
}
|
|
this._modCount++;
|
|
this._elementCount--;
|
|
},
|
|
|
|
_removeEntryForKey: function(key)
|
|
{
|
|
var hash = computeHashCode(key);
|
|
var index = hash & (this._elementData.length - 1);
|
|
var entry = this._elementData[index];
|
|
var last = null;
|
|
while (entry != null && !(entry._origKeyHash == hash && equals(key, entry._key))) {
|
|
last = entry;
|
|
entry = entry._next;
|
|
}
|
|
if (!entry)
|
|
return null;
|
|
if (!last)
|
|
this._elementData[index] = entry._next;
|
|
else
|
|
last._next = entry._next;
|
|
this._modCount++;
|
|
this._elementCount--;
|
|
return entry;
|
|
},
|
|
|
|
size: function()
|
|
{
|
|
return this._elementCount;
|
|
},
|
|
|
|
values: function()
|
|
{
|
|
return new ValueCollection(this);
|
|
}
|
|
};
|
|
|
|
return HashMap;
|
|
})();
|
|
|
|
var map = new HashMap();
|
|
var COUNT = 500000;
|
|
|
|
for (var i = 0; i < COUNT; ++i)
|
|
map.put(i, 42);
|
|
|
|
var result = 0;
|
|
for (var j = 0; j < 5; ++j) {
|
|
for (var i = 0; i < COUNT; ++i)
|
|
result += map.get(i);
|
|
}
|
|
|
|
var keySum = 0;
|
|
var valueSum = 0;
|
|
for (var iterator = map.entrySet().iterator(); iterator.hasNext();) {
|
|
var entry = iterator.next();
|
|
keySum += entry.key;
|
|
valueSum += entry.value;
|
|
}
|
|
|
|
if (result != 105000000)
|
|
throw "Error: result = " + result;
|
|
if (keySum != 124999750000)
|
|
throw "Error: keySum = " + keySum;
|
|
if (valueSum != 21000000)
|
|
throw "Error: valueSum = " + valueSum;
|
|
|