"""Represents a collection which maps _keys_ to _items_,
   where a key can map to at most one item. Each such 
   mapping may be represented by an [[Entry]].
   
   A `Map` is a [[Collection]] of its `Entry`s, and a 
   [[Correspondence]] from keys to items.
   
   The presence of an entry in a map may be tested using the 
   `in` operator:
   
       if ("lang"->"en_AU" in settings) { ... }
 
   The entries of the map may be iterated using `for`:
   
       for (key->item in settings) { ... }
   
   The item for a key may be obtained using the item
   operator:
   
       String lang = settings["lang"] else "en_US";
   
   Keys are compared for equality using [[Object.equals]] or
   [[Comparable.compare]]. There may be at most one entry 
   per key."""
see (`class Entry`, 
     `function forKey`, `function forItem`, 
     `function byItem`, `function byKey`)
shared interface Map<out Key,out Item>
        satisfies Collection<Key->Item> &
                  Correspondence<Object,Item>
        given Key satisfies Object {
    
    "Determines if there is an entry in this map with the
     given [[key]]."
    see (`function contains`)
    shared actual formal Boolean defines(Object key);
    
    "Returns the item of the entry with the given [[key]], 
     or `null` if there is no entry with the given `key` in
     this map."
    shared actual formal Item? get(Object key);
    
    "Determines if the given [[value|entry]] is an [[Entry]]
     belonging to this map."
    see (`function defines`)
    shared actual default Boolean contains(Object entry) {
        if (is Key->Anything entry, defines(entry.key)) {
            if (exists item = get(entry.key)) {
                if (exists entryItem = entry.item) {
                    return item==entryItem;
                }
                else {
                    return false;
                }
            }
            else {
                return !entry.item exists;
            }
        }
        else {
            return false;
        }
    }
    
    shared actual formal Map<Key,Item> clone();
    
    "Two maps are considered equal iff they have the same 
     _entry sets_. The entry set of a `Map` is the set of 
     `Entry`s belonging to the map. Therefore, the maps are 
     equal iff they have same set of `keys`, and for every 
     key in the key set, the maps have equal items."
    shared actual default Boolean equals(Object that) {
        if (is Map<Object,Anything> that,
                that.size==size) {
            for (entry in this) {
                value thatItem = that[entry.key];
                if (exists thisItem = entry.item) {
                    if (exists thatItem) {
                        if (thatItem!=thisItem) {
                            return false;
                        }
                    }
                    else {
                        return false;
                    }
                }
                else if (thatItem exists) {
                    return false;
                }
            }
            else {
                return true;
            }
        }
        else {
            return false;
        }
    }
    
    shared actual default Integer hash {
        variable Integer hashCode = 0;
        for (elem in this) {
            hashCode += elem.hash;
        }
        return hashCode;
    }
    
    "A [[Collection]] containing the keys of this map."
    actual shared default Collection<Key> keys {
        object keys
                satisfies Collection<Key> {
            contains(Object key) => outer.defines(key);
            iterator() => { for (k->v in outer) k }.iterator();
            clone() => [*this];
            size => outer.size;
        }
        return keys;
    }
    
    "A [[Collection]] containing the items stored in this 
     map. An element can be stored under more than one key 
     in the map, and so it can occur more than once in the 
     resulting collection."
    shared default Collection<Item> items {
        object items
                satisfies Collection<Item> {
            shared actual Boolean contains(Object item) {
                for (k->v in outer) {
                    if (exists v, v==item) {
                        return true;
                    }
                }
                return false;
            }
            iterator() => { for (k->v in outer) v }.iterator();
            clone() => [*this];
            size => outer.size;
        }
        return items;
    }
    
    "Produces a map with the same [[keys]] as this map. 
     For every key, the item is the result of applying the 
     given [[transformation|Map.mapItems.mapping]] function 
     to its associated item in this map. This is a lazy 
     operation, returning a view of this map."
    shared default Map<Key,Result> mapItems<Result>(
        "The function that transforms a key/item pair of
         this map, producing the item of the resulting map."
        Result mapping(Key key, Item item)) 
            given Result satisfies Object {
        object map
                extends Object()
                satisfies Map<Key,Result> {
            
            defines(Object key) => outer.defines(key);
            
            shared actual Result? get(Object key) {
                if (is Key key, defines(key)) {
                    assert (is Item item = outer[key]);
                    return mapping(key, item);
                }
                else {
                    return null;
                }
            }
            
            function mapEntry(Key->Item entry) 
                    => entry.key -> 
                        mapping(entry.key, entry.item);
            
            iterator() => outer.map(mapEntry).iterator();
            
            size => outer.size;
            
            clone() => outer.clone().mapItems(mapping);
            
        }
        return map;
    }
    
    "Produces a map by applying a [[filtering]] function 
     to the [[keys]] of this map. This is a lazy operation, 
     returning a view of this map."
    shared default Map<Key,Item> filterKeys(
        "The predicate function that filters the keys of 
         this map, determining if there is a corresponding
         entry in the resulting map."
        Boolean filtering(Key key)) {
        object map
                extends Object()
                satisfies Map<Key,Item> {
            
            shared actual Item? get(Object key) {
                if (is Key key, filtering(key)) {
                    return outer[key];
                }
                else {
                    return null;
                }
            }
            
            shared actual Boolean defines(Object key) {
                if (is Key key, filtering(key)) {
                    return outer.defines(key);
                }
                else {
                    return false;
                }
            }
            
            function filterEntry(Key->Item entry) 
                    => filtering(entry.key);
            
            iterator() => outer.filter(filterEntry).iterator();
            
            clone() => outer.clone().filterKeys(filtering);
            
        }
        return map;
    }
    
    "Produces a map whose keys are the union of the keys
     of this map, with the keys of the given [[map|other]].
     For any given key in the resulting map, its associated
     item is the item associated with the key in the given
     map, if any, or the item associated with the key in 
     this map otherwise.
     
     That is, for any `key` in the resulting patched map:
     
         map.patch(other)[key] == other[key] else map[key]
     
     This is a lazy operation producing a view of this map
     and the given map."
    shared default
    Map<Key|OtherKey,Item|OtherItem> patch<OtherKey,OtherItem>
            (Map<OtherKey,OtherItem> other) 
            given OtherKey satisfies Object 
            given OtherItem satisfies Object {
        object patch 
                extends Object()
                satisfies Map<Key|OtherKey,Item|OtherItem> {
            
            get(Object key) => other[key] else outer[key];
            
            clone() => outer.clone().patch(other.clone());
            
            defines(Object key) 
                    => other.defines(key) || 
                       outer.defines(key);
            
            shared actual Boolean contains(Object entry) {
                if (is Entry<Object,Object> entry) {
                    return entry in other || 
                            !other.defines(entry.key) 
                                && entry in outer;
                }
                else {
                    return false;
                }
            }
            
            //efficient when map is much smaller than outer,
            //which is probably the common case 
            size => outer.size +
                    other.keys.count(not(outer.defines));
            
            iterator() => ChainedIterator(other,
                outer.filter(not(other.contains)));
            
        }
        return patch;
    }
    
}

