0

在我进行测试时,我发现了我的代码中的错误。

我很难找到我的Deque迭代器出了什么问题。它没有正确迭代,我不知道如何修复它。我已经包含了失败测试的屏幕截图和我完成的代码。

附注:我的教授希望迭代器在向前迭代或反向迭代时从头部出列元素,这就是为什么迭代器更难弄清楚的原因。

失败的单元测试截图: https ://imgur.com/a/srlmrNQ

非常感谢你的帮助!

完整的源代码:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<E> implements Iterable<E>
{
    private class DequeNode<E>
    {
        private DequeNode<E> _next;
        private DequeNode<E> _previous;
        private E _data;

        private DequeNode(E data)
        {
            _data = data;
        }
    }

    private DequeNode<E> _head;
    private DequeNode<E> _tail;
    private int _depth;
    private static final int EXCLUSIVE_INDEX_START = -1;


    public Deque()
    {
        _head = null;
        _tail = null;
        _depth = 0;
    }

    public boolean enqueue(E element) // This is INSERTION at the TAIL //TODO: DONE!!
    {
        DequeNode<E> newNode = new DequeNode<E>(element);

        if (isEmpty())
        {
            _head = newNode;
        }
        else
        {
            _tail._next = newNode;
            newNode._previous = _tail;
        }
        _tail = newNode;
        _depth++;

        return true;
    }

    public void enqueueAll(Iterable<E> elements)
    {
        for (E eachElement : elements)
        {
            enqueue(eachElement);
        }
    }

    public boolean enqueueHead(E element) // This is insertion at the head //TODO: DONE!!
    {
        DequeNode<E> newNode = new DequeNode<E>(element);

        if (isEmpty())
        {
            _tail = newNode;
        }
        else
        {
            _head._previous = newNode;
            newNode._next = _head;
        }
        _head = newNode;
        _depth++;

        return true;
    }

    public E head()
    {
        checkForStackUnderflow();
        return _head._data;
    }

    public E tail()
    {
        checkForStackUnderflow();
        return _tail._data;
    }

    public E dequeue() // This is removal at the head //TODO: DONE!!
    {
        checkForStackUnderflow();

        E removed = _head._data;

        if (_head._next == null)
        {
            _tail = null;
        }
        else
        {
            _head._next._previous = null;
        }
        _head = _head._next;
        _depth--;

        return removed;
    }

    public E dequeueTail() // This is removal at the tail //TODO: DONE!!
    {
        checkForStackUnderflow();

        E removed = _tail._data;

        if (_head._next == null)
        {
            _head = null;
        }
        else
        {
            _tail._previous._next = null;
        }
        _tail = _tail._previous;
        _depth--;

        return removed;
    }

    public void clear()
    {
        _head = _tail = null;
        _depth = 0;
    }

    public int depth()
    {
        return _depth;
    }

    public boolean isEmpty()
    {
        return _depth == 0;
    }

    public Iterator<E> iterator()
    {
        return new DequeIterator(this, false);
    }

    public Iterator<E> reverseIterator()
    {
        return new DequeIterator(this, true);
    }

    private void checkForStackUnderflow()
    {
        if (isEmpty())
        {
            throw new NoSuchElementException("Stack underflow captain!!!");
        }
    }

    private class DequeIterator implements Iterator<E>
    {
        // The instance variables used throughout the program.
        private int _index;
        private Deque<E> _theList;
        private DequeNode<E> _current;
        private boolean _iterateReverse;


        public DequeIterator(Deque<E> deque, boolean reverse)
        {
            _theList = deque;
            _iterateReverse = reverse;
            _index = 0;
            _current = _head;

            /* If the flag for reverse iteration is detected, then just start
            the index at the end and iterate from the tail.
             */
            if (reverse)
            {
                _index = _theList._depth - 1;
                _current = _theList._tail;
            }
        }

        public boolean hasNext()
        {
            boolean results;

            // If we are reverse iterating check if the index is > than -1.
            if (_iterateReverse)
            {
                results = _index > EXCLUSIVE_INDEX_START;
            }
            /* Getting here means that we are forward iterating so check if the
            index is less than size AKA if we have more elements to go through.
             */
            else
            {
                results = _index < _theList._depth;
            }
            return  results;
        }


        public E next()
        {
            // If we don't have more elements to iterate through then we throw.
            if (!hasNext())
            {
                throw new NoSuchElementException();
            }
            // Update the current to descent if we are reverse iterating.
            if (_iterateReverse)
            {
                _current = _current._previous;
                _index--;
            }
            // If we get to here then just update the current value forward.
            else
            {
                _current = _current._next;
                _index++;
            }

            return dequeue();
        }
    }
}
4

1 回答 1

1

由于代码在每次迭代中更新索引值并在迭代的每次出队操作中减小深度值,因此出现了深度小于索引值的用例,因此返回了不正确的 hasNext() 值(这似乎是所有失败的测试场景的根本原因)。

实现 hasNext() 的简单方法如下:

返回_theList._depth > 0;

这将适用于上述用例,因为在每个 next() 操作中都会执行 dequeue() 操作(这会降低深度值)。

于 2019-11-05T14:07:44.693 回答