インデックスのあるソート済みコレクションなどなど

こすげです。

今朝方、Javaでプログラムを作っていて、インデックスのある（要は先頭からn番目とか言ってサクッとn番目の要素にアクセスできるってことね）ソート済みコレクションを内包したコンテナ・クラスを作る必要が出てきました。しかもコレクションの対象となるクラスは、抽象クラスでコンパレータ（クラスのインスタンスの大小を比較するためのメソッド）は純粋仮想メソッドというおまけつき（笑。あ、もちろん、実際にコレクションに入れるのは、コンパレータを実装したサブクラスになります。
人から聞かれたら「んなもん、ねーから、作れ」という所なんですが、これは自分のことなんで、『作れ」といっても、だれも作ってくれない。で、作る訳なんですけど、なるべく楽をしたい訳です。
まーず、キーなんかはいらないんで、インデックスのあるコレクションを元にするか、ソート済みのコレクションを元にするか、要は、List系かSet系（と言っても、使える実装はTreeSetしかねーじゃん）のどっちか何ですけどね。

ここからは、朝の通勤途中、電車内で、寝て電車が揺れることに寄りかかってくるおねーちゃんを肘で小突きながら考えたこと（笑
ここで、ソート済みになるSetの実装がTreeしかないってのが、極めて問題でして。。。わかっている人は分かっているんだと思いますが、Tree構造ってのは左右のバランスが取れてないととても効率が悪いというか、単なるLinkedListになっちゃうわけです。
特に今回、コレクションに突っ込むデータは、ファイルに格納されていて、実は目的とは逆順にソートされている（絶対ではない経験上）。極端な話、読み込んで逆順に並べ替えてやればＯＫというか、まあ、仕様上目的と逆順にソートされている保証はないので、ソートしますけど。こんなデータ、Treeに読み込んだら。。。あわわ、アンバランスな木構造をバランスの取れた木構造に直すことはできますけど、Javaの、TreeSet にそんな実装入っているのかなぁ・・・。
なぁんで、擬似インデックスを作って、「こいつの１コ前は」とか「こいつの６コ前は」とか、配列変数感覚でガンガン、アクセスするのはちょいとはばかられる、というか、年寄りは怖くてできない訳です。

あ、擬似インデックスはこんな感じで作ろうかと（笑

// datas means target Set Collection public E get(int index) throws IndexOutOfBoundsException { E obj = null; if (0 <= index && index < datas.size()) { Iterator it = datas.iterator(); for (int i = 0; i <= index; i++) { obj = it.next(); } } else { throw new IndexOutOfBoundsException(); } return obj; }

そこで、しつこく寄っかかってくるおねーちゃんを、ひとしきり、肘でさみだれ突きをして、「やっぱぁ、ArrayListだんべや」って覚悟を決めちゃった訳です。 まぁ、たーしか、Collectionsに、sortとか、binarySearch とかあったし・・・ で、ここからは、学生に課題をやらせながら考えたこと まっ、sortはいいでしょ、コンパレータ渡すだけだしね。で問題は、binarySearch なんですね。あ、いい忘れてましたけど、要素での検索も必要なんですね。今回のプログラムでは。で、

binarySearch(List<? extends Comparable<? super T>> list, T key) 

こいつも

binarySearch(List<? extends T> list, T key, Comparator<? super T> c) 

こいつも、keyを渡しとるやんけ。。。なめんなよ、ワレ、T は、abstract だっていうとるやないけ（笑 で、ここで、性格が実装ににじみ出てくる訳でして（笑。結局、以下参照（大爆笑

// search by date: String // UnSortedArrayException is my defined. public int execSearch(String date) throws UnSortedArrayException { int result = -1; if (sorted) { int lower = 0; int upper = datas.size() - 1; int mid, judge; while (lower < upper) { mid = (lower + upper)/2; judge = date.compareTo(datas.get(mid).getDate()); if (judge < 0) { upper = mid - 1; } else if (0 < judge) { lower = mid + 1; } else { result = mid; break; } } } else { throw new UnSortedArrayException(); } return result; }

「老兵は死なず、ただ醜態を晒すのみ」

Ｑ. 先生しつもんです。タイトルの最後に「などなど」って書いてありますけど、どれが「など」なんですか？
Ａ. それは大人の事情なんで、質問してはいけません