C#

Harvey Saayman wrote:

1.5*N

public class SlimList<T> : IList<T>
{

	#region Constants

	private const int OVERHEAD = 31;
	private const int MAX_CAPACITY = 1 << 30;
	private const string NEGATIVE_CAPACITY = "Capacity cannot be less than 0.";

	#endregion


	#region Variables

	private T[][] items;
	private int count;
	private int capacity;
	private int capacityIndex;
	private int lastSize;

	#endregion


	#region Properties

	/// <summary>
	/// Gets or sets an item at the specified zero-based index.
	/// </summary>
	/// <param name="index">The zero-based index of the item to get or set.</param>
	/// <returns>The item at the specified zero-based index.</returns>
	public T this[int index]
	{
		get
		{

			// Validate index.
			ValidateIndex(index);


			// Index of first array.
			int firstIndex = (index == 0 ? 0 : (int)Math.Truncate(Math.Log(index, 2)));


			// Calculate index into the sub-array.
			int baseIndex = (firstIndex == 0 ? 0 : (1 << firstIndex));
			int offset = index - baseIndex;


			// Return item.
			return items[firstIndex][offset];

		}
		set
		{

			// Validate index.
			ValidateIndex(index);


			// Index of first array.
			int firstIndex = (index == 0 ? 0 : (int)Math.Truncate(Math.Log(index, 2)));


			// Calculate index into the sub-array.
			int baseIndex = (firstIndex == 0 ? 0 : (1 << firstIndex));
			int offset = index - baseIndex;


			// Assign item.
			items[firstIndex][offset] = value;

		}
	}


	/// <summary>
	/// The number of items currently in the list.
	/// </summary>
	public int Count
	{
		get
		{
			return this.count;
		}
	}


	/// <summary>
	/// The number of items the list can currently hold before increasing size.
	/// </summary>
	public int Capacity
	{
		get
		{
			return this.capacity;
		}
	}


	/// <summary>
	/// Always returns false.
	/// </summary>
	public bool IsReadOnly
	{
		get
		{
			return false;
		}
	}


	#endregion


	#region Constructors

	/// <summary>
	/// Creates an empty list.
	/// </summary>
	public SlimList()
	{
		this.Clear();
	}


	/// <summary>
	/// Creates a list with a capacity at least as great as the specified capacity.
	/// </summary>
	/// <param name="initialCapacity">The initial minimum capacity.</param>
	/// <remarks>
	/// As capacities increase exponentially, the specified capacity is used as an minimum.
	/// The actual initial capacity may actually be nearly twice as much as the specified
	/// initial capacity.
	/// </remarks>
	public SlimList(int initialCapacity)
	{

		// Initialize empty list.
		this.Clear();
		if (initialCapacity == 0)
		{
			return;
		}
		else if (initialCapacity < 0)
		{
			throw new InvalidOperationException(NEGATIVE_CAPACITY);
		}


		// Make capacity 2.
		this.items[0] = new T[2];
		this.capacity = 2;
		this.capacityIndex = 0;
		this.lastSize = 1;


		// Increase capacity until it is equal to or more than the requested capacity.
		while (this.capacity < initialCapacity)
		{
			this.capacityIndex++;
			this.lastSize <<= 1;
			this.capacity <<= 1;
			this.items[this.capacityIndex] = new T[this.lastSize];
		}
		
	}


	/// <summary>
	/// Creates a list from the elements in another collection.
	/// </summary>
	/// <param name="collection">
	/// The collection from which elements will be copied to the new list.
	/// </param>
	public SlimList(IEnumerable<T> collection)
	{

		// Initialize empty list.
		this.Clear();
		
		
		// Add each item in the collection to this list.
		foreach (T item in collection)
		{
			this.Add(item);
		}
		
	}

	#endregion

	
	#region Methods

	/// <summary>
	/// Get the index of an item.
	/// </summary>
	/// <param name="item">The item to get the index of.</param>
	/// <returns>The index, or -1 if it could not be found.</returns>
	public int IndexOf(T item)
	{
		EqualityComparer<T> comparer = EqualityComparer<T>.Default;
		for (int i = 0; i < count; i++)
		{
			if(comparer.Equals(item, this[i]))
			{
				return i;
			}
		}
		return -1;
	}


	/// <summary>
	/// Confirms the specified index is valid.
	/// </summary>
	/// <param name="index">The index to check.</param>
	/// <remarks>
	/// Will throw an exception if the index is out of the valid range.
	/// </remarks>
	private void ValidateIndex(int index)
	{
		if (index < 0 || index >= count)
		{
			throw new IndexOutOfRangeException();
		}
	}


	/// <summary>
	/// Inserts an item at the specified index.
	/// </summary>
	/// <param name="index">The index to insert the item at.</param>
	/// <param name="item">The item to insert.</param>
	public void Insert(int index, T item)
	{

		// Validate index.
		this.ValidateIndex(index);


		// Increase the list size.
		this.Add(this[this.count - 1]);


		// Make room for the new item.
		for (int i = this.count - 1; i > index; i--)
		{
			this[i] = this[i - 1];
		}


		// Assign the item to the specified index.
		this[index] = item;

	}


