The Labs \ Source Viewer \ SSCLI \ System.Collections.Specialized \ FixedStringLookup

  1. //------------------------------------------------------------------------------
  2. // <copyright file="FixedStringLookup.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. namespace System.Collections.Specialized
  16. {
  17.    
  18.     using System;
  19.     using System.Collections;
  20.     using System.Diagnostics;
  21.     using System.Globalization;
  22.    
  23.     // This class provides a very efficient way to lookup an entry in a list of strings,
  24.     // providing that they are declared in a particular way.
  25.    
  26.     // It requires the set of strings to be orderded into an array of arrays of strings.
  27.     // The first indexer must the length of the string, so that each sub-array is of the
  28.     // same length. The contained array must be in alphabetical order. Furthermore, if the
  29.     // table is to be searched case-insensitively, the strings must all be lower case.
  30.     static internal class FixedStringLookup
  31.     {
  32.        
  33.         // Returns whether the match is found in the lookup table
  34.         static internal bool Contains(string[][] lookupTable, string value, bool ignoreCase)
  35.         {
  36.             int length = value.Length;
  37.             if (length <= 0 || length - 1 >= lookupTable.Length) {
  38.                 return false;
  39.             }
  40.            
  41.             string[] subArray = lookupTable[length - 1];
  42.             if (subArray == null) {
  43.                 return false;
  44.             }
  45.             return Contains(subArray, value, ignoreCase);
  46.         }
  47.        
  48.         #if DEBUG
  49.        
  50.         static internal void VerifyLookupTable(string[][] lookupTable, bool ignoreCase)
  51.         {
  52.             for (int i = 0; i < lookupTable.Length; i++) {
  53.                 string[] subArray = lookupTable[i];
  54.                 if (subArray != null) {
  55.                     string lastValue = null;
  56.                     for (int j = 0; j < subArray.Length; j++) {
  57.                         string value = subArray[j];
  58.                         // Must all be the length of the hashed position
  59.                         Debug.Assert(value.Length == i + 1, "Lookup table contains an item in the wrong subtable. Item name: " + value);
  60.                         if (lastValue != null) {
  61.                             // Must be sorted within the sub array;
  62.                             Debug.Assert(string.Compare(lastValue, value, ((ignoreCase) ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal)) < 0, String.Format(CultureInfo.InvariantCulture, "Lookup table is out of order. Items {0} and {1} are reversed", lastValue, value));
  63.                         }
  64.                         lastValue = value;
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.        
  70.         #endif
  71.        
  72.         // This routine finds a hit within a single sorted array, with the assumption that the
  73.         // value and all the strings are of the same length.
  74.         private static bool Contains(string[] array, string value, bool ignoreCase)
  75.         {
  76.             int min = 0;
  77.             int max = array.Length;
  78.             int pos = 0;
  79.             char searchChar;
  80.             while (pos < value.Length) {
  81.                 if (ignoreCase) {
  82.                     searchChar = char.ToLower(value[pos], CultureInfo.InvariantCulture);
  83.                 }
  84.                 else {
  85.                     searchChar = value[pos];
  86.                 }
  87.                 if ((max - min) <= 1) {
  88.                     // we are down to a single item, so we can stay on this row until the end.
  89.                     if (searchChar != array[min][pos]) {
  90.                         return false;
  91.                     }
  92.                     pos++;
  93.                     continue;
  94.                 }
  95.                
  96.                 // There are multiple items to search, use binary search to find one of the hits
  97.                 if (!FindCharacter(array, searchChar, pos, ref min, ref max)) {
  98.                     return false;
  99.                 }
  100.                 // and move to next char
  101.                 pos++;
  102.             }
  103.             return true;
  104.         }
  105.        
  106.         // Do a binary search on the character array at the specific position and constrict the ranges appropriately.
  107.         private static bool FindCharacter(string[] array, char value, int pos, ref int min, ref int max)
  108.         {
  109.             int index = min;
  110.             while (min < max) {
  111.                 index = (min + max) / 2;
  112.                 char comp = array[index][pos];
  113.                 if (value == comp) {
  114.                     // We have a match. Now adjust to any adjacent matches
  115.                     int newMin = index;
  116.                     while (newMin > min && array[newMin - 1][pos] == value) {
  117.                         newMin--;
  118.                     }
  119.                     min = newMin;
  120.                    
  121.                     int newMax = index + 1;
  122.                     while (newMax < max && array[newMax][pos] == value) {
  123.                         newMax++;
  124.                     }
  125.                     max = newMax;
  126.                     return true;
  127.                 }
  128.                 if (value < comp) {
  129.                     max = index;
  130.                 }
  131.                 else {
  132.                     min = index + 1;
  133.                 }
  134.             }
  135.             return false;
  136.         }
  137.     }
  138. }

Developer Fusion