仮想的な配列をソートしたりバイナリサーチしたり
…したくなったので、こんなカンジで作ってみたんですが、どうでしょう(´д`)
public interface IVirtualArray<T> { T this[int index] { get; set; } }
public static class VirtualArrayUtil { public static int BinarySearch<T>(IVirtualArray<T> array, int index, int length, Func<T,int> func) { int lo = index; int hi = index + length - 1; while (lo <= hi) { int mid = lo + ( ( hi - lo ) >> 1 ); int result = func( array[ mid ] ); if( result == 0 ) { return mid; } else if( result < 0 ) { lo = mid + 1; } else { hi = mid - 1; } } return -1; } public static int BinarySearchFirst<T>(IVirtualArray<T> array, int index, int length, Func<T,int> func) { int lo = index; int hi = index + length - 1; int first = -1; while( lo <= hi ) { int mid = lo + ( ( hi - lo ) >> 1 ); int result = func( array[mid] ); if( result == 0 ) { first = mid; hi = mid - 1; } else { if( first != -1 ) { lo = mid + 1; } else { if( result < 0 ) { lo = mid + 1; } else { hi = mid - 1; } } } } return first; } public static int BinarySearchLast<T>(IVirtualArray<T> array, int index, int length, Func<T, int> func) { int lo = index; int hi = index + length - 1; int last = -1; while( lo <= hi ) { int mid = lo + ( ( hi - lo ) >> 1 ); int result = func( array[mid] ); if( result == 0 ) { last = mid; lo = mid + 1; } else { if( last != -1 ) { hi = mid - 1; } else { if( result < 0 ) { lo = mid + 1; } else { hi = mid - 1; } } } } return last; } public static int BinarySearchInsert<T>(IVirtualArray<T> array, int index, int length, Func<T, int> func) { int lo = index; int hi = index + length - 1; int insert = lo; while( lo <= hi ) { int mid = lo + ( ( hi - lo ) >> 1 ); int result = func( array[mid] ); if( result <= 0 ) { lo = mid + 1; insert = lo; } else { hi = mid - 1; } } return insert; } public static void Sort<T>(IVirtualArray<T> array, int index, int length, Func<T, T, int> func) { QuickSort( array, index, index + ( length - 1 ), func ); } private static void QuickSort<T>(IVirtualArray<T> array, int left, int right, Func<T, T, int> func) { do { int i = left; int j = right; T x = array[ i + ( ( j - i ) >> 1 ) ]; do { while( func( array[ i ], x ) < 0 ) { i++; } while( func( x, array[ j ] ) < 0 ) { j--; } if( i > j ) { break; } if( i < j ) { T key = array[ i ]; array[ i ] = array[ j ]; array[ j ] = key; } i++; j--; } while( i <= j ); if( j - left <= right - i ) { if( left < j ) { QuickSort( array, left, j, func ); } left = i; } else { if( i < right ) { QuickSort( array, i, right, func ); } right = j; } } while( left < right ); } }
IVirtualArrayを実装してget/setでインデックスに対する実際のデータの解決を実装すれば、VirtualArrayUtilを通じてソートやサーチができるようになるという感じ。
Array.Sortだと一端配列につめる必要があるけど、IVirtualArrayなら必要に応じて実際のデータを解決すれば済むというのがやりたいことです(・ω・)