Ian Moulster's blog

A Microsoft employee translating Microsoft technology into plain English

A .NET CF search class

A .NET CF search class

  • Comments 3

There's a clever little feature on smartphones that I've been keen to replicate in my own .NET CF apps: It's the way searching happens when you're looking for a contact. It works like this: Let's say I'm looking for my friend Graham. I go to contacts and press 4724 - and it finds a match. Why 4724? Because the letters "GRAH" (the start of his name) appear on these number keys. It doesn't matter that "R" is the 3rd letter on key 7 because the phone is clever enough to search for all possible combinations of strings and match them against my contact list. The result is that I can find my contacts quickly without having to jab away at the 7 key three times to get an "R".

So wouldn't it be great if you could do that kind of search in your own smartphone applications? Well I wrote a little class to do just that, it's pasted below. You use it like this (this is all in C#, apologies to VB folk):

PhoneKeyScanner pks = new PhoneKeyScanner("4724");
MyList.Items.Add(new ListViewItem(pks.FirstCombination()));
while (pks.CombinationsRemain())
  MyList.Items.Add(new ListViewItem(pks.NextCombination()));

So in this case the listview would be filled with "GPAG", "GQAG", "GRAG" etc all the way to "ISCI"" (and of course including "GRAH"). Which makes it a simple process to search whatever it is you need to look for in order to find a match. For example if I wanted to replicate the contacts search, I'd scan all of my contacts within the while loop against each combination, and would of course eventually get a match on "GRAH".

My challenge is to improve the speed. I'm sort of a part time developer so any of you hard-core folks out there will, I'm sure, be able to squeeze some extra efficiency out of this code. And yes I know there's no error checking - so shoot me. This is just illustrative code, not for the real world...

Anyhow, if you can improve on this I'd be really interested. Remembering of course that this is the .NET CF, so there are limitations on what you can do.

 public class PhoneKeyScanner
            {
            private NameValueCollection LastValues = new NameValueCollection();
            private NameValueCollection FirstValues = new NameValueCollection();
            private string InitialPhoneKeys;
            private string CurrentCombination;
            private string InitialCombination;

            /// <summary>
            /// Returns the first letter on a given Phone keypad number
            /// </summary>
            /// <remarks>
            /// For example, if the number "2" is passed in, the letter "A" is returned
            /// ("A" is the first letter on the key "2" on a telephone)
            /// </remarks>
            public string FirstChar ( string phoneKey )
                {
                return FirstValues[phoneKey];
                }

            /// <summary>
            /// Constructor for Phone_Number class
            /// </summary>
            /// <remarks>
            /// This constructor does two things: 
            /// 1) It sets up the namevalue collections with the first letter and last letter corresponding to the keys on a telephone keypad. 
            /// 2) It uses the input set of keys from the telephone keypad to construct the starting string of letters. 
            /// For example, if "359" is passed in, then the initial string of letters is set to "DJW".
            /// </remarks>
            public PhoneKeyScanner ( string phoneKeys )
                {
                LastValues["2"] = "C";
                LastValues["3"] = "F";
                LastValues["4"] = "I";
                LastValues["5"] = "L";
                LastValues["6"] = "O";
                LastValues["7"] = "S";
                LastValues["8"] = "V";
                LastValues["9"] = "Z";
                FirstValues["2"] = "A";
                FirstValues["3"] = "D";
                FirstValues["4"] = "G";
                FirstValues["5"] = "J";
                FirstValues["6"] = "M";
                FirstValues["7"] = "P";
                FirstValues["8"] = "T";
                FirstValues["9"] = "W";

                InitialPhoneKeys = phoneKeys;
                InitialCombination = "";
                for (int i = 0; i < InitialPhoneKeys.Length; i++)
                    {
                    InitialCombination = InitialCombination + FirstChar(InitialPhoneKeys.Substring(i, 1));
                    }

                CurrentCombination = InitialCombination;
                }

            /// <summary>
            /// Check whether there are any more valid combinations of letters remaining
            /// </summary>
            /// <remarks>
            /// Each number on a phone keypad corresponds to a number of letters of the alphabet. 
            /// This method checks whether the instance has cycled through all of the combination of letters for a given number sequence.
            /// For example, if numbers "234" are entered, the range of  possible letter values starts with "ADG" and ends with "CFI". 
            /// So this method will return "false" if the last combination returned was "CFI" in this case.
            /// </remarks>
            public bool CombinationsRemain ()
                {
                int CountEndValues = 0;
                for (int i = 0; i < CurrentCombination.Length; i++)
                    {
                    if (CurrentCombination.Substring(i, 1) == LastValues[InitialPhoneKeys.Substring(i, 1)])
                        CountEndValues += 1;
                    }
                if (CountEndValues == CurrentCombination.Length)
                    return false; // All are at their last position, so no combinations remain
                else
                    return true;
                }

            /// <summary>
            /// Return the next set of letters corresponding to the numbers entered on the telephone keypad
            /// </summary>
            /// <remarks>
            /// Primarily this method exists only to allow TicCombination to call itself recursively in order 
            /// to calculate the next combination of letters.
            /// </remarks>
            public string NextCombination ()
                {
                CurrentCombination = TickCombination(CurrentCombination, 1);
                return CurrentCombination;
                }

            /// <summary>
            /// Find the next combination of letters on the telephone keypad
            /// </summary>
            /// <remarks>
            /// This method is the heart of the searching algorithm. 
            /// It calls itself recursively in order to determine what the next set of letters is. 
            /// For example, if "DLN" is passed in, "DLO" is returned. 
            /// And if "DLO" is passed in, then "EJM" is returned (take a look at a telephone keypad to see why this is).
            /// </remarks>
            private string TickCombination ( string incomingCombination, int incrementLevel )
                {
                string LeftmostValues;
                string InitialValueThisLevel;
                string RightmostValues;
                string NextValueThisLevel;

                if (incomingCombination.Substring(incomingCombination.Length - incrementLevel, 1) == LastValues[InitialPhoneKeys.Substring(InitialPhoneKeys.Length - incrementLevel, 1)])
                    {
                    // If the digit at the current level is the last one....for example: If the input string is WGNF and the current level is 1,
                    // then we're at the last digit (F) for the current level (1). In which case we set the current level character back to the first
                    // digit for this level (ie back to D in this case) and call this same method recursively but for one level up.
                    LeftmostValues = incomingCombination.Substring(0, incomingCombination.Length - incrementLevel);
                    InitialValueThisLevel = FirstValues[InitialPhoneKeys.Substring(InitialPhoneKeys.Length - incrementLevel, 1)];
                    RightmostValues = incomingCombination.Substring(incomingCombination.Length - incrementLevel + 1);
                    return TickCombination(LeftmostValues + InitialValueThisLevel + RightmostValues, incrementLevel + 1);
                    }
                else
                    {
                    // Otherwise, just increment the character at the current level and return the result
                    LeftmostValues = incomingCombination.Substring(0, incomingCombination.Length - incrementLevel);
                    NextValueThisLevel = NextKeyValue(incomingCombination.Substring(incomingCombination.Length - incrementLevel, 1), InitialPhoneKeys.Substring(InitialPhoneKeys.Length - incrementLevel, 1));
                    RightmostValues = incomingCombination.Substring(incomingCombination.Length - incrementLevel + 1);
                    return (LeftmostValues + NextValueThisLevel + RightmostValues);
                    }
                }

            /// <summary>
            /// Returns the next letter on the given telephone keypad key
            /// </summary>
            /// <remarks>
            /// This looks more complicated than it is....
            /// a) initialKeyValue is the character ie "A", "B", "C", etc.
            /// b) phoneKeyDigit is the button on the mobile phone that has been pressed eg "2", "3", etc
            /// If the character is the last one for the digit pressed, then return the first character. Otherwise, just move along one. 
            /// So "A" would return "B"; and "B" would return "C". But "C" would return "A" again.
            /// </remarks>
            public string NextKeyValue ( string initialKeyValue, string phoneKeyDigit )
                {
                if (LastValues[phoneKeyDigit] == initialKeyValue)
                    return FirstValues[phoneKeyDigit];
                else
                    {
                    // First we convert the string (which only has one character) to a char. Then we add one to it, cast it to an integer and back
                    // in order to do so. Then we convert it back to a string. So "A" becomes "B", and "Q" becomes "R" etc.
                    char[] i = initialKeyValue.ToCharArray();
                    i[0] = (char)((int)i[0] + 1);
                    return (i[0].ToString());
                    }
                }

            /// <summary>
            /// Return the initial combination that was created by the constructor
            /// </summary>
            public string FirstCombination ()
                {
                return InitialCombination;
                }
            }
Leave a Comment
  • Please add 3 and 3 and type the answer here:
  • Post
  • Finishing up high-level design this week..busy, busy.
    Software / Hardware&amp;nbsp;

    Check this out: &amp;nbsp;USB...
  • Finishing up high-level design this week..busy, busy.
    Software / Hardware&amp;nbsp;

    Check this out: &amp;nbsp;USB...
  • Finishing up high-level design this week..busy, busy.
    Software / Hardware&amp;nbsp;

    Check this out: &amp;nbsp;USB...
Page 1 of 1 (3 items)