MAP

template <typename K, typename V> pure Map<K, V> map();
template <typename K, typename V> pure bool empty(Map<K, V> m);
template <typename K, typename V> pure Map<K, V> insert(Map<K, V> m, Tuple<K, V> k);
template <typename K, typename V> pure Optional<Tuple<K, V>> find(Map<K, V> m, const K &k);
template <typename K, typename V> pure Map<K, V> erase(Map<K, V> m, const K &k);
template <typename K, typename V> pure size_t size(Map<K, V> m);
template <typename K, typename V, typename A, typename F> pure A foldl(Map<K, V> m, const A &arg, F func);
template <typename K, typename V, typename A, typename F> pure A foldr(Map<K, V> m, const A &arg, F func);
template <typename W, typename K, typename V, typename F> pure Map<K, W> map(Map<K, V> m, F func);
template <typename K, typename V> pure List<K> keys(Map<K, V> m);
template <typename K, typename V> pure List<V> values(Map<K, V> m);
template <typename K, typename V> pure Result<Map<K, V>, Map<K, V>> split(Map<K, V> m, K k);
template <typename K, typename V> pure Map<K, V> merge(Map<K, V> ma, Map<K, V> mb);
template <typename K, typename V> pure bool verify(Map<K, V> m);
template <typename K, typename V> pure int compare(Map<K, V> m1, Map<K, V> m2);
template <typename K, typename V> pure String show(Map<K, V> m);
template <typename K, typename V> pure MapItr<K, V> begin(Map<K, V> m);
template <typename K, typename V> pure MapItr<K, V> end(Map<K, V> m);
template <typename K, typename V> MapItr<K, V> &operator++(MapItr<K, V> &i);
template <typename K, typename V> MapItr<K, V> &operator--(MapItr<K, V> &i);
template <typename K, typename V> MapItr<K, V> &operator+(MapItr<K, V> &i, ssize_t offset);
template <typename K, typename V> MapItr<K, V> &operator-(MapItr<K, V> &i, ssize_t offset);
template <typename K, typename V> MapItr<K, V> &operator+=(MapItr<K, V> &i, ssize_t offset);
template <typename K, typename V> MapItr<K, V> &operator-=(MapItr<K, V> &i, ssize_t offset);
template <typename K, typename V> pure Tuple<K, V> operator*(MapItr<K, V> &i);
template <typename K, typename V> bool operator==(const MapItr<K, V> &i, const MapItr<K, V> &j);
template <typename K, typename V> bool operator!=(const MapItr<K, V> &i, const MapItr<K, V> &j);

template <typename K, typename V>
pure Map<K, V> map()

Construct an empty map. O(1).

template <typename K, typename V>
pure bool empty(Map<K, V> m)

Test if a map is empty. O(1).

template <typename K, typename V>
pure Map<K, V> insert(Map<K, V> m, Tuple<K, V> k)

Insert a key-valuue pair into a map. O(log(n)).

template <typename K, typename V>
pure Optional<Tuple<K, V>> find(Map<K, V> m, const K &k)

Find an entry in the map. O(log(n)).

template <typename K, typename V>
pure Map<K, V> erase(Map<K, V> m, const K &k)

Remove an entry from the map. O(log(n)).

template <typename K, typename V>
pure size_t size(Map<K, V> m)

Map size. O(1).

template <typename K, typename V, typename A, typename F>
pure A foldl(Map<K, V> m, const A &arg, F func)

Map fold left. ([](A a, Tuple<K, V> e) -> A). O(n).

template <typename K, typename V, typename A, typename F>
pure A foldr(Map<K, V> m, const A &arg, F func)

Map fold right. ([](A a, Tuple<K, V> e) -> A). O(n).

template <typename W, typename K, typename V, typename F>
pure Map<K, W> map(Map<K, V> m, F func)

Map map. ([](Tuple<K, V> e) -> Tuple<K, W>). O(n).

template <typename K, typename V>
pure List<K> keys(Map<K, V> m)

All map keys. O(n).

template <typename K, typename V>
pure List<V> values(Map<K, V> m)

All map Values. O(n).

template <typename K, typename V>
pure Result<Map<K, V>, Map<K, V>> split(Map<K, V> m, K k)

Map split. O(log(n)).

template <typename K, typename V>
pure Map<K, V> merge(Map<K, V> ma, Map<K, V> mb)

Map merge. O(log(n) + log(m)).

template <typename K, typename V>
pure bool verify(Map<K, V> m)

Map verify. O(n).

template <typename K, typename V>
pure int compare(Map<K, V> m1, Map<K, V> m2)

Map compare. O(n).

template <typename K, typename V>
pure String show(Map<K, V> m)

Map show. O(n).

template <typename K, typename V>
pure MapItr<K, V> begin(Map<K, V> m)

Construct an iterator pointing to the least entry of a map. O(1).

template <typename K, typename V>
pure MapItr<K, V> end(Map<K, V> m)

Construct an iterator representing one past the greatest entry of a map. O(1).

template <typename K, typename V>
MapItr<K, V> &operator++(MapItr<K, V> &i)

Map iterator increment. O(1).

template <typename K, typename V>
MapItr<K, V> &operator--(MapItr<K, V> &i)

Map iterator decrement. O(1).

template <typename K, typename V>
MapItr<K, V> &operator+(MapItr<K, V> &i, ssize_t offset)

Map iterator add offset. O(1).

template <typename K, typename V>
MapItr<K, V> &operator-(MapItr<K, V> &i, ssize_t offset)

Map iterator substract offset. O(1).

template <typename K, typename V>
MapItr<K, V> &operator+=(MapItr<K, V> &i, ssize_t offset)

Map iterator add offset. O(1).

template <typename K, typename V>
MapItr<K, V> &operator-=(MapItr<K, V> &i, ssize_t offset)

Map iterator substract offset. O(1).

template <typename K, typename V>
pure Tuple<K, V> operator*(MapItr<K, V> &i)

Map iterator dereference. O(log(delta)), where delta is distance to last dereference.

template <typename K, typename V>
bool operator==(const MapItr<K, V> &i, const MapItr<K, V> &j)

Map iterator same offset. O(1).

template <typename K, typename V>
bool operator!=(const MapItr<K, V> &i, const MapItr<K, V> &j)

Map iterator different offset. O(1).