packages feed

SegmentTree (empty) → 0.1

raw patch · 5 files changed

+332/−0 lines, 5 filesdep +basesetup-changed

Dependencies added: base

Files

+ Data/SegmentTree.hs view
@@ -0,0 +1,75 @@+-- | This module contains the 'SegmentTree' data structure, its+-- constructor and the query function.+--+-- Example Usage:+--+-- @+--     import Data.Monoid+--     import Data.SegmentTree+--     ...+--     st = mkTree $ map Sum [0..10]+--     ...+--     queryTree st (0, 10) == Sum 55+--     queryTree st (5, 10) == Sum 45+--     queryTree st (0, 4)  == Sum 10+-- @++module Data.SegmentTree ( SegmentTree(..), mkTree, queryTree ) where++import Data.Monoid+import Text.Printf++data (Monoid a) => Tree a = Branch a (Tree a) (Tree a) | Leaf a++getCargo (Branch x _ _) = x+getCargo (Leaf x)       = x++-- | A 'SegmentTree' is a binary tree and the bounds of its+-- corresponding interval.+data (Monoid a) => SegmentTree a = SegmentTree (Tree a) (Int, Int)++instance (Monoid a) => Show (SegmentTree a) where+    show (SegmentTree t (l, u)) = unlines $ go t (l, u)+        where+          go (Branch _ lc rc) (l, u) = +              let m = (u-l) `div` 2+                  (ls, rs) = (go lc (l, l+m), go rc (l+m+1, u))+                  (ls', rs') = (indentTree True ls, indentTree False rs)+                  ts = printf "[%d..%d]" l u+              in concat [[ts], ls', rs']+          go (Leaf _) (l, u) = [printf "[%d]" l]+          indentTree _ [] = []+          indentTree True [x] = [printf "|-- %s" x]+          indentTree False [x] = [printf "`-- %s" x]+          indentTree True (x:xs) = indentTree True [x] ++ map ("|     "++) xs+          indentTree False (x:xs) = indentTree False [x] ++ map ("      "++) xs++-- | Build the 'SegmentTree' for the given list. Time: O(n*log n)+mkTree :: (Monoid a) => [a] -> SegmentTree a+mkTree xs = SegmentTree (go xs listBounds) listBounds+    where+      listBounds = (0, length xs - 1)+      go ys (l, u)+          -- invariant: head ys == xs !! l+          | l == u    = Leaf (head ys)+          | otherwise = +              let m      = (u-l) `div` 2+                  leftc  = go ys (l, l+m)+                  rightc = go (drop (m+1) ys) (l+m+1, u)+              in Branch (getCargo leftc `mappend` getCargo rightc) +                        leftc rightc++-- | Query the 'SegmentTree' for the specified closed interval. Time:+-- O(log n)+queryTree :: (Monoid a) => SegmentTree a -> (Int, Int) -> a+queryTree (SegmentTree t (s, e)) (l, u) = go t (s, e)+    where+      -- we're querying for (l, u)+      go t (s, e)+          | (l > e) || (u < s)   = mempty+          | (l <= s) && (u >= e) = getCargo t+          | otherwise = let (Branch _ leftc rightc) = t+                            m = (e-s) `div` 2+                            lv = go leftc (s, s+m)+                            rv = go rightc (s+m+1, e)+                        in lv `mappend` rv
+ Data/SegmentTree/Examples.hs view
@@ -0,0 +1,73 @@+-- | Example uses of 'SegmentTree's.++module Data.SegmentTree.Examples +    ( -- * Sum Monoid+      intervalSum+      -- * Any Monoid+    , intervalAny+      -- * GCD Monoid+    , GCD(..), intervalGCD+      -- * String Monoid+    , intervalConcat+      -- * Unwords Monoid+    , Unwords(..), intervalUnwords+    ) where++import Data.SegmentTree++import Data.Monoid++-------------+-- Sum monoid+-------------++-- | Find the sum of the elements in the interval [l, u].+intervalSum :: SegmentTree (Sum Int) -> (Int, Int) -> Int+intervalSum t bds@(l, u) = getSum $ queryTree t bds++-------------+-- Any monoid+-------------++-- | Find out if any of the elements are True in the interval [l, u].+intervalAny :: SegmentTree Any -> (Int, Int) -> Bool+intervalAny t bds@(l, u) = getAny $ queryTree t bds++-------------+-- GCD monoid+-------------++newtype (Integral a) => GCD a = GCD { getGCD :: a }++instance (Integral a) => Monoid (GCD a) where+    mempty = GCD $ fromIntegral 1+    (GCD x) `mappend` (GCD y) = GCD $ gcd x y+    +-- | Find the greatest common divisor of the elements in the interval+-- [l, u].+intervalGCD :: SegmentTree (GCD Int) -> (Int, Int) -> Int+intervalGCD t bds@(l, u) = getGCD $ queryTree t bds++----------------+-- String monoid+----------------++-- | Concatenate the strings in the interval [l, u].+intervalConcat :: SegmentTree String -> (Int, Int) -> String+intervalConcat t bds@(l, u) = queryTree t bds++---------------+-- Unwords monoid+---------------++newtype Unwords = Unwords { getUnwords :: String }++instance Monoid Unwords where+    mempty = Unwords ""+    (Unwords "") `mappend` y = y+    x `mappend` (Unwords "") = x+    (Unwords x) `mappend` (Unwords y) = Unwords (x ++ " " ++ y)++-- | Unwords the words in the interval [l, u].+intervalUnwords :: SegmentTree Unwords -> (Int, Int) -> String+intervalUnwords t bds@(l, u) = getUnwords $ queryTree t bds
+ LICENSE view
@@ -0,0 +1,165 @@+		   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.++   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.++  6. Revised Versions of the GNU Lesser General Public License.++  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.++  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.++  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.
+ SegmentTree.cabal view
@@ -0,0 +1,17 @@+Name:		SegmentTree+Version:	0.1+Cabal-Version:	>= 1.2+Build-type:	Simple+License:	LGPL+License-File:	LICENSE+Author:		Alexandru Scvortov+Maintainer:	scvalex@gmail.com+Homepage:	http://scvalex.github.com/articles/SegmentTree.html+Category:	Data+Synopsis:	Data structure for O(log n) mconcats on list intervals+Description:	The 'SegmentTree' data structure allows for logarithmic +                time accumulations on preprocessed lists of 'Monoid's.++Library+  Build-Depends:	base+  Exposed-modules:	Data.SegmentTree, Data.SegmentTree.Examples
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain