phishman3579 / java-algorithms-implementation Goto Github PK

I'm opening this issue just to point you to my PR that fixes it: #159 - all the details are on the PR description.

We added the following test (in MathematicsTests) which checks that the method Multiplication.multiplyUsingLoopWithStringInput works correctly when multiplying with zero. It fails with the error below

Test:
@test
public void testMultiplyUsingLoopsWithStringInputZero(){
long result = Integer.parseInt(Multiplication.multiplyUsingLoopWithStringInput("0", "0"));
long expected = 0;
//Requirement:
//When multiplying two values where one or both is zero the result should be zero
assertTrue(result ==expected);
}

Error:
Testcase: testMultiplyUsingLoopsWithStringInputZero(com.jwetherell.algorithms.mathematics.test.MathematicsTest): Caused an ERROR
[junit] For input string: ""
[junit] java.lang.NumberFormatException: For input string: ""
[junit] at java.base/java.lang.NumberFormatException.forInputString(NumberFormatException.java:67)
[junit] at java.base/java.lang.Integer.parseInt(Integer.java:678)
[junit] at java.base/java.lang.Integer.parseInt(Integer.java:786)
[junit] at com.jwetherell.algorithms.mathematics.test.MathematicsTest.testMultiplyUsingLoopsWithStringInputZero(Unknown Source)

It seems that by always taking the lowest cost edge like this:
final Graph.Edge<Integer> e = edgesAvailable.remove();
, without checking if it is still connecting us to the unvisited vertex we will end up with cycles.
When I added these lines of code in my project:
while (!unvisited.contains(e.getToVertex())) { e = edgesAvailable.remove(); }
It performs well. I've implemented my own Graph, Edge and Vertex class which should behave the same as these used in this project, maybe I'm missing something. Worth checking it out.

function next in ArrayQueueIterator maybe happen ArrayIndexOutOfBoundsException;
because "queue.firstIndex+index" maybe not the real index
public T next() {
if (queue.firstIndex+index < queue.lastIndex) {
last = queue.firstIndex+index;
return queue.array[queue.firstIndex+index++];
//this is my change
// return queue.array[(queue.firstIndex+index++) % queue.array.length];
}
return null;
}

this is a simple test
IQueue arrayQueue = new Queue.ArrayQueue();
for(int i=0;i<1024;i++){

        arrayQueue.offer(i);
    }
    System.out.println(arrayQueue.poll());
    arrayQueue.offer(1024);
    Iterator it = arrayQueue.toQueue().iterator();
    while (it.hasNext()){
        System.out.println(it.next());
    }

Data Structures -> Tree.

May I have alternate link?

So,this maybe a bug

In contains method of ArrayList if condition to check if value is equal should return false, when the condition is not satisfied.

Last Testcase gets fail : 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
a longest increasing subsequence is
0, 2, 6, 9, 11, 15. or
0, 4, 6, 9, 11, 15 or
0, 2, 6, 9, 13, 15 or
0, 4, 6, 9, 13, 15

But it return wrong answer: 0, 1, 3, 7, 11, 15

Here's a custom test case written:

BinaryHeap.BinaryHeapArray<Integer> aHeapMax = new BinaryHeap.BinaryHeapArray<Integer>(BinaryHeap.Type.MAX);
aHeapMax.add(10);
aHeapMax.add(11);
aHeapMax.clear();
assertNull(aHeapMax.getHeadValue()); // we expect null here

We expect that the head of BinaryHeapArray becomes null on clear, but it does not, and BinaryHeapArray::getHeadValue and BinaryHeapArray::toString functions return the first value of the heap array despite asking for a clear.

For instance, the class Graph.CostPathPair is not correct:

import java.util.HashSet;
import org.junit.Test;
import com.jwetherell.algorithms.data_structures.Graph;
import com.jwetherell.algorithms.data_structures.Graph.*;

