TreeMap and Comparator question

[Darko Aleksic]

I tried finding out about this thing, but I just got more and more
frustrated... so - can someone just clarify this for me: if you give a
Comparator to a TreeMap, it must compare() keys, you can't compare
values?

What I've done before, when I needed a map sorted by values, was to
make a <Map.Entry<Key,Value>> Comparator, dump the entrySet() to a
list, sort it using that Comparator, clear the map and put everything
back in.

But I would like to be able to sort by keys or values when I wanted,
is it even doable? Or I have to create a new map every time? And if I
do, can't I just pass the old map and new Comparator (the one that
sorts by values or by keys, whatever is needed)?

And another thing - for normal sorting - if I change a field of a key
that is used while sorting, how do I tell the TreeMap that I've done
that? Or the only way is to remove the key, change that field and put
the key back in?

Hm, while typing this, I realized I might want to rethink what I'm
doing, but the questions still stand

 

[vahan]

As we see in source ordering operation takes place when we put some
K(key), V(value) into MapTee:

public V put(K key, V value) {
Entry<K,V> t = root;

if (t == null) {
incrementSize();
root = new Entry<K,V>(key, value, null);
return null;
}

while (true) {
int cmp = compare(key, t.key); // in this point we have
comparing operation
if (cmp == 0) {
return t.setValue(value);
} else if (cmp < 0) {
if (t.left != null) {
t = t.left;
} else {
incrementSize();
t.left = new Entry<K,V>(key, value, t);
fixAfterInsertion(t.left);
return null;
}
} else { // cmp > 0
if (t.right != null) {
t = t.right;
} else {
incrementSize();
t.right = new Entry<K,V>(key, value, t);
fixAfterInsertion(t.right);
return null;
}
}
}
}

So as we see there are comparing only by K if you want to compare by
value to , create your own class (MyTreeMap extends TreeMap) and
override "put" method,
In this case you will have class which compares V.

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Darko Aleksic schreef:

I tried finding out about this thing, but I just got more and more
frustrated... so - can someone just clarify this for me: if you give a
Comparator to a TreeMap, it must compare() keys, you can't compare
values?

What I've done before, when I needed a map sorted by values, was to
make a <Map.Entry<Key,Value>> Comparator, dump the entrySet() to a
list, sort it using that Comparator, clear the map and put everything
back in.

But I would like to be able to sort by keys or values when I wanted,
is it even doable? Or I have to create a new map every time? And if I
do, can't I just pass the old map and new Comparator (the one that
sorts by values or by keys, whatever is needed)?

And another thing - for normal sorting - if I change a field of a key
that is used while sorting, how do I tell the TreeMap that I've done
that? Or the only way is to remove the key, change that field and put
the key back in?

Hm, while typing this, I realized I might want to rethink what I'm
doing, but the questions still stand

Jakarta Commons Collections[*] has a SortedBidiMap, where both keys and
values are sorted. Though I do not understand what you mean by ‘put
them back in’ after they are sorted. This will loose the sorting.
Unless you use a LinkedHashMap, perhaps that is what you want?

Cheers, H.

[*] Unfortunately, not generified yet. The discussion is ongoing.
There is a nice Sourceforge project which has generic versions of most
of it: larvalabs.com.
- --
Hendrik Maryns

==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFEl7Nqe+7xMGD3itQRAlGmAJ4qWLOYZbfdgkSYnSiZMajBpq+yngCfd7o6
/kpLgLcahx7E639NtgjyPpU=
=qxWO
-----END PGP SIGNATURE-----

 

[Thomas Hawtin]

I tried finding out about this thing, but I just got more and more
frustrated... so - can someone just clarify this for me: if you give a
Comparator to a TreeMap, it must compare() keys, you can't compare
values?

I guess you could look up the value from the key in the tree. Might be
more safe to look it up in another copy of the map. You might want to
use a SortedSet for the sorting and another map for the key lookup.

A common hack is to add extra data onto the key which isn't used for
testing equality.

What I've done before, when I needed a map sorted by values, was to
make a <Map.Entry<Key,Value>> Comparator, dump the entrySet() to a
list, sort it using that Comparator, clear the map and put everything
back in.

Entries do not necessarily work with Compartors. Some entry sets may
return the same Map.Entry object just with different values. So when
comapre(Entry<Key,Value>,Entry<Key,Value>) is called, both arguments are
the same object. You should be alright with HashMap and TreeMap, but not
IdentityHashMap.

And another thing - for normal sorting - if I change a field of a key
that is used while sorting, how do I tell the TreeMap that I've done
that? Or the only way is to remove the key, change that field and put
the key back in?

Yes. In fact it's a good idea to make keys immutable.

Tom Hawtin

 

[Darko Aleksic]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Darko Aleksic schreef:

I tried finding out about this thing, but I just got more and more
frustrated... so - can someone just clarify this for me: if you give a
Comparator to a TreeMap, it must compare() keys, you can't compare
values?

What I've done before, when I needed a map sorted by values, was to
make a <Map.Entry<Key,Value>> Comparator, dump the entrySet() to a
list, sort it using that Comparator, clear the map and put everything
back in.

But I would like to be able to sort by keys or values when I wanted,
is it even doable? Or I have to create a new map every time? And if I
do, can't I just pass the old map and new Comparator (the one that
sorts by values or by keys, whatever is needed)?

And another thing - for normal sorting - if I change a field of a key
that is used while sorting, how do I tell the TreeMap that I've done
that? Or the only way is to remove the key, change that field and put
the key back in?

Hm, while typing this, I realized I might want to rethink what I'm
doing, but the questions still stand

Jakarta Commons Collections[*] has a SortedBidiMap, where both keys and
values are sorted. Though I do not understand what you mean by ‘put
them back in’ after they are sorted. This will loose the sorting.
Unless you use a LinkedHashMap, perhaps that is what you want?

Yes, LinkedHashMap is what I used to do that, sorry I didn't mention
that. I will take a look at SortedBidiMap, thanks.

Darko

Cheers, H.

[*] Unfortunately, not generified yet. The discussion is ongoing.
There is a nice Sourceforge project which has generic versions of most
of it: larvalabs.com.