Merge branch 'master' into popl2012

Conflicts:
	program/Main.hs

Semantic conflicts:
	program/README (left a FIXME to adapt it for popl2012)

diff --git a/program/Main.hs b/program/Main.hs
index d45755e..92c91fc 100644 (file)
--- a/program/Main.hs
+++ b/program/Main.hs
@@ -5,28 +5,15 @@ import System.IO
 import Data.Array.IArray
 import Data.Array.Unboxed
 import ArrayStuff
-import Text.CSV
+import TSV
 
 -- Command-line interface with simple tab-separated input/output formats.
 -- ./match <example.in
 
--- pretty silly but it does the job
-swapTabCommaIn s = map (\c -> if c == '\t' then ',' else if c == ',' then '\t' else c) s
-removeQuotes s = filter (\c -> not (c == '"')) s
-
--- Some versions of Text.CSV do not use or accept a trailing newline; compensate for that.
-removeTrailingNewline s = if not (null s) && last s == '\n' then init s else s
-addTrailingNewline s = if not (null s) && last s /= '\n' then s ++ ['\n'] else s
-
-parseTSV fname str = case parseCSV fname (swapTabCommaIn $ removeTrailingNewline str) of
-       Left pe -> Left pe
-       Right ll -> Right $ map (map swapTabCommaIn) ll
-printTSV ll = addTrailingNewline $ removeQuotes $ swapTabCommaIn $ printCSV $ map (map swapTabCommaIn) ll
-
 main = do
        incsv <- hGetContents stdin
        -- handle errors another day, or let the platform do it
-       let Right inll = parseTSV "standard input" incsv
+       let inll = parseTSV incsv
        let loadList = tail (head inll)
        let numRvrs = length loadList
        let loadA = listArray (0, numRvrs-1) (map read loadList)
@@ -45,4 +32,4 @@ main = do
        let pnrA = funcArray (0, numProps-1) (\j -> read $ pxarr ! (2*j, 0))
        let theInst = PMInstance numRvrs numProps loadA prefA expA fixA pnrA
        let PMatching theMatching = doMatching pmDefaults theInst
-       hPutStr stdout $ printTSV $ map (\(i, j) -> map show [i, j]) theMatching
+       hPutStr stdout $ formatTSV $ map (\(i, j) -> map show [i, j]) theMatching

diff --git a/program/Makefile b/program/Makefile
index d72db83..344ddf0 100644 (file)
--- a/program/Makefile
+++ b/program/Makefile
@@ -10,4 +10,4 @@ all-optimized:
 clean:
        rm -f *.hi *.o match
 
-# Necessary libraries (on Fedora): ghc-fgl, ghc-csv.  Others I miss?
+# Necessary libraries (on Fedora): ghc-fgl.  Others I miss?

diff --git a/program/README b/program/README
new file mode 100644 (file)
index 0000000..56e3d08
--- /dev/null
+++ b/program/README
@@ -0,0 +1,40 @@
+                        Proposal matcher implementation
+
+                   By Matt McCutchen <matt@mattmccutchen.net>
+             in collaboration with Samir Khuller <samir@cs.umd.edu>
+
+TODO: There is probably more to say here about the program, even after we add
+the paper about the algorithm/reduction.
+
+Setup
+-----
+
+Requirements:
+- GHC on your $PATH
+- GHC "fgl" package
+
+Compile with "make".
+
+Interactive experimentation
+---------------------------
+
+"./run" starts GHCi with all of the important definitions of the proposal
+matcher in scope.  This is good for interactive experimentation.
+
+Batch front-end
+---------------
+
+./match is a front-end that reads an instance from stdin and prints the matching
+to stdout.
+
+<<< FIXME: Adapt the following for popl2012 branch >>>
+Input: A tab-separated array with one column per reviewer.  The first row gives
+the relative loads of the reviewers.  Thereafter, each row gives the preference
+values (1 to 39, 40 = conflict of interest) of all reviewers for a single
+proposal.  See the example.in.
+
+Reviewers and proposals are numbered from 0 in the order they appear in the
+input.
+
+Output: A tab-separated array.  Each row gives the reviewer number and proposal
+number of a matched pair.

diff --git a/program/TSV.hs b/program/TSV.hs
new file mode 100644 (file)
index 0000000..9b2cf9f
--- /dev/null
+++ b/program/TSV.hs
@@ -0,0 +1,31 @@
+module TSV (
+       parseTSV, formatTSV
+) where
+import Data.List
+
+-- Simple implementation of tab-separated values with a trailing newline and no
+-- quoting support.
+
+splitList :: Eq a => a -> Bool -> [a] -> [[a]]
+splitList delim terminated =
+       let sl [] | terminated = []
+           sl l = case break (== delim) l of
+                  (hh, []) -> [hh]
+                  (hh, {-delim-} _ : t) -> hh : sl t
+       in sl
+
+-- We use the Eq only to check the validity...
+joinList :: Eq a => a -> Bool -> [[a]] -> [a]
+joinList delim terminated l =
+       if any (any (== delim)) l then error "joinList: item contains delimiter"
+       else if terminated
+       then concatMap (++ [delim]) l
+       else intercalate [delim] l
+
+type TSV = [[String]]
+
+formatTSV :: TSV -> String
+formatTSV = joinList '\n' True . map (joinList '\t' False)
+
+parseTSV :: String -> TSV
+parseTSV = map (splitList '\t' False) . splitList '\n' True