< Summary

Class:GDX.Collections.Generic.IntKeyDictionary[TValue]
Assembly:GDX
File(s):D:/BuildAgent/work/GDX-Documentation/Projects/GDX_Development/Packages/com.dotbunny.gdx/GDX/Collections/Generic/IntKeyDictionary.cs
Covered lines:350
Uncovered lines:27
Coverable lines:377
Total lines:649
Line coverage:92.8% (350 of 377)
Covered branches:0
Total branches:0
Covered methods:19
Total methods:19
Method coverage:100% (19 of 19)

Coverage History

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity NPath complexity Sequence coverage
IntKeyDictionary(...)0%330100%
AddWithExpandCheck(...)0%220100%
AddWithUniqueCheck(...)0%33095.65%
AddSafe(...)0%4.284074.07%
AddUnchecked(...)0%110100%
ContainsKey(...)0%3.033085.71%
ExpandWhenFull()0%440100%
Reserve(...)0%6.146084.21%
IndexOf(...)0%330100%
TryModifyValue(...)0%33093.33%
TryRemove(...)0%550100%
TryRemoveNoValueClear(...)0%5.135082.86%
TryGetValue(...)0%33093.75%
MoveNext(...)0%440100%
MoveNext(...)0%330100%
MoveNext(...)0%330100%
Clear()0%330100%

File(s)

D:/BuildAgent/work/GDX-Documentation/Projects/GDX_Development/Packages/com.dotbunny.gdx/GDX/Collections/Generic/IntKeyDictionary.cs

