9.31 LAB: Iterable 2-3-4 tree In this lab, the Tree234 class is extended to support iteration with an enhanced for loop. Such support is provided via the implementation of an iterator that can iterate through the tree's keys in ascending order. An iterator is an object that maintains a reference to a specific element in a collection and can move to the next element. Ex: A Tree234 iterator references the tree's minimum key upon construction. The iterator can then move to the second to minimum key, then the third to minimum, and so on. Eventually the iterator moves to the last key and can move no further. Overview of Iterable and Iterator in Java Enhanced for loops work on any class that implements the Iterable interface. Tree234 stores a collection of integer keys, so the Tree234 class implements Iterable. Implementing Iterable requires Tree234 to implement the iterator() method, which returns an Iterator. Note the subtle difference in names: Iterable and Iterator. More specifically, the Tree234's iterator() method returns an instance of a class that implements the Iterator interface. The implementing class must implement the Iterator interface's two methods: • . boolean hasNext() returns true if the iterator can move to a larger key, or false if the iterator currently references the tree's maximum key. Integer next() returns the key currently referenced by the iterator and advances to the tree's next key. Step 1: Inspect the Node234.java file Inspect the Node234.java file. Access Node234.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. Node234.java is read only and has a complete implementation of a Node234 class for a 2-3-4 tree node. Fields are protected and so must be accessed through the provided getter and setter methods. Step 2: Inspect the Tree234lterator.java file Inspect the Tree2341terator.java file. The Tree234lterator class is declared, but no fields exist and methods are not implemented. The implementation must satisfy the following requirements: • . The iterator never changes the tree in any way Iteration starts at the tree's minimum key and ends at the maximum Construction occurs in worst-case O(log N) time • hasNext() executes in worst-case O(1) time . next() executes in worst-case O(log N) time • The iterator's space complexity is worst-case O(log N) For simplicity, assume the tree is not changed by an outside source during the iterator's lifetime. Step 3: Understand requirement implications To satisfy the requirements, the iterator must maintain a collection of node references. A node exists in the collection only if that node must be revisited at some point in time. The iterator must visit only the necessary nodes to deliver a key when next() is called. "Visiting" a node means calling any of that node's methods. Ex: Suppose an iterator is built for the tree below and the iterator's next() method is called three times to return keys 5, 10, and 15. The iterator should have only visited the highlighted nodes. Node visited by iterator that has iterated through keys 5, 10, and 15 Node not visited by iterator that has iterated through keys 5, 10, and 15 10 20 30 70 40 50 60 80 90 5 15 25 35 45 55 65 75 85 95 Step 4: Implement the Tree234Iterator class Implement the Tree234lterator to satisfy the complexity requirements mentioned above. Code in LabProgram.java adds random keys to a Tree234 object, then tests that the iterator properly iterates through all keys in ascending order. But time and space complexity aren't tested by LabProgram. LabProgram only ensures that the iterator properly iterates through all keys. Most unit tests will fail if the iterator does not properly iterate through all the tree's keys in the correct order. So run code in develop mode and ensure that the test passes before submitting code.

9.31 LAB: Iterable 2-3-4 tree In this lab, the Tree234 class is extended to support iteration with an enhanced for loop. Such support is provided via the implementation of an iterator that can iterate through the tree's keys in ascending order. An iterator is an object that maintains a reference to a specific element in a collection and can move to the next element. Ex: A Tree234 iterator references the tree's minimum key upon construction. The iterator can then move to the second to minimum key, then the third to minimum, and so on. Eventually the iterator moves to the last key and can move no further. Overview of Iterable and Iterator in Java Enhanced for loops work on any class that implements the Iterable interface. Tree234 stores a collection of integer keys, so the Tree234 class implements Iterable. Implementing Iterable requires Tree234 to implement the iterator() method, which returns an Iterator. Note the subtle difference in names: Iterable and Iterator. More specifically, the Tree234's iterator() method returns an instance of a class that implements the Iterator interface. The implementing class must implement the Iterator interface's two methods: • . boolean hasNext() returns true if the iterator can move to a larger key, or false if the iterator currently references the tree's maximum key. Integer next() returns the key currently referenced by the iterator and advances to the tree's next key. Step 1: Inspect the Node234.java file Inspect the Node234.java file. Access Node234.java by clicking on the orange arrow next to LabProgram.java at the top of the coding window. Node234.java is read only and has a complete implementation of a Node234 class for a 2-3-4 tree node. Fields are protected and so must be accessed through the provided getter and setter methods. Step 2: Inspect the Tree234lterator.java file Inspect the Tree2341terator.java file. The Tree234lterator class is declared, but no fields exist and methods are not implemented. The implementation must satisfy the following requirements: • . The iterator never changes the tree in any way Iteration starts at the tree's minimum key and ends at the maximum Construction occurs in worst-case O(log N) time • hasNext() executes in worst-case O(1) time . next() executes in worst-case O(log N) time • The iterator's space complexity is worst-case O(log N) For simplicity, assume the tree is not changed by an outside source during the iterator's lifetime. Step 3: Understand requirement implications To satisfy the requirements, the iterator must maintain a collection of node references. A node exists in the collection only if that node must be revisited at some point in time. The iterator must visit only the necessary nodes to deliver a key when next() is called. "Visiting" a node means calling any of that node's methods. Ex: Suppose an iterator is built for the tree below and the iterator's next() method is called three times to return keys 5, 10, and 15. The iterator should have only visited the highlighted nodes. Node visited by iterator that has iterated through keys 5, 10, and 15 Node not visited by iterator that has iterated through keys 5, 10, and 15 10 20 30 70 40 50 60 80 90 5 15 25 35 45 55 65 75 85 95 Step 4: Implement the Tree234Iterator class Implement the Tree234lterator to satisfy the complexity requirements mentioned above. Code in LabProgram.java adds random keys to a Tree234 object, then tests that the iterator properly iterates through all keys in ascending order. But time and space complexity aren't tested by LabProgram. LabProgram only ensures that the iterator properly iterates through all keys. Most unit tests will fail if the iterator does not properly iterate through all the tree's keys in the correct order. So run code in develop mode and ensure that the test passes before submitting code.

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 9PE

See similar textbooks