src/Text/Util/TextDataUtil/ListUtilities.cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

//
//  Copyright (c) Microsoft Corporation. All rights reserved.
//  Licensed under the MIT License. See License.txt in the project root for license information.
//
namespace Microsoft.VisualStudio.Text.Utilities
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// Handy list-oriented utilities.
    /// </summary>
    internal static class ListUtilities
    {
        /// <summary>
        /// Do a binary search in <paramref name="list"/> for an element that matches <paramref name="target"/>
        /// </summary>
        /// <param name="list">List to search.</param>
        /// <param name="target">Object of the search.</param>
        /// <param name="compare">Comparison function between an element and target (returns &lt; 0 if e comes before t, 0 if e matches, &gt; 0 if e comes after).
        /// <param name="index">Index of the matching element (or, if there is no exact match, index of the element that follows it).</param>
        /// <returns>true if an exact match was found.</returns>
        /// <remarks>Yes, I know there is List.BinarySearch but that doesn't do exactly what I need most of the time.</remarks>
        public static bool BinarySearch<E>(IList<E> list, Func<E, int> compare, out int index)
        {
            int lo = 0;
            int hi = list.Count;

            while (lo < hi)
            {
                index = (lo + hi) / 2;

                int cmp = compare(list[index]);
                if (cmp < 0)
                {
                    lo = index + 1;
                }
                else if (cmp == 0)
                {
                    return true;
                }
                else
                {
                    hi = index;
                }
            }

            index = lo;
            return false;
        }

        public static T? FirstOrNullable<T>(this IEnumerable<T> source)
           where T : struct
        {
            if (source == null)
            {
                throw new ArgumentNullException(nameof(source));
            }

            return source.Cast<T?>().FirstOrDefault();
        }
    }
    }