Skip to content

Commit 038befe

Browse files
npathainpathai
authored
Merge pull request iluwatar#779 from mitchellirvin/bst-iterator
iluwatar#778: Binary Search Tree Iterator
2 parents 74f3799 + 8458e42 commit 038befe

File tree

15 files changed

+572
-179
lines changed

15 files changed

+572
-179
lines changed

‎iterator/etc/bst.jpg

75.6 KB
Loading

‎iterator/etc/iterator.ucls

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
<?xml version="1.0" encoding="UTF-8"?>
22
<class-diagram version="1.1.8" icons="true" automaticImage="PNG" always-add-relationships="false" generalizations="true"
33
realizations="true" associations="true" dependencies="false" nesting-relationships="true">
4-
<class id="1" language="java" name="com.iluwatar.iterator.TreasureChest" project="iterator"
4+
<class id="1" language="java" name="com.iluwatar.iterator.list.TreasureChest" project="iterator"
55
file="/iterator/src/main/java/com/iluwatar/iterator/TreasureChest.java" binary="false" corner="BOTTOM_RIGHT">
66
<position height="124" width="195" x="1" y="237"/>
77
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -10,7 +10,7 @@
1010
<operations public="true" package="true" protected="true" private="true" static="true"/>
1111
</display>
1212
</class>
13-
<class id="2" language="java" name="com.iluwatar.iterator.Item" project="iterator"
13+
<class id="2" language="java" name="com.iluwatar.iterator.list.Item" project="iterator"
1414
file="/iterator/src/main/java/com/iluwatar/iterator/Item.java" binary="false" corner="BOTTOM_RIGHT">
1515
<position height="160" width="157" x="195" y="401"/>
1616
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -19,7 +19,7 @@
1919
<operations public="true" package="true" protected="true" private="true" static="true"/>
2020
</display>
2121
</class>
22-
<enumeration id="3" language="java" name="com.iluwatar.iterator.ItemType" project="iterator"
22+
<enumeration id="3" language="java" name="com.iluwatar.iterator.list.ItemType" project="iterator"
2323
file="/iterator/src/main/java/com/iluwatar/iterator/ItemType.java" binary="false" corner="BOTTOM_RIGHT">
2424
<position height="160" width="145" x="388" y="601"/>
2525
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -28,7 +28,7 @@
2828
<operations public="true" package="true" protected="true" private="true" static="true"/>
2929
</display>
3030
</enumeration>
31-
<interface id="4" language="java" name="com.iluwatar.iterator.ItemIterator" project="iterator"
31+
<interface id="4" language="java" name="com.iluwatar.iterator.list.ItemIterator" project="iterator"
3232
file="/iterator/src/main/java/com/iluwatar/iterator/ItemIterator.java" binary="false" corner="BOTTOM_RIGHT">
3333
<position height="106" width="131" x="236" y="237"/>
3434
<display autosize="true" stereotype="true" package="true" initial-value="false" signature="true"
@@ -37,7 +37,7 @@
3737
<operations public="true" package="true" protected="true" private="true" static="true"/>
3838
</display>
3939
</interface>
40-
<class id="5" language="java" name="com.iluwatar.iterator.TreasureChestItemIterator" project="iterator"
40+
<class id="5" language="java" name="com.iluwatar.iterator.list.TreasureChestItemIterator" project="iterator"
4141
file="/iterator/src/main/java/com/iluwatar/iterator/TreasureChestItemIterator.java" binary="false"
4242
corner="BOTTOM_RIGHT">
4343
<position height="160" width="323" x="236" y="37"/>

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

Lines changed: 63 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -1,76 +1,95 @@
11
/**
2-
* The MIT License
3-
* Copyright (c) 2014-2016 Ilkka Seppälä
2+
* The MIT License Copyright (c) 2014-2016 Ilkka Seppälä
43
*
5-
* Permission is hereby granted, free of charge, to any person obtaining a copy
6-
* of this software and associated documentation files (the "Software"), to deal
7-
* in the Software without restriction, including without limitation the rights
8-
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9-
* copies of the Software, and to permit persons to whom the Software is
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
108
* furnished to do so, subject to the following conditions:
119
*
12-
* The above copyright notice and this permission notice shall be included in
13-
* all copies or substantial portions of the Software.
10+
* The above copyright notice and this permission notice shall be included in all copies or
11+
* substantial portions of the Software.
1412
*
15-
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16-
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17-
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18-
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19-
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20-
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21-
* THE SOFTWARE.
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.
2218
*/
2319
package com.iluwatar.iterator;
2420

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.Item;
29+
import com.iluwatar.iterator.list.ItemType;
30+
import com.iluwatar.iterator.list.TreasureChest;
2531
import org.slf4j.Logger;
2632
import org.slf4j.LoggerFactory;
2733

