File: Collections\ImmutableListTestBase.cs
Web Access
Project: src\src\Compilers\Core\CodeAnalysisTest\Microsoft.CodeAnalysis.UnitTests.csproj (Microsoft.CodeAnalysis.UnitTests)
// 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.
 
// NOTE: This code is derived from an implementation originally in dotnet/runtime:
// https://raw.githubusercontent.com/dotnet/runtime/v6.0.0-preview.5.21301.5/src/libraries/System.Collections.Immutable/tests/ImmutableListTestBase.cs
//
// See the commentary in https://github.com/dotnet/roslyn/pull/50156 for notes on incorporating changes made to the
// reference implementation.
 
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using Microsoft.CodeAnalysis.Collections;
using Roslyn.Utilities;
using Xunit;
 
namespace Microsoft.CodeAnalysis.UnitTests.Collections
{
    public abstract class ImmutableListTestBase : SimpleElementImmutablesTestBase
    {
        protected static readonly Func<IList, object?, object> IndexOfFunc = (l, v) => l.IndexOf(v);
        protected static readonly Func<IList, object?, object> ContainsFunc = (l, v) => l.Contains(v);
        protected static readonly Func<IList, object?, object> RemoveFunc = (l, v) => { l.Remove(v); return l.Count; };
 
        internal abstract IReadOnlyList<T> GetListQuery<T>(ImmutableSegmentedList<T> list);
 
        private protected abstract ImmutableSegmentedList<TOutput> ConvertAllImpl<T, TOutput>(ImmutableSegmentedList<T> list, Converter<T, TOutput> converter);
 
        private protected abstract void ForEachImpl<T>(ImmutableSegmentedList<T> list, Action<T> action);
 
        private protected abstract ImmutableSegmentedList<T> GetRangeImpl<T>(ImmutableSegmentedList<T> list, int index, int count);
 
        private protected abstract void CopyToImpl<T>(ImmutableSegmentedList<T> list, T[] array);
 
        private protected abstract void CopyToImpl<T>(ImmutableSegmentedList<T> list, T[] array, int arrayIndex);
 
        private protected abstract void CopyToImpl<T>(ImmutableSegmentedList<T> list, int index, T[] array, int arrayIndex, int count);
 
        private protected abstract bool ExistsImpl<T>(ImmutableSegmentedList<T> list, Predicate<T> match);
 
        private protected abstract T? FindImpl<T>(ImmutableSegmentedList<T> list, Predicate<T> match);
 
        private protected abstract ImmutableSegmentedList<T> FindAllImpl<T>(ImmutableSegmentedList<T> list, Predicate<T> match);
 
        private protected abstract int FindIndexImpl<T>(ImmutableSegmentedList<T> list, Predicate<T> match);
 
        private protected abstract int FindIndexImpl<T>(ImmutableSegmentedList<T> list, int startIndex, Predicate<T> match);
 
        private protected abstract int FindIndexImpl<T>(ImmutableSegmentedList<T> list, int startIndex, int count, Predicate<T> match);
 
        private protected abstract T? FindLastImpl<T>(ImmutableSegmentedList<T> list, Predicate<T> match);
 
        private protected abstract int FindLastIndexImpl<T>(ImmutableSegmentedList<T> list, Predicate<T> match);
 
        private protected abstract int FindLastIndexImpl<T>(ImmutableSegmentedList<T> list, int startIndex, Predicate<T> match);
 
        private protected abstract int FindLastIndexImpl<T>(ImmutableSegmentedList<T> list, int startIndex, int count, Predicate<T> match);
 
        private protected abstract bool TrueForAllImpl<T>(ImmutableSegmentedList<T> list, Predicate<T> test);
 
        private protected abstract int BinarySearchImpl<T>(ImmutableSegmentedList<T> list, T item);
 
        private protected abstract int BinarySearchImpl<T>(ImmutableSegmentedList<T> list, T item, IComparer<T>? comparer);
 
        private protected abstract int BinarySearchImpl<T>(ImmutableSegmentedList<T> list, int index, int count, T item, IComparer<T>? comparer);
 
