Data.Columbia.Dictionaries

Documentation

• * Conversions to and from LazyMaps

lazyMapToMap :: LazyMap k v -> Map k v

It forces a lazy dictionary into a dictionary. This takes O(n) time as opposed to the O(n log n) that it would take to build the Map via its interface. It is still very wrong and this conversion should only be used as a step in reading dictionaries from a stream representation.

mapToLazyMap :: Map k v -> LazyMap k v

• * Rudimentary manipulation operations

lazyMapToAscList :: LazyMap k v -> [(k, v)]

lazyMapSize :: LazyMap k v -> Int

lazyMapRange :: Ord k => k -> k -> WithAddress (LazyMap k v) -> WithAddress (LazyMap k v)

lazyMapRange is for computing a specific range in a LazyMap -- no balancing is done.

lazyMapOpenRange :: Ord k => k -> k -> WithAddress (LazyMap k v) -> WithAddress (LazyMap k v)

lazyMapMinKey :: LazyMap k v -> Maybe k

These find the minimum and maximum keys resp. of LazyMaps provided the keys are ordered.

lazyMapMaxKey :: LazyMap k v -> Maybe k

lazyMapMerge :: WithAddress (LazyMap k v) -> WithAddress (LazyMap k v) -> WithAddress (LazyMap k v)

It merges two LazyMaps in O(n) time, provided the lazyMapMaxKey lm <= lazyMapMinKey lm2. No attempt is made to balance the resulting tree structure.

• * Seeking to and reading a sub-range

seekInRange :: forall ctx k v m. (Ord k, Data ctx k, Data ctx v, Sat (ctx Int), Sat (ctx (LazyMap k v)), Sat (ctx Word32), Sat (ctx (WithAddress (LazyMap k v))), HasField ctx RWCtx, Monad m) => k -> k -> PolyTraversal ctx m (WithAddress (LazyMap k v))

seekInRange is a seeking operation. It is applicable to LazyMaps in a stream representation; it requires a stream to be seeked at a LazyMap. Its function is to locate the entries of a dictionary that are bounded above and below by certain key values. The key values located are partitioned into subtrees, in such a way as to maximize the number of subtrees that can be directly referenced in the file (and minimize the number of new nodes constructed to structure the resulting tree).