module RegAlloc.Data.IndexedSets (
    IndexedSet,
    indexedSet,
    elements,
    card,
    indexOf,
    elementAt
) where
    import Data.Array
    import Data.Set

    newtype Ord element => IndexedSet element = IndexedSet (Array Int element) deriving (Eq, Ord)

    indexedSet :: Ord element => Set element -> IndexedSet element
    indexedSet set = IndexedSet (listArray (1,cardinality set) (setToList set))

    elements :: Ord element => IndexedSet element -> Set element
    elements (IndexedSet array) = mkSet (elems array)

    card :: Ord element => IndexedSet element -> Int
    card (IndexedSet array) = snd (bounds array)

    indexOf :: Ord element => IndexedSet element -> element -> Int
    indexOf (IndexedSet array) element
        = let
              findIn (lowerBound,upperBound)
                  | lowerBound > upperBound
                      = error "RegAlloc.Data.IndexedSets.index: element not covered"
                  | otherwise
                      = let
                            center = (lowerBound + upperBound) `div` 2
                        in
                        case compare element (array ! center) of
                            LT -> findIn (lowerBound,pred center)
                            EQ -> center
                            GT -> findIn (succ center,upperBound)
          in
          findIn (bounds array)

    elementAt :: Ord element => IndexedSet element -> Int -> element
    elementAt (IndexedSet array) = (array !)