Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit038befe

Browse files
authored
Merge pull requestiluwatar#779 from mitchellirvin/bst-iterator
iluwatar#778: Binary Search Tree Iterator
2 parents74f3799 +8458e42 commit038befe

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-diagramversion="1.1.8"icons="true"automaticImage="PNG"always-add-relationships="false"generalizations="true"
33
realizations="true"associations="true"dependencies="false"nesting-relationships="true">
4-
<classid="1"language="java"name="com.iluwatar.iterator.TreasureChest"project="iterator"
4+
<classid="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
<positionheight="124"width="195"x="1"y="237"/>
77
<displayautosize="true"stereotype="true"package="true"initial-value="false"signature="true"
@@ -10,7 +10,7 @@
1010
<operationspublic="true"package="true"protected="true"private="true"static="true"/>
1111
</display>
1212
</class>
13-
<classid="2"language="java"name="com.iluwatar.iterator.Item"project="iterator"
13+
<classid="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
<positionheight="160"width="157"x="195"y="401"/>
1616
<displayautosize="true"stereotype="true"package="true"initial-value="false"signature="true"
@@ -19,7 +19,7 @@
1919
<operationspublic="true"package="true"protected="true"private="true"static="true"/>
2020
</display>
2121
</class>
22-
<enumerationid="3"language="java"name="com.iluwatar.iterator.ItemType"project="iterator"
22+
<enumerationid="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
<positionheight="160"width="145"x="388"y="601"/>
2525
<displayautosize="true"stereotype="true"package="true"initial-value="false"signature="true"
@@ -28,7 +28,7 @@
2828
<operationspublic="true"package="true"protected="true"private="true"static="true"/>
2929
</display>
3030
</enumeration>
31-
<interfaceid="4"language="java"name="com.iluwatar.iterator.ItemIterator"project="iterator"
31+
<interfaceid="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
<positionheight="106"width="131"x="236"y="237"/>
3434
<displayautosize="true"stereotype="true"package="true"initial-value="false"signature="true"
@@ -37,7 +37,7 @@
3737
<operationspublic="true"package="true"protected="true"private="true"static="true"/>
3838
</display>
3939
</interface>
40-
<classid="5"language="java"name="com.iluwatar.iterator.TreasureChestItemIterator"project="iterator"
40+
<classid="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
<positionheight="160"width="323"x="236"y="37"/>
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 orsubstantial 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
packagecom.iluwatar.iterator;
2420

21+
importstaticcom.iluwatar.iterator.list.ItemType.ANY;
22+
importstaticcom.iluwatar.iterator.list.ItemType.POTION;
23+
importstaticcom.iluwatar.iterator.list.ItemType.RING;
24+
importstaticcom.iluwatar.iterator.list.ItemType.WEAPON;
25+
26+
importcom.iluwatar.iterator.bst.BstIterator;
27+
importcom.iluwatar.iterator.bst.TreeNode;
28+
importcom.iluwatar.iterator.list.Item;
29+
importcom.iluwatar.iterator.list.ItemType;
30+
importcom.iluwatar.iterator.list.TreasureChest;
2531
importorg.slf4j.Logger;
2632
importorg.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 ({@linkItemIterator}) adds abstraction layer on top of a collection
38+
* In this example the Iterator ({@linkIterator}) 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
publicclassApp {
3943

4044
privatestaticfinalLoggerLOGGER =LoggerFactory.getLogger(App.class);
4145

42-
/**
43-
* Program entry point
44-
*
45-
* @param args command line args
46-
*/
47-
publicstaticvoidmain(String[]args) {
48-
TreasureChestchest =newTreasureChest();
46+
privatestaticfinalTreasureChestTREASURE_CHEST =newTreasureChest();
4947

50-
ItemIteratorringIterator =chest.iterator(ItemType.RING);
51-
while (ringIterator.hasNext()) {
52-
LOGGER.info(ringIterator.next().toString());
48+
privatestaticvoiddemonstrateTreasureChestIteratorForType(ItemTypeitemType) {
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-
ItemIteratorpotionIterator =chest.iterator(ItemType.POTION);
58-
while (potionIterator.hasNext()) {
59-
LOGGER.info(potionIterator.next().toString());
57+
privatestaticvoiddemonstrateBstIterator() {
58+
LOGGER.info("------------------------");
59+
LOGGER.info("BST Iterator: ");
60+
TreeNode<Integer>root =buildIntegerBst();
61+
BstIteratorbstIterator =newBstIterator<>(root);
62+
while (bstIterator.hasNext()) {
63+
LOGGER.info("Next node: " +bstIterator.next().getVal());
6064
}
65+
}
6166

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

64-
ItemIteratorweaponIterator =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+
returnroot;
80+
}
7081

71-
ItemIteratorit =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+
publicstaticvoidmain(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.
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+
packagecom.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+
publicinterfaceIterator<T> {
26+
27+
booleanhasNext();
28+
29+
Tnext();
30+
}
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+
packagecom.iluwatar.iterator.bst;
20+
21+
importcom.iluwatar.iterator.Iterator;
22+
importjava.util.ArrayDeque;
23+
importjava.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+
publicclassBstIterator<TextendsComparable<T>>implementsIterator<TreeNode<T>> {
33+
34+
privateArrayDeque<TreeNode<T>>pathStack;
35+
36+
publicBstIterator(TreeNode<T>root) {
37+
pathStack =newArrayDeque<>();
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+
privatevoidpushPathToNextSmallest(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+
publicbooleanhasNext() {
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+
publicTreeNode<T>next()throwsNoSuchElementException {
69+
if (pathStack.isEmpty()) {
70+
thrownewNoSuchElementException();
71+
}
72+
TreeNode<T>next =pathStack.pop();
73+
pushPathToNextSmallest(next.getRight());
74+
returnnext;
75+
}
76+
77+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp