Finding Common Elements Between k Collections

[Pr0x1mo]

Given two collections of elements, A and B, generate a third collection, C, containing only those elements common in collections A and B, with duplicates allowed.

And this is the criteria i should be following:

It should be able to accept as input 0 to k collections, stored as simple arrays. We’re restricting the data structure to arrays since we haven’t covered higher order datastructures yet.

The elements of the collections should all be of type Comparable, and they should all be derived from the same base class (not counting the Object class). Implementation of the Comparable interface is necessary since the elements must be compared to each other in order to determine commonality. They must all be derived from the same base class since comparisons between different data types is undefined.

Duplicate elements should be allowed; e.g., if there are M instances of the value, “XYZ”, in all the input collections, there should be M instances of the value, “XYZ”, in the collection of common elements.
The collections should be allowed to be of varying lengths; i.e., some collections may have more items than others.
One of the collections must be designated as the “query” collection, which is the collection containing the elements to which the elements in the other collections are compared.
The total number of element comparisons performed should be less than the value for the quadratic solution described above. That is, the total number of comparisons in the worst case should be less than (k - 1)N2. Do not be concerned about average performance or best case performance. Also, the total number of comparisons is defined, for this assignment, to be only those comparisons that are performed once the traversal of the query collection begins, and the other collections are checked for the presence of the elements in the query collection. Any comparisons performed to manipulate the data prior to searching for the common elements should be ignored.
This is the code i have so far for CommonElements:

package Module4; 

//Define a class

public class CommonElements<T> implements Comparable<T> {
    private int comparisons = 0;
    private Comparable[][] mArray;

    CommonElements() {
    }
    CommonElements(Comparable[][] collections) {
        mArray = collections;
}

public Comparable[] findCommonElements(Comparable[][] collections) {
    try {
        insertionSort(collections);
}
    catch (NullPointerException e) {
        System.out.println("Error: Empty Array!");
}
    Comparable[] lCmmnCllctn;

    if (collections.length > 0) {
        lCmmnCllctn = new Comparable[collections[0].length];
        Comparable[] lQryCllctn = createQuery(collections);
        Comparable[][] lOthrCllctn = createOther(collections);
        int lFll = 0;

        for (Comparable query : lQryCllctn) {

            boolean lMtch = true;

            for (int li = 0; li < lOthrCllctn.length; li++) {

                for (int lj = 0; lj < lOthrCllctn[li].length; lj++) {

                    comparisons++;

                    if (query.compareTo(lOthrCllctn[li][lj]) == 0) {

                        lMtch = true;

                        break;
                        }
                    else
                        lMtch = false;
                    }
                }

            if (lMtch == true) {

                lCmmnCllctn[lFll] = query;

                lFll++;
                }
            }
        }
    else 
    {
        lCmmnCllctn = createQuery(collections);
        }

    return lCmmnCllctn;
    }
public int getComparisons() {
    return comparisons;
}

public Comparable[][] getArray() {
    return mArray;
}

public void lStArry(Comparable[][] collections) {
    mArray = collections;
}

private Comparable[] createQuery(Comparable[][] collections) {

    Comparable[] lQryCllctn = new Comparable[collections.length];
    for (int li = 0; li < collections[0].length; li++) {
        lQryCllctn[li] = collections[0][li];
        }
    return lQryCllctn;
    }

private Comparable[][] createOther(Comparable[][] collections) {
    Comparable[][] lOthrCllctn = new Comparable[collections.length - 1][];
    for (int li = 1; li < collections.length; li++) {
        for (int lj = 0; lj < collections[li].length; lj++) {
            lOthrCllctn[li][lj] = collections[li][lj];
            }
        }
    return lOthrCllctn;
    }
private Comparable[][] insertionSort(Comparable[][] collections) {
    for (int lj = 0; lj < collections.length; lj++) {
        for (int li = 1; li < collections[lj].length; li++) {
            Comparable firstUnsorted = collections[lj][li];
            int index = li - 1;

            while (index >= 0 && firstUnsorted.compareTo(collections[lj][index]) < 0) {
                collections[lj][index + 1] = collections[lj][index];

                index--;
                }
            collections[lj][index + 1] = firstUnsorted;
            }
        }
    return collections;
    }



public void toString(Comparable[][] collections) {
    for (int li = 0; li < collections.length; li++) {
        for (int lj = 0; lj < collections[li].length; lj++) {
            System.out.println("Set " + li + ": " + collections[li][lj]);
            }
        }
    }


public void toString(Comparable[] collections) {
    for (int li = 0; li < collections.length; li++) {
        System.out.println("Set " + li + ": " + collections[li]);
        }
    }

//Override

@Override

//Define a method

public int compareTo(T other) {
    if (this.compareTo(other) < 0 || this.compareTo(other) > 0)
        return Integer.signum(this.compareTo(other));
    else
        return 0;
    }
}

