How to preserve insertion order in HashMap in Vala

Question

I'm using a HashMap. When I iterate over the map, the data is returned in (often the same) random order. But the data was inserted in a specific order, and I need to preserve the insertion order. How can I do this in Vala? In Java there is LinkedHashMap but I don't see any equivalent for Gee.Map.

Answer 1

Never heard of Vala, but it's easy to do (roughly) on your own what LinkedHashMap does internally. Write a wrapper that contains a doubly linked list of keys along with the hash map. Values in the map must consist of pairs, where one element is the actual map value and the other is a reference to the linked list node for the key. For each add, enqueue the key at the end of the list in addition to adding the key-><value, node ptr> entry to the map. For each remove, delete the associated key from the list using the node pointer (a constant time operation due to the double links), then remove the entry from the map. To look up a key, use the map. To traverse in insertion order, traverse the list.

Okay, since the originally accepted answer turned out to be incorrect, here's a quick and dirty working example in Java. I'll let you translate to Vala.

import java.util.HashMap;
import java.util.Iterator;

public class MyLinkedHashMap<K, V> implements Iterable<K> {
  private final HashMap<K, Pair<K, V>> map = new HashMap<>();
  private final Link<K> header = makeHeader();

  /** Hash value along with a link reference to support remove(). */
  private static class Pair<K, V> {
    V value;
    Link<K> link;

    Pair(V value, Link<K> link) {
      this.value = value;
      this.link = link;
    }
  }

  /** A link in the doubly linked list of keys. */
  private static class Link<K> {
    K key;
    Link<K> prev;
    Link<K> next;

    Link() {}
    Link(K key, Link<K> prev, Link<K> next) {
      this.key = key;
      this.prev = prev;
      this.next = next;
    }
  }

  @Override
  public Iterator<K> iterator() {
    return new MyLinkedHashMapIterator();
  }

  /** Iterator over map keys guaranteed to produce insertion order. */
  private class MyLinkedHashMapIterator implements Iterator<K> {
    private Link<K> ptr = header.next;

    @Override
    public boolean hasNext() {
      return ptr != header;
    }

    @Override
    public K next() {
      K key = ptr.key;
      ptr = ptr.next;
      return key;
    }
  }

  /** Make a header for a circular doubly linked list. */
  private static <K> Link<K> makeHeader() {
    Link<K> header = new Link<K>();
    return header.next = header.prev = header;
  }

  /** Put a key/value in the map, remembering insertion order with a link in the list. */
  public V put(K key, V value) {
    Link<K> link = new Link<K>(key, header.prev, header);
    link.prev.next = link;
    header.prev = link;
    Pair<K, V> pair = map.put(key, new Pair<>(value, link));
    return pair == null ? null : pair.value;
  }

  /** Get the value mapped to a key or return {@code null} if none. */
  public V get(K key) {
   Pair<K, V> pair =  map.get(key);
   return pair == null ? null : pair.value;
  }

  /** Remove a key from both map and linked list. */
  public V remove(K key) {
    Pair<K, V> pair = map.remove(key);
    if (pair == null) {
      return null;
    }
    pair.link.prev.next = pair.link.next;
    pair.link.next.prev = pair.link.prev;
    return pair.value;
  }

  /** Trivial unit test. */
  public static void main(String [] args) {
    MyLinkedHashMap<String, Integer> map = new MyLinkedHashMap<>();
    int n = 0;
    for (String key : new String [] { "one", "two", "three", "four", "five", "six", "seven" }) {
      map.put(key, ++n);
    }
    for (String key : map) {
      System.out.println("For key " + key + " we have " + map.get(key));
    }
    String [] evenKeys = new String [] { "two", "four", "six" };
    for (String evenKey : evenKeys) {
      map.remove(evenKey);
    }
    System.out.println("After even keys removed...");
    for (String key : map) {
      System.out.println("For key " + key + " we have " + map.get(key));
    }
    n = 0;
    for (String evenKey : evenKeys) {
      map.put(evenKey, n += 2);
    }
    System.out.println("After putting them back again...");
    for (String key : map) {
      System.out.println("For key " + key + " we have " + map.get(key));
    }
  }
}

This produces:

