Java data structure

Question

I need some data structure that I can build from standard collections or using guava. So it should be mutable Map<Enum, V>. Where V is pretty interesting structure.

V requirements:

• mutable
• sorted by comparator (with allowing elements such as compare(a, b) == 0) - these is need for iterations
• set (there is no such a and b, that a.equals(b) == true) - optional

extra optional requirement to map

• keys should be iterated by their natural order

now it's HashMap<SomeEnum, LinkedList<Entity>> with different stuff like collections.sort() in the code.

Thanks.

Answer 1

A Sample implementation

Here is a Guava Multimap implementation of the class you need:

First the drawback: it will have to reside in package com.google.common.collect. The makers of guava have in their infinite wisdom made AbstractSortedSetMultimap package scoped.

I will use this enum in all my examples:

public enum Color{
    RED, BLUE, GREEN
};

Constructing the Class

There are six constructors:

• Empty (Uses a HashMap and natural ordering for values)

  SortedSetMultimap<Color,String> simple = 
      new EnumValueSortMultiMap<Color, String>();
  

• with a Comparator(V) (Uses a HashMap<K,SortedSet<V>> with the supplied comparator for the values)

  SortedSetMultimap<Color,String> inreverse =
      new EnumValueSortMultiMap<Color, String>(
          Ordering.natural().reverse()
      );
  

• with a Map<K,SortedSet<V>> (use this if you want to sort keys, pass in a SortedMap implementation)

  SortedSetMultimap<Color,String> withSortedKeys = 
      new EnumValueSortMultiMap<Color, String>(
          new TreeMap<Color, Collection<String>>()
      );
  

• with a Map<K,SortedSet<V>> and a Comparator<V> (same as above, but values are sorted using custom comparator)

  SortedSetMultimap<Color,String> reverseWithSortedKeys = 
      new EnumValueSortMultiMap<Color, String>(
          new TreeMap<Color, Collection<String>>(),
          Ordering.natural().reverse()
      );
  

• with a Class<K extends Enum<K>> (uses an EnumMap internally for higher efficiency, natural ordering for values)

  SortedSetMultimap<Color,String> withEnumMap =
      new EnumValueSortMultiMap<Color, String>(
          Color.class
      );
  

• with a Class<K extends Enum<K>> and a Comparator<V> (same as above, but values are sorted using custom comparator)

  SortedSetMultimap<Color,String> reverseWithEnumMap =
      new EnumValueSortMultiMap<Color, String>(
          Color.class, Ordering.natural().reverse()
      );
  

Source Code

Here's the class:

package com.google.common.collect;

import java.util.Collection;
import java.util.Comparator;
import java.util.EnumMap;
import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;

public class EnumValueSortMultiMap<K extends Enum<K>,
    V extends Comparable<? super V>>
    extends AbstractSortedSetMultimap<K, V>{

    private static final long serialVersionUID = 5359491222446743952L;

    private Comparator<? super V> comparator;
    private Class<K> enumType;

    public EnumValueSortMultiMap(){
        this(new HashMap<K, Collection<V>>());
    }

    public EnumValueSortMultiMap(final Comparator<? super V> comparator){
        this(new HashMap<K, Collection<V>>(), comparator);
    }

    public EnumValueSortMultiMap(final Map<K, Collection<V>> map){
        this(map, Ordering.natural());
    }

    public EnumValueSortMultiMap(final Map<K, Collection<V>> map,
        final Comparator<? super V> comparator){
        super(map);
        this.comparator = comparator;
    }

    public EnumValueSortMultiMap(final Class<K> enumClass,
        final Comparator<? super V> comparator){
        this(new EnumMap<K, Collection<V>>(enumClass), comparator);
    }

    public EnumValueSortMultiMap(final Class<K> enumClass){
        this(new EnumMap<K, Collection<V>>(enumClass));
    }

    @Override
    Map<K, Collection<V>> backingMap(){
        return new EnumMap<K, Collection<V>>(enumType);
    }

    @Override
    public Comparator<? super V> valueComparator(){
        return comparator;
    }

    @Override
    SortedSet<V> createCollection(){
        return new TreeSet<V>(comparator);
    }

}

---

Other ways to do it

UPDATE: I guess the proper Guava way to do it would have been something like this (it uses the SortedArrayList class I wrote in my other answer):

public static <E extends Enum<E>, V> Multimap<E, V> getMap(
    final Class<E> clz){

    return Multimaps.newListMultimap(
        Maps.<E, Collection<V>> newEnumMap(clz),
        new Supplier<List<V>>(){
            @Override
            public List<V> get(){
                return new SortedArrayList<V>();
            }
        }
    );
}

Answer 2

If an extra class is too much, you maybe want to use the factory methods of the class Multimaps.

SortedSetMultimap<Color, Entity> set = Multimaps.newSortedSetMultimap(
    new HashMap<Enum, Collection<Entity>>(), 
    new Supplier<TreeSet<Entity>>() {
        @Override
        public TreeSet<Entity> get() {
            return new TreeSet<Entity>(new Comparator<Entity>() {
                @Override
                public int compare(Entity o1, Entity o2) {
                    //TODO implement
                }
            });
        }
});

Answer 3

You can use an EnumMap instead of the current HashMap. EnumMaps are more efficient for enum keys. In guava check Multimap [examples].

Answer 4

You need an collection implementation V which is used this way: HashMap<SomeEnum, V>. The above stated requirements affect V (not Entity). Right?

I think a link TreeSet<E> should fullfill your requirents:

• TreeSet implements the Set interface
• Sorted by natural order or custom Comparator
• Elements can be added and removed