When I find something interesting and new, I post it here - that's mostly programming, of course, not everything.

Wednesday, September 17, 2008

Java: have a set of pairs, need a map

In Java, as in may other discourses, maps and sets of pairs with unique keys are more or less the same thing. The problem is that Map in Java is represented as a set of Map.Entry<X, Y>; and Map.Entry is not the best way to represent pairs in your code.

Personally I, probably like the best half of Java programmers, have my own class named Pair<X, Y>; the components are called, yes, x and y. In Map.Entry they are called key and value.

So I had to make Pair<X, Y> implement Map.Entry<X, Y>, so that I would not need to recreate a Map.Entry<X, Y> every time I have a Pair<X, Y>.

Now, if I have a Set<Pair<X, Y>>, what should I do to produce a Map<X, Y>, without replicating all my data? I will need an AbstractMap<X, Y>, and provide a method, entrySet(). I already have a set; the trouble is, this set is a set of pairs, Set<Pair<X, Y>>. Should I replicate it? No way; what if there's 50 million records? Can I cast it? No... it is just impossible. should I wrap it somehow? Yes, kind of.

Luckily, I have some cool classes and methods already that would help me to do the job.

The cool class is called Function<X, Y>. The traditional approach is to declare it as an interface with one method, Y apply(X x). I thought it would be cool to implement additional methods. First, having an Iterator<X>, one would like to map this iterator using a function, right? That's what the method in Function<X, Y>, Iterator<Y> map(Iterator<X> iteratorX is for:

public Iterator<Y> map(final Iterator<X> iteratorX) {
return new Iterator<Y>() {
public boolean hasNext() {
return iteratorX.hasNext();
}

public Y next() {
return apply(iteratorX.next());
}

public void remove() {
iteratorX.remove();
}
};
}


This was the biggest chunk of code.

Now that we can map an iterator, we can as well map an iterable, a collection, a list... but we need a set. Here we go:

public Set<Y> map(final Set<X> setX) {
return new AbstractSet<Y>() {
public Iterator<Y> iterator() {
return map(setX.iterator());
}

public int size() {
return setX.size();
}
};
}


How does it all help me? I just want to map my Set<Pair<X, Y>> to a Set<Map.Entry<X, Y>> without multiplying entities. So we need a function that returns the same pair, but shows it as a map entry. This is an identity function. Let's define it in Function class:

public static <T, T0 super T> Function<T, T0> id() {
return new Function<T, T0>() {
public T0 apply(T t) { return t; }
};
}


See, while it returns the same instance, but, in the eyes of compiler, casts it to some superclass. Now that we have it, let's apply it to solve our problem:


public static <X, Y> Map<X, Y> Map(final Set<Pair<X, Y>> pairs) {
final Function<Pair<X, Y>, Map.Entry<X, Y>> idmap = Function.id();

return new AbstractMap<X, Y>() {
public Set<Entry<X, Y>> entrySet() {
return idmap.map(pairs);
}
};
}


One little note. We had to introduce the variable, idmap - thus mentally "reifying" our identity function; it would not work if we just called Function.id() on spot - Java compiler would be too confused.

No comments:

Followers

Subscribe To My Podcast

whos.amung.us