For key one we have 1
For key two we have 2
For key three we have 3
For key four we have 4
For key five we have 5
For key six we have 6
For key seven we have 7
After even keys removed...
For key one we have 1
For key three we have 3
For key five we have 5
For key seven we have 7
After putting them back again...
For key one we have 1
For key three we have 3
For key five we have 5
For key seven we have 7
For key two we have 2
For key four we have 4
For key six we have 6

Answer 2

As far as I know, there is no equivalent of LinkedHashMap in Vala. Using a TreeMap and setting the comparison function to always return 1 (or -1 if you want the reverse order) for other Map entries will preserve the order and allow you to iterate through the Map in the order that items were added but get will not function as expected.

Unfortunately, after thoroughly examining the Gee source, there appears to be no way other than to roll your own. The most straightforward way is to subclass HashMap and use an ArrayList to keep a track of the order of the keys as they are inserted. You could also use a LinkedList, you would only need to change the internal ArrayList _keys field to a LinkedList. The choice depends on your use case. From the docs -

This implementation (ArrayList) is pretty good for rarely modified data. Because they are stored in an array this structure does not fit for highly mutable data.

The following is a basic implementation, in Vala (arrayhashmap.vala):

using Gee;

public class ArrayHashMap<K,V> : HashMap<K,V> {

    private weak Set<K> _keyset;
    private weak Collection<V> _values;
    private weak Set<Entry<K,V>> _entries;
    internal ArrayList<K> _keys = new ArrayList<K>();

    private class KeySet<K> : AbstractSet<K> {

        private weak ArrayList<K> _keys;

        public KeySet (ArrayList<K> keys) {
            _keys = keys;
        }

        public override Iterator<K> iterator () {
            return _keys.iterator();
        }

        public override int size {
            get { return _keys.size; }
        }

        public override bool read_only {
            get { return true; }
        }

        public override bool add (K key) {
            assert_not_reached ();
        }

        public override void clear () {
            assert_not_reached ();
        }

        public override bool remove (K key) {
            assert_not_reached ();
        }

        public override bool contains (K key) {
            return _keys.contains (key);
        }
    }

    private class ValueCollection<K,V> : AbstractCollection<V> {
        private weak ArrayHashMap<K,V> _map;

        public ValueCollection (ArrayHashMap map) {
            _map = map;
        }

        public override Iterator<V> iterator () {
            return new ValueIterator<K,V> (_map);
        }

        public override int size {
            get { return _map.size; }
        }

        public override bool read_only {
            get { return true; }
        }

        public override bool add (V value) {
            assert_not_reached ();
        }

        public override void clear () {
            assert_not_reached ();
        }

        public override bool remove (V value) {
            assert_not_reached ();
        }

        public override bool contains (V value) {
            Iterator<V> it = iterator ();
            while (it.next ()) {
                if (_map.value_equal_func (it.get (), value)) {
                    return true;
                }
            }
            return false;
        }
    }

    private class ValueIterator<K,V> : Object, Traversable<V>, Iterator<V> {
        protected weak ArrayHashMap<K,V> _map;
        protected Iterator<K> _keys;

        public ValueIterator (ArrayHashMap<K,V> map) {
            _map = map;
            _keys = map._keys.iterator();
        }

        public bool next () {
            return _keys.next();
        }

        public bool has_next () {
            return _keys.has_next();
        }

        public virtual bool read_only {
            get {
                return true;
            }
        }

        public bool valid {
            get {
                return _keys.valid;
            }
        }

        public new V get () {
            return _map.get(_keys.get());
        }

        public void remove () {
            assert_not_reached ();
        }

        public bool foreach(ForallFunc<V> f) {
            foreach (K key in _map._keys)
                if (!f(_map.get(key)))
                    return false;
            return true;
        }
    }

    private class EntrySet<K,V> : AbstractSet<Entry<K, V>> {
        private weak ArrayHashMap<K,V> _map;

        public EntrySet (ArrayHashMap<K,V> map) {
            _map = map;
        }

        public override Iterator<Entry<K, V>> iterator () {
            return new EntryIterator<K,V> (_map);
        }

        public override int size {
            get { return _map.size; }
        }

