dense-int-set (empty) → 0.1.5
raw patch · 5 files changed
+439/−0 lines, 5 filesdep +basedep +cerealdep +cereal-vectorsetup-changed
Dependencies added: base, cereal, cereal-vector, deferred-folds, hashable, vector, vector-algorithms
Files
- LICENSE +22/−0
- Setup.hs +2/−0
- dense-int-set.cabal +30/−0
- library/DenseIntSet.hs +275/−0
- library/DenseIntSet/Prelude.hs +110/−0
+ LICENSE view
@@ -0,0 +1,22 @@+Copyright (c) 2018, Metrix.AI++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
+ dense-int-set.cabal view
@@ -0,0 +1,30 @@+name: dense-int-set+version: 0.1.5+category: Data+synopsis: Dense int-set+homepage: https://github.com/metrix-ai/dense-int-set+bug-reports: https://github.com/metrix-ai/dense-int-set/issues+author: Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer: Metrix.AI Tech Team <tech@metrix.ai>+copyright: (c) 2018, Metrix.AI+license: MIT+license-file: LICENSE+build-type: Simple+cabal-version: >=1.10++library+ hs-source-dirs: library+ default-extensions: Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedLists, OverloadedStrings, PatternGuards, PatternSynonyms, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples+ default-language: Haskell2010+ exposed-modules:+ DenseIntSet+ other-modules:+ DenseIntSet.Prelude+ build-depends:+ base >=4.11 && <5,+ cereal >=0.5.5 && <0.6,+ cereal-vector >=0.2.0.1 && <0.3,+ deferred-folds >=0.9.7 && <0.10,+ hashable >=1 && <2,+ vector >=0.12 && <0.13,+ vector-algorithms >=0.7.0.4 && <0.8
+ library/DenseIntSet.hs view
@@ -0,0 +1,275 @@+module DenseIntSet+(+ -- * DenseIntSet+ DenseIntSet,+ -- ** Constructors+ foldable,+ topValueIndices,+ filteredIndices,+ -- *** Composition+ intersection,+ union,+ -- ** Accessors+ size,+ lookup,+ -- *** Vectors+ presentElementsVector,+ filterVector,+ indexVector,+ -- *** Unfoldrs+ presentElementsUnfoldr,+ absentElementsUnfoldr,+ vectorElementsUnfoldr,+ -- * Composition+ DenseIntSetComposition,+ compose,+ composeList,+)+where++import DenseIntSet.Prelude hiding (intersection, union, lookup)+import qualified DeferredFolds.Unfoldr as Unfoldr+import qualified Data.Vector as Vector+import qualified Data.Vector.Unboxed as UnboxedVector+import qualified Data.Vector.Generic as GenericVector+import qualified Data.Vector.Generic.Mutable as MutableGenericVector+import qualified Data.Vector.Algorithms.Intro as IntroVectorAlgorithm+++-- * DenseIntSet+-------------------------++{-|+Set of integer values represented as a space-optimized dense array of booleans,+where an entry only occupies 1 bit.+Compared to IntSet of the \"containers\" library,+it trades off the the ability for modification for much better lookup performance.+Hence it best fits the usage patterns, where you first create the set and then only use it for lookups.++Since there's multiple ways to implement a monoid for this data-structure,+the instances are provided for "DenseIntSetComposition", which+is open for interpretation of how to compose.+-}+newtype DenseIntSet = DenseIntSet (UnboxedVector Word64)++deriving instance Eq DenseIntSet++deriving instance Ord DenseIntSet++instance Show DenseIntSet where + show = show . toList++deriving instance Serialize DenseIntSet++instance Hashable DenseIntSet where+ hashWithSalt salt (DenseIntSet vec) = hashWithSalt salt (GenericVector.toList vec)++instance IsList DenseIntSet where+ type Item DenseIntSet = Int+ fromList list = foldable (foldl' max 0 list) list+ toList = toList . presentElementsUnfoldr+++-- * Constructors+-------------------------++{-|+Given a maximum int, construct from a foldable of ints, which are smaller or equal to it.++It is your responsibility to ensure that the values match this contract.+-}+foldable :: Foldable foldable => Int -> foldable Int -> DenseIntSet+foldable size foldable = let+ !wordsAmount = divCeiling size 64+ in DenseIntSet $ runST $ do+ indexSetMVec <- MutableGenericVector.new wordsAmount+ forM_ foldable $ \ index -> let+ (wordIndex, bitIndex) = divMod index 64+ in MutableGenericVector.modify indexSetMVec (flip setBit bitIndex) wordIndex+ GenericVector.unsafeFreeze indexSetMVec++{-|+Interpret a composition as an intersection of sets.+-}+intersection :: DenseIntSetComposition -> DenseIntSet+intersection = zipWords (.&.) maxBound++{-|+Interpret a composition as a union of sets.+-}+union :: DenseIntSetComposition -> DenseIntSet+union = zipWords (.|.) 0++zipWords :: (Word64 -> Word64 -> Word64) -> Word64 -> DenseIntSetComposition -> DenseIntSet+zipWords append empty (DenseIntSetComposition minLength vecs) = DenseIntSet $ runST $ let+ wordIndexUnfoldr = Unfoldr.intsInRange 0 (pred minLength)+ vecVec = Vector.fromList vecs+ vecUnfoldr = Unfoldr.foldable vecVec+ wordUnfoldrAt wordIndex = fmap (flip GenericVector.unsafeIndex wordIndex) vecUnfoldr+ finalWordAt = foldr append empty . wordUnfoldrAt+ in do+ indexSetMVec <- MutableGenericVector.new minLength+ forM_ wordIndexUnfoldr $ \ index -> MutableGenericVector.unsafeWrite indexSetMVec index (finalWordAt index)+ GenericVector.unsafeFreeze indexSetMVec++{-|+Using the provided ordering function, select the indices of the specified amount of top-ordered elements of a generic vector.+-}+topValueIndices :: (GenericVector.Vector vector a, GenericVector.Vector vector (a, Int)) => (a -> a -> Ordering) -> Int -> vector a -> DenseIntSet+topValueIndices compare amount valueVec = let+ valuesAmount = GenericVector.length valueVec+ limitedAmount = min amount valuesAmount+ wordsAmount = divCeiling valuesAmount 64+ in runST $ do+ pairMVec <- GenericVector.unsafeThaw (GenericVector.imap (\ index count -> (count, index)) valueVec)+ IntroVectorAlgorithm.selectBy (\ a b -> compare (fst b) (fst a)) pairMVec limitedAmount+ indexSetMVec <- MutableGenericVector.new wordsAmount+ forM_ (Unfoldr.intsInRange 0 (pred limitedAmount)) $ \ pairIndex -> do+ (_, index) <- MutableGenericVector.unsafeRead pairMVec pairIndex+ let (wordIndex, bitIndex) = divMod index 64+ MutableGenericVector.modify indexSetMVec (flip setBit bitIndex) wordIndex+ DenseIntSet <$> GenericVector.unsafeFreeze indexSetMVec++{-|+Select the indices of vector elements, which match the predicate.+-}+filteredIndices :: GenericVector.Vector vector a => (a -> Bool) -> vector a -> DenseIntSet+filteredIndices predicate valueVec = DenseIntSet $ let+ valuesAmount = GenericVector.length valueVec+ wordsAmount = divCeiling valuesAmount 64+ indexUnfoldr = do+ (index, a) <- Unfoldr.vectorWithIndices valueVec+ guard (predicate a)+ return (divMod index 64)+ in runST $ do+ indexSetMVec <- MutableGenericVector.new wordsAmount+ forM_ indexUnfoldr $ \ (wordIndex, bitIndex) -> MutableGenericVector.modify indexSetMVec (flip setBit bitIndex) wordIndex+ GenericVector.unsafeFreeze indexSetMVec+++-- * Accessors+-------------------------++{-|+/O(log n)/. Count the amount of present elements in the set.+-}+size :: DenseIntSet -> Int+size (DenseIntSet vec) = getSum (foldMap (Sum . popCount) (Unfoldr.vector vec))++{-|+/O(1)/. Check whether an int is a member of the set.+-}+lookup :: Int -> DenseIntSet -> Bool+lookup index (DenseIntSet vec) = let+ (wordIndex, bitIndex) = divMod index 64+ in vec GenericVector.!? wordIndex & maybe False (flip testBit bitIndex)+++-- ** Vectors+-------------------------++{-|+Extract the present elements into a vector.+-}+presentElementsVector :: GenericVector.Vector vector Int => DenseIntSet -> vector Int+presentElementsVector intSet = let+ sizeVal = size intSet+ unfoldr = Unfoldr.zipWithIndex (presentElementsUnfoldr intSet)+ in runST $ do+ mv <- MutableGenericVector.unsafeNew sizeVal+ forM_ unfoldr $ \ (index, element) -> MutableGenericVector.unsafeWrite mv index element+ GenericVector.unsafeFreeze mv++{-|+Filter a vector, leaving only the entries, under the indices, which are in the set.++It is your responsibility to ensure that the indices in the set don't exceed the original vector's bounds.+-}+filterVector :: GenericVector.Vector vector a => DenseIntSet -> vector a -> vector a+filterVector set vector = let+ !newVectorSize = size set+ in runST $ do+ newVector <- MutableGenericVector.unsafeNew newVectorSize+ forM_ (Unfoldr.zipWithIndex (vectorElementsUnfoldr vector set)) $ \ (newIndex, a) -> do+ MutableGenericVector.unsafeWrite newVector newIndex a+ GenericVector.unsafeFreeze newVector++{-|+Construct a vector, which maps from the original ints into their indices amongst the ones present in the set.+-}+indexVector :: GenericVector.Vector vector (Maybe Int) => DenseIntSet -> vector (Maybe Int)+indexVector set@(DenseIntSet setVec) = let+ indexVecSize = GenericVector.length setVec * 64+ in runST $ do+ v <- MutableGenericVector.replicate indexVecSize Nothing+ forM_ (Unfoldr.zipWithIndex (presentElementsUnfoldr set)) $ \ (index, element) -> do+ MutableGenericVector.unsafeWrite v element (Just index)+ GenericVector.unsafeFreeze v+++-- ** Unfoldr+-------------------------++{-|+Unfold the present elements.+-}+presentElementsUnfoldr :: DenseIntSet -> Unfoldr Int+presentElementsUnfoldr (DenseIntSet vec) = do+ (wordIndex, word) <- Unfoldr.vectorWithIndices vec+ bitIndex <- Unfoldr.setBitIndices word+ return (wordIndex * 64 + bitIndex)++{-|+Unfold the absent elements.+-}+absentElementsUnfoldr :: DenseIntSet -> Unfoldr Int+absentElementsUnfoldr (DenseIntSet vec) = do+ (wordIndex, word) <- Unfoldr.vectorWithIndices vec+ bitIndex <- Unfoldr.unsetBitIndices word+ return (wordIndex * 64 + bitIndex)++{-|+Unfold the elements of a vector by indices in the set.++It is your responsibility to ensure that the indices in the set don't exceed the vector's bounds.+-}+vectorElementsUnfoldr :: (GenericVector.Vector vector a) => vector a -> DenseIntSet -> Unfoldr a+vectorElementsUnfoldr vec = fmap (vec GenericVector.!) . presentElementsUnfoldr+++-- * Composition+-------------------------++{-|+Abstraction over the composition of sets,+which is cheap to append and can be used for interpreted merging of sets.+-}+data DenseIntSetComposition = DenseIntSetComposition !Int [UnboxedVector Word64]++instance Semigroup DenseIntSetComposition where+ (<>) (DenseIntSetComposition leftMinLength leftVecs) =+ if null leftVecs+ then id+ else \ (DenseIntSetComposition rightMinLength rightVecs) -> if null rightVecs+ then DenseIntSetComposition leftMinLength leftVecs+ else DenseIntSetComposition (min leftMinLength rightMinLength) (leftVecs <> rightVecs)++instance Monoid DenseIntSetComposition where+ mempty = DenseIntSetComposition 0 []+ mappend = (<>)++{-|+Lift a set into composition.+-}+compose :: DenseIntSet -> DenseIntSetComposition+compose (DenseIntSet vec) = DenseIntSetComposition (UnboxedVector.length vec) (pure vec)++{-|+Lift a list of sets into composition.+-}+composeList :: [DenseIntSet] -> DenseIntSetComposition+composeList list = if null list+ then mempty+ else let+ unboxedVec = fmap (\ (DenseIntSet x) -> x) list+ in DenseIntSetComposition (foldr1 min (fmap UnboxedVector.length unboxedVec)) unboxedVec
+ library/DenseIntSet/Prelude.hs view
@@ -0,0 +1,110 @@+module DenseIntSet.Prelude+(+ module Exports,+ UnboxedVector,+ bitsInWord,+ divCeiling,+)+where+++-- base+-------------------------+import Control.Applicative as Exports+import Control.Arrow as Exports+import Control.Category as Exports+import Control.Concurrent as Exports+import Control.Exception as Exports+import Control.Monad as Exports hiding (mapM_, sequence_, forM_, msum, mapM, sequence, forM)+import Control.Monad.IO.Class as Exports+import Control.Monad.Fix as Exports hiding (fix)+import Control.Monad.ST as Exports+import Data.Bits as Exports+import Data.Bool as Exports+import Data.Char as Exports+import Data.Coerce as Exports+import Data.Complex as Exports+import Data.Data as Exports+import Data.Dynamic as Exports+import Data.Either as Exports+import Data.Fixed as Exports+import Data.Foldable as Exports hiding (toList)+import Data.Function as Exports hiding (id, (.))+import Data.Functor as Exports+import Data.Functor.Identity as Exports+import Data.Int as Exports+import Data.IORef as Exports+import Data.Ix as Exports+import Data.List as Exports hiding (sortOn, isSubsequenceOf, uncons, concat, foldr, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, find, maximumBy, minimumBy, mapAccumL, mapAccumR, foldl')+import Data.Maybe as Exports+import Data.Monoid as Exports hiding (Last(..), First(..), (<>))+import Data.Ord as Exports+import Data.Proxy as Exports+import Data.Ratio as Exports+import Data.Semigroup as Exports+import Data.STRef as Exports+import Data.String as Exports+import Data.Traversable as Exports+import Data.Tuple as Exports+import Data.Unique as Exports+import Data.Version as Exports+import Data.Word as Exports+import Debug.Trace as Exports+import Foreign.ForeignPtr as Exports+import Foreign.Ptr as Exports+import Foreign.StablePtr as Exports+import Foreign.Storable as Exports hiding (sizeOf, alignment)+import GHC.Conc as Exports hiding (withMVar, threadWaitWriteSTM, threadWaitWrite, threadWaitReadSTM, threadWaitRead)+import GHC.Exts as Exports (lazy, inline, sortWith, groupWith, IsList(..))+import GHC.Generics as Exports (Generic)+import GHC.IO.Exception as Exports+import Numeric as Exports+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, id, (.))+import System.Environment as Exports+import System.Exit as Exports+import System.IO as Exports+import System.IO.Error as Exports+import System.IO.Unsafe as Exports+import System.Mem as Exports+import System.Mem.StableName as Exports+import System.Timeout as Exports+import Text.ParserCombinators.ReadP as Exports (ReadP, ReadS, readP_to_S, readS_to_P)+import Text.ParserCombinators.ReadPrec as Exports (ReadPrec, readPrec_to_P, readP_to_Prec, readPrec_to_S, readS_to_Prec)+import Text.Printf as Exports (printf, hPrintf)+import Text.Read as Exports (Read(..), readMaybe, readEither)+import Unsafe.Coerce as Exports++-- deferred-folds+-------------------------+import DeferredFolds.Unfoldr as Exports (Unfoldr(..))++-- hashable+-------------------------+import Data.Hashable as Exports (Hashable(..))++-- vector+-------------------------+import Data.Vector as Exports (Vector)++-- cereal+-------------------------+import Data.Serialize as Exports (Serialize)++-- cereal-vector+-------------------------+import Data.Vector.Serialize ()++-- +-------------------------+import qualified Data.Vector.Unboxed as UnboxedVector+++type UnboxedVector = UnboxedVector.Vector++{-# NOINLINE bitsInWord #-}+bitsInWord :: Int+bitsInWord = finiteBitSize (0 :: Word)++{-# INLINE divCeiling #-}+divCeiling :: Integral a => a -> a -> a+divCeiling a b = div (a - 1) b + 1