How to create a SortedList in C# with the ability to find floor and ceiling values

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:

ExperiencePointsRequiredLevel
01
5002
25003
100004

 

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

And, here’s the code in use:

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

Code to populate rate table and do a lookup:

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

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 thoughts on “How to create a SortedList in C# with the ability to find floor and ceiling values

  1. By making the declaration line the following :

    public class SortedListWithFloorAndCeiling<K, V> :  SortedList<K, V> where K:IComparable<K> {

    you can then write the class to use key1.CompareTo(key2) instead of key1 < key2, key >= key2, etc. This means the class will now work for any Key that implements IComparable, which includes Int32, string, and most other primitives.

    Just a little something I picked up from Java, where the syntax would be

    public class SortedListWithFloorAndCeiling<K extends Comparable<K>, V>
    extends HashMap<K, V> {

Leave a Reply

Your email address will not be published. Required fields are marked *