[Bug-gnubg] The match and game data structure

[Øystein Johansen]

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.

-Øystein