-- $Id: hash.ghc,v 1.3 2001/06/18 18:17:03 doug Exp $
-- http://www.bagley.org/~doug/shootout/
-- from Bryn Keller
-- build with ghc -O2 -package data hash.ghc

import System (getArgs)
import FiniteMap
import Numeric (showInt)

countKeys tbl 0 = 0
countKeys tbl n = case (lookupWithDefaultFM tbl False (show n)) of
                    True -> 1 + countKeys tbl (n - 1)
                    _    -> countKeys tbl (n - 1)

buildTable tbl max num | num <= max = buildTable (addToFM tbl (showHex num "") True) max (num + 1)
                       | otherwise = tbl

showHex n r = let (n',d) = quotRem n 16
                  r'     = toEnum (fromEnum '0' + fromIntegral d) : r
                  in if n' == 0 then r' else showHex n' r'

main = do  args <- getArgs
           case args of
            [number] -> let num = read number
                            tbl = buildTable emptyFM num 1
                    in do putStrLn $ show (countKeys tbl num)
            _        -> fail "You must enter a number."