Наличие Multimap, отсортированного по ключам только в Java

Я хотел бы иметь c.g.c.c.Multimap, который сортируется только на основе ключей. Значения не должны сортироваться. Я пытался создать что-то с guava TreeMultimap, но я не могу использовать его, потому что тип значения не реализует Comparable.

public class MyObject /* doesn't implement Comparable */ {
  private String name;
  private int score;
  // Getters/setters are implemented
  public static Function<MyObject,Integer> myObjectToScore {
    @Override public Integer apply (MyObject o) { return o.score; }
  }
  public static Multimap<Integer,MyObject> indexOnScore(Iterable<MyObject> i) {
    Multimap<Integer,MyObject> m = Multimaps.index(i, myObjectToScore());
    // Do the sort of the keys.
    return m;
  }
}

Я подумал о получении SortedSet ключей, а затем повторил по каждому из этих ключей в отсортированном наборе для получения различных значений, но я надеялся использовать существующую (но неоткрытую) функцию в Гуаве, а не используя этот вид взлома.

Примечание. Я не буду использовать MyObject реализовать Comparable, потому что это не имеет смысла с моим фактическим объектом.

Пример ввода/вывода:

Set<MyObject> s = Sets.newHashSet(
  new MyObject("a", 2),
  new MyObject("b", 3),
  new MyObject("c", 1),
  new MyObject("d", 3),
  new MyObject("e", 1)
); // Assuming constructor MyObject(String name, int score)

for (Map.Entry<Integer, MyObject> e: MyObject.indexedOnScore(s).entries()) {
  System.out.printf("%d -> %s%n", e.getKey(), e.getValue().getName());
}

Печать

1 -> c // or switched with line below
1 -> e
2 -> a
3 -> b // or switched with line below
3 -> d

Ответы

Ответ 1

Multimaps.index возвращает ImmutableListMultimap, поэтому вы не сможете отсортировать его после его создания. Однако вы можете сначала создать отсортированную копию вашего Iterable<MyObject> и подать, чтобы Multimap.index... ImmutableListMultimap хранит вещи в том же порядке, что и им.

public static ImmutableMultimap<Integer, MyObject> indexOnScore(Iterable<MyObject> i) {
  List<MyObject> sorted = Ordering.natural().onResultOf(myObjectToScore())
      .sortedCopy(i);
  return Multimaps.index(sorted, myObjectToScore());
}

Другим вариантом может быть создание TreeMultimap и использование Ordering.arbitrary() в качестве Comparator для значений.

Ответ 2

MultimapBuilder был введен в Guava 16:

<K extends Comparable<? super K>, V> ListMultimap<K, V> multimap() {
    return MultimapBuilder.treeKeys().linkedListValues().build();
}

Это держит ваши ключи отсортированными по их естественному порядку (treeKeys() также перегружен, чтобы принять пользовательский компаратор), а значения, связанные с каждым ключом, поддерживаются в LinkedList (ArrayList и HashSet входят в число другие варианты).

Ответ 3

Несмотря на то, что конкретная ситуация в OP, похоже, была получена с помощью встроенных функций построения multimap, мне нужна изменчивая версия того, что он просил. В случае, если это помогает кому-то, вот общий метод, который я создал:

static <K, V> Multimap<K, V> newTreeArrayListMultimap(
    final int expectedValuesPerKey)
{
    return Multimaps.newMultimap(new TreeMap<K, Collection<V>>(),
        new Supplier<Collection<V>>()
        {
            @Override
            public Collection<V> get()
            {
                return new ArrayList<V>(expectedValuesPerKey);
            }
        });
}

Ответ 4

Вызвать Multimaps.newMultimap, что дает вам гибкость для создания, например, Multimap, поддерживаемого TreeMap, значениями которого являются ArrayLists.

Ответ 5

Я хотел бы указать, что альтернативное предлагаемое решение, а именно "создать TreeMultimap и использовать Ordering.arbitrary() в качестве компаратора для значений", работает только в том случае, если MyObject не переопределяет equals() или hashcode(). Ordering.arbitrary() не согласуется с равенствами и вместо этого использует идентификатор объекта, что делает его нецелесообразным использовать в сочетании с TreeSet.

Ответ 6

Вы можете сделать это с помощью TreeMultimap, если вы используете Comparators.

Создайте Comparator для типа ключа и типа значения (MyObject?). Затем используйте create (Comparator keyComparator, Comparator valueComparator), чтобы сделать карту.

Преимущество использования компаратора над реализацией Comparable заключается в том, что вы можете сделать Comparator конкретным для ситуации, которую вы хотите с картой, и это не влияет на ваш объект в целом. Пока ваш компаратор совместим с равными, он может делать все, что вам нужно.

Ответ 7

Как насчет этого:

    public static Multimap<Integer, MyObject> indexOnScore(Iterable<MyObject> i) {
        Multimap<Integer, MyObject> m = Multimaps.index(i, myObjectToScore());

        Multimap<Integer, MyObject> sortedKeys = Multimaps.newMultimap(
                Maps.<Integer, Collection<MyObject>>newTreeMap(),
                new Supplier<Collection<MyObject>>() {
                    @Override
                    public Collection<MyObject> get() {
                        return Lists.newArrayList(); // Or a Set if appropriate
                    }
                }
        );

        sortedKeys.putAll(m);

        return sortedKeys;
    }

В этом случае накладные расходы на создание двух отдельных Multimap.