2834
/**
29-
*
3035
* The Iterator pattern is a design pattern in which an iterator is used to traverse a container and
3136
* access the container's elements. The Iterator pattern decouples algorithms from containers.
3237
* <p>
33-
* In this example the Iterator ({@link ItemIterator}) adds abstraction layer on top of a collection
38+
* In this example the Iterator ({@link Iterator}) adds abstraction layer on top of a collection
3439
* ({@link TreasureChest}). This way the collection can change its internal implementation without
3540
* affecting its clients.
36-
*
3741
*/
3842
public class App {
3943

4044
private static final Logger LOGGER = LoggerFactory.getLogger(App.class);
4145

42-
/**
43-
* Program entry point
44-
*
45-
* @param args command line args
46-
*/
47-
public static void main(String[] args) {
48-
TreasureChest chest = new TreasureChest();
46+
private static final TreasureChest TREASURE_CHEST = new TreasureChest();
4947

50-
ItemIterator ringIterator = chest.iterator(ItemType.RING);
51-
while (ringIterator.hasNext()) {
52-
LOGGER.info(ringIterator.next().toString());
48+
private static void demonstrateTreasureChestIteratorForType(ItemType itemType) {
49+
LOGGER.info("------------------------");
50+
LOGGER.info("Item Iterator for ItemType " + itemType + ": ");
51+
Iterator<Item> itemIterator = TREASURE_CHEST.iterator(itemType);
52+
while (itemIterator.hasNext()) {
53+
LOGGER.info(itemIterator.next().toString());
5354
}
55+
}
5456

55-
LOGGER.info("----------");
56-
57-
ItemIterator potionIterator = chest.iterator(ItemType.POTION);
58-
while (potionIterator.hasNext()) {
59-
LOGGER.info(potionIterator.next().toString());
57+
private static void demonstrateBstIterator() {
58+
LOGGER.info("------------------------");
59+
LOGGER.info("BST Iterator: ");
60+
TreeNode<Integer> root = buildIntegerBst();
61+
BstIterator bstIterator = new BstIterator<>(root);
62+
while (bstIterator.hasNext()) {
63+
LOGGER.info("Next node: " + bstIterator.next().getVal());
6064
}
65+
}
6166

62-
LOGGER.info("----------");
67+
private static TreeNode<Integer> buildIntegerBst() {
68+
TreeNode<Integer> root = new TreeNode<>(8);
6369

64-
ItemIterator weaponIterator = chest.iterator(ItemType.WEAPON);
65-
while (weaponIterator.hasNext()) {
66-
LOGGER.info(weaponIterator.next().toString());
67-
}
70+
root.insert(3);
71+
root.insert(10);
72+
root.insert(1);
73+
root.insert(6);
74+
root.insert(14);
75+
root.insert(4);
76+
root.insert(7);
77+
root.insert(13);
6878

69-
LOGGER.info("----------");
79+
return root;
80+
}
7081

71-
ItemIterator it = chest.iterator(ItemType.ANY);
72-
while (it.hasNext()) {
73-
LOGGER.info(it.next().toString());
74-
}
82+
/**
83+
* Program entry point
84+
*
85+
* @param args command line args
86+
*/
87+
public static void main(String[] args) {
88+
demonstrateTreasureChestIteratorForType(RING);
89+
demonstrateTreasureChestIteratorForType(POTION);
90+
demonstrateTreasureChestIteratorForType(WEAPON);
91+
demonstrateTreasureChestIteratorForType(ANY);
92+
93+
demonstrateBstIterator();
7594
}
7695
}

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

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

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

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
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+
/**
22+
* Iterator interface to be implemented by iterators over various data structures
23+
* @param <T> generically typed for various objects
24+
*/
25+
public interface Iterator<T> {
26+
27+
boolean hasNext();
28+
29+
T next();
30+
}

‎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+
}

0 commit comments

Comments
 (0)