Skip to content

Commit 7f3eb1b

Browse files
aitorfisiriak
aitorfi
and
siriak
authored
Add generic Node classes (TheAlgorithms#2782)
Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent 78f7706 commit 7f3eb1b

16 files changed

+329
-1
lines changed

‎DevUtils/Nodes/LargeTreeNode.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package DevUtils.Nodes;
2+
3+
import java.util.Collection;
4+
5+
/**
6+
* {@link TreeNode} extension that holds a {@link Collection}
7+
* of refrences to child Nodes.
8+
*
9+
* @param <E> The type of the data held in the Node.
10+
*
11+
* @author <a href="https://github.com/aitorfi">aitorfi</a>
12+
*/
13+
public class LargeTreeNode<E> extends TreeNode<E> {
14+
/** {@link Collection} that holds the Nodes' child nodes. */
15+
private Collection<LargeTreeNode<E>> childNodes;
16+
17+
/** Empty contructor. */
18+
public LargeTreeNode() {
19+
super();
20+
}
21+
22+
/**
23+
* Initializes the Nodes' data.
24+
*
25+
* @param data Value to which data will be initialized.
26+
* @see TreeNode#TreeNode(Object)
27+
*/
28+
public LargeTreeNode(E data) {
29+
super(data);
30+
}
31+
32+
/**
33+
* Initializes the Nodes' data and parent node reference.
34+
*
35+
* @param data Value to which data will be initialized.
36+
* @param parentNode Value to which the nodes' parent reference will be set.
37+
* @see TreeNode#TreeNode(Object, Node)
38+
*/
39+
public LargeTreeNode(E data, LargeTreeNode<E> parentNode) {
40+
super(data, parentNode);
41+
}
42+
43+
/**
44+
* Initializes the Nodes' data and parent and child nodes references.
45+
*
46+
* @param data Value to which data will be initialized.
47+
* @param parentNode Value to which the nodes' parent reference will be set.
48+
* @param childNodes {@link Collection} of child Nodes.
49+
* @see TreeNode#TreeNode(Object, Node)
50+
*/
51+
public LargeTreeNode(E data, LargeTreeNode<E> parentNode, Collection<LargeTreeNode<E>> childNodes) {
52+
super(data, parentNode);
53+
this.childNodes = childNodes;
54+
}
55+
56+
/**
57+
* @return True if the node is a leaf node, otherwise false.
58+
* @see TreeNode#isLeafNode()
59+
*/
60+
@Override
61+
public boolean isLeafNode() {
62+
return (childNodes == null || childNodes.size() == 0);
63+
}
64+
65+
public Collection<LargeTreeNode<E>> getChildNodes() {
66+
return childNodes;
67+
}
68+
69+
public void setChildNodes(Collection<LargeTreeNode<E>> childNodes) {
70+
this.childNodes = childNodes;
71+
}
72+
}

‎DevUtils/Nodes/Node.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package DevUtils.Nodes;
2+
3+
/**
4+
* Base class for any node implementation which
5+
* contains a generic type variable.
6+
*
7+
* All known subclasses: {@link TreeNode}, {@link SimpleNode}.
8+
*
9+
* @param <E> The type of the data held in the Node.
10+
*
11+
* @author <a href="https://github.com/aitorfi">aitorfi</a>
12+
*/
13+
public abstract class Node<E> {
14+
/** Generic type data stored in the Node. */
15+
private E data;
16+
17+
/** Empty constructor. */
18+
public Node() {}
19+
20+
/**
21+
* Initializes the Nodes' data.
22+
*
23+
* @param data Value to which data will be initialized.
24+
*/
25+
public Node(E data) {
26+
this.data = data;
27+
}
28+
29+
public E getData() {
30+
return data;
31+
}
32+
33+
public void setData(E data) {
34+
this.data = data;
35+
}
36+
}

‎DevUtils/Nodes/SimpleNode.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package DevUtils.Nodes;
2+
3+
/**
4+
* Simple Node implementation that holds
5+
* a reference to the next Node.
6+
*
7+
* @param <E> The type of the data held in the Node.
8+
*
9+
* @author <a href="https://github.com/aitorfi">aitorfi</a>
10+
*/
11+
public class SimpleNode<E> extends Node<E> {
12+
/** Reference to the next Node. */
13+
private SimpleNode<E> nextNode;
14+
15+
/** Empty contructor. */
16+
public SimpleNode() {
17+
super();
18+
}
19+
20+
/**
21+
* Initializes the Nodes' data.
22+
*
23+
* @param data Value to which data will be initialized.
24+
* @see Node#Node(Object)
25+
*/
26+
public SimpleNode(E data) {
27+
super(data);
28+
}
29+
30+
/**
31+
* Initializes the Nodes' data and next node reference.
32+
*
33+
* @param data Value to which data will be initialized.
34+
* @param nextNode Value to which the next node reference will be set.
35+
*/
36+
public SimpleNode(E data, SimpleNode<E> nextNode) {
37+
super(data);
38+
this.nextNode = nextNode;
39+
}
40+
41+
/**
42+
* @return True if there is a next node, otherwise false.
43+
*/
44+
public boolean hasNext() {
45+
return (nextNode != null);
46+
}
47+
48+
public SimpleNode<E> getNextNode() {
49+
return nextNode;
50+
}
51+
52+
public void setNextNode(SimpleNode<E> nextNode) {
53+
this.nextNode = nextNode;
54+
}
55+
}

‎DevUtils/Nodes/SimpleTreeNode.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package DevUtils.Nodes;
2+
3+
/**
4+
* Simple TreeNode extension that holds references
5+
* to two child Nodes (left and right).
6+
*
7+
* @param <E> The type of the data held in the Node.
8+
*
9+
* @author <a href="https://github.com/aitorfi">aitorfi</a>
10+
*/
11+
public class SimpleTreeNode<E> extends TreeNode<E> {
12+
/** Refrence to the child Node on the left. */
13+
private SimpleTreeNode<E> leftNode;
14+
/** Refrence to the child Node on the right. */
15+
private SimpleTreeNode<E> rightNode;
16+
17+
/** Empty contructor. */
18+
public SimpleTreeNode() {
19+
super();
20+
}
21+
22+
/**
23+
* Initializes the Nodes' data.
24+
*
25+
* @param data Value to which data will be initialized.
26+
* @see TreeNode#TreeNode(Object)
27+
*/
28+
public SimpleTreeNode(E data) {
29+
super(data);
30+
}
31+
32+
/**
33+
* Initializes the Nodes' data and parent node reference.
34+
*
35+
* @param data Value to which data will be initialized.
36+
* @param parentNode Value to which the nodes' parent reference will be set.
37+
* @see TreeNode#TreeNode(Object, Node)
38+
*/
39+
public SimpleTreeNode(E data, SimpleTreeNode<E> parentNode) {
40+
super(data, parentNode);
41+
}
42+
43+
/**
44+
* Initializes the Nodes' data and parent and child nodes references.
45+
*
46+
* @param data Value to which data will be initialized.
47+
* @param parentNode Value to which the nodes' parent reference will be set.
48+
* @param leftNode Value to which the nodes' left child reference will be set.
49+
* @param rightNode Value to which the nodes' right child reference will be set.
50+
*/
51+
public SimpleTreeNode(E data, SimpleTreeNode<E> parentNode, SimpleTreeNode<E> leftNode, SimpleTreeNode<E> rightNode) {
52+
super(data, parentNode);
53+
this.leftNode = leftNode;
54+
this.rightNode = rightNode;
55+
}
56+
57+
/**
58+
* @return True if the node is a leaf node, otherwise false.
59+
* @see TreeNode#isLeafNode()
60+
*/
61+
@Override
62+
public boolean isLeafNode() {
63+
return (leftNode == null && rightNode == null);
64+
}
65+
66+
public SimpleTreeNode<E> getLeftNode() {
67+
return leftNode;
68+
}
69+
70+
public void setLeftNode(SimpleTreeNode<E> leftNode) {
71+
this.leftNode = leftNode;
72+
}
73+
74+
public SimpleTreeNode<E> getRightNode() {
75+
return rightNode;
76+
}
77+
78+
public void setRightNode(SimpleTreeNode<E> rightNode) {
79+
this.rightNode = rightNode;
80+
}
81+
}

‎DevUtils/Nodes/TreeNode.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package DevUtils.Nodes;
2+
3+
/**
4+
* Base class for any tree node which
5+
* holds a reference to the parent node.
6+
*
7+
* All known subclasses: {@link SimpleTreeNode}, {@link LargeTreeNode}.
8+
*
9+
* @param <E> The type of the data held in the Node.
10+
*
11+
* @author <a href="https://github.com/aitorfi">aitorfi</a>
12+
*/
13+
public abstract class TreeNode<E> extends Node<E> {
14+
/** Refernce to the parent Node. */
15+
private TreeNode<E> parentNode;
16+
/** Indicates the depth at which this node is in the tree. */
17+
private int depth;
18+
19+
/** Empty contructor. */
20+
public TreeNode() {
21+
super();
22+
depth = 0;
23+
}
24+
25+
/**
26+
* Initializes the Nodes' data.
27+
*
28+
* @param data Value to which data will be initialized.
29+
* @see Node#Node(Object)
30+
*/
31+
public TreeNode(E data) {
32+
super(data);
33+
depth = 0;
34+
}
35+
36+
/**
37+
* Initializes the Nodes' data and parent node reference.
38+
*
39+
* @param data Value to which data will be initialized.
40+
* @param parentNode Value to which the nodes' parent reference will be set.
41+
*/
42+
public TreeNode(E data, TreeNode<E> parentNode) {
43+
super(data);
44+
this.parentNode = parentNode;
45+
depth = this.parentNode.getDepth() + 1;
46+
}
47+
48+
/**
49+
* @return True if the node is a leaf node, otherwise false.
50+
*/
51+
public abstract boolean isLeafNode();
52+
53+
/**
54+
* @return True if the node is the root node, otherwise false.
55+
*/
56+
public boolean isRootNode() {
57+
return (parentNode == null);
58+
}
59+
60+
public TreeNode<E> getParent() {
61+
return parentNode;
62+
}
63+
64+
public void setParent(TreeNode<E> parentNode) {
65+
this.parentNode = parentNode;
66+
depth = this.parentNode.getDepth() + 1;
67+
}
68+
69+
public int getDepth() {
70+
return depth;
71+
}
72+
}

‎Searches/SearchAlgorithm.java renamed to ‎DevUtils/Searches/SearchAlgorithm.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package Searches;
1+
package DevUtils.Searches;
22

33
/**
44
* The common interface of most searching algorithms

‎Searches/BinarySearch.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66
import java.util.Random;
77
import java.util.concurrent.ThreadLocalRandom;
88
import java.util.stream.IntStream;
9+
import DevUtils.Searches.SearchAlgorithm;
910

1011
/**
1112
* Binary search is one of the most popular algorithms The algorithm finds the position of a target

‎Searches/ExponentalSearch.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
import java.util.Random;
55
import java.util.concurrent.ThreadLocalRandom;
66
import java.util.stream.IntStream;
7+
import DevUtils.Searches.SearchAlgorithm;
78

89
import static java.lang.String.format;
910

‎Searches/FibonacciSearch.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package Searches;
22

3+
import DevUtils.Searches.SearchAlgorithm;
4+
35
/*
46
* Fibonacci Search is a popular algorithm which finds the position of a target value in
57
* a sorted array

‎Searches/IterativeBinarySearch.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import java.util.Arrays;
66
import java.util.Random;
77
import java.util.stream.Stream;
8+
import DevUtils.Searches.SearchAlgorithm;
89

910
/**
1011
* Binary search is one of the most popular algorithms This class represents iterative version

‎Searches/IterativeTernarySearch.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import java.util.Arrays;
66
import java.util.Random;
77
import java.util.stream.Stream;
8+
import DevUtils.Searches.SearchAlgorithm;
89

910
/**
1011
* A iterative version of a ternary search algorithm This is better way to implement the ternary

‎Searches/JumpSearch.java

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package Searches;
22

3+
import DevUtils.Searches.SearchAlgorithm;
4+
35
public class JumpSearch implements SearchAlgorithm {
46

57
public static void main(String[] args) {

‎Searches/LinearSearch.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
import java.util.Random;
44
import java.util.stream.Stream;
5+
import DevUtils.Searches.SearchAlgorithm;
56

67
/**
78
* Linear search is the easiest search algorithm It works with sorted and unsorted arrays (an binary

‎Searches/LowerBound.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import java.util.Random;
66
import java.util.concurrent.ThreadLocalRandom;
77
import java.util.stream.IntStream;
8+
import DevUtils.Searches.SearchAlgorithm;
89

910
/**
1011
* The LowerBound method is used to return an index pointing to the first element in the range

‎Searches/TernarySearch.java

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
import java.util.Arrays;
66
import java.util.Random;
77
import java.util.stream.Stream;
8+
import DevUtils.Searches.SearchAlgorithm;
89

910
/**
1011
* A ternary search algorithm is a technique in computer science for finding the minimum or maximum

0 commit comments

Comments
 (0)