Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.SplayMap

Contents

Splay
Internal update

Description

A mutable splay tree-based map.

Invariants

Splay tree is a self-adjusting tree that follows the splaying operation heuristic.

http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

Invariants

Left children have keys smaller keys than the parent. Right children have bigger keys than the parent.

Thanks

Synopsis

type SplayIndex = Int
undefSI :: SplayIndex
nullSI :: SplayIndex -> Bool
data SplayNode k v = SplayNode {
- lSN :: !SplayIndex
- rSN :: !SplayIndex
- keySN :: !k
- valSN :: !v
}
type SplayNodeRepr k v = (SplayIndex, SplayIndex, k, v)
data SplayMap k v s = SplayMap {
- capacitySM :: !Int
- rootSM :: !(MVector s SplayIndex)
- dataSM :: !(Buffer s (SplayNode k v))
}
newSM :: (Unbox k, Unbox v, PrimMonad m) => Int -> m (SplayMap k v (PrimState m))
buildSM :: (Ord k, Unbox k, Unbox v, PrimMonad m) => Int -> Vector (k, v) -> m (SplayMap k v (PrimState m))
clearSM :: PrimMonad m => SplayMap k v (PrimState m) -> m ()
lengthSM :: PrimMonad m => SplayMap k v (PrimState m) -> m Int
lookupSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v))
insertSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> v -> m (Maybe v)
insertSM_ :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> v -> m ()
deleteSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (SplayNode k v))
deleteSM_ :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m ()
memberSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m Bool
_readLMostSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex
_readRMostSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex
_lookupWithSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> (k -> Ordering) -> Bool -> m (Maybe (k, v))
lookupLESM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v))
lookupLTSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v))
lookupGESM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v))
lookupGTSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v))
dfsSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> m (Vector (k, v))
rotateRSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex
rotateLSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex
splayBySM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> (k -> Ordering) -> SplayIndex -> m (SplayIndex, Ordering)
splayLMostSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex
splayRMostSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex
pushRootSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> SplayNode k v -> m ()
popRootSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> m (SplayNode k v)
writeLSM :: (HasCallStack, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> SplayIndex -> m ()
writeRSM :: (HasCallStack, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> SplayIndex -> m ()
writeKSM :: (HasCallStack, Unbox k, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> k -> m ()
writeVSM :: (HasCallStack, Unbox v, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> v -> m ()
readLSM :: (HasCallStack, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> m SplayIndex
readRSM :: (HasCallStack, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> m SplayIndex
readKSM :: (HasCallStack, Unbox k, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> m k
readVSM :: (HasCallStack, Unbox v, PrimMonad m) => Buffer (PrimState m) (SplayNode k v) -> SplayIndex -> m v

Documentation

type SplayIndex = Int #

Index of a SplayNode stored in a SplayMap.

undefSI :: SplayIndex #

nullSI :: SplayIndex -> Bool #

data SplayNode k v #

Splay tree node.

Constructors

SplayNode
Fields lSN :: !SplayIndex rSN :: !SplayIndex keySN :: !k valSN :: !v

Instances

Instances details

(Unbox k, Unbox v) => Vector Vector (SplayNode k v) #
Instance details Defined in Data.SplayMap Methods basicUnsafeFreeze :: Mutable Vector s (SplayNode k v) -> ST s (Vector (SplayNode k v)) # basicUnsafeThaw :: Vector (SplayNode k v) -> ST s (Mutable Vector s (SplayNode k v)) # basicLength :: Vector (SplayNode k v) -> Int # basicUnsafeSlice :: Int -> Int -> Vector (SplayNode k v) -> Vector (SplayNode k v) # basicUnsafeIndexM :: Vector (SplayNode k v) -> Int -> Box (SplayNode k v) # basicUnsafeCopy :: Mutable Vector s (SplayNode k v) -> Vector (SplayNode k v) -> ST s () # elemseq :: Vector (SplayNode k v) -> SplayNode k v -> b -> b #
(Unbox k, Unbox v) => MVector MVector (SplayNode k v) #
Instance details Defined in Data.SplayMap Methods basicLength :: MVector s (SplayNode k v) -> Int # basicUnsafeSlice :: Int -> Int -> MVector s (SplayNode k v) -> MVector s (SplayNode k v) # basicOverlaps :: MVector s (SplayNode k v) -> MVector s (SplayNode k v) -> Bool # basicUnsafeNew :: Int -> ST s (MVector s (SplayNode k v)) # basicInitialize :: MVector s (SplayNode k v) -> ST s () # basicUnsafeReplicate :: Int -> SplayNode k v -> ST s (MVector s (SplayNode k v)) # basicUnsafeRead :: MVector s (SplayNode k v) -> Int -> ST s (SplayNode k v) # basicUnsafeWrite :: MVector s (SplayNode k v) -> Int -> SplayNode k v -> ST s () # basicClear :: MVector s (SplayNode k v) -> ST s () # basicSet :: MVector s (SplayNode k v) -> SplayNode k v -> ST s () # basicUnsafeCopy :: MVector s (SplayNode k v) -> MVector s (SplayNode k v) -> ST s () # basicUnsafeMove :: MVector s (SplayNode k v) -> MVector s (SplayNode k v) -> ST s () # basicUnsafeGrow :: MVector s (SplayNode k v) -> Int -> ST s (MVector s (SplayNode k v)) #
(Show k, Show v) => Show (SplayNode k v) #
Instance details Defined in Data.SplayMap Methods showsPrec :: Int -> SplayNode k v -> ShowS # show :: SplayNode k v -> String # showList :: [SplayNode k v] -> ShowS #
(Eq k, Eq v) => Eq (SplayNode k v) #
Instance details Defined in Data.SplayMap Methods (==) :: SplayNode k v -> SplayNode k v -> Bool # (/=) :: SplayNode k v -> SplayNode k v -> Bool #
(Unbox k, Unbox v) => Unbox (SplayNode k v) #
Instance details Defined in Data.SplayMap
IsoUnbox (SplayNode k v) (SplayNodeRepr k v) #
Instance details Defined in Data.SplayMap Methods toURepr :: SplayNode k v -> SplayNodeRepr k v # fromURepr :: SplayNodeRepr k v -> SplayNode k v #
newtype MVector s (SplayNode k v) #
Instance details Defined in Data.SplayMap newtype MVector s (SplayNode k v) = MV_SplayNode (MVector s (SplayNodeRepr k v))
newtype Vector (SplayNode k v) #
Instance details Defined in Data.SplayMap newtype Vector (SplayNode k v) = V_SplayNode (Vector (SplayNodeRepr k v))

type SplayNodeRepr k v = (SplayIndex, SplayIndex, k, v) #

Internal representation of `SplayNode a` for implementing Unbox.

data SplayMap k v s #

Mutable, splay tree-based map.

Constructors

SplayMap
Fields capacitySM :: !Int The maximum number of elements. rootSM :: !(MVector s SplayIndex) Index of the root node. dataSM :: !(Buffer s (SplayNode k v)) Data storage.

newSM :: (Unbox k, Unbox v, PrimMonad m) => Int -> m (SplayMap k v (PrimState m)) #

\(O(N)\) Creates a new SplayMap of capacity n.

buildSM :: (Ord k, Unbox k, Unbox v, PrimMonad m) => Int -> Vector (k, v) -> m (SplayMap k v (PrimState m)) #

\(O(N)\) Creates a new SplayMap of capacity n with initial values xs.

TODO: faster implementation?

clearSM :: PrimMonad m => SplayMap k v (PrimState m) -> m () #

\(O(1)\) Resets the splay tree to the initial state.

lengthSM :: PrimMonad m => SplayMap k v (PrimState m) -> m Int #

lookupSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v)) #

Amortized \(O(\log N)\).

insertSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> v -> m (Maybe v) #

Amortized \(O(\log N)\). Returns old value with the same key if there is.

TODO: consider making a multiset with splay tree?

insertSM_ :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> v -> m () #

deleteSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (SplayNode k v)) #

Amortized \(O(\log N)\).

deleteSM_ :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m () #

memberSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m Bool #

_readLMostSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex #

Reads the left most child without splaying.

_readRMostSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex #

Reads the right most child without splaying.

_lookupWithSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> (k -> Ordering) -> Bool -> m (Maybe (k, v)) #

Amortized \(O(\log N)\). Internal use only.

lookupLESM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v)) #

Amortized \(O(\log N)\).

lookupLTSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v)) #

Amortized \(O(\log N)\).

lookupGESM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v)) #

Amortized \(O(\log N)\).

lookupGTSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> k -> m (Maybe (k, v)) #

Amortized \(O(\log N)\).

dfsSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> m (Vector (k, v)) #

Returns (key, value) pairs sorted by the keys in ascending order.

Splay

rotateRSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex #

\(O(1)\) Left child rotation.

Visualization

Move up l, move i to the right node of l, set lr as the left node of i.

     i*           l        * .. the side of the child is updated
                
   l*  r  -->  ll   i
                  
ll   lr           lr  r

Returns l.

rotateLSM :: (HasCallStack, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex #

\(O(1)\) Right child rotation.

Visualization

Move up r, move i to the left node of r, set rl as the right node of i.

  i*             r           * .. the side of the child is updated
               
l   r*   -->   i   rr
             
  rl  rr     l   rl

Returns r.

splayBySM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> (k -> Ordering) -> SplayIndex -> m (SplayIndex, Ordering) #

Amortized \(O(\log N)\) Splay v so that it is under r (or to the root if s is null).

Top-down splaying

The are two known approaches for the splaying operation: bottom-up and top-down. The former is easier to understand but less efficient. The latter is faster and uses less memory.

splayLMostSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex #

splayRMostSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> SplayIndex -> m SplayIndex #

pushRootSM :: (HasCallStack, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> SplayNode k v -> m () #

Amortized \(O(\log N)\).

popRootSM :: (HasCallStack, Ord k, Unbox k, Unbox v, PrimMonad m) => SplayMap k v (PrimState m) -> m (SplayNode k v) #

Amortized \(O(\log N)\). Removes the current root.

TODO: Less splaying