src/Compilers/Core/CodeAnalysisTest/Collections/BitArrayTests.cs - main - githubmirror/roslyn

src/Compilers/Core/CodeAnalysisTest/Collections/BitArrayTests.cs
332 строки10 KB
Jared Parsons
generated move
28 сен 2020, 19:36
28 сен 2020, 19:361cca63b
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

#nullable disable

using System;
using System.Collections.Generic;
using System.Linq;
using Xunit;

namespace Microsoft.CodeAnalysis.UnitTests.Collections
{
    public class BitVectorTests
    {
        private const int seed = 128129347;
        private const int rounds = 200;
        private const int maxBits = 132;

        [Fact]
        public void UpperBitsUnset()
        {
            for (int a = 0; a < 5; a++) // number of words
            {
                for (int b = -1; b < 2; b++) // number of bits more or less than that number of words
                {
                    int n = BitVector.BitsPerWord * a + b;
                    if (n < 0) continue;
                    BitVector arr = BitVector.AllSet(n);
                    if (n > 0) Assert.True(arr[n - 1]);
                    Assert.False(arr[n]);
                }
            }
        }

        [Fact]
        public void CheckRandomData()
        {
            var r1 = new Random(seed);
            var r2 = new Random(seed);

            for (int capacity = 0; capacity < maxBits; capacity++)
                CheckRandomDataCore(r1, r2, capacity);

            for (int i = 0; i < rounds; i++)
            {
                int capacity = r1.Next(maxBits);
                Assert.Equal(r2.Next(maxBits), capacity);
                CheckRandomDataCore(r1, r2, capacity);
            }
        }

        private void CheckRandomDataCore(Random r1, Random r2, int capacity)
        {
            BitVector d = BitVector.Create(capacity);
            Assert.Equal(capacity, d.Capacity);
            for (int i1 = 0; i1 < capacity; i1++)
                d[i1] = r1.NextBool();
            Assert.Equal(capacity, d.Capacity);

            for (int i2 = 0; i2 < capacity; i2++)
                Assert.Equal(d[i2], r2.NextBool());
        }

        [Fact]
        public void CheckIntersection()
        {
            var r = new Random(seed);
            for (int capacity = 0; capacity < maxBits; capacity++)
                CheckIntersectionCore(capacity, r);
            for (int i = 0; i < rounds; i++)
            {
                CheckIntersectionCore(r.Next(maxBits), r);
            }
        }

        private void CheckIntersectionCore(int capacity, Random r)
        {
            BitVector b1 = BitVector.Empty, b2 = BitVector.Empty;
            b1.EnsureCapacity(capacity);
            b2.EnsureCapacity(capacity);
            bool[] a1 = new bool[capacity], a2 = new bool[capacity];
            for (int i = 0; i < capacity; i++)
            {
                b1[i] = a1[i] = r.NextBool();
                b2[i] = a2[i] = r.NextBool();
            }
            bool changed = b1.IntersectWith(b2);
            bool changed2 = false;
            for (int i = 0; i < capacity; i++)
            {
                bool a = a1[i];
                a1[i] &= a2[i];
                changed2 |= (a != a1[i]);
            }
            for (int i = 0; i < capacity; i++)
            {
                Assert.Equal(a1[i], b1[i]);
            }
            Assert.Equal(changed, changed2);
        }

        [Fact]
        public void CheckUnion()
        {
            var r = new Random(seed);
            for (int capacity = 0; capacity < maxBits; capacity++)
            {
                CheckUnionCore(capacity, capacity, r);
            }

            for (int i = 0; i < rounds; i++)
            {
                CheckUnionCore(r.Next(maxBits), r.Next(maxBits), r);
            }
        }

        private void CheckUnionCore(int capacity1, int capacity2, Random r)
        {
            BitVector b1 = BitVector.Empty, b2 = BitVector.Empty;
            b1.EnsureCapacity(capacity1);
            b2.EnsureCapacity(capacity2);

            var maxCapacity = Math.Max(capacity1, capacity2);
            bool[] a1 = new bool[maxCapacity],
                   a2 = new bool[maxCapacity];

            for (int i = 0; i < capacity1; i++)
            {
                b1[i] = a1[i] = r.NextBool();
            }

            for (int i = 0; i < capacity2; i++)
            {
                b2[i] = a2[i] = r.NextBool();
            }

            bool changed = b1.UnionWith(b2);
            bool changed2 = false;

            for (int i = 0; i < maxCapacity; i++)
            {
                bool a = a1[i];
                a1[i] |= a2[i];
                changed2 |= (a != a1[i]);
            }
            for (int i = 0; i < maxCapacity; i++)
            {
                Assert.Equal(a1[i], b1[i]);
            }
            Assert.Equal(changed2, changed);
        }