public class GraphTest {
    @Test
    public void testCostVertexPair() {
        HashSet<Edge<Integer>> s1 = new HashSet<Graph.Edge<Integer>>();
        s1.add(new Edge<Integer>(1, new Vertex<Integer>(10), new Vertex<Integer>(20)));
        s1.add(new Edge<Integer>(2, new Vertex<Integer>(20), new Vertex<Integer>(30)));
        Graph.CostPathPair<Integer> p1 = new Graph.CostPathPair<Integer>(1, s1);

        HashSet<Edge<Integer>> s2 = new HashSet<Graph.Edge<Integer>>();
        s2.add(new Edge<Integer>(2, new Vertex<Integer>(10), new Vertex<Integer>(20)));
        s2.add(new Edge<Integer>(1, new Vertex<Integer>(20), new Vertex<Integer>(30)));
        Graph.CostPathPair<Integer> p2 = new Graph.CostPathPair<Integer>(1, s2);

        System.err.println(p1.equals(p2)); // => false
        System.err.println(p2.equals(p1)); // => false
        System.err.println(p1.hashCode()); // 62
        System.err.println(p2.hashCode()); // 62
    }
}

(question arising while testing: Shouldn't the class Graph be moved in the graph package?)

Sended to PR and after merged. Why not add more valuble?
So what I was thought add a template for PR and Also added CONTRIBUTE.md file and style of code.
I had plan to add all this infomation.
Here is link to more about it.
Do you want send PR?
Yes!

Hey! @mciancia
Can I contribute your repo because I saw you have missed some graph part?
DFS and BFS which is standard agos.

/** Deep copies **/
public Graph(Graph<T> g) {
    type = g.getType();

    // Copy the vertices which also copies the edges
    for (Vertex<T> v : g.getVertices())
        this.allVertices.add(new Vertex<T>(v));

    for (Vertex<T> v : this.getVertices()) {
        for (Edge<T> e : v.getEdges()) {
            this.allEdges.add(e);
        }
    }
}

I don't think it‘s a Deep copies. Although those new Vertices have associated with those Edges, but Edges still associated with old Vertices;

Hi

In a recent code, I've found a following suspicious code at src/com/jwetherell/algorithms/data_structures/DisjointSet.java

115         @Override
116         public boolean equals(Object o) {
117             if (!(o instanceof Item))
118                 return false;
119 
120             final Item<T> i = (Item<T>) o;
121             if ((i.parent!=null && parent!=null) && !(i.parent.value.equals(parent.value)))
122                 return false;
123             if ((i.value!=null && value!=null) && !(value.equals(value)))
124                 return false;
125             return true;
126         } 

In Line 123, should !(value.equals(value) be !(i.value.equals(value)? This may not be an issue, but wanted to report just in case. Thanks!

In Queue.java,

        // Grow the array by 50% and rearrange to make sequential
        private void grow(int size) {
            int growSize = (size + (size<<1));
            T[] temp = (T[]) new Object[growSize];
            // Since the array can wrap around, make sure you grab the first chunk 
            int adjLast = lastIndex % array.length;
            if (adjLast < firstIndex) {
                System.arraycopy(array, 0, temp, array.length-adjLast, adjLast+1);
            }
            // Copy the remaining
            System.arraycopy(array, firstIndex, temp, 0, array.length-firstIndex);
            array = null;
            array = temp;
            lastIndex = (lastIndex - firstIndex);
            firstIndex = 0;
        }

I think int growSize = (size + (size<<1)) will actually triple the size instead of growing size by 50%.
I believe this is a typo and it should be int growSize = (size + (size>>1)) and I have make a pull request to fix that #100

In the files FenwickTree.java, Matrix.java and SegmentTree.java (all in the folder \src\com\jwetherell\algorithms\data_structures), there are comments saying TODO: This is ugly and how to handle number overflow?. See example below.

These functions do the same things, therefore some refactoring could decrease code repetition. Specifically, a class could be created which holds functions for adding, subtracting, multiplying and comparing the different types BigDecimal, BigInteger, Long, Double, Float and Integer.

Furthermore, there seems to be no branch coverage for using these different types, since all tests just use Integers. Tests for the different types should be added.

/* TODO: This is ugly and how to handle number overflow? */
if (this.sum instanceof BigDecimal || data.sum instanceof BigDecimal) {
    BigDecimal result = ((BigDecimal)this.sum).subtract((BigDecimal)data.sum);
    this.sum = (N)result;
} else if (this.sum instanceof BigInteger || data.sum instanceof BigInteger) {
    BigInteger result = ((BigInteger)this.sum).subtract((BigInteger)data.sum);
    this.sum = (N)result;
} else if (this.sum instanceof Long || data.sum instanceof Long) {
    Long result = (this.sum.longValue() - data.sum.longValue());
    this.sum = (N)result;
} else if (this.sum instanceof Double || data.sum instanceof Double) {
    Double result = (this.sum.doubleValue() - data.sum.doubleValue());
    this.sum = (N)result;
} else if (this.sum instanceof Float || data.sum instanceof Float) {
    Float result = (this.sum.floatValue() - data.sum.floatValue());
    this.sum = (N)result;
} else {
    // Integer
    Integer result = (this.sum.intValue() - data.sum.intValue());
    this.sum = (N)result;
}

It would be most helpfull if the KdTree.XYZPoint included the math for mapping a latitude/longitude pair into the 3 dimensional XYZpoint.

I think it is something along the line of

point[0] = cos(toRadians(latitude)) * cos(toRadians(longitude));
point[1] = cos(toRadians(latitude)) * sin(toRadians(longitude));
point[2] = sin(toRadians(latitude));

Regarding MergeSort.java

In the source code comments, it states "Space: In-place." and according to "In-place algorithms" wikipedia states

"an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes."

However, in line 47 of the code the output array is used to merge the left and right half and is later used to overwrite the input array. This takes O(nlogn) extra space which is not constant.

    node.lesser = greater;
    if (greater != null)
        greater.parent = node;

greater node is already node.greater.
By above assignment, the greater is now assigned to both node.lesser and node.greater

Just wanted to let you know that your K-d tree implementation is very very slow compared to eg the one from https://github.com/AReallyGoodName/OfflineReverseGeocode

in the below code the 1st query correctly returns [b, c, a] but the 2nd query does not return anything (i.e. returns null) while I assume it should return [b, c]

public static void main(String[] args) {

    java.util.List<IntervalTree.IntervalData<String>> intervals = new ArrayList<IntervalTree.IntervalData<String>>();
    intervals.add((new IntervalTree.IntervalData<String>(1, 5, "a")));
    intervals.add((new IntervalTree.IntervalData<String>(2, 6, "b")));
    intervals.add((new IntervalTree.IntervalData<String>(3, 7, "c")));

    IntervalTree<String> tree = new IntervalTree<String>(intervals);

    IntervalTree.IntervalData<String> query1 = tree.query(5);
    System.out.println(query1.getData());

    IntervalTree.IntervalData<String> query2 = tree.query(6);
    System.out.println(query2.getData());
}

Hi!,
I'm seeing here in readme file it has very good content but needs to more organize way.
Likes :

         1. Contents list
        2.  Add relative link to direct code in readme.md
       3. Remove extra folder from repo
       4. Add contribute.md file
       5. Add PULL_REQUEST_TEMPLETE.md
       6. Add License 

Would you like to help ?
Yes! :)

Incorrect value is returrned for "big" n values (n > 92) because of the encoding limitation of the used primary type (long). Either an IllegalArgumentException should be raised or a zero value returned for all algorithms.

Fibonacci sequence tests

algorithm: FibonacciSequenceUsingLoop

f(25) =                75025 [    4.157 µs]
f(26) =               121393 [    5.207 µs]
f(27) =               196418 [    5.023 µs]
...
f(90) =  2880067194370816120 [   18.408 µs]
f(91) =  4660046610375530309 [   18.718 µs]
f(92) =  7540113804746346429 [   18.741 µs]
f(93) = -6246583658587674878 [   19.363 µs] KO
f(94) =  1293530146158671551 [   18.479 µs] KO
f(95) = -4953053512429003327 [   19.053 µs] KO

algorithm: FibonacciSequenceUsingRecursion

f(25) =                75025 [    1.581 ms]
f(26) =               121393 [    2.671 ms]
f(27) =               196418 [    4.328 ms]
f(28) =               317811 [    7.032 ms]
f(29) =               514229 [    9.708 ms]
f(30) =               832040 [   15.432 ms]
f(31) =              1346269 [   24.880 ms]
f(32) =              2178309     time out

algorithm: FibonacciSequenceUsingMatrixMultiplication

f(25) =                75025 [   23.856 µs]
f(26) =               121393 [   29.692 µs]
f(27) =               196418 [   30.164 µs]
...
f(90) =  2880067194370816120 [   88.054 µs]
f(91) =  4660046610375530309 [   88.248 µs]
f(92) =  7540113804746346429 [   89.123 µs]
f(93) = -6246583658587674878 [  114.994 µs] KO
f(94) =  1293530146158671551 [   91.361 µs] KO
f(95) = -4953053512429003327 [   92.010 µs] KO

algorithm: FibonacciSequenceUsingBinetsFormula

f(25) =                75025 [    5.359 µs]
f(26) =               121393 [    4.295 µs]
f(27) =               196418 [    4.476 µs]
...
f(90) =  2880067194370825216 [    3.210 µs]
f(91) =  4660046610375544832 [    3.850 µs]
f(92) =  7540113804746369024 [    3.288 µs]
f(93) =  9223372036854775807 [    3.637 µs] KO
f(94) =  9223372036854775807 [    3.654 µs] KO
f(95) =  9223372036854775807 [    3.752 µs] KO

hi i have a set of unordered strings (in general elements)
i might create a hashcode string or integer identifying uniquely this set.I addition i have to create a fast function given a string(element) returns fastly all sets containing this element. Have you a idea if there is a fast adt for it? maybe a Trie?
Ideally i think a tree where every parent node contains a hashcode based on children.

Thanks for algorithms.

I have a question concerning KdTree. Would there be a lot of changes to make to implement radial search?

I came up with the following solution, but this does not work correctly (something is definetely wrong with examined collection):

https://gist.github.com/uburoiubu/c09dd8df5a9f739b0d16f400df76da6a

 public static final String reverseWithStringBuilder(String string) {
        StringBuilder builder = new StringBuilder();
        for (int i = (string.length() - 1); i >= 0; i--) {
            builder.append(string.charAt(i));
        }
        return builder.toString();
    }

can we simplify this code to

 public static final String reverseWithStringBuilder2(String string) {
        StringBuilder builder = new StringBuilder(string);
        builder.reverse();
        return builder.toString();
    }

Almost all methods have input parameter as String string .
Can it be renamed to something else like String inputStringor String inputor source

I was reading the source. It is trivial but can be helpful for novice programmers.

this code is not wrong. I wonder can you modify it.
in my opinion, replacementNode must be a leaf node.
so if it is a left leaf node or a right leaf node,
just make sure replacementParent.lesser = null; or replacementParent.greater= null;

A test directory should contain all test classes.
Useful with JUnit or when building distributions.

"I like what you have. Here is another way to do the HeapSort. public void sort(int arr[])
{
int n = arr.length;

    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        // Move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
    int largest = i;  // Initialize largest as root
    int l = 2*i + 1;  // left = 2*i + 1
    int r = 2*i + 2;  // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i)
    {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

/* A utility function to print array of size n */
static void printArray(int arr[])
{
    int n = arr.length;
    for (int i=0; i<n; ++i)
        System.out.print(arr[i]+"" "");
    System.out.println();
}"

Hello,

Is there a Ternary Search Tree implementation here by a different name?

I tried to look for TST or Ternary and didn't see one. Was wondering if it appears under a different name.

Thank you.

Hi, due to academic issues I have reviewed your code and I have detected possible design patterns that can be implemented in order to improve the appearance of the code.

Strategy Pattern
A new interface called "WithOrigin" is created which refers to methods specific to shortest path algorithms of a graph considering an initial vertex and an end.
The Dijkstra and Bellman-Ford classes represent concrete classes that implement the interface described above. Each class will perform its own implementation of the methods provided by the interface.
In addition, the pattern gives rise to a new class called "ShortestWay" that will represent a handler for these algorithms. It communicates directly with the client and provides it with a kind of facade (not considering the pattern) that allows to choose the algorithm of interest.

The class diagram would be as follows:

Decorator Pattern
For this solution an interface called Node was created that will be joined with the abstract class LinkedList with a composition relation of multiplicity 2. The concrete classes called SinglyNode and DoublyNode will implement the Node interface.
It should be emphasized that with this solution the List file, original of the analyzed code is segregated into other classes. Thus, in order to provide greater modularity.



The ArrayList and LinkedList classes, including the latter's child classes, are separated into separate files.



LinkedList child classes.

The class diagram would be as follows:

Iterator Pattern
For this solution, an extra operation is added to the IGraph interface called createIterator() that will allow choosing the type of path of interest.
An Iterator interface is added with the operations used by the traversal algorithms. The concrete classes BreadthFirst and DepthFirst implement this interface.


Iterator interface.

Concrete classes that implement the interface.

The class diagram would be as follows:

Interval Tree: Does it support zero length intervals, and does it support querying all overlapping intervals that touch an interval from the side (adjacent)?

There's an incorrect comment on line 14 says "Average case = O(n) Worst case = O(n^2) Best case = O(n_log n)", which contradicts commtent on line 6 and 7 that says " *Quicksort is a sorting algorithm which, on average, makes O(n_log n) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons", I think the latter is correct.

For my project, I needed to implement sorting with the American flag. Searching the Internet for a code just to get acquainted with the algorithm (it's easier for me), I went to this repository. Focusing on it - I wrote the code in C ++. And it turned out that the algorithm can not count large numbers. I had an array of 16 elements and each element could be from 1 to 999. It turned out that it sorts only by units and tens. Replacing the line with the next - the code worked.

temp = (int)Math.log10(i) + 2; //86 line in the code

Then I decided to test an array with numbers up to 30,000. Here it has already sorted by units, tens and hundreds, not counting thousands. And only at this stage did I realize your next mistake. The algorithm requires the number of radix of the largest number, while for this same number you take not the number of the array, but the size of the array. As more and more numbers are given each time, the maximum will change to the last. In this code, everything depends not on the maximum number, but on the size of the array.
For the algorithm to work, you need to pass to the logarithm not the cell number of the array, but its value:

//The first variant
for (int i : unsorted)
{
	temp = (int)Math.log10(unsorted[i]) + 1;
	if(temp > max)
	{
		max = temp;
	}
}

In general, in my code I wrote as follows:

//The second variant
int getMaxNumberOfDigits()
{
	int count = 1;
	int value = ArrayProcessing<int>::getMax(Array, array_size); //My own function, but I think it is clear that it performs
	while(true)
	{
		value /= 10;
		if(value != 0)
		{
			count++;
		}
		else
		{
			break;
		}
	}
	return count;
}

My method is easier to understand. Your method sorts through each element of the array and calculates the number of its radix for each of them. And my method by the same search at once defines the largest element and only for one of it calculates quantity of radix. My method is faster because you don't have to count the number of radix for each element of the array.
I think Java would be the same mistake. I advise you to correct this mistake with either the first or the second variant. Here is a link to the file just in case.

In the function Matrix.add (see code below), the innermost for-loop is unneeded (notice that the iterator i is not used at all). Removing this for-loop can reduce the time complexity from cubic to quadratic, in relation to the width of the matrix. I have tried removing it, and all tests still pass.

The exact same problem is apparent in Matrix.subtract.

These functions can be found in the filesrc\com\jwetherell\algorithms\data_structures\Matrix.java

public Matrix<T> add(Matrix<T> input) {
    Matrix<T> output = new Matrix<T>(this.rows, this.cols);
    if ((this.cols != input.cols) || (this.rows != input.rows))
        return output;
    for (int r = 0; r < output.rows; r++) {
        for (int c = 0; c < output.cols; c++) {
            for (int i = 0; i < cols; i++) {
                T m1 = this.get(r, c);
                T m2 = input.get(r, c);
                T result;
                /* TODO: This is ugly and how to handle number overflow? */
                if (m1 instanceof BigDecimal || m2 instanceof BigDecimal) {
                    BigDecimal result2 = ((BigDecimal)m1).add((BigDecimal)m2);
                    result = (T)result2;
                } else if (m1 instanceof BigInteger || m2 instanceof BigInteger) {
                    BigInteger result2 = ((BigInteger)m1).add((BigInteger)m2);
                    result = (T)result2;
                } else if (m1 instanceof Long || m2 instanceof Long) {
                    Long result2 = (m1.longValue() + m2.longValue());
                    result = (T)result2;
                } else if (m1 instanceof Double || m2 instanceof Double) {
                    Double result2 = (m1.doubleValue() + m2.doubleValue());
                    result = (T)result2;
                } else if (m1 instanceof Float || m2 instanceof Float) {
                    Float result2 = (m1.floatValue() + m2.floatValue());
                    result = (T)result2;
                } else {
                    // Integer
                    Integer result2 = (m1.intValue() + m2.intValue());
                    result = (T)result2;
                }
                output.set(r, c, result);
            }
        }
    }
    return output;
}

AVLNode parent - is actually always a left or a right child of variable node.