Skip to content

Instantly share code, notes, and snippets.

@jesuslpm
Last active November 13, 2017 13:58
Show Gist options
  • Save jesuslpm/9bdb21a4e157ffdefca50162966f77fe to your computer and use it in GitHub Desktop.
Save jesuslpm/9bdb21a4e157ffdefca50162966f77fe to your computer and use it in GitHub Desktop.
The world’s smallest indexing code
public class Index<TItem, TKey>
{
private readonly SortedSet<KeyValuePair<TKey, List<TItem>>> sortedSet;
public Index(IEnumerable<TItem> items, Func<TItem, TKey> keySelector, Comparer<TKey> keyComparer = null)
{
if (keyComparer == null) keyComparer = Comparer<TKey>.Default;
var keyPairComparer = Comparer<KeyValuePair<TKey, List<TItem>>>.Create((x, y) => keyComparer.Compare(x.Key, y.Key));
var keyPairs = items.GroupBy(keySelector).Select(x => new KeyValuePair<TKey, List<TItem>>(x.Key, x.ToList()));
sortedSet = new SortedSet<KeyValuePair<TKey, List<TItem>>>(keyPairs, keyPairComparer);
}
public IEnumerable<TItem> All()
{
foreach (var keyPair in this.sortedSet)
{
foreach (var item in keyPair.Value) yield return item;
}
}
public IEnumerable<TItem> ExactMatchSearch(TKey key)
{
return this.RangeSearch(key, key);
}
public IEnumerable<TItem> RangeSearch(TKey fromKey, TKey toKey)
{
var lowerValue = new KeyValuePair<TKey, List<TItem>>(fromKey, null);
var upperValue = new KeyValuePair<TKey, List<TItem>>(toKey, null);
foreach (var keyPair in this.sortedSet.GetViewBetween(lowerValue, upperValue))
{
foreach (var item in keyPair.Value) yield return item;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp2
{
static class Program
{
static void Main(string[] args)
{
var array = new int[] { 8, 5, 1, 11, 2, 2, 3, 1, 5, 5, 1, 2 };
var index = array.BuildIndex(x => x);
foreach (var x in index(6, 15))
{
Console.WriteLine(x);
}
}
private static int BinarySearchFirstGreaterOrEquals<TItem, TKey>(this TItem[] sortedArray, Func<TItem, TKey> keySelector, TKey key)
{
int l = 0; int r = sortedArray.Length - 1;
if (Comparer<TKey>.Default.Compare(key, keySelector(sortedArray[r])) > 0) return sortedArray.Length;
while (l < r)
{
int m = (l + r) / 2;
if (Comparer<TKey>.Default.Compare(key, keySelector(sortedArray[m])) > 0) l = m + 1;
else r = m ;
}
return l;
}
private static IEnumerable<TItem> Search<TItem, TKey>(this TItem[] sortedArray, Func<TItem, TKey> keySelector, TKey from, TKey to)
{
for(var index = sortedArray.BinarySearchFirstGreaterOrEquals(keySelector, from); index < sortedArray.Length; index++ )
{
var item = sortedArray[index];
var key = keySelector(item);
if (Comparer<TKey>.Default.Compare(key, from) < 0) yield break;
if (Comparer<TKey>.Default.Compare(key, to) > 0) yield break;
yield return item;
}
}
public static Func<TKey, TKey, IEnumerable<TItem>> BuildIndex<TKey, TItem>(this IEnumerable<TItem> collection, Func<TItem, TKey> keySelector)
{
var sortedArray = collection.OrderBy(keySelector).ToArray();
return (TKey from, TKey to) => sortedArray.Search(keySelector, from, to);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment