ArrayDeque.cs

Go to the documentation of this file.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime.CompilerServices;
 
namespace IKVM.CoreLib.Collections
{
 
    internal class ArrayDeque<T> : IDeque<T>
    {
 
        const int MIN_INITIAL_CAPACITY = 8;
 
        static int CalculateSize(int numElements)
        {
            int initialCapacity = MIN_INITIAL_CAPACITY;
 
            // Find the best power of two to hold elements.
            // Tests "<=" because arrays aren't kept full.
            if (numElements >= initialCapacity)
            {
                initialCapacity = numElements;
                initialCapacity |= (initialCapacity >>> 1);
                initialCapacity |= (initialCapacity >>> 2);
                initialCapacity |= (initialCapacity >>> 4);
                initialCapacity |= (initialCapacity >>> 8);
                initialCapacity |= (initialCapacity >>> 16);
                initialCapacity++;
 
                if (initialCapacity < 0)   // Too many elements, must back off
                    initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
            }
 
            return initialCapacity;
        }
 
        T?[] _elements;
        int _head;
        int _tail;
 
        public ArrayDeque()
        {
            _elements = new T?[16];
        }
 
        public ArrayDeque(int initialCapacity)
        {
            EnsureCapacity(initialCapacity);
        }
 
        [MemberNotNull(nameof(_elements))]
        void EnsureCapacity(int capacity)
        {
            _elements = new T?[CalculateSize(capacity)];
        }
 
        void DoubleCapacity()
        {
            Debug.Assert(_head == _tail);
 
            int p = _head;
            int n = _elements.Length;
            int r = n - p; // number of elements to the right of p
            int newCapacity = n << 1;
            if (newCapacity < 0)
                throw new InvalidOperationException("Sorry, deque too big");
 
            var a = new T?[newCapacity];
            Array.Copy(_elements, p, a, 0, r);
            Array.Copy(_elements, 0, a, r, p);
            _elements = a;
 
            _head = 0;
            _tail = n;
        }
 
        public int Count => (_tail - _head) & (_elements.Length - 1);
 
        public bool IsEmpty => _head == _tail;
 
        public void InsertFirst(T item)
        {
            var m = _elements.Length - 1;
            var p = (_head - 1) & m;
 
            _elements[p] = item;
            _head = p;
 
            if (_head == _tail)
                DoubleCapacity();
        }
 
        public bool TryRemoveFirst([MaybeNullWhen(false)] out T result)
        {
            if (_head == _tail)
            {
                result = default;
                return false;
            }
 
            var m = _elements.Length - 1;
            var h = _head;
 
            result = _elements[h]!;
#if NET
            if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
#endif
                _elements[h] = default;
            _head = (h + 1) & m;
            return true;
        }
 
        public T RemoveFirst()
        {
            if (TryRemoveFirst(out var result) == false)
                throw new InvalidOperationException("The deque is empty.");
 
            return result;
        }
 
        public void InsertLast(T item)
        {
            var m = _elements.Length - 1;
            var p = (_tail + 1) & m;
 
            _elements[_tail] = item;
            _tail = p;
 
            if (_tail == _head)
                DoubleCapacity();
        }
 
        public bool TryRemoveLast([MaybeNullWhen(false)] out T result)
        {
            if (_head == _tail)
            {
                result = default;
                return false;
            }
 
            var m = _elements.Length - 1;
            var p = (_tail - 1) & m;
 
            result = _elements[p]!;
#if NET
            if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
#endif
                _elements[p] = default;
            _tail = p;
            return true;
        }
 
        public T RemoveLast()
        {
            if (TryRemoveLast(out var result) == false)
                throw new InvalidOperationException("The deque is empty.");
 
            return result;
        }
 
        public bool TryPeekFirst([MaybeNullWhen(false)] out T result)
        {
            if (_head == _tail)
            {
                result = default;
                return false;
            }
 
            result = _elements[_head]!;
            return true;
        }
 
        public T PeekFirst()
        {
            if (TryPeekFirst(out var result) == false)
                throw new InvalidOperationException("The deque is empty.");
 
            return result;
        }
 
        public bool TryPeekLast([MaybeNullWhen(false)] out T result)
        {
            if (_head == _tail)
            {
                result = default;
                return false;
            }
 
            var m = _elements.Length - 1;
            var t = (_tail - 1) & m;
            result = _elements[t]!;
            return true;
        }
 
        public T PeekLast()
        {
            if (TryPeekLast(out var result) == false)
                throw new InvalidOperationException("The deque is empty.");
 
            return result;
        }
 
