A while back, I wrote a browser-based game. I made it very flexible, and much of the logic was loaded from the database. One of the things I had in the database was how many experience points were needed for each level. The Level table looked something like this:
| ExperiencePointsRequired | Level |
| 0 | 1 |
| 500 | 2 |
| 2500 | 3 |
| 10000 | 4 |
Whenever the player gained any experience points, I had to check to see what level they were.
I could have loaded the Level table into a SortedList, and iterated through each element (starting with the first), until I reached an element that had a higher ExperiencePointsRequired than the player had. But, being a programmer, I wanted a better (re-usable) solution.
If a player had 3600 experience points, I wanted a way to determine their level by just calling “LevelList.FloorValueFor(3600);”, and have it return the value “3”.
That’s why I built a SortedList object that had the ability to search for the floor and ceiling elements – the first element below, or above, a specified value.
I tried making the class as generic as possible, but ran into some limits. First, there wasn’t any good way to use generics to ensure that the key value was a number. Second, I eventually wanted to write the same type of list for strings, which use a different method to see if one string is “less than”, or “greater than”, another string.
Here’s the code I eventually came up with.
SortedListWithFloorAndCeilingIntegerKey.cs
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
}
}And, here’s the code in use:
private void Level()
{
SortedListWithFloorAndCeilingIntegerKey<int> levels = new SortedListWithFloorAndCeilingIntegerKey<int>();
levels.Add(0, 1);
levels.Add(500, 2);
levels.Add(2500, 3);
levels.Add(10000, 4);
int userExperiencePoints = 3600;
int userLevel = levels.FloorValueFor(userExperiencePoints);
int experiencePointsForNextLevel = levels.CeilingKeyFor(userExperiencePoints); // will return 10000
int pointsNeededForNextLevel = experiencePointsForNextLevel - userExperiencePoints;
}Like all SortedList objects, we store a key/value pair. In this case, we want to use the experience points as the key, since that’s what we will be searching on. The “value” of the key/value pair will be the level, an integer. That’s why the levels object is declared as “SortedListWithFloorAndCeilingIntegerKey<int>”.
You could easily store any other type of object in the value part of the key/value pair – including your own business object.
For example, let’s say you’re writing a program that calculates billing rate for medical insurance. You need to charge different rates for different age brackets. So, your key would be the lower age for the age bracket. Your value might be a more complex object that stores different rates, based on whether or not the insured is a smoker.
Here’s how that might look:
InsuranceRate.cs
public class InsuranceRate
{
public double NonSmoker { get; private set; }
public double Smoker { get; private set; }
public InsuranceRate(double nonSmoker, double smoker)
{
NonSmoker = nonSmoker;
Smoker = smoker;
}
public double RateBasedOnSmokingStatus(bool isSmoker)
{
return isSmoker ? Smoker : NonSmoker;
}
}Code to populate rate table and do a lookup:
private void Insurance()
{
SortedListWithFloorAndCeilingIntegerKey<InsuranceRate> rates =
new SortedListWithFloorAndCeilingIntegerKey<InsuranceRate>();
rates.Add(0, new InsuranceRate(10, 20)); // 0 through 17
rates.Add(18, new InsuranceRate(20, 40)); // 18 through 24
rates.Add(25, new InsuranceRate(25, 50)); // 25 through 39
rates.Add(40, new InsuranceRate(40, 100)); // 40 through 59
rates.Add(60, new InsuranceRate(75, 200)); // 60 and up
// Determine the rate for a 42 year old non-smoker
double applicantRate = rates.FloorValueFor(42).RateBasedOnSmokingStatus(false); // return 40
}If you want to use some other numeric datatype for the key value, replace all the “Int32″s with whatever datatype you want to use. But don’t change the “int” return type on FloorIndexFor() and CeilingIndexFor(). That always needs to be “int”, since it’s the value from the enumerator from the base SortedList class.
I did make a version of this class that used doubles for the keys, since that’s the numeric datatype with the widest range. Then, no matter what numeric datatype you used for your key, like an Int32, it was saved as a double. But then, if you call the GetFloorKey() or GetCeilingKey() method, you’ll probably need to convert the returned double to an Int32. That’s not a huge problem, but I decided to go this route, since it worked for my application.
Here’s a version to use if your key will be a string. Something to remember with this class is that the key strings are case-sensitive. So, “A” does not equal “a”.
SortedListWithFloorAndCeilingStringKey.cs
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
}
}Summary
Now I have a way to find the nearest entry in a SortedList that’s above or below my value, for those times when I may not have exact matching key values.
I’m going to keep an eye on future changes to the .Net framework, to see if I can ever make this more generic and not have a different class for each key datatype.
The source code for these classes is also on GitHub at https://gist.github.com/ScottLilly/7041037
2 Comments