#LineLine coverage
 1using System;
 2
 3namespace GDX.Collections.Generic
 4{
 5    /// <summary>
 6    ///     An optimized <see cref="System.Collections.Generic.Dictionary{T,T}" />-like data structure with a
 7    ///     <see cref="string"/> key requirement.
 8    /// </summary>
 9    [Serializable]
 10    public struct IntKeyDictionary<TValue>
 11    {
 12        public int[] Buckets;
 13        public IntKeyEntry<TValue>[] Entries;
 14        public int FreeListHead;
 15        public int Count;
 16
 17        /// <summary>
 18        /// Initializes the dictionary with at least <paramref name="minCapacity"/> capacity.
 19        /// </summary>
 20        /// <param name="minCapacity">The minimal initial capacity to reserve.</param>
 21        public IntKeyDictionary(int minCapacity)
 3522        {
 3523            int primeCapacity = DictionaryPrimes.GetPrime(minCapacity);
 24
 3525            Buckets = new int[primeCapacity];
 136826            for (int i = 0; i < primeCapacity; i++)
 64927            {
 64928                Buckets[i] = int.MaxValue;
 64929            }
 30
 3531            Entries = new IntKeyEntry<TValue>[primeCapacity];
 32
 136833            for (int i = 0; i < primeCapacity; i++)
 64934            {
 64935                Entries[i].Next = (1 << 31) | (i + 1);
 64936            }
 37
 3538            Count = 0;
 3539            FreeListHead = 0;
 3540        }
 41
 42        /// <summary>
 43        /// Adds the key value pair to the dictionary, expanding if necessary but not checking for duplicate entries.
 44        /// </summary>
 45        /// <param name="key">The key to add.</param>
 46        /// <param name="value">The value to add.</param>
 47        public void AddWithExpandCheck(int key, TValue value)
 5448        {
 5449            int freeIndex = FreeListHead;
 50
 5451            if (freeIndex >= Buckets.Length)
 252            {
 253                ExpandWhenFull();
 254            }
 55
 5456            int hashCode = key & 0x7FFFFFFF;
 5457            int hashIndex = hashCode % Buckets.Length;
 5458            int indexAtBucket = Buckets[hashIndex];
 5459            ref IntKeyEntry<TValue> entry = ref Entries[freeIndex];
 60
 5461            FreeListHead = entry.Next & 0x7FFFFFFF;
 5462            entry.Next = indexAtBucket;
 5463            entry.Key = key;
 5464            entry.Value = value;
 5465            Buckets[hashIndex] = freeIndex;
 66
 5467            ++Count;
 5468        }
 69
 70        /// <summary>
 71        /// Adds the key value pair to the dictionary, checking for duplicates but not expanding if necessary.
 72        /// </summary>
 73        /// <param name="key">The key to add.</param>
 74        /// <param name="value">The value to add.</param>
 75        /// <returns>True if the entry was successfully created.</returns>
 76        public bool AddWithUniqueCheck(int key, TValue value)
 377        {
 378            int freeIndex = FreeListHead;
 379            int hashCode = key & 0x7FFFFFFF;
 380            int hashIndex = hashCode % Buckets.Length;
 381            int indexAtBucket = Buckets[hashIndex];
 82
 383            int nextKeyIndex = indexAtBucket;
 84
 385            while (nextKeyIndex != int.MaxValue)
 186            {
 187                ref IntKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 188                nextKeyIndex = currEntry.Next;
 189                if (currEntry.Key == key)
 190                {
 191                    return false;
 92                }
 093            }
 94
 295            ref IntKeyEntry<TValue> entry = ref Entries[freeIndex];
 96
 297            FreeListHead = entry.Next & 0x7FFFFFFF;
 298            entry.Next = indexAtBucket;
 299            entry.Key = key;
 2100            entry.Value = value;
 2101            Buckets[hashIndex] = freeIndex;
 102
 2103            ++Count;
 2104            return true;
 3105        }
 106
 107        /// <summary>
 108        /// Adds the key value pair to the dictionary, checking for duplicate entries and expanding if necessary.
 109        /// </summary>
 110        /// <param name="key">The key to add.</param>
 111        /// <param name="value">The value to add.</param>
 112        /// <returns>True if the entry was successfully created.</returns>
 113        public bool AddSafe(int key, TValue value)
 61114        {
 61115            int freeIndex = FreeListHead;
 116
 61117            if (freeIndex >= Buckets.Length)
 3118            {
 3119                ExpandWhenFull();
 3120            }
 121
 61122            int hashCode = key & 0x7FFFFFFF;
 61123            int hashIndex = hashCode % Buckets.Length;
 61124            int indexAtBucket = Buckets[hashIndex];
 125
 61126            int nextKeyIndex = indexAtBucket;
 127
 61128            while (nextKeyIndex != int.MaxValue)
 0129            {
 0130                IntKeyEntry<TValue> currEntry = Entries[nextKeyIndex];
 0131                nextKeyIndex = currEntry.Next;
 0132                if (currEntry.Key == key)
 0133                {
 0134                    return false;
 135                }
 0136            }
 137
 61138            ref IntKeyEntry<TValue> entry = ref Entries[freeIndex];
 139
 61140            FreeListHead = entry.Next & 0x7FFFFFFF;
 61141            entry.Next = indexAtBucket;
 61142            entry.Key = key;
 61143            entry.Value = value;
 61144            Buckets[hashIndex] = freeIndex;
 145
 61146            ++Count;
 61147            return true;
 61148        }
 149
 150        /// <summary>
 151        /// Adds the key value pair to the dictionary, without checking for available capacity or duplicate entries.
 152        /// </summary>
 153        /// <param name="key">The key to add.</param>
 154        /// <param name="value">The value to add.</param>
 155        public void AddUnchecked(int key, TValue value)
 16156        {
 16157            int dataIndex = FreeListHead;
 16158            int hashCode = key & 0x7FFFFFFF;
 16159            int bucketIndex = hashCode % Buckets.Length;
 16160            int initialBucketValue = Buckets[bucketIndex];
 161
 16162            ref IntKeyEntry<TValue> entry = ref Entries[dataIndex];
 163
 16164            FreeListHead = entry.Next & 0x7FFFFFFF;
 16165            entry.Next = initialBucketValue;
 16166            entry.Key = key;
 16167            entry.Value = value;
 16168            Buckets[bucketIndex] = dataIndex;
 16169        }
 170
 171
 172        /// <summary>
 173        /// Checks if the dictionary contains the given key.
 174        /// </summary>
 175        /// <param name="key">The key to check for.</param>
 176        /// <returns>True if the dictionary contains the key.</returns>
 177        public bool ContainsKey(int key)
 19178        {
 19179            int hashCode = key & 0x7FFFFFFF;
 19180            int bucketIndex = hashCode % Buckets.Length;
 19181            int nextKeyIndex = Buckets[bucketIndex];
 182
 19183            while (nextKeyIndex != int.MaxValue)
 18184            {
 18185                ref IntKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 186
 18187                if (currEntry.Key == key)
 18188                {
 18189                    return true;
 190                }
 191
 0192                nextKeyIndex = currEntry.Next;
 0193            }
 194
 1195            return false;
 19196        }
 197
 198        /// <summary>
 199        /// Resizes the dictionary with the assumption that it is full. Do not use otherwise.
 200        /// </summary>
 201        public void ExpandWhenFull()
 9202        {
 9203            int oldCapacity = Buckets.Length;
 9204            int nextPrimeCapacity = DictionaryPrimes.GetNextSize(oldCapacity);
 205
 9206            int[] newBuckets = new int[nextPrimeCapacity];
 684207            for (int i = 0; i < nextPrimeCapacity; i++)
 333208            {
 333209                newBuckets[i] = int.MaxValue;
 333210            }
 211
 9212            IntKeyEntry<TValue>[] newEntries = new IntKeyEntry<TValue>[nextPrimeCapacity];
 9213            Array.Copy(Entries, 0, newEntries, 0, oldCapacity);
 214
 324215            for (int i = 0; i < oldCapacity; i++)
 153216            {
 153217                ref IntKeyEntry<TValue> entry = ref newEntries[i];
 218
 153219                int newBucketIndex = (entry.Key & 0x7FFFFFFF) % nextPrimeCapacity;
 220
 153221                int indexAtBucket = newBuckets[newBucketIndex];
 153222                entry.Next = indexAtBucket;
 153223                newBuckets[newBucketIndex] = i;
 153224            }
 225
 378226            for (int i = oldCapacity; i < nextPrimeCapacity; i++)
 180227            {
 180228                newEntries[i].Next = (1 << 31) | (i + 1);
 180229            }
 230
 9231            Buckets = newBuckets;
 9232            Entries = newEntries;
 9233        }
 234
 235        /// <summary>
 236        /// Expands the dictionary if it does not have enough empty space for <paramref name="capacityToReserve"/>.
 237        /// </summary>
 238        /// <param name="capacityToReserve"></param>
 239        public void Reserve(int capacityToReserve)
 1240        {
 1241            int oldCapacity = Entries.Length;
 1242            if (Count + capacityToReserve > oldCapacity)
 1243            {
 1244                int minCapacity = Count + capacityToReserve;
 1245                int nextPrimeCapacity = DictionaryPrimes.GetNextSize(minCapacity);
 246
 1247                int[] newBuckets = new int[nextPrimeCapacity];
 328248                for (int i = 0; i < nextPrimeCapacity; i++)
 163249                {
 163250                    newBuckets[i] = int.MaxValue;
 163251                }
 252
 1253                IntKeyEntry<TValue>[] newEntries = new IntKeyEntry<TValue>[nextPrimeCapacity];
 1254                Array.Copy(Entries, 0, newEntries, 0, oldCapacity);
 255
 36256                for (int i = 0; i < oldCapacity; i++)
 17257                {
 17258                    ref IntKeyEntry<TValue> entry = ref newEntries[i];
 259
 17260                    if (entry.Next >= 0)
 0261                    {
 0262                        int newBucketIndex = (entry.Key & 0x7FFFFFFF) % nextPrimeCapacity;
 263
 0264                        int indexAtBucket = newBuckets[newBucketIndex];
 0265                        entry.Next = indexAtBucket;
 0266                        newBuckets[newBucketIndex] = i;
 0267                    }
 17268                }
 269
 294270                for (int i = oldCapacity; i < nextPrimeCapacity; i++)
 146271                {
 146272                    newEntries[i].Next = (1 << 31) | (i + 1);
 146273                }
 274
 1275                Buckets = newBuckets;
 1276                Entries = newEntries;
 1277            }
 1278        }
 279
 280        /// <summary>
 281        /// Finds the index of the entry corresponding to a key.
 282        /// </summary>
 283        /// <param name="key">The key to find the index of.</param>
 284        /// <returns>The index of the entry, or -1 if the entry does not exist.</returns>
 285        public int IndexOf(int key)
 63286        {
 63287            int hashCode = key & 0x7FFFFFFF;
 63288            int bucketIndex = hashCode % Buckets.Length;
 63289            int nextKeyIndex = Buckets[bucketIndex];
 290
 65291            while (nextKeyIndex != int.MaxValue)
 64292            {
 64293                ref IntKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 294
 64295                if (currEntry.Key == key)
 62296                {
 62297                    return nextKeyIndex;
 298                }
 299
 2300                nextKeyIndex = currEntry.Next;
 2301            }
 302
 1303            return -1;
 63304        }
 305
 306        /// <summary>
 307        /// Replaces the value of the entry if the entry exists.
 308        /// </summary>
 309        /// <param name="key">The key of the entry to modify.</param>
 310        /// <param name="value">The new value of the entry.</param>
 311        /// <returns>True if the entry was found.</returns>
 312        public bool TryModifyValue(int key, TValue value)
 2313        {
 2314            int hashCode = key & 0x7FFFFFFF;
 2315            int bucketIndex = hashCode % Buckets.Length;
 2316            int nextKeyIndex = Buckets[bucketIndex];
 317
 2318            while (nextKeyIndex != int.MaxValue)
 1319            {
 1320                ref IntKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 1321                nextKeyIndex = currEntry.Next;
 322
 1323                if (currEntry.Key == key)
 1324                {
 1325                    currEntry.Value = value;
 1326                    return true;
 327                }
 0328            }
 329
 1330            return false;
 2331        }
 332
 333        /// <summary>
 334        /// Removes the entry if it exists.
 335        /// </summary>
 336        /// <param name="key">The key to remove.</param>
 337        /// <returns>True if the entry was found.</returns>
 338        public bool TryRemove(int key)
 5339        {
 5340            int hashCode = key & 0x7FFFFFFF;
 5341            int bucketIndex = hashCode % Buckets.Length;
 5342            int indexAtBucket = Buckets[bucketIndex];
 5343            int indexOfKey = indexAtBucket;
 5344            int previousIndex = indexAtBucket;
 345
 5346            bool foundIndex = false;
 347
 6348            while (indexOfKey != int.MaxValue)
 5349            {
 5350                ref IntKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 351
 5352                if (currEntry.Key == key)
 4353                {
 4354                    foundIndex = true;
 4355                    break;
 356                }
 357
 1358                previousIndex = indexOfKey;
 1359                indexOfKey = currEntry.Next;
 1360            }
 361
 5362            if (foundIndex)
 4363            {
 4364                ref IntKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 4365                int nextUsedIndex = currEntry.Next;
 4366                int nextFreeIndex = FreeListHead;
 367
 4368                currEntry.Value = default;
 4369                currEntry.Next = nextFreeIndex | (1 << 31);
 4370                Entries[indexOfKey] = currEntry;
 4371                FreeListHead = indexOfKey;
 372
 4373                if (indexOfKey == indexAtBucket)
 3374                {
 3375                    Buckets[bucketIndex] = nextUsedIndex;
 3376                }
 377                else
 1378                {
 1379                    Entries[previousIndex].Next = nextUsedIndex;
 1380                }
 381
 4382                return true;
 383            }
 384
 1385            return false;
 5386        }
 387
 388        /// <summary>
 389        /// Removes the entry if it exists, but does not remove the value of the key value pair.
 390        /// </summary>
 391        /// <param name="key">The key to remove.</param>
 392        /// <returns>True if the entry was found.</returns>
 393        public bool TryRemoveNoValueClear(int key)
 3394        {
 3395            int hashCode = key & 0x7FFFFFFF;
 3396            int bucketIndex = hashCode % Buckets.Length;
 3397            int indexAtBucket = Buckets[bucketIndex];
 3398            int indexOfKey = indexAtBucket;
 3399            int previousIndex = indexAtBucket;
 400
 3401            bool foundIndex = false;
 402
 3403            while (indexOfKey != int.MaxValue)
 2404            {
 2405                ref IntKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 406
 2407                if (currEntry.Key == key)
 2408                {
 2409                    foundIndex = true;
 2410                    break;
 411                }
 412
 0413                previousIndex = indexOfKey;
 0414                indexOfKey = currEntry.Next;
 0415            }
 416
 3417            if (foundIndex)
 2418            {
 2419                ref IntKeyEntry<TValue> currEntry = ref Entries[indexOfKey];
 2420                int nextUsedIndex = currEntry.Next;
 2421                int nextFreeIndex = FreeListHead;
 422
 2423                currEntry.Next = nextFreeIndex | (1 << 31);
 2424                Entries[indexOfKey] = currEntry;
 2425                FreeListHead = indexOfKey;
 426
 2427                if (indexOfKey == indexAtBucket)
 2428                {
 2429                    Buckets[bucketIndex] = nextUsedIndex;
 2430                }
 431                else
 0432                {
 0433                    Entries[previousIndex].Next = nextUsedIndex;
 0434                }
 435
 2436                return true;
 437            }
 438
 1439            return false;
 3440        }
 441
 442        /// <summary>
 443        /// Attempts to get the value for the given key; returns true if key was found, false otherwise.
 444        /// </summary>
 445        /// <param name="key">The key to retrieve.</param>
 446        /// <param name="value">The value of the entry found.</param>
 447        /// <returns>True if the entry was found; false otherwise.</returns>
 448        public bool TryGetValue(int key, out TValue value)
 2449        {
 2450            int hashCode = key & 0x7FFFFFFF;
 2451            int bucketIndex = hashCode % Buckets.Length;
 2452            int nextKeyIndex = Buckets[bucketIndex];
 453
 2454            while (nextKeyIndex != int.MaxValue)
 1455            {
 1456                ref IntKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 1457                nextKeyIndex = currEntry.Next;
 458
 1459                if (currEntry.Key == key)
 1460                {
 1461                    value = currEntry.Value;
 1462                    return true;
 463                }
 0464            }
 465
 1466            value = default;
 1467            return false;
 2468        }
 469
 470        /// <summary>
 471        ///     Directly access a value by key.
 472        /// </summary>
 473        /// <param name="key">The target key to look for a value identified by.</param>
 474        /// <exception cref="ArgumentNullException">Thrown when a null <paramref name="key"/> is provided to lookup.</ex
 475        /// <exception cref="System.Collections.Generic.KeyNotFoundException">Thrown when the <paramref name="key"/> is 
 476        public TValue this[int key]
 477        {
 478            get
 6479            {
 6480                int hashCode = key & 0x7FFFFFFF;
 6481                int bucketIndex = hashCode % Buckets.Length;
 6482                int nextKeyIndex = Buckets[bucketIndex];
 483
 484
 6485                while (nextKeyIndex != int.MaxValue)
 6486                {
 6487                    ref IntKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 6488                    nextKeyIndex = currEntry.Next;
 489
 6490                    if (currEntry.Key == key)
 6491                    {
 6492                        return currEntry.Value;
 493                    }
 0494                }
 495
 0496                throw new System.Collections.Generic.KeyNotFoundException();
 6497            }
 498
 499            set
 56500            {
 56501                int freeIndex = FreeListHead;
 502
 56503                if (freeIndex >= Buckets.Length)
 3504                {
 3505                    ExpandWhenFull();
 3506                }
 507
 56508                int hashCode = key & 0x7FFFFFFF;
 56509                int bucketIndex = hashCode % Buckets.Length;
 56510                int indexAtBucket = Buckets[bucketIndex];
 511
 56512                int nextKeyIndex = indexAtBucket;
 513
 56514                while (nextKeyIndex != int.MaxValue)
 1515                {
 1516                    ref IntKeyEntry<TValue> currEntry = ref Entries[nextKeyIndex];
 1517                    nextKeyIndex = currEntry.Next;
 1518                    if (currEntry.Key == key)
 1519                    {
 1520                        currEntry.Value = value;
 1521                        return;
 522                    }
 0523                }
 524
 55525                ref IntKeyEntry<TValue> entry = ref Entries[freeIndex];
 526
 55527                FreeListHead = entry.Next & 0x7FFFFFFF;
 55528                entry.Next = indexAtBucket;
 55529                entry.Key = key;
 55530                entry.Value = value;
 55531                Buckets[bucketIndex] = freeIndex;
 532
 55533                ++Count;
 56534            }
 535        }
 536
 537        /// <summary>
 538        /// Iterates the dictionary.
 539        /// </summary>
 540        /// <param name="iteratedIndexCount">The number of indices iterated so far - pass in 0 at the start of iteration
 541        /// <param name="iteratorVersion">The version when iteration started.</param>
 542        /// <param name="dictionaryVersion">The current version of the dictionary - update this on add, remove, or clear
 543        /// <param name="entry">The entry returned by the iterator</param>
 544        /// <returns>Whether the iterator found an entry, finished iteration, or could not continue due to an invalid ve
 545        public IteratorState MoveNext(ref int iteratedIndexCount, int iteratorVersion, in int dictionaryVersion, out Int
 5546        {
 5547            entry = default;
 548
 5549            if (iteratorVersion != dictionaryVersion)
 1550            {
 1551                return IteratorState.InvalidVersion;
 552            }
 553
 19554            while (iteratedIndexCount < Entries.Length)
 18555            {
 18556                ref IntKeyEntry<TValue> keyEntry = ref Entries[iteratedIndexCount];
 18557                iteratedIndexCount++;
 558
 18559                if (keyEntry.Next >= 0)
 3560                {
 3561                    entry = keyEntry;
 3562                    return IteratorState.FoundEntry;
 563                }
 15564            }
 565
 1566            return IteratorState.Finished;
 5567        }
 568
 569        /// <summary>
 570        /// Iterates the dictionary.
 571        /// NOTE: if you suspect the dictionary might be modified while iterating, this will not catch the error -- use 
 572        /// </summary>
 573        /// <param name="iteratedIndexCount">The number of indices iterated so far - pass in 0 at the start of iteration
 574        /// <param name="entry">The entry returned by the iterator</param>
 575        /// <returns>Whether or not the iterator found an entry</returns>
 576        public bool MoveNext(ref int iteratedIndexCount, out IntKeyEntry<TValue> entry)
 3577        {
 3578            entry = default;
 579
 18580            while (iteratedIndexCount < Entries.Length)
 17581            {
 17582                ref IntKeyEntry<TValue> keyEntry = ref Entries[iteratedIndexCount];
 17583                iteratedIndexCount++;
 584
 17585                if (keyEntry.Next >= 0)
 2586                {
 2587                    entry = keyEntry;
 588
 2589                    return true;
 590                }
 15591            }
 592
 1593            return false;
 3594        }
 595
 596        /// <summary>
 597        /// Iterates the dictionary.
 598        /// NOTE: if you suspect the dictionary might be modified while iterating, this will not catch the error -- use 
 599        /// </summary>
 600        /// <param name="iteratedIndexCount">The number of indices iterated so far - pass in 0 at the start of iteration
 601        /// <returns>Whether or not the iterator found an entry</returns>
 602        public bool MoveNext(ref int iteratedIndexCount)
 3603        {
 18604            while (iteratedIndexCount < Entries.Length)
 17605            {
 17606                ref IntKeyEntry<TValue> keyEntry = ref Entries[iteratedIndexCount];
 17607                iteratedIndexCount++;
 608
 17609                if (keyEntry.Next >= 0)
 2610                {
 2611                    return true;
 612                }
 15613            }
 614
 1615            return false;
 3616        }
 617
 618        /// <summary>
 619        /// Clears the dictionary.
 620        /// </summary>
 621        public void Clear()
 1622        {
 1623            int length = Entries.Length;
 624
 76625            for (int i = 0; i < length; i++)
 37626            {
 37627                Buckets[i] = int.MaxValue;
 37628            }
 629
 76630            for (int i = 0; i < length; i++)
 37631            {
 37632                ref IntKeyEntry<TValue> entryAt = ref Entries[i];
 37633                entryAt.Next = (1 << 31) | (i + 1);
 37634                entryAt.Value = default;
 37635            }
 636
 1637            FreeListHead = 0;
 1638            Count = 0;
 1639        }
 640    }
 641
 642    [Serializable]
 643    public struct IntKeyEntry<T>
 644    {
 645        public int Key;
 646        public int Next;
 647        public T Value;
 648    }
 649}