        [Fact]
        public void CheckTrueBits()
        {
            var r1 = new Random(seed);
            var r2 = new Random(seed);
            for (int capacity = 0; capacity < maxBits; capacity++)
            {
                CheckTrueBitsCore(capacity, r1, r2);
            }
            for (int i = 0; i < rounds; i++)
            {
                var capacity = r1.Next(maxBits);
                Assert.Equal(capacity, r2.Next(maxBits));
                CheckTrueBitsCore(capacity, r1, r2);
            }
        }

        [Fact]
        public void CheckWords()
        {
            for (int capacity = 0; capacity < maxBits; capacity++)
            {
                BitVector b = BitVector.Create(capacity);
                for (int i = 0; i < capacity; i++)
                {
                    b[i] = false;
                }

                var required = BitVector.WordsRequired(capacity);
                var count = BitVector.AllSet(capacity).Words().Count();

                Assert.Equal(required, count);
            }
        }

        [Fact]
        public void CheckIsTrue()
        {
            var r1 = new Random(seed);

            for (int capacity = 0; capacity < maxBits; capacity++)
            {
                BitVector b = BitVector.Create(capacity);
                for (int i = 0; i < capacity; i++)
                {
                    b[i] = r1.NextBool();
                }

                var index = 0;
                foreach (var word in b.Words())
                {
                    for (var i = 0; i < BitVector.BitsPerWord; i++)
                    {
                        if (index >= capacity)
                        {
                            break;
                        }

                        Assert.Equal(b[index], BitVector.IsTrue(word, index));

                        index++;
                    }
                }
            }
        }

        [Fact]
        public void CheckWordsRequired()
        {
            for (int capacity = 0; capacity < maxBits; capacity++)
            {
                var required = BitVector.WordsRequired(capacity);
                var count = BitVector.AllSet(capacity).Words().Count();

                Assert.Equal(count, required);
            }
        }

        private void CheckTrueBitsCore(int capacity, Random r1, Random r2)
        {
            BitVector b = BitVector.Create(capacity);
            for (int i = 0; i < capacity; i++)
            {
                b[i] = r1.NextBool();
            }

            IEnumerable<int> i1 = b.TrueBits();
            IEnumerator<int> i2 = i1.GetEnumerator();
            for (int i = 0; i < capacity; i++)
            {
                if (r2.NextBool())
                {
                    Assert.True(i2.MoveNext());
                    Assert.Equal(i2.Current, i);
                }
            }

            Assert.False(i2.MoveNext());
            i2.Dispose();
        }

        [Theory]
        [InlineData(0, 0)]
        [InlineData(0, 1)]
        [InlineData(0, 128)]
        [InlineData(65, 64)]
        [InlineData(65, 65)]
        [InlineData(65, 128)]
        public void IndexerGet(int capacity, int index)
        {
            var b = BitVector.Create(capacity);
            Assert.Equal(capacity, b.Capacity);

            Assert.False(b[index]);
            Assert.Equal(capacity, b.Capacity);
        }

        [Theory]
        [InlineData(0, 0)]
        [InlineData(0, 1)]
        [InlineData(0, 128)]
        [InlineData(65, 64)]
        [InlineData(65, 65)]
        [InlineData(65, 128)]
        public void IndexerSet(int capacity, int index)
        {
            var b = BitVector.Create(capacity);
            Assert.Equal(capacity, b.Capacity);
            capacity = Math.Max(capacity, index + 1);

            b[index] = true;
            Assert.True(b[index]);
            Assert.Equal(capacity, b.Capacity);

            b[index] = false;
            Assert.False(b[index]);
            Assert.Equal(capacity, b.Capacity);
        }

        [Theory]
        [InlineData(0, -1)]
        [InlineData(0, -128)]
        [InlineData(65, -1)]
        [InlineData(65, -128)]
        public void IndexerGet_OutOfRange(int capacity, int index)
        {
            var b = BitVector.Create(capacity);
            Assert.Equal(capacity, b.Capacity);

            Assert.Throws<IndexOutOfRangeException>(() => _ = b[index]);
            Assert.Equal(capacity, b.Capacity);
        }

        [Theory]
        [InlineData(0, -1)]
        [InlineData(0, -128)]
        [InlineData(65, -1)]
        [InlineData(65, -128)]
        public void IndexerSet_OutOfRange(int capacity, int index)
        {
            var b = BitVector.Create(capacity);
            Assert.Equal(capacity, b.Capacity);

            Assert.Throws<IndexOutOfRangeException>(() => b[index] = false);
            Assert.Equal(capacity, b.Capacity);

            Assert.Throws<IndexOutOfRangeException>(() => b[index] = true);
            Assert.Equal(capacity, b.Capacity);
        }
    }

    internal static class RandomExtensions
    {
        public static bool NextBool(this Random self)
        {
            return self.Next(2) == 0;
        }
    }
}