public const string __doc__ = "High performance data structures\n";

[PythonType]

[DontMapIEnumerableToContains, DebuggerDisplay("deque, {__len__()} items"), DebuggerTypeProxy(typeof(CollectionDebugProxy))]

public class deque : IEnumerable, ICodeFormattable, IStructuralEquatable, ICollection, IReversible, IWeakReferenceable {

private object[] _data;

private readonly object _lockObj = new object();

private int _head, _tail;

private int _itemCnt, _maxLen, _version;

public deque() : this(-1) { }

private deque(int maxlen) {

// internal private constructor accepts maxlen < 0

_maxLen = maxlen;

_data = _maxLen < 0 ? new object[8] : new object[Math.Min(_maxLen, 8)];

}

public static object __new__(CodeContext/*!*/ context, PythonType cls, [ParamDictionary]IDictionary<object, object> dict, params object[] args) {

if (cls == DynamicHelpers.GetPythonTypeFromType(typeof(deque))) return new deque();

return cls.CreateInstance(context);

}

public void __init__() {

_maxLen = -1;

clear();

}

public void __init__([ParamDictionary]IDictionary<object, object> dict) {

_maxLen = VerifyMaxLen(dict);

clear();

}

public void __init__(object iterable) {

_maxLen = -1;

clear();

extend(iterable);

}

public void __init__(object iterable, object maxlen) {

_maxLen = VerifyMaxLenValue(maxlen);

clear();

extend(iterable);

}

public void __init__(object iterable, [ParamDictionary]IDictionary<object, object> dict) {

if (VerifyMaxLen(dict) < 0) {

__init__(iterable);

} else {

__init__(iterable, VerifyMaxLen(dict));

}

}

private static int VerifyMaxLen(IDictionary<object, object> dict) {

if (dict.Count != 1) {

throw PythonOps.TypeError("deque() takes at most 1 keyword argument ({0} given)", dict.Count);

}

object value;

if (!dict.TryGetValue("maxlen", out value)) {

IEnumerator<object> e = dict.Keys.GetEnumerator();

if (e.MoveNext()) {

throw PythonOps.TypeError("deque(): '{0}' is an invalid keyword argument", e.Current);

}

}

return VerifyMaxLenValue(value);

}

private static int VerifyMaxLenValue(object value) {

if (value is null) {

return -1;

}

int res = value switch {

int i32 => i32,

BigInteger bi => (int)bi,

Extensible<BigInteger> ebi => (int)ebi.Value,

_ => throw PythonOps.TypeError("an integer is required")

};

if (res < 0) throw PythonOps.ValueError("maxlen must be non-negative");

return res;

}

#region core deque APIs

public void append(object x) {

lock (_lockObj) {

_version++;

// overwrite head if queue is at max length

if (_itemCnt == _maxLen) {

if (_maxLen == 0) {

return;

}

_data[_tail++] = x;

if (_tail == _data.Length) {

_tail = 0;

}

_head = _tail;

return;

}

if (_itemCnt == _data.Length) {

GrowArray();

}

_itemCnt++;

_data[_tail++] = x;

if (_tail == _data.Length) {

_tail = 0;

}

}

}

public void appendleft(object x) {

lock (_lockObj) {

_version++;

// overwrite tail if queue is full

if (_itemCnt == _maxLen) {

if (_maxLen == 0) {

return;

}

_head--;

if (_head < 0) {

_head = _data.Length - 1;

}

_tail = _head;

_data[_head] = x;

return;

}

if (_itemCnt == _data.Length) {

GrowArray();

}

_itemCnt++;

--_head;

if (_head < 0) {

_head = _data.Length - 1;

}

_data[_head] = x;

}

}

public void clear() {

lock (_lockObj) {

_version++;

_head = _tail = 0;

_itemCnt = 0;

if (_maxLen < 0) _data = new object[8];

else _data = new object[Math.Min(_maxLen, 8)];

}

}

public object copy(CodeContext context)

=> __copy__(context);

public void extend(object iterable) {

// d.extend(d)

if (ReferenceEquals(iterable, this)) {

WalkDeque(idx => {

append(_data[idx]);

return true;

});

return;

}

IEnumerator e = PythonOps.GetEnumerator(iterable);

while (e.MoveNext()) {

append(e.Current);

}

}

public void extendleft(object iterable) {

// d.extendleft(d)

if (ReferenceEquals(iterable, this)) {

WalkDeque(idx => {

appendleft(_data[idx]);

return true;

});

return;

}

IEnumerator e = PythonOps.GetEnumerator(iterable);

while (e.MoveNext()) {

appendleft(e.Current);

}

}

public int index(CodeContext context, object value) {

lock (_lockObj) {

return index(context, value, 0, _itemCnt);

}

}

public int index(CodeContext context, object value, int start) {

lock (_lockObj) {

return index(context, value, start, _itemCnt);

}

}

public int index(CodeContext context, object value, int start, int stop) {

lock (_lockObj) {

if (start < 0) {

start += _itemCnt;

if (start < 0) start = 0;

}

if (stop < 0) {

stop += _itemCnt;

if (stop < 0) stop = 0;

}

int found = -1;

int cnt = 0;

var startVersion = _version;

try {

WalkDeque((int index) => {

if (cnt >= start) {

if (cnt >= stop) return false;

if (PythonOps.IsOrEqualsRetBool(_data[index], value)) {

found = index;

return false;

}

}

cnt += 1;

return true;

});

} catch (IndexOutOfRangeException) {

Debug.Assert(startVersion != _version);

}

if (startVersion != _version) {

throw PythonOps.RuntimeError("deque mutated during iteration");

}

if (found == -1) {

throw PythonOps.ValueError($"{value} not in deque");

}

return cnt;

}

}

public int index(CodeContext context, object item, object start)

=> index(context, item, Converter.ConvertToIndex(start));

public int index(CodeContext context, object item, object start, object stop)

=> index(context, item, Converter.ConvertToIndex(start), Converter.ConvertToIndex(stop));

public void insert(CodeContext context, int index, object @object) {

lock (_lockObj) {

if (_itemCnt == _maxLen) throw PythonOps.IndexError("deque already at its maximum size");

if (index >= _itemCnt) {

append(@object);

} else if (index <= -_itemCnt || index == 0) {

appendleft(@object);

} else {

rotate(context, -index);

if (index < 0) {

append(@object);

} else {

appendleft(@object);

}

rotate(context, index);

}

}

}

public object pop() {

lock (_lockObj) {

if (_itemCnt == 0) {

throw PythonOps.IndexError("pop from an empty deque");

}

_version++;

if (_tail != 0) {

_tail--;

} else {

_tail = _data.Length - 1;

}

_itemCnt--;

object res = _data[_tail];

_data[_tail] = null;

return res;

}

}

public object popleft() {

lock (_lockObj) {

if (_itemCnt == 0) {

throw PythonOps.IndexError("pop from an empty deque");

}

_version++;

object res = _data[_head];

_data[_head] = null;

if (_head != _data.Length - 1) {

_head++;

} else {

_head = 0;

}

_itemCnt--;

return res;

}

}

public void remove(object value) {

lock (_lockObj) {

int found = -1;

int startVersion = _version;

try {

WalkDeque((int index) => {

if (PythonOps.IsOrEqualsRetBool(_data[index], value)) {

found = index;

return false;

}

return true;

});

} catch (IndexOutOfRangeException) {

Debug.Assert(_version != startVersion);

}

if (_version != startVersion) {

throw PythonOps.IndexError("deque mutated during remove().");

}

if (found == _head) {

popleft();

} else if (found == (_tail > 0 ? _tail - 1 : _data.Length - 1)) {

pop();

} else if (found == -1) {

throw PythonOps.ValueError("deque.remove(value): value not in deque");

} else {

// otherwise we're removing from the middle and need to slide the values over...

_version++;

int start;

if (_head >= _tail) {

start = 0;

} else {

start = _head;

}

bool finished = false;

object copying = _tail != 0 ? _data[_tail - 1] : _data[_data.Length - 1];

for (int i = _tail - 2; i >= start; i--) {

object tmp = _data[i];

_data[i] = copying;

if (i == found) {

finished = true;

break;

}

copying = tmp;

}

if (_head >= _tail && !finished) {

for (int i = _data.Length - 1; i >= _head; i--) {

object tmp = _data[i];

_data[i] = copying;

if (i == found) break;

copying = tmp;

}

}

// we're one smaller now

_tail--;

_itemCnt--;

if (_tail < 0) {

// and tail just wrapped to the beginning

_tail = _data.Length - 1;

}

}

}

}

public void rotate(CodeContext/*!*/ context) {

rotate(context, 1);

}

public void rotate(CodeContext/*!*/ context, object n) {

lock (_lockObj) {

// rotation is easy if we have no items!

if (_itemCnt == 0) return;

// set rot to the appropriate positive int

int rot = context.LanguageContext.ConvertToInt32(n) % _itemCnt;

rot = rot % _itemCnt;

if (rot == 0) return; // no need to rotate if we'll end back up where we started

if (rot < 0) rot += _itemCnt;

_version++;

if (_itemCnt == _data.Length) {

// if all indices are filled no moves are required

_head = _tail = (_tail - rot + _data.Length) % _data.Length;

} else {

// too bad, we got gaps, looks like we'll be doing some real work.

object[] newData = new object[_itemCnt]; // we re-size to itemCnt so that future rotates don't require work

int curWriteIndex = rot;

WalkDeque(delegate(int curIndex) {

newData[curWriteIndex] = _data[curIndex];

curWriteIndex = (curWriteIndex + 1) % _itemCnt;

return true;

});

_head = _tail = 0;

_data = newData;

}

}

}

public object this[CodeContext/*!*/ context, object index] {

get {

lock (_lockObj) {

return _data[IndexToSlot(context, index)];

}

}

set {

lock (_lockObj) {

_data[IndexToSlot(context, index)] = value;

}

}

}

public int count(CodeContext/*!*/ context, object x) {

int cnt = 0;

foreach (var o in this) {

if (PythonOps.IsOrEqualsRetBool(o, x)) {

cnt++;

}

}

return cnt;

}

public object reverse(CodeContext/*!*/ context) {

lock (_lockObj) {

if (_itemCnt == 0) return null;

_version++;

var cnt = _itemCnt >> 1;

var newIndex = _tail;

WalkDeque((curIndex) => {

if (--cnt < 0) return false;

newIndex--;

if (newIndex < 0) {

newIndex = _data.Length - 1;

}

var tmp = _data[curIndex];

_data[curIndex] = _data[newIndex];

_data[newIndex] = tmp;

return true;

});

}

return null;

}

public object maxlen => _maxLen == -1 ? null : (object)_maxLen;

#endregion

public bool __contains__(CodeContext/*!*/ context, object key) {

lock (_lockObj) {

int found = -1;

var startVersion = _version;

try {

WalkDeque((int index) => {

if (PythonOps.IsOrEqualsRetBool(_data[index], key)) {

found = index;

return false;

}

return true;

});

} catch (IndexOutOfRangeException) {

Debug.Assert(startVersion != _version);

}

if (startVersion != _version) {

throw PythonOps.RuntimeError("deque mutated during iteration");

}

return found != -1;

}

}

public object __copy__(CodeContext/*!*/ context) {

if (GetType() == typeof(deque)) {

deque res = new deque(_maxLen);

res.extend(((IEnumerable)this).GetEnumerator());

return res;

} else {

return PythonCalls.Call(context, DynamicHelpers.GetPythonType(this), ((IEnumerable)this).GetEnumerator());

}

}

public void __delitem__(CodeContext/*!*/ context, object index) {

lock (_lockObj) {

int realIndex = IndexToSlot(context, index);

_version++;

if (realIndex == _head) {

popleft();

} else if (realIndex == (_tail - 1) ||

(realIndex == (_data.Length - 1) && _tail == _data.Length)) {

pop();

} else {

// we're removing an index from the middle, what a pain...

// we'll just recreate our data by walking the data once.

object[] newData = new object[_data.Length];

int writeIndex = 0;

WalkDeque(delegate(int curIndex) {

if (curIndex != realIndex) {

newData[writeIndex++] = _data[curIndex];

}

return true;

});

_head = 0;

_tail = writeIndex;

_data = newData;

_itemCnt--;

}

}

}

public PythonTuple __reduce__() {

lock (_lockObj) {

object[] items = new object[_itemCnt];

int curItem = 0;

WalkDeque(delegate(int curIndex) {

items[curItem++] = _data[curIndex];

return true;

});

return PythonTuple.MakeTuple(

DynamicHelpers.GetPythonType(this),

PythonTuple.MakeTuple(PythonList.FromArrayNoCopy(items))

);

}

}

public int __len__() {

return _itemCnt;

}

[SpecialName]

public deque InPlaceAdd(object other) {

extend(other);

return this;

}

#region binary operators

public static deque operator +([NotNone] deque x, object y) {

if (y is deque t) return x + t;

throw PythonOps.TypeError($"can only concatenate deque (not \"{PythonOps.GetPythonTypeName(y)}\") to deque");

}

public static deque operator +([NotNone] deque x, [NotNone] deque y) {

var d = new deque(x._maxLen);

d.extend(x);

d.extend(y);

return d;

}

private static deque MultiplyWorker(deque self, int count) {

var d = new deque(self._maxLen);

if (count <= 0 || self._itemCnt == 0) return d;

d.extend(self);

if (count == 1) return d;

if (d._maxLen < 0 || d._itemCnt * count <= d._maxLen) {

var data = ArrayOps.Multiply(d._data, d._itemCnt, count);

d._data = data;

d._itemCnt = data.Length;

Debug.Assert(d._head == 0);

d._tail = 0;

} else {

var tempdata = ArrayOps.Multiply(d._data, d._itemCnt, (d._maxLen + (d._itemCnt - 1)) / d._itemCnt);

var data = new object[d._maxLen];

Array.Copy(tempdata, tempdata.Length - d._maxLen, data, 0, data.Length);

d._data = data;

d._itemCnt = data.Length;

Debug.Assert(d._head == 0);

d._tail = 0;

}

return d;

}

public static deque operator *([NotNone] deque x, int n) {

return MultiplyWorker(x, n);

}

public static deque operator *(int n, [NotNone] deque x) {

return MultiplyWorker(x, n);

}

public static object operator *([NotNone] deque self, [NotNone] Runtime.Index count) {

return PythonOps.MultiplySequence(MultiplyWorker, self, count, true);

}

public static object operator *([NotNone] Runtime.Index count, [NotNone] deque self) {

return PythonOps.MultiplySequence(MultiplyWorker, self, count, false);

}

public static object operator *([NotNone] deque self, object count) {

if (Converter.TryConvertToIndex(count, out int index)) {

return self * index;

}

throw PythonOps.TypeErrorForUnIndexableObject(count);

}

public static object operator *(object count, [NotNone] deque self) {

if (Converter.TryConvertToIndex(count, out int index)) {

return index * self;

}

throw PythonOps.TypeErrorForUnIndexableObject(count);

}

#endregion

#region IEnumerable Members

IEnumerator IEnumerable.GetEnumerator() {

return new _deque_iterator(this);

}

[PythonType]

public sealed class _deque_iterator : IEnumerable, IEnumerator {

private readonly deque _deque;

private int _curIndex;

private int _moveCnt;

private readonly int _version;

private int IndexToRealIndex(int index) {

index += _deque._head;

if (index > _deque._data.Length) {

index -= _deque._data.Length;

}

return index;

}

public _deque_iterator(deque d, int index = 0) {

lock (d._lockObj) {

// clamp index to range

if (index < 0) index = 0;

else if (index > d._itemCnt) index = d._itemCnt;

_deque = d;

_curIndex = IndexToRealIndex(index) - 1;

_moveCnt = index;

_version = d._version;

}

}

#region IEnumerator Members

object IEnumerator.Current {

get {

return _deque._data[_curIndex];

}

}

bool IEnumerator.MoveNext() {

lock (_deque._lockObj) {

if (_version != _deque._version) {

throw PythonOps.RuntimeError("deque mutated during iteration");

}

if (_moveCnt < _deque._itemCnt) {

_curIndex++;

_moveCnt++;

if (_curIndex == _deque._data.Length) {

_curIndex = 0;

}

return true;

}

return false;

}

}

void IEnumerator.Reset() {

_moveCnt = 0;

_curIndex = _deque._head - 1;

}

#endregion

#region IEnumerable Members

public IEnumerator GetEnumerator() => this;

#endregion

public int __length_hint__() {

lock (_deque._lockObj) {

if (_version != _deque._version) {

return 0;

}

}

return _deque._itemCnt - _moveCnt;

}

public PythonTuple __reduce__(CodeContext context) {

return PythonTuple.MakeTuple(

DynamicHelpers.GetPythonType(this),

PythonTuple.MakeTuple(

_deque,

_moveCnt

)

);

}

}

#endregion

#region __reversed__ implementation

public virtual IEnumerator __reversed__() {

return new _deque_reverse_iterator(this);

}

[PythonType]

public class _deque_reverse_iterator : IEnumerable, IEnumerator {

private readonly deque _deque;

private int _curIndex;

private int _moveCnt;

private readonly int _version;

public _deque_reverse_iterator(deque d) {

lock (d._lockObj) {

_deque = d;

_curIndex = d._tail;

_version = d._version;

}

}

#region IEnumerator Members

object IEnumerator.Current {

get {

return _deque._data[_curIndex];

}

}

bool IEnumerator.MoveNext() {

lock (_deque._lockObj) {

if (_version != _deque._version) {

throw PythonOps.RuntimeError("deque mutated during iteration");

}

if (_moveCnt < _deque._itemCnt) {

_curIndex--;

_moveCnt++;

if (_curIndex < 0) {

_curIndex = _deque._data.Length - 1;

}

return true;

}

return false;

}

}

void IEnumerator.Reset() {

_moveCnt = 0;

_curIndex = _deque._tail;

}

#endregion

#region IEnumerable Members

public IEnumerator GetEnumerator() => this;

#endregion

public int __length_hint__() {

lock (_deque._lockObj) {

if (_version != _deque._version) {

return 0;

}

}

return _deque._itemCnt - _moveCnt;

}

}

#endregion

#region private members

private void GrowArray() {

// do nothing if array is already at its max length

if (_data.Length == _maxLen) return;

object[] newData;

if (_maxLen < 0) newData = new object[_data.Length * 2];

else newData = new object[Math.Min(_maxLen, _data.Length * 2)];

// make the array completely sequential again

// by starting head back at 0.

int cnt1, cnt2;

if (_head >= _tail) {

cnt1 = _data.Length - _head;

cnt2 = _data.Length - cnt1;

} else {