root/hiersort/sim/Que.hs

-- | Que.hs
-- A simple O(1) queue.
--
-- Copytight (C) 2007, 2008 Serguey Zefirov
--
-- This program is free software; you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation; either version 3, or (at your option)
-- any later version.
-- See file COPYING or visit http://www.gnu.org/licenses for details.

-- I wrote this because broken compatibility in Data.Seq library module between
-- my two home computers with ghc 6.4 and ghc 6.6+.
--

module Que(
                 Que(..)
                ,empty
                ,fromList
                ,toList
                ,head
                ,size
                ,insert
                ,append
                ,appends
                ,take
        ) where

import Prelude (id,(.),(++),($),reverse,length,otherwise,Ord(..),Num(..),Maybe(..),Show(..))

data Que a = Que [a] [a]

empty = Que [] []

head (Que (x:xs) ys) = Just (x,Que xs ys)
head (Que [] []) = Nothing
head (Que _  ys) = let (x:xs) = reverse ys in Just (x,Que xs [])

insert x (Que xs ys) = Que (x:xs) ys

append y (Que xs ys) = Que xs (y:ys)
appends [] = id
appends (x:xs) = appends xs . append x

size (Que xs ys) = length xs + length ys

fromList xs = Que xs []

toList (Que xs ys) = xs++reverse ys

instance Show a => Show (Que a) where
        show q = "fromList "++show (toList q)

take n q
        | n > 0, Just (x,q') <- head q = let (l,q'') = take (n-1) q' in (x:l,q'')
        | otherwise = ([],q)