smawk (empty) → 0

raw patch · 5 files changed

+394/−0 lines, 5 filesdep +basedep +primitivedep +semigroupoids

Dependencies added: base, primitive, semigroupoids, transformers

Files

• CHANGELOG.md +2/−0
• LICENSE.md +230/−0
• README.md +27/−0
• smawk.cabal +47/−0
• src/Data/Smawk.hs +88/−0

@@ -0,0 +1,2 @@+# 0+* Written

@@ -0,0 +1,230 @@+# License++Licensed under either of+ * Apache License, Version 2.0 (http://www.apache.org/licenses/LICENSE-2.0)+ * BSD 2-Clause license (https://opensource.org/licenses/BSD-2-Clause)+at your option.++## BSD 2-Clause License++- Copyright 2019 Edward Kmett and Sean Chalmers++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:++1. Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.++2. 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.++THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``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 AUTHORS 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.++## Apache License++_Version 2.0, January 2004_  +_&lt;<http://www.apache.org/licenses/>&gt;_++### Terms and Conditions for use, reproduction, and distribution++#### 1. Definitions++“License” shall mean the terms and conditions for use, reproduction, and+distribution as defined by Sections 1 through 9 of this document.++“Licensor” shall mean the copyright owner or entity authorized by the copyright+owner that is granting the License.++“Legal Entity” shall mean the union of the acting entity and all other entities+that control, are controlled by, or are under common control with that entity.+For the purposes of this definition, “control” means **(i)** the power, direct or+indirect, to cause the direction or management of such entity, whether by+contract or otherwise, or **(ii)** ownership of fifty percent (50%) or more of the+outstanding shares, or **(iii)** beneficial ownership of such entity.++“You” (or “Your”) shall mean an individual or Legal Entity exercising+permissions granted by this License.++“Source” form shall mean the preferred form for making modifications, including+but not limited to software source code, documentation source, and configuration+files.++“Object” form shall mean any form resulting from mechanical transformation or+translation of a Source form, including but not limited to compiled object code,+generated documentation, and conversions to other media types.++“Work” shall mean the work of authorship, whether in Source or Object form, made+available under the License, as indicated by a copyright notice that is included+in or attached to the work (an example is provided in the Appendix below).++“Derivative Works” shall mean any work, whether in Source or Object form, that+is based on (or derived from) the Work and for which the editorial revisions,+annotations, elaborations, or other modifications represent, as a whole, an+original work of authorship. For the purposes of this License, Derivative Works+shall not include works that remain separable from, or merely link (or bind by+name) to the interfaces of, the Work and Derivative Works thereof.++“Contribution” shall mean any work of authorship, including the original version+of the Work and any modifications or additions to that Work or Derivative Works+thereof, that is intentionally submitted to Licensor for inclusion in the Work+by the copyright owner or by an individual or Legal Entity authorized to submit+on behalf of the copyright owner. For the purposes of this definition,+“submitted” means any form of electronic, verbal, or written communication sent+to the Licensor or its representatives, including but not limited to+communication on electronic mailing lists, source code control systems, and+issue tracking systems that are managed by, or on behalf of, the Licensor for+the purpose of discussing and improving the Work, but excluding communication+that is conspicuously marked or otherwise designated in writing by the copyright+owner as “Not a Contribution.”++“Contributor” shall mean Licensor and any individual or Legal Entity on behalf+of whom a Contribution has been received by Licensor and subsequently+incorporated within the Work.++#### 2. Grant of Copyright License++Subject to the terms and conditions of this License, each Contributor hereby+grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free,+irrevocable copyright license to reproduce, prepare Derivative Works of,+publicly display, publicly perform, sublicense, and distribute the Work and such+Derivative Works in Source or Object form.++#### 3. Grant of Patent License++Subject to the terms and conditions of this License, each Contributor hereby+grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free,+irrevocable (except as stated in this section) patent license to make, have+made, use, offer to sell, sell, import, and otherwise transfer the Work, where+such license applies only to those patent claims licensable by such Contributor+that are necessarily infringed by their Contribution(s) alone or by combination+of their Contribution(s) with the Work to which such Contribution(s) was+submitted. If You institute patent litigation against any entity (including a+cross-claim or counterclaim in a lawsuit) alleging that the Work or a+Contribution incorporated within the Work constitutes direct or contributory+patent infringement, then any patent licenses granted to You under this License+for that Work shall terminate as of the date such litigation is filed.++#### 4. Redistribution++You may reproduce and distribute copies of the Work or Derivative Works thereof+in any medium, with or without modifications, and in Source or Object form,+provided that You meet the following conditions:++* **(a)** You must give any other recipients of the Work or Derivative Works a copy of+this License; and+* **(b)** You must cause any modified files to carry prominent notices stating that You+changed the files; and+* **(c)** You must retain, in the Source form of any Derivative Works that You distribute,+all copyright, patent, trademark, and attribution notices from the Source form+of the Work, excluding those notices that do not pertain to any part of the+Derivative Works; and+* **(d)** If the Work includes a “NOTICE” text file as part of its distribution, then any+Derivative Works that You distribute must include a readable copy of the+attribution notices contained within such NOTICE file, excluding those notices+that do not pertain to any part of the Derivative Works, in at least one of the+following places: within a NOTICE text file distributed as part of the+Derivative Works; within the Source form or documentation, if provided along+with the Derivative Works; or, within a display generated by the Derivative+Works, if and wherever such third-party notices normally appear. The contents of+the NOTICE file are for informational purposes only and do not modify the+License. You may add Your own attribution notices within Derivative Works that+You distribute, alongside or as an addendum to the NOTICE text from the Work,+provided that such additional attribution notices cannot be construed as+modifying the License.++You may add Your own copyright statement to Your modifications and may provide+additional or different license terms and conditions for use, reproduction, or+distribution of Your modifications, or for any such Derivative Works as a whole,+provided Your use, reproduction, and distribution of the Work otherwise complies+with the conditions stated in this License.++#### 5. Submission of Contributions++Unless You explicitly state otherwise, any Contribution intentionally submitted+for inclusion in the Work by You to the Licensor shall be under the terms and+conditions of this License, without any additional terms or conditions.+Notwithstanding the above, nothing herein shall supersede or modify the terms of+any separate license agreement you may have executed with Licensor regarding+such Contributions.++#### 6. Trademarks++This License does not grant permission to use the trade names, trademarks,+service marks, or product names of the Licensor, except as required for+reasonable and customary use in describing the origin of the Work and+reproducing the content of the NOTICE file.++#### 7. Disclaimer of Warranty++Unless required by applicable law or agreed to in writing, Licensor provides the+Work (and each Contributor provides its Contributions) on an “AS IS” BASIS,+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied,+including, without limitation, any warranties or conditions of TITLE,+NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A PARTICULAR PURPOSE. You are+solely responsible for determining the appropriateness of using or+redistributing the Work and assume any risks associated with Your exercise of+permissions under this License.++#### 8. Limitation of Liability++In no event and under no legal theory, whether in tort (including negligence),+contract, or otherwise, unless required by applicable law (such as deliberate+and grossly negligent acts) or agreed to in writing, shall any Contributor be+liable to You for damages, including any direct, indirect, special, incidental,+or consequential damages of any character arising as a result of this License or+out of the use or inability to use the Work (including but not limited to+damages for loss of goodwill, work stoppage, computer failure or malfunction, or+any and all other commercial damages or losses), even if such Contributor has+been advised of the possibility of such damages.++#### 9. Accepting Warranty or Additional Liability++While redistributing the Work or Derivative Works thereof, You may choose to+offer, and charge a fee for, acceptance of support, warranty, indemnity, or+other liability obligations and/or rights consistent with this License. However,+in accepting such obligations, You may act only on Your own behalf and on Your+sole responsibility, not on behalf of any other Contributor, and only if You+agree to indemnify, defend, and hold each Contributor harmless for any liability+incurred by, or claims asserted against, such Contributor by reason of your+accepting any such warranty or additional liability.++_END OF TERMS AND CONDITIONS_++### APPENDIX: How to apply the Apache License to your work++To apply the Apache License to your work, attach the following boilerplate+notice, with the fields enclosed by brackets `[]` replaced with your own+identifying information. (Don't include the brackets!) The text should be+enclosed in the appropriate comment syntax for the file format. We also+recommend that a file or class name and description of purpose be included on+the same “printed page” as the copyright notice for easier identification within+third-party archives.++    Copyright [yyyy] [name of copyright owner]+    +    Licensed under the Apache License, Version 2.0 (the "License");+    you may not use this file except in compliance with the License.+    You may obtain a copy of the License at+    +      http://www.apache.org/licenses/LICENSE-2.0+    +    Unless required by applicable law or agreed to in writing, software+    distributed under the License is distributed on an "AS IS" BASIS,+    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+    See the License for the specific language governing permissions and+    limitations under the License.+