        public override bool read_only {
            get { return true; }
        }

        public override bool add (Entry<K, V> entry) {
            assert_not_reached ();
        }

        public override void clear () {
            assert_not_reached ();
        }

        public override bool remove (Entry<K, V> entry) {
            assert_not_reached ();
        }

        public override bool contains (Entry<K, V> entry) {
            return _map.has (entry.key, entry.value);
        }
    }

    private class EntryIterator<K,V> : Object, Traversable<Entry<K,V>>, Iterator<Entry<K,V>> {
        protected weak ArrayHashMap<K,V> _map;
        protected Iterator<K> _keys;

        public EntryIterator (ArrayHashMap<K,V> map) {
            _map = map;
            _keys = map._keys.iterator();
        }

        public bool next () {
            return _keys.next();
        }

        public bool has_next () {
            return _keys.has_next();
        }

        public virtual bool read_only {
            get {
                return true;
            }
        }

        public bool valid {
            get {
                return _keys.valid;
            }
        }

        public new Entry<K,V> get () {
            K* k = _keys.get();
            var ent = new Entry<K,V>(k, _map.get(k));
            return ent;
        }

        public void remove () {
            assert_not_reached ();
        }

        public bool foreach(ForallFunc<Entry<K,V>> f) {
            foreach (K key in _map._keys)
                if (!f(new Entry<K,V>(key, _map.get(key))))
                    return false;
            return true;
        }
    }

    public class Entry<K,V> : Map.Entry<K,V> {
        weak K _key;
        weak V _value;

        public override K key {
            get {
                return _key;
            }
        }

        public override V value {
            get {
                return _value;
            } set {
                _value = value;
            }
        }

        public override bool read_only {get { return true; }}

        public Entry (K key, V value) {
            this._key = key;
            this._value = value;
        }
    }

    public new void @set(K key, V value) {
        if (!_keys.contains(key))
        _keys.add(key);
        base.set(key, value);
    }

    public new void unset(K key, out V? value = null) {
        _keys.remove(key);
        base.unset(key, out value);
    }

    public new void clear() {
        base.clear();
        _keys.clear();
    }

    public new Set<unowned K> keys {
        owned get {
            Set<K> keys = _keyset;
            if (_keyset == null) {
                keys = new KeySet<K> (_keys);
                _keyset = keys;
                keys.add_weak_pointer ((void**) (&_keyset));
            }
            return keys;
        }
    }

    public new Collection<unowned V> values {
        owned get {
            Collection<K> values = _values;
            if (_values == null) {
                values = new ValueCollection<K,V> (this);
                _values = values;
                values.add_weak_pointer ((void**) (&_values));
            }
            return values;
        }
    }

    public override Set<Entry<K,V>> entries {
        owned get {
            Set<Entry<K,V>> entries = _entries;
            if (_entries == null) {
                entries = new EntrySet<K,V> (this);
                _entries = entries;
                entries.add_weak_pointer ((void**) (&_entries));
            }
            return entries;
        }
    }

}

You can test it with this awful test case (tests.vala):

public static void doTest() {
    const string[] strings = { "test", "another", "one-more", "how-about-this-one", "even-more" };

    var entries3 = new ArrayHashMap<string, int>();

    for (int i = 0; i < strings.length; i++)
        entries3.set(strings[i], i);

    entries3.unset("one-more");

    foreach (var entry in entries3.keys)
        message ("%s:%d", entry, entries3.get(entry));

    entries3.set ("for-your-viewing-pleasure", 3);

    foreach (var entry in entries3.keys)
        message ("%s:%d", entry, entries3.get(entry));

    entries3.set ("for-your-viewing-pleasure", 7);

    foreach (var entry in entries3.entries)
        message ("%s:%d", entry.key, entries3.get(entry.key));

}

public static int main (string[] args) {
    Test.init(ref args);
    Test.add_func ("/ArrayHashMap", doTest);
    Test.run();
    return 0;
}

Run the whole package together:

valac --pkg gee-0.8 -g tests.vala arrayhashmap.vala

This is a very rough implementation, based on how HashMap works internally. You may want to refactor it for better maintainability and write some more unit tests. If you find any problems, let me know and we can work through them.

I hope this helps.