[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Bug-gnubg] The match and game data structure

From: Øystein Johansen
Subject: [Bug-gnubg] The match and game data structure
Date: Fri, 30 Jun 2006 11:03:54 +0200


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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]