deque (empty) → 0.1

raw patch · 4 files changed

+185/−0 lines, 4 filesdep +basedep +base-preludesetup-changed

Dependencies added: base, base-prelude

Files

• LICENSE +22/−0
• Setup.hs +2/−0
• deque.cabal +47/−0
• library/Deque.hs +114/−0

@@ -0,0 +1,22 @@+Copyright (c) 2016, Nikita Volkov++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.

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

@@ -0,0 +1,47 @@+name:+  deque+version:+  0.1+synopsis:+  Double-ended queue+description:+  An implementation of double-ended queue (aka Dequeue or Deque)+  based on the head-tail linked list.+homepage:+  https://github.com/nikita-volkov/deque +bug-reports:+  https://github.com/nikita-volkov/deque/issues +author:+  Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer:+  Nikita Volkov <nikita.y.volkov@mail.ru>+copyright:+  (c) 2016, Nikita Volkov+license:+  MIT+license-file:+  LICENSE+build-type:+  Simple+cabal-version:+  >=1.10+++source-repository head+  type:+    git+  location:+    git://github.com/nikita-volkov/deque.git+++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, OverloadedStrings, PatternGuards, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeFamilies, TypeOperators, UnboxedTuples+  default-language:+    Haskell2010+  exposed-modules:+    Deque+  build-depends:+    base-prelude < 2

@@ -0,0 +1,114 @@+module Deque where++import BasePrelude hiding (uncons, unsnoc, cons, snoc, reverse)+import qualified BasePrelude+++data Deque a =+  Deque [a] [a]++-- |+-- /O(1)/.+fromList :: [a] -> Deque a+fromList list =+  Deque [] list++-- |+-- /O(1)/, occasionally /O(n)/.+shiftRight :: Deque a -> Deque a+shiftRight deque =+  fromMaybe deque $+  fmap (\(a, b) -> snoc a b) $+  uncons deque++-- |+-- /O(1)/, occasionally /O(n)/.+shiftLeft :: Deque a -> Deque a+shiftLeft deque =+  fromMaybe deque $+  fmap (\(a, b) -> cons a b) $+  unsnoc deque++-- |+-- /O(1)/.+cons :: a -> Deque a -> Deque a+cons a (Deque snocList consList) =+  Deque (snocList) (a : consList)++-- |+-- /O(1)/.+snoc :: a -> Deque a -> Deque a+snoc a (Deque snocList consList) =+  Deque (a : snocList) (consList)++-- |+-- /O(1)/, occasionally /O(n)/.+uncons :: Deque a -> Maybe (a, Deque a)+uncons (Deque snocList consList) =+  case consList of+    head : tail ->+      Just (head, Deque snocList tail)+    _ ->+      case BasePrelude.reverse snocList of+        head : tail ->+          Just (head, Deque [] tail)+        _ ->+          Nothing++-- |+-- /O(1)/, occasionally /O(n)/.+unsnoc :: Deque a -> Maybe (a, Deque a)+unsnoc (Deque snocList consList) =+  case snocList of+    head : tail ->+      Just (head, Deque tail consList)+    _ ->+      case BasePrelude.reverse consList of+        head : tail ->+          Just (head, Deque tail [])+        _ ->+          Nothing++-- |+-- /O(n)/.+prepend :: Deque a -> Deque a -> Deque a+prepend (Deque snocList1 consList1) (Deque snocList2 consList2) =+  Deque snocList3 consList3+  where+    snocList3 =+      snocList2 ++ foldl' (flip (:)) snocList1 consList2+    consList3 =+      consList1++-- |+-- /O(1)/.+reverse :: Deque a -> Deque a+reverse (Deque snocList consList) =+  Deque consList snocList++-- |+-- /O(1)/, occasionally /O(n)/.+tail :: Deque a -> Deque a+tail =+  fromMaybe <$> id <*> fmap snd . uncons++-- |+-- /O(1)/, occasionally /O(n)/.+init :: Deque a -> Deque a+init =+  fromMaybe <$> id <*> fmap snd . unsnoc+++instance Monoid (Deque a) where+  mempty =+    Deque [] []+  mappend =+    prepend++instance Foldable Deque where+  foldr step init (Deque snocList consList) =+    foldr step (foldl' (flip step) init snocList) consList+  foldl' step init (Deque snocList consList) =+    foldr' (flip step) (foldl' step init consList) snocList++deriving instance Functor Deque