Re: [Bug-gnubg] The match and game data structure

[Jonathan Kinsey]

Øystein Johansen wrote:
> Hi,
> 
> I have a bad feeling that our data structure for storing matches, games and 
> moverecords are not the best. I'm sometimes affraid it really sucks. I also 
> believe there is a releation between the end product quality and the internal 
> code quality, and I believe these data strutures, might be the Achilles heel 
> in our project.
> 
> Of course I would love to improve this, however I do not want to code 
> anything before I'm sure it's an improvement. I therefore hope that a small 
> discussion about this issue can help us design a better data structure for 
> holding the match data.
> 
> Todays system is simple. (I don't mind things beeing simple, I believe simple 
> is yet beautiful and functional. I'm an advocate of KISS principles). The 
> match is a global linked list of all games. It uses the linked list 
> implementation in the lib directory, which is actually a circular linked 
> list. Each game is a new linked list of moverecords.
> 
> The good thing about this circular list is that appending new elements 
> (moverecords) is a O(1) operation. However, the good things stop there. 
> Looping through a list is a bit cumbersome. It's hard to keep track of a 
> current move and a current game. (We actually have global pointers for this.) 
> This data structure has shown to be bad for working with positions, since it 
> depends on a global list (lMatch).
> 
> Short: I believe it's time for a redesign of the match holding data structure.
> 
> Any suggestions? What's the best redesign. Simply a double linked list (not 
> circular). Do we need match head and game head, to keep track of the size, 
> current move and state etc.? I'm willing to start implementing a better 
> structure if we agree on what we need.

Perhaps I've coded too much C++...  I think a better exercise is to
separate the logic from the data and think more in terms of
modules/interfaces and let this drive the data structures.

In practice this would mean calling functions to work with matches and
games rather than using globals/structs throughout the code.

As an example look at this code from show.c:

for( pl = lMatch.plNext; pl != &lMatch; pl = pl->plNext, ++n )
{
      pmr = (moverecord *) ( (list *) pl->p )->plNext->p;
      pmgi = &pmr->g;
      assert( pmr->mt == MOVE_GAMEINFO );
        ...

It's pretty hard to work out what the code in this example does, which
kind of says something...
Anyway it could look something like:

for (i = 1; i < getNumGames(); i++)
{
      game *g = getGame(i);
      pmgi = getGameInfo(g);
        ...

Jon

signature.asc
Description: OpenPGP digital signature