Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
633 lines (525 sloc) 15.4 KB
// Copyright (c) 2012 DotNetAnywhere
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
using System;
#if LOCALTEST
using System.Collections;
using System.Collections.Generic;
namespace System_.Collections.Generic {
#else
namespace System.Collections.Generic {
#endif
public class Dictionary<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable {
public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>,
IDisposable, IDictionaryEnumerator, IEnumerator {
Dictionary<TKey, TValue> dict;
private int curSlot, curItem;
internal Enumerator(Dictionary<TKey, TValue> dictionary) {
this.dict = dictionary;
this.curSlot = -1;
this.curItem = 0;
}
public bool MoveNext() {
do {
if (this.curSlot >= this.dict.capacity) {
return false;
}
if (this.curSlot < 0 || this.dict.keys[this.curSlot] == null ||
this.curItem > this.dict.keys[this.curSlot].Count) {
this.curSlot++;
this.curItem = 0;
} else {
this.curItem++;
}
if (this.curSlot >= this.dict.capacity) {
return false;
}
} while (this.dict.keys[this.curSlot] == null || this.curItem >= dict.keys[this.curSlot].Count);
return true;
}
public KeyValuePair<TKey, TValue> Current {
get {
return new KeyValuePair<TKey, TValue>(
this.dict.keys[this.curSlot][this.curItem],
this.dict.values[this.curSlot][this.curItem]
);
}
}
object IEnumerator.Current {
get { return this.Current; }
}
void IEnumerator.Reset() {
this.curSlot = -1;
this.curItem = 0;
}
DictionaryEntry IDictionaryEnumerator.Entry {
get {
return new DictionaryEntry(
this.dict.keys[this.curSlot][this.curItem],
this.dict.values[this.curSlot][this.curItem]
);
}
}
object IDictionaryEnumerator.Key {
get {
return dict.keys[this.curSlot][this.curItem];
}
}
object IDictionaryEnumerator.Value {
get {
return this.dict.values[this.curSlot][this.curItem];
}
}
public void Dispose() {
this.dict = null;
}
}
public sealed class KeyCollection : ICollection<TKey>, IEnumerable<TKey>, ICollection, IEnumerable {
public struct Enumerator : IEnumerator<TKey>, IDisposable, IEnumerator {
private Dictionary<TKey, TValue>.Enumerator hostEnumerator;
internal Enumerator(Dictionary<TKey, TValue> host) {
this.hostEnumerator = host.GetEnumerator();
}
public void Dispose() {
this.hostEnumerator.Dispose();
}
public bool MoveNext() {
return this.hostEnumerator.MoveNext();
}
public TKey Current {
get { return this.hostEnumerator.Current.Key; }
}
object IEnumerator.Current {
get { return this.hostEnumerator.Current.Key; }
}
void IEnumerator.Reset() {
((IEnumerator)this.hostEnumerator).Reset();
}
}
private Dictionary<TKey, TValue> dictionary;
public KeyCollection(Dictionary<TKey, TValue> dictionary) {
if (dictionary == null) {
throw new ArgumentException("dictionary");
}
this.dictionary = dictionary;
}
public void CopyTo(TKey[] array, int index) {
throw new NotImplementedException();
}
public Enumerator GetEnumerator() {
return new Enumerator(this.dictionary);
}
void ICollection<TKey>.Add(TKey item) {
throw new NotSupportedException("this is a read-only collection");
}
void ICollection<TKey>.Clear() {
throw new NotSupportedException("this is a read-only collection");
}
bool ICollection<TKey>.Contains(TKey item) {
return this.dictionary.ContainsKey(item);
}
bool ICollection<TKey>.Remove(TKey item) {
throw new NotSupportedException("this is a read-only collection");
}
IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator() {
return this.GetEnumerator();
}
void ICollection.CopyTo(Array array, int index) {
this.CopyTo((TKey[])array, index);
}
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
public int Count {
get {
return this.dictionary.Count;
}
}
bool ICollection<TKey>.IsReadOnly {
get {
return true;
}
}
bool ICollection.IsSynchronized {
get {
return false;
}
}
object ICollection.SyncRoot {
get {
return ((ICollection)this.dictionary).SyncRoot;
}
}
}
public sealed class ValueCollection : ICollection<TValue>, IEnumerable<TValue>, ICollection, IEnumerable {
public struct Enumerator : IEnumerator<TValue>, IDisposable, IEnumerator {
private Dictionary<TKey, TValue>.Enumerator hostEnumerator;
internal Enumerator(Dictionary<TKey, TValue> host) {
this.hostEnumerator = host.GetEnumerator();
}
public void Dispose() {
this.hostEnumerator.Dispose();
}
public bool MoveNext() {
return this.hostEnumerator.MoveNext();
}
public TValue Current {
get { return this.hostEnumerator.Current.Value; }
}
object IEnumerator.Current {
get { return this.hostEnumerator.Current.Value; }
}
void IEnumerator.Reset() {
((IEnumerator)this.hostEnumerator).Reset();
}
}
private Dictionary<TKey, TValue> dictionary;
public ValueCollection(Dictionary<TKey, TValue> dictionary) {
if (dictionary == null) {
throw new ArgumentException("dictionary");
}
this.dictionary = dictionary;
}
public void CopyTo(TValue[] array, int index) {
throw new NotImplementedException();
}
public Enumerator GetEnumerator() {
return new Enumerator(this.dictionary);
}
void ICollection<TValue>.Add(TValue item) {
throw new NotSupportedException("this is a read-only collection");
}
void ICollection<TValue>.Clear() {
throw new NotSupportedException("this is a read-only collection");
}
bool ICollection<TValue>.Contains(TValue item) {
return this.dictionary.ContainsValue(item);
}
bool ICollection<TValue>.Remove(TValue item) {
throw new NotSupportedException("this is a read-only collection");
}
IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator() {
return this.GetEnumerator();
}
void ICollection.CopyTo(Array array, int index) {
this.CopyTo((TValue[])array, index);
}
IEnumerator IEnumerable.GetEnumerator() {
return this.GetEnumerator();
}
public int Count {
get {
return this.dictionary.Count;
}
}
bool ICollection<TValue>.IsReadOnly {
get {
return true;
}
}
bool ICollection.IsSynchronized {
get {
return false;
}
}
object ICollection.SyncRoot {
get {
return ((ICollection)this.dictionary).SyncRoot;
}
}
}
private static int[] capacities = {
11, 23, 47, 97, 191, 379, 757, 1511, 3023, 6047, 12097, 24179, 48353, 96731
};
private List<TKey>[] keys;
private List<TValue>[] values;
private int capacity, capacityIndex, count;
private IEqualityComparer<TKey> comparer;
public Dictionary() {
this.Init(0, null);
}
public Dictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) { }
public Dictionary(IEqualityComparer<TKey> comparer) {
this.Init(0, comparer);
}
public Dictionary(int capacity) {
this.Init(capacity, null);
}
public Dictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) {
this.Init(dictionary.Count, comparer);
foreach (var item in dictionary) {
this.Add(item.Key, item.Value);
}
}
public Dictionary(int capacity, IEqualityComparer<TKey> comparer) {
this.Init(capacity, comparer);
}
private void Init(int initialCapacity, IEqualityComparer<TKey> comparer) {
// Initialise the comparer
this.comparer = comparer ?? EqualityComparer<TKey>.Default;
// Initialise the capacity of the dictionary
this.capacityIndex = -1;
for (int i = 0; i < capacities.Length; i++) {
if (initialCapacity <= capacities[i]) {
this.capacityIndex = i;
this.capacity = capacities[i];
break;
}
}
if (this.capacityIndex == -1){
// If the capacity is off the end of the scale, then just use the capacity given
this.capacity = initialCapacity;
this.capacityIndex = capacities.Length;
}
this.Clear();
}
private int GetSlot(TKey key) {
uint hash = (uint)key.GetHashCode();
return (int)(hash % (uint)this.capacity);
}
public void Add(TKey key, TValue value) {
Add(key, value, false);
}
private void Add(TKey key, TValue value, bool replace) {
if (key == null) {
throw new ArgumentNullException();
}
int slot = this.GetSlot(key);
List<TKey> keySlot = this.keys[slot];
if (keySlot != null) {
// There are element(s) at this index, so see if this key is already in this dictionary
// Can't use keySlot.IndexOf() because it doesn't honour the comparer
for (int i = keySlot.Count - 1; i >= 0; i--) {
if (this.comparer.Equals(keySlot[i], key)) {
// The key is already in this dictionary
if (replace) {
this.values[slot][i] = value;
return;
} else {
throw new ArgumentException("Key already exists in dictionary");
}
}
}
// Key not already in dictionary, so carry on
}
this.count++;
if (this.count > this.capacity) {
// Increase capacity
List<TKey>[] currentKeys = this.keys;
List<TValue>[] currentValues = this.values;
this.capacityIndex++;
this.capacity = (this.capacityIndex >= capacities.Length) ?
this.capacity * 2 + 1 : capacities[this.capacityIndex];
this.Clear();
// Add all the items in this dictionary to the enlarged dictionary lists.
for (int slotIdx = currentKeys.Length - 1; slotIdx >= 0; slotIdx--) {
List<TKey> currentKeySlot = currentKeys[slotIdx];
if (currentKeySlot != null) {
List<TValue> currentValueSlot = currentValues[slotIdx];
for (int listIdx = currentKeySlot.Count - 1; listIdx >= 0; listIdx--) {
this.Add(currentKeySlot[listIdx], currentValueSlot[listIdx], false);
}
}
}
// Reload these values, as they will have changed due to dictionary capacity resizing
slot = key.GetHashCode() % this.capacity;
keySlot = this.keys[slot];
}
List<TValue> valueSlot;
if (keySlot == null) {
// There are no elements at this index, so create a new list for the element being added
this.keys[slot] = keySlot = new List<TKey>(1);
this.values[slot] = valueSlot = new List<TValue>(1);
} else {
valueSlot = this.values[slot];
}
keySlot.Add(key);
valueSlot.Add(value);
}
public TValue this[TKey key] {
get {
TValue value;
if (this.TryGetValue(key, out value)) {
return value;
}
throw new KeyNotFoundException(key.ToString());
}
set {
Add(key, value, true);
}
}
public bool TryGetValue(TKey key, out TValue value) {
if (key == null) {
throw new ArgumentNullException();
}
int slot = this.GetSlot(key);
List<TKey> keySlot = this.keys[slot];
if (keySlot != null) {
// Can't use keySlot.IndexOf() because it doesn't honour the comparer
for (int i = keySlot.Count - 1; i >= 0; i--) {
if (this.comparer.Equals(keySlot[i], key)) {
value = this.values[slot][i];
return true;
}
}
}
value = default(TValue);
return false;
}
public bool ContainsKey(TKey key) {
TValue dummy;
return (TryGetValue(key, out dummy));
}
public bool ContainsValue(TValue value) {
Enumerator e = new Enumerator(this);
while (e.MoveNext()) {
if (e.Current.Value.Equals(value)) {
return true;
}
}
return false;
}
public bool Remove(TKey key) {
int slot = this.GetSlot(key);
List<TKey> keySlot = this.keys[slot];
if (keySlot != null) {
// Can't use keySlot.IndexOf() because it doesn't honour the comparer
for (int i = keySlot.Count - 1; i >= 0; i--) {
if (this.comparer.Equals(keySlot[i], key)) {
keySlot.RemoveAt(i);
this.values[slot].RemoveAt(i);
this.count--;
return true;
}
}
}
return false;
}
public IEqualityComparer<TKey> Comparer {
get {
return this.comparer;
}
}
public int Count {
get {
return this.count;
}
}
public KeyCollection Keys {
get {
return new KeyCollection(this);
}
}
public ValueCollection Values {
get {
return new ValueCollection(this);
}
}
public bool IsReadOnly {
get {
return false;
}
}
public void Clear() {
this.keys = new List<TKey>[this.capacity];
this.values = new List<TValue>[this.capacity];
this.count = 0;
}
public Enumerator GetEnumerator() {
return new Enumerator(this);
}
ICollection<TKey> IDictionary<TKey, TValue>.Keys {
get {
return new KeyCollection(this);
}
}
ICollection<TValue> IDictionary<TKey, TValue>.Values {
get {
return new ValueCollection(this);
}
}
void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item) {
this.Add(item.Key, item.Value);
}
bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item) {
return this.ContainsKey(item.Key);
}
void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) {
throw new Exception("The method or operation is not implemented.");
}
bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item) {
return this.Remove(item.Key);
}
IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() {
return new Enumerator(this);
}
IEnumerator IEnumerable.GetEnumerator() {
return new Enumerator(this);
}
public bool IsFixedSize {
get {
return false;
}
}
object IDictionary.this[object key] {
get {
return this[(TKey)key];
}
set {
this[(TKey)key] = (TValue)value;
}
}
ICollection IDictionary.Keys {
get {
return Keys;
}
}
ICollection IDictionary.Values {
get {
return Values;
}
}
void IDictionary.Add(object key, object value) {
Add((TKey)key, (TValue)value);
}
bool IDictionary.Contains(object key) {
return ContainsKey((TKey)key);
}
IDictionaryEnumerator IDictionary.GetEnumerator() {
return new Enumerator(this);
}
void IDictionary.Remove(object key) {
Remove((TKey)key);
}
public bool IsSynchronized {
get {
return false;
}
}
public object SyncRoot {
get {
return this;
}
}
public void CopyTo(Array array, int index) {
throw new Exception("The method or operation is not implemented.");
}
}
}