//----------------------------------------------------------------------------- // // 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; } }