Early this year, I decided to brush up on my algorithms and data structure knowledge. I took these great two courses (1, 2) on PluralSight by Robert Horvick.
To practice what I learned in this course, I decided to create generic versions of the different algorithms and data structures.
What do I mean by generic versions? These types of courses always use integers or strings to demonstrate the algorithms. Instead of using those primitive data types, I'm reimplementing the algorithms and data structures using C#'s generic type parameters.
Here's a console application with a generic method BoyerMooreHorspoolSearchSequence to perform a Boyer–Moore–Horspool algorithm search looking for a sequence of T:
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main(string[] args)
{
var numbers = Enumerable.Range(250, 750).ToArray();
var index = BoyerMooreHorspoolSearchSequence(numbers.AsEnumerable(), new int[] { 500, 501, 502 });
Console.WriteLine("Boyer-Moore-Horspool Search Sequence:");
Console.WriteLine(index);
Console.ReadKey();
Console.Clear();
}
private static int BoyerMooreHorspoolSearchSequence<T>(IEnumerable<T> list, IEnumerable<T> needle) where T : IComparable
{
var items = list.ToArray();
var itemsLength = items.Length;
var needleArray = needle.ToArray();
var needleLength = needleArray.Length;
int shiftAmountIfMissing = needleLength;
Dictionary<T, int> badMatchTable = new Dictionary<T, int>();
for (int i = 0; i < needleLength - 1; i++)
{
badMatchTable[needleArray[i]] = needleLength - i - 1;
}
int listIndex = 0;
while (listIndex <= itemsLength - needleLength)
{
int matchIndex = needleLength - 1;
while (true)
{
if (items[listIndex + matchIndex].CompareTo(needleArray[matchIndex]) == 0)
{
matchIndex--;
}
else
{
break;
}
if (matchIndex <= 0)
{
return listIndex;
}
}
if (badMatchTable.TryGetValue(items[listIndex + needleLength - 1], out int amountToShift))
{
listIndex += amountToShift;
}
else
{
listIndex += shiftAmountIfMissing;
}
}
return -1;
}
}
By using a generic type parameter with the constraint that the type has to implement the IComparable interface, you can perform the Boyer–Moore–Horspool algorithm without knowing the exact type you are working with.
If you want to understand the logic behind the Boyer–Moore–Horspool algorithm, I recommend checking out the courses mentioned earlier. There's also a lot of other great resources out there online!
Disclaimer: This code works, but is only developed for the sake of practice. Use at your own risk or just use a sorting library. If you see some room for improvement, there most likely is, I'm all ears~
Top comments (0)