Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Specialized SortedList classes to let you search for the entry immediately before, or after, the requested key value.
using System;
using System.Collections.Generic;
namespace DotNetToolBox.Collections
{
public class SortedListWithFloorAndCeilingIntegerKey<TV> : SortedList<Int32, TV>
{
#region Floor object methods
public int FloorIndexFor(Int32 searchKey)
{
RaiseExceptionIfListIsEmpty();
// If the lowest value is higher than the search key, then there is no floor value possible.
if(Keys[0] > searchKey)
{
throw new ArgumentOutOfRangeException("No floor value exists. Lowest key value is higher than search key value.");
}
// If the search key value exists as an exact match, return its index.
if(ContainsKey(searchKey))
{
return Keys.IndexOf(searchKey);
}
// If the search key value is greater than the highest value, then the highest value is the floor value.
if(Keys[Count - 1] < searchKey)
{
return (Count - 1);
}
// There weren't any short-circuit solutions, so do the search.
return FindFloorObjectIndex(searchKey);
}
public Int32 FloorKeyFor(Int32 searchKey)
{
return Keys[FloorIndexFor(searchKey)];
}
public TV FloorValueFor(Int32 searchKey)
{
return Values[FloorIndexFor(searchKey)];
}
#endregion
#region Ceiling object methods
public int CeilingIndexFor(Int32 searchKey)
{
RaiseExceptionIfListIsEmpty();
// If the highest value is lower than the search key, then there is no ceiling value possible.
if(Keys[Count - 1] < searchKey)
{
throw new ArgumentOutOfRangeException("No ceiling value exists. Highest key value is lower than search key value.");
}
// If the search key value exists as an exact match, return it.
if(ContainsKey(searchKey))
{
return Keys.IndexOf(searchKey);
}
// If the search key value is lower than the lowest value, then the lowest value is the ceiling value.
if(Keys[0] > searchKey)
{
return 0;
}
// There weren't any short-circuit solutions, so do the search.
return (FindFloorObjectIndex(searchKey) + 1);
}
public Int32 CeilingKeyFor(Int32 searchKey)
{
return Keys[CeilingIndexFor(searchKey)];
}
public TV CeilingValueFor(Int32 searchKey)
{
return Values[CeilingIndexFor(searchKey)];
}
#endregion
#region Private methods
private void RaiseExceptionIfListIsEmpty()
{
if(Count == 0)
{
throw new ArgumentOutOfRangeException("List does not contain any values.");
}
}
private int FindFloorObjectIndex(double searchKey)
{
int lowIndex = 0;
int highIndex = Count;
int midIndex = lowIndex + ((highIndex - lowIndex) / 2);
bool continueSearching = true;
while(continueSearching)
{
midIndex = lowIndex + ((highIndex - lowIndex) / 2);
if((midIndex == lowIndex) || (midIndex == highIndex))
{
continueSearching = false;
}
else if(Keys[midIndex] < searchKey)
{
lowIndex = midIndex;
}
else
{
highIndex = midIndex;
}
}
return midIndex;
}
#endregion
}
}
using System;
using System.Collections.Generic;
namespace DotNetToolBox.Collections
{
// NOTE; This class does not treat upper-case letters the same as lower-case letters.
// So, "A" will not be equal to "a".
// That's how string.CompareOrdinal works.
public class SortedListWithFloorAndCeilingStringKey<TV> : SortedList<string, TV>
{
#region Floor object methods
public int FloorIndexFor(string searchKey)
{
RaiseExceptionIfListIsEmpty();
// If the lowest value is higher than the search key, then there is no floor value possible.
if(string.CompareOrdinal(Keys[0], searchKey) > 0)
{
throw new ArgumentOutOfRangeException("No floor value exists. Lowest key value is higher than search key value.");
}
// If the search key value exists as an exact match, return it.
if(ContainsKey(searchKey))
{
return Keys.IndexOf(searchKey);
}
// If the search key value is greater than the highest value, then the highest value is the floor value.
if(string.CompareOrdinal(Keys[Count - 1], searchKey) < 0)
{
return (Count - 1);
}
// There weren't any short-circuit solutions, so do the search.
return FindFloorObjectIndex(searchKey);
}
public string FloorKeyFor(string searchKey)
{
return Keys[FloorIndexFor(searchKey)];
}
public TV FloorValueFor(string searchKey)
{
return Values[FloorIndexFor(searchKey)];
}
#endregion
#region Ceiling object methods
public int CeilingIndexFor(string searchKey)
{
RaiseExceptionIfListIsEmpty();
// If the highest value is lower than the search key, then there is no ceiling value possible.
if(string.CompareOrdinal(Keys[Count - 1], searchKey) < 0)
{
throw new ArgumentOutOfRangeException("No ceiling value exists. Highest key value is lower than search key value.");
}
// If the search key value exists as an exact match, return it.
if(ContainsKey(searchKey))
{
return Keys.IndexOf(searchKey);
}
// If the search key value is lower than the lowest value, then the lowest value is the ceiling value.
if(string.CompareOrdinal(Keys[0], searchKey) > 0)
{
return 0;
}
// There weren't any short-circuit solutions, so do the search.
return (FindFloorObjectIndex(searchKey) + 1);
}
public string CeilingKeyFor(string searchKey)
{
return Keys[CeilingIndexFor(searchKey)];
}
public TV CeilingValueFor(string searchKey)
{
return Values[CeilingIndexFor(searchKey)];
}
#endregion
#region Private methods
private void RaiseExceptionIfListIsEmpty()
{
if(Count == 0)
{
throw new ArgumentOutOfRangeException("List does not contain any values.");
}
}
private int FindFloorObjectIndex(string searchKey)
{
int lowIndex = 0;
int highIndex = Count;
int midIndex = lowIndex + ((highIndex - lowIndex) / 2);
bool continueSearching = true;
while(continueSearching)
{
midIndex = lowIndex + ((highIndex - lowIndex) / 2);
if((midIndex == lowIndex) || (midIndex == highIndex))
{
continueSearching = false;
}
else if(string.CompareOrdinal(Keys[midIndex], searchKey) < 0)
{
lowIndex = midIndex;
}
else
{
highIndex = midIndex;
}
}
return midIndex;
}
#endregion
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.