Module org.dyn4j
Package org.dyn4j

Class BinarySearchTreeIterator<E extends java.lang.Comparable<E>>

  • Type Parameters:
    E - the comparable type
    All Implemented Interfaces:
    java.util.Iterator<E>

    final class BinarySearchTreeIterator<E extends java.lang.Comparable<E>>
    extends java.lang.Object
    implements java.util.Iterator<E>
    An iterator class for looping through the elements of a BinarySearchTree in order or in reverse order.

    The remove() method is unsupported.

    Since:
    2.2.0
    Version:
    3.2.3
    Author:
    William Bittle
    • Field Detail

      • stack

        final java.util.Deque<BinarySearchTreeNode<E extends java.lang.Comparable<E>>> stack
        The node stack for iterative traversal
      • from

        final E extends java.lang.Comparable<E> from
        The value to start iteration from; can be null
      • to

        final E extends java.lang.Comparable<E> to
        The value to end iteration; can be null
      • inOrder

        final boolean inOrder
        The traversal direction
    • Constructor Detail

      • BinarySearchTreeIterator

        public BinarySearchTreeIterator​(BinarySearchTreeNode<E> root)
        Default constructor using in-order traversal.
        Parameters:
        root - the root node of the subtree to traverse
        Throws:
        java.lang.NullPointerException - if node is null
      • BinarySearchTreeIterator

        public BinarySearchTreeIterator​(BinarySearchTreeNode<E> root,
                                        boolean inOrder)
        Full constructor.
        Parameters:
        root - the root node of the subtree to traverse
        inOrder - true to iterate in-order, false to iterate reverse order
        Throws:
        java.lang.NullPointerException - if node is null
      • BinarySearchTreeIterator

        public BinarySearchTreeIterator​(BinarySearchTreeNode<E> root,
                                        E from,
                                        E to)
        Full constructor.
        Parameters:
        root - the root node of the subtree to traverse
        from - the value to start iterating from (inclusive)
        to - the value to stop iterating after (inclusive)
        Throws:
        java.lang.NullPointerException - if node is null
        Since:
        3.2.3
    • Method Detail

      • pushLeftFrom

        protected void pushLeftFrom​(E from)
        Pushes the required nodes onto the stack to begin iterating nodes in order starting from the given value.
        Parameters:
        from - the value to start iterating from
        Since:
        3.2.3
      • pushLeft

        protected void pushLeft​(BinarySearchTreeNode<E> node)
        Pushes the left most nodes of the given subtree onto the stack.
        Parameters:
        node - the root node of the subtree
      • pushRight

        protected void pushRight​(BinarySearchTreeNode<E> node)
        Pushes the right most nodes of the given subtree onto the stack.
        Parameters:
        node - the root node of the subtree
      • hasNext

        public boolean hasNext()
        Specified by:
        hasNext in interface java.util.Iterator<E extends java.lang.Comparable<E>>
      • next

        public E next()
        Specified by:
        next in interface java.util.Iterator<E extends java.lang.Comparable<E>>
      • remove

        public void remove()
        Currently unsupported.
        Specified by:
        remove in interface java.util.Iterator<E extends java.lang.Comparable<E>>