Std

Mainly a port of Rust's std.
git clone https://git.philomathiclife.com/repos/Std
Log | Files | Refs | README

Vec.cs (19042B)

      1 using Std.Clone;
      2 using Std.Cmp;
      3 using Std.Convert;
      4 using Std.Hashing;
      5 using Std.Iter;
      6 using Std.Maybe;
      7 using static Std.Maybe.Maybe<ulong>;
      8 using Std.Num;
      9 using Std.Ops;
     10 using Std.Result;
     11 using System;
     12 using System.Runtime.CompilerServices;
     13 using System.Runtime.InteropServices;
     14 #region Namespaces
     15 namespace Std.Vec {
     16     #region Types
     17     [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)]
     18     public struct IntoIterator<T>: IDoubleEndedIterator<T>, IExactSizeIterator<T>, IFusedIterator<T>, IInto<IntoIterator<T>>, IIntoIterator<T, IntoIterator<T>> where T: notnull {
     19 
     20         #region Type-level Constructors
     21         #endregion
     22 
     23         #region Instance Constructors
     24         public IntoIterator() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!");
     25         internal IntoIterator(Vec<T> vec) => (_vec, _index, _indexBack) = (vec, 0, (int)vec.Len - 1);
     26         #endregion
     27 
     28         #region Type-level Fields
     29         #endregion
     30 
     31         #region Instance Fields
     32         Vec<T> _vec;
     33         int _index;
     34         int _indexBack;
     35         #endregion
     36 
     37         #region Type-level Properties
     38         #endregion
     39 
     40         #region Instance Properties
     41         #endregion
     42 
     43         #region Type-level Functions
     44         #endregion
     45 
     46         #region Instance Functions
     47         public Result<Unit, ulong> AdvanceBy(ulong n) {
     48 
     49             if (n == ulong.MinValue) {
     50                 return new(new Unit());
     51             } else {
     52                 var val = _indexBack - _index + 1;
     53 
     54                 if (n > (ulong)val) {
     55                     _index = _indexBack + 1;
     56                     return new((ulong)val);
     57                 } else {
     58                     _index += (int)n;
     59                     return new(new Unit());
     60                 }
     61             }
     62         }
     63         public Result<Unit, ulong> AdvanceBackBy(ulong n) {
     64 
     65             if (n == ulong.MinValue) {
     66                 return new(new Unit());
     67             } else {
     68                 var val = _indexBack - _index + 1;
     69 
     70                 if (n > (ulong)val) {
     71                     _indexBack = _index - 1;
     72                     return new((ulong)val);
     73                 } else {
     74                     _indexBack -= (int)n;
     75                     return new(new Unit());
     76                 }
     77             }
     78         }
     79         public readonly ReadOnlySpan<T> AsSlice() => _index <= _indexBack ? _vec.AsSlice()[_index..(_indexBack + 1)] : ReadOnlySpan<T>.Empty;
     80         public readonly ulong Count() => Len();
     81         public override readonly bool Equals(object? _) => false;
     82         public TInit Fold<TInit>(TInit init, Fn<TInit, T, TInit> f) where TInit: notnull {
     83 
     84             while (_index <= _indexBack) { init = f(init, _vec[(uint)_index++]); }
     85             return init;
     86         }
     87         public override readonly int GetHashCode() => 0;
     88         public readonly IntoIterator<T> Into() => this;
     89         public readonly IntoIterator<T> IntoIter() => this;
     90         public readonly bool IsEmpty() => Len() == ulong.MinValue;
     91         public readonly Maybe<T> Last() => _index > _indexBack ? Maybe<T>.None() : new(_vec[(uint)_indexBack]);
     92         public readonly ulong Len() => (ulong)(1 + _indexBack - _index);
     93         [MethodImpl(MethodImplOptions.AggressiveInlining)]
     94         public Maybe<T> Next() => _index > _indexBack ? Maybe<T>.None() : Maybe<T>.Some(_vec[(uint)_index++]);
     95         public Maybe<T> NextBack() => _indexBack < _index ? Maybe<T>.None() : Maybe<T>.Some(_vec[(uint)_indexBack--]);
     96         public TInit RFold<TInit>(TInit init, Fn<TInit, T, TInit> f) where TInit: notnull {
     97 
     98             while (_index <= _indexBack) { init = f(init, _vec[(uint)_indexBack--]); }
     99             return init;
    100         }
    101         public readonly Prod<ulong, Maybe<ulong>> SizeHint() => new(Len(), Some(Len()));
    102         public override readonly string ToString() => string.Empty;
    103         public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, T, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull {
    104 
    105             while (_index <= _indexBack) {
    106                 var res = f(init, _vec[(uint)_index++]);
    107 
    108                 if (res.IsErr) {
    109                     return res;
    110                 } else {
    111                     init = res._ok;
    112                 }
    113             }
    114             return new(init);
    115         }
    116         readonly Result<IntoIterator<T>, Bottom> ITryInto<IntoIterator<T>, Bottom>.TryInto() => new(this);
    117         public Result<TInit, TErr> TryRFold<TInit, TErr>(TInit init, Fn<TInit, T, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull {
    118 
    119             while (_index <= _indexBack) {
    120                 var res = f(init, _vec[(uint)_indexBack--]);
    121 
    122                 if (res.IsErr) {
    123                     return res;
    124                 } else {
    125                     init = res._ok;
    126                 }
    127             }
    128             return new(init);
    129         }
    130         #endregion
    131 
    132         #region Operators
    133         #endregion
    134 
    135         #region Types
    136         #endregion
    137     }
    138     [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)]
    139     public struct Vec<T>: IFromIterator<Vec<T>, T>, IExtend<T>, IIndex<uint, T>, IIndexMut<uint, T>, IInto<Vec<T>>, IIntoIterator<T, IntoIterator<T>> where T: notnull {
    140 
    141         #region Type-level Constructors
    142         #endregion
    143 
    144         #region Instance Constructors
    145         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    146         public Vec() => (_arr, _len) = (System.Array.Empty<T>(), uint.MinValue);
    147         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    148         public Vec(uint capacity) => (_arr, _len) = (capacity == uint.MinValue ? System.Array.Empty<T>() : new T[(int)capacity], uint.MinValue);
    149         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    150         internal Vec(T[] arr, uint len) => (_arr, _len) = (arr, len);
    151         #endregion
    152 
    153         #region Type-level Fields
    154         static T? _dummy = default;
    155         #endregion
    156 
    157         #region Instance Fields
    158         T[] _arr;
    159         [System.Diagnostics.CodeAnalysis.SuppressMessage("Style", "IDE0032:Use auto property", Justification = "Want to make public property readonly.")]
    160         uint _len;
    161         #endregion
    162 
    163         #region Type-level Properties
    164         #endregion
    165 
    166         #region Instance Properties
    167         public readonly uint Capacity => (uint)_arr.Length;
    168         public readonly bool IsEmpty => _len == uint.MinValue;
    169         public readonly ref readonly T this[uint index] {
    170             [MethodImpl(MethodImplOptions.AggressiveInlining)]
    171             get {
    172 
    173                 if (index < _len) {
    174                     return ref _arr[(int)index];
    175                 } else {
    176                     throw new InvalidOperationException($"The index, {index.ToString()}, is greater than or equal to the length, {_len.ToString()}, of the vector.");
    177                 }
    178             }
    179         }
    180         public readonly uint Len => _len;
    181         internal readonly T[] Array => _arr;
    182         #endregion
    183 
    184         #region Type-level Functions
    185         public static Vec<T> New() => new(uint.MinValue);
    186         public static Vec<T> WithCapacity(uint capacity) => new(capacity);
    187         public static Vec<T> FromIter<TIter>(TIter iter) where TIter: notnull, IIterator<T> {
    188 
    189             var vec = new Vec<T>();
    190             _ = vec.Extend(iter);
    191             return vec;
    192         }
    193         #endregion
    194 
    195         #region Instance Functions
    196         public Unit Append(ref Vec<T> other) {
    197 
    198             _ = Reserve(other._len);
    199             System.Array.Copy(other._arr, 0L, _arr, _len, other._len);
    200             _len += other._len;
    201             other._len = uint.MinValue;
    202             return new();
    203         }
    204         public readonly T[] AsArray() => _arr;
    205         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    206         public readonly Span<T> AsMutSlice() => _arr.AsSpan()[..(int)_len];
    207         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    208         public readonly ReadOnlySpan<T> AsSlice() => _arr.AsSpan()[..(int)_len];
    209         public Unit Clear() => Truncate(uint.MinValue);
    210         public Unit DeDupBy(FnRef<T, T, bool> f) {
    211 
    212             var len = _len;
    213 
    214             if (len == uint.MinValue) { return new(); }
    215             Span<T> span = new(_arr, 0, (int)len);
    216             var nextRead = 1u;
    217             var nextWrite = 1u;
    218             T val0;
    219             T val1;
    220 
    221             while (nextRead < len) {
    222                 val0 = span[(int)nextRead];
    223                 val1 = span[(int)(nextWrite - 1)];
    224 
    225                 if (!f(ref val0, ref val1)) {
    226                     if (nextRead != nextWrite) { _ = span.Swap(nextRead, nextWrite); }
    227                     nextWrite++;
    228                 }
    229                 nextRead++;
    230             }
    231             return Truncate(nextWrite);
    232         }
    233         public Unit DeDupByKey<T2>(FnRef<T, T2> f) where T2: notnull, IPartialEq<T2, T2> => DeDupBy((ref T a, ref T b) => f(ref a) == f(ref b));
    234         public override readonly bool Equals(object? _) => false;
    235         public Unit Extend<TIter>(TIter iter) where TIter: notnull, IIterator<T> {
    236 
    237             var cap = iter.SizeHint().Item0;
    238             _ = Reserve(cap > uint.MaxValue ? uint.MaxValue : (uint)cap);
    239             var val = iter.Next();
    240 
    241             while (val.IsSome) {
    242                 
    243                 if ((uint)_arr.Length <= _len + 1u) {
    244                     var tmp = new T[2 * _arr.Length];
    245                     System.Array.Copy(_arr, 0L, tmp, 0L, _arr.Length);
    246                     _arr = tmp;
    247                 }
    248                 _arr[(int)_len++] = val._some;
    249                 val = iter.Next();
    250             }
    251             return new();
    252         }
    253         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    254         public Unit ExtendFromSlice(ReadOnlySpan<T> other) {
    255 
    256             _ = Reserve((uint)other.Length);
    257             other.CopyTo(new(_arr, (int)_len, other.Length));
    258             _len += (uint)other.Length;
    259             return new();
    260         }
    261         public Unit ExtendOne(T val) => Push(val);
    262         public Unit ExtendReserve(uint additional) => Reserve(additional);
    263         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    264         public readonly Maybe<T> Get(uint index) => index < _len ? new(this[index]) : Maybe<T>.None();
    265         public override readonly int GetHashCode() => 0;
    266         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    267         public readonly ref T GetMut(uint index, out bool exists) {
    268 
    269             if (index < _len) {
    270                 exists = true;
    271                 return ref _arr[(int)index];
    272             } else {
    273                 exists = false;
    274                 return ref _dummy!;
    275             }
    276         }
    277         public Unit Insert(uint index, T elem) {
    278 
    279             if (index <= _len) {
    280                 _ = Reserve(1u);
    281                 System.Array.Copy(_arr, index, _arr, 1L + index, _len - index);
    282                 _len++;
    283                 _arr[index] = elem;
    284                 return new();
    285             } else {
    286                 throw new InvalidOperationException($"The index, {index.ToString()}, is greater than the length, {_len.ToString()}, of the vector.");
    287             }
    288         }
    289         public readonly Vec<T> Into() => this;
    290         public readonly IntoIterator<T> IntoIter() => new(this);
    291         public readonly ref T ItemMut(uint index) {
    292 
    293             if (index < _len) {
    294                 return ref _arr[(int)index];
    295             } else {
    296                 throw new InvalidOperationException($"The index, {index.ToString()}, is greater than or equal to the length, {_len.ToString()}, of the vector.");
    297             }
    298         }
    299         public readonly Prod<T[], uint> IntoRawParts() => new(_arr, _len);
    300         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    301         public Maybe<T> Pop() => _len == uint.MinValue ? Maybe<T>.None() : new(_arr[(int)--_len]);
    302         [MethodImpl(MethodImplOptions.AggressiveInlining)]
    303         public Unit Push(T val) {
    304 
    305             _ = Reserve(1u);
    306             _arr[(int)_len++] = val;
    307             return new();
    308         }
    309         public T Remove(uint index) {
    310 
    311             if (index >= _len) {
    312                 throw new InvalidOperationException($"The index, {index.ToString()}, is greater than or equal to the length, {_len.ToString()}, of the vector.");
    313             } else {
    314                 var val = _arr[index];
    315                 System.Array.Copy(_arr, index + 1L, _arr, index, (--_len) - index);
    316                 return val;
    317             }
    318         }
    319         public Unit Reserve(uint additional) {
    320 
    321             additional += _len;
    322             if ((uint)_arr.Length < additional) { System.Array.Resize(ref _arr, (int)additional.NextPowerOfTwo()); }
    323             return new();
    324         }
    325         public Unit ReserveExact(uint additional) {
    326 
    327             additional += _len;
    328             if ((uint)_arr.Length < additional) { System.Array.Resize(ref _arr, (int)additional); }
    329             return new();
    330         }
    331         public Unit ResizeWith(uint newLen, Fn<T> f) {
    332 
    333             var len = _len;
    334 
    335             if (newLen > len) {
    336                 _ = Reserve(newLen - len);
    337                 for (var i = len; i < newLen; i++) { _arr[i] = f(); }
    338                 _len = newLen;
    339                 return new();
    340             } else {
    341                 return Truncate(newLen);
    342             }
    343         }
    344         public Unit Retain(FnIn<T, bool> f) {
    345 
    346             var len = _len;
    347             var del = uint.MinValue;
    348             Span<T> span = new(_arr, 0, (int)len);
    349             T val;
    350 
    351             for (var i = uint.MinValue; i < len; i++) {
    352                 val = span[(int)i];
    353 
    354                 if (!f(in val)) {
    355                     del += 1u;
    356                 } else if (del > uint.MinValue) {
    357                     _ = span.Swap(i - del, i);
    358                 }
    359             }
    360             return del > uint.MinValue ? Truncate(len - del) : new();
    361         }
    362         public Unit SetLenUnsafe(uint newLen) {
    363 
    364             _len = newLen;
    365             return new();
    366         }
    367         public Unit ShrinkTo(uint min) {
    368 
    369             min = min >= _len ? min : _len;
    370 
    371             if ((uint)_arr.Length > min) {
    372                 System.Array.Resize(ref _arr, (int)min);
    373             } else if ((uint)_arr.Length < min) {
    374                 throw new InvalidOperationException($"The current capacity, {_arr.Length.ToString()}, is smaller than the minimum value, {min.ToString()}, that was passed.");
    375             }
    376             return new();
    377         }
    378         public Unit ShrinkToFit() {
    379 
    380             if ((uint)_arr.Length > _len) {
    381                 System.Array.Resize(ref _arr, (int)_len);
    382             }
    383             return new();
    384         }
    385         public Vec<T> SplitOff(uint at) {
    386 
    387             if (at < uint.MinValue) {
    388                 var otherLen = _len - at;
    389                 Vec<T> other = new(otherLen);
    390                 _len = at;
    391                 other._len = otherLen;
    392                 System.Array.Copy(_arr, (int)at, other._arr, 0, (int)otherLen);
    393                 return other;
    394             } else if (at == uint.MinValue) {
    395                 _arr = new T[_arr.Length];
    396                 _len = uint.MinValue;
    397                 return new(_arr, _len);
    398             } else {
    399                 throw new InvalidOperationException($"The index to split at, {at.ToString()}, must be less than or equal to the length, {_len.ToString()}.");
    400             }
    401         }
    402         public T SwapRemove(uint index) {
    403 
    404             var val = this[index];
    405             _arr[(int)index] = _arr[(int)(--_len)];
    406             return val;
    407         }
    408         public override readonly string ToString() => string.Empty;
    409         public Unit Truncate(uint len) {
    410             _len = len < _len ? len : _len;
    411             return new();
    412         }
    413         readonly Result<Vec<T>, Bottom> ITryInto<Vec<T>, Bottom>.TryInto() => new(this);
    414         #endregion
    415 
    416         #region Operators
    417         #endregion
    418 
    419         #region Types
    420         #endregion
    421     }
    422     public static class Functions {
    423 
    424         #region Type-level Constructors
    425         #endregion
    426 
    427         #region Instance Constructors
    428         #endregion
    429 
    430         #region Type-level Fields
    431         #endregion
    432 
    433         #region Instance Fields
    434         #endregion
    435 
    436         #region Type-level Properties
    437         #endregion
    438 
    439         #region Instance Properties
    440         #endregion
    441 
    442         #region Type-level Functions
    443         public static Vec<T> Clone<T>(in this Vec<T> self) where T: notnull, IClone<T> => new(Std.Functions.Clone(self.Array), self.Len);
    444         public static Ordering Cmp<T>(in this Vec<T> self, in Vec<T> other) where T: notnull, IOrd<T> => self.AsSlice().Cmp(other.AsSlice());
    445         public static int CompareToComparable<T>(in this Vec<T> self, in Vec<T> other) where T: notnull, IComparable<T> => self.AsSlice().CompareToComparable(other.AsSlice());
    446         public static bool Eq<T0, T1>(in this Vec<T0> self, in Vec<T1> other) where T0: notnull, IPartialEq<T0, T1> where T1: notnull, IPartialEq<T1, T0> => self.AsSlice().Eq(other.AsSlice());
    447         public static bool EqualsEquatable<T>(in this Vec<T> self, in Vec<T> other) where T: notnull, IEquatable<T> => self.AsSlice().EqualsEquatable(other.AsSlice());
    448         public static bool Ge<T0, T1>(in this Vec<T0> self, in Vec<T1> other) where T0: notnull, IPartialOrd<T0, T1> where T1: notnull, IPartialOrd<T1, T0> => self.AsSlice().Ge(other.AsSlice());
    449         public static int GetHashCodeEquatable<T>(in this Vec<T> self) where T: notnull, IEquatable<T> => self.AsSlice().GetHashCodeEquatable();
    450         public static bool Gt<T0, T1>(in this Vec<T0> self, in Vec<T1> other) where T0: notnull, IPartialOrd<T0, T1> where T1: notnull, IPartialOrd<T1, T0> => self.AsSlice().Gt(other.AsSlice());
    451         public static Unit Hash<T, THasher>(in this Vec<T> self, ref THasher hasher) where T: notnull, IHashable where THasher: notnull, IHasher => self.AsSlice().Hash(ref hasher);
    452         public static string LowerHex(in this Vec<byte> self) => self.AsSlice().LowerHex();
    453         public static bool Le<T0, T1>(in this Vec<T0> self, in Vec<T1> other) where T0: notnull, IPartialOrd<T0, T1> where T1: notnull, IPartialOrd<T1, T0> => self.AsSlice().Le(other.AsSlice());
    454         public static bool Lt<T0, T1>(in this Vec<T0> self, in Vec<T1> other) where T0: notnull, IPartialOrd<T0, T1> where T1: notnull, IPartialOrd<T1, T0> => self.AsSlice().Lt(other.AsSlice());
    455         public static bool Ne<T0, T1>(in this Vec<T0> self, in Vec<T1> other) where T0: notnull, IPartialEq<T0, T1> where T1: notnull, IPartialEq<T1, T0> => self.AsSlice().Ne(other.AsSlice());
    456         public static Maybe<Ordering> PartialCmp<T0, T1>(in this Vec<T0> self, in Vec<T1> other) where T0: notnull, IPartialOrd<T0, T1> where T1: notnull, IPartialOrd<T1, T0> => self.AsSlice().PartialCmp(other.AsSlice());
    457         public static string ToArrayString<T>(in this Vec<T> self) where T: notnull => self.AsSlice().ToArrayString();
    458         public static string UpperHex(in this Vec<byte> self) => self.AsSlice().UpperHex();
    459         #endregion
    460 
    461         #region Instance Functions
    462         #endregion
    463 
    464         #region Operators
    465         #endregion
    466 
    467         #region Types
    468         #endregion
    469     }
    470     #endregion
    471 
    472     #region Namespaces
    473     #endregion
    474 }
    475 #endregion