And the following is my main with the 2 arrays supplied to me:

package Module4;




 public class Module4 {


    public static void main(String[] agrs){

    CommonElements obj = new CommonElements();


Comparable[] col_1 = {
        "Baltimore Ravens", 
        "Seattle Seahawks", 
        "Indianapolis Colts", 
        "Houston Texans", 
        "Tennessee Titans", 
        "Jacksonville Jaguars", 
        "Arizona Cardinals", 
        "New England Patriots",
        "Baltimore Ravens",
        "Cincinnati Bengals",
        "bye week",
        "Kansas City Chiefs",
        "Cincinnati Bengals",
        "Cleveland Browns",
        "San Francisco 49ers",
        "St. Louis Rams",
        "Cleveland Browns" };
Comparable[] col_2 = {
        "Pittsburgh Steelers", 
        "Tennessee Titans", 
        "St. Louis Rams", 
        "New York Jets", 
        "bye week", 
        "Houston Texans", 
        "Jacksonville Jaguars",
        "Arizona Cardinals",
        "Pittsburgh Steelers", 
        "Seattle Seahawks", 
        "Cincinnati Bengals",
        "San Francisco 49ers",
        "Cleveland Browns",
        "Indianapolis Colts", 
        "San Diego Chargers", 
        "Cleveland Browns",
        "Cincinnati Bengals"};
Comparable[][] collections = {col_1, col_2};

obj.findCommonElements(collections);
//obj.compareTo(collections);
//obj.toString(Comparable[][] collections);

}

}

My question is more along the lines of how do i get the 3rd column to display to show what common items both these arrays share?

My professor gave us a guided template showing that: 1. Create a class called CommonElements, to contain your algorithm and associated methods and attributes. 2. In your CommonElements class, encapsulate your algorithm within a method called findCommonElements, that has the following signature: public Comparable[] findCommonElements(Comparable[][] collections).

Whats commented out is what im trying to do to call the class from above to display what common elements these 2 arrays share.

The error i got using the above was:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
    at Module4.CommonElements.createQuery(CommonElements.java:80)
    at Module4.CommonElements.findCommonElements(CommonElements.java:24)
    at Module4.CommonElement.main(CommonElement.java:51)

What do i need to do to this code to get it to compile and display the column of commonalities between the arrays?

[Norm]

Can you sort the arrays? That would make the search easier.

[wolle]

Implementation of the Comparable interface is necessary since the elements must be compared to each other in order to determine commonality.

Implementing Comparable is not necessary for elements to be compared for equality. Overriding the equals method of Object would be sufficient for that.

If on the other hand elements are to be sorted then Comparable must be implemented to establish an order among elements. So in a way the Comparable requirement strongly suggests that the query array is supposed to be sorted.

If the query array is sorted then a binary search can be used to check whether an element is present. This is much faster than a linear search (the complexity drops from linear to logarithmic) so it allows the brute force approach to be beat. The resulting algorithm will end up O(N*logN) rather than O(N*N).