Skip to content

Commit 1c2ddfa

Browse files
mitchellirvinmitchellirvin
committed
Refactored App.java to remove duplicate code and elegantly demonstrate each implementation of the Iterator interface. Removed the redundant ItemIterator interface. Added insert() method to TreeNode class to allow for more elegant construction of BSTs.
1 parent 3e0cfa5 commit 1c2ddfa

File tree

18 files changed

+406
-432
lines changed

18 files changed

+406
-432
lines changed

‎iterator/etc/bst.jpg

75.6 KB
Loading

‎iterator/etc/bst.png

-99.2 KB
Binary file not shown.

‎iterator/pom.xml

Lines changed: 0 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -48,11 +48,5 @@
4848
<artifactId>junit-jupiter-params</artifactId>
4949
<scope>test</scope>
5050
</dependency>
51-
<dependency>
52-
<groupId>org.junit.platform</groupId>
53-
<artifactId>junit-platform-runner</artifactId>
54-
<version>1.2.0</version>
55-
<scope>test</scope>
56-
</dependency>
5751
</dependencies>
5852
</project>

‎iterator/src/main/java/com/iluwatar/iterator/App.java

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
/**
2+
* The MIT License Copyright (c) 2014-2016 Ilkka Seppälä
3+
*
4+
* Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
5+
* associated documentation files (the "Software"), to deal in the Software without restriction,
6+
* including without limitation the rights to use, copy, modify, merge, publish, distribute,
7+
* sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
8+
* furnished to do so, subject to the following conditions:
9+
*
10+
* The above copyright notice and this permission notice shall be included in all copies or
11+
* substantial portions of the Software.
12+
*
13+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
14+
* NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
15+
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
16+
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
17+
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18+
*/
19+
package com.iluwatar.iterator;
20+
21+
import static com.iluwatar.iterator.list.ItemType.ANY;
22+
import static com.iluwatar.iterator.list.ItemType.POTION;
23+
import static com.iluwatar.iterator.list.ItemType.RING;
24+
import static com.iluwatar.iterator.list.ItemType.WEAPON;
25+
26+
import com.iluwatar.iterator.bst.BstIterator;
27+
import com.iluwatar.iterator.bst.TreeNode;
28+
import com.iluwatar.iterator.list.ItemType;
29+
import com.iluwatar.iterator.list.TreasureChest;
30+
import org.slf4j.Logger;
31+
import org.slf4j.LoggerFactory;
32+
33+
/**
34+
* The Iterator pattern is a design pattern in which an iterator is used to traverse a container and
35+
* access the container's elements. The Iterator pattern decouples algorithms from containers.
36+
* <p>
37+
* In this example the Iterator ({@link Iterator}) adds abstraction layer on top of a collection
38+
* ({@link TreasureChest}). This way the collection can change its internal implementation without
39+
* affecting its clients.
40+
*/
41+
public class App {
42+
43+
private static final Logger LOGGER = LoggerFactory.getLogger(App.class);
44+
45+
private static final TreasureChest TREASURE_CHEST = new TreasureChest();
46+
47+
private static void demonstrateTreasureChestIteratorForType(ItemType itemType) {
48+
LOGGER.info("------------------------");
49+
LOGGER.info("Item Iterator for ItemType " + itemType + ": ");
50+
Iterator itemIterator = TREASURE_CHEST.iterator(itemType);
51+
while (itemIterator.hasNext()) {
52+
LOGGER.info(itemIterator.next().toString());
53+
}
54+
}
55+
56+
private static void demonstrateBstIterator() {
57+
LOGGER.info("------------------------");
58+
LOGGER.info("BST Iterator: ");
59+
TreeNode<Integer> root = buildIntegerBst();
60+
BstIterator bstIterator = new BstIterator<>(root);
61+
while (bstIterator.hasNext()) {
62+
LOGGER.info("Next node: " + bstIterator.next().getVal());
63+
}
64+
}
65+
66+
private static TreeNode<Integer> buildIntegerBst() {
67+
TreeNode<Integer> root = new TreeNode<>(8);
68+
69+
root.insert(3);
70+
root.insert(10);
71+
root.insert(1);
72+
root.insert(6);
73+
root.insert(14);
74+
root.insert(4);
75+
root.insert(7);
76+
root.insert(13);
77+
78+
return root;
79+
}
80+
81+
/**
82+
* Program entry point
83+
*
84+
* @param args command line args
85+
*/
86+
public static void main(String[] args) {
87+
demonstrateTreasureChestIteratorForType(RING);
88+
demonstrateTreasureChestIteratorForType(POTION);
89+
demonstrateTreasureChestIteratorForType(WEAPON);
90+
demonstrateTreasureChestIteratorForType(ANY);
91+
92+
demonstrateBstIterator();
93+
}
94+
}

‎iterator/src/main/java/com/iluwatar/iterator/interfaces/Iterator.java renamed to ‎iterator/src/main/java/com/iluwatar/iterator/Iterator.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@
1616
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1717
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1818
*/
19-
package com.iluwatar.iterator.interfaces;
19+
package com.iluwatar.iterator;
2020

2121
/**
2222
* Iterator interface to be implemented by iterators over various data structures

‎iterator/src/main/java/com/iluwatar/iterator/binarysearchtree/BstIterator.java

Lines changed: 0 additions & 78 deletions
This file was deleted.

‎iterator/src/main/java/com/iluwatar/iterator/binarysearchtree/TreeNode.java

Lines changed: 0 additions & 66 deletions
This file was deleted.

‎iterator/src/main/java/com/iluwatar/iterator/bst/BstIterator.java

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
/**
2+
* The MIT License Copyright (c) 2014-2016 Ilkka Seppälä
3+
*
4+
* Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
5+
* associated documentation files (the "Software"), to deal in the Software without restriction,
6+
* including without limitation the rights to use, copy, modify, merge, publish, distribute,
7+
* sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
8+
* furnished to do so, subject to the following conditions:
9+
*
10+
* The above copyright notice and this permission notice shall be included in all copies or
11+
* substantial portions of the Software.
12+
*
13+
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
14+
* NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
15+
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
16+
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
17+
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18+
*/
19+
package com.iluwatar.iterator.bst;
20+
21+
import com.iluwatar.iterator.Iterator;
22+
import java.util.ArrayDeque;
23+
import java.util.NoSuchElementException;
24+
25+
/**
26+
* An in-order implementation of a BST Iterator. For example, given a BST with Integer values,
27+
* expect to retrieve TreeNodes according to the Integer's natural ordering (1, 2, 3...)
28+
*
29+
* @param <T> This Iterator has been implemented with generic typing to allow for TreeNodes of
30+
* different value types
31+
*/
32+
public class BstIterator<T extends Comparable<T>> implements Iterator<TreeNode<T>> {
33+
34+
private ArrayDeque<TreeNode<T>> pathStack;
35+
36+
public BstIterator(TreeNode<T> root) {
37+
pathStack = new ArrayDeque<>();
38+
pushPathToNextSmallest(root);
39+
}
40+
41+
/**
42+
* This BstIterator manages to use O(h) extra space, where h is the height of the tree It achieves
43+
* this by maintaining a stack of the nodes to handle (pushing all left nodes first), before
44+
* handling self or right node
45+
*
46+
* @param node TreeNode that acts as root of the subtree we're interested in.
47+
*/
48+
private void pushPathToNextSmallest(TreeNode<T> node) {
49+
while (node != null) {
50+
pathStack.push(node);
51+
node = node.getLeft();
52+
}
53+
}
54+
55+
/**
56+
* @return true if this iterator has a "next" element
57+
*/
58+
@Override
59+
public boolean hasNext() {
60+
return !pathStack.isEmpty();
61+
}
62+
63+
/**
64+
* @return TreeNode next. The next element according to our in-order traversal of the given BST
65+
* @throws NoSuchElementException if this iterator does not have a next element
66+
*/
67+
@Override
68+
public TreeNode<T> next() throws NoSuchElementException {
69+
if (pathStack.isEmpty()) {
70+
throw new NoSuchElementException();
71+
}
72+
TreeNode<T> next = pathStack.pop();
73+
pushPathToNextSmallest(next.getRight());
74+
return next;
75+
}
76+
77+
}

‎iterator/src/main/java/com/iluwatar/iterator/binarysearchtree/README.md renamed to ‎iterator/src/main/java/com/iluwatar/iterator/bst/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ this iterator will return nodes according to "In Order" binary tree traversal.
99
This means that given a binary search tree like the following, the iterator would
1010
return values in order: 1, 3, 4, 6, 7, 8, 10, 13, 14.
1111

12-
![BST](../../../../../../../etc/bst.png "Binary Search Tree")
12+
![BST](../../../../../../../etc/bst.jpg "Binary Search Tree")
1313

1414
### How It's Done
1515
**The trivial solution** to a binary search tree iterator would be to construct a List (or similar

0 commit comments

Comments
 (0)