packages feed

hashtables-plus (empty) → 0.1.0

raw patch · 6 files changed

+663/−0 lines, 6 filesdep +basedep +hashabledep +hashtablessetup-changed

Dependencies added: base, hashable, hashtables, loch-th, placeholders

Files

+ LICENSE view
@@ -0,0 +1,22 @@+Copyright (c) 2014, Nikita Volkov++Permission is hereby granted, free of charge, to any person+obtaining a copy of this software and associated documentation+files (the "Software"), to deal in the Software without+restriction, including without limitation the rights to use,+copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the+Software is furnished to do so, subject to the following+conditions:++The above copyright notice and this permission notice shall be+included in all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES+OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT+HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,+WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR+OTHER DEALINGS IN THE SOFTWARE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ hashtables-plus.cabal view
@@ -0,0 +1,89 @@+name:+  hashtables-plus+version:+  0.1.0+synopsis:+  Extensions for a "hashtables" library+description:+  Provides advanced data structures built on top of the ones from the +  \"hashtables\" library: multimap, set, "StableName"-based structures.+category:+  Data, Data Structures+homepage:+  https://github.com/nikita-volkov/hashtables-plus +bug-reports:+  https://github.com/nikita-volkov/hashtables-plus/issues +author:+  Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer:+  Nikita Volkov <nikita.y.volkov@mail.ru>+copyright:+  (c) 2014, Nikita Volkov+license:+  MIT+license-file:+  LICENSE+build-type:+  Simple+cabal-version:+  >=1.10+++source-repository head+  type:+    git+  location:+    git://github.com/nikita-volkov/hashtables-plus.git+++library+  hs-source-dirs:+    library+  other-modules:+    HashtablesPlus.Prelude+  exposed-modules:+    HashtablesPlus+    HashtablesPlus.HashRef+  build-depends:+    -- data:+    hashtables == 1.1.*,+    hashable == 1.2.*,+    -- debugging:+    loch-th == 0.2.*,+    placeholders == 0.1.*,+    -- general:+    base >= 4.5 && < 5+  default-extensions:+    Arrows+    BangPatterns+    ConstraintKinds+    DataKinds+    DefaultSignatures+    DeriveDataTypeable+    DeriveGeneric+    EmptyDataDecls+    FlexibleContexts+    FlexibleInstances+    FunctionalDependencies+    GADTs+    GeneralizedNewtypeDeriving+    ImpredicativeTypes+    LambdaCase+    LiberalTypeSynonyms+    MultiParamTypeClasses+    MultiWayIf+    NoImplicitPrelude+    NoMonomorphismRestriction+    OverloadedStrings+    PatternGuards+    QuasiQuotes+    RankNTypes+    RecordWildCards+    ScopedTypeVariables+    StandaloneDeriving+    TemplateHaskell+    TupleSections+    TypeFamilies+    TypeOperators+  default-language:+    Haskell2010
+ library/HashtablesPlus.hs view
@@ -0,0 +1,447 @@+{-# LANGUAGE UndecidableInstances #-}+module HashtablesPlus +(+  -- * Data Structures+  Table,+  Set,+  HashRefSet,+  MultiTable,+  Sized,+  -- * HashTable Implementations+  -- | +  -- These are aliases of implementations of a class 'HashTable',+  -- which provide different performance and memory consumption characteristics.+  -- They are used as parameters to data structures.+  -- For more info refer to the documentation on aliased types.+  Basic,+  Cuckoo,+  Linear,+  -- * Interface+  Key,+  Row,+  UniqueKey,+  MultiKey,+  Value,+  Collection(..),+  Lookup(..),+  LookupMulti(..),+  Elem(..),+  Insert(..),+  Delete(..),+  Size(..),+  Null(..),+  forM_,+  toList,+)+where++import HashtablesPlus.Prelude hiding (elem, toList, null, insert, delete, lookup, foldM, forM_)+import qualified HashtablesPlus.HashRef as HR+import qualified Data.HashTable.IO as T+import qualified Data.HashTable.ST.Basic+import qualified Data.HashTable.ST.Cuckoo+import qualified Data.HashTable.ST.Linear+++-- * Shared Interface+-------------------------++-- | +-- A row of a collection. +-- For tables and multitables it's a key-value pair, +-- for sets it's just the item.+type family Row c+-- | +-- A unique row identifier.+-- For tables it's a key,+-- for multitables it's a key-value pair,+-- for sets it's the item itself.+type family UniqueKey c+-- |+-- A non-unique row identifier.+-- For tables and sets there is none,+-- for multitables it's a key.+type family MultiKey c+-- |+-- An item of a collection.+-- For tables and multitables it's a value (from the key-value pair),+-- for sets it's the item.+type family Value c++class Collection c where+  -- |+  -- Create a new collection.+  new :: IO c+  -- |+  -- Strictly fold over the rows.+  foldM :: c -> r -> (r -> Row c -> IO r) -> IO r++class Collection c => Lookup c where+  -- |+  -- Lookup an item by a unique key.+  lookup :: c -> UniqueKey c -> IO (Maybe (Value c))++class Collection c => LookupMulti c where+  -- |+  -- Lookup multiple items by a non-unique key.+  lookupMulti :: c -> MultiKey c -> IO [Value c]++class Collection c => Elem c where+  -- |+  -- Check whether the collection contains a row by the given unique key.+  elem :: c -> UniqueKey c -> IO Bool+  default elem :: Lookup c => c -> UniqueKey c -> IO Bool+  elem = ((fmap isJust) .) . lookup++class Collection c => Insert c where+  -- | +  -- Insert a row into a collection.+  -- +  -- Returns a boolean signifying whether a new row has been inserted.+  -- Note that if a row has been replaced it returns 'False'.+  insert :: c -> Row c -> IO Bool+  -- |+  -- Same as 'insert', but avoiding the calculation of the operation result.+  insertFast :: c -> Row c -> IO ()+  insertFast = (void .) . insert++class Collection c => Delete c where+  -- |+  -- Delete a row from a collection by its identifier.+  -- +  -- Returns a boolean signifying whether a row has been removed.+  delete :: c -> UniqueKey c -> IO Bool+  -- |+  -- Same as 'delete', but avoiding the calculation of the operation result.+  deleteFast :: c -> UniqueKey c -> IO ()+  deleteFast = (void .) . delete++class Collection c => Size c where+  -- |+  -- /O(1)/.+  -- Get the size of a collection.+  size :: c -> IO Int++class Collection c => Null c where+  -- |+  -- /O(1)/.+  -- Check whether a collection is empty.+  null :: c -> IO Bool+  default null :: (Size c) => c -> IO Bool+  null = fmap (<= 0) . size++-- |+-- Traverse thru all the rows of a collection with side effects.+forM_ :: (Collection c) => c -> (Row c -> IO ()) -> IO ()+forM_ c f = foldM c () (\() r -> f r)++-- |+-- /O(n)/.+-- Convert a collection to a list.+toList :: (Collection c) => c -> IO [Row c]+toList c = foldM c [] (\li ro -> return $ ro : li)++-- |+-- A constraint for values usable as hash table key.+type Key k = (Hashable k, Eq k)++++-- * 'HashTable' Implementations+-------------------------++type Basic = Data.HashTable.ST.Basic.HashTable+type Cuckoo = Data.HashTable.ST.Cuckoo.HashTable+type Linear = Data.HashTable.ST.Linear.HashTable++++-- * HashTable+-------------------------++-- | +-- A newtype wrapper over a 'HashTable' implementation @t@.+-- +-- E.g.:+-- +-- @+-- type CuckooTable k v = 'Table' 'Cuckoo' k v+-- @+newtype Table t k v = Table (T.IOHashTable t k v)++type instance Row (Table t k v) = (k, v)+type instance UniqueKey (Table t k v) = k+type instance Value (Table t k v) = v++instance (HashTable t, Key k) => Collection (Table t k v) where+  new = Table <$> T.new+  foldM (Table t) z f = T.foldM f z t++instance (HashTable t, Key k) => Lookup (Table t k v) where+  lookup (Table t) = T.lookup t++instance (HashTable t, Key k) => Elem (Table t k v)++instance (HashTable t, Key k) => Insert (Table t k v) where+  insert (Table t) (k, v) = do+    T.lookup t k >>= \case+      Just v' -> return False +      Nothing -> T.insert t k v >> return True+  insertFast (Table t) (k, v) = T.insert t k v++instance (HashTable t, Key k) => Delete (Table t k v) where+  delete (Table t) k = do+    T.lookup t k >>= \case+      Just v' -> return False +      Nothing -> T.delete t k >> return True+  deleteFast (Table t) k = T.delete t k++++-- * Sets+-------------------------++-- ** Set+-------------------------++-- | +-- A set of values, +-- which have instances for 'Eq' and 'Hashable'.+-- +-- @t@ is the underlying 'HashTable' implementation, +-- @a@ is the item.+-- +-- E.g.:+-- +-- @+-- type CuckooSet a = 'Set' 'Cuckoo' a+-- @+newtype Set t a = Set (T.IOHashTable t a ())++type instance Row (Set t a) = a+type instance UniqueKey (Set t a) = a+type instance Value (Set t a) = a++instance (HashTable t, Key a) => Collection (Set t a) where+  new = Set <$> T.new+  foldM (Set table) z f = T.foldM f' z table where +    f' z (a, _) = f z a++instance (HashTable t, Key a) => Elem (Set t a) where+  elem (Set table) a = T.lookup table a >>= return . isJust++instance (HashTable t, Key a) => Insert (Set t a) where+  insert (Set table) a = do+    T.lookup table a >>= \case+      Just _ -> return False+      Nothing -> do+        T.insert table a ()+        return True+  insertFast (Set table) a = T.insert table a ()++instance (HashTable t, Key a) => Delete (Set t a) where+  delete (Set table) a = do+    T.lookup table a >>= \case+      Just _ -> do+        T.delete table a+        return True+      Nothing -> return False+  deleteFast (Set table) a = T.delete table a++-- ** HashRefSet+-------------------------++-- | +-- A specialized set of 'HR.HashRef's.+-- +-- @t@ is the underlying 'HashTable' implementation, +-- @a@ is the item.+-- +-- E.g.:+-- +-- @+-- type LinearHashRefSet a = 'HashRefSet' 'Linear' a+-- @+newtype HashRefSet t a = HashRefSet (T.IOHashTable t (StableName a) a)++type instance Row (HashRefSet t a) = HR.HashRef a+type instance UniqueKey (HashRefSet t a) = HR.HashRef a+type instance Value (HashRefSet t a) = HR.HashRef a++instance (HashTable t) => Collection (HashRefSet t a) where+  new = HashRefSet <$> T.new+  foldM (HashRefSet table) z f = T.foldM f' z table where +    f' z (sn, a) = f z (HR.HashRef sn a)++instance (HashTable t) => Elem (HashRefSet t a) where+  elem (HashRefSet table) (HR.HashRef sn a) = T.lookup table sn >>= return . isJust++instance (HashTable t) => Insert (HashRefSet t a) where+  insert (HashRefSet table) (HR.HashRef sn a) = do+    T.lookup table sn >>= \case+      Just _ -> return False+      Nothing -> do+        T.insert table sn a+        return True+  insertFast (HashRefSet table) (HR.HashRef sn a) = T.insert table sn a++instance (HashTable t) => Delete (HashRefSet t a) where+  delete (HashRefSet table) (HR.HashRef sn a) = do+    T.lookup table sn >>= \case+      Just _ -> do+        T.delete table sn+        return True+      Nothing -> return False+  deleteFast (HashRefSet table) (HR.HashRef sn a) = T.delete table sn++++-- * Sized+-------------------------++-- |+-- A wrapper over a 'Collection',+-- which adds 'null' and 'size' functions of /O(1)/ complexity.+-- +-- E.g.:+-- +-- @+-- type SizedLinearTable k v = 'Sized' ('Table' 'Linear' k v)+-- @+data Sized c = Sized !c {-# UNPACK #-} !(IORef Int)++type instance Row (Sized c) = Row c+type instance UniqueKey (Sized c) = UniqueKey c+type instance MultiKey (Sized c) = MultiKey c+type instance Value (Sized c) = Value c++instance (Collection c) => Collection (Sized c) where+  new = Sized <$> new <*> newIORef 0+  foldM (Sized c _) = foldM c++instance (Lookup c) => Lookup (Sized c) where+  lookup (Sized c _) a = lookup c a++instance (LookupMulti c) => LookupMulti (Sized c) where+  lookupMulti (Sized c _) k = lookupMulti c k++instance (Elem c) => Elem (Sized c) where+  elem (Sized c _) a = elem c a++instance (Insert c) => Insert (Sized c) where+  insert (Sized c size) a = do+    ok <- insert c a  +    when ok $ modifyIORef size succ+    return ok++instance (Delete c) => Delete (Sized c) where+  delete (Sized c size) a = do+    ok <- delete c a+    when ok $ modifyIORef size pred+    return ok++instance (Collection c) => Size (Sized c) where+  size (Sized _ s) = readIORef s++instance (Collection c) => Null (Sized c)++++-- * MultiTable+-------------------------++-- |+-- A multitable (or multimap) with underlying 'HashTable' @t@, key @k@ and +-- a set implementation @s@.+-- +-- E.g.:+-- +-- @+-- type BasicMultiTable k v = 'MultiTable' 'Basic' k ('Set' 'Basic' v)+-- @+-- +-- If a 'Sized' implementation of set is specified, +-- a more space efficient instance of 'Delete' will be used. E.g.:+-- +-- @+-- MultiTable Basic k ('Sized' (Set Basic v))+-- @+newtype MultiTable t k s = MultiTable (T.IOHashTable t k s)++type instance Row (MultiTable t k s) = (k, Row s)+type instance UniqueKey (MultiTable t k s) = (k, UniqueKey s)+type instance MultiKey (MultiTable t k s) = k+type instance Value (MultiTable t k s) = Value s++instance (HashTable t, Key k, Collection s) => +         Collection (MultiTable t k s) where+  new = MultiTable <$> T.new+  foldM (MultiTable t) z f = T.foldM f' z t where+    f' z (k, s) = foldM s z f'' where+      f'' z v = f z (k, v)++instance (HashTable t, Key k, Collection s, Value s ~ Row s) => +         LookupMulti (MultiTable t k s) where+  lookupMulti (MultiTable t) k = do+    T.lookup t k >>= \case+      Nothing -> return []+      Just s -> toList s++instance (HashTable t, Key k, Elem s) => +         Elem (MultiTable t k s) where+  elem (MultiTable t) (k, v) = do+    T.lookup t k >>= \case+      Nothing -> return False+      Just s -> elem s v++instance (HashTable t, Key k, Insert s) => +         Insert (MultiTable t k s) where+  insert (MultiTable t) (k, v) = do+    T.lookup t k >>= \case+      Nothing -> do+        s <- new+        insertFast s v+        T.insert t k s+        return True+      Just s -> do+        insert s v+  insertFast (MultiTable t) (k, v) = do+    T.lookup t k >>= \case+      Nothing -> do+        s <- new+        insertFast s v+        T.insert t k s+      Just s -> do+        insertFast s v++instance (HashTable t, Key k, Delete c) => Delete (MultiTable t k c) where+  delete (MultiTable t) (k, v) = do+    T.lookup t k >>= \case+      Nothing -> return False+      Just s -> delete s v+  deleteFast (MultiTable t) (k, v) = do+    T.lookup t k >>= \case+      Nothing -> return ()+      Just s -> deleteFast s v+      +instance (HashTable t, Key k, Delete c) => Delete (MultiTable t k (Sized c)) where+  delete (MultiTable t) (k, v) = do+    T.lookup t k >>= \case+      Nothing -> return False+      Just s -> do+        delete s v >>= \case+          False -> return False+          True -> do+            null s >>= \case+              False -> return ()+              True -> T.delete t k+            return True+  deleteFast (MultiTable t) (k, v) = do+    T.lookup t k >>= \case+      Nothing -> return ()+      Just s -> do+        deleteFast s v+        null s >>= \case+          False -> return ()+          True -> T.delete t k+
+ library/HashtablesPlus/HashRef.hs view
@@ -0,0 +1,35 @@+module HashtablesPlus.HashRef where++import HashtablesPlus.Prelude+++-- | +-- A reference to a mutable value, +-- which provides instances for 'Hashable' and 'Eq'.+-- +-- It allows to use the values without those instances as keys in hash tables.+data HashRef a = HashRef {-# UNPACK #-} !(StableName a) !a++-- |+-- Create a new reference.+-- +-- Two references created from the same value are not guaranteed to be equal or+-- produce the same hash. +-- However the references created from different values are guaranteed+-- to be different.+new :: a -> IO (HashRef a)+new a = do+  sn <- makeStableName a+  return $ HashRef sn a++-- |+-- Extract the value from this reference.+value :: HashRef a -> a+value (HashRef _ a) = a++instance Hashable (HashRef a) where+  hashWithSalt s (HashRef sn _) = hashWithSalt s sn+  hash (HashRef sn _) = hash sn++instance Eq (HashRef a) where+  HashRef a _ == HashRef b _ = a == b
+ library/HashtablesPlus/Prelude.hs view
@@ -0,0 +1,68 @@+module HashtablesPlus.Prelude+( +  module Exports,++  traceM,+  bug,+  bottom,+)+where++-- base+import Prelude as Exports hiding (concat, foldr, mapM_, sequence_, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, mapM, sequence, FilePath, id, (.))+import Control.Monad as Exports hiding (mapM_, sequence_, forM_, msum, mapM, sequence, forM)+import Control.Applicative as Exports+import Control.Arrow as Exports hiding (left, right)+import Control.Category as Exports+import Data.Monoid as Exports+import Data.Foldable as Exports+import Data.Traversable as Exports hiding (for)+import Data.Maybe as Exports+import Data.Either as Exports+import Data.List as Exports hiding (concat, foldr, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, find, maximumBy, minimumBy, mapAccumL, mapAccumR, foldl')+import Data.Tuple as Exports+import Data.Ord as Exports (Down(..))+import Data.String as Exports+import Data.Int as Exports+import Data.Word as Exports+import Data.Ratio as Exports+import Data.Fixed as Exports+import Data.Ix as Exports+import Data.Data as Exports+import Text.Read as Exports (readMaybe, readEither)+import Control.Exception as Exports hiding (tryJust, try, assert)+import Control.Concurrent as Exports hiding (yield)+import System.Mem.StableName as Exports+import System.Timeout as Exports+import System.Exit as Exports+import System.IO.Unsafe as Exports+import System.IO as Exports (Handle, hClose)+import System.IO.Error as Exports+import Unsafe.Coerce as Exports+import GHC.Exts as Exports hiding (Any, traceEvent)+import GHC.Generics as Exports (Generic)+import GHC.IO.Exception as Exports+import Data.IORef as Exports+import Data.STRef as Exports+import Control.Monad.ST as Exports+import Debug.Trace as Exports++-- placeholders+import Development.Placeholders as Exports++-- hashable+import Data.Hashable as Exports (Hashable(..), hash, hashWithSalt)++-- hashtables+import Data.HashTable.Class as Exports (HashTable)+++import qualified Debug.Trace.LocationTH++traceM :: (Monad m) => String -> m ()+traceM s = trace s $ return ()++bug = [e| $(Debug.Trace.LocationTH.failure) . (msg <>) |] where+  msg = "A \"hashtables-plus\" package bug: " :: String++bottom = [e| $bug "Bottom evaluated" |]