Java Program to implement Sparse Vector

Code:

import java.util.Scanner;
import java.util.TreeMap;
import java.util.Map;

/** Class SparseVector **/
class SparseVector
{
/* Tree map is used to maintain sorted order */
    private TreeMap st;
    private int N;

    /** Constructor **/
    public SparseVector(int N)
    {
        this.N = N;
        st = new TreeMap();
    }

    /** Function to insert a (key, value) pair **/
    public void put(int i, double value) 
    {
        if (i < 0 || i >= N) 
               throw new RuntimeException("\nError : Out of Bounds\n");

        if (value == 0.0) 
            st.remove(i);
        else
            st.put(i, value);
    }

    /** Function to get value for a key **/
    public double get(int i) 
    {
        if (i < 0 || i >= N) 
        {
            throw new RuntimeException("\nError : Out of Bounds\n");
        }
        if (st.containsKey(i)) 
            return st.get(i);
        else                
            return 0.0;
    }

    /** Function to get size of the vector **/
    public int size() 
    {
        return N;
    }

    /** Function to get dot product of two vectors **/
    public double dot(SparseVector b) 
    {
        SparseVector a = this;
        if (a.N != b.N) 
               throw new RuntimeException("Error : Vector lengths are not same");

        double sum = 0.0;

        if (a.st.size() <= b.st.size()) 
        {
            for (Map.Entry entry : a.st.entrySet())
                if (b.st.containsKey(entry.getKey()))
                    sum += a.get(entry.getKey()) * b.get(entry.getKey());
        }          
        else  
        {
            for (Map.Entry entry : b.st.entrySet())
                if (a.st.containsKey(entry.getKey()))
                    sum += a.get(entry.getKey()) * b.get(entry.getKey());
        }
        return sum;
    }

    /** Function to get sum of two vectors **/
    public SparseVector plus(SparseVector b) 
    {
        SparseVector a = this;
        if (a.N != b.N) 
               throw new RuntimeException("Error : Vector lengths are not same");

        SparseVector c = new SparseVector(N);

        for (Map.Entry entry : a.st.entrySet())
            c.put(entry.getKey(), a.get(entry.getKey()));

        for (Map.Entry entry : b.st.entrySet())
            c.put(entry.getKey(), b.get(entry.getKey()) + c.get(entry.getKey()));

        return c;
    }

    /** Function toString() for printing vector **/
    public String toString() 
    {
        String s = "";
        for (Map.Entry entry : st.entrySet())
            s += "(" + entry.getKey() + ", " + st.get(entry.getKey()) + ") ";

        return s;
    }
}

/** Class SparseVector **/
public class SparseVectorTest
{
    public static void main(String[] args)
    {
        System.out.println("Sparse Vector Test\n");
        Scanner scan = new Scanner(System.in);

        System.out.println("Enter size of sparse vectors");
        int n = scan.nextInt();

        SparseVector v1 = new SparseVector(n);
        SparseVector v2 = new SparseVector(n);

        System.out.println("\nEnter number of entries for vector 1");
        int n1 = scan.nextInt();
        System.out.println("Enter "+ n1 +" (int, double) pairs");
        for (int i = 0; i < n1; i++)
            v1.put(scan.nextInt(), scan.nextDouble() );

        System.out.println("\nEnter number of entries for vector 2");
        int n2 = scan.nextInt();
        System.out.println("Enter "+ n2 +" (int, double) pairs");
        for (int i = 0; i < n2; i++)
            v2.put(scan.nextInt(), scan.nextDouble() );

        System.out.println("\n");
        System.out.println("Vector v1 = " + v1);
        System.out.println("Vector v2 = " + v2);
        System.out.println("\nv1 dot v2 = " + v1.dot(v2));
        System.out.println("v1  +  v2   = " + v1.plus(v2));
    }
}



Output:

Sparse Vector Test

Enter size of sparse vectors
70000

Enter number of entries for vector 1
4
Enter 4 (int, double) pairs
3 1.0
2500 6.3
5000 10.0
60000 5.7

Enter number of entries for vector 2
3
Enter 3 (int, double) pairs
1 7.5
3 5.7
2500 -6.3


Vector v1 = (3, 1.0) (2500, 6.3) (5000, 10.0) (60000, 5.7)
Vector v2 = (1, 7.5) (3, 5.7) (2500, -6.3)

v1 dot v2 = -33.989999999999995
v1  +  v2   = (1, 7.5) (3, 6.7) (5000, 10.0) (60000, 5.7)



More Java Programs: