Australian Voting

Australian Voting was fun, I set up 3 classes: Ballot, Candidate, and Election to simulate the election.

Ballot keeps track of a single ballot and which vote on that ballot is active. Candidate keeps a linked list of the Ballots that that Candidate owns, and it's responsible for redistributing those ballots when it loses. It also keeps track of how many votes it has so we can determine who has won. Election keeps an array of all the ballots and candidates, and runs the actual election process. The main() function reads in the input and drives the Election.

I built the 'array of intermingled linked lists' that Downing discussed when he introduced the project. It's a very elegant method of dealing with the ballots and minimizing the number of ballots which need to be recalculated.

To get the Candidate to be able to talk back to the Election to give its ballots back to other Candidates, I had to move all the class definitions above the method definitions. This isn't that hard, but it means you have to state all the methods as Election::AddBallot() instead of just AddBallot().

I used getline() and istringstream to parse the input, it worked better than using >> on cin for looking at each line.

Unfortunately, UVa was down all Sunday, so I couldn't test my project. All the inputs I gave it seemed to give good results, and it worked against the tests I found on Blackboard, but about 1 in the morning UVa messaged me with a Failure. It would have been nice to know that before the turn in deadline.....

Stable Marriage looks interesting, I remember this problem from my Algorithms class with Plaxton. Everybody always cracks up at the word 'man-optimal'. I'm glad we don't have to prove things about SMP, but it's going to be interesting to implement it efficiently.

Sick

I'm sick today.  Luckily I wasn't sick last week for the test....

In other news, the test wasn't too bad, I'm happy with my grade.  I was surprised at the content of the test, because it definitely had more specifics than I thought it would.  The question about CRC I thought was too specific, it caught me off guard.

The implementing preincrement and postincrement operators was a great question though, because it foreshadows operator overloading.  That'll be fun.

MacFUSE

Have you ever gotten frustrated with having to scp things around to your CS account from your Mac?  Wouldn't it be nice if you could just drag and drop?

Have you ever wanted to be able to read and write to your Boot Camp drive?  Maybe you want to give it a custom icon?

Here's the answer: MacFUSE and friends ntfs-3g, MacFusion, and sshfs.

MacFUSE is an implementation of the FUSE userspace filesystem API from Linux, and it allows you to easily build a normal program which implements a filesystem that looks just like a network share or hard drive to the Mac, without having to muck about in kernel land.  The upside for us is that it allows you do things like mounting another computer's files if you can SSH to that computer.

Just install MacFUSE, then either download MacFusion (GUI) or sshfs (command line), and tell it what computer to mount.  If you've got a ssh config file set up, you can just type in the name of your CS machine, and it'll mount.

Here's my command line for mounting on the CS machines:

mkdir /Volumes/sshfs

./sshfs-static-leopard lord-yupa.cs.utexas.edu: /Volumes/sshfs -oauto_cache,volname=sshfs

Now  you can view your CS account's files like they were on your local system!  You can drag and drop or go into command line and do things.  It might be a bit slower than a local filesystem, but still usable.

Be warned, if you try to do things from both ends of the connection (like svn up from the CS machine, and editing a file from the OSX machine) the files may get out of sync.  The auto_cache option helps by clearing the cache of a file if its modified date changes on the far end, so just click on the file in Finder or navigate out and back in to the folder to refresh its contents.

To unmount, just type "umount /Volumes/sshfs" or click the eject button in Finder.

Tips for Mac users

If you're using a Mac to work on the project, it's easy to get cppunit and doxygen installed using Macports: http://www.macports.org/  (Leopard installer)  It's a package manager like apt-get or yum for Linux, but for OS X.  It also keeps all its changes inside the /opt/local directory, so  you don't have to worry about screwing up your OS X install.

(You've already installed the OS X Developer Tools, right?  Because otherwise you don't have any compiler in the first place.)

You just type 'sudo port selfupdate' to get the list of ports, then type 'sudo port install cppunit' and let it chug away.  It'll take a while, because the developers of macports decided that supplying prebuilt binaries would be too much hassle or something, so you'll have to compile all the dependencies.  I suggest downloading Doxygen from the doxygen site instead of building it because it takes a very long time to compile using macports: ftp link However, the GUI isn't terribly helpful, so the command line version might be better.

After it's done, you should be able to type doxygen to use it.  To include cppunit, you should add 

"-I/opt/local/include -L/opt/local/lib" to your g++ command, like so:

g++ -ansi -pedantic -I/opt/local/include -L/opt/local/lib -lcppunit -ldl -Wall -DTEST main.c++ -o main.app

I also omit the .app extension from the output file, because on OS X that's supposed to be an application and the output from g++ isn't.

Or you could just simply ssh to the CS machines.  But I think it's important to understand how to do things on OS X.

Windows users:  if you want a command line that sucks less than command prompt, use a PuTTY session to the CS machines, or if you want to build locally, a mintty set up with Cygwin.

Aside: we should be using googletest, because it's cooler and doesn't require registering every single test.  It even has 'death tests' that check that a test crashes, and non-fatal assertions.

http://code.google.com/p/googletest/

lvalue/rvalue

I've always wondered what lvalue and rvalue really meant - and why they were different from 'left operand' and 'right operand'.  It's probably because I know more Java than C++, and Java has lvalue and rvalue, but doesn't allow you to do silly things like '++++i;'.

Definitions:

rvalue: static, read only value, generally a number.  Example: 2,  (2+2), (i+2), i++. Similar to 'const' in C++.

lvalue: Can be assigned to but also has a value, generally a variable or an expression that returns a variable.  Examples:  i, (++i), (i += 3), etc.

The distinction comes in when  you look at the type of a value in an expression, for example:

a = 2 + 3;

In this example, a is an lvalue, 2 and 3 are rvalues, and the sum 5 is also a (hidden) rvalue.

a = ++i;

Here, a is an lvalue because it's being assigned to, and i is an lvalue because it is a variable, but critically, (++i) is also an lvalue because the operator '++' returns the variable it's operating on after the incrementation operation, rather than just the resulting value.  This allows expressions like ++++i to compile and have meaning, because they're effectively (++(++i)).

This begs the question: what does a = (++i = i) do?  No idea. 

Why is this more important to C++ programmers than C programmers?  C programmers have to deal with this rvalue/lvalue distinction only if they're writing expressions that have multiple assignments in them, which you generally shouldn't do because it's confusing to read and understand.   C++ programmers have the same problems, but they also have to understand the rules when they use an advanced C++ feature called operator overloading.  This allows objects to respond to operators like '++' with behaviors specific to that object.  For example, an iterator could move to the next object in the list when ++ is called.  

However, there's a big difference between the preincrement form '++i' and the postincrement form 'i++'.  Preincrement returns the lvalue variable i after it performs the 'increment' operation, and postincrement returns the lvalue variable i before it performs the operation. When a C++ programmer implements postincrement, they have to copy the object that is being incremented, and return the old version after incrementing the new one.