HashSet.cs (11613B)
1 using Std.Clone; 2 using Std.Cmp; 3 using Std.Convert; 4 using Std.Hashbrown.HashMap; 5 using Std.Hashing; 6 using Std.Iter; 7 using Std.Maybe; 8 using Std.Ops; 9 using Std.Result; 10 using System; 11 using System.Runtime.CompilerServices; 12 using System.Runtime.InteropServices; 13 #region Namespaces 14 namespace Std.Hashbrown.HashSet { 15 #region Types 16 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 17 struct HashSet<TKey, THasher, TBuildHasher>: IExtend<TKey>, IInto<HashSet<TKey, THasher, TBuildHasher>>, IIntoIterator<TKey, IntoIter<TKey>> where TKey: notnull, IEq<TKey>, IHashable where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher> { 18 19 #region Type-level Constructors 20 #endregion 21 22 #region Instance Constructors 23 public HashSet() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 24 [MethodImpl(MethodImplOptions.AggressiveInlining)] 25 internal HashSet(HashMap<TKey, Unit, THasher, TBuildHasher> map) => _map = map; 26 #endregion 27 28 #region Type-level Fields 29 static readonly TKey? _dummy = default; 30 #endregion 31 32 #region Instance Fields 33 internal HashMap<TKey, Unit, THasher, TBuildHasher> _map; 34 #endregion 35 36 #region Type-level Properties 37 #endregion 38 39 #region Instance Properties 40 #endregion 41 42 #region Type-level Functions 43 [MethodImpl(MethodImplOptions.AggressiveInlining)] 44 internal static HashSet<TKey, THasher, TBuildHasher> WithCapacityAndHasher(ulong capacity, TBuildHasher hashBuilder) => new(HashMap<TKey, Unit, THasher, TBuildHasher>.WithCapacityAndHasher(capacity, hashBuilder)); 45 [MethodImpl(MethodImplOptions.AggressiveInlining)] 46 internal static HashSet<TKey, THasher, TBuildHasher> WithHasher(TBuildHasher hashBuilder) => new(HashMap<TKey, Unit, THasher, TBuildHasher>.WithHasher(hashBuilder)); 47 #endregion 48 49 #region Instance Functions 50 [MethodImpl(MethodImplOptions.AggressiveInlining)] 51 internal readonly ulong Capacity() => _map.Capacity(); 52 [MethodImpl(MethodImplOptions.AggressiveInlining)] 53 internal Unit Clear() => _map.Clear(); 54 [MethodImpl(MethodImplOptions.AggressiveInlining)] 55 internal readonly bool Contains(in TKey k) => _map.ContainsKey(in k); 56 public override readonly bool Equals(object? _) => false; 57 [MethodImpl(MethodImplOptions.AggressiveInlining)] 58 public Unit Extend<TIter>(TIter iter) where TIter: notnull, IIterator<TKey> => _map.Extend(iter.Map<TIter, TKey, ProdMut<TKey, Unit>>((k) => new ProdMut<TKey, Unit>(k, new Unit()))); 59 [MethodImpl(MethodImplOptions.AggressiveInlining)] 60 public Unit ExtendOne(TKey k) { 61 62 _ = _map.Insert(k, new Unit()); 63 return new Unit(); 64 } 65 [MethodImpl(MethodImplOptions.AggressiveInlining)] 66 public Unit ExtendReserve(uint additional) => _map.ExtendReserve(additional); 67 [MethodImpl(MethodImplOptions.AggressiveInlining)] 68 internal readonly Maybe<TKey> Get(in TKey k) { 69 70 var val = _map.GetKeyValue(in k); 71 return val.IsSome ? new(val._some.Item0) : Maybe<TKey>.None(); 72 } 73 public override readonly int GetHashCode() => 0; 74 [MethodImpl(MethodImplOptions.AggressiveInlining)] 75 internal ref readonly TKey GetOrInsert(TKey key) { 76 77 var hash = HashMap.Functions.MakeHash<TKey, THasher, TBuildHasher>(_map._hashBuilder, key); 78 var item = _map._table.Find(hash, (in ProdMut<TKey, Unit> tup) => tup.Item0 == key); 79 80 if (item.IsSome) { 81 return ref item._some.AsRef().Item0; 82 } else { 83 var hashBuilder = _map._hashBuilder; 84 var bucket = _map._table.Insert(hash, new(key, new Unit()), (in ProdMut<TKey, Unit> tup) => HashMap.Functions.MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 85 return ref bucket.AsRef().Item0; 86 } 87 } 88 [MethodImpl(MethodImplOptions.AggressiveInlining)] 89 internal ref readonly TKey GetOrInsertWith(TKey key, Fn<TKey> f) { 90 91 var hash = HashMap.Functions.MakeHash<TKey, THasher, TBuildHasher>(_map._hashBuilder, key); 92 var item = _map._table.Find(hash, (in ProdMut<TKey, Unit> tup) => tup.Item0 == key); 93 94 if (item.IsSome) { 95 return ref item._some.AsRef().Item0; 96 } else { 97 var hashBuilder = _map._hashBuilder; 98 var bucket = _map._table.Insert(hash, new(f(), new Unit()), (in ProdMut<TKey, Unit> tup) => HashMap.Functions.MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 99 return ref bucket.AsRef().Item0; 100 } 101 } 102 internal readonly ref readonly TKey GetRef(in TKey k, out bool exists) { 103 104 var copy = k; 105 var hash = HashMap.Functions.MakeHash<TKey, THasher, TBuildHasher>(_map._hashBuilder, k); 106 var item = _map._table.Find(hash, (in ProdMut<TKey, Unit> tup) => tup.Item0 == copy); 107 108 if (item.IsSome) { 109 exists = true; 110 return ref item._some.AsRef().Item0; 111 } else { 112 exists = false; 113 return ref _dummy!; 114 } 115 } 116 [MethodImpl(MethodImplOptions.AggressiveInlining)] 117 internal readonly TBuildHasher Hasher() => _map.Hasher(); 118 [MethodImpl(MethodImplOptions.AggressiveInlining)] 119 internal bool Insert(TKey k) => _map.Insert(k, new Unit()).IsNone; 120 [MethodImpl(MethodImplOptions.AggressiveInlining)] 121 public readonly HashSet<TKey, THasher, TBuildHasher> Into() => this; 122 [MethodImpl(MethodImplOptions.AggressiveInlining)] 123 public readonly IntoIter<TKey> IntoIter() => new(_map.IntoIter()); 124 [MethodImpl(MethodImplOptions.AggressiveInlining)] 125 internal readonly bool IsEmpty() => _map.IsEmpty(); 126 [MethodImpl(MethodImplOptions.AggressiveInlining)] 127 internal readonly ulong Len() => _map.Len(); 128 [MethodImpl(MethodImplOptions.AggressiveInlining)] 129 internal bool Remove(in TKey k) => _map.Remove(in k).IsSome; 130 [MethodImpl(MethodImplOptions.AggressiveInlining)] 131 internal Maybe<TKey> Replace(TKey k) { 132 133 var hash = HashMap.Functions.MakeHash<TKey, THasher, TBuildHasher>(_map._hashBuilder, k); 134 var item = _map._table.Find(hash, (in ProdMut<TKey, Unit> tup) => tup.Item0 == k); 135 136 if (item.IsSome) { 137 138 ref var val = ref item._some.AsMut(); 139 var old = val.Item0; 140 val.Item0 = k; 141 return new(old); 142 } else { 143 var hashBuilder = _map._hashBuilder; 144 var bucket = _map._table.Insert(hash, new(k, new Unit()), (in ProdMut<TKey, Unit> tup) => HashMap.Functions.MakeHash<TKey, THasher, TBuildHasher>(hashBuilder, tup.Item0)); 145 return Maybe<TKey>.None(); 146 } 147 } 148 [MethodImpl(MethodImplOptions.AggressiveInlining)] 149 internal Unit Reserve(ulong additional) => _map.Reserve(additional); 150 [MethodImpl(MethodImplOptions.AggressiveInlining)] 151 internal Unit Retain(FnIn<TKey, bool> f) => _map.Retain((ref TKey k, ref Unit _) => f(in k)); 152 [MethodImpl(MethodImplOptions.AggressiveInlining)] 153 internal Unit ShrinkTo(ulong minCapacity) => _map.ShrinkTo(minCapacity); 154 [MethodImpl(MethodImplOptions.AggressiveInlining)] 155 internal Unit ShrinkToFit() => _map.ShrinkToFit(); 156 [MethodImpl(MethodImplOptions.AggressiveInlining)] 157 internal Maybe<TKey> Take(in TKey k) { 158 159 var val = _map.RemoveEntry(in k); 160 return val.IsSome ? new(val._some.Item0) : Maybe<TKey>.None(); 161 } 162 public override readonly string ToString() => string.Empty; 163 readonly Result<HashSet<TKey, THasher, TBuildHasher>, Bottom> ITryInto<HashSet<TKey, THasher, TBuildHasher>, Bottom>.TryInto() => new(this); 164 #endregion 165 166 #region Operators 167 #endregion 168 169 #region Types 170 #endregion 171 } 172 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 173 struct IntoIter<TKey>: IInto<IntoIter<TKey>>, IExactSizeIterator<TKey>, IFusedIterator<TKey> where TKey: notnull { 174 175 #region Type-level Constructors 176 #endregion 177 178 #region Instance Constructors 179 public IntoIter() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 180 [MethodImpl(MethodImplOptions.AggressiveInlining)] 181 internal IntoIter(IntoIter<TKey, Unit> iter) => _iter = iter; 182 #endregion 183 184 #region Type-level Fields 185 #endregion 186 187 #region Instance Fields 188 IntoIter<TKey, Unit> _iter; 189 #endregion 190 191 #region Type-level Properties 192 #endregion 193 194 #region Instance Properties 195 #endregion 196 197 #region Type-level Functions 198 #endregion 199 200 #region Instance Functions 201 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<TKey>.AdvanceByDefault(ref this, n); 202 public ulong Count() => IIterator<TKey>.CountDefault(ref this); 203 public TInit Fold<TInit>(TInit init, Fn<TInit, TKey, TInit> f) where TInit: notnull => IIterator<TKey>.FoldDefault(ref this, init, f); 204 public override readonly bool Equals(object? _) => false; 205 public override readonly int GetHashCode() => 0; 206 public readonly IntoIter<TKey> Into() => this; 207 public readonly bool IsEmpty() => _iter.IsEmpty(); 208 public Maybe<TKey> Last() => IIterator<TKey>.LastDefault(ref this); 209 public readonly ulong Len() => _iter.Len(); 210 [MethodImpl(MethodImplOptions.AggressiveInlining)] 211 public Maybe<TKey> Next() { 212 213 var val = _iter.Next(); 214 return val.IsSome ? new(val._some.Item0) : Maybe<TKey>.None(); 215 } 216 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => _iter.SizeHint(); 217 public override readonly string ToString() => string.Empty; 218 public Result<TInit, TErr> TryFold<TInit, TErr>(TInit init, Fn<TInit, TKey, Result<TInit, TErr>> f) where TInit: notnull where TErr: notnull => IIterator<TKey>.TryFoldDefault(ref this, init, f); 219 readonly Result<IntoIter<TKey>, Bottom> ITryInto<IntoIter<TKey>, Bottom>.TryInto() => new(this); 220 #endregion 221 222 #region Operators 223 #endregion 224 225 #region Types 226 #endregion 227 } 228 static class Functions { 229 230 #region Type-level Constructors 231 #endregion 232 233 #region Instance Constructors 234 #endregion 235 236 #region Type-level Fields 237 #endregion 238 239 #region Instance Fields 240 #endregion 241 242 #region Type-level Properties 243 #endregion 244 245 #region Instance Properties 246 #endregion 247 248 #region Type-level Functions 249 [MethodImpl(MethodImplOptions.AggressiveInlining)] 250 internal static HashSet<TKey, THasher, TBuildHasher> Clone<TKey, THasher, TBuildHasher>(in this HashSet<TKey, THasher, TBuildHasher> self) where TKey: notnull, IClone<TKey>, IEq<TKey>, IHashable where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher>, IClone<TBuildHasher> => new(self._map.Clone()); 251 #endregion 252 253 #region Instance Functions 254 #endregion 255 256 #region Operators 257 #endregion 258 259 #region Types 260 #endregion 261 } 262 #endregion 263 264 #region Namespaces 265 #endregion 266 } 267 #endregion