C# Look up dictionary

Question

I'm currently trying to create a program that estimates location based on signal strength. The signal strength value is an int and then i need a lookup dictionary with ranges.

So I would have something like:

Signal Strenth             Position
0-9                            1
10-19                          2
20-29                          3

and then I would want to look up what position a signal strength relates to, for example 15 would relate to position 2.

I know I can just have a load of if statements but is there a good way to do this using some sort of lookup dictionary?

Answer 1

When you want to use Dictionary, you need at least some special key type to deal with the ranges. KeyType can be abstract and two derived types KeyTypeRange(int int) and KEyTypeSearch( int). Some special comparison logic must be implemented to compare an KeyTypeSearch with an KeyTypeRange.

SortedDictionary<KeyType,int>  lookup = new Dictionary<int,int>();
lookup.Add( new KeyTypeRange(1,10),1);
lookup.Add( new KeyTypeRange(11,20),2);
lookup.Add( new KeyTypeRange(21,30),3);
lookup.TryGetValue( new KeyTypeSearch(15) );

It shows a possible solution to use different esearch keys and key values in dictionaries. But this seems to be Overkill for this problem. This problem is solved best by the BinarySearch solution.

Answer 2

If you have arbitrary but consecutive ranges you can use an array of the upper bounds and perform a binary search to get the position:

// Definition of ranges
int[] ranges = new int[] { 9, 19, 29 };

// Lookup
int position = Array.BinarySearch(ranges, 15);
if (position < 0)
    position = ~position;

// Definition of range names
string[] names = new string[] { "home", "street", "city", "far away" };

Console.WriteLine("Position is: {0}", names[position]);

Array.BinarySearch returns the index of the item in the array if it exists (array must be sorted obviously) or the bitwise inverted index where the item should be inserted to keep the array sorted.

Answer 3

if there is a direct correlation between signal range and the position then use what @agileguy suggested.

If you have positions distributed non linearly across the signal strength then one way would be:

class SignalStrengthPositionMapper
{
    private static readonly int[] signalStrength = { Int32.MinValue, 0, 5, 11, 15, 20, 27, 35 };
    public static int GetPosition(int strength)
    {
        return StrengthSearch(0, signalStrength.Length, strength);
    }

    // modified binary search
    private static int StrengthSearch(int start, int end, int strength)
    {
        int mid = 0;
        while (start <= end)
        {
            mid = (start + end) / 2;

            if (strength >= signalStrength[mid])         // lower bound check
            {
                start = mid + 1;
                if (strength < signalStrength[start])    // upper bound check
                    return mid;
            }
            else if (strength < signalStrength[mid])     // upper bound check
            {
                end = mid - 1;
                if (strength >= signalStrength[end])     // lower bound check
                    return mid;
            }
        }
        return 0;
    }
}

Answer 4

One solution would be to use a simple list, where each position in the list represents a different position that you're scanning for. In code, it might look something like this (assuming that all position numbers are sequential):

** Note: I have not actually run this code to make sure it works as-is... you might also need to implement an IEqualityComparer on Range in order for the IndexOf operation to return the proper position:

public class Controller
{
   List m_positions = new List();

   public void LoadPositions()
   {
      m_positions.Add(new Range(0, 9));
      m_positions.Add(new Range(10, 19));
      m_positions.Add(new Range(20, 29));
   }

   public int GetPosition (int signal)
   {
      Range range = m_positions.Single(a => IsBetween(signal, a.Min, a.Max));

      return m_positions.IndexOf(range);
   }

   private static bool IsBetween (int target, int min, int max)
   {
      return min = target;
   }
}

It's probably pretty self-explanatory, but to avoid any confusion, here's what the Range class might look like:

public class Range
{
   public Range(int min, int max)
   {
      this.Min = min;
      this.Max = max;
   }

   public int Min
   {
      get;
      private set;
   }

   public int Max
   {
      get;
      private set;
   }
}

Answer 5

Good is a function of purpose. All of the above solutions work well presuming that any given range is a small number of integers. Otherwise you may want to use whatever the real world math function is to determine your group. For instance, for the example given, your answer function would be x % 10 + 1; That'll run much faster than a dictionary.

Answer 6

For future expansion i would do 2 dictionaries. Just in case those rates change so a

dictionary<string,dictionary<int,int>>

or just use custom classes the string would be static strings like low med, high, then you can change the ranges in your foreach initilixing the initial values

Answer 7

Try using generics:

Dictionary<int,int>  lookup = new Dictionary<int,int>();
lookup.Add(0,1);
lookup.Add(1,1);
lookup.Add(2,1);
lookup.Add(3,1);
...
lookup.Add(9,1);
lookup.Add(10,2);
lookup.Add(11,2);

etc

Then, lookup[22] would return value of 3. I suggest using a set of loops to create your 'ranges'. With this method, you're guaranteed O(1) access time.

Answer 8

You could do a Dictionary, where the first int is the signal strength and the second int is the position. You would need to add an entry for every value in the range (so, one for signal strength 0, position 1, signal strength 1, position 1, etc.), but it would be a very quick, single line lookup.

Something like:

Dictionary<int, int> values;

values = new Dictionary<int, int>();

values[0] = 1;
values[1] = 1;
...
values[29] = 3;

and then, to access it:

Console.WriteLine(values[27].ToString());

Answer 9

What about :

int position = signalStrength / 10 + 1;

Kindness,

Dan