Java: If object of same parameters exists do not add new object

Question

Here is my object constructor

static class Edge {
    int source; // source node
    int destination; // destination node
    int weight; // weight of the edge
    int predecessor; // previous node
    public Edge() {};
    public Edge(int s, int d, int w) { source = s; destination = d; weight = w; }
}

Now, here is the statement where I create a new Edge object

edges.add(new Edge(nodeStart, tempDest, tempWeight));

I need to skip over that statement if there has already been an object created with the same parameters (nodeStart, tempDest)

Basically, I don't want to add the same edge twice.

edges.add(new Edge(0, 1, tempWeight));
edges.add(new Edge(0, 1, tempWeight));

If that happens, I want to make sure it only adds it once, and not new identical objects.

Answer 1

The proper way would be to make edges a Set<Edge>. And then properly override hashcode and equals.

So, you should declare edges like so:

Set<Edge> egdes = new HashSet<Edge>();

And you should implement hashCode and equals like so:

public boolean equals(Object o) {
    if (o == null) return false;
    if (o == this) return true;
    if (!(o instanceof Edge)) return false;
    Edge oEdge = (Edge) o;
    return this.source == oEdge.source && 
           this.destination == oEdge.destination && 
           this.weight == oEdge.weight;
}

public int hashCode(){
    return source * 3 + dest * 11 + weight * 13;
}

You should read up on properly implementing equals and hashCode. My examples are not great. But the general idea is conveyed.

Answer 2

Use a Set instead of a List to store your edge objects and define the Edge equals and hashCode correctly. This will prevent duplicates which are logically equal.

Answer 3

To say that you do not want "duplicates", first you have to tell java how you consider two edges are equal. You do this using the equals method (otherwise there is no way for java to know when two of the objects of your Edge class are equal).
When you give a equals method to your object, you have to give a hashCode to your object. See this question for an explanation.
(Actually you oveerride these methods. Default implementations of both are present in java.lang.Object from which all java objects extend)

So first you have to tell java when two Edges are equal. Add a equals method and a hashcode method to your class. See Justin's answer for details.

Once done, you have make sure that your collection of edge objects do not have duplicates. For this you can use a HashSet. (and not a List. A List can have duplicates. A Set cannot. This tutorial gives a good explanation)

In the statement, edges.add..., edges should be a HashSet (or any implementation of set).
HashSet<Edge> edges = new HashSet<Edge>();

Once you have done this, you have a List (er, Set) of unique Edges.

If you need only a List and not a set, you can create a List out of this Set:

ArrayList edgesAsList = new ArrayList<Edge>(edges);

Answer 4

Another possible way is to just check edges.contains() before adding the new edge.

Edge newEdge = new Edge(nodeStart, tempDest, tempWeight);
if (!edges.contains(newEdge))
    edges.add(newEdge);

You will need to properly implement the equals method in Edge in order for this to work though. See my other answer for that code.

Note: This way is a much slower way than using a Set to exclude duplicates.

Answer 5

Based on your comments I think really all you need is a customized ArrayList.

On a side note, based on your comments to other answers it seems you need to do a lot of random access by index and not by parameter. That is, you indicated you want to get an Edge by the order in which it was added rather than by specifying unique-ifying parameters, and that you may want to access that order in a highly non-sequential way. For the random access case, this data structure's performance will be better than the custom Set proposed above, because it pays a high upfront-cost of O(N) insert time, where N grows with the size of the set; however, when you go to do random access you get the same great O(1) by index retrieval time that an ArrayList offers. In comparison, for the custom Set, even if you extend a LinkedHashSet to maintain access order you'd pay O(1) insert time, but O(N), to iterate through the entries in order, random access time.

Basically, you pay the unique-ifying constraint upfront, and forget about it later. In the case of the set, you pay an access time constraint later. Of course, that's not the end of the story, there is definitely a solution which might let both worlds be satisfied. Suppose we keep more data (ah, memory vs. CPU/time), and in the data structure below instead of searching through the list to find out if we already have the Edge in question we maintain an internal Set as well. When we go to insert, we first try finding the Edge in the Set (O(1)), when the Edge is unfound, we add it to the Set and to the List. Now, we have to keep an extra Set around (that's the memory cost) to avoid a time penalty for looking at our List during inserts.

So far so good, but we now need to also define a hashing function which generates unique hashCodes for, well, what you consider unique. In other words, we want to make sure, loosely: hashCode(Edge a) != hashCode(Edge b) where a != b should hold for some unbelievably large space of a and b being different in some sense you define. Given you define such a function you still have to pay the memory cost for keeping a set, but that's maybe not so bad if you really care about the insert cost.

Here's the simple straight List concept, it's easily modified to also maintain a Set, and you would modify the contains function below to check the Set rather than check search the List if you wanted to go with the hybrid approach.

public class EdgeArrayList extends ArrayList<Edge>{
    @Override
    public boolean add(Edge e){
        if(contains(e)){
            return false;
        }
        super.add(e);
        return true;
    }

    @Override
    public boolean contains(Object o){
        if(!(o instanceof Edge))
            return false;

        Edge e = (Edge) o;

        for(Edge item : this){
            if(item.source == e.source && 
               item.destination == e.destination && 
               item.weight == e.weight){
                return true;
            }
        }
       return false;
   }

}

Usage would then be as you suggest, where Edges already contained in the EdgeArrayList will simply not be added:

EdgeArrayList foo = new EdgeArrayList();
foo.add(new Edge(0, 0, 0));
foo.add(new Edge(0, 0, 0));

At the end of this foo contains just the first instance of an Edge with all parameters set to 0 (I've tested this, it really works).

Some pitfalls here -- checking that a new Edge is not the list will incur an O(N) hit on the order of the size of the current list N.

Answer 6

This seems like a candidate for a factory where in you could check for an existing object for the criteria inside the factory implementation and return the one already existing.. just my 2 cents...