	/// <summary>
	/// Remove the item at the specified index from the list.
	/// </summary>
	/// <param name="index">
	/// The index of the item to remove.
	/// </param>
	public void RemoveAt(int index)
	{

		// Ensure index is valid.
		this.ValidateIndex(index);


		// Shift elements.
		for (int i = index; i + 1 < this.count; i++)
		{
			this[i] = this[i + 1];
		}


		// Decrement item count.
		this.count--;

	}

	
	/// <summary>
	/// Add the specified item to the end of the list.
	/// </summary>
	/// <param name="item">
	/// The item to add.
	/// </param>
	public void Add(T item)
	{

		// Increment count.
		count++;


		// Need to add more space to the list?
		if (count > capacity)
		{

			// Handle initial states.
			if (capacity == 0)
			{
				capacity = 1;
				this.lastSize = 1;
			}
			else if (capacity == 2)
			{
				this.lastSize = 1;
			}
			else if (capacity == MAX_CAPACITY)
			{
				throw new InvalidOperationException("The list is full.");
			}


			// Increase capacity.
			capacity <<= 1;
			this.capacityIndex++;
			this.lastSize <<= 1;


			// Create new nested array of items.
			this.items[this.capacityIndex] = new T[this.lastSize];

		}


		// Assign item to last index.
		this[count - 1] = item;

	}


	/// <summary>
	/// Empties the list.
	/// </summary>
	public void Clear()
	{

		// Reset array of arrays.
		items = new T[OVERHEAD][];


		// Reset all size-related values.
		this.count = 0;
		this.capacity = 0;
		this.capacityIndex = -1;
		this.lastSize = 0;

	}


	/// <summary>
	/// Checks if the specified item exists in this list.
	/// </summary>
	/// <param name="item">
	/// The item to search for.
	/// </param>
	/// <returns>
	/// True, if the item was found; otherwise, false.
	/// </returns>
	public bool Contains(T item)
	{
		return this.IndexOf(item) >= 0;
	}


	/// <summary>
	/// Copies the values in this list to an array.
	/// </summary>
	/// <param name="array">The array to copy the values to.</param>
	/// <param name="arrayIndex">
	/// The index into the destination array to start placing values.
	/// </param>
	public void CopyTo(T[] array, int arrayIndex)
	{
		for (int i = 0; i < this.count; i++)
		{
			array[i + arrayIndex] = this[i];
		}
	}

	
	/// <summary>
	/// Removes the specified item from this list.
	/// </summary>
	/// <param name="item">
	/// The item to remove.
	/// </param>
	/// <returns>
	/// True, if the item was found and removed; otherwise, false.
	/// </returns>
	public bool Remove(T item)
	{

		// Variables.
		int index = this.IndexOf(item);
		bool removed;


		// If found, remove item.
		if (index >= 0)
		{
			this.RemoveAt(index);
			removed = true;
		}
		else
		{
			removed = false;
		}


		// Return success or failure.
		return removed;

	}
	

	/// <summary>
	/// Returns an enumerator that can iterate over each item in the list.
	/// </summary>
	/// <returns>The enumerator.</returns>
	public IEnumerator<T> GetEnumerator()
	{
		for (int i = 0; i < this.count; i++)
		{
			yield return this[i];
		}
	}


	/// <summary>
	/// Returns an enumerator that can iterate over each item in the list.
	/// </summary>
	/// <returns>
	/// The enumerator.
	/// </returns>
	/// <remarks>
	/// This version just calls the generic version.
	/// </remarks>
	IEnumerator IEnumerable.GetEnumerator()
	{
		return this.GetEnumerator();
	}

	#endregion

}

<pre lang="C#">int x = 5;</pre>

aspdotnetdev wrote:

while (this.capacity < initialCapacity)
{
this.capacityIndex++;
this.lastSize <<= 1;
this.capacity <<= 1;
this.items[this.capacityIndex] = new T[this.lastSize];
}

Luc Pattyn wrote:

Why on earth would you create several arrays when you only need one?

aspdotnetdev wrote:

(though it could be argued that Log is not truly an O(1) operation, it could be implemented as such with an array to perform the lookup rather than perform the calculation, or in hardware, as the BSR instruction demonstrates, though both are moot points when you consider that you would have to use an n-bit number to perform the lookup anyway with either List or SlimList)

aspdotnetdev wrote:

as it is implemented, it has some performance issues, which are discussed at the bottom of the article in the forum

roguemat wrote:

I also cannot bring that application to the foreground(voiding the use of sendkeys).

private void WaitAll(WaitHandle[] waitHandles) {
  if (Thread.CurrentThread.ApartmentState == ApartmentState.STA) {
    // WaitAll for multiple handles on an STA thread is not supported.
    // ...so wait on each handle individually.
    foreach(WaitHandle myWaitHandle in waitHandles) {
      WaitHandle.WaitAny(new WaitHandle[]{myWaitHandle});
    }
  }
  else {
    WaitHandle.WaitAll(waitHandles);
  }
}

try {
    ...
} catch(Exception exc) {
    MessageBox.Show(exc.ToString());
}

CarlMartin10 wrote:

I just need some help every now and then