"An immutable [[Map]] with no entries."
shared object emptyMap 
        extends Object() 
        satisfies Map<Nothing, Nothing> {
    
    shared actual Null get(Object key) => null;
    shared actual Collection<Nothing> keys
            => emptySet;
    shared actual Collection<Nothing> items
            => emptySet;
    
    clone() => this;
    iterator() => emptyIterator;
    size => 0;
    empty => true;
    
    defines(Object index) => false;
    
    contains(Object element) => false;
    containsAny({Object*} elements) => false;
    containsEvery({Object*} elements) => false;
    
    shared actual Map<Nothing, Nothing> mapItems<Result>
            (Result mapping(Nothing key, Nothing item))
            given Result satisfies Object 
            => emptyMap;
    
    shared actual Integer count
            (Boolean selecting(Nothing->Nothing element)) 
            => 0;
    
    shared actual Null find
            (Boolean selecting(Nothing->Nothing element)) 
            => null;
    
    shared actual Null findLast
            (Boolean selecting(Nothing->Nothing element)) 
            => null;
    
    shared actual Boolean any
            (Boolean selecting(Nothing->Nothing element)) 
            => false;
    
    shared actual Boolean every
            (Boolean selecting(Nothing->Nothing element)) 
            => true;
    
    skip(Integer skipping) => this;
    take(Integer taking) => this;
    by(Integer step) => this;
    
}