        public bool RemoveFirst(T item)
        {
            int m = _elements.Length - 1;
            int p = _head;
 
            while (p != _tail)
            {
                if (EqualityComparer<T?>.Default.Equals(item, _elements[p]))
                {
                    DeleteAt(p);
                    return true;
                }
 
                p = (p + 1) & m;
            }
 
            return false;
        }
 
        public bool RemoveLast(T item)
        {
            int m = _elements.Length - 1;
            int p = _tail;
 
            while (p != _head)
            {
                p = (p - 1) & m;
 
                if (EqualityComparer<T?>.Default.Equals(item, _elements[p]))
                {
                    DeleteAt(p);
                    return true;
                }
            }
 
            return false;
        }
 
        bool DeleteAt(int i)
        {
            var elements = _elements;
            int m = elements.Length - 1;
            int h = _head;
            int t = _tail;
            int f = (i - h) & m;
            int b = (t - i) & m;
 
            // invariant: head <= i < tail mod circularity
            if (f >= ((t - h) & m))
                throw new InvalidOperationException("Concurrent operation.");
 
            if (f < b)
            {
                if (h <= i)
                {
                    Array.Copy(elements, h, elements, h + 1, f);
                }
                else
                {
                    Array.Copy(elements, 0, elements, 1, i);
                    elements[0] = elements[m];
                    Array.Copy(elements, h, elements, h + 1, m - h);
                }
 
                elements[h] = default;
                _head = (h + 1) & m;
                return false;
            }
            else
            {
                if (i < t)
                {
                    Array.Copy(elements, i + 1, elements, i, b);
                    _tail = t - 1;
                }
                else
                {
                    Array.Copy(elements, i + 1, elements, i, m - i);
                    elements[m] = elements[0];
                    Array.Copy(elements, 1, elements, 0, t);
                    _tail = (t - 1) & m;
                }
 
                return true;
            }
        }
 
        public bool Contains(T item)
        {
            int m = _elements.Length - 1;
            int i = _head;
 
            while (i != _tail)
            {
                if (EqualityComparer<T?>.Default.Equals(item, _elements[i]))
                    return true;
 
                i = (i + 1) & m;
            }
 
            return false;
        }
 
        public void Clear()
        {
            int h = _head;
            int t = _tail;
 
            if (h != t)
            {
                _head = _tail = 0;
 
#if NET
                // no need to zero out elements for unmanaged structs
                if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
                {
#endif
                    int i = h;
                    int m = _elements.Length - 1;
 
                    do
                    {
                        _elements[i] = default;
                        i = (i + 1) & m;
                    } while (i != t);
#if NET
                }
#endif
            }
        }
 
        public void CopyTo(T[] a)
        {
            if (_head < _tail)
            {
                Array.Copy(_elements, _head, a, 0, Count);
            }
            else if (_head > _tail)
            {
                int headPortionLen = _elements.Length - _head;
                Array.Copy(_elements, _head, a, 0, headPortionLen);
                Array.Copy(_elements, 0, a, headPortionLen, _tail);
            }
        }
 
        public void CopyTo(IList<T> list)
        {
            if (_head < _tail)
            {
                for (int i = _head; i < Count; i++)
                    list.Add(_elements[i]!);
            }
            else if (_head > _tail)
            {
                int headPortionLen = _elements.Length - _head;
 
                for (int i = _head; i < headPortionLen; i++)
                    list.Add(_elements[i]!);
 
                for (int i = headPortionLen; i < _tail; i++)
                    list.Add(_elements[i]!);
            }
        }
 
        public void CopyTo(ImmutableArray<T>.Builder builder)
        {
            if (_head < _tail)
            {
                builder.AddRange(_elements.AsSpan().Slice(_head, Count)!);
            }
            else if (_head > _tail)
            {
                int headPortionLen = _elements.Length - _head;
                builder.AddRange(_elements.AsSpan().Slice(_head, headPortionLen)!);
                builder.AddRange(_elements.AsSpan().Slice(headPortionLen, _tail)!);
            }
        }
 
        public T[] ToArray()
        {
            var a = new T[Count];
            CopyTo(a);
            return a;
        }
 
        public ImmutableArray<T> ToImmutableArray()
        {
            var a = ImmutableArray.CreateBuilder<T>(Count);
            CopyTo(a);
            return a.DrainToImmutable();
        }
 
        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            if (_head < _tail)
            {
                for (int i = _head; i < Count; i++)
                    yield return _elements[i]!;
            }
            else if (_head > _tail)
            {
                int headPortionLen = _elements.Length - _head;
 
                for (int i = _head; i < headPortionLen; i++)
                    yield return _elements[i]!;
 
                for (int i = headPortionLen; i < _tail; i++)
                    yield return _elements[i]!;
            }
        }
 
        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }
 
    }
 
}