Skip to content

Commit 6775988

Browse files
aadityatiwariaadityatiwari
authored
Merge pull request #1 from phishman3579/master
Upstream syncup
2 parents a159900 + 356dfb1 commit 6775988

File tree

140 files changed

+3370
-885
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

140 files changed

+3370
-885
lines changed

‎.travis.yml

+6-4
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
before_script:
2+
- sudo apt-get install ant-optional
23
- export OPTS="-server -Xmx3072M"
34
- export JAVA_OPTS="${JAVA_OPTS} ${OPTS}"
45
- export ANT_OPTS="${ANT_OPTS} ${OPTS}"
@@ -8,13 +9,15 @@ before_script:
89
language: java
910

1011
jdk:
12+
- oraclejdk9
1113
- oraclejdk8
12-
- oraclejdk7
14+
# - oraclejdk7
1315
# - oraclejdk6
1416

15-
# - openjdk8
17+
# - openjdk9
18+
- openjdk8
1619
- openjdk7
17-
- openjdk6
20+
# - openjdk6
1821

1922
env:
2023
- TEST_SUITE=run_tests
@@ -27,4 +30,3 @@ env:
2730
# - TEST_SUITE=sorts
2831

2932
script: "ant $TEST_SUITE"
30-

‎README.md

+46-32
Original file line numberDiff line numberDiff line change
@@ -44,22 +44,26 @@ This is a collection of algorithms and data structures which I've implement over
4444
* [Hash Array Mapped Trie (HAMT)](src/com/jwetherell/algorithms/data_structures/HashArrayMappedTrie.java)
4545
* [Hash Map (associative array)](src/com/jwetherell/algorithms/data_structures/HashMap.java)
4646
* [Interval Tree](src/com/jwetherell/algorithms/data_structures/IntervalTree.java)
47-
* [Implicit Key Treap]((src/com/jwetherell/algorithms/data_structures/ImplicitKeyTreap.java))
47+
* [Implicit Key Treap](src/com/jwetherell/algorithms/data_structures/ImplicitKeyTreap.java)
4848
* [KD Tree (k-dimensional tree or k-d tree)](src/com/jwetherell/algorithms/data_structures/KDTree.java)
49-
* [List [backed by an array or a linked list]]((src/com/jwetherell/algorithms/data_structures/List.java))
49+
* [List [backed by an array or a linked list]](src/com/jwetherell/algorithms/data_structures/List.java)
50+
* [LCP Array (Longest Common Prefix) [backed by a Suffix Array]](src/com/jwetherell/algorithms/data_structures/LCPArray.java)
5051
* [Matrix](src/com/jwetherell/algorithms/data_structures/Matrix.java)
5152
* [Patricia Trie](src/com/jwetherell/algorithms/data_structures/PatriciaTrie.java)
5253
* [Quad-Tree (Point-Region or MX-CIF)](src/com/jwetherell/algorithms/data_structures/QuadTree.java)
5354
* [Queue [backed by an array or a linked list]](src/com/jwetherell/algorithms/data_structures/Queue.java)
54-
* [Radix Trie (associative array) [backed by a Patricia Trie]](src/com/jwetherell/algorithms/data_structures/RadixTree.java)
55+
* [Radix Trie (associative array) [backed by a Patricia Trie]](src/com/jwetherell/algorithms/data_structures/RadixTrie.java)
5556
* [Red-Black Tree](src/com/jwetherell/algorithms/data_structures/RedBlackTree.java)
5657
* [Segment Tree](src/com/jwetherell/algorithms/data_structures/SegmentTree.java)
5758
* [Skip List](src/com/jwetherell/algorithms/data_structures/SkipList.java)
5859
* [Splay Tree](src/com/jwetherell/algorithms/data_structures/SplayTree.java)
5960
* [Stack [backed by an array or a linked list]](src/com/jwetherell/algorithms/data_structures/Stack.java)
61+
* [Suffix Array](src/com/jwetherell/algorithms/data_structures/SuffixArray.java)
6062
* [Suffix Tree (Ukkonen's algorithm)](src/com/jwetherell/algorithms/data_structures/SuffixTree.java)
61-
* [Suffix Trie [backed by a Trie]](src/com/jwetherell/algorithms/data_structures/SufficTrie.java)
63+
* [Suffix Trie [backed by a Trie]](src/com/jwetherell/algorithms/data_structures/SuffixTrie.java)
64+
* [Ternary Search Tree](src/com/jwetherell/algorithms/data_structures/TernarySearchTree.java)
6265
* [Treap](src/com/jwetherell/algorithms/data_structures/Treap.java)
66+
* [Tree](src/com/jwetherell/algorithms/data_structures/Tree.java)
6367
* [Tree Map (associative array) [backed by an AVL Tree]](src/com/jwetherell/algorithms/data_structures/TreeMap.java)
6468
* [Trie](src/com/jwetherell/algorithms/data_structures/Trie.java)
6569
* [Trie Map (associative array) [backed by a Trie]](src/com/jwetherell/algorithms/data_structures/TrieMap.java)
@@ -80,10 +84,15 @@ This is a collection of algorithms and data structures which I've implement over
8084
+ using only shifts
8185
+ using logarithms
8286
+ [Fast Fourier Transform](src/com/jwetherell/algorithms/mathematics/FastFourierTransform.java)
87+
* [Exponentiation](src/com/jwetherell/algorithms/mathematics/Exponentiation.java)
88+
+ recursive exponentiation
89+
+ fast recursive exponentiation
90+
+ fast modular recursive exponentiation
8391
* [Primes](src/com/jwetherell/algorithms/mathematics/Primes.java)
8492
+ is prime
8593
+ prime factorization
8694
+ sieve of eratosthenes
95+
+ Miller-Rabin test
8796
+ [Co-Primes (relatively prime, mutually prime)](src/com/jwetherell/algorithms/mathematics/Coprimes.java)
8897
+ [Greatest Common Divisor](src/com/jwetherell/algorithms/mathematics/GreatestCommonDivisor.java)
8998
- using Euclid's algorithm
@@ -145,43 +154,47 @@ This is a collection of algorithms and data structures which I've implement over
145154
* Graph Traversal
146155
- [Depth First Traversal](src/com/jwetherell/algorithms/graph/DepthFirstTraversal.java)
147156
- [Breadth First Traversal](src/com/jwetherell/algorithms/graph/BreadthFirstTraversal.java)
148-
* [Edmonds Karp](src/com/jwetherell/algorithms/graph/EdmondsKarp.java)
157+
* [Edmonds Karp](src/com/jwetherell/algorithms/graph/EdmondsKarp.java)
158+
* Matching
159+
- [Turbo Matching](src/com/jwetherell/algorithms/graph/TurboMatching.java)
160+
* [Lowest common ancestor in tree](src/com/jwetherell/algorithms/data_structures/Tree.java)
161+
149162

150163
## Search
151164
* Get index of value in array
152-
+ [Linear](src/com/jwetherell/algorithms/Sequences/LinearSearch.java)
153-
+ [Quickselect](src/com/jwetherell/algorithms/Sequences/QuickSelect.java)
154-
+ [Binary [sorted array input only]](src/com/jwetherell/algorithms/Sequences/BinarySearch.java)
155-
+ [Lower bound [sorted array input only]](src/com/jwetherell/algorithms/Sequences/LpperBound.java)
156-
+ [Upper bound [sorted array input only]](src/com/jwetherell/algorithms/Sequences/UpperBound.java)
165+
+ [Linear](src/com/jwetherell/algorithms/search/LinearSearch.java)
166+
+ [Quickselect](src/com/jwetherell/algorithms/search/QuickSelect.java)
167+
+ [Binary [sorted array input only]](src/com/jwetherell/algorithms/search/BinarySearch.java)
168+
+ [Lower bound [sorted array input only]](src/com/jwetherell/algorithms/search/LowerBound.java)
169+
+ [Upper bound [sorted array input only]](src/com/jwetherell/algorithms/search/UpperBound.java)
157170
+ Optimized binary (binary until a threashold then linear) [sorted array input only]
158-
+ [Interpolation [sorted array input only]](src/com/jwetherell/algorithms/Sequences/InterpolationSearch.java)
171+
+ [Interpolation [sorted array input only]](src/com/jwetherell/algorithms/search/InterpolationSearch.java)
159172

160173
## Sequences
161-
* [Find longest common subsequence (dynamic programming)](src/com/jwetherell/algorithms/Sequences/LongestCommonSubsequence.java)
162-
* [Find longest increasing subsequence (dynamic programming)](src/com/jwetherell/algorithms/Sequences/LongestIncreasingSubsequence.java)
163-
* [Find number of times a subsequence occurs in a sequence (dynamic programming)](src/com/jwetherell/algorithms/Sequences/SubsequenceCounter.java)
164-
* [Find i-th element in a Fibonacci sequence](src/com/jwetherell/algorithms/Sequences/FibonacciSequence.java)
174+
* [Find longest common subsequence (dynamic programming)](src/com/jwetherell/algorithms/sequence/LongestCommonSubsequence.java)
175+
* [Find longest increasing subsequence (dynamic programming)](src/com/jwetherell/algorithms/sequence/LongestIncreasingSubsequence.java)
176+
* [Find number of times a subsequence occurs in a sequence (dynamic programming)](src/com/jwetherell/algorithms/sequence/SubsequenceCounter.java)
177+
* [Find i-th element in a Fibonacci sequence](src/com/jwetherell/algorithms/sequence/FibonacciSequence.java)
165178
+ using a loop
166179
+ using recursion
167180
+ using matrix multiplication
168181
+ using Binet's formula
169-
* [Find total of all elements in a sequence(Arithmetic Progression)](src/com/jwetherell/algorithms/Sequences/ArithmeticProgression.java)
182+
* [Find total of all elements in a sequence(Arithmetic Progression)](src/com/jwetherell/algorithms/sequence/ArithmeticProgression.java)
170183
+ using a loop
171184
+ using Triangular numbers
172-
* [Largest sum of contiguous subarray (Kadane's algorithm)](src/com/jwetherell/algorithms/Sequences/LargestSumContiguousSubarray.java)
173-
* [Longest palin­dromic sub­se­quence (dynamic programming)](src/com/jwetherell/algorithms/Sequences/LongestPalin­dromicSub­se­quence.java)
185+
* [Largest sum of contiguous subarray (Kadane's algorithm)](src/com/jwetherell/algorithms/sequence/LargestSumContiguousSubarray.java)
186+
* [Longest palin­dromic sub­se­quence (dynamic programming)](src/com/jwetherell/algorithms/sequence/LongestPalindromicSubsequence.java)
174187

175188
## Sorts
176-
* [American Flag Sort](src/com/jwetherell/algorithms/Sorts/AmericanFlagSort.java)
177-
* [Bubble Sort](src/com/jwetherell/algorithms/Sorts/BubbleSort.java)
178-
* [Counting Sort (Integers only)](src/com/jwetherell/algorithms/Sorts/CountingSort.java)
179-
* [Heap Sort](src/com/jwetherell/algorithms/Sorts/HeapSort.java)
180-
* [Insertion Sort](src/com/jwetherell/algorithms/Sorts/InsertionSort.java)
181-
* [Merge Sort](src/com/jwetherell/algorithms/Sorts/AMergeSort.java)
182-
* [Quick Sort](src/com/jwetherell/algorithms/Sorts/QuickSort.java)
183-
* [Radix Sort (Integers only)](src/com/jwetherell/algorithms/Sorts/RadixSort.java)
184-
* [Shell's Sort](src/com/jwetherell/algorithms/Sorts/ShellSort.java)
189+
* [American Flag Sort](src/com/jwetherell/algorithms/sorts/AmericanFlagSort.java)
190+
* [Bubble Sort](src/com/jwetherell/algorithms/sorts/BubbleSort.java)
191+
* [Counting Sort (Integers only)](src/com/jwetherell/algorithms/sorts/CountingSort.java)
192+
* [Heap Sort](src/com/jwetherell/algorithms/sorts/HeapSort.java)
193+
* [Insertion Sort](src/com/jwetherell/algorithms/sorts/InsertionSort.java)
194+
* [Merge Sort](src/com/jwetherell/algorithms/sorts/MergeSort.java)
195+
* [Quick Sort](src/com/jwetherell/algorithms/sorts/QuickSort.java)
196+
* [Radix Sort (Integers only)](src/com/jwetherell/algorithms/sorts/RadixSort.java)
197+
* [Shell's Sort](src/com/jwetherell/algorithms/sorts/ShellSort.java)
185198

186199
## String Functions
187200
### [String Functions](src/com/jwetherell/algorithms/strings/StringFunctions.java)
@@ -198,9 +211,10 @@ This is a collection of algorithms and data structures which I've implement over
198211
+ using additional storage (a StringBuilder)
199212
+ using in-place symetric element compares
200213
* Subsets of characters in a String
201-
* Edit (Levenshtein) Distance of two Strings
202-
* [KMP (Knuth–Morris–Pratt) Algorithm - Length of maximal prefix-suffix for each prefix](src/com/jwetherell/algorithms/strings/KnuthMorrisPratt.java)
203-
* [String rotations](src/com/jwetherell/algorithms/strings/Rotation.java)
204-
+ Findin lexicographically minimal string rotation
205-
+ Findin lexicographically maximal string rotation
214+
* Edit (Levenshtein) Distance of two Strings (Recursive, Iterative)
215+
### [Manacher's algorithm (Find the longest Palindrome)](src/com/jwetherell/algorithms/strings/Manacher.java)
216+
### [KMP (Knuth–Morris–Pratt) Algorithm - Length of maximal prefix-suffix for each prefix](src/com/jwetherell/algorithms/strings/KnuthMorrisPratt.java)
217+
### [String rotations](src/com/jwetherell/algorithms/strings/Rotation.java)
218+
+ Find in lexicographically minimal string rotation
219+
+ Find in lexicographically maximal string rotation
206220

‎src/com/jwetherell/algorithms/data_structures/AVLTree.java

+3-3
Original file line numberDiff line numberDiff line change
@@ -12,9 +12,9 @@
1212
* trees are more rigidly balanced, they are faster than red-black trees for
1313
* lookup intensive applications. However, red-black trees are faster for
1414
* insertion and removal.
15-
*
16-
* http://en.wikipedia.org/wiki/AVL_tree
17-
*
15+
* <p>
16+
* @see <a href="https://en.wikipedia.org/wiki/AVL_tree">AVL Tree (Wikipedia)</a>
17+
* <br>
1818
* @author Justin Wetherell <phishman3579@gmail.com>
1919
*/
2020
public class AVLTree<T extends Comparable<T>> extends BinarySearchTree<T> {

‎src/com/jwetherell/algorithms/data_structures/BTree.java

+4-4
Original file line numberDiff line numberDiff line change
@@ -14,9 +14,9 @@
1414
* two children. Unlike self-balancing binary search trees, the B-tree is
1515
* optimized for systems that read and write large blocks of data. It is
1616
* commonly used in databases and file-systems.
17-
*
18-
* http://en.wikipedia.org/wiki/B-tree
19-
*
17+
* <p>
18+
* @see <a href="https://en.wikipedia.org/wiki/B-tree">B-Tree (Wikipedia)</a>
19+
* <br>
2020
* @author Justin Wetherell <phishman3579@gmail.com>
2121
*/
2222
@SuppressWarnings("unchecked")
@@ -109,7 +109,7 @@ public boolean add(T value) {
109109
/**
110110
* The node's key size is greater than maxKeySize, split down the middle.
111111
*
112-
* @param node
112+
* @param nodeToSplit
113113
* to split.
114114
*/
115115
private void split(Node<T> nodeToSplit) {

‎src/com/jwetherell/algorithms/data_structures/BinaryHeap.java

+9-9
Original file line numberDiff line numberDiff line change
@@ -16,9 +16,9 @@
1616
* the tree is not complete, the nodes of that level are filled from left to
1717
* right. 2) The heap property: each node is right than or equal to each of its
1818
* children according to a comparison predicate defined for the data structure.
19-
*
20-
* http://en.wikipedia.org/wiki/Binary_heap
21-
*
19+
* <p>
20+
* @see <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary Heap (Wikipedia)</a>
21+
* <br>
2222
* @author Justin Wetherell <phishman3579@gmail.com>
2323
*/
2424
@SuppressWarnings("unchecked")
@@ -289,8 +289,8 @@ public boolean validate() {
289289
/**
290290
* Validate the node for the heap invariants.
291291
*
292-
* @param node
293-
* to validate for.
292+
* @param index
293+
* of node to validate for.
294294
* @return True if node is valid.
295295
*/
296296
private boolean validateNode(int index) {
@@ -341,7 +341,7 @@ public T[] getHeap() {
341341
*/
342342
@Override
343343
public T getHeadValue() {
344-
if (array.length == 0) return null;
344+
if (size == 0 || array.length == 0) return null;
345345
return array[0];
346346
}
347347

@@ -372,7 +372,7 @@ public String toString() {
372372
protected static class HeapPrinter {
373373

374374
public static <T extends Comparable<T>> String getString(BinaryHeapArray<T> tree) {
375-
if (tree.array.length == 0)
375+
if (tree.size == 0 || tree.array.length == 0)
376376
return "Tree has no nodes.";
377377

378378
T root = tree.array[0];
@@ -449,8 +449,8 @@ public int size() {
449449
/**
450450
* Get the navigation directions through the tree to the index.
451451
*
452-
* @param index
453-
* of the Node to get directions for.
452+
* @param idx
453+
* index of the Node to get directions for.
454454
* @return Integer array representing the directions to the index.
455455
*/
456456
private static int[] getDirections(int idx) {

‎src/com/jwetherell/algorithms/data_structures/BinarySearchTree.java

+4-4
Original file line numberDiff line numberDiff line change
@@ -19,9 +19,9 @@
1919
* keys less than the node's key. 2) The right subtree of a node contains only
2020
* nodes with keys greater than the node's key. 3) Both the left and right
2121
* subtrees must also be binary search trees.
22-
*
23-
* http://en.wikipedia.org/wiki/Binary_search_tree
24-
*
22+
* <p>
23+
* @see <a href="https://en.wikipedia.org/wiki/Binary_search_tree">Binary Search Tree (Wikipedia)</a>
24+
* <br>
2525
* @author Justin Wetherell <phishman3579@gmail.com>
2626
*/
2727
@SuppressWarnings("unchecked")
@@ -185,7 +185,7 @@ protected void rotateLeft(Node<T> node) {
185185
* Rotate tree right at sub-tree rooted at node.
186186
*
187187
* @param node
188-
* Root of tree to rotate left.
188+
* Root of tree to rotate right.
189189
*/
190190
protected void rotateRight(Node<T> node) {
191191
Node<T> parent = node.parent;

‎src/com/jwetherell/algorithms/data_structures/CompactSuffixTrie.java

+8-3
Original file line numberDiff line numberDiff line change
@@ -8,9 +8,9 @@
88
* string in a way that allows for a particularly fast implementation of many
99
* important string operations. This implementation is based upon a patricia
1010
* trie which IS a compact trie.
11-
*
12-
* http://en.wikipedia.org/wiki/Suffix_trie
13-
*
11+
* <p>
12+
* @see <a href="https://en.wikipedia.org/wiki/Suffix_trie">Suffix Trie (Wikipedia)</a>
13+
* <br>
1414
* @author Justin Wetherell <phishman3579@gmail.com>
1515
*/
1616
@SuppressWarnings("unchecked")
@@ -141,4 +141,9 @@ private Set<String> getSuffixes(PatriciaTrie.Node node, String prefix) {
141141
public String toString() {
142142
return PatriciaTrie.PatriciaTriePrinter.getString(tree);
143143
}
144+
145+
public boolean equals(CompactSuffixTrie<C> trie){
146+
if(this.getSuffixes().equals(trie.getSuffixes())) return true;
147+
return false;
148+
}
144149
}

‎src/com/jwetherell/algorithms/data_structures/DisjointSet.java

+7-7
Original file line numberDiff line numberDiff line change
@@ -3,14 +3,14 @@
33
/**
44
* In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of
55
* elements partitioned into a number of disjoint (non-overlapping) subsets.
6-
*
7-
* It supports two useful operations:
6+
* <p>
7+
* It supports two useful operations:<br>
88
* Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its "representative"; by comparing the
9-
* result of two Find operations, one can determine whether two elements are in the same subset.
10-
* Union: Join two subsets into a single subset.
11-
*
12-
* http://en.wikipedia.org/wiki/Disjoint-set_data_structure
13-
*
9+
* result of two Find operations, one can determine whether two elements are in the same subset.<br>
10+
* Union: Join two subsets into a single subset.<br>
11+
* <p>
12+
* @see <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint Set (Wikipedia)</a>
13+
* <br>
1414
* @author Justin Wetherell <phishman3579@gmail.com>
1515
*/
1616
@SuppressWarnings("unchecked")

‎src/com/jwetherell/algorithms/data_structures/FenwickTree.java

+4-4
Original file line numberDiff line numberDiff line change
@@ -10,13 +10,13 @@
1010
* for calculation and manipulation of the prefix sums of a table of values. Fenwick trees
1111
* primarily solve the problem of balancing prefix sum calculation efficiency with element
1212
* modification efficiency.
13-
*
14-
* http://en.wikipedia.org/wiki/Fenwick_tree
15-
*
13+
* <p>
1614
* This class is meant to be somewhat generic, all you'd have to do is extend
1715
* the Data abstract class to store your custom data. I've included a range sum
1816
* implementations.
19-
*
17+
* <p>
18+
* @see <a href="https://en.wikipedia.org/wiki/Fenwick_tree">Fenwick Tree (Wikipedia)</a>
19+
* <br>
2020
* @author Justin Wetherell <phishman3579@gmail.com>
2121
*/
2222
@SuppressWarnings("unchecked")

‎src/com/jwetherell/algorithms/data_structures/Graph.java

+3-3
Original file line numberDiff line numberDiff line change
@@ -10,9 +10,9 @@
1010
* Graph. Could be directed or undirected depending on the TYPE enum. A graph is
1111
* an abstract representation of a set of objects where some pairs of the
1212
* objects are connected by links.
13-
*
14-
* http://en.wikipedia.org/wiki/Graph_(mathematics)
15-
*
13+
* <p>
14+
* @see <a href="https://en.wikipedia.org/wiki/Graph_(mathematics)">Graph (Wikipedia)</a>
15+
* <br>
1616
* @author Justin Wetherell <phishman3579@gmail.com>
1717
*/
1818
@SuppressWarnings("unchecked")

‎src/com/jwetherell/algorithms/data_structures/HashArrayMappedTrie.java

+4-4
Original file line numberDiff line numberDiff line change
@@ -10,12 +10,12 @@
1010
* A hash array mapped trie (HAMT) is an implementation of an associative
1111
* array that combines the characteristics of a hash table and an array mapped
1212
* trie. It is a refined version of the more general notion of a hash tree.
13-
*
13+
* <p>
1414
* This implementation is 32-bit and steps in 5-bit intervals, maximum tree
1515
* height of 7.
16-
*
17-
* http://en.wikipedia.org/wiki/Hash_array_mapped_trie
18-
*
16+
* <p>
17+
* @see <a href="https://en.wikipedia.org/wiki/Hash_array_mapped_trie">Hash Array Mapped Trie (Wikipedia)</a>
18+
* <br>
1919
* @author Justin Wetherell <phishman3579@gmail.com>
2020
*/
2121
@SuppressWarnings("unchecked")

0 commit comments

Comments
 (0)