Portability | portable |
---|---|

Stability | experimental |

Maintainer | Uwe Schmidt (uwe@fh-wedel.de) |

Safe Haskell | Safe-Inferred |

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