#!/n/flip/h/dreeves/mash/mash

pout[args__] := WriteString["stdout", args]perr[args__] := WriteString["stderr", args]\(SetAttributes[assert, HoldFirst]; 

    assert[test_] := 
      If[\(! Evaluate[test]\), {perr["FAILED: ", Hold[test], "
"]; 
          Exit[1]; }, True]; \)

\(\( (*\ Command - line\ args\ for\ use\ with\ Front - \(end : \)\ *) 

    \(ARGV = {"progname", "test.url", "test.req", 
        "1*1024^2"}; \)\)\)

\(If[Length[ARGV] < 4, 
	
      pout["Usage: ", ARGV[\([1]\)], 
        " url-file request-file cache-size
"]; 
	Exit[1]]; 


    urlFilename = ARGV[\([2]\)]; 
reqFilename = ARGV[\([3]\)]; 

    cacheSize = ToExpression[ARGV[\([4]\)]]; 


    perr["Begin slurping data.
"]; 

    idSizePairs = ReadList[urlFilename, {Number, Number}]; 

    Scan[\((size[#[\([1]\)]] = #[\([2]\)]; next[#[\([1]\)]] = Null; 
          prev[#[\([1]\)]] = Null)\)&, idSizePairs]; 

    perr["Done slurping id/size data.
"]; 

    requests = ReadList[reqFilename]; 

    perr["Done slurping requests.
"]; 

free = cacheSize; 

    cacheHead = \(-1\); 
cacheTail = \(-2\); 
next[cacheHead] = cacheTail; 
    prev[cacheHead] = Null; 
prev[cacheTail] = cacheHead; 
    next[cacheTail] = Null; 
hitCount = 0; 


    in[id_] := prev[id] =!= Null && next[id] =!= Null
\)\(insertBefore[x_, me_] := 
      \((
		assert[prev[me] === Null && next[me] === Null]; 
		
        prev[me] = prev[x]; next[me] = x; 
		next[prev[x]] = me; 
        prev[x] = me; 
		me)\)\)\(insertAfter[x_, me_] := insertBefore[next[x], me]
\)\(remove[me_] := 
      \((
		next[prev[me]] = next[me]; prev[next[me]] = prev[me]; 
		
        prev[me] = Null; next[me] = Null; 
		me)\)
\)\(printcache[str_] := 
      Module[{p}, 
		pout[str, ": "]; 
		
        For[p = cacheHead, p != cacheTail, p = next[p], 
			
          pout[p, ", "]]; 
		pout[cacheTail]; 
		
        pout["  free: ", free, "
"]; ]
\)\(processRequest[id_] := 
	
      Which[
		in[id], 
			\(hitCount++\); 
			remove[id]; 
			
        insertAfter[cacheHead, id], 
		size[id] > cacheSize, Null, 
		
        True, 
			
        While[free < size[id], 
				
          assert[prev[cacheTail] != cacheHead]; 
				
          free += size[remove[prev[cacheTail]]]]; 
			
        free -= size[insertAfter[cacheHead, id]]]
\)\(time = \(Scan[processRequest, requests] // Timing\) // First; 


    pout[hitCount, "
"]; 

    perr["Hit ratio: ", hitCount, " / ", Length[requests], " = ", 
      N[hitCount/Length[requests]], "
(CPU time: ", time, ")
"]; 
    \)