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

Commit7f3eb1b

Browse files
aitorfisiriak
andauthored
Add generic Node classes (TheAlgorithms#2782)
Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent78f7706 commit7f3eb1b

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+
packageDevUtils.Nodes;
2+
3+
importjava.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+
publicclassLargeTreeNode<E>extendsTreeNode<E> {
14+
/** {@link Collection} that holds the Nodes' child nodes. */
15+
privateCollection<LargeTreeNode<E>>childNodes;
16+
17+
/** Empty contructor. */
18+
publicLargeTreeNode() {
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+
publicLargeTreeNode(Edata) {
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+
publicLargeTreeNode(Edata,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+
publicLargeTreeNode(Edata,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+
publicbooleanisLeafNode() {
62+
return (childNodes ==null ||childNodes.size() ==0);
63+
}
64+
65+
publicCollection<LargeTreeNode<E>>getChildNodes() {
66+
returnchildNodes;
67+
}
68+
69+
publicvoidsetChildNodes(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+
packageDevUtils.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+
publicabstractclassNode<E> {
14+
/** Generic type data stored in the Node. */
15+
privateEdata;
16+
17+
/** Empty constructor. */
18+
publicNode() {}
19+
20+
/**
21+
* Initializes the Nodes' data.
22+
*
23+
* @param data Value to which data will be initialized.
24+
*/
25+
publicNode(Edata) {
26+
this.data =data;
27+
}
28+
29+
publicEgetData() {
30+
returndata;
31+
}
32+
33+
publicvoidsetData(Edata) {
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+
packageDevUtils.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+
publicclassSimpleNode<E>extendsNode<E> {
12+
/** Reference to the next Node. */
13+
privateSimpleNode<E>nextNode;
14+
15+
/** Empty contructor. */
16+
publicSimpleNode() {
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+
publicSimpleNode(Edata) {
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+
publicSimpleNode(Edata,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+
publicbooleanhasNext() {
45+
return (nextNode !=null);
46+
}
47+
48+
publicSimpleNode<E>getNextNode() {
49+
returnnextNode;
50+
}
51+
52+
publicvoidsetNextNode(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+
packageDevUtils.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+
publicclassSimpleTreeNode<E>extendsTreeNode<E> {
12+
/** Refrence to the child Node on the left. */
13+
privateSimpleTreeNode<E>leftNode;
14+
/** Refrence to the child Node on the right. */
15+
privateSimpleTreeNode<E>rightNode;
16+
17+
/** Empty contructor. */
18+
publicSimpleTreeNode() {
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+
publicSimpleTreeNode(Edata) {
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+
publicSimpleTreeNode(Edata,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+
publicSimpleTreeNode(Edata,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+
publicbooleanisLeafNode() {
63+
return (leftNode ==null &&rightNode ==null);
64+
}
65+
66+
publicSimpleTreeNode<E>getLeftNode() {
67+
returnleftNode;
68+
}
69+
70+
publicvoidsetLeftNode(SimpleTreeNode<E>leftNode) {
71+
this.leftNode =leftNode;
72+
}
73+
74+
publicSimpleTreeNode<E>getRightNode() {
75+
returnrightNode;
76+
}
77+
78+
publicvoidsetRightNode(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+
packageDevUtils.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+
publicabstractclassTreeNode<E>extendsNode<E> {
14+
/** Refernce to the parent Node. */
15+
privateTreeNode<E>parentNode;
16+
/** Indicates the depth at which this node is in the tree. */
17+
privateintdepth;
18+
19+
/** Empty contructor. */
20+
publicTreeNode() {
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+
publicTreeNode(Edata) {
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+
publicTreeNode(Edata,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+
publicabstractbooleanisLeafNode();
52+
53+
/**
54+
* @return True if the node is the root node, otherwise false.
55+
*/
56+
publicbooleanisRootNode() {
57+
return (parentNode ==null);
58+
}
59+
60+
publicTreeNode<E>getParent() {
61+
returnparentNode;
62+
}
63+
64+
publicvoidsetParent(TreeNode<E>parentNode) {
65+
this.parentNode =parentNode;
66+
depth =this.parentNode.getDepth() +1;
67+
}
68+
69+
publicintgetDepth() {
70+
returndepth;
71+
}
72+
}

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
packageSearches;
1+
packageDevUtils.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
importjava.util.Random;
77
importjava.util.concurrent.ThreadLocalRandom;
88
importjava.util.stream.IntStream;
9+
importDevUtils.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
importjava.util.Random;
55
importjava.util.concurrent.ThreadLocalRandom;
66
importjava.util.stream.IntStream;
7+
importDevUtils.Searches.SearchAlgorithm;
78

89
importstaticjava.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
packageSearches;
22

3+
importDevUtils.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
importjava.util.Arrays;
66
importjava.util.Random;
77
importjava.util.stream.Stream;
8+
importDevUtils.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
importjava.util.Arrays;
66
importjava.util.Random;
77
importjava.util.stream.Stream;
8+
importDevUtils.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
packageSearches;
22

3+
importDevUtils.Searches.SearchAlgorithm;
4+
35
publicclassJumpSearchimplementsSearchAlgorithm {
46

57
publicstaticvoidmain(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
importjava.util.Random;
44
importjava.util.stream.Stream;
5+
importDevUtils.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
importjava.util.Random;
66
importjava.util.concurrent.ThreadLocalRandom;
77
importjava.util.stream.IntStream;
8+
importDevUtils.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
importjava.util.Arrays;
66
importjava.util.Random;
77
importjava.util.stream.Stream;
8+
importDevUtils.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)
[8]ページ先頭
©2009-2025 Movatter.jp