|
#nullable disable
//
// OrderedDictionary.cs
//
// Author:
// Eric Maupin <me@ermau.com>
//
// Copyright (c) 2009 Eric Maupin (http://www.ermau.com)
//
// 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;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using Microsoft.Maui;
using Microsoft.Maui.Controls;
using Microsoft.Maui.Controls.Internals;
namespace Cadenza.Collections
{
internal sealed class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IList<KeyValuePair<TKey, TValue>>
{
readonly Dictionary<TKey, TValue> _dict;
readonly List<TKey> _keyOrder;
readonly ICollection<KeyValuePair<TKey, TValue>> _kvpCollection;
readonly ReadOnlyCollection<TKey> _roKeys;
readonly ReadOnlyValueCollection _roValues;
public OrderedDictionary() : this(0)
{
}
public OrderedDictionary(int capacity) : this(capacity, EqualityComparer<TKey>.Default)
{
}
public OrderedDictionary(IEqualityComparer<TKey> equalityComparer) : this(0, equalityComparer)
{
}
public OrderedDictionary(int capacity, IEqualityComparer<TKey> equalityComparer)
{
_dict = new Dictionary<TKey, TValue>(capacity, equalityComparer);
_kvpCollection = _dict;
_keyOrder = new List<TKey>(capacity);
_roKeys = new ReadOnlyCollection<TKey>(_keyOrder);
_roValues = new ReadOnlyValueCollection(this);
}
public OrderedDictionary(ICollection<KeyValuePair<TKey, TValue>> dictionary) : this(dictionary, EqualityComparer<TKey>.Default)
{
}
public OrderedDictionary(ICollection<KeyValuePair<TKey, TValue>> dictionary, IEqualityComparer<TKey> equalityComparer) : this(dictionary != null ? dictionary.Count : 0, equalityComparer)
{
if (dictionary == null)
throw new ArgumentNullException(nameof(dictionary));
foreach (KeyValuePair<TKey, TValue> kvp in dictionary)
Add(kvp.Key, kvp.Value);
}
/// <summary>
/// Gets the equality comparer being used for <typeparamref name="TKey"/>.
/// </summary>
public IEqualityComparer<TKey> Comparer
{
get { return _dict.Comparer; }
}
/// <summary>
/// Gets the value at the specified index.
/// </summary>
/// <param name="index">The index to get the value at.</param>
/// <returns>The value at the specified index.</returns>
/// <exception cref="IndexOutOfRangeException">
/// <paramref name="index" /> is less than 0 or greater than
/// <see cref="Count" />.
/// </exception>
public TValue this[int index]
{
get { return _dict[_keyOrder[index]]; }
}
void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)
{
Add(item.Key, item.Value);
}
/// <summary>
/// Clears the dictionary.
/// </summary>
public void Clear()
{
_dict.Clear();
_keyOrder.Clear();
}
bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)
{
return _kvpCollection.Contains(item);
}
void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
if (array == null)
throw new ArgumentNullException(nameof(array));
if (Count > array.Length - arrayIndex)
throw new ArgumentException("Not enough space in array to copy");
if (arrayIndex < 0)
throw new ArgumentOutOfRangeException(nameof(arrayIndex));
for (var i = 0; i < _keyOrder.Count; ++i)
{
TKey key = _keyOrder[i];
array[arrayIndex++] = new KeyValuePair<TKey, TValue>(key, _dict[key]);
}
}
/// <summary>
/// Gets the number of items in the dictionary.
/// </summary>
public int Count
{
get { return _dict.Count; }
}
bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
{
get { return false; }
}
bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)
{
return _kvpCollection.Remove(item) && _keyOrder.Remove(item.Key);
}
/// <summary>
/// Adds the <paramref name="key" /> and <paramref name="value" /> to the dictionary.
/// </summary>
/// <param name="key">The key to associate with the <paramref name="value" />.</param>
/// <param name="value">The value to add.</param>
/// <exception cref="ArgumentNullException"><paramref name="key" /> is <c>null</c>.</exception>
/// <exception cref="ArgumentException"><paramref name="key" /> already exists in the dictionary.</exception>
public void Add(TKey key, TValue value)
{
_dict.Add(key, value);
_keyOrder.Add(key);
}
/// <summary>
/// Gets whether or not <paramref name="key" /> is in the dictionary.
/// </summary>
/// <param name="key">The key to look for.</param>
/// <returns><c>true</c> if the key was found, <c>false</c> if not.</returns>
/// <exception cref="ArgumentNullException">If <paramref name="key" /> is <c>null</c>.</exception>
public bool ContainsKey(TKey key)
{
return _dict.ContainsKey(key);
}
/// <summary>
/// Gets or sets the value associated with <paramref name="key" />.
/// </summary>
/// <param name="key">The key to get or set the value for.</param>
/// <returns>The value associated with the key.</returns>
/// <exception cref="KeyNotFoundException"><paramref name="key" /> was not found attempting to get.</exception>
public TValue this[TKey key]
{
get { return _dict[key]; }
set
{
if (!_dict.ContainsKey(key))
_keyOrder.Add(key);
_dict[key] = value;
}
}
/// <summary>
/// Gets a read only collection of keys in the dictionary.
/// </summary>
public ICollection<TKey> Keys
{
get { return _roKeys; }
}
/// <summary>
/// Removes the key and associated value from the dictionary if found.
/// </summary>
/// <param name="key">The key to remove.</param>
/// <returns><c>true</c> if the key was found, <c>false</c> if not.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key" /> is <c>null</c>.</exception>
public bool Remove(TKey key)
{
return _dict.Remove(key) && _keyOrder.Remove(key);
}
/// <summary>
/// Attempts to get the <paramref name="value" /> for the <paramref name="key" />.
/// </summary>
/// <param name="key">The key to search for.</param>
/// <param name="value">The value, if found.</param>
/// <returns><c>true</c> if the key was found, <c>false</c> otherwise.</returns>
/// <exception cref="ArgumentNullException">If <paramref name="key" /> is <c>null</c>.</exception>
public bool TryGetValue(TKey key, out TValue value)
{
return _dict.TryGetValue(key, out value);
}
/// <summary>
/// Gets a read only collection of values in the dictionary.
/// </summary>
public ICollection<TValue> Values
{
get { return _roValues; }
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
foreach (TKey key in _keyOrder)
yield return new KeyValuePair<TKey, TValue>(key, this[key]);
}
int IList<KeyValuePair<TKey, TValue>>.IndexOf(KeyValuePair<TKey, TValue> item)
{
return _keyOrder.IndexOf(item.Key);
}
void IList<KeyValuePair<TKey, TValue>>.Insert(int index, KeyValuePair<TKey, TValue> item)
{
Insert(index, item.Key, item.Value);
}
KeyValuePair<TKey, TValue> IList<KeyValuePair<TKey, TValue>>.this[int index]
{
get { return new KeyValuePair<TKey, TValue>(_keyOrder[index], this[index]); }
set
{
_keyOrder[index] = value.Key;
_dict[value.Key] = value.Value;
}
}
/// <summary>
/// Removes they key and associated value from the dictionary located at <paramref name="index" />.
/// </summary>
/// <param name="index">The index at which to remove an item.</param>
public void RemoveAt(int index)
{
TKey key = _keyOrder[index];
Remove(key);
}
/// <summary>
/// Gets whether or not <paramref name="value" /> is in the dictionary.
/// </summary>
/// <param name="value">The value to look for.</param>
/// <returns><c>true</c> if the value was found, <c>false</c> if not.</returns>
public bool ContainsValue(TValue value)
{
return _dict.ContainsValue(value);
}
/// <summary>
/// Gets the index of <paramref name="key" />.
/// </summary>
/// <param name="key">The key to find the index of.</param>
/// <returns>-1 if the key was not found, the index otherwise.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key" /> is <c>null</c>.</exception>
public int IndexOf(TKey key)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
return _keyOrder.IndexOf(key);
}
/// <summary>
/// Gets the index of <paramref name="key" /> starting with <paramref name="startIndex" />.
/// </summary>
/// <param name="key">The key to find the index of.</param>
/// <param name="startIndex">The index to start the search at.</param>
/// <returns>-1 if the key was not found, the index otherwise.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key" /> is <c>null</c>.</exception>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="startIndex" /> is not within the valid range of indexes.</exception>
public int IndexOf(TKey key, int startIndex)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
return _keyOrder.IndexOf(key, startIndex);
}
/// <summary>
/// Gets the index of <paramref name="key" /> between the range given by <paramref name="startIndex" /> and
/// <paramref name="count" />.
/// </summary>
/// <param name="key">The key to find the index of.</param>
/// <param name="startIndex">The index to start the search at.</param>
/// <param name="count">How many items to search, including the <paramref name="startIndex" />.</param>
/// <returns>-1 if the key was not found, the index otherwise.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key" /> is <c>null</c>.</exception>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="startIndex" /> is not within the valid range of indexes.</exception>
/// <exception cref="ArgumentOutOfRangeException">
/// <paramref name="startIndex" /> and <paramref name="count" /> are not a
/// valid range.
/// </exception>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="count" /> is less than 0.</exception>
public int IndexOf(TKey key, int startIndex, int count)
{
if (key == null)
throw new ArgumentNullException(nameof(key));
return _keyOrder.IndexOf(key, startIndex, count);
}
/// <summary>
/// Inserts the <paramref name="key" /> and <paramref name="value" /> at the specified index.
/// </summary>
/// <param name="index">The index to insert the key and value at.</param>
/// <param name="key">The key to assicate with the <paramref name="value" />.</param>
/// <param name="value">The value to insert.</param>
/// <exception cref="ArgumentNullException"><paramref name="key" /> is <c>null</c>.</exception>
/// <exception cref="ArgumentOutOfRangeException">
/// <paramref name="index" /> is less than 0 or greater than
/// <see cref="Count" />
/// </exception>
public void Insert(int index, TKey key, TValue value)
{
_keyOrder.Insert(index, key);
_dict.Add(key, value);
}
public void Move(int oldIndex, int newIndex)
{
TKey key = _keyOrder[oldIndex];
_keyOrder.RemoveAt(oldIndex);
_keyOrder.Insert(newIndex, key);
}
class ReadOnlyValueCollection : IList<TValue>
{
readonly OrderedDictionary<TKey, TValue> _odict;
public ReadOnlyValueCollection(OrderedDictionary<TKey, TValue> dict)
{
_odict = dict;
}
public void Add(TValue item)
{
throw new NotSupportedException();
}
public void Clear()
{
throw new NotSupportedException();
}
public bool Contains(TValue item)
{
return _odict.ContainsValue(item);
}
public void CopyTo(TValue[] array, int arrayIndex)
{
if (array == null)
throw new ArgumentNullException(nameof(array));
if (Count > array.Length - arrayIndex)
throw new ArgumentException("Not enough space in array to copy");
if (arrayIndex < 0 || arrayIndex > array.Length)
throw new ArgumentOutOfRangeException(nameof(arrayIndex));
for (var i = 0; i < _odict.Count; ++i)
array[arrayIndex++] = _odict[i];
}
public int Count
{
get { return _odict.Count; }
}
public bool IsReadOnly
{
get { return true; }
}
public bool Remove(TValue item)
{
throw new NotSupportedException();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public IEnumerator<TValue> GetEnumerator()
{
for (var i = 0; i < _odict._keyOrder.Count; ++i)
yield return _odict[i];
}
public int IndexOf(TValue item)
{
return _odict._dict.Values.IndexOf(item);
}
public void Insert(int index, TValue item)
{
throw new NotSupportedException();
}
public TValue this[int index]
{
get { return _odict[index]; }
set { throw new NotSupportedException(); }
}
public void RemoveAt(int index)
{
throw new NotSupportedException();
}
}
}
} |