VecDeque.cs - Std | Philomathic Life

VecDeque.cs (28023B)
      1 using Std.Clone;
      2 using Std.Cmp;
      3 using Std.Convert;
      4 using Std.Iter;
      5 using Std.Maybe;
      6 using Std.Num;
      7 using Std.Ops;
      8 using Std.Vec;
      9 using System;
     10 using Std.Result;
     11 using System.Runtime.CompilerServices;
     12 using System.Runtime.InteropServices;
     13 #region Namespaces
     14 namespace Std.Collections.VecDeque {
     15     #region Types
     16     [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)]
     17     public struct IntoIterator<T>: IDoubleEndedIterator<T>, IExactSizeIterator<T>, IFusedIterator<T>, IInto<IntoIterator<T>>, IIntoIterator<T, IntoIterator<T>> where T: notnull {
     18 
     19         #region Type-level Constructors
     20         #endregion
     21 
     22         #region Instance Constructors
     23         public IntoIterator() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!");
     24         [MethodImpl(MethodImplOptions.AggressiveInlining)]
     25         internal IntoIterator(VecDeque<T> inner) => _inner = inner;
     26         #endregion
     27 
     28         #region Type-level Fields
     29         #endregion
     30 
     31         #region Instance Fields
     32         VecDeque<T> _inner;
     33         #endregion
     34 
     35         #region Type-level Properties
     36         #endregion
     37 
     38         #region Instance Properties
     39         #endregion
     40 
     41         #region Type-level Functions
     42         #endregion
     43 
     44         #region Instance Functions
     45         public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<T>.AdvanceByDefault(ref this, n);
     46         public Result<Unit, ulong> AdvanceBackBy(ulong n) => IDoubleEndedIterator<T>.AdvanceBackByDefault(ref this, n);
     47         public ulong Count() => IIterator<T>.CountDefault(ref this);
     48         public override readonly bool Equals(object? _) => false;
     49         public TInit Fold<TInit>(TInit init, Fn<TInit, T, TInit> f) where TInit: notnull => IIterator<T>.FoldDefault(ref this, init, f);
     50         public override readonly int GetHashCode() => 0;
     51         public readonly IntoIterator<T> Into() => this;
     52         public readonly IntoIterator<T> IntoIter() => this;
     53         public readonly bool IsEmpty() => _inner.IsEmpty;
     54         public Maybe<T> Last() => IIterator<T>.LastDefault(ref this);
     55         public readonly ulong Len() => SizeHint().Item0;
     56         [MethodImpl(MethodImplOptions.AggressiveInlining)]
     57         public Maybe<T> Next() => _inner.PopFront();
     58         public Maybe<T> NextBack() => _inner.PopBack();
     59         public TInit RFold<TInit>(TInit init, Fn<TInit, T, TInit> f) where TInit: notnull => IDoubleEndedIterator<T>.RFoldDefault(ref this, init, f);
     60         public readonly Prod<ulong, Maybe<ulong>> SizeHint() {
     61 
     62             var len = _inner.Len;
     63             return new(len, new(len));
     64         }
     65         public override readonly string ToString() => string.Empty;
     66         public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, T, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<T>.TryFoldDefault(ref this, init, f);
     67         readonly Result<IntoIterator<T>, Bottom> ITryInto<IntoIterator<T>, Bottom>.TryInto() => new(this);
     68         public Result<TInit, TErr> TryRFold<TInit, TErr>(TInit init, Fn<TInit, T, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IDoubleEndedIterator<T>.TryRFoldDefault(ref this, init, f);
     69         #endregion
     70 
     71         #region Operators
     72         #endregion
     73 
     74         #region Types
     75         #endregion
     76     }
     77     [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)]
     78     public struct VecDeque<T>: IExtend<T>, IIndex<uint, T>, IIndexMut<uint, T>, IInto<VecDeque<T>>, IIntoIterator<T, IntoIterator<T>> where T: notnull {
     79 
     80         #region Type-level Constructors
     81         #endregion
     82 
     83         #region Instance Constructors
     84         [MethodImpl(MethodImplOptions.AggressiveInlining)]
     85         public VecDeque() => (_buf, _tail, _head) = (Vec<T>.WithCapacity(Math.Max(Functions.INITIAL_CAPACITY + 1u, Functions.MINIMUM_CAPACITY + 1u).NextPowerOfTwo()), uint.MinValue, uint.MinValue);
     86         [MethodImpl(MethodImplOptions.AggressiveInlining)]
     87         public VecDeque(uint capacity) => (_buf, _tail, _head) = (Vec<T>.WithCapacity(Math.Max(capacity + 1u, Functions.MINIMUM_CAPACITY + 1u).NextPowerOfTwo()), uint.MinValue, uint.MinValue);
     88         [MethodImpl(MethodImplOptions.AggressiveInlining)]
     89         internal VecDeque(Vec<T> buf, uint tail, uint head) => (_buf, _tail, _head) = (buf, tail, head);
     90         #endregion
     91 
     92         #region Type-level Fields
     93         static T? _dummy = default;
     94         #endregion
     95 
     96         #region Instance Fields
     97         internal Vec<T> _buf;
     98         internal uint _tail;
     99         internal uint _head;
    100         #endregion
    101 
    102         #region Type-level Properties
    103         #endregion
    104 
    105         #region Instance Properties
    106         readonly uint Cap => _buf.Capacity;
    107         public readonly uint Capacity => Cap - 1u;
    108         public readonly bool IsEmpty => _tail == _head;
    109         public readonly ref readonly T this[uint index] {
    110             [MethodImpl(MethodImplOptions.AggressiveInlining)]
    111             get {
    112                 if (index < Len) {
    113                     return ref Ptr()[(int)WrapAdd(_tail, index)];
    114                 } else {
    115                     throw new InvalidOperationException($"The index, {index.ToString()}, is greater than or equal to the length, {Len.ToString()}, of the VecDeque.");
    116                 }
    117             }
    118         }
    119         public readonly uint Len => Count(_tail, _head, Cap);
    120         #endregion
    121 
    122         #region Type-level Functions
    123         static uint Count(uint tail, uint head, uint size) => (head.WrappingSub(tail)) & (size - 1u);
    124         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    125         public static VecDeque<T> New() => new(uint.MinValue);
    126         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    127         public static VecDeque<T> WithCapacity(uint capacity) => new(capacity);
    128         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    129         static uint WrapIndex(uint index, uint size) => index & (size - 1u);
    130         #endregion
    131 
    132         #region Instance Functions
    133         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    134         readonly T[] Ptr() => _buf.Array;
    135         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    136         public Unit Append(ref VecDeque<T> other) {
    137 
    138             _ = Reserve(other.Len);
    139             _ = other.AsSlices(out var left, out var right);
    140             _ = CopySlice(_head, left);
    141             _ = CopySlice(WrapAdd(_head, (uint)left.Length), right);
    142             _head = WrapAdd(_head, other.Len);
    143             other._tail = other._head;
    144             return new Unit();
    145         }
    146         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    147         public readonly Unit AsMutSlices(out Span<T> v0, out Span<T> v1) {
    148 
    149             var head = _head;
    150             var tail = _tail;
    151             var buf = BufferAsMutSlice();
    152             _ = buf.RingSlices(head, tail, out v0, out v1);
    153             return new Unit();
    154         }
    155         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    156         public readonly Unit AsSlices(out ReadOnlySpan<T> v0, out ReadOnlySpan<T> v1) {
    157 
    158             var buf = BufferAsSlice();
    159             var slices = buf.RingSlices(_head, _tail, out v0, out v1);
    160             return new Unit();
    161         }
    162         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    163         public readonly Maybe<T> Back() => Get(Len.WrappingSub(1u));
    164         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    165         public readonly ref T BackMut(out bool exists) => ref GetMut(Len.WrappingSub(1u), out exists);
    166         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    167         readonly Span<T> BufferAsMutSlice() => Ptr().AsSpan(0, (int)Cap);
    168         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    169         readonly ReadOnlySpan<T> BufferAsSlice() => Ptr().AsSpan(0, (int)Cap);
    170         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    171         readonly T BufferRead(uint off) => Ptr()[(int)off];
    172         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    173         readonly Unit BufferWrite(uint off, T value) {
    174 
    175             Ptr()[(int)off] = value;
    176             return new Unit();
    177         }
    178         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    179         readonly Unit Copy(uint dst, uint src, uint len) {
    180 
    181             var arr = Ptr();
    182             Array.Copy(arr, (int)src, arr, (int)dst, (int)len);
    183             return new Unit();
    184         }
    185         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    186         Unit CopySlice(uint dst, ReadOnlySpan<T> src) {
    187 
    188             var headRoom = Cap - dst;
    189             if ((uint)src.Length <= headRoom) {
    190                 src.CopyTo(Ptr().AsSpan((int)dst));
    191             } else {
    192                 var left = src[..(int)headRoom];
    193                 var right = src[(int)headRoom..];
    194                 var arr = Ptr();
    195                 left.CopyTo(arr.AsSpan((int)dst));
    196                 right.CopyTo(arr.AsSpan());
    197             }
    198             return new Unit();
    199         }
    200         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    201         public Unit Clear() => Truncate(uint.MinValue);
    202         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    203         readonly Unit CopyNonOverlapping(uint dst, uint src, uint len) {
    204 
    205             var ptr = Ptr();
    206             Array.Copy(ptr, (int)src, ptr, (int)dst, (int)len);
    207             return new Unit();
    208         }
    209         public override readonly bool Equals(object? _) => false;
    210         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    211         public Unit Extend<TIter>(TIter iter) where TIter: notnull, IIterator<T> {
    212 
    213             Maybe<T> mbe;
    214             while ((mbe = iter.Next()).IsSome) {
    215                 if (Len == Cap) {
    216                     var (lower, _) = iter.SizeHint();
    217                     _ = Reserve((uint)lower.SaturatingAdd(1ul));
    218                 }
    219                 var head = _head;
    220                 _head = WrapAdd(_head, 1u);
    221                 _ = BufferWrite(head, mbe.Unwrap());
    222             }
    223             return new Unit();
    224         }
    225         public Unit ExtendOne(T val) => PushBack(val);
    226         public Unit ExtendReserve(uint additional) => Reserve(additional);
    227         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    228         public readonly Maybe<T> Front() => Get(uint.MinValue);
    229         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    230         public readonly ref T FrontMut(out bool exists) => ref GetMut(uint.MinValue, out exists);
    231         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    232         public readonly Maybe<T> Get(uint index) => index < Len ? new(Ptr()[(int)WrapAdd(_tail, index)]) : Maybe<T>.None();
    233         public override readonly int GetHashCode() => 0;
    234         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    235         public readonly ref T GetMut(uint index, out bool exists) {
    236 
    237             if (index < Len) {
    238                 exists = true;
    239                 return ref Ptr()[(int)WrapAdd(_tail, index)];
    240             } else {
    241                 exists = false;
    242                 return ref _dummy!;
    243             }
    244         }
    245         [MethodImpl(MethodImplOptions.NoInlining)]
    246         Unit Grow() {
    247 
    248             var oldCap = Cap;
    249             _ = _buf.ReserveExact(oldCap);
    250             return HandleCapacityIncrease(oldCap);
    251         }
    252         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    253         Unit HandleCapacityIncrease(uint oldCapacity) {
    254 
    255             var newCapacity = Cap;
    256             if (_tail <= _head) {
    257             } else if (_head < oldCapacity - _tail) {
    258                 _ = CopyNonOverlapping(oldCapacity, uint.MinValue, _head);
    259                 _head += oldCapacity;
    260             } else {
    261                 var newTail = newCapacity - (oldCapacity - _tail);
    262                 _ = CopyNonOverlapping(newTail, _tail, oldCapacity - _tail);
    263                 _tail = newTail;
    264             }
    265             return new Unit();
    266         }
    267         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    268         public Unit Insert(uint index, T value) {
    269 
    270             if (IsFull()) { _ = Grow(); }
    271             var idx = WrapAdd(_tail, index);
    272             var distanceToTail = index;
    273             var distanceToHead = Len - index;
    274             var contiguous = IsContiguous();
    275             var dTailLEdHead = distanceToTail <= distanceToHead;
    276             var idxGETail = idx >= _tail;
    277             if (contiguous && dTailLEdHead && index == uint.MinValue) {
    278                 _tail = WrapSub(_tail, 1u);
    279             } else if (contiguous && dTailLEdHead) {
    280                 var newTail = WrapSub(_tail, 1u);
    281                 _ = Copy(newTail, _tail, 1u);
    282                 _ = Copy(_tail, _tail + 1u, index - 1u);
    283                 _tail = newTail;
    284             } else if (contiguous && !dTailLEdHead) {
    285                 _ = Copy(idx + 1u, idx, _head - idx);
    286                 _head = WrapAdd(_head, 1u);
    287             } else if (!contiguous && dTailLEdHead && idxGETail) {
    288                 _ = Copy(_tail - 1u, _tail, index);
    289                 _tail -= 1u;
    290             } else if (!contiguous && dTailLEdHead && !idxGETail && idx == uint.MinValue) {
    291                 _ = Copy(_tail - 1u, _tail, Cap - _tail);
    292                 _ = Copy(Cap - 1u, uint.MinValue, 1u);
    293                 _tail -= 1u;
    294             } else if (!contiguous && dTailLEdHead && !idxGETail ) {
    295                 _ = Copy(_tail - 1u, _tail, Cap - _tail);
    296                 _ = Copy(Cap - 1u, uint.MinValue, 1u);
    297                 _ = Copy(uint.MinValue, 1u, idx - 1u);
    298                 _tail -= 1u;
    299             } else {
    300                 _ = Copy(idx + 1u, idx, _head - idx);
    301                 _head += 1u;
    302             }
    303             var newIdx = WrapAdd(_tail, index);
    304             return BufferWrite(newIdx, value);
    305         }
    306         public readonly IntoIterator<T> IntoIter() => new(this);
    307         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    308         readonly bool IsContiguous() => _tail <= _head;
    309         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    310         readonly bool IsFull() => Cap - Len == 1u;
    311         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    312         public readonly ref T ItemMut(uint index) {
    313 
    314             if (index < Len) {
    315                 return ref Ptr()[(int)WrapAdd(_tail, index)];
    316             } else {
    317                 throw new InvalidOperationException($"The index, {index.ToString()}, is greater than or equal to the length, {Len.ToString()}, of the VecDeque.");
    318             }
    319         }
    320         public readonly VecDeque<T> Into() => this;
    321         public Span<T> MakeContiguous() {
    322 
    323             if (IsContiguous()) {
    324                 var t = _tail;
    325                 var h = _head;
    326                 _ = BufferAsMutSlice().RingSlices(h, t, out var w0, out var _);
    327                 return w0;
    328             }
    329             var buf = Ptr();
    330             var cap = Cap;
    331             var len = Len;
    332             var free = _tail - _head;
    333             var tailLen = cap - _tail;
    334             if (free >= tailLen) {
    335                 Array.Copy(buf, 0, buf, (int)tailLen, (int)_head);
    336                 Array.Copy(buf, (int)_tail, buf, 0, (int)tailLen);
    337                 _tail = uint.MinValue;
    338                 _head = len;
    339             } else if (free > _head) {
    340                 Array.Copy(buf, (int)_tail, buf, (int)_head, (int)tailLen);
    341                 Array.Copy(buf, 0, buf, (int)(_head + tailLen), (int)_head);
    342                 _tail = _head;
    343                 _head = WrapAdd(_tail, len);
    344             } else {
    345                 var leftEdge = uint.MinValue;
    346                 var rightEdge = _tail;
    347                 while (leftEdge < len && rightEdge != cap) {
    348                     var rightOffset = uint.MinValue;
    349                     for (var i = leftEdge; i < rightEdge; i++) {
    350                         rightOffset = (i - leftEdge) % (cap - rightEdge);
    351                         _ = buf.AsSpan().Swap(i, rightEdge + rightOffset);
    352                     }
    353                     var nOps = rightEdge - leftEdge;
    354                     leftEdge += nOps;
    355                     rightEdge += rightOffset + 1u;
    356                 }
    357                 _tail = uint.MinValue;
    358                 _head = len;
    359             }
    360             var tail = _tail;
    361             var head = _head;
    362             _ = BufferAsMutSlice().RingSlices(head, tail, out var v0, out var _);
    363             return v0;
    364         }
    365         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    366         public Maybe<T> PopBack() {
    367 
    368             if (IsEmpty) {
    369                 return Maybe<T>.None();
    370             } else {
    371                 _head = WrapSub(_head, 1u);
    372                 var head = _head;
    373                 return new(BufferRead(head));
    374             }
    375         }
    376         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    377         public Maybe<T> PopFront() {
    378 
    379             if (IsEmpty) {
    380                 return Maybe<T>.None();
    381             } else {
    382                 var tail = _tail;
    383                 _tail = WrapAdd(_tail, 1u);
    384                 return new(BufferRead(tail));
    385             }
    386         }
    387         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    388         public Unit PushBack(T value) {
    389 
    390             if (IsFull()) { _ = Grow(); }
    391             var head = _head;
    392             _head = WrapAdd(_head, 1u);
    393             return BufferWrite(head, value);
    394         }
    395         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    396         public Unit PushFront(T value) {
    397 
    398             if (IsFull()) { _ = Grow(); }
    399             _tail = WrapSub(_tail, 1u);
    400             var tail = _tail;
    401             return BufferWrite(tail, value);
    402         }
    403         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    404         public Maybe<T> Remove(uint index) {
    405 
    406             if (IsEmpty || Len <= index) { return Maybe<T>.None(); }
    407             var idx = WrapAdd(_tail, index);
    408             var elem = new Maybe<T>(BufferRead(idx));
    409             var distanceToTail = index;
    410             var distanceToHead = Len - index;
    411             var contiguous = IsContiguous();
    412             var dTailLEdHead = distanceToTail <= distanceToHead;
    413             var idxGETail = idx >= _tail;
    414             if (contiguous && dTailLEdHead) {
    415                 _ = Copy(_tail + 1u, _tail, index);
    416                 _tail += 1u;
    417             } else if (contiguous && !dTailLEdHead) {
    418                 _ = Copy(idx, idx + 1u, _head - idx - 1u);
    419                 _head -= 1u;
    420             } else if (!contiguous && dTailLEdHead && idxGETail) {
    421                 _ = Copy(_tail + 1u, _tail, index);
    422                 _tail = WrapAdd(_tail, 1u);
    423             } else if (!contiguous && !dTailLEdHead && !idxGETail) {
    424                 _ = Copy(idx, idx + 1u, _head - idx - 1u);
    425                 _head -= 1u;
    426             } else if (!contiguous && !dTailLEdHead && idxGETail) {
    427                 _ = Copy(idx, idx + 1u, Cap - idx - 1u);
    428                 if (_head != uint.MinValue) {
    429                     _ = Copy(Cap - 1u, uint.MinValue, 1u);
    430                     _ = Copy(uint.MinValue, 1u, _head - 1u);
    431                 }
    432                 _head = WrapSub(_head, 1u);
    433             } else {
    434                 _ = Copy(1u, uint.MinValue, idx);
    435                 _ = Copy(uint.MinValue, Cap - 1u, 1u);
    436                 _ = Copy(_tail + 1u, _tail, Cap - _tail - 1u);
    437                 _tail = WrapAdd(_tail, 1u);
    438             }
    439             return elem;
    440         }
    441         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    442         public Unit Reserve(uint additional) {
    443 
    444             var oldCap = Cap;
    445             var usedCap = Len + 1u;
    446             var newCap = usedCap.CheckedAdd(additional).AndThen(Functions.f).Expect("Capacity overflow.");
    447             if (newCap > oldCap) {
    448                 _ = _buf.ReserveExact(newCap - usedCap);
    449                 _ = HandleCapacityIncrease(oldCap);
    450             }
    451             return new Unit();
    452         }
    453         public Unit ReserveExact(uint additional) => Reserve(additional);
    454         public Unit ResizeWith(uint newLen, Fn<T> f) {
    455 
    456             var len = Len;
    457             return newLen > len ? Extend(new RepeatWith<T>(f).Take<RepeatWith<T>, T>(newLen - len)) : Truncate(newLen);
    458         }
    459         public Unit Retain(FnIn<T, bool> f) {
    460 
    461             var len = Len;
    462             var del = uint.MinValue;
    463             var iter = IntoIter();
    464             Maybe<T> mbe;
    465             var i = uint.MinValue;
    466             while ((mbe = iter.Next()).IsSome) {
    467                 if (!f(mbe.Unwrap())) {
    468                     del += 1u;
    469                 } else if (del > uint.MinValue) {
    470                     _ = Swap(i - del, i);
    471                 }
    472                 i++;
    473             }
    474             return del > uint.MinValue ? Truncate(len - del) : new Unit();
    475         }
    476         public Unit ShrinkTo(uint minCapacity) {
    477 
    478             minCapacity = Math.Min(minCapacity, Capacity);
    479             var targetCap = Math.Max(Math.Max(minCapacity, Len + 1u), Functions.MINIMUM_CAPACITY + 1u).NextPowerOfTwo();
    480             if (targetCap < Cap) {
    481                 var headOutside = _head == uint.MinValue || _head >= targetCap;
    482                 if (_tail >= targetCap && headOutside) {
    483                    _ = CopyNonOverlapping(uint.MinValue, _tail, Len);
    484                     _head = Len;
    485                     _tail = uint.MinValue;
    486                 } else if (_tail == uint.MinValue && _tail < targetCap && headOutside) {
    487                     var len = WrapSub(_head, targetCap);
    488                     _ = CopyNonOverlapping(uint.MinValue, targetCap, len);
    489                     _head = len;
    490                 } else if (_tail >= targetCap) {
    491                     var len = Cap - _tail;
    492                     var newTail = targetCap - len;
    493                     _ = CopyNonOverlapping(newTail, _tail, len);
    494                     _tail = newTail;
    495                 }
    496                 _ = _buf.ShrinkTo(targetCap);
    497             }
    498             return new Unit();
    499         }
    500         public Unit ShrinkToFit() => ShrinkTo(uint.MinValue);
    501         public VecDeque<T> SplitOff(uint at) {
    502 
    503             var len = Len;
    504             var otherLen = len - at;
    505             var other = WithCapacity(otherLen);
    506             _ = AsSlices(out var firstHalf, out var secondHalf);
    507             var firstLen = (uint)firstHalf.Length;
    508             if (at < firstLen) {
    509                 var amountInFirst = firstLen - at;
    510                 firstHalf[(int)at..].CopyTo(other.Ptr().AsSpan());
    511                 secondHalf.CopyTo(other.Ptr().AsSpan((int)amountInFirst));
    512             } else {
    513                 var offset = at - firstLen;
    514                 secondHalf[(int)offset..].CopyTo(other.Ptr().AsSpan());
    515             }
    516             _head = WrapSub(_head, otherLen);
    517             other._head = other.WrapIndex(otherLen);
    518             return other;
    519         }
    520         public readonly Unit Swap(uint i, uint j) {
    521 
    522             var ri = WrapAdd(_tail, i);
    523             var rj = WrapAdd(_tail, j);
    524             var arr = Ptr();
    525             return arr.AsSpan().Swap(ri, rj);
    526         }
    527         public Maybe<T> SwapRemoveBack(uint index) {
    528 
    529             var length = Len;
    530             if (length > uint.MinValue && index < length - 1u) {
    531                 _ = Swap(index, length - 1u);
    532             } else if (index >= length) {
    533                 return Maybe<T>.None();
    534             }
    535             return PopBack();
    536         }
    537         public Maybe<T> SwapRemoveFront(uint index) {
    538 
    539             var length = Len;
    540             if (length > uint.MinValue && index < length && index != uint.MinValue) {
    541                 _ = Swap(index, uint.MinValue);
    542             } else if (index >= length) {
    543                 return Maybe<T>.None();
    544             }
    545             return PopFront();
    546         }
    547         public override readonly string ToString() => string.Empty;
    548         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    549         public Unit Truncate(uint len) {
    550 
    551             if (len <= Len) { _head = WrapSub(_head, Len - len); }
    552             return new Unit();
    553         }
    554         readonly Result<VecDeque<T>, Bottom> ITryInto<VecDeque<T>, Bottom>.TryInto() => new(this);
    555         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    556         readonly uint WrapAdd(uint idx, uint addend) => WrapIndex(idx.WrappingAdd(addend), Cap);
    557         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    558         readonly uint WrapIndex(uint idx) => WrapIndex(idx, Cap);
    559         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    560         readonly uint WrapSub(uint idx, uint subtrahend) => WrapIndex(idx.WrappingSub(subtrahend), Cap);
    561         #endregion
    562 
    563         #region Operators
    564         #endregion
    565 
    566         #region Types
    567         #endregion
    568     }
    569     public static class Functions {
    570 
    571         #region Type-level Constructors
    572         #endregion
    573 
    574         #region Instance Constructors
    575         #endregion
    576 
    577         #region Type-level Fields
    578         internal static readonly Fn<uint, Maybe<uint>> f = (u) => u.CheckedNextPowerOfTwo();
    579         internal const uint INITIAL_CAPACITY = 7u;
    580         internal const uint MINIMUM_CAPACITY = 1u;
    581         #endregion
    582 
    583         #region Instance Fields
    584         #endregion
    585 
    586         #region Type-level Properties
    587         #endregion
    588 
    589         #region Instance Properties
    590         #endregion
    591 
    592         #region Type-level Functions
    593         public static VecDeque<T> Clone<T>(in this VecDeque<T> self) where T: notnull, IClone<T> => new(self._buf.Clone(), self._tail, self._head);
    594         // Normal queues are used when you know for sure data is to be sorted in FIFO order; however sometimes there are situations where
    595         // this is not a guarantee and only a strong statisical likelihood. In such a situation, performing a linear scan and removing the value
    596         // is going to be the fastest way to search for T (since most of the time the item will be found immediately).
    597         // If code knows for sure the queue is in FIFO, then code SHOULD use the PopBack/PopFront functions.
    598         // If code is not confident of the order, then a VecDeque should likely not be used at all.
    599         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    600         public static Maybe<uint> LinearSearch<T>(in this VecDeque<T> self, in T x) where T: notnull, IEq<T> {
    601 
    602             var iter = self.IntoIter();
    603             Maybe<T> mbe;
    604             var index = uint.MinValue;
    605             while ((mbe = iter.Next()).IsSome) {
    606                 if (mbe.Unwrap() == x) {
    607                     return new(index);
    608                 } else {
    609                     index++;
    610                 }
    611             }
    612             return new();
    613         }
    614         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    615         public static uint LinearSearchUnsafe<T>(in this VecDeque<T> self, in T x) where T: notnull, IEq<T> {
    616 
    617             var iter = self.IntoIter();
    618             Maybe<T> mbe;
    619             var index = uint.MinValue;
    620             while ((mbe = iter.Next()).IsSome) {
    621                 if (mbe.Unwrap() == x) {
    622                     return index;
    623                 } else {
    624                     index++;
    625                 }
    626             }
    627             throw new ArgumentException("The value does not exist in the VecDeque.", nameof(x));
    628         }
    629         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    630         public static Maybe<T> LinearSearchAndPop<T>(ref this VecDeque<T> self, in T x) where T: notnull, IEq<T> {
    631 
    632             var iter = self.IntoIter();
    633             Maybe<T> mbe;
    634             var index = uint.MinValue;
    635             while ((mbe = iter.Next()).IsSome) {
    636                 if (mbe.Unwrap() == x) {
    637                     return self.Remove(index);
    638                 } else {
    639                     index++;
    640                 }
    641             }
    642             return Maybe<T>.None();
    643         }
    644         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    645         public static T LinearSearchAndPopUnsafe<T>(ref this VecDeque<T> self, in T x) where T: notnull, IEq<T> {
    646 
    647             var iter = self.IntoIter();
    648             Maybe<T> mbe;
    649             var index = uint.MinValue;
    650             while ((mbe = iter.Next()).IsSome) {
    651                 if (mbe.Unwrap() == x) {
    652                     return self.Remove(index).Unwrap();
    653                 } else {
    654                     index++;
    655                 }
    656             }
    657             throw new ArgumentException("The value does not exist in the VecDeque.", nameof(x));
    658         }
    659         #endregion
    660 
    661         #region Instance Functions
    662         #endregion
    663 
    664         #region Operators
    665         #endregion
    666 
    667         #region Types
    668         #endregion
    669     }
    670     #endregion
    671 
    672     #region Namespaces
    673     #endregion
    674 }
    675 #endregion
	Std Mainly a port of Rust's std.
	git clone https://git.philomathiclife.com/repos/Std
	Log \| Files \| Refs \| README