bitset 1.0 → 1.1
raw patch · 5 files changed
+85/−181 lines, 5 filesdep ~QuickCheckdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: QuickCheck, base
API changes (from Hackage documentation)
+ Data.BitSet: toIntegral :: Integral b => BitSet a -> b
+ Data.BitSet: unsafeFromIntegral :: Integral b => b -> BitSet a
Files
- CHANGES +11/−0
- Data/BitSet.hs +19/−0
- LICENSE +25/−160
- bitset.cabal +10/−9
- tests/Properties.hs +20/−12
+ CHANGES view
@@ -0,0 +1,11 @@+-*- mode: outline -*-++* 1.1+Added conversion to and from the underlying Integral value (thanks to Mathieu+Boespflug).++* 1.0+Instead of a custom Hash typeclass, we now use Enum. It's standard and it gives+us exactly what we need, so it's a win-win.++Also, use unboxed tuples to represent the bitset.
Data/BitSet.hs view
@@ -23,6 +23,8 @@ , delete , member , size+ , toIntegral+ , unsafeFromIntegral ) where import Prelude hiding ( null )@@ -61,7 +63,15 @@ -- | /O(1)/ The number of elements in the bit set. size :: BitSet a -> Int +-- | /O(1)/ Project a bit set to an integer.+toIntegral :: Integral b => BitSet a -> b +-- | /O(n)/ Make a bit set of type @BitSet a@ from an integer. This is unsafe+-- because it is not checked whether the bits set in the integer correspond to+-- values of type @a@. This is only useful as a more efficient alternative to+-- fromList.+unsafeFromIntegral :: Integral b => b -> BitSet a+ -- * Implementation {-# INLINE empty #-}@@ -87,3 +97,12 @@ {-# INLINE size #-} size (BS count _) = count++{-# INLINE toIntegral #-}+toIntegral (BS _ i) = fromIntegral i++{-# INLINE unsafeFromIntegral #-}+unsafeFromIntegral x = let i = fromIntegral x in BS (count i) i+ where count 0 = 0+ count z | z `mod` 2 == 0 = 1 + count (shiftR z 1)+ | otherwise = count (shiftR z 1)
LICENSE view
@@ -1,165 +1,30 @@- GNU LESSER GENERAL PUBLIC LICENSE- Version 3, 29 June 2007-- Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>- Everyone is permitted to copy and distribute verbatim copies- of this license document, but changing it is not allowed.--- This version of the GNU Lesser General Public License incorporates-the terms and conditions of version 3 of the GNU General Public-License, supplemented by the additional permissions listed below.-- 0. Additional Definitions. -- As used herein, "this License" refers to version 3 of the GNU Lesser-General Public License, and the "GNU GPL" refers to version 3 of the GNU-General Public License.-- "The Library" refers to a covered work governed by this License,-other than an Application or a Combined Work as defined below.-- An "Application" is any work that makes use of an interface provided-by the Library, but which is not otherwise based on the Library.-Defining a subclass of a class defined by the Library is deemed a mode-of using an interface provided by the Library.-- A "Combined Work" is a work produced by combining or linking an-Application with the Library. The particular version of the Library-with which the Combined Work was made is also called the "Linked-Version".-- The "Minimal Corresponding Source" for a Combined Work means the-Corresponding Source for the Combined Work, excluding any source code-for portions of the Combined Work that, considered in isolation, are-based on the Application, and not on the Linked Version.-- The "Corresponding Application Code" for a Combined Work means the-object code and/or source code for the Application, including any data-and utility programs needed for reproducing the Combined Work from the-Application, but excluding the System Libraries of the Combined Work.-- 1. Exception to Section 3 of the GNU GPL.-- You may convey a covered work under sections 3 and 4 of this License-without being bound by section 3 of the GNU GPL.-- 2. Conveying Modified Versions.-- If you modify a copy of the Library, and, in your modifications, a-facility refers to a function or data to be supplied by an Application-that uses the facility (other than as an argument passed when the-facility is invoked), then you may convey a copy of the modified-version:-- a) under this License, provided that you make a good faith effort to- ensure that, in the event an Application does not supply the- function or data, the facility still operates, and performs- whatever part of its purpose remains meaningful, or-- b) under the GNU GPL, with none of the additional permissions of- this License applicable to that copy.-- 3. Object Code Incorporating Material from Library Header Files.-- The object code form of an Application may incorporate material from-a header file that is part of the Library. You may convey such object-code under terms of your choice, provided that, if the incorporated-material is not limited to numerical parameters, data structure-layouts and accessors, or small macros, inline functions and templates-(ten or fewer lines in length), you do both of the following:-- a) Give prominent notice with each copy of the object code that the- Library is used in it and that the Library and its use are- covered by this License.-- b) Accompany the object code with a copy of the GNU GPL and this license- document.-- 4. Combined Works.-- You may convey a Combined Work under terms of your choice that,-taken together, effectively do not restrict modification of the-portions of the Library contained in the Combined Work and reverse-engineering for debugging such modifications, if you also do each of-the following:-- a) Give prominent notice with each copy of the Combined Work that- the Library is used in it and that the Library and its use are- covered by this License.-- b) Accompany the Combined Work with a copy of the GNU GPL and this license- document.-- c) For a Combined Work that displays copyright notices during- execution, include the copyright notice for the Library among- these notices, as well as a reference directing the user to the- copies of the GNU GPL and this license document.-- d) Do one of the following:-- 0) Convey the Minimal Corresponding Source under the terms of this- License, and the Corresponding Application Code in a form- suitable for, and under terms that permit, the user to- recombine or relink the Application with a modified version of- the Linked Version to produce a modified Combined Work, in the- manner specified by section 6 of the GNU GPL for conveying- Corresponding Source.-- 1) Use a suitable shared library mechanism for linking with the- Library. A suitable mechanism is one that (a) uses at run time- a copy of the Library already present on the user's computer- system, and (b) will operate properly with a modified version- of the Library that is interface-compatible with the Linked- Version. -- e) Provide Installation Information, but only if you would otherwise- be required to provide such information under section 6 of the- GNU GPL, and only to the extent that such information is- necessary to install and execute a modified version of the- Combined Work produced by recombining or relinking the- Application with a modified version of the Linked Version. (If- you use option 4d0, the Installation Information must accompany- the Minimal Corresponding Source and Corresponding Application- Code. If you use option 4d1, you must provide the Installation- Information in the manner specified by section 6 of the GNU GPL- for conveying Corresponding Source.)-- 5. Combined Libraries.-- You may place library facilities that are a work based on the-Library side by side in a single library together with other library-facilities that are not Applications and are not covered by this-License, and convey such a combined library under terms of your-choice, if you do both of the following:-- a) Accompany the combined library with a copy of the same work based- on the Library, uncombined with any other library facilities,- conveyed under the terms of this License.+Copyright (c) 2009 Denis Bueno+All rights reserved. - b) Give prominent notice with the combined library that part of it- is a work based on the Library, and explaining where to find the- accompanying uncombined form of the same work.+Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are+met: - 6. Revised Versions of the GNU Lesser General Public License.+ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer. - The Free Software Foundation may publish revised and/or new versions-of the GNU Lesser General Public License from time to time. Such new-versions will be similar in spirit to the present version, but may-differ in detail to address new problems or concerns.+ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution. - Each version is given a distinguishing version number. If the-Library as you received it specifies that a certain numbered version-of the GNU Lesser General Public License "or any later version"-applies to it, you have the option of following the terms and-conditions either of that published version or of any later version-published by the Free Software Foundation. If the Library as you-received it does not specify a version number of the GNU Lesser-General Public License, you may choose any version of the GNU Lesser-General Public License ever published by the Free Software Foundation.+ * Neither the name of Denis Bueno nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission. - If the Library as you received it specifies that a proxy can decide-whether future versions of the GNU Lesser General Public License shall-apply, that proxy's public statement of acceptance of any version is-permanent authorization for you to choose that version for the-Library.+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
bitset.cabal view
@@ -1,23 +1,24 @@ Name: bitset-Version: 1.0+Version: 1.1 Synopsis: A functional data structure for efficient membership testing. Description: A /bit set/ maintains a record of members from a type that can be mapped into (non-negative) @Int@s. Supports insertion, deletion, size, and membership testing, and is completely pure (functional). Category: Data Structures-License: LGPL+License: BSD3 License-file: LICENSE+Data-files: CHANGES Author: Denis Bueno Maintainer: Denis Bueno <dbueno@gmail.com> Stability: provisional Cabal-Version: >= 1.2.3-Build-Depends: base, QuickCheck Build-type: Simple--Exposed-modules: Data.BitSet-Build-depends: base >= 4.0.0-Extensions: ScopedTypeVariables, DeriveDataTypeable-Ghc-options: -Wall -O2-Ghc-prof-options: -prof -auto-all Extra-source-files: tests/Properties.hs++Library+ Exposed-modules: Data.BitSet+ Build-depends: base >= 4.0.0 && < 5, QuickCheck >= 2 && < 3+ Extensions: ScopedTypeVariables, DeriveDataTypeable+ Ghc-options: -Wall -O2+ Ghc-prof-options: -prof -auto-all
tests/Properties.hs view
@@ -14,24 +14,27 @@ main :: IO () main = do- dbgMsg "prop_size: " >> check config prop_size- dbgMsg "prop_size_insert: " >> check config prop_size_insert- dbgMsg "prop_size_delete: " >> check config prop_size_delete- dbgMsg "prop_insert: " >> check config prop_insert- dbgMsg "prop_delete: " >> check config prop_delete- dbgMsg "prop_insDelIdempotent: " >> check config prop_insDelIdempotent- dbgMsg "prop_delDelIdempotent: " >> check config prop_delDelIdempotent- dbgMsg "prop_insInsIdempotent: " >> check config prop_insInsIdempotent- dbgMsg "prop_extensional: " >> check config prop_extensional- dbgMsg "prop_fromList: " >> check config prop_fromList- dbgMsg "prop_empty: " >> check config prop_empty+ dbgMsg "prop_size: " >> quickCheckWith myargs prop_size+ dbgMsg "prop_size_insert: " >> quickCheckWith myargs prop_size_insert+ dbgMsg "prop_size_delete: " >> quickCheckWith myargs prop_size_delete+ dbgMsg "prop_insert: " >> quickCheckWith myargs prop_insert+ dbgMsg "prop_delete: " >> quickCheckWith myargs prop_delete+ dbgMsg "prop_insDelIdempotent: " >> quickCheckWith myargs prop_insDelIdempotent+ dbgMsg "prop_delDelIdempotent: " >> quickCheckWith myargs prop_delDelIdempotent+ dbgMsg "prop_insInsIdempotent: " >> quickCheckWith myargs prop_insInsIdempotent+ dbgMsg "prop_extensional: " >> quickCheckWith myargs prop_extensional+ dbgMsg "prop_fromList: " >> quickCheckWith myargs prop_fromList+ dbgMsg "prop_empty: " >> quickCheckWith myargs prop_empty+ dbgMsg "prop_integral: " >> quickCheckWith (myargs{ maxSize = 40 }) prop_integral dbgMsg = hPutStr stderr -config = defaultConfig{ configMaxTest = 2000 }+myargs = stdArgs{ maxSize = 64 } -- * Quickcheck properties +trivial test = classify test "trivial"+ prop_size xs = trivial (List.null uxs) $ length uxs == size (foldr insert empty uxs)@@ -82,6 +85,11 @@ prop_empty x = not $ xa `member` empty where xa = abs x :: Int++prop_integral x s = trivial (null s) $ xa `member` reconstructed+ where reconstructed = unsafeFromIntegral (toIntegral xs)+ xa = abs x :: Int+ xs = xa `insert` s