//-----------------------------------------------------------------------------
//
// Copyright (c) 2010 Nesterovsky Bros. All rights reserved.
//
//
// A map based on immutable AVL tree.
//
//-----------------------------------------------------------------------------
namespace NesterovskyBros.Collections.AVL
{
using System;
using System.Collections.Generic;
using System.Runtime.Serialization;
using System.Security.Permissions;
///
/// A generic collection of key/value pairs.
///
/// The type of keys in the map.
/// The type of values in the map.
[Serializable]
public class Map:
IDictionary,
IList>,
ICloneable
{
///
/// A key collection.
///
public struct KeyCollection: ICollection
{
///
/// Creates a key collection.
///
/// A tree navigator.
/// A key comparer.
public KeyCollection(
TreeNavigator> navigator,
IComparer comparer)
{
this.navigator = navigator.Root.Navigator();
this.comparer = comparer;
}
#region ICollection Members
///
/// Gets the number of elements contained in the collection.
///
public int Count
{
get { return navigator.Count; }
}
///
/// Indicates that collection is read only.
///
public bool IsReadOnly
{
get { return true; }
}
///
/// Throws an exception. Operation is not supported.
///
/// An key value.
public void Add(K key)
{
throw new NotSupportedException();
}
///
/// Throws an exception. Operation is not supported.
///
public void Clear()
{
throw new NotSupportedException();
}
///
/// Determines whether the collection contains a specific key.
///
/// An object to locate.
///
/// True if item is found in the collection, and false otherwise.
///
public bool Contains(K key)
{
return navigator.Root.Find(key, comparer) != null;
}
///
/// Copies the elements of the collection to an array, starting at a
/// particular array index.
///
///
/// An array that is the destination of the elements copied
/// from the collection.
///
///
/// An index in array at which copying begins.
///
public void CopyTo(K[] array, int index)
{
if (array == null)
{
throw new ArgumentException("array");
}
if (index < 0)
{
throw new ArgumentException("index");
}
if ((array.Length - index) < this.navigator.Count)
{
throw new ArgumentException("array");
}
if (!this.navigator.IsNull)
{
var navigator = this.navigator.Root.Navigator();
navigator.MoveToLeftmost();
do
{
array[index++] = navigator.Current.Value.Key;
}
while(navigator.MoveToSuccessor());
}
}
///
/// Throws an exception. Operation is not supported.
///
/// An key value.
public bool Remove(K key)
{
throw new NotSupportedException();
}
#endregion
#region IEnumerable Members
///
/// Returns an enumerator that iterates through the collection.
///
/// A key enumerator.
public IEnumerator GetEnumerator()
{
if (!this.navigator.IsNull)
{
var navigator = this.navigator.Root.Navigator();
navigator.MoveToLeftmost();
do
{
yield return navigator.Current.Value.Key;
}
while(navigator.MoveToSuccessor());
}
}
#endregion
#region IEnumerable Members
///
/// Returns an enumerator that iterates through the collection.
///
/// A key enumerator.
System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
///
/// A tree navigator.
///
public readonly TreeNavigator> navigator;
///
/// A key comparer.
///
public readonly IComparer comparer;
}
///
/// A value collection.
///
public struct ValueCollection: ICollection
{
///
/// Creates a value collection.
///
/// A tree navigator.
public ValueCollection(
TreeNavigator> navigator)
{
this.navigator = navigator.Root.Navigator();
}
#region ICollection Members
///
/// Gets the number of elements contained in the collection.
///
public int Count
{
get { return navigator.Count; }
}
///
/// Indicates that collection is read only.
///
public bool IsReadOnly
{
get { return true; }
}
///
/// Throws an exception. Operation is not supported.
///
/// A value.
public void Add(V value)
{
throw new NotSupportedException();
}
///
/// Throws an exception. Operation is not supported.
///
public void Clear()
{
throw new NotSupportedException();
}
///
/// Determines whether the collection contains a specific key.
///
/// A value.
///
/// True if item is found in the collection, and false otherwise.
///
public bool Contains(V value)
{
IEqualityComparer comparer = EqualityComparer.Default;
if (this.navigator.IsNull)
{
return false;
}
var navigator = this.navigator.Root.Navigator();
navigator.MoveToLeftmost();
do
{
if (comparer.Equals(navigator.Current.Value.Value, value))
{
return true;
}
}
while(navigator.MoveToSuccessor());
return false;
}
///
/// Copies the elements of the collection to an array, starting at a
/// particular array index.
///
///
/// An array that is the destination of the elements copied
/// from the collection.
///
///
/// An index in array at which copying begins.
///
public void CopyTo(V[] array, int index)
{
if (array == null)
{
throw new ArgumentException("array");
}
if (index < 0)
{
throw new ArgumentException("index");
}
if ((array.Length - index) < this.navigator.Count)
{
throw new ArgumentException("array");
}
if (!this.navigator.IsNull)
{
var navigator = this.navigator.Root.Navigator();
navigator.MoveToLeftmost();
do
{
array[index++] = navigator.Current.Value.Value;
}
while(navigator.MoveToSuccessor());
}
}
///
/// Throws an exception. Operation is not supported.
///
/// A value.
public bool Remove(V value)
{
throw new NotSupportedException();
}
#endregion
#region IEnumerable Members
///
/// Returns an enumerator that iterates through the collection.
///
/// A value enumerator.
public IEnumerator GetEnumerator()
{
if (!this.navigator.IsNull)
{
var navigator = this.navigator.Root.Navigator();
navigator.MoveToLeftmost();
do
{
yield return navigator.Current.Value.Value;
}
while(navigator.MoveToSuccessor());
}
}
#endregion
#region IEnumerable Members
///
/// Returns an enumerator that iterates through the collection.
///
/// A key enumerator.
System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
///
/// A tree navigator.
///
public readonly TreeNavigator> navigator;
}
///
/// Creates a map instance.
///
///
/// A default comparer will be used to order keys.
///
public Map():
this(Comparer.Default)
{
}
///
/// Creates a copy of map.
/// Note that this operation is cheap.
///
/// A map to copy.
public Map(Map that)
{
comparer = that.comparer;
navigator = that.navigator.Root.Navigator();
}
///
/// Creates a map instance.
///
///
/// A comparer instance.
/// If null value is specified then default comparer will be used.
///
public Map(IComparer comparer)
{
this.comparer = comparer ?? Comparer.Default;
this.navigator = new TreeNavigator>();
}
///
/// Creates a map instance.
/// A default comparer will be used to order keys.
///
///
/// A kay/value collection.
///
public Map(ICollection> collection):
this(collection, Comparer.Default, false)
{
}
///
/// Creates a map instance.
///
///
/// A kay/value collection.
///
///
/// A comparer to order keys.
/// If null is specified then a default comparer is used.
///
public Map(
ICollection> collection,
IComparer comparer):
this(collection, comparer, false)
{
}
///
/// Creates a map instance.
/// A default comparer will be used to order keys.
///
///
/// An kay/value collection.
///
///
/// If ordered is true then collection is assumed to be ordered
/// according to a default comparer (this speeds construction up),
/// and false when ordering of collection elements is not known.
///
public Map(ICollection> collection, bool ordered):
this(collection, Comparer.Default, ordered)
{
}
///
/// Creates a map instance.
///
///
/// A kay/value collection.
///
///
/// A comparer to order keys.
/// If null is specified then a default comparer is used.
///
///
/// If ordered is true then collection is assumed to be ordered
/// according to a default comparer (this speeds construction up),
/// and false when ordering of collection elements is not known.
///
public Map(
ICollection> collection,
IComparer comparer,
bool ordered)
{
this.comparer = comparer ?? Comparer.Default;
if (ordered)
{
navigator =
TreeNavigator>.Create(collection).Navigator();
}
else
{
navigator = new TreeNavigator>();
foreach(KeyValuePair value in collection)
{
navigator.Insert(value, comparer);
}
}
}
///
/// Creates a clone of this map.
/// Note that this operation is cheap.
///
/// A clone of this map.
public Map Clone()
{
return new Map(this);
}
#region ICloneable Members
///
/// Creates a clone of this map.
/// Note that this operation is cheap.
///
/// A clone of this map.
object ICloneable.Clone()
{
return Clone();
}
#endregion
///
/// Gets a comparer instance.
///
public IComparer Comparer
{
get { return comparer; }
}
///
/// Gets a comparer instance.
///
public TreeNavigator> Navigator
{
get { return navigator.Clone(); }
}
#region IDictionary Members
///
/// Gets an collection containing the keys of map.
///
public KeyCollection Keys
{
get { return new KeyCollection(navigator, comparer); }
}
///
/// Gets an collection containing the keys of map.
///
ICollection IDictionary.Keys
{
get { return Keys; }
}
///
/// Gets an collection containing the values of map.
///
public ValueCollection Values
{
get { return new ValueCollection(navigator); }
}
///
/// Gets an collection containing the values of map.
///
ICollection IDictionary.Values
{
get { return Values; }
}
///
/// Gets or sets the element with the specified key.
///
/// A key of the element to get or set.
/// A value for the key
///
/// There is no value in the map for a specified key.
///
public V this[K key]
{
get
{
var node = navigator.Root.Find(key, comparer);
if (node == null)
{
throw new KeyNotFoundException();
}
return navigator.Current.Value.Value;
}
set
{
int c = navigator.Find(key, comparer);
if (c == 0)
{
navigator.Replace(new KeyValuePair(key, value));
}
else
{
navigator.Insert(new KeyValuePair(key, value), c > 0);
}
}
}
///
/// Adds an element with the provided key and value to the map.
///
/// A key of an element to add.
/// A value of an element to add.
///
/// An element with the same key already exists in the map.
///
public void Add(K key, V value)
{
Add(new KeyValuePair(key, value));
}
///
/// Determines whether the map contains an element with
/// the specified key.
///
/// A key to locate.
///
/// true if the map contains an element with the key, and
/// otherwise, false.
///
public bool ContainsKey(K key)
{
return navigator.Root.Find(key, comparer) != null;
}
///
/// Removes the element with the specified key from the map.
///
/// A key of the element to remove.
///
/// true if the element is successfully removed, and otherwise, false.
/// This method also returns false if key was not found in the map.
///
public bool Remove(K key)
{
if (navigator.Find(key, comparer) != 0)
{
return false;
}
navigator.Remove();
return true;
}
///
/// Gets the value associated with the specified key.
///
/// A key whose value to get.
///
/// When this method returns, the value associated with the specified key,
/// if the key is found, otherwise, the default value for the type of the
/// value parameter. This parameter is passed uninitialized.
///
///
/// true if the map contains an element with the specified key, and
/// false otherwise.
///
public bool TryGetValue(K key, out V value)
{
bool succeeds;
var node = navigator.Root.Find(key, comparer);
if (node != null)
{
value = node.Value.Value;
succeeds = true;
}
else
{
value = default(V);
succeeds = false;
}
return succeeds;
}
#endregion
#region ICollection> Members
///
/// Gets the number of elements contained in the collection.
///
public int Count
{
get { return navigator.Count; }
}
///
/// Indicates that collection is read only.
///
public bool IsReadOnly
{
get { return false; }
}
///
/// Adds an element with the provided key and value to the map.
///
/// A value to add.
///
/// An element with the same key already exists in the map.
///
public void Add(KeyValuePair value)
{
int c = navigator.Find(value.Key, comparer);
if (c == 0)
{
throw new ArgumentException("value");
}
navigator.Insert(value, c >= 0);
}
///
/// Clears the map.
///
public void Clear()
{
navigator.Clear();
}
///
/// Determines whether the collection contains a specific key.
///
/// An element to locate.
///
/// True if item is found in the collection, and false otherwise.
///
public bool Contains(KeyValuePair value)
{
return ContainsKey(value.Key);
}
///
/// Copies the elements of the collection to an array, starting at a
/// particular array index.
///
///
/// An array that is the destination of the elements copied
/// from the collection.
///
///
/// An index in array at which copying begins.
///
public void CopyTo(KeyValuePair[] array, int index)
{
navigator.CopyTo(array, index);
}
///
/// Removes the element with the specified key from the map.
///
/// A value to remove.
///
/// true if the element is successfully removed, and otherwise, false.
/// This method also returns false if key was not found in the map.
///
public bool Remove(KeyValuePair value)
{
return Remove(value.Key);
}
///
/// Gets an element enumerator.
///
/// A key/value pair enumerator.
public IEnumerator> GetEnumerator()
{
return navigator.GetEnumerator();
}
///
/// Gets an element enumerator.
///
/// A key/value pair enumerator.
System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
#region IList> Members
///
/// Gets or sets the element at the specified index.
///
///
/// A zero-based index of the element to get or set.
///
/// An element at the specified index.
public KeyValuePair this[int index]
{
get
{
if (!navigator.MoveToIndex(index))
{
throw new ArgumentOutOfRangeException("index");
}
return navigator.Current.Value;
}
set
{
// Do not account index but key only.
this[value.Key] = value.Value;
}
}
///
/// Determines the index of a specific item in the list.
///
/// An item to locate.
///
/// An index of item if found in the list, or -1 otherwise.
///
public int IndexOf(KeyValuePair item)
{
if (navigator.Find(item.Key, comparer) == 0)
{
return navigator.Index;
}
return -1;
}
///
/// Inserts an item to the list at the specified index.
/// Note that index is not accounted but key only.
///
///
/// A zero-based index at which item should be inserted.
///
/// An item to insert.
public void Insert(int index, KeyValuePair item)
{
Add(item);
}
///
/// Removes a list item at the specified index.
///
///
/// An index of item to remove.
///
public void RemoveAt(int index)
{
navigator.RemoveAt(index);
}
#endregion
///
/// A tree navigator.
///
private readonly TreeNavigator> navigator;
///
/// A key comparer.
///
private readonly IComparer comparer;
}
}