かなりの量のコードを実行する必要があるため、誰かが本当にこれを手伝ってくれるかどうかはわかりませんが、どんな助けも大歓迎です。これが私の関連コードです:
public class BTree implements Iterable<String> {
/** Left child */
BTree left;
/** Right Child */
BTree right;
/** Comparator to use for sorting */
Comparator<String> comp;
/** Parent node */
BTree parent;
/** String stored in this leaf */
String s;
/** # of iterators currently working on it */
int active = 0;
/** Size of the BTree */
int size;
public void build(Iterable<String> iter, int numStrings) {
if (this.active > 0) {
throw new ConcurrentModificationException();
}
else {
Iterator<String> itr = iter.iterator();
while (numStrings != 0 && itr.hasNext()) {
String s = itr.next();
if (!this.contains(s)) {
this.insert(s);
this.size++;
numStrings--;
}
}
}
}
/**
* Inserts the string into the given BTree
* @param str - String to insert
*/
private void insert(String str) {
if (this.s.equals("")) {
this.s = str;
}
else if (this.comp.compare(str, this.s) > 0) {
if (this.right == null) {
BTree bt = BTree.binTree(this.comp);
bt.s = str;
this.right = bt;
bt.parent = this;
}
else {
this.right.insert(str);
}
}
else if (this.comp.compare(str, this.s) < 0) {
if (this.left == null) {
BTree bt = BTree.binTree(this.comp);
bt.s = str;
this.left = bt;
bt.parent = this;
}
else {
this.left.insert(str);
}
}
}
private class BTreeIterator implements Iterator<String> {
/** Current BTree being iterated over */
BTree current;
/** How many next() calls have there been */
int count;
/** Size of the BTree */
int max;
/** Constructor for BTreeIterator
* @param current
*/
BTreeIterator(BTree current) {
this.current = current;
this.count = 0;
this.max = current.size;
active++;
}
/** Returns true if there is another string to iterate over
* @return boolean
*/
public boolean hasNext() {
if (this.count != this.max) {
return true;
}
else {
active--;
return false;
}
}
/**
* Returns the next string in the iterator
* @return String
*/
public String next() {
if (this.count == 0) {
this.count++;
current = this.current.getLeftMost();
if (this.current.s.equals("")) {
throw new NoSuchElementException();
}
return this.current.s;
}
else if (this.current.right != null) {
this.current = this.current.right.getLeftMost();
this.count++;
return this.current.s;
}
else {
BTree tree = this.current;
while (tree.parent.right == tree) {
tree = tree.parent;
}
this.current = tree.parent;
this.count++;
return this.current.s;
}
}
/** Throws an exception since we aren't removing anything from the trees
*/
public void remove() {
throw new UnsupportedOperationException();
}
}
}
}
while (tree.parent.right == tree)
イテレータの next() メソッドの行で例外がスローされます。面白いことに、私のコードは、24000 語のファイルを辞書式に並べ替えたり、辞書式に並べ替えたりするコンパレータで問題なく動作しました。次のコンパレータを使用する場合にのみ、例外がスローされます。
class StringWithOutPrefixByLex implements Comparator<String> {
/**
* compares o1 and o2
* @param o1 first String in comparison
* @param o2 second String in comparison
* @return a negative integer, zero, or a positive integer
* as the first argument is less than, equal to, or
* greater than the second.
*/
public int compare(String o1, String o2) {
String s1, s2;
if(o1.length() > 4){
s1 = o1.substring(3);
}
else {
s1 = o1;
}
if(o2.length() > 4){
s2 = o2.substring(3);
}
else {
s2 = o2;
}
return s1.compareTo(s2);
}
}
さらに奇妙なことに、同じファイルに対して 199 語まではそのコンパレーターで問題なく動作しますが、200 語まで構築するとすぐに機能しなくなります。
tree.parent.right
編集: コードがwhile tree.parent
isを参照しようとしているために例外が発生したと判断しましたがnull
、なぜそれをしようとしているのかわかりません。tree.parent
以下の私のコメントで説明されているように、私が知る限り、私のコードは null を呼び出そうとするべきではありません。