1 cananian 1.1.2.1 // MapComparator.java, created Mon Sep 17 17:16:46 2001 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Util;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import java.util.ArrayList;
7 cananian 1.1.2.2 import java.util.Collections;
8 cananian 1.1.2.2 import java.util.Comparator;
9 cananian 1.3 import java.util.List;
10 cananian 1.1.2.2 import java.util.Map;
11 cananian 1.3
12 cananian 1.3 import net.cscott.jutil.Default;
13 cananian 1.1.2.1 /**
14 cananian 1.1.2.1 * A <code>MapComparator</code> compares two unsorted maps by first
15 cananian 1.1.2.1 * sorting their keys and then comparing them entry-by-entry (treating
16 cananian 1.1.2.1 * the map as a sorted pair list).
17 cananian 1.1.2.1 *
18 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
19 cananian 1.3 * @version $Id: MapComparator.java,v 1.3 2004/02/08 01:56:15 cananian Exp $
20 cananian 1.1.2.1 */
21 cananian 1.3 public class MapComparator<K,V> implements Comparator<Map<K,V>> {
22 cananian 1.3 final Comparator<Map.Entry<K,V>> entryComparator;
23 cananian 1.3 final Comparator<List<Map.Entry<K,V>>> listComparator;
24 cananian 1.1.2.1
25 cananian 1.1.2.1 /** Creates a <code>MapComparator</code> which compares
26 cananian 1.1.2.1 * entries in the order defined by the <code>keyComparator</code>
27 cananian 1.1.2.1 * and compares keys (using <code>keyComparator</code>) before values
28 cananian 1.1.2.1 * (using <code>valueComparator</code>).
29 cananian 1.1.2.1 * If <code>keyComparator</code> is <code>null</code>, then all
30 cananian 1.1.2.1 * keys must implement <code>java.lang.Comparable</code>.
31 cananian 1.1.2.1 * If <code>valueComparator</code> is <code>null</code>, then all
32 cananian 1.1.2.1 * values must implement <code>java.lang.Comparable</code>.
33 cananian 1.1.2.1 */
34 cananian 1.3 public MapComparator(Comparator<? super K> keyComparator,
35 cananian 1.3 Comparator<? super V> valueComparator) {
36 cananian 1.3 if (keyComparator==null) keyComparator = Default.<K>comparator();
37 cananian 1.3 if (valueComparator==null) valueComparator = Default.<V>comparator();
38 cananian 1.1.2.1 this.entryComparator =
39 cananian 1.3 new EntryComparator<K,V>(keyComparator, valueComparator);
40 cananian 1.3 this.listComparator =
41 cananian 1.3 new ListComparator<Map.Entry<K,V>>(true, entryComparator);
42 cananian 1.1.2.1 }
43 cananian 1.1.2.1
44 cananian 1.3 public int compare(Map<K,V> m1, Map<K,V> m2) {
45 cananian 1.3 ArrayList<Map.Entry<K,V>>
46 cananian 1.3 al1 = new ArrayList<Map.Entry<K,V>>(m1.entrySet()),
47 cananian 1.3 al2 = new ArrayList<Map.Entry<K,V>>(m2.entrySet());
48 cananian 1.1.2.1 Collections.sort(al1, entryComparator);
49 cananian 1.1.2.1 Collections.sort(al2, entryComparator);
50 cananian 1.1.2.1 return listComparator.compare(al1, al2);
51 cananian 1.1.2.1 }
52 cananian 1.3 private static class EntryComparator<K,V>
53 cananian 1.3 implements Comparator<Map.Entry<K,V>> {
54 cananian 1.3 final Comparator<? super K> keyComparator;
55 cananian 1.3 final Comparator<? super V> valueComparator;
56 cananian 1.3 EntryComparator(Comparator<? super K> keyComparator,
57 cananian 1.3 Comparator<? super V> valueComparator) {
58 cananian 1.1.2.1 this.keyComparator = keyComparator;
59 cananian 1.1.2.1 this.valueComparator = valueComparator;
60 cananian 1.1.2.1 }
61 cananian 1.3 public int compare(Map.Entry<K,V> me1, Map.Entry<K,V> me2) {
62 cananian 1.1.2.1 int c = keyComparator.compare(me1.getKey(), me2.getKey());
63 cananian 1.1.2.1 if (c!=0) return c;
64 cananian 1.1.2.1 return valueComparator.compare(me1.getValue(), me2.getValue());
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 }
67 cananian 1.2 }