Data.StringMap.Dim2Search

2-dimensional range search of numeric values, e.g. pairs of Ints or Doubles using StringMap and prefix search

Assumption: The coordinates, e.g. Int values are converted into strings of equal length such that the ordering is preserved by the lexikographic ordering.

Example: convert an Int (>= 0) into a String intToString = reverse . take 19 . (++ repeat '0') . reverse . show

Do this for both coordinates of a tuple (x,y)::(Int,Int) and merge the two strings character by character. The resulting string is used as key and stored together with an attribute in a StringMap.

A range search for all keys within a rectangle (p1, p2) = ((x1,y1),(x2,y2)) in a map m can be done by lookupGE p1' . lookupLE p2' $ m with p1' and p2' as the to string converted points of the rectangle.

lookupGE p1' throws away all keys not located in the quadrant with p1 as lower left corner, lookupLE p2' all key not located in the quadrant with p2 as upper right corner. So the combination (lookupRange) computed the intersection of these two quadrants.

Efficiency of these two function is about the same as a normal lookup from StringMap.Base.

This module should be imported qualified, the names in Data.StringMap.Dim2Search are the same as theirs siblings in Data.StringMap:

 import           Data.StringMap (StringMap)
 import qualified Data.StringMap             as M
 import qualified Data.StringMap.Dim2Search  as Dim2

Documentation

lookupGE :: Key -> StringMap a -> StringMap a

remove all entries from the map with key less than the argument key

lookupLE :: Key -> StringMap a -> StringMap a

lookupRange :: Key -> Key -> StringMap a -> StringMap a

Combination of lookupLE and lookupGE

 keys $ lookupRange "a" "b" $ fromList $ zip ["", "a", "ab", "b", "ba", "c"] [1..] = ["a","ab","b"]

For all keys in k = keys $ lookupRange lb ub m, this property holts true: k >= ub && k <= lb