Last active
August 21, 2019 11:18
-
-
Save fengyj/1dc020ec0cc11f0bc4e51bbfa9fa677b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void Main() | |
| { | |
| var myValues = new MyValues("abc,a,def,a,def,abcd,dd"); | |
| foreach (var item in myValues) | |
| { | |
| System.Console.WriteLine(item); | |
| } | |
| System.Console.WriteLine("another test:"); | |
| myValues = new MyValues("abe,b,def,a,def,abcd"); | |
| foreach (var item in myValues) | |
| { | |
| System.Console.WriteLine(item); | |
| } | |
| System.Console.WriteLine("test3:"); | |
| myValues = new MyValues("z,z"); | |
| foreach (var item in myValues) | |
| { | |
| System.Console.WriteLine(item); | |
| } | |
| System.Console.WriteLine("test4:"); | |
| myValues = new MyValues("M"); | |
| foreach (var item in myValues) | |
| { | |
| System.Console.WriteLine(item); | |
| } | |
| } | |
| public class MyValues : IEnumerable<String> { | |
| private readonly static String[] allWords = new String[50]; | |
| private static int wordsCount = 0; | |
| private readonly int[] _values; | |
| public MyValues(string values) { | |
| _values = parse(values); | |
| } | |
| public IEnumerator<string> GetEnumerator() { | |
| return _values.Select(w => allWords[w]).GetEnumerator(); | |
| } | |
| IEnumerator IEnumerable.GetEnumerator() { | |
| return GetEnumerator(); | |
| } | |
| private int[] parse(String values) { | |
| HashSet<int> words = new HashSet<int>(); | |
| int start = 0; | |
| for(int pos = 0; pos < values.Length; pos++) { | |
| if(values[pos] != ',' && pos != values.Length - 1) continue; | |
| var wordPosition = GetValue(values, start, (pos == values.Length - 1 ? pos + 1 : pos) - start); | |
| if (wordPosition.Item2) // new word, the old indexes larger than the current one, needs to increase the index value | |
| { | |
| HashSet<int> newWords = new HashSet<int>(); | |
| foreach(var w in words) { | |
| if(w >= wordPosition.Item1) | |
| newWords.Add(w + 1); | |
| else | |
| newWords.Add(w); | |
| } | |
| words = newWords; | |
| } | |
| words.Add(wordPosition.Item1); | |
| start = pos + 1; | |
| } | |
| return words.OrderBy(w => w).ToArray(); | |
| } | |
| private Tuple<int, bool> GetValue(String values, int start, int length) { | |
| for(int i = 0; i < wordsCount; i++) { // could use binary search here | |
| String word = allWords[i]; | |
| int result = Compare(word, values, start, length); | |
| if (result == 0) { | |
| return Tuple.Create(i, false); // it's not a new word | |
| } | |
| if (result < 0) { | |
| AddWord(values, start, length, i); | |
| return Tuple.Create(i, true); // it's a new word, return the index of it | |
| } | |
| } | |
| AddWord(values, start, length, wordsCount); | |
| return Tuple.Create(wordsCount - 1, true); // it's a new word, return the index of it | |
| } | |
| private void AddWord(String values, int start, int length, int position) { | |
| String word = values.Substring(start, length); | |
| for(int i = wordsCount - 1; i >= position; i--) { | |
| allWords[i + 1] = allWords[i]; | |
| } | |
| allWords[position] = word; | |
| wordsCount++; | |
| } | |
| private int Compare(String sample, String values, int start, int length) { | |
| for(int i = 0; i < (sample.Length > length ? length : sample.Length); i++) { | |
| int result = values[i + start].CompareTo(sample[i]); | |
| if(result == 0) continue; | |
| return result; | |
| } | |
| return length.CompareTo(sample.Length); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment