sequential-index (empty) → 0.0

raw patch · 5 files changed

+190/−0 lines, 5 filesdep +basedep +bytestringsetup-changed

Dependencies added: base, bytestring

Files

• Data/SequentialIndex.hs +87/−0
• LICENSE +30/−0
• README +4/−0
• Setup.hs +2/−0
• sequential-index.cabal +67/−0

@@ -0,0 +1,87 @@+module Data.SequentialIndex+(+  SequentialIndex+, mantissa+, exponent+, zero+, one+, sequentialIndex+, between+, toByteString+, fromByteString+)+where++import           Data.Bits+import           Prelude         hiding (exponent)+import qualified Data.ByteString as B++-- must always be in normalised form!+data SequentialIndex +    = SI !Integer !Int+    deriving (Eq)++mantissa :: SequentialIndex -> Integer+mantissa (SI m _) = m++exponent :: SequentialIndex -> Int+exponent (SI _ e) = e++zero :: SequentialIndex+zero = SI 0 0++one :: SequentialIndex+one = SI 1 0++commonBase :: SequentialIndex -> SequentialIndex -> (Integer, Integer, Int)+commonBase (SI m1 e1) (SI m2 e2) = (m1', m2', e)+    where e = max e1 e2+          m1' = m1 `shift` (e - e1)+          m2' = m2 `shift` (e - e2)++sequentialIndex :: Integer -> Int -> SequentialIndex+sequentialIndex 0 _ = zero+sequentialIndex mx ex+    = case () of+        _ | v < zero  -> error "Invalid SequentialIndex: below zero"+          | v > one   -> error "Invalid SequentialIndex: beyond one"+          | otherwise -> v+    where v = until (\(SI m _) -> m `testBit` 0) +                    (\(SI m e) -> SI (m `shiftR` 1) (e - 1)) +                    (SI mx ex)++instance Bounded SequentialIndex where+    minBound = zero+    maxBound = one++instance Ord SequentialIndex where+    a `compare` b = a' `compare` b'+        where (a', b', _) = commonBase a b++instance Show SequentialIndex where+    show (SI m e) = case map sbit bits of+                      []      -> "0.0"+                      [d1]    -> d1 : ".0"+                      (d1:ds) -> d1 : '.' : ds+        where bits = map (testBit m) [e, e - 1 .. 0]+              +              sbit False = '0'+              sbit True  = '1'++between :: SequentialIndex -> SequentialIndex -> SequentialIndex+between a b = sequentialIndex (m1 + m2) (e + 1)+    where (m1, m2, e) = commonBase a b++toByteString :: SequentialIndex -> B.ByteString+toByteString (SI m e) = B.unfoldr step m'+    where e' = (e `div` 8) * 8 + 7+          m' = m `shift` (e' - e)++          step 0 = Nothing+          step v = let (q, r) = v `divMod` 256+                   in Just (fromInteger r, q)++fromByteString :: B.ByteString -> SequentialIndex+fromByteString bs = sequentialIndex m (max 0 $ e - 1)+    where (m, e) = B.foldr step (0, 0) bs+          step w (mx, ex) = (mx `shiftL` 8 + toInteger w, ex + 8)

@@ -0,0 +1,30 @@+Copyright (c)2011, Aristid Breitkreuz++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * 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.++    * Neither the name of Aristid Breitkreuz nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++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.

@@ -0,0 +1,4 @@+Sequential index numbers between 0.0 and 1.0 that allow arbitrarily inserting new numbers in between. They can possibly used for disk-based and other special containers, where adding a new element without changing the indexes of the other elements is important.++Conceptually, SequentialIndex denotes a path to an element in an imaginary binary tree.+

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,67 @@+-- sequential-index.cabal auto-generated by cabal init. For additional+-- options, see+-- http://www.haskell.org/cabal/release/cabal-latest/doc/users-guide/authors.html#pkg-descr.+-- The name of the package.+Name:                sequential-index++-- The package version. See the Haskell package versioning policy+-- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for+-- standards guiding when and how versions should be incremented.+Version:             0.0++-- A short (one-line) description of the package.+Synopsis:            Sequential index numbers between 0.0 and 1.0 that allow arbitrarily inserting new numbers in between (for special containers).++-- A longer description of the package.+Description:         Sequential index numbers between 0.0 and 1.0 that allow arbitrarily inserting new numbers in between. They can possibly used for disk-based and other special containers, where adding a new element without changing the indexes of the other elements is important.+                     +                     Conceptually, SequentialIndex denotes a path to an element in an imaginary binary tree.++-- The license under which the package is released.+License:             BSD3++-- The file containing the license text.+License-file:        LICENSE++-- The package author(s).+Author:              Aristid Breitkreuz++-- An email address to which users can send suggestions, bug reports,+-- and patches.+Maintainer:          aristidb@googlemail.com++-- A copyright notice.+Copyright:           Copyright (C) 2011 Aristid Breitkreuz++Homepage:            https://github.com/aristidb/sequential-index++Category:            Data++Build-type:          Simple++-- Extra files to be distributed with the package, such as examples or+-- a README.+Extra-source-files:  README++-- Constraint on the version of Cabal needed to build this package.+Cabal-version:       >=1.2+++Library+  -- Modules exported by the library.+  Exposed-modules:     Data.SequentialIndex++  -- GHC Options.+  GHC-Options:         -Wall+  +  -- Packages needed in order to build this package.+  Build-depends:+                       base >=4.2.0.0 && <5,+                       bytestring >=0.9.1.5 && <0.10+  +  -- Modules not exported by this package.+  -- Other-modules:       +  +  -- Extra tools (e.g. alex, hsc2hs, ...) needed to build the source.+  -- Build-tools:         +