CODEWITHSUNDEEP
javadata-structures
jmasterx
jmasterx

Reputation: 54123

Data structure to check for pairs?

Say I have objects A,B,C,D. They can contain references to one another, for example, A might reference B and C, and C might reference A. I want to create segments but dont want to create them twice, so I don't want segment A C and segment C A, just 1 of them. So I want to keep a list of created segments, ex: A C, and check if I already have an A C or C A and skip it if so.

Is there a data structure that can do this?

Thanks

if(list.contains(a,b)
{
   //dont add
}

Upvotes: 2

Views: 364

Answers (5)

Yogendra Singh
Yogendra Singh

Reputation: 34367

Use java.util.Set/ java.util.HashSet and keep adding the references you find e.g.

   Set set1 = new HashSet();
   set1.add(A), set1.Add(C), set1.Add(C)

You can add this finding in an external set, as finalSet.add(set1)

  Set<Set> finalSet = new HashSet<Set>();
  finalSet.add(set1);

This will filter out the duplicates automatically and in the end, you will be left with A & C only.

Upvotes: 0

Damian Leszczyński - Vash
Damian Leszczyński - Vash

Reputation: 30865

Your problem is related with graph theory.

What you can try is to remove that internal list and create a Incidence Martrix, that all you objects share.

The final solution mostly depend of the task goal and available structure. So is hard to choose best solution for you problem with the description you have provided.

Upvotes: 0

jdevelop
jdevelop

Reputation: 12296

you may introduce something like 

class PairKey<T extends Comparable<T>> { 
  final T fst, snd;
  public PairKey(T a, T b) {
    if (a.compareTo(b) <=0 ) {
      fst = a;
      snd = b;
    } else {
      fst = b;
      snd = a;
    }
  }

  @Override
  public int hashCode() {
    return a.hashCode() & 37 & b.hashCode();
  }

  @Override
  public boolean equals(Object other) {
    if (other == this) return true;
    if (!(other instanceOf PairKey)) return false;
    PairKey<T> obj = (PairKey<T>) other;
    return (obj.fst.equals(fst) && obj.snd.equals(snd));
  }
}

then you may put edges into HashSet < PairKey < ? extends Comparable> > and then check if the given pair is already there.

You will need to make your vertexes comparable, so it will be possible to treat PairKey(A,B) equal to PairKey(B,A)

And then HashSet will do the rest for you, e.g you will be able to query 

pairs.contains(new PairKey(A,B));

and if pairs contain either PairKey(A,B) or PairKey(B,A) - it will return true.

hashCode implementation might be slightly different, may be IDE will generate something more sophisticated.

Hope that helps.

Upvotes: 2

Woot4Moo
Woot4Moo

Reputation: 24316

I would use an object called Pair that would look something like this: 

class Pair  
{  
    Node start;  
    Node end;  

    public Pair(Node start, Node end)  
    { 
      this.start=start;
      this.end=end;  
    }  

   public Pair reverse()  
   {  
       return new Pair(end,start);  
   }  
}

Now you can do something like this: 

if(pairs.contains(currentPair) || pairs.contains(currentPair.reverse())  
{  
    continue;
}  else{  
     pairs.add(currentPair);  
}

As pointed out in the comments, you will need to implement equals and hashcode. However, doing the check in equals to make it match the reversal of the segment is a bad practice in a pure OO since. By implementing equals in the fashion, described within the comments, would bind Pair to your application only and remove the portability of it.

Upvotes: 1

Ted Hopp
Ted Hopp

Reputation: 234807

You can use a set of sets of objects.

Set<Set<MyObjectType>> segments = new HashSet<Set<MyObjectType>>();

Then you can add two-element sets representing pairs of MyObject. Since sets are unordered, if segments contains a set with A and B, attempting to add a set containing B and A will treat it as already present in segments.

Set<MyObjectType> segment = new HashSet<MyObjectType>();
segment.add(A); // A and B are instances of MyObjectType
segment.add(B);
segments.add(segment);
segment = new HashSet<MyObjectType>();
segment.add(B);
segment.add(A);
segments.add(segment);
System.out.println("Number of segments: " + segments.size()); // prints 1

Upvotes: 0

Related Questions