开发者

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++;
        }
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