// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
/*============================================================
**
** Class: SortedList
**
** [....]
**
** Purpose: A sorted dictionary.
**
**
===========================================================*/
namespace System.Collections {
using System;
using System.Security.Permissions;
using System.Diagnostics;
using System.Globalization;
using System.Diagnostics.Contracts;
// The SortedList class implements a sorted list of keys and values. Entries in
// a sorted list are sorted by their keys and are accessible both by key and by
// index. The keys of a sorted list can be ordered either according to a
// specific IComparer implementation given when the sorted list is
// instantiated, or according to the IComparable implementation provided
// by the keys themselves. In either case, a sorted list does not allow entries
// with duplicate keys.
//
// A sorted list internally maintains two arrays that store the keys and
// values of the entries. The capacity of a sorted list is the allocated
// length of these internal arrays. As elements are added to a sorted list, the
// capacity of the sorted list is automatically increased as required by
// reallocating the internal arrays. The capacity is never automatically
// decreased, but users can call either TrimToSize or
// Capacity explicitly.
//
// The GetKeyList and GetValueList methods of a sorted list
// provides access to the keys and values of the sorted list in the form of
// List implementations. The List objects returned by these
// methods are aliases for the underlying sorted list, so modifications
// made to those lists are directly reflected in the sorted list, and vice
// versa.
//
// The SortedList class provides a convenient way to create a sorted
// copy of another dictionary, such as a Hashtable. For example:
//
// Hashtable h = new Hashtable();
// h.Add(...);
// h.Add(...);
// ...
// SortedList s = new SortedList(h);
//
// The last line above creates a sorted list that contains a copy of the keys
// and values stored in the hashtable. In this particular example, the keys
// will be ordered according to the IComparable interface, which they
// all must implement. To impose a different ordering, SortedList also
// has a constructor that allows a specific IComparer implementation to
// be specified.
//
[DebuggerTypeProxy(typeof(System.Collections.SortedList.SortedListDebugView))]
[DebuggerDisplay("Count = {Count}")]
[System.Runtime.InteropServices.ComVisible(true)]
#if FEATURE_CORECLR
[Obsolete("Non-generic collections have been deprecated. Please use collections in System.Collections.Generic.")]
#endif
[Serializable]
public class SortedList : IDictionary, ICloneable
{
private Object[] keys;
private Object[] values;
private int _size;
private int version;
private IComparer comparer;
private KeyList keyList;
private ValueList valueList;
[NonSerialized]
private Object _syncRoot;
private const int _defaultCapacity = 16;
private static Object[] emptyArray = new Object[0];
// Constructs a new sorted list. The sorted list is initially empty and has
// a capacity of zero. Upon adding the first element to the sorted list the
// capacity is increased to 16, and then increased in multiples of two as
// required. The elements of the sorted list are ordered according to the
// IComparable interface, which must be implemented by the keys of
// all entries added to the sorted list.
public SortedList() {
Init();
}
private void Init()
{
keys = emptyArray;
values = emptyArray;
_size = 0;
comparer = new Comparer(CultureInfo.CurrentCulture);
}
// Constructs a new sorted list. The sorted list is initially empty and has
// a capacity of zero. Upon adding the first element to the sorted list the
// capacity is increased to 16, and then increased in multiples of two as
// required. The elements of the sorted list are ordered according to the
// IComparable interface, which must be implemented by the keys of
// all entries added to the sorted list.
//
public SortedList(int initialCapacity) {
if (initialCapacity < 0)
throw new ArgumentOutOfRangeException("initialCapacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
Contract.EndContractBlock();
keys = new Object[initialCapacity];
values = new Object[initialCapacity];
comparer = new Comparer(CultureInfo.CurrentCulture);
}
// Constructs a new sorted list with a given IComparer
// implementation. The sorted list is initially empty and has a capacity of
// zero. Upon adding the first element to the sorted list the capacity is
// increased to 16, and then increased in multiples of two as required. The
// elements of the sorted list are ordered according to the given
// IComparer implementation. If comparer is null, the
// elements are compared to each other using the IComparable
// interface, which in that case must be implemented by the keys of all
// entries added to the sorted list.
//
public SortedList(IComparer comparer)
: this() {
if (comparer != null) this.comparer = comparer;
}
// Constructs a new sorted list with a given IComparer
// implementation and a given initial capacity. The sorted list is
// initially empty, but will have room for the given number of elements
// before any reallocations are required. The elements of the sorted list
// are ordered according to the given IComparer implementation. If
// comparer is null, the elements are compared to each other using
// the IComparable interface, which in that case must be implemented
// by the keys of all entries added to the sorted list.
//
public SortedList(IComparer comparer, int capacity)
: this(comparer) {
Capacity = capacity;
}
// Constructs a new sorted list containing a copy of the entries in the
// given dictionary. The elements of the sorted list are ordered according
// to the IComparable interface, which must be implemented by the
// keys of all entries in the the given dictionary as well as keys
// subsequently added to the sorted list.
//
public SortedList(IDictionary d)
: this(d, null) {
}
// Constructs a new sorted list containing a copy of the entries in the
// given dictionary. The elements of the sorted list are ordered according
// to the given IComparer implementation. If comparer is
// null, the elements are compared to each other using the
// IComparable interface, which in that case must be implemented
// by the keys of all entries in the the given dictionary as well as keys
// subsequently added to the sorted list.
//
public SortedList(IDictionary d, IComparer comparer)
: this(comparer, (d != null ? d.Count : 0)) {
if (d==null)
throw new ArgumentNullException("d", Environment.GetResourceString("ArgumentNull_Dictionary"));
Contract.EndContractBlock();
d.Keys.CopyTo(keys, 0);
d.Values.CopyTo(values, 0);
Array.Sort(keys, values, comparer);
_size = d.Count;
}
// Adds an entry with the given key and value to this sorted list. An
// ArgumentException is thrown if the key is already present in the sorted list.
//
public virtual void Add(Object key, Object value) {
if (key == null) throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
Contract.EndContractBlock();
int i = Array.BinarySearch(keys, 0, _size, key, comparer);
if (i >= 0)
throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", GetKey(i), key));
Insert(~i, key, value);
}
// Returns the capacity of this sorted list. The capacity of a sorted list
// represents the allocated length of the internal arrays used to store the
// keys and values of the list, and thus also indicates the maximum number
// of entries the list can contain before a reallocation of the internal
// arrays is required.
//
public virtual int Capacity {
get {
return keys.Length;
}
set {
if (value < Count) {
throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
}
Contract.EndContractBlock();
if (value != keys.Length) {
if (value > 0) {
Object[] newKeys = new Object[value];
Object[] newValues = new Object[value];
if (_size > 0) {
Array.Copy(keys, 0, newKeys, 0, _size);
Array.Copy(values, 0, newValues, 0, _size);
}
keys = newKeys;
values = newValues;
}
else {
// size can only be zero here.
Contract.Assert( _size == 0, "Size is not zero");
keys = emptyArray;
values = emptyArray;
}
}
}
}
// Returns the number of entries in this sorted list.
//
public virtual int Count {
get {
return _size;
}
}
// Returns a collection representing the keys of this sorted list. This
// method returns the same object as GetKeyList, but typed as an
// ICollection instead of an IList.
//
public virtual ICollection Keys {
get {
return GetKeyList();
}
}
// Returns a collection representing the values of this sorted list. This
// method returns the same object as GetValueList, but typed as an
// ICollection instead of an IList.
//
public virtual ICollection Values {
get {
return GetValueList();
}
}
// Is this SortedList read-only?
public virtual bool IsReadOnly {
get { return false; }
}
public virtual bool IsFixedSize {
get { return false; }
}
// Is this SortedList synchronized (thread-safe)?
public virtual bool IsSynchronized {
get { return false; }
}
// Synchronization root for this object.
public virtual Object SyncRoot {
get {
if( _syncRoot == null) {
System.Threading.Interlocked.CompareExchange