|Maintainer||Uwe Schmidt (firstname.lastname@example.org)|
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
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
p2' as the to string converted points of the rectangle.
lookupGE p1' throws away all keys not located in the quadrant with
as lower left corner,
lookupLE p2' all key not located in the quadrant
p2 as upper right corner. So the combination (
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
remove all entries from the map with key less than the argument key