Wordnet.java

/*
Correctness:  36/36 tests passed
Memory:       4/4 tests passed
Timing:       26/27 tests passed
Aggregate score: 99.26%


********************************************************************************
*  TIMING (substituting reference SAP)
********************************************************************************

Timing WordNet
*-----------------------------------------------------------
Running 11 total tests.

Test 2: count number of SAP operations when constructing a WordNet object
        and calling distance() and sap() three times each
  * calls to constructor = 1
  * calls to length()    = 6
  * calls to ancestor()  = 12
    - minimum required   = 3
    - maximum allowed    = 6
==> FAILED
*/

import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.ST;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Topological;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class WordNet {

    private final ST<Integer, Bag<String>> st1; // Dictionary ids to all the words of a synset noun
    private final ST<String, Bag<Integer>> st2; // Dictionary nouns to all its hypernyms
    private final SAP sap;

    // constructor takes the name of the two input files
    public WordNet(String synsets, String hypernyms) {
        // read and save the synsets file
        In in1 = new In(synsets);
        String[] linesSynsets = in1.readAllLines();
        // number of synsets
        int n = linesSynsets.length;
        st2 = new ST<>();
        st1 = new ST<>();

        String[] synsetsLineArray;
        for (String line : linesSynsets) { // for each read line
            synsetsLineArray = line.split(",");
            for (String word : synsetsLineArray[1].split(" ")) { // for each noun  in1 a given synset
                int id = Integer.parseInt(synsetsLineArray[0]);

                // build first symbol table
                if (!st1.contains(id)) {
                    st1.put(id, new Bag<>());
                }
                Bag<String> bag1 = st1.get(id);
                bag1.add(word);

                //build second symbol table
                if (!st2.contains(word)) {
                    st2.put(word, new Bag<>());
                }
                Bag<Integer> bag2 = st2.get(word);
                bag2.add(id);
            }
        }

        // build of Digraph
        Digraph wnDigraph = new Digraph(n);

        // read and save the hypernyms file
        List<String> hypernymLine; // hypernymsLineArray list as we do not know how many there are
        In in2 = new In(hypernyms);
        String[] lines2 = in2.readAllLines();
        int roots = 0; // the number of roots of the graph

        for (String line : lines2) {
            hypernymLine = Arrays.asList(line.split(","));
            for (int h = 1; h < hypernymLine.size(); h++) {
                int v = Integer.parseInt(hypernymLine.get(0));
                int w = Integer.parseInt(hypernymLine.get(h));
                // build the digraph
                wnDigraph.addEdge(v, w);
            }
        }
        // rooted?
        for (int v : st1) {
            if (wnDigraph.outdegree(v) == 0) {
                roots += 1;
            }
        }

        Topological topological = new Topological(wnDigraph);
        // is this graph a DAG?
        if (!topological.hasOrder() || roots > 1) {
            throw new IllegalArgumentException();
        }
        sap = new SAP(wnDigraph);
    }

    // returns all WordNet nouns
    public Iterable<String> nouns() {
        ArrayList<String> nouns = new ArrayList<>();
        for (String noun : st2) {
            nouns.add(noun);
        }
        return nouns;
    }

    // is the word a WordNet noun?
    public boolean isNoun(String word) {
        try {
            return null != st2.get(word);
        } catch (NullPointerException e) {
            throw new IllegalArgumentException();
        }
    }

    // distance between nounA and nounB (defined below)
    public int distance(String nounA, String nounB) {
        return findDistanceAncestor(nounA, nounB)[0];
    }

    // a synset (second field of synsets.txt) that is the common ancestor of nounA and nounB
    // in a shortest ancestral path (defined below)
    public String sap(String nounA, String nounB) {
        int idAncestor = findDistanceAncestor(nounA, nounB)[1];
        String res = " ";
        ArrayList<String> resArray = new ArrayList<>();
        for (String s : st1.get(idAncestor)) {
            resArray.add(s);
        }
        Collections.reverse(resArray);
        StringBuilder sb = new StringBuilder();
        for (String s : resArray) {
            sb.append(s);
            sb.append(" ");
        }
        res = sb.toString();
        return res;
    }


    private int[] findDistanceAncestor(String nounA, String nounB) {
        ArrayList<Integer> idsNounA = new ArrayList<>();
        ArrayList<Integer> idsNounB = new ArrayList<>();
        Bag<Integer> idsNounABag;
        Bag<Integer> idsNounBBag;

        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;

        if (isNoun(nounA) && isNoun(nounB)) {
            idsNounABag = st2.get(nounA);
            idsNounBBag = st2.get(nounB);

            for (Integer id : idsNounABag) {
                idsNounA.add(id);
            }

            for (Integer id : idsNounBBag) {
                idsNounB.add(id);
            }

            res[0] = sap.length(idsNounA, idsNounB);
            res[1] = sap.ancestor(idsNounA, idsNounB);

            return res;

        } else throw new IllegalArgumentException();
    }

    // do unit testing of this class
    public static void main(String[] args) {

        // read the files
        WordNet wordNet = new WordNet(args[0], args[1]);

        //StdOut.println(" All the wordNet nouns are :  " + wordNet.nouns());
        String nounA = "n"; // Black_Plague, black_marlin
        String nounB = "b";
        //String nounC = "0,'hood,(slang)";

        //StdOut.println("noun : " + nounA + " is " + wordNet.isNoun(nounA));
//        StdOut.println("noun : " + nounB + " is " + wordNet.isNoun(nounB));
        //StdOut.print("WordNet contains " + word1 + " is " + wordNet.isNoun(word1));
        //StdOut.print("distance between " + nounA + " and " + nounB + " is " + wordNet.distance(nounA, nounB) + "\n");
        StdOut.print("a shortest common ancestor between :" + nounA + " and : " + nounB + " is  " + wordNet.sap(nounA, nounB) + "\n");
    }
}