HashSet.cs (21689B)
1 using Std.Clone; 2 using Std.Cmp; 3 using Std.Convert; 4 using @base = Std.Hashbrown.HashSet; 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.Collections.HashSet { 15 #region Types 16 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 17 public struct Difference<TKey, THasher, TBuildHasher>: IInto<Difference<TKey, THasher, TBuildHasher>>, IFusedIterator<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 Difference() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 24 internal Difference(IntoIter<TKey> iter, HashSet<TKey, THasher, TBuildHasher> other) => (_iter, _other) = (iter, other); 25 #endregion 26 27 #region Type-level Fields 28 #endregion 29 30 #region Instance Fields 31 IntoIter<TKey> _iter; 32 HashSet<TKey, THasher, TBuildHasher> _other; 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<TKey>.AdvanceByDefault(ref this, n); 46 public ulong Count() => IIterator<TKey>.CountDefault(ref this); 47 public TInit Fold<TInit>(TInit init, Fn<TInit, TKey, TInit> f) where TInit: notnull => IIterator<TKey>.FoldDefault(ref this, init, f); 48 public override readonly bool Equals(object? _) => false; 49 public override readonly int GetHashCode() => 0; 50 public readonly Difference<TKey, THasher, TBuildHasher> Into() => this; 51 public Maybe<TKey> Last() => IIterator<TKey>.LastDefault(ref this); 52 public Maybe<TKey> Next() { 53 54 while (true) { 55 var elt = _iter.Next(); 56 57 if (elt.IsSome) { 58 59 if (!_other.Contains(elt._some)) { 60 return new(elt._some); 61 } 62 } else { 63 return Maybe<TKey>.None(); 64 } 65 } 66 } 67 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => new(ulong.MinValue, _iter.SizeHint().Item1); 68 public override readonly string ToString() => string.Empty; 69 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); 70 readonly Result<Difference<TKey, THasher, TBuildHasher>, Bottom> ITryInto<Difference<TKey, THasher, TBuildHasher>, Bottom>.TryInto() => new(this); 71 #endregion 72 73 #region Operators 74 #endregion 75 76 #region Types 77 #endregion 78 } 79 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 80 public struct HashSet<TKey, THasher, TBuildHasher>: IEq<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> { 81 82 #region Type-level Constructors 83 #endregion 84 85 #region Instance Constructors 86 public HashSet() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 87 [MethodImpl(MethodImplOptions.AggressiveInlining)] 88 internal HashSet(@base::HashSet<TKey, THasher, TBuildHasher> @base) => _base = @base; 89 [MethodImpl(MethodImplOptions.AggressiveInlining)] 90 public HashSet(uint capacity, TBuildHasher hashBuilder) => _base = @base::HashSet<TKey, THasher, TBuildHasher>.WithCapacityAndHasher(capacity, hashBuilder); 91 [MethodImpl(MethodImplOptions.AggressiveInlining)] 92 public HashSet(TBuildHasher hashBuilder) => _base = @base::HashSet<TKey, THasher, TBuildHasher>.WithHasher(hashBuilder); 93 #endregion 94 95 #region Type-level Fields 96 #endregion 97 98 #region Instance Fields 99 internal @base::HashSet<TKey, THasher, TBuildHasher> _base; 100 #endregion 101 102 #region Type-level Properties 103 #endregion 104 105 #region Instance Properties 106 public readonly uint Capacity => (uint)_base.Capacity(); 107 public readonly bool IsEmpty => _base.IsEmpty(); 108 public readonly uint Len => (uint)_base.Len(); 109 #endregion 110 111 #region Type-level Functions 112 public static HashSet<TKey, THasher, TBuildHasher> WithCapacityAndHasher(uint capacity, TBuildHasher hashBuilder) => new(@base::HashSet<TKey, THasher, TBuildHasher>.WithCapacityAndHasher(capacity, hashBuilder)); 113 public static HashSet<TKey, THasher, TBuildHasher> WithHasher(TBuildHasher hashBuilder) => new(@base::HashSet<TKey, THasher, TBuildHasher>.WithHasher(hashBuilder)); 114 #endregion 115 116 #region Instance Functions 117 [MethodImpl(MethodImplOptions.AggressiveInlining)] 118 public Unit Clear() => _base.Clear(); 119 [MethodImpl(MethodImplOptions.AggressiveInlining)] 120 public readonly bool Contains(in TKey k) => _base.Contains(in k); 121 public readonly Difference<TKey, THasher, TBuildHasher> Difference(in HashSet<TKey, THasher, TBuildHasher> other) => new(IntoIter(), other); 122 public override readonly bool Equals(object? _) => false; 123 [MethodImpl(MethodImplOptions.AggressiveInlining)] 124 public Unit Extend<TIter>(TIter iter) where TIter: notnull, IIterator<TKey> => _base.Extend(iter); 125 public Unit ExtendOne(TKey val) => _base.ExtendOne(val); 126 public Unit ExtendReserve(uint additional) => _base.Reserve(additional); 127 [MethodImpl(MethodImplOptions.AggressiveInlining)] 128 public readonly Maybe<TKey> Get(in TKey k) => _base.Get(in k); 129 public override readonly int GetHashCode() => 0; 130 [MethodImpl(MethodImplOptions.AggressiveInlining)] 131 public ref readonly TKey GetOrInsert(TKey key) => ref _base.GetOrInsert(key); 132 [MethodImpl(MethodImplOptions.AggressiveInlining)] 133 public ref readonly TKey GetOrInsertWith(TKey key, Fn<TKey> f) => ref _base.GetOrInsertWith(key, f); 134 [MethodImpl(MethodImplOptions.AggressiveInlining)] 135 public readonly ref readonly TKey GetRef(in TKey k, out bool exists) => ref _base.GetRef(in k, out exists); 136 [MethodImpl(MethodImplOptions.AggressiveInlining)] 137 public readonly TBuildHasher Hasher() => _base.Hasher(); 138 [MethodImpl(MethodImplOptions.AggressiveInlining)] 139 public bool Insert(TKey k) => _base.Insert(k); 140 public readonly Intersection<TKey, THasher, TBuildHasher> Intersection(HashSet<TKey, THasher, TBuildHasher> other) => new(IntoIter(), other); 141 public readonly HashSet<TKey, THasher, TBuildHasher> Into() => this; 142 public readonly IntoIter<TKey> IntoIter() => new(_base.IntoIter()); 143 public readonly bool IsDisjoint(in HashSet<TKey, THasher, TBuildHasher> other) { 144 145 var cpy = this; 146 var cpyOther = other; 147 var iter = cpy.IntoIter(); 148 var iterOther = cpyOther.IntoIter(); 149 return cpy.Len <= cpyOther.Len ? iter.All<IntoIter<TKey>, TKey>((v) => !cpyOther.Contains(in v)) : iterOther.All<IntoIter<TKey>, TKey>((v) => !cpy.Contains(in v)); 150 } 151 public readonly bool IsSubset(in HashSet<TKey, THasher, TBuildHasher> other) { 152 153 var cpy = this; 154 var cpyOther = other; 155 var iter = cpy.IntoIter(); 156 return cpy.Len <= cpyOther.Len && iter.All<IntoIter<TKey>, TKey>((v) => cpyOther.Contains(in v)); 157 } 158 public readonly bool IsSuperset(in HashSet<TKey, THasher, TBuildHasher> other) => other.IsSubset(in this); 159 [MethodImpl(MethodImplOptions.AggressiveInlining)] 160 public bool Remove(in TKey k) => _base.Remove(in k); 161 [MethodImpl(MethodImplOptions.AggressiveInlining)] 162 public Maybe<TKey> Replace(TKey k) => _base.Replace(k); 163 [MethodImpl(MethodImplOptions.AggressiveInlining)] 164 public Unit Reserve(uint additional) => _base.Reserve(additional); 165 public readonly Unit Retain(FnIn<TKey, bool> f) => _base.Retain(f); 166 public Unit ShrinkTo(uint minCapacity) => _base.ShrinkTo(minCapacity); 167 public Unit ShrinkToFit() => _base.ShrinkToFit(); 168 public readonly SymmetricDifference<TKey, THasher, TBuildHasher> SymmetricDifference(in HashSet<TKey, THasher, TBuildHasher> other) => new(Difference(in other).Chain<Difference<TKey, THasher, TBuildHasher>, TKey, Difference<TKey, THasher, TBuildHasher>>(other.Difference(in this))); 169 public Maybe<TKey> Take(in TKey k) => _base.Take(in k); 170 public override readonly string ToString() => string.Empty; 171 readonly Result<HashSet<TKey, THasher, TBuildHasher>, Bottom> ITryInto<HashSet<TKey, THasher, TBuildHasher>, Bottom>.TryInto() => new(this); 172 public readonly Union<TKey, THasher, TBuildHasher> Union(in HashSet<TKey, THasher, TBuildHasher> other) => Len >= other.Len ? new(IntoIter().Chain<IntoIter<TKey>, TKey, Difference<TKey, THasher, TBuildHasher>>(other.Difference(in this))) : new(other.IntoIter().Chain<IntoIter<TKey>, TKey, Difference<TKey, THasher, TBuildHasher>>(Difference(in other))); 173 #endregion 174 175 #region Operators 176 public static bool operator !=(HashSet<TKey, THasher, TBuildHasher> val0, HashSet<TKey, THasher, TBuildHasher> val1) { 177 178 Maybe<TKey> v; 179 Maybe<TKey> v2; 180 var iter = val0.IntoIter(); 181 var iter2 = val1.IntoIter(); 182 bool ne; 183 184 while ((v = iter.Next()).IsSome) { 185 v2 = iter2.Next(); 186 187 if (v2.IsNone) { 188 return true; 189 } else { 190 ne = v._some != v2._some; 191 192 if (ne) { 193 return true; 194 } 195 } 196 } 197 return iter2.Next().IsSome; 198 } 199 public static bool operator ==(HashSet<TKey, THasher, TBuildHasher> val0, HashSet<TKey, THasher, TBuildHasher> val1) { 200 201 Maybe<TKey> v; 202 Maybe<TKey> v2; 203 var iter = val0.IntoIter(); 204 var iter2 = val1.IntoIter(); 205 206 while ((v = iter.Next()).IsSome) { 207 v2 = iter2.Next(); 208 if (v2.IsNone || !(v._some == v2._some)) { return false; } 209 } 210 return iter2.Next().IsNone; 211 } 212 #endregion 213 214 #region Types 215 #endregion 216 } 217 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 218 public struct Intersection<TKey, THasher, TBuildHasher>: IInto<Intersection<TKey, THasher, TBuildHasher>>, IFusedIterator<TKey> where TKey: notnull, IEq<TKey>, IHashable where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher> { 219 220 #region Type-level Constructors 221 #endregion 222 223 #region Instance Constructors 224 public Intersection() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 225 internal Intersection(IntoIter<TKey> iter, HashSet<TKey, THasher, TBuildHasher> other) => (_iter, _other) = (iter, other); 226 #endregion 227 228 #region Type-level Fields 229 #endregion 230 231 #region Instance Fields 232 IntoIter<TKey> _iter; 233 HashSet<TKey, THasher, TBuildHasher> _other; 234 #endregion 235 236 #region Type-level Properties 237 #endregion 238 239 #region Instance Properties 240 #endregion 241 242 #region Type-level Functions 243 #endregion 244 245 #region Instance Functions 246 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<TKey>.AdvanceByDefault(ref this, n); 247 public ulong Count() => IIterator<TKey>.CountDefault(ref this); 248 public TInit Fold<TInit>(TInit init, Fn<TInit, TKey, TInit> f) where TInit: notnull => IIterator<TKey>.FoldDefault(ref this, init, f); 249 public override readonly bool Equals(object? _) => false; 250 public override readonly int GetHashCode() => 0; 251 public readonly Intersection<TKey, THasher, TBuildHasher> Into() => this; 252 public Maybe<TKey> Last() => IIterator<TKey>.LastDefault(ref this); 253 public Maybe<TKey> Next() { 254 255 while (true) { 256 var elt = _iter.Next(); 257 258 if (elt.IsSome) { 259 260 if (_other.Contains(elt._some)) { 261 return new(elt._some); 262 } 263 } else { 264 return Maybe<TKey>.None(); 265 } 266 } 267 } 268 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => new(ulong.MinValue, _iter.SizeHint().Item1); 269 public override readonly string ToString() => string.Empty; 270 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); 271 readonly Result<Intersection<TKey, THasher, TBuildHasher>, Bottom> ITryInto<Intersection<TKey, THasher, TBuildHasher>, Bottom>.TryInto() => new(this); 272 #endregion 273 274 #region Operators 275 #endregion 276 277 #region Types 278 #endregion 279 } 280 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 281 public struct IntoIter<TKey>: IInto<IntoIter<TKey>>, IExactSizeIterator<TKey>, IFusedIterator<TKey> where TKey: notnull { 282 283 #region Type-level Constructors 284 #endregion 285 286 #region Instance Constructors 287 public IntoIter() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 288 internal IntoIter(@base::IntoIter<TKey> @base) => _base = @base; 289 #endregion 290 291 #region Type-level Fields 292 #endregion 293 294 #region Instance Fields 295 @base::IntoIter<TKey> _base; 296 #endregion 297 298 #region Type-level Properties 299 #endregion 300 301 #region Instance Properties 302 #endregion 303 304 #region Type-level Functions 305 #endregion 306 307 #region Instance Functions 308 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<TKey>.AdvanceByDefault(ref this, n); 309 public ulong Count() => IIterator<TKey>.CountDefault(ref this); 310 public TInit Fold<TInit>(TInit init, Fn<TInit, TKey, TInit> f) where TInit: notnull => IIterator<TKey>.FoldDefault(ref this, init, f); 311 public override readonly bool Equals(object? _) => false; 312 public override readonly int GetHashCode() => 0; 313 public readonly IntoIter<TKey> Into() => this; 314 public readonly bool IsEmpty() => _base.IsEmpty(); 315 public Maybe<TKey> Last() => IIterator<TKey>.LastDefault(ref this); 316 public readonly ulong Len() => _base.Len(); 317 [MethodImpl(MethodImplOptions.AggressiveInlining)] 318 public Maybe<TKey> Next() => _base.Next(); 319 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => _base.SizeHint(); 320 public override readonly string ToString() => string.Empty; 321 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); 322 readonly Result<IntoIter<TKey>, Bottom> ITryInto<IntoIter<TKey>, Bottom>.TryInto() => new(this); 323 #endregion 324 325 #region Operators 326 #endregion 327 328 #region Types 329 #endregion 330 } 331 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 332 public struct SymmetricDifference<TKey, THasher, TBuildHasher>: IInto<SymmetricDifference<TKey, THasher, TBuildHasher>>, IFusedIterator<TKey> where TKey: notnull, IEq<TKey>, IHashable where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher> { 333 334 #region Type-level Constructors 335 #endregion 336 337 #region Instance Constructors 338 public SymmetricDifference() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 339 internal SymmetricDifference(Chain<TKey, Difference<TKey, THasher, TBuildHasher>, Difference<TKey, THasher, TBuildHasher>> iter) => _iter = iter; 340 #endregion 341 342 #region Type-level Fields 343 #endregion 344 345 #region Instance Fields 346 Chain<TKey, Difference<TKey, THasher, TBuildHasher>, Difference<TKey, THasher, TBuildHasher>> _iter; 347 #endregion 348 349 #region Type-level Properties 350 #endregion 351 352 #region Instance Properties 353 #endregion 354 355 #region Type-level Functions 356 #endregion 357 358 #region Instance Functions 359 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<TKey>.AdvanceByDefault(ref this, n); 360 public ulong Count() => IIterator<TKey>.CountDefault(ref this); 361 public TInit Fold<TInit>(TInit init, Fn<TInit, TKey, TInit> f) where TInit: notnull => IIterator<TKey>.FoldDefault(ref this, init, f); 362 public override readonly bool Equals(object? _) => false; 363 public override readonly int GetHashCode() => 0; 364 public readonly SymmetricDifference<TKey, THasher, TBuildHasher> Into() => this; 365 public Maybe<TKey> Last() => IIterator<TKey>.LastDefault(ref this); 366 public Maybe<TKey> Next() => _iter.Next(); 367 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => new(ulong.MinValue, _iter.SizeHint().Item1); 368 public override readonly string ToString() => string.Empty; 369 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); 370 readonly Result<SymmetricDifference<TKey, THasher, TBuildHasher>, Bottom> ITryInto<SymmetricDifference<TKey, THasher, TBuildHasher>, Bottom>.TryInto() => new(this); 371 #endregion 372 373 #region Operators 374 #endregion 375 376 #region Types 377 #endregion 378 } 379 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 380 public struct Union<TKey, THasher, TBuildHasher>: IInto<Union<TKey, THasher, TBuildHasher>>, IFusedIterator<TKey> where TKey: notnull, IEq<TKey>, IHashable where THasher: notnull, IHasher where TBuildHasher: notnull, IBuildHasher<THasher> { 381 382 #region Type-level Constructors 383 #endregion 384 385 #region Instance Constructors 386 public Union() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 387 internal Union(Chain<TKey, IntoIter<TKey>, Difference<TKey, THasher, TBuildHasher>> iter) => _iter = iter; 388 #endregion 389 390 #region Type-level Fields 391 #endregion 392 393 #region Instance Fields 394 Chain<TKey, IntoIter<TKey>, Difference<TKey, THasher, TBuildHasher>> _iter; 395 #endregion 396 397 #region Type-level Properties 398 #endregion 399 400 #region Instance Properties 401 #endregion 402 403 #region Type-level Functions 404 #endregion 405 406 #region Instance Functions 407 public Result<Unit, ulong> AdvanceBy(ulong n) => IIterator<TKey>.AdvanceByDefault(ref this, n); 408 public ulong Count() => IIterator<TKey>.CountDefault(ref this); 409 public TInit Fold<TInit>(TInit init, Fn<TInit, TKey, TInit> f) where TInit: notnull => IIterator<TKey>.FoldDefault(ref this, init, f); 410 public override readonly bool Equals(object? _) => false; 411 public override readonly int GetHashCode() => 0; 412 public readonly Union<TKey, THasher, TBuildHasher> Into() => this; 413 public Maybe<TKey> Last() => IIterator<TKey>.LastDefault(ref this); 414 public Maybe<TKey> Next() => _iter.Next(); 415 public readonly Prod<ulong, Maybe<ulong>> SizeHint() => new(ulong.MinValue, _iter.SizeHint().Item1); 416 public override readonly string ToString() => string.Empty; 417 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); 418 readonly Result<Union<TKey, THasher, TBuildHasher>, Bottom> ITryInto<Union<TKey, THasher, TBuildHasher>, Bottom>.TryInto() => new(this); 419 #endregion 420 421 #region Operators 422 #endregion 423 424 #region Types 425 #endregion 426 } 427 public static class Functions { 428 429 #region Type-level Constructors 430 #endregion 431 432 #region Instance Constructors 433 #endregion 434 435 #region Type-level Fields 436 #endregion 437 438 #region Instance Fields 439 #endregion 440 441 #region Type-level Properties 442 #endregion 443 444 #region Instance Properties 445 #endregion 446 447 #region Type-level Functions 448 public 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(@base.Functions.Clone(in self._base)); 449 #endregion 450 451 #region Instance Functions 452 #endregion 453 454 #region Operators 455 #endregion 456 457 #region Types 458 #endregion 459 } 460 #endregion 461 462 #region Namespaces 463 #endregion 464 } 465 #endregion