1*dbdfc1f6Syamt{- 2*dbdfc1f6Syamt/* $NetBSD: lru.hs,v 1.1 2006/10/09 12:32:46 yamt Exp $ */ 3*dbdfc1f6Syamt 4*dbdfc1f6Syamt/*- 5*dbdfc1f6Syamt * Copyright (c)2005 YAMAMOTO Takashi, 6*dbdfc1f6Syamt * All rights reserved. 7*dbdfc1f6Syamt * 8*dbdfc1f6Syamt * Redistribution and use in source and binary forms, with or without 9*dbdfc1f6Syamt * modification, are permitted provided that the following conditions 10*dbdfc1f6Syamt * are met: 11*dbdfc1f6Syamt * 1. Redistributions of source code must retain the above copyright 12*dbdfc1f6Syamt * notice, this list of conditions and the following disclaimer. 13*dbdfc1f6Syamt * 2. Redistributions in binary form must reproduce the above copyright 14*dbdfc1f6Syamt * notice, this list of conditions and the following disclaimer in the 15*dbdfc1f6Syamt * documentation and/or other materials provided with the distribution. 16*dbdfc1f6Syamt * 17*dbdfc1f6Syamt * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18*dbdfc1f6Syamt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19*dbdfc1f6Syamt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20*dbdfc1f6Syamt * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21*dbdfc1f6Syamt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22*dbdfc1f6Syamt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23*dbdfc1f6Syamt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24*dbdfc1f6Syamt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25*dbdfc1f6Syamt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26*dbdfc1f6Syamt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27*dbdfc1f6Syamt * SUCH DAMAGE. 28*dbdfc1f6Syamt */ 29*dbdfc1f6Syamt-} 30*dbdfc1f6Syamt 31*dbdfc1f6Syamtimport System.Environment 32*dbdfc1f6Syamtimport System.IO 33*dbdfc1f6Syamtimport List 34*dbdfc1f6Syamtimport Maybe 35*dbdfc1f6Syamt 36*dbdfc1f6Syamtcontain x xs = isJust $ find (== x) xs 37*dbdfc1f6Syamt 38*dbdfc1f6Syamtdo_lru1 npg n q qlen [] = (reverse n, q) 39*dbdfc1f6Syamtdo_lru1 npg n q qlen rs@(r:rs2) = 40*dbdfc1f6Syamt if contain r q then 41*dbdfc1f6Syamt let 42*dbdfc1f6Syamt nq = delete r q 43*dbdfc1f6Syamt in 44*dbdfc1f6Syamt do_lru1 npg n (r:nq) qlen rs2 45*dbdfc1f6Syamt else if qlen < npg then 46*dbdfc1f6Syamt do_lru1 npg (r:n) (r:q) (qlen+1) rs2 47*dbdfc1f6Syamt else 48*dbdfc1f6Syamt let 49*dbdfc1f6Syamt nq = take (qlen-1) q 50*dbdfc1f6Syamt in 51*dbdfc1f6Syamt do_lru1 npg (r:n) (r:nq) qlen rs2 52*dbdfc1f6Syamt 53*dbdfc1f6Syamtdo_lru npg rs = fst $ do_lru1 npg [] [] 0 rs 54*dbdfc1f6Syamt 55*dbdfc1f6Syamtmain = do 56*dbdfc1f6Syamt xs <- getContents 57*dbdfc1f6Syamt args <- getArgs 58*dbdfc1f6Syamt let 59*dbdfc1f6Syamt ls = lines xs 60*dbdfc1f6Syamt npgs::Int 61*dbdfc1f6Syamt npgs = read $ args !! 0 62*dbdfc1f6Syamt pgs::[Int] 63*dbdfc1f6Syamt pgs = map read ls 64*dbdfc1f6Syamt mapM_ print $ do_lru npgs pgs 65