2
\$\begingroup\$

I have written the following program for next word prediction using n-grams. The data structure is like a trie with frequency of each word.

Any suggestions are welcome, but I am more concerned about the compareTo and equals method, where the contract of if(obj1.compareTo(other)==0) then (obj1.equals(obj2) is not honored.

I need the compareTo() method to sort the list in the end.

package com.predictor;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 *
 * @author Sapan Parikh
 */
public class WordTree implements Comparable<Object> {

    String word;
    Integer frequency = 1;
    Map<WordTree, WordTree> map = new HashMap<>();

    public WordTree() {
        this.word = "";
    }

    public WordTree(String word) {
        this.word = word;
    }

    public void addToTree(List<List<String>> ngrams) {
        for (List ngram : ngrams) {
            addNgrams(ngram);
        }

    }

    private void addNgrams(List<String> ngram) {
        if (ngram == null || ngram.isEmpty()) {
            return;
        }
        WordTree t = new WordTree(ngram.remove(0).toLowerCase());
        if (this.map.containsKey(t)) {
            t = this.map.get(t);
            t.frequency++;
            this.map.put(t, t);
        } else {
            this.map.put(t, t);
        }
        try {
            this.map.get(t).addNgrams(ngram);
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    public static void main(String[] args) {
        WordTree t = new WordTree();
        t.addToTree(WordChunker.ngrams(4, "A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. Map is pretty cool too\n"
                + "\n"));
        System.out.println(t.suggestNext(chunkLastN(3, "Red-Black tree based")));
    }

    public static List<String> chunkLastN(int n,String string){
        List<String> chunks = new ArrayList<>();
        if(string!=null && string.lastIndexOf(" ")==-1){
            chunks.add(string);
        }
        while(string!=null && n>0 && string.lastIndexOf(" ")>0){
            chunks.add(0,string.substring(string.lastIndexOf(" ")).trim());
            string = string.substring(0, string.lastIndexOf(" "));
            n--;
        }
        System.out.println(chunks);
        return chunks;
    }
    @Override
    public int compareTo(Object o) {
        if (!(o instanceof WordTree)) {
            throw new ClassCastException("The object must be compared with WordTree type");
        }
        WordTree w = (WordTree) o;
        if (this.frequency < w.frequency) {            
            return 1;
        } else if (this.frequency == w.frequency) {
            return  0;
        } else {
            return -1;
        }

    }

    public List<WordTree> suggestNext(List<String> chunks) {
        List<String> lst = new ArrayList<>();
        if (chunks == null || chunks.isEmpty()) {
            return Collections.EMPTY_LIST;
        } else if (chunks.size() == 1) {
            Set<WordTree> keySet = this.map.get(new WordTree(chunks.remove(0))).map.keySet();
            ArrayList<WordTree> suggestions = new ArrayList<>(keySet);
              Collections.sort(suggestions);
              return suggestions;
        } else {
            return this.map.get(new WordTree(chunks.remove(0))).suggestNext(chunks);
        }

    }

    @Override
    public int hashCode() {
        int hash = 5;
        hash = 61 * hash + Objects.hashCode(this.word);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final WordTree other = (WordTree) obj;
        if (!Objects.equals(this.word, other.word)) {
            return false;
        }
        return true;
    }

    public void print() {
        System.out.println("word " + this.word + " can be followd by " + this.map.keySet());
        for (Map.Entry e : this.map.entrySet()) {
            ((WordTree) e.getValue()).print();
        }

    }

    @Override
    public String toString() {
        return " \"" + word + "\":" + frequency; //To change body of generated methods, choose Tools | Templates.
    }
}
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

First let answer about your concern

I am more concerned about the compareTo and equals method where the contract of if(obj1.compareTo(other)==0) then (obj1.equals(obj2) is not honored

equals Method

Your equals method can be minimized

public boolean equals(Object obj) {
    // It's up to you whether you will do this or not
    if(obj == null || getClass() != obj.getClass()) {
        return false;
    }

    final WordTree other = (WordTree) obj;

    if(!Objects.equals(this.word, other.word)) {
        return false;
    }
    return true;
}

You are using Objects class. But this is my classical approach.

public boolean equals(Object obj) {
    if (obj == null || getClass() != obj.getClass()) {
        return false;
    }

    final WordTree other = (WordTree) obj;

    // also check the equality of frequency of two words
    // since 'frequency' is also a field
    return (!"".equals(word) && word.equals(other.word)) &&                                 
           (this.frequency == other.frequency);
}

compareTo Method

Your compareTo method implementation is OK (if your logic says to compare two WordTree objects on the basis of the word frequency). ClassCastException can be easily dropped, as compareTo method receives generics you can change the method signature to:

public int compareTo(WordTree w) {}

There can be a slight optimization

    if(this.frequency == w.frequency) {            
        return 0;
    } 
    else {
        return (this.frequency > w.frequency) ? 1 : -1
    }

This is just a micro optimization and I think the compiler already makes it for you.

UPDATE after OP's comment

How would you re-write the compareTo and equals so that Map map = new HashMap<>(); can be re-written as TreeMap. Right now it wont work!

I researched and found a possible explanation from Jon Skeet's answer. The problem is about inconsistency of equals and compareTo methods. The compareTo must return 0 if and only if equals returns true. So I'm changing my code (though I'm not sure it will work accordingly since i don't have the full code I can't test it) :

public int compareTo(WordTree w){
    if(this.frequency > w.frequency) {
        return 1;
    }
    else if(this.frequency < w.frequency) {
        return -1;
    }
    else {
        return this.word.compareTo(w.word);
    }
}

General Review

  • The constructors can be written as

    public WordTree() {
        this("");
    }
    
    public WordTree(String word) {
        this.word = word;
    }
    

    This is just a personal preference to reuse the code, but many will differ from my opinion. Do as it suits you.

  • frequency, map(rename to suite the purpose), word should be private fields and have getters and setters logic to access or mutate.

    This is called encapsulation and it's one of the main part of OOP languages.

    However I think map shouldn't have any getter and setter cause client code doesn't need to worry about behind the curtain map implementation.

  • Name of the class is WordTree but the toString() method is returning the word and word-count or frequency. However I think your print() method achieves the toString behavior. Try to think of a good class name.

  • Main method shouldn't be in an API class you should test your class from another class like WordTreeTester which should have the main method.

  • A 2 cent suggestion try to create Javadoc and comment. But comment WHY are you doing not WHAT are you doing.

  • I'm not very good in Java Collections framework but I think you should also implement Iterable interface.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Objects is a class in JDK 1.7 docs.oracle.com/javase/7/docs/api How would you re-write the compareTo and equals so that Map<WordTree, WordTree> map = new HashMap<>(); can be re-written as TreeMap. Right now it wont work! \$\endgroup\$
    – Grrrrr
    Aug 26, 2013 at 16:28
  • \$\begingroup\$ Sorry I didn't know about Objects class. I edited my answer, but I don't see why you can't change HashMap to TreeMap! \$\endgroup\$ Aug 26, 2013 at 16:44
  • \$\begingroup\$ Well, TreeMap seem to be using compareTo method while "putting" objects in the bucket so it ends up overwriting all the objects with same frequency. so in the end that Map will have one object with frequency=1 one object with freq=2 and so on \$\endgroup\$
    – Grrrrr
    Aug 26, 2013 at 16:52
  • \$\begingroup\$ The last part of the first equals method can be simplified to Objects.equals(this.word, other.word) :) \$\endgroup\$ Nov 27, 2013 at 21:48
  • \$\begingroup\$ @SimonAndréForsberg yes that was actually done by the OP. I like to show him the classical way, though now I think it's unnecessary. \$\endgroup\$ Nov 27, 2013 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.