Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Java programming question Need help with question: C 8.47 C 8.47: To implement the preorder method of the AbstractTree class, we relied on the convenience of creating a snapshot. Reimplement a preorder method that creates a lazy iterator. (See Section 7.4.2 for discussion of iterators

Java programming question Need help with question: C 8.47 C 8.47: To implement the preorder method of the AbstractTree class, we relied on the convenience of creating a snapshot. Reimplement a preorder method that creates a lazy iterator. (See Section 7.4.2 for discussion of iterators

C++ Programming: From Problem Analysis to Program Design
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter17: Linked Lists
Section: Chapter Questions
Problem 10PE
See similar textbooks
icon
Related questions
Question

Java programming question

Need help with question: C 8.47

C 8.47: To implement the preorder method of the AbstractTree class, we relied on the convenience of creating a snapshot. Reimplement a preorder method that creates a lazy iterator. (See Section 7.4.2 for discussion of iterators.)

7.4. Iterators 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 11- nested ArrayIterator class /** * A (nonstatic) inner class. Note well that each instance contains an implicit * reference to the containing list, allowing it to access the list's members. */ private class ArrayIterator implements Iterator<E> { private int j = 0; private boolean removable = false; // index of the next element to report // can remove be called at this time? ** * Tests whether the iterator has a next object. * @return true if there are further objects, false otherwise */ public boolean hasNext() { return j < size; } // size is field of outer instance /** * Returns the next object in the iterator. * * @return next object * @throws NoSuch Element Exception if there are no further elements */ public E next() throws NoSuch Element Exception { if (j == size) throw new NoSuch ElementException("No next element"); removable = true; // this element can subsequently be removed return data[j++]; // post-increment j, so it is ready for future call to next } 285 ** * Removes the element returned by most recent call to next. * @throws IllegalStateException if next has not yet been called * @throws IllegalStateException if remove was already called since recent next j--; removable = false; public void remove() throws IllegalStateException { if (!removable) throw new IllegalStateException("nothing to remove"); ArrayList.this.remove(j-1); // that was the last one returned // next element has shifted one cell to the left // do not allow remove again until next is called } }//- end of nested ArrayIterator class /** Returns an iterator of the elements stored in the list. */ public Iterator<E> iterator() { return new Arraylterator(); // create a new instance of the inner class } Code Fragment 7.13: Code providing support for ArrayList iterators. (This should be nested within the ArrayList class definition of Code Fragments 7.2 and 7.3.)
Transcribed Image Text:7.4. Iterators 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 11- nested ArrayIterator class /** * A (nonstatic) inner class. Note well that each instance contains an implicit * reference to the containing list, allowing it to access the list's members. */ private class ArrayIterator implements Iterator<E> { private int j = 0; private boolean removable = false; // index of the next element to report // can remove be called at this time? ** * Tests whether the iterator has a next object. * @return true if there are further objects, false otherwise */ public boolean hasNext() { return j < size; } // size is field of outer instance /** * Returns the next object in the iterator. * * @return next object * @throws NoSuch Element Exception if there are no further elements */ public E next() throws NoSuch Element Exception { if (j == size) throw new NoSuch ElementException("No next element"); removable = true; // this element can subsequently be removed return data[j++]; // post-increment j, so it is ready for future call to next } 285 ** * Removes the element returned by most recent call to next. * @throws IllegalStateException if next has not yet been called * @throws IllegalStateException if remove was already called since recent next j--; removable = false; public void remove() throws IllegalStateException { if (!removable) throw new IllegalStateException("nothing to remove"); ArrayList.this.remove(j-1); // that was the last one returned // next element has shifted one cell to the left // do not allow remove again until next is called } }//- end of nested ArrayIterator class /** Returns an iterator of the elements stored in the list. */ public Iterator<E> iterator() { return new Arraylterator(); // create a new instance of the inner class } Code Fragment 7.13: Code providing support for ArrayList iterators. (This should be nested within the ArrayList class definition of Code Fragments 7.2 and 7.3.)
7.4.2 Implementing Iterators There are two general styles for implementing iterators that differ in terms of what work is done when the iterator instance is first created, and what work is done each time the iterator is advanced with a call to next(). A snapshot iterator maintains its own private copy of the sequence of elements, which is constructed at the time the iterator object is created. It effectively records a "snapshot" of the sequence of elements at the time the iterator is created, and is therefore unaffected by any subsequent changes to the primary collection that may occur. Implementing snapshot iterators tends to be very easy, as it requires a simple traversal of the primary structure. The downside of this style of iterator is that it requires O(n) time and O(n) auxiliary space, upon construction, to copy and store a collection of n elements. A lazy iterator is one that does not make an upfront copy, instead perform- ing a piecewise traversal of the primary structure only when the next() method is called to request another element. The advantage of this style of iterator is that it can typically be implemented so the iterator requires only O(1) space and O(1) construction time. One downside (or feature) of a lazy iterator is that its behavior is affected if the primary structure is modified (by means other than by the itera- tor's own remove method) before the iteration completes. Many of the iterators in Java's libraries implement a “fail-fast” behavior that immediately invalidates such an iterator if its underlying collection is modified unexpectedly. We will demonstrate how to implement iterators for both the ArrayList and Linked Positional List classes as examples. We implement lazy iterators for both, including support for the remove operation (but without any fail-fast guarantee). Iterations with the ArrayList class We begin by discussing iteration for the ArrayList<E> class. We will have it im- plement the Iterable<E> interface. (In fact, that requirement is already part of Java's List interface.) Therefore, we must add an iterator() method to that class definition, which returns an instance of an object that implements the Iterator<E> interface. For this purpose, we define a new class, Arraylterator, as a nonstatic nested class of ArrayList (i.e., an inner class, as described in Section 2.6). The advantage of having the iterator as an inner class is that it can access private fields (such as the array A) that are members of the containing list. Our implementation is given in Code Fragment 7.13. The iterator() method of ArrayList returns a new instance of the inner Arraylterator class. Each iterator maintains a field j that represents the index of the next element to be returned. It is initialized to 0, and when j reaches the size of the list, there are no more elements to return. In order to support element removal through the iterator, we also maintain a boolean variable that denotes whether a call to remove is currently permissible.
Transcribed Image Text:7.4.2 Implementing Iterators There are two general styles for implementing iterators that differ in terms of what work is done when the iterator instance is first created, and what work is done each time the iterator is advanced with a call to next(). A snapshot iterator maintains its own private copy of the sequence of elements, which is constructed at the time the iterator object is created. It effectively records a "snapshot" of the sequence of elements at the time the iterator is created, and is therefore unaffected by any subsequent changes to the primary collection that may occur. Implementing snapshot iterators tends to be very easy, as it requires a simple traversal of the primary structure. The downside of this style of iterator is that it requires O(n) time and O(n) auxiliary space, upon construction, to copy and store a collection of n elements. A lazy iterator is one that does not make an upfront copy, instead perform- ing a piecewise traversal of the primary structure only when the next() method is called to request another element. The advantage of this style of iterator is that it can typically be implemented so the iterator requires only O(1) space and O(1) construction time. One downside (or feature) of a lazy iterator is that its behavior is affected if the primary structure is modified (by means other than by the itera- tor's own remove method) before the iteration completes. Many of the iterators in Java's libraries implement a “fail-fast” behavior that immediately invalidates such an iterator if its underlying collection is modified unexpectedly. We will demonstrate how to implement iterators for both the ArrayList and Linked Positional List classes as examples. We implement lazy iterators for both, including support for the remove operation (but without any fail-fast guarantee). Iterations with the ArrayList class We begin by discussing iteration for the ArrayList<E> class. We will have it im- plement the Iterable<E> interface. (In fact, that requirement is already part of Java's List interface.) Therefore, we must add an iterator() method to that class definition, which returns an instance of an object that implements the Iterator<E> interface. For this purpose, we define a new class, Arraylterator, as a nonstatic nested class of ArrayList (i.e., an inner class, as described in Section 2.6). The advantage of having the iterator as an inner class is that it can access private fields (such as the array A) that are members of the containing list. Our implementation is given in Code Fragment 7.13. The iterator() method of ArrayList returns a new instance of the inner Arraylterator class. Each iterator maintains a field j that represents the index of the next element to be returned. It is initialized to 0, and when j reaches the size of the list, there are no more elements to return. In order to support element removal through the iterator, we also maintain a boolean variable that denotes whether a call to remove is currently permissible.
Expert Solution
steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Binomial Heap
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
SEE MORE TEXTBOOKS