"""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]]. Thus, each distinct key 
   occurs in at most one entry. Two 
   non-[[identical|Identifiable]] keys are considered 
   distinct only if they are unequal, according to their own 
   definition of [[value equality|Object.equals]].
   
   A `Map` is a [[Collection]] of its `Entry`s, and a 
   [[Correspondence]] from keys to items.
   
   A new `Map` may be obtained by calling the function 
   [[ceylon.language::map]].
   
       value settings = map { "lang"->"en_AU", "loc"->"ES" };
   
   The [[emptyMap]] is a `Map` with no entries.
   
   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";
   
   An implementation of `Map` may compare keys for equality 
   using [[Object.equals]] or [[Comparable.compare]]."""
see (`class Entry`, `function package.map`,
     `function forKey`, `function forItem`, 
     `function byItem`, `function byKey`,
      `value emptyMap`)
tagged("Collections")
shared interface Map<out Key=Object, out Item=Anything>
        satisfies Collection<Key->Item> &
                  Correspondence<Object,Item>
        given Key satisfies Object {
    
    "Returns the item of the entry with the given [[key]], 
     or `null` if there is no entry with the given `key` in
     this map."
    see (`function getOrDefault`)
    shared actual formal Item? get(Object key);
    
    "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 the given [[default]] if there is no entry with the 
     given `key` in this map.
     
     For maps with non-null items, the expression:
     
         map.getOrDefault(key, def)
     
     is equivalent to this common idiom:
     
         map[key] else def
     
     However, when the map has null items, `getOrDefault()`
     will preserve them.
     
     Note that high-quality implementations of `Map` should 
     refine this default implementation."
    see (`function get`)
    shared default Item|Default getOrDefault<Default>
            (Object key, Default default) {
        if (defines(key)) {
            if (exists item = get(key)) {
                return item;
            }
            else {
                assert (is Item null);
                return null;
            }
        }
        else {
            return default;
        }
    }
    
    function lookup(Object key)
            => getOrDefault(key, Missing.instance);
    
    "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 Object->Anything entry, defines(entry.key)) {
            value item = get(entry.key);
            value entryItem = entry.item;
            return
                if (exists item, exists entryItem)
                then item == entryItem 
                else entryItem exists == item exists;
        }
        else {
            return false;
        }
    }
    
    distinct => this;
    
    shared actual {<Key->Item>*} 
    defaultNullElements<Default>(Default defaultValue)
            given Default satisfies Object => this;
    
    "A shallow copy of this map, that is, a map with the
     same entries as this map, which do not change if the
     entries in this map change."
    shared actual formal Map<Key,Item> clone();
    
    "A [[Collection]] containing the keys of this map."
    //TODO: should be a Set
    shared actual default Collection<Key> keys
            => object extends Object() 
                      satisfies Set<Key> {
        contains(Object key) => outer.defines(key);
        iterator() => outer.map(Entry.key).iterator();
        size => outer.size;
        empty => outer.empty;
        clone() => set(this);
    };
    
    "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 => Items();
    
    "A bag of items."
    class Items() extends Object() 
                  satisfies Collection<Item> {
        contains(Object item) 
                => outer.any((entry) 
                    => if (exists it = entry.item) 
                            then it==item 
                            else false);
        iterator() => outer.map(Entry.item).iterator();
        size => outer.size;
        empty => outer.empty;
        clone() => [*this];
        //implement hash and equals for bag semantics
        hash => frequencies().hash;
        equals(Object that) 
                => if (is Items that) 
                then frequencies()==that.frequencies() 
                else false;
    }
    
    "Invert this map, producing a new immutable map where 
     the keys of the new map are the non-null items of this
     map, and each item of the new map is a nonempty 
     sequence of keys of this map.
     
     For example, the expression:
     
         { \"fee\", \"fi\", \"fo\", \"fum\", \"foo\" }
            .tabulate(String.size)
            .inverse()
     
     produces the map 
     `{ 2->[\"fo\", \"fi\"], 3->[ \"fum\", \"fee\", \"foo\"] }`.
     
     The order of keys in the key sequences is not defined
     and should not be relied upon.
     
     This is an eager operation, and the resulting map does
     not reflect changes to this map."
    shared default Map<Item&Object, [Key+]> inverse() 
            => coalescedMap
                .summarize<Item&Object,ElementEntry<Key>>
                    (Entry.item, (keys, Key->Item entry) 
                        => ElementEntry(keys, entry.key));
                //not very useful, since the entries of a
                //map don't usually have a very meaningful
                //order (except for TreeMaps!)
                //.mapItems((_, item) => item.reversed);
    
    "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;
    }
    
    "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
            extends Object()
            satisfies Map<Key,Result> {
        
        defines(Object key) => outer.defines(key);
        
        shared actual Result? get(Object key) { 
            if (is Key key) {
                return
                    switch (item = outer.lookup(key))
                    case (Missing.instance) null
                    else mapping(key, item);
            }
            else {
                return null;
            } 
        }
        
        shared actual Result|Default
        getOrDefault<Default>
                (Object key, Default default) {
            if (is Key key) {
                return
                    switch (item = outer.lookup(key))
                    case (Missing.instance) default 
                    else mapping(key, item);
            }
            else {
                return default;
            }
        }
        
        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);
        
    };
    
    "Produces a map containing the elements of this map, 
     after replacing every `null` item in the map with the 
     [[given default value|defaultValue]]. The item `null` 
     does not ocur in the resulting map."
    see (`value coalescedMap`)
    shared default
    Map<Key,Item&Object|Default>
    defaultNullItems<Default>(
        "A default value that replaces `null` items."
        Default defaultValue)
            given Default satisfies Object
            => mapItems((key, elem) 
                => elem else defaultValue);
    
    "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
            extends Object()
            satisfies Map<Key,Item> {
        
        get(Object key)
                => if (is Key key, filtering(key))
                then outer[key] 
                else null;
        
        defines(Object key) 
                => if (is Key key, filtering(key))
                then outer.defines(key) 
                else false;
        
        shared actual Item|Default
        getOrDefault<Default>
                (Object key, Default default) 
                => if (is Key key, filtering(key))
                then outer.getOrDefault(key, default)
                else default;
        
        iterator() 
                => outer.filter(forKey(filtering))
                        .iterator();
        
        clone() => outer.clone().filterKeys(filtering);
        
    };
    
    "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.getOrDefault(key, 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
            => object 
            extends Object()
            satisfies Map<Key|OtherKey,Item|OtherItem> {
        
        defines(Object key) 
                => other.defines(key) || 
                   outer.defines(key);
        
        get(Object key) 
                => switch (result = other.lookup(key))
                case (Missing.instance) outer.get(key) 
                else result;
        
        shared actual OtherItem|Item|Default 
        getOrDefault<Default>
                (Object key, Default default) 
                => switch (result = other.lookup(key))
                case (Missing.instance)
                    outer.getOrDefault(key, default)
                else result;
        
        clone() => outer.clone().patch(other.clone());
        
        contains(Object entry)
                => if (is Object->Anything entry)
                then entry in other ||
                        !other.defines(entry.key)
                            && entry in outer
                else 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)));
        
    };
    
    "A map with every entry of this map whose item is
     non-null."
    see (`function defaultNullItems`)
    shared default
    Map<Key,Item&Object> coalescedMap 
            => object
            extends Object()
            satisfies Map<Key,Item&Object> {
        
        defines(Object key) => outer[key] exists;
        
        get(Object key) => outer[key] of <Item&Object>?;
        
        shared actual Default|Item&Object 
        getOrDefault<Default>
                (Object key, Default default)
                => outer.getOrDefault(key, default) 
                    else default;
        
        iterator()
                => { for (entry in outer) 
                     if (exists it=entry.item) 
                            entry.key->it }
                        .iterator();
        
        clone() => outer.clone().coalescedMap;
        
    };
    
}

"Create a new immutable [[Map]] containing every [[Entry]] 
 produced by the given [[stream]], resolving items with
 duplicate keys according to the given [[function|choosing]].
 
 For example:
 
     map { 1->\"hello\", 2->\"goodbye\" }
 
 produces the map `{ 1->\"hello\", 2->\"goodbye\" }`.
 
 This is an eager operation and the resulting map does not 
 reflect changes to the given [[stream]]."
shared Map<Key,Item> map<Key,Item>(
    "The stream of entries."
    {<Key->Item>*} stream,
    "A function that chooses between items with duplicate 
     keys. By default, the item that occurs _earlier_ in the 
     stream is chosen."
    Item choosing(Item earlier, Item later) => earlier)
        given Key satisfies Object
        => stream.summarize(Entry.key, 
                (Item? item, entry) 
                        => if (exists item) 
                        then choosing(item, entry.item)
                        else entry.item);

"An immutable [[Map]] with no entries."
tagged("Collections")
shared object emptyMap 
        extends Object() 
        satisfies Map<Nothing, Nothing> {
    
    get(Object key) => null;
    
    shared actual Default getOrDefault<Default>
            (Object key, Default default) => default;
    
    keys => emptySet;
    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;
    
    count(Boolean selecting(Nothing->Nothing element)) => 0;
    any(Boolean selecting(Nothing->Nothing element)) => false;
    every(Boolean selecting(Nothing->Nothing element)) => true;
    
    shared actual 
    Null find(Boolean selecting(Nothing->Nothing element)) 
            => null;
    
    shared actual 
    Null findLast(Boolean selecting(Nothing->Nothing element)) 
            => null;
        
    skip(Integer skipping) => this;
    take(Integer taking) => this;
    by(Integer step) => this;
    
    shared actual 
    void each(void step(Nothing->Nothing element)) {}
    
}

class Missing of instance {
    shared new instance {}
}