Functionality to choose random, but unique, numbers.

(Unfortunately, it doesn't appear to be nearly as fast as 
 just checking randoms against a map)

\begin{code}

module RndUniq where

import Random
import Data.Set
-- import Debug.Trace

trace x e = e

-- (Integral a, Random a, RandomGen g) => (a,a) -> g -> Int -> [a]
urandomRs :: RandomGen g => (Int,Int) -> g -> Int -> [Int]
urandomRs (mn,mx) g n = 
    let rs = rnds g (mx-mn+1)
    in trace ("** rs= "++show rs) $ (toList $ foldl (add_kth (mn,mx)) empty $ take n rs)

add_kth :: (Int,Int) -> Set Int -> Int -> Set Int
add_kth range set k = trace ("Adding "++show k++"'th to set "++show (toList set)) $ insert (find_value range k set) set

rnds :: RandomGen g => g -> Int -> [Int]
rnds g mx = if mx == 1 then [1] else 
            let (r,g') = randomR (1,mx) g
            in r : rnds g' (mx-1)


-- find the k'th value *not* in a set
-- (the range is inclusive)
find_value :: (Int,Int) -> Int -> Set Int -> Int
find_value (mn,mx) k set = 
   trace ("**"++show (mn,mx)++" : "++show (toList set)++" : "++show k) $
   if k <= 0 || k > mx-mn+1-(fromIntegral $ size set) then error ("k="++show k++" out of range ("++show mn++","++show mx++"),size="++show (size set))
   else if Data.Set.null set then (mn+k-1)
   else let pivot            = mn+(mx-mn) `div` 2
            (left,piv,right) = splitMember pivot set  -- sizes [mn..pivot-1][pivot][pivot+1..mx]
            empty_left       = pivot - mn - (fromIntegral $ size left)
        in trace ("** pivot: "++show pivot++" empty_left: "++show empty_left) $
          case compare (empty_left+1) k of 
           LT -> if piv then find_value (pivot+1,mx) (k-empty_left) right 
                        else find_value (pivot+1,mx) (k-empty_left-1) right 
           EQ -> if piv then find_value (pivot+1,mx) 1 right
                        else trace ("** Found: "++show pivot++"\n") pivot
           GT -> find_value (mn,pivot-1) k left 
        
\end{code}