where the data should go( big problem)

[Jigar Gosar]

Yellow,
Imagine two object Chessboard and ChessPiece.
Question:where the data as to "which square(i,j) on chessboard contains which chesspiece", should go?
confused read ahead.
Should chessboard should contain two dimentional array of chesspiece references
(i.e ChessPiece arr[][]=new ChessPiece[8][8]
or should each chess piece should have an x and y variable so as to indicate where it is currently placed on chessboard.
Now,having made my problem clear using an example of chessboard,the actual problem contains very big chessboard like object of 1000x1000 squares and there are many chesspiece like objects eg.10000 on this imaginary chess board.
Possiblity 1 nly chessboard has two dimentional array and stores reference to chesspiece in it and null value if there is no chesspiece present on that particular chess square(ie. arr[i][j]).
Arguments:
1.disadvantage:A lot of space will be wasted since there will be many null values.
2.advantage:we will be immediately able to query that which chesspiece is on any(i,j) chess square.
3.disadvantage:it will be very difficult and time consuming process to query that given a chesspiece object, where it lies on chess board.We will have iterate all chess squares inquring wheather that i,j square contains the given chesspiece.
4.advantage: no two piece can be on given chesssquare since we are not maintaining this info in chesspiece's variable x,y.

Possiblity 2 nly each chesspiece contains the info as to where it belongs on chessboard. this info is maintained in its private variable "int x,y".
Argument:
1.disadvantage:it is possible that two chesspiece might ,by mistake, contain same x,y values this leads to inconsistancy since no two chesspiece can be on same chess square.
2.advantage:we can easily query each chess piece so as to find which chess square it is currently occuping(since that info is stored in its internal x,y var).
3.disadvantage:in order to find which chesspiece is present on given i,j square we will have to query all chesspiece and ask them wheather they are currently belonging to i,j square this is time consuming since there are 10000 chesspiece in this imaginary chess board.
4.advantage: space is saved since we now only maintain 10000 x,y varibles and not 1000x1000 references to chesspiece.
Possiblity 3: we maintain both array of 1000x1000 references in chessboard and int x,y variable in each chesspiece.
Argument:
1.advantage:now we can quickly query chess square as to which piece it contains and also quickly query chesspiece as to which chess square it belongs on the chessboard.
2.DISADVANTAGE: this is a big disadvantage large amount of memory space is required and there is redundant information maintained in chesspiece object(10000 x "int x,y") and in chessboard object(arr[1000][1000]).this redudancy also leads to inconsistancy.
Now can u help me in any way to avoid the disadvantage and achive the advantage of Possiblity 3.
This is a very big problem for me please help.
Can i maintain such info in a collection and gain advantage of possiblity 3 and avoid its disadvantage.Please be spesific as to how.
Any and all suggessions will be appreciated.

[smita raval]

I don't know if it will be helpful to you or not, but what I think a possibility something like taking reverse approach...
* Take two HashMaps
* In one hashmap, you store key as your element,
like your chessboard example, "white king",
as value of it, store it's x value.
* In another Hashmap, use the same key
value "white king".As value of it, store it's
y value.
* This way, you store only those values which is
not null. i.e. saving memory(I don't know if
you have to store null value or not, you
can't store it because it will not be unique).
* You can find chesspiece position or x/y by
accessing two Hashmaps.
Hope this may help you.
smita
[ September 23, 2002: Message edited by: smita raval ]
[ September 23, 2002: Message edited by: smita raval ]

[Vin Kris]

class ChessSquare {
int X ;
int Y ;
int getX() { return X; }
int getY() { return Y; }
ChessBoard(int x, int Y) { this.X=x; this.Y=y; }
String key() { 
// return X conact Y in String form
// for ex: [32,345] => key = "00320345" if your chess board is 10000 * 10000
}
class ChessPiece {
String name;
ChessPiece(String name) { this.name = name; }
String position() { return key(); }
int getX() { return X; }
int getY() { return Y; }
}
}
class ChessBoard {
static Map chessMap = new HashMap();
public static void main(String [] args) {
int X=0, Y=0;
ChessSquare.ChessPiece newPiece = new ChessSquare(X,Y).new ChessPiece("Rooke");
chessMap.put( newPiece.key(), newPiece );
}
}

Jigar, I hope the above example solves your problem. It is nearly what you want - It atleast doesn't have any of the disadvantages but has the advantages that you have listed. Also, you don't even have to store all elements. Only the elements that occupy a position on your chess board.
You could replace the HashMap with TreeMap at the cost of a little performance. HashMap itself should be costlier than an ArrayList - so you could do some profiling and decide.
Advantages - Memory
Disadvantages - (1) More time in accessing a HashMap
(2) Having to create ChessSquare object (costly operation) for a ChessPiece - so you'd have to handle the code to move your pieces around your board.
I haven't even compiled the above code, so please be liberal if there are any syntax errors.
Am i too late? Have you already designed your board? I'd love to find out how you solved it.

[Jigar Gosar]

thanks ,
to smita (why i like that name)
using the approach u suggested i can find the x,y position for a given piece "white king" but given x and y cordinated how can i find which piece(if any) is occuping the square.
(possiblity 2 disadv 1 & 3 remain.)
the problem i am trying to solve is that given x,y i should be able to find which piece is at that position AND given a chess piece i should be able to find at which x,y cordinate is it present. and i dont want to maintain any redudant information ;.

to Vin Kris
your suggestion is very different and appealing.
but there are many problems implementing it.
and the problem i am trying to address is not only with chess board.
now,
in the problem there are many chess squares which donot have any chess piece. so we will be wasting a lot of space by creating that many chess pieces.
will u be kind enough to tell me how will i maintain blank squares.
to give u a better idea, imagine, i alredy have 1000x1000 array which stores objects of type ChessSquare. if i want to access chess square at loc [32,345] i simply write the code
ChessSquare csq=arr[32][345];
now i simply add or remove a ChessPiece to csq on mouse clicks.
but the info i require is that given a chesspiece to which chess square it belongs.

may be i really dont get your solution,explain it to me in detail by creating a 3x3 chessboard with 3 ChessPieces on it and how to move them from one chess square to another.

btw. how do u become a ranch hand from green horn
[ October 08, 2002: Message edited by: Jigar Gosarr ]

[Ilja Preuss]

Originally posted by Jigar Gosarr:
Possiblity 1 nly chessboard has two dimentional array and stores reference to chesspiece in it and null value if there is no chesspiece present on that particular chess square(ie. arr[i][j]).
Arguments:
1.disadvantage:A lot of space will be wasted since there will be many null values.

How much memory will it take exactly? How much memory do you have at your disposal?

3.disadvantage:it will be very difficult and time consuming process to query that given a chesspiece object, where it lies on chess board.We will have iterate all chess squares inquring wheather that i,j square contains the given chesspiece.

Seems to be a very simple algorithm to me, and might even be fast enough. How fast does it have to be?
I would analyse the constraints very carefully before dismissing this simple solution!

Possiblity 2 nly each chesspiece contains the info as to where it belongs on chessboard. this info is maintained in its private variable "int x,y".
Argument:
1.disadvantage:it is possible that two chesspiece might ,by mistake, contain same x,y values this leads to inconsistancy since no two chesspiece can be on same chess square.

You could of course take care of this by some other means (like comparing the new position of one piece to the positions of all others).

3.disadvantage:in order to find which chesspiece is present on given i,j square we will have to query all chesspiece and ask them wheather they are currently belonging to i,j square this is time consuming since there are 10000 chesspiece in this imaginary chess board.

Again, I think this should be rather fast.
BTW, what needs to be faster: checking the position of a piece or looking up what piece is standing at a specific location?

[Vin Kris]

Jigar, When you say you already have a 1000 * 1000 array of ChessSquare objects - you are assuming the dis-advantage 1 of Possibilty-1 in your post.
Like Ilja Preuss says, the operations should be fast enough - unless your requirement mandates that the search operation is executed repeatedly for many pieces. It would be helpful if you could give the requirements briefly - what you are trying to achieve.
neways, using the inner class approach, the empty locations need not be maintained.
I have tried to code a sample program that demostrates moving the pieces.

class ChessSquare {
int xPos;
int yPos;
Integer key ;
 
public int getXPos() { return xPos; }
public int getYPos() { return yPos; }
 
public ChessSquare(int X, int Y) throws Exception { 
key = new Integer( X * ChessBoard.KEYGEN + Y ) ;
if( ChessBoard.occupied(key) ) throw new PositionOccupiedException(key);
this.xPos = X; this.yPos = Y; 
}
 
public Integer key() { return key; }
 
class ChessPiece {
String name;
ChessPiece(String name) { this.name = name; }
public String position() { return key; }
public String name() { return name; }
 
public void moveTo(int X, int Y) {
Integer newPos = X * ChessBoard.KEYGEN + Y;
ChessBoard.occupy(this, newPos);
xPos = X; yPos = Y;
key = newPos;
}
}
}
 
class ChessBoard {
// The chess board
private static HashMap board = new HashMap();
 
// A single instance of this board
private static ChessBoard chessBoard = null;
 
public static int ROWS ;
public static int COLS ;
 
// value used to generate the HashMap keys
// for ex: Pos [32][3] => Key = 32 * 100 + 3 = 3203. Given key = 3203 => X = 3203/100 & Y = 3203 % 100.
public static int KEYGEN ;
 
private ChessBoard(int rows, int cols) { 
ROWS = rows; COLS = cols; 
KEYGEN = Math.pow( 10, new String(rows).length() );
}
 
static ChessBoard create(int size) {
if( chessBoard == null ) {
chessBoard = new ChessBoard(size,size);
}
return chessBoard;
}
 
static void occupy(ChessSquare.ChessPiece piece, Integer postion) throws Exception {
if( board.containsKey(position) ) throw new PositionOccupiedException(position);
board.remove( piece.key() );
board.put( newPos, piece );
}
 
static boolean occupied(Integer pos) {
return board.containsKey(pos) ;
}
 
static ChessSquare.ChessPiece lookAt(Integer position) { return (ChessSquare.ChessPiece)board.get(position); }
}
 
public class Game {
public static void main(String [] args) {
ChessBoard.create(8); // create a chess board of size 8 * 8 => KEYGEN = 10.
 
try {
ChessSquare.ChessPiece wKPawn = new ChessSquare(6,3).new ChessPiece("White King Pawn");
ChessSquare.ChessPiece bQPawn = new ChessSquare(0,4).new ChessPiece("Black Queen Pawn");
 
wKPawn.moveTo(4,3);
bQPawn.moveTo(3,4);
 
wKPawn.moveTo(3,4); // throws Exception
 
} catch (PositionOccupiedException e) {
ChessSquare.ChessPiece piece = ChessBoard.lookAt(e.getPosition());
if( piece.name().startsWith("Black") ) {
// kill
}
}
}
}

The above code, doesn't maintain the information about the empty locations. If you anyway need to maintain them (a primitive int[][] array I suppose), then the solution would be closer to your possibilty 3 and not with all the dis-advantages.
[ October 08, 2002: Message edited by: Vin Kris ]