ujh/iomrascalai — pull request #4 by TisButMe (2014-05-15 13:31:21+00:00)
Title: Implement chains

Here is a first PR to handle chains. A lot of stuff has been changed/reworked, so here is a list of most of the changes, and a rational.

### New things
* Added a Coord struct. It contains a col/row pair. Coord is now used in Chain to store references to Stones via their coordinates.
* Renamed Point to Stone, to reflect the fact that it also stores its colour, and the id of its chain, and to differentiate it better from Coord.
* Stones now store a chain_id, which is the index of the chain containing that stone in the chains Vec contained by the board.
* Chain now contains a Vec which stores the coordinates of the Stones inside that chain.
* board.play() now correctly handles chains, creating a new one if the stone added is isolated, or adding it to previous chains if not. It will correctly merge chains that have been "bridged" by the new move.
* Executing the program will now let you play by entering successive coordinates. It displays the board and the known chains after every move.

##### Rationale for this architecture:
-> My first idea was to use "simple" &pointers to the corresponding structures, but of course this failed because of circular references between Stone and Chain, and the compiler can't figure out a lifetime.
-> I then went on to try to use RefCell/Cells, but they do not help with circular references.
-> I then tried to use Rc/Weak, which is (according to the Rust masters in Rust's IRC chan) the usual way of doing this, but they don't easily/safely allow for mutations. As the main idea was to be able to access Stone through Chains to change them (for example to Empty if the chain is captured), I thought keeping the option of mutability was important.
-> I didn't really want to consider unsafe pointers at this stage (maybe later in optimisation).
-> Because of all these constraints, I ended up with the current iteration, which works (although I didn't write unit tests yet, you can test it out on the command line), but is probably inefficient. It also doesn't allow for method such as chain.stones() or stone.get_chain(), you have to go through the board.
-> Note: Coords are very small (16 bits), which makes them more memory efficient than pointers (32 to 64 bits depending on the arch). This adds the limits of a 256*256 board size (which I think is reasonable). I don't know if that's interesting/useful or not, but given that the current plan is to have whole trees of board states, now using too much memory probably is a good thing.

### To do:
* Liberties counting. Current status: none at all, although I don't see any major difficulty with this one, you would just add liberties when merging a stone into a chain or a chain into a chain.
* Captures/suicide: After liberty counting works.

### RFC:
* All the get() methods I implemented return an Option. That's good because it enforces checking and prevents failures, but it also lead to A LOT of unwrap() use in cases we know the coordinates/index is good (have a look at the code to be convinced). I'm not sure it's actually worth using Option this low in the implementation, maybe using a pattern like
```
if board.is_ok(col, row) {
board.get(col, row)
}
```
with get failing on invalid col/row would be better in the long run.