        [Fact]
        public void CopyToEmptyTest()
        {
            var array = new int[0];
            CopyToImpl(ImmutableSegmentedList<int>.Empty, array);
            CopyToImpl(ImmutableSegmentedList<int>.Empty, array, 0);
            CopyToImpl(ImmutableSegmentedList<int>.Empty, 0, array, 0, 0);
            ((ICollection)this.GetListQuery(ImmutableSegmentedList<int>.Empty)).CopyTo(array, 0);
        }
 
        [Fact]
        public void CopyToTest()
        {
            var list = ImmutableSegmentedList.Create(1, 2);
            var enumerable = (IEnumerable<int>)list;
 
            var array = new int[2];
            CopyToImpl(list, array);
            Assert.Equal(enumerable, array);
 
            array = new int[2];
            CopyToImpl(list, array, 0);
            Assert.Equal(enumerable, array);
 
            array = new int[2];
            CopyToImpl(list, 0, array, 0, list.Count);
            Assert.Equal(enumerable, array);
 
            array = new int[1]; // shorter than source length
            CopyToImpl(list, 0, array, 0, array.Length);
            Assert.Equal(enumerable.Take(array.Length), array);
 
            array = new int[3];
            CopyToImpl(list, 1, array, 2, 1);
            Assert.Equal(new[] { 0, 0, 2 }, array);
 
            array = new int[2];
            ((ICollection)GetListQuery(list)).CopyTo(array, 0);
            Assert.Equal(enumerable, array);
        }
 
        [Fact]
        public void ForEachTest()
        {
            ForEachImpl(ImmutableSegmentedList<int>.Empty, n => { throw ExceptionUtilities.Unreachable(); });
 
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(5, 3));
            var hitTest = new bool[list.Max() + 1];
            ForEachImpl(list, i =>
            {
                Assert.False(hitTest[i]);
                hitTest[i] = true;
            });
 
            for (int i = 0; i < hitTest.Length; i++)
            {
                Assert.Equal(list.Contains(i), hitTest[i]);
                Assert.Equal(((IList)list).Contains(i), hitTest[i]);
            }
        }
 
        [Fact]
        public void ExistsTest()
        {
            Assert.False(ExistsImpl(ImmutableSegmentedList<int>.Empty, n => true));
 
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(1, 5));
            Assert.True(ExistsImpl(list, n => n == 3));
            Assert.False(ExistsImpl(list, n => n == 8));
        }
 
        [Fact]
        public void FindAllTest()
        {
            Assert.True(FindAllImpl(ImmutableSegmentedList<int>.Empty, n => true).IsEmpty);
            var list = ImmutableSegmentedList<int>.Empty.AddRange(new[] { 2, 3, 4, 5, 6 });
            var actual = FindAllImpl(list, n => n % 2 == 1);
            var expected = list.ToList().FindAll(n => n % 2 == 1);
            Assert.Equal<int>(expected, actual.ToList());
        }
 
        [Fact]
        public void FindTest()
        {
            Assert.Equal(0, FindImpl(ImmutableSegmentedList<int>.Empty, n => true));
            var list = ImmutableSegmentedList<int>.Empty.AddRange(new[] { 2, 3, 4, 5, 6 });
            Assert.Equal(3, FindImpl(list, n => (n % 2) == 1));
        }
 
        [Fact]
        public void FindLastTest()
        {
            Assert.Equal(0, FindLastImpl(ImmutableSegmentedList<int>.Empty, n => { throw ExceptionUtilities.Unreachable(); }));
            var list = ImmutableSegmentedList<int>.Empty.AddRange(new[] { 2, 3, 4, 5, 6 });
            Assert.Equal(5, FindLastImpl(list, n => (n % 2) == 1));
        }
 
        [Fact]
        public void FindIndexTest()
        {
            Assert.Equal(-1, FindIndexImpl(ImmutableSegmentedList<int>.Empty, n => true));
            Assert.Equal(-1, FindIndexImpl(ImmutableSegmentedList<int>.Empty, 0, n => true));
            Assert.Equal(-1, FindIndexImpl(ImmutableSegmentedList<int>.Empty, 0, 0, n => true));
 
            // Create a list with contents: 100,101,102,103,104,100,101,102,103,104
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(100, 5).Concat(Enumerable.Range(100, 5)));
            var bclList = list.ToList();
            Assert.Equal(-1, FindIndexImpl(list, n => n == 6));
 
            for (int idx = 0; idx < list.Count; idx++)
            {
                for (int count = 0; count <= list.Count - idx; count++)
                {
                    foreach (int c in list)
                    {
                        int predicateInvocationCount = 0;
                        Predicate<int> match = n =>
                        {
                            predicateInvocationCount++;
                            return n == c;
                        };
                        int expected = bclList.FindIndex(idx, count, match);
                        int expectedInvocationCount = predicateInvocationCount;
                        predicateInvocationCount = 0;
                        int actual = FindIndexImpl(list, idx, count, match);
                        int actualInvocationCount = predicateInvocationCount;
                        Assert.Equal(expected, actual);
                        Assert.Equal(expectedInvocationCount, actualInvocationCount);
 
                        if (count == list.Count)
                        {
                            // Also test the FindIndex overload that takes no count parameter.
                            predicateInvocationCount = 0;
                            actual = FindIndexImpl(list, idx, match);
                            Assert.Equal(expected, actual);
                            Assert.Equal(expectedInvocationCount, actualInvocationCount);
 
                            if (idx == 0)
                            {
                                // Also test the FindIndex overload that takes no index parameter.
                                predicateInvocationCount = 0;
                                actual = FindIndexImpl(list, match);
                                Assert.Equal(expected, actual);
                                Assert.Equal(expectedInvocationCount, actualInvocationCount);
                            }
                        }
                    }
                }
            }
        }
 
        [Fact]
        public void FindLastIndexTest()
        {
            Assert.Equal(-1, FindLastIndexImpl(ImmutableSegmentedList<int>.Empty, n => true));
            Assert.Equal(-1, FindLastIndexImpl(ImmutableSegmentedList<int>.Empty, 0, n => true));
            Assert.Equal(-1, FindLastIndexImpl(ImmutableSegmentedList<int>.Empty, 0, 0, n => true));
 
            // Create a list with contents: 100,101,102,103,104,100,101,102,103,104
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(100, 5).Concat(Enumerable.Range(100, 5)));
            var bclList = list.ToList();
            Assert.Equal(-1, FindLastIndexImpl(list, n => n == 6));
 
            for (int idx = 0; idx < list.Count; idx++)
            {
                for (int count = 0; count <= idx + 1; count++)
                {
                    foreach (int c in list)
                    {
                        int predicateInvocationCount = 0;
                        Predicate<int> match = n =>
                        {
                            predicateInvocationCount++;
                            return n == c;
                        };
                        int expected = bclList.FindLastIndex(idx, count, match);
                        int expectedInvocationCount = predicateInvocationCount;
                        predicateInvocationCount = 0;
                        int actual = FindLastIndexImpl(list, idx, count, match);
                        int actualInvocationCount = predicateInvocationCount;
                        Assert.Equal(expected, actual);
                        Assert.Equal(expectedInvocationCount, actualInvocationCount);
 
                        if (count == list.Count)
                        {
                            // Also test the FindIndex overload that takes no count parameter.
                            predicateInvocationCount = 0;
                            actual = FindLastIndexImpl(list, idx, match);
                            Assert.Equal(expected, actual);
                            Assert.Equal(expectedInvocationCount, actualInvocationCount);
 
                            if (idx == list.Count - 1)
                            {
                                // Also test the FindIndex overload that takes no index parameter.
                                predicateInvocationCount = 0;
                                actual = FindLastIndexImpl(list, match);
                                Assert.Equal(expected, actual);
                                Assert.Equal(expectedInvocationCount, actualInvocationCount);
                            }
                        }
                    }
                }
            }
        }
 
        [Fact]
        public void IList_IndexOf_NullArgument()
        {
            this.AssertIListBaseline(IndexOfFunc, 1, null);
            this.AssertIListBaseline(IndexOfFunc, "item", null);
            this.AssertIListBaseline(IndexOfFunc, new int?(1), null);
            this.AssertIListBaseline(IndexOfFunc, new int?(), null);
        }
 
        [Fact]
        public void IList_IndexOf_ArgTypeMismatch()
        {
            this.AssertIListBaseline(IndexOfFunc, "first item", new object());
            this.AssertIListBaseline(IndexOfFunc, 1, 1.0);
 
            this.AssertIListBaseline(IndexOfFunc, new int?(1), 1);
            this.AssertIListBaseline(IndexOfFunc, new int?(1), new int?(1));
            this.AssertIListBaseline(IndexOfFunc, new int?(1), string.Empty);
        }
 
        [Fact]
        public void IList_IndexOf_EqualsOverride()
        {
            this.AssertIListBaseline(IndexOfFunc, new ProgrammaticEquals(v => v is string), "foo");
            this.AssertIListBaseline(IndexOfFunc, new ProgrammaticEquals(v => v is string), 3);
        }
 
        [Fact]
        public void IList_Contains_NullArgument()
        {
            this.AssertIListBaseline(ContainsFunc, 1, null);
            this.AssertIListBaseline(ContainsFunc, "item", null);
            this.AssertIListBaseline(ContainsFunc, new int?(1), null);
            this.AssertIListBaseline(ContainsFunc, new int?(), null);
        }
 
        [Fact]
        public void IList_Contains_ArgTypeMismatch()
        {
            this.AssertIListBaseline(ContainsFunc, "first item", new object());
            this.AssertIListBaseline(ContainsFunc, 1, 1.0);
 
            this.AssertIListBaseline(ContainsFunc, new int?(1), 1);
            this.AssertIListBaseline(ContainsFunc, new int?(1), new int?(1));
            this.AssertIListBaseline(ContainsFunc, new int?(1), string.Empty);
        }
 
        [Fact]
        public void IList_Contains_EqualsOverride()
        {
            this.AssertIListBaseline(ContainsFunc, new ProgrammaticEquals(v => v is string), "foo");
            this.AssertIListBaseline(ContainsFunc, new ProgrammaticEquals(v => v is string), 3);
        }
 
        [Fact]
        public void ConvertAllTest()
        {
            Assert.True(ConvertAllImpl<int, float>(ImmutableSegmentedList<int>.Empty, n => n).IsEmpty);
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(5, 10));
            Converter<int, double> converter = n => 2.0 * n;
            var expected = list.ToList().Select(x => converter(x)).ToList();
            var actual = ConvertAllImpl(list, converter);
            Assert.Equal<double>(expected.ToList(), actual.ToList());
        }
 
        [Fact]
        public void GetRangeTest()
        {
            Assert.True(GetRangeImpl(ImmutableSegmentedList<int>.Empty, 0, 0).IsEmpty);
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(5, 10));
            var bclList = list.ToList();
 
            for (int index = 0; index < list.Count; index++)
            {
                for (int count = 0; count < list.Count - index; count++)
                {
                    var expected = bclList.GetRange(index, count);
                    var actual = GetRangeImpl(list, index, count);
                    Assert.Equal<int>(expected.ToList(), actual.ToList());
                }
            }
        }
 
        [Fact]
        public void TrueForAllTest()
        {
            Assert.True(TrueForAllImpl(ImmutableSegmentedList<int>.Empty, n => false));
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(5, 10));
            this.TrueForAllTestHelper(list, n => n % 2 == 0);
            this.TrueForAllTestHelper(list, n => n % 2 == 1);
            this.TrueForAllTestHelper(list, n => true);
        }
 
        [Fact]
        public void RemoveAllTest()
        {
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(5, 10));
            this.RemoveAllTestHelper(list, n => false);
            this.RemoveAllTestHelper(list, n => true);
            this.RemoveAllTestHelper(list, n => n < 7);
            this.RemoveAllTestHelper(list, n => n > 7);
            this.RemoveAllTestHelper(list, n => n == 7);
        }
 
        [Fact]
        public void ReverseTest()
        {
            var list = ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(5, 10));
 
            for (int i = 0; i < list.Count; i++)
            {
                for (int j = 0; j < list.Count - i; j++)
                {
                    this.ReverseTestHelper(list, i, j);
                }
            }
        }
 
        [Fact]
        public void Sort_NullComparison_Throws()
        {
            Assert.Throws<ArgumentNullException>("comparison", () => this.SortTestHelper(ImmutableSegmentedList<int>.Empty, (Comparison<int>)null!));
        }
 
        [Fact]
        public void SortTest()
        {
            var scenarios = new[] {
                ImmutableSegmentedList<int>.Empty,
                ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(1, 50)),
                ImmutableSegmentedList<int>.Empty.AddRange(Enumerable.Range(1, 50).Reverse()),
            };
 
            foreach (var scenario in scenarios)
            {
                var expected = scenario.ToList();
                expected.Sort();
                var actual = this.SortTestHelper(scenario);
                Assert.Equal<int>(expected, actual);
 
                expected = scenario.ToList();
                Comparison<int> comparison = (x, y) => x > y ? 1 : (x < y ? -1 : 0);
                expected.Sort(comparison);
                actual = this.SortTestHelper(scenario, comparison);
                Assert.Equal<int>(expected, actual);
 
                expected = scenario.ToList();
                IComparer<int>? comparer = null;
                expected.Sort(comparer);
                actual = this.SortTestHelper(scenario, comparer);
                Assert.Equal<int>(expected, actual);
 
                expected = scenario.ToList();
                comparer = Comparer<int>.Create(comparison);
                expected.Sort(comparer);
                actual = this.SortTestHelper(scenario, comparer);
                Assert.Equal<int>(expected, actual);
 
                for (int i = 0; i < scenario.Count; i++)
                {
                    for (int j = 0; j < scenario.Count - i; j++)
                    {
                        expected = scenario.ToList();
                        comparer = null;
                        expected.Sort(i, j, comparer);
                        actual = this.SortTestHelper(scenario, i, j, comparer);
                        Assert.Equal<int>(expected, actual);
                    }
                }
            }
        }
 
        [Fact]
        public void BinarySearch()
        {
            var basis = new List<int>(Enumerable.Range(1, 50).Select(n => n * 2));
            var query = basis.ToImmutableSegmentedList();
            for (int value = basis.First() - 1; value <= basis.Last() + 1; value++)
            {
                int expected = basis.BinarySearch(value);
                int actual = BinarySearchImpl(query, value);
                if (expected != actual) Debugger.Break();
                Assert.Equal(expected, actual);
 
                for (int index = 0; index < basis.Count - 1; index++)
                {
                    for (int count = 0; count <= basis.Count - index; count++)
                    {
                        expected = basis.BinarySearch(index, count, value, null);
                        actual = BinarySearchImpl(query, index, count, value, null);
                        if (expected != actual) Debugger.Break();
                        Assert.Equal(expected, actual);
                    }
                }
            }
        }
 
        [Fact]
        public void BinarySearchPartialSortedList()
        {
            var reverseSorted = System.Collections.Immutable.ImmutableArray.CreateRange(Enumerable.Range(1, 150).Select(n => n * 2).Reverse());
            this.BinarySearchPartialSortedListHelper(reverseSorted, 0, 50);
            this.BinarySearchPartialSortedListHelper(reverseSorted, 50, 50);
            this.BinarySearchPartialSortedListHelper(reverseSorted, 100, 50);
        }
 
        private void BinarySearchPartialSortedListHelper(System.Collections.Immutable.ImmutableArray<int> inputData, int sortedIndex, int sortedLength)
        {
            if (sortedIndex < 0)
                throw new ArgumentOutOfRangeException(nameof(sortedIndex));
            if (sortedLength < 1)
                throw new ArgumentOutOfRangeException(nameof(sortedLength));
 
            inputData = inputData.Sort(sortedIndex, sortedLength, Comparer<int>.Default);
            int min = inputData[sortedIndex];
            int max = inputData[sortedIndex + sortedLength - 1];
 
            var basis = new List<int>(inputData);
            var query = inputData.ToImmutableSegmentedList();
            for (int value = min - 1; value <= max + 1; value++)
            {
                for (int index = sortedIndex; index < sortedIndex + sortedLength; index++) // make sure the index we pass in is always within the sorted range in the list.
                {
                    for (int count = 0; count <= sortedLength - index; count++)
                    {
                        int expected = basis.BinarySearch(index, count, value, null);
                        int actual = BinarySearchImpl(query, index, count, value, null);
                        if (expected != actual) Debugger.Break();
                        Assert.Equal(expected, actual);
                    }
                }
            }
        }
 
        [Fact]
        public void SyncRoot()
        {
            var collection = (ICollection)this.GetEnumerableOf<int>();
            Assert.NotNull(collection.SyncRoot);
            Assert.Same(collection.SyncRoot, collection.SyncRoot);
        }
 
        [Fact]
        public void GetEnumeratorTest()
        {
            var enumerable = this.GetEnumerableOf(1);
            Assert.Equal(new[] { 1 }, enumerable.ToList()); // exercises the enumerator
 
            IEnumerable enumerableNonGeneric = enumerable;
            Assert.Equal(new[] { 1 }, enumerableNonGeneric.Cast<int>().ToList()); // exercises the enumerator
        }
 
        private protected abstract void RemoveAllTestHelper<T>(ImmutableSegmentedList<T> list, Predicate<T> test);
 
        private protected abstract void ReverseTestHelper<T>(ImmutableSegmentedList<T> list, int index, int count);
 
        private protected abstract List<T> SortTestHelper<T>(ImmutableSegmentedList<T> list);
 
        private protected abstract List<T> SortTestHelper<T>(ImmutableSegmentedList<T> list, Comparison<T> comparison);
 
        private protected abstract List<T> SortTestHelper<T>(ImmutableSegmentedList<T> list, IComparer<T>? comparer);
 
        private protected abstract List<T> SortTestHelper<T>(ImmutableSegmentedList<T> list, int index, int count, IComparer<T>? comparer);
 
        protected void AssertIListBaselineBothDirections<T1, T2>(Func<IList, object?, object> operation, T1 item, T2 other)
        {
            this.AssertIListBaseline(operation, item, other);
            this.AssertIListBaseline(operation, other, item);
        }
 
        /// <summary>
        /// Asserts that the <see cref="ImmutableSegmentedList{T}"/> or <see cref="ImmutableSegmentedList{T}.Builder"/>'s
        /// implementation of <see cref="IList"/> behave the same way <see cref="List{T}"/> does.
        /// </summary>
        /// <typeparam name="T">The type of the element for one collection to test with.</typeparam>
        /// <param name="operation">
        /// The <see cref="IList"/> operation to perform.
        /// The function is provided with the <see cref="IList"/> implementation to test
        /// and the item to use as the argument to the operation.
        /// The function should return some equatable value by which to compare the effects
        /// of the operation across <see cref="IList"/> implementations.
        /// </param>
        /// <param name="item">The item to add to the collection.</param>
        /// <param name="other">The item to pass to the <paramref name="operation"/> function as the second parameter.</param>
        protected void AssertIListBaseline<T>(Func<IList, object?, object> operation, T item, object? other)
        {
            IList bclList = new List<T> { item };
            IList testedList = (IList)this.GetListQuery(ImmutableSegmentedList.Create(item));
 
            object expected = operation(bclList, other);
            object actual = operation(testedList, other);
            Assert.Equal(expected, actual);
        }
 
        private void TrueForAllTestHelper<T>(ImmutableSegmentedList<T> list, Predicate<T> test)
        {
            var bclList = list.ToList();
            var expected = bclList.TrueForAll(test);
            var actual = TrueForAllImpl(list, test);
            Assert.Equal(expected, actual);
        }
 
        protected class ProgrammaticEquals
        {
            private readonly Func<object?, bool> equalsCallback;
 
            internal ProgrammaticEquals(Func<object?, bool> equalsCallback)
            {
                this.equalsCallback = equalsCallback;
            }
 
            public override bool Equals(object? obj)
            {
                return this.equalsCallback(obj);
            }
 
            public override int GetHashCode()
            {
                throw new NotImplementedException();
            }
        }
    }
}