Why is this while loop stuck in infinite loop?
I'm working on a hybrid data structure that is an ordered double-linked list where each node contains an array[] of SIZE. My difficulty is the add method.
Using unit testing provided by the professor, a test string is broken up into individual characters and added to the list using a provided comparator. The default test is abcdefghijklmnopqrstuvwxyzaeiou
The add method I wrote adds the first item fine, but it doesn't advance past that character. Since the test works for other students in the class, it must be my code screwing things up.
The code I came up with is
boolean add(E item){
Chunk<E> currentNode= head; //set lookup node to the head
if (size==0) {
//new chunk, connect it with head
Chunk<E> newNode= new Chunk<E>();
newNode.next= head;
newNode.prev=head;
head.next= newNode;
head.prev= newNode;
//add item and update counters
ll.insertItem(newNode, item);
size++;
//System.out.println(currentNode.items[0]);
}
else {
if (currentNode.next== head) {
ll.insertItem(currentNode, item);
}
while (currentNode.next != head) {
currentNode= currentNode.next;
System.out.println(currentNode.items[0]);
//if the add item is less than first item, move to previous node
if (comp.compare(item, currentNode.items[0])<0)
currentNode= currentNode.prev;
//if item fits within a chunk
if (comp.compare(item, currentNode.items[0])> 0 &&
comp.compare(item, currentNode.items[currentNode.numUsed-1])<0) {
ll.insertItem(currentNode, item);
//otherwise, move search onto next node
} else {
currentNode= currentNode.next;
}
}
}
return true;
}
ll.insertItem is a helper method in a nested class that determines which location in the array to insert the item, and if the array is full, splits the node into two nodes, copying the latter half of the old node to the new, then adds the item to the appropriate node.I implemented it as
public void insertItem(Chunk<E> node, E item) {
if(node.numUsed==0) {
node.items[0]=item;
node.numUsed++;
}else if (开发者_如何学Gonode.numUsed<chunkSize) {
for (int i=0; i<=node.numUsed; i++) {
if (comp.compare(item, node.items[i])>0) {
for (int j= node.numUsed; j>i; j--) {
node.items[j+1]= node.items[j];
}
node.items[i]= item;
node.numUsed++;
}
}
} else {
//make new chunk, determine which chunk item should be added
Chunk<E> newChunk= newChunk(node);
size++;
//if item fits in new node
if (comp.compare(item, newChunk.items[0])>0) {
insertItem(newChunk, item);
} else {
insertItem(node, item); //item fits in old node
}
}
}
WHat I'm not getting is why this is stuck in an infinite loop, especially on the first character of the test string. Since the if (size==0)
conditional executes, why is the code repeating adding the a character?
Addenum- Requested by RD
System.out.println("insertion order: "+order);
Comparator<String> comp = new StringCmp();
((CmpCnt)comp).resetCmpCnt(); // reset the counter inside the comparator
ChunkList<String> clist = new ChunkList<String>(comp);
for (int i = 0; i < order.length(); i++){
String s = order.substring(i, i+1);
clist.add(s);
}
You are not incrementing numUsed after adding the first item
this:
if(node.numUsed==0) {
node.items[0]=item;
}
should be:
if(node.numUsed==0) {
node.items[0]=item;
node.numUsed++;
}
精彩评论