Index.hs

Haskell

Public Domain

Assign contiguous indices to the elements of a list of ordered values

Download (right click, save as, rename as appropriate)

Embed

       

Tags:

binarySearch hashing Haskell index indexing lookupTable mapping 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
-- |Given a finite list of totally ordered values, these functions create a
-- (hopefully efficient) bijection between the values and a contiguous subset
-- of the integers.  This module was inspired by similar code in the
-- implementation of "Data.Graph".
--
-- This module is best imported @qualified@ as the 'lookup' function conflicts
-- with 'Prelude.lookup'.

module Index where
 import Prelude hiding (lookup)
 import Array
 import List (group, sort)

 type Index a = Array Int a

 -- |Creates an 'Index' object from the given list of values.  The resulting
 -- 'Index' may contain fewer elements than the list does if two or more
 -- elements compare equal to each other.
 mkIndex :: Ord a => [a] -> Index a
 mkIndex objs = listArray (0, length dex - 1) dex
  where dex = map head $ group $ sort objs

 -- |Returns the 'Int' assigned to the given value by the 'Index', or 'Nothing'
 -- if the value does not appear in the 'Index'
 lookup :: Ord a => Index a -> a -> Maybe Int
 lookup dex x = binsearch (bounds dex)
  where binsearch (low, high)
	 | low > high = Nothing
	 | otherwise = case compare x (dex ! i) of
	   LT -> binsearch (low, i - 1)
	   EQ -> Just i
	   GT -> binsearch (i + 1, high)
	   where i = (low + high) `div` 2

 -- |Returns the 'Int' assigned to the given value by the 'Index'.  If the
 -- value does not appear in the 'Index', an error results.
 getIndex :: Ord a => Index a -> a -> Int
 getIndex dex x = case lookup dex x of
  Just i  -> i
  Nothing -> error "Nonexistent value passed to Index.getIndex"

 -- |Returns the element in the 'Index' corresponding to the given 'Int'
 unindex :: Index a -> Int -> a
 unindex = (!)