mirror of
https://github.com/Facepunch/sbox-public.git
synced 2026-04-20 14:28:17 -04:00
71f266059a
This commit imports the C# engine code and game files, excluding C++ source code. [Source-Commit: ceb3d758046e50faa6258bc3b658a30c97743268]
95 lines
3.5 KiB
C#
95 lines
3.5 KiB
C#
// RichTextKit
|
|
// Copyright © 2019-2020 Topten Software. All Rights Reserved.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License"); you may
|
|
// not use this product except in compliance with the License. You may obtain
|
|
// a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
|
|
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
|
|
// License for the specific language governing permissions and limitations
|
|
// under the License.
|
|
|
|
using System;
|
|
using System.Collections.Generic;
|
|
using System.Text;
|
|
|
|
namespace Topten.RichTextKit.Utils
|
|
{
|
|
/// <summary>
|
|
/// Extension methods for binary searching an IReadOnlyList collection
|
|
/// </summary>
|
|
public static class BinarySearchExtension
|
|
{
|
|
private static int GetMedian( int low, int hi )
|
|
{
|
|
System.Diagnostics.Debug.Assert( low <= hi );
|
|
System.Diagnostics.Debug.Assert( hi - low >= 0, "Length overflow!" );
|
|
return low + ((hi - low) >> 1);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Performs a binary search on the entire contents of an IReadOnlyList
|
|
/// </summary>
|
|
/// <typeparam name="T">The list element type</typeparam>
|
|
/// <param name="list">The list to be searched</param>
|
|
/// <param name="value">The value to search for</param>
|
|
/// <returns>The index of the found item; otherwise the bitwise complement of the index of the next larger item</returns>
|
|
public static int BinarySearch<T>( this IReadOnlyList<T> list, T value ) where T : IComparable
|
|
{
|
|
return list.BinarySearch( value, ( a, b ) => a.CompareTo( b ) );
|
|
}
|
|
|
|
|
|
/// <summary>
|
|
/// Performs a binary search on the entire contents of an IReadOnlyList
|
|
/// </summary>
|
|
/// <typeparam name="T">The list element type</typeparam>
|
|
/// <typeparam name="U">The value type being searched for</typeparam>
|
|
/// <param name="list">The list to be searched</param>
|
|
/// <param name="value">The value to search for</param>
|
|
/// <param name="compare">A comparison function</param>
|
|
/// <returns>The index of the found item; otherwise the bitwise complement of the index of the next larger item</returns>
|
|
public static int BinarySearch<T, U>( this IReadOnlyList<T> list, U value, Func<T, U, int> compare )
|
|
{
|
|
return BinarySearch( list, 0, list.Count, value, compare );
|
|
}
|
|
|
|
/// <summary>
|
|
/// Performs a binary search on a a subset of an IReadOnlyList
|
|
/// </summary>
|
|
/// <typeparam name="T">The list element type</typeparam>
|
|
/// <typeparam name="U">The value type being searched for</typeparam>
|
|
/// <param name="list">The list to be searched</param>
|
|
/// <param name="index">The start of the range to be searched</param>
|
|
/// <param name="length">The length of the range to be searched</param>
|
|
/// <param name="value">The value to search for</param>
|
|
/// <param name="compare">A comparison function</param>
|
|
/// <returns>The index of the found item; otherwise the bitwise complement of the index of the next larger item</returns>
|
|
public static int BinarySearch<T, U>( this IReadOnlyList<T> list, int index, int length, U value, Func<T, U, int> compare )
|
|
{
|
|
// Based on this: https://referencesource.microsoft.com/#mscorlib/system/array.cs,957
|
|
int lo = index;
|
|
int hi = index + length - 1;
|
|
while ( lo <= hi )
|
|
{
|
|
int i = GetMedian( lo, hi );
|
|
int c = compare( list[i], value );
|
|
if ( c == 0 ) return i;
|
|
if ( c < 0 )
|
|
{
|
|
lo = i + 1;
|
|
}
|
|
else
|
|
{
|
|
hi = i - 1;
|
|
}
|
|
}
|
|
return ~lo;
|
|
}
|
|
}
|
|
}
|