@@ -0,0 +1,27 @@+smawk+=====++[![Hackage][hackage-shield]][hackage]++This package implements the SMAWK algorithm by+[Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber and Maria Klawe][smawk]+for finding the minimum value in each row of an implicitly defined totally monotone matrix.++This has many applications in computational geometry, such as finding the farthest point+from each point in a convex polygon, finding optimal enclosing polygon. It can also be+used to implement paragraph line breaking in a manner analogous to Knuth and Platt, but in+linear time. It also has uses in RNA secondary structure prediction, various sequence+alignment problems, construction of prefix codes, image thresholding, etc.++Contact Information+-------------------++Contributions and bug reports are welcome!++Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.++-Edward Kmett++[smawk]: https://link.springer.com/article/10.1007%2FBF01840359+[hackage]: https://hackage.haskell.org/package/smawk+[hackage-shield]: https://img.shields.io/hackage/v/smawk.svg

@@ -0,0 +1,47 @@+cabal-version: 2.2+name: smawk+version: 0+synopsis: Linear time row minima for totally monotone matrices+homepage: https://github.com/ekmett/codex/tree/master/smawk#readme+license: BSD-2-Clause OR Apache-2.0+license-file: LICENSE.md+author: Edward Kmett+maintainer: Edward Kmett <ekmett@gmail.com>+copyright: Copyright (c) 2019 Edward Kmett+stability: experimental+category: FFI+build-type: Simple+description:+  This implements the SMAWK algorithm by Peter Shor, Shlomo Moran,+  Alok Aggarwal, Robert Wilber and Maria Klawe for finding the minimum+  value in each row of an implicitly defined totally monotone matrix.+  .+  This has many applications in computational geometry, such as finding+  the farthest point from each point in a convex polygon, finding+  optimal enclosing polygon. It can also be used to implement paragraph+  line breaking in a manner analogous to Knuth and Platt, but in linear+  time. It also has uses in RNA secondary structure prediction, various+  sequence alignment problems, construction of prefix codes, image+  thresholding, etc.+extra-doc-files:+  README.md,+  CHANGELOG.md++source-repository head+  type: git+  location: https://github.com/ekmett/codex+  subdir: smawk++library+  hs-source-dirs: src+  default-language: Haskell2010+  ghc-options:+    -Wall -Wincomplete-uni-patterns -Wincomplete-record-updates+    -Wredundant-constraints -Widentities -Wmissing-export-lists+  build-depends:+    , base >= 4.11 && < 5+    , primitive ^>= 0.7+    , semigroupoids >= 5 && < 6+    , transformers ^>= 0.5.5+  exposed-modules:+    Data.Smawk

