1 files changed, 174 insertions, 0 deletions
diff --git a/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Deque.cs b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Deque.cs
new file mode 100644
index 000000000..66496d68f
--- /dev/null
+++ b/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Utils/Deque.cs
@@ -0,0 +1,174 @@
+// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
+// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)
+
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+
+namespace Tango.Scripting.Editors.Utils
+{
+	/// <summary>
+	/// Double-ended queue.
+	/// </summary>
+	[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
+	[Serializable]
+	public sealed class Deque<T> : ICollection<T>
+	{
+		T[] arr = Empty<T>.Array;
+		int size, head, tail;
+		
+		/// <inheritdoc/>
+		public int Count {
+			get { return size; }
+		}
+		
+		/// <inheritdoc/>
+		public void Clear()
+		{
+			arr = Empty<T>.Array;
+			size = 0;
+			head = 0;
+			tail = 0;
+		}
+		
+		/// <summary>
+		/// Gets/Sets an element inside the deque.
+		/// </summary>
+		public T this[int index] {
+			get {
+				ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1);
+				return arr[(head + index) % arr.Length];
+			}
+			set {
+				ThrowUtil.CheckInRangeInclusive(index, "index", 0, size - 1);
+				arr[(head + index) % arr.Length] = value;
+			}
+		}
+		
+		/// <summary>
+		/// Adds an element to the end of the deque.
+		/// </summary>
+		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1702:CompoundWordsShouldBeCasedCorrectly", MessageId = "PushBack")]
+		public void PushBack(T item)
+		{
+			if (size == arr.Length)
+				SetCapacity(Math.Max(4, arr.Length * 2));
+			arr[tail++] = item;
+			if (tail == arr.Length) tail = 0;
+			size++;
+		}
+		
+		/// <summary>
+		/// Pops an element from the end of the deque.
+		/// </summary>
+		public T PopBack()
+		{
+			if (size == 0)
+				throw new InvalidOperationException();
+			if (tail == 0)
+				tail = arr.Length - 1;
+			else
+				tail--;
+			T val = arr[tail];
+			arr[tail] = default(T); // allow GC to collect the element
+			size--;
+			return val;
+		}
+		
+		/// <summary>
+		/// Adds an element to the front of the deque.
+		/// </summary>
+		public void PushFront(T item)
+		{
+			if (size == arr.Length)
+				SetCapacity(Math.Max(4, arr.Length * 2));
+			if (head == 0)
+				head = arr.Length - 1;
+			else
+				head--;
+			arr[head] = item;
+			size++;
+		}
+		
+		/// <summary>
+		/// Pops an element from the end of the deque.
+		/// </summary>
+		public T PopFront()
+		{
+			if (size == 0)
+				throw new InvalidOperationException();
+			T val = arr[head];
+			arr[head] = default(T); // allow GC to collect the element
+			head++;
+			if (head == arr.Length) head = 0;
+			size--;
+			return val;
+		}
+		
+		void SetCapacity(int capacity)
+		{
+			T[] newArr = new T[capacity];
+			CopyTo(newArr, 0);
+			head = 0;
+			tail = (size == capacity) ? 0 : size;
+			arr = newArr;
+		}
+		
+		/// <inheritdoc/>
+		public IEnumerator<T> GetEnumerator()
+		{
+			if (head < tail) {
+				for (int i = head; i < tail; i++)
+					yield return arr[i];
+			} else {
+				for (int i = head; i < arr.Length; i++)
+					yield return arr[i];
+				for (int i = 0; i < tail; i++)
+					yield return arr[i];
+			}
+		}
+		
+		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
+		{
+			return this.GetEnumerator();
+		}
+		
+		bool ICollection<T>.IsReadOnly {
+			get { return false; }
+		}
+		
+		void ICollection<T>.Add(T item)
+		{
+			PushBack(item);
+		}
+		
+		/// <inheritdoc/>
+		public bool Contains(T item)
+		{
+			EqualityComparer<T> comparer = EqualityComparer<T>.Default;
+			foreach (T element in this)
+				if (comparer.Equals(item, element))
+					return true;
+			return false;
+		}
+		
+		/// <inheritdoc/>
+		public void CopyTo(T[] array, int arrayIndex)
+		{
+			if (array == null)
+				throw new ArgumentNullException("array");
+			if (head < tail) {
+				Array.Copy(arr, head, array, arrayIndex, tail - head);
+			} else {
+				int num1 = arr.Length - head;
+				Array.Copy(arr, head, array, arrayIndex, num1);
+				Array.Copy(arr, 0, array, arrayIndex + num1, tail);
+			}
+		}
+		
+		bool ICollection<T>.Remove(T item)
+		{
+			throw new NotSupportedException();
+		}
+	}
+}