Module MTreeMap

Views the given mutable map as a tree map.

This is an unchecked downcast, not a conversion: it only re-types the map it is given. Applying it to a map that is not a tree map, for example a hash map from MMap.create, fails immediately with a ClassCastException. The maps it accepts are the ones create and subMap produce.

See create for an example of the create, populate, asTreeMap, query route.

The entry of the map whose key is the least one greater than or equal to the given key. See floorEntry for an example.

The least key of the map that is greater than or equal to the given key. See floorKey for an example comparing all four of these functions.

Creates a new empty tree map.

Note the return type: the result is an MMap.T, not an MTreeMap.T. None of the sorted operations of this module can be reached from that type, so the result has to be passed through asTreeMap first. Entries are added and read with the ordinary MMap operations either way.

The key and value types cannot be inferred from create () alone, so the binding needs an annotation.

Example:

> import "MTreeMap" as MTreeMap
> m = MTreeMap.create () :: <Proc> MMap.T Integer String
> MMap.put m 30 "thirty"
Nothing
> MMap.put m 10 "ten"
Nothing
> MMap.put m 20 "twenty"
Nothing
> MMap.entries m
[(10, "ten"), (20, "twenty"), (30, "thirty")]
> MTreeMap.floorKey (MTreeMap.asTreeMap m) 25
Just 20

Unlike the entries of a hash map, the entries of a tree map come out in key order, so this example needs no sort.

The entry of the map whose key is the greatest one less than or equal to the given key. The entry type is MMap.Entry; take it apart with MMap.keyOf and MMap.valueOf.

Example:

> import "MTreeMap" as MTreeMap
> m = MTreeMap.create () :: <Proc> MMap.T Integer String
> MMap.put m 10 "ten"
Nothing
> MMap.put m 20 "twenty"
Nothing
> MMap.put m 30 "thirty"
Nothing
> t = MTreeMap.asTreeMap m
> pair entry = (MMap.keyOf entry, MMap.valueOf entry)
> map pair (MTreeMap.floorEntry t 25)
Just (20, "twenty")
> map pair (MTreeMap.ceilingEntry t 25)
Just (30, "thirty")
> map pair (MTreeMap.lowerEntry t 20)
Just (10, "ten")
> map pair (MTreeMap.higherEntry t 20)
Just (30, "thirty")
> map pair (MTreeMap.floorEntry t 5)
Nothing

map is applied over the Maybe, so a missing entry stays Nothing. These four functions pick the same entries as floorKey, ceilingKey, lowerKey and higherKey pick keys.

The greatest key of the map that is less than or equal to the given key.

Example:

> import "MTreeMap" as MTreeMap
> m = MTreeMap.create () :: <Proc> MMap.T Integer String
> MMap.put m 10 "ten"
Nothing
> MMap.put m 20 "twenty"
Nothing
> MMap.put m 30 "thirty"
Nothing
> t = MTreeMap.asTreeMap m
> MTreeMap.floorKey t 20
Just 20
> MTreeMap.ceilingKey t 20
Just 20
> MTreeMap.lowerKey t 20
Just 10
> MTreeMap.higherKey t 20
Just 30
> MTreeMap.floorKey t 25
Just 20
> MTreeMap.floorKey t 5
Nothing

floorKey and ceilingKey accept the given key itself; lowerKey and higherKey exclude it. The given key does not have to be a key of the map, and all four return Nothing when the map has no key on that side.

The entry of the map whose key is the least one strictly greater than the given key. See floorEntry for an example.

The least key of the map that is strictly greater than the given key. See floorKey for an example comparing all four of these functions.

The entry of the map whose key is the greatest one strictly less than the given key. See floorEntry for an example.

The greatest key of the map that is strictly less than the given key. See floorKey for an example comparing all four of these functions.

subMap m from to is a view of the entries of m whose keys are at least from and less than to. The range is half-open: from is included and to is excluded, so subMap m k k is always empty.

The result is a live view, not a copy. Changes to the map show up in the view, and writes through the view go into the map.

Example:

> import "MTreeMap" as MTreeMap
> m = MTreeMap.create () :: <Proc> MMap.T Integer String
> MMap.put m 10 "ten"
Nothing
> MMap.put m 20 "twenty"
Nothing
> MMap.put m 30 "thirty"
Nothing
> t = MTreeMap.asTreeMap m
> MMap.entries (MTreeMap.subMap t 10 30)
[(10, "ten"), (20, "twenty")]
> MMap.entries (MTreeMap.subMap t 20 20)
[]
> MMap.put (MTreeMap.subMap t 10 30) 15 "fifteen"
Nothing
> MMap.entries m
[(10, "ten"), (15, "fifteen"), (20, "twenty"), (30, "thirty")]

The key 30 is absent from the first view because the upper bound is exclusive. The last two commands show the view being written through into the underlying map.