@@ -0,0 +1,88 @@+{-# options_ghc -Wno-incomplete-uni-patterns #-}++-- | This module implements a generalized version of the SMAWK algorithm+-- for computing row minima in totally ordered matrices.+--+-- I do not require rows or column numbers to be actual numbers, or even ordered,+-- instead comparing columns using occurrence order.+--+-- Unlike @Map@-based implementations, the runtime of this is actually linear.+module Data.Smawk+  ( smawk+  , smawk1+  ) where++import Control.Monad.Trans.State.Strict+import qualified Data.Foldable as Foldable+import Data.Maybe (fromJust)+import Data.Semigroup (Min(..),Arg(..))+import Data.Semigroup.Foldable (Foldable1)+import Data.List.NonEmpty (nonEmpty)+import Data.Primitive.Array (indexArray)+import GHC.Exts as Exts++-- |+-- >>> collate "abcde"+-- ("ace","bd")+collate :: [a] -> ([a],[a])+collate = Prelude.foldr (\a ~(x,y) -> (a:y,x)) mempty++-- |+-- @'uncurry' 'interleave' . 'collate' = id@+--+-- >>> interleave "ace" "bd"+-- "abcde"+interleave :: [a] -> [a] -> [a]+interleave (a:as) bs = a:interleave bs as+interleave [] bs = bs++-- |+-- /O(|rows| + |cols|)/.+--+-- Computes __row__ minima in totally monotone matrices using the SMAWK algorithm.+--+-- Returns 'Nothing' if we have no columns.+smawk+  :: (Traversable f, Foldable g, Ord a)+  => f r -- ^ rows (in any desired ascending order)+  -> g c -- ^ columns (in any desired ascending order)+  -> (r -> c -> a) -- ^ a monotone matrix+  -> Maybe (f c) -- ^ each of the row minima+smawk rs cs0 m = (\cs -> smawk1 rs cs m) <$> nonEmpty (Foldable.toList cs0)+{-# inline smawk #-}++-- |+-- /O(|rows| + |cols|)/.+--+-- Computes __row__ minima in totally monotone matrices using the SMAWK algorithm.+smawk1+  :: (Traversable f, Foldable1 g, Ord a)+  => f r -- ^ rows (in any desired ascending order)+  -> g c -- ^ columns (in any desired ascending order)+  -> (r -> c -> a) -- ^ a monotone matrix+  -> f c -- ^ each of the row minima+smawk1 rs0 cs0 m = evalState (traverse refill rs0) $ go (Foldable.toList rs0) [0..length raws-1] where+  raws = Exts.fromList $ Foldable.toList cs0+  refill _ = state $ \ ~(x:xs) -> (indexArray raws x,xs)+  go [] _ = []+  go rs cs = interleave broken minima where+    m' r c = m r (indexArray raws c)+    broken = zipWith skim es $ path cs' (minima <> repeat l)+    -- skim a bs = snd $ minimum $ fmap (\i -> (m i a, i)) bs+    skim a bs = case getMin $ fromJust $ foldMap (\i -> Just $ Min $ Arg (m' a i) i) bs of Arg _ i -> i+    path xs ~(y:ys) = case span (<=y) xs of+      (as, bs) -> as:path (y:bs) ys+    rs' = Exts.fromList rs -- a zipper yields same complexity, worst constants+    n = length rs'+    minima = go os cs'+    (es,os) = collate rs+    rcs' = reduce cs [] 0+    cs' = reverse rcs'+    l = head rcs'+    reduce [] ys _ = ys+    reduce (x:xs) [] _ = reduce xs [x] 1+    reduce xxs@(x:xs) yys@(y:ys) t+      | ri <- indexArray rs' (t-1), m' ri y > m' ri y = reduce xxs ys (t-1)+      | t /= n = reduce xs (x:yys) (t+1)+      | otherwise = reduce xs yys t+{-# inlinable smawk1 #-}