PDA

View Full Version : Java Multi-Dimensional, Quad-Directional Linked List.



Brandon
01-18-2013, 06:10 AM
Problem: I cannot figure out how to insert Rows of nodes at a specified position..

http://i.imgur.com/qlFK9.png

Imagine inserting to where specified in the picture above..

My node class:


package linkedlist;

public class Node {
public Node Up, Down, Left, Right;
public int Value;

public Node() {
Value = -1;
Up = Down = Left = Right = null;
}
}



The implementation:

package linkedlist;

public class Matrix {
private int Width, Height;
private Node Reference, RowIterator, ColumnIterator;

public Matrix(int Width, int Height) {
Reference = new Node();
this.Width = Width; this.Height = Height;
RowIterator = ColumnIterator = Reference;

for (int I = 0; I < Height; ++I) {
for (int J = 0; J < Width; ++J) {
if (I == 0) {
if (J < Width - 1) {
RowIterator.Right = new Node();
RowIterator.Right.Left = RowIterator;
RowIterator = RowIterator.Right;
}
}
else {
if (J < Width - 1) {
if (J == 0) {
RowIterator.Up = ColumnIterator;
}

RowIterator.Right = new Node();
RowIterator.Up.Down = RowIterator;
RowIterator.Right.Left = RowIterator;
RowIterator.Right.Up = RowIterator.Up.Right;
RowIterator = RowIterator.Right;
}
}
}

if (I < Height - 1) {
ColumnIterator.Down = new Node();
RowIterator = ColumnIterator = ColumnIterator.Down;
}
}
}

public void SetValue(int X, int Y, int Value) {
RowIterator = Reference;

for (int I = 0; I < Y; ++I) {
RowIterator = RowIterator.Down;
}

for (int J = 0; J < X; ++J) {
RowIterator = RowIterator.Right;
}

RowIterator.Value = Value;
}

public int GetValue(int X, int Y) {
RowIterator = Reference;

for (int I = 0; I < Y; ++I) {
RowIterator = RowIterator.Down;
}

for (int J = 0; J < X; ++J) {
RowIterator = RowIterator.Right;
}

return RowIterator.Value;
}

public void InsertRow(int RowIndex) {
RowIterator = ColumnIterator = Reference;
++Height;

for (int I = 0; I < RowIndex; ++I) {
RowIterator = RowIterator.Down;
}

for (int I = 0; I < Width; ++I) {
if (I == 0) {
RowIterator.Up = new Node();
RowIterator.Up.Down = RowIterator;
RowIterator = RowIterator.Right;
}
else {
RowIterator.Up = new Node();
RowIterator.Up.Down = RowIterator;
RowIterator.Up.Left = RowIterator.Left.Up;
RowIterator.Up.Left.Right = RowIterator.Up;
RowIterator = RowIterator.Right;
}
}

if (RowIndex == 0) {
Reference = Reference.Up;
}
}

public int GetWidth() {
return Width;
}

public int GetHeight() {
return Height;
}
}



The usage:

package linkedlist;

public class LinkedList {
public static void main(String[] args) {
Matrix M = new Matrix(6, 6);

int K = 0;

for (int I = 0; I < 6; ++I) {
for (int J = 0; J < 6; ++J) {
M.SetValue(J, I, K++);
}
}

M.InsertRow(1);

for (int I = 0; I < M.GetHeight(); ++I) {
for (int J = 0; J < 6; ++J) {
System.out.print(M.GetValue(J, I) + " ");
}
System.out.println();
}
}
}



How do I insert a row?

Example Result of the above:



00 01 02 03 04 05
06 07 08 09 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35
30 31 32 33 34 35


I'm attempting to insert rows above a specified row.. I got code for row 0 but can't get anything to work for beyond 0..

The Directions:

Each node can hold 4 directions. Up, Down, Left, Right.
Nodes in the corners can only move two directions. (To Their Adjacent Nodes).
Nodes on the Edges can only move three directions. (To Their Adjacent Nodes).
Nodes anywhere else, the center, etc.. can move all directions (To Their Adjacent Nodes).


Any idea on insertion? I got traversal and creation working.. I can get Deleting rows working but not inserting rows :S

Recursive
01-18-2013, 06:45 AM
In main, you put 6 x 6 for matrix dimensions, but the output is 7 x 6. Doesn't that mean it inserted a new row afterall?

superuser
01-18-2013, 10:54 AM
I really don't know how Java works, but this reminds be of old-schoold MCGA screen-modes and setting pixels in it :)

For instance, you could have an array of pointers holding references to nodes. Lets say you have 8x8 matrix. To get a specific node, it's just simple math:


n = y * 8 + x

So, to add a row, just simply insert 8 node-pointers (pseudo):


function InsertRow(row)
begin
remains = nodes from row * 8 to the end
currentnodes = nodes up until row * 8

nodes[] = currentnodes + 8 nodes + remains
end

So, to iterate lets say down, you can do


pos = currentpos + 8

etc.

I may be way off since as I said, I don't know Java, but still :)

Brandon
01-18-2013, 03:55 PM
...


I know what you mean but I can't use arrays for linked list class above.


EDIT.. I slept on it, woke up, ate, solved it..


public void InsertRow(int RowIndex) {
RowIterator = ColumnIterator = Reference;
++Height;

for (int I = 0; I < RowIndex; ++I) {
RowIterator = RowIterator.Down;
if (I < RowIndex - 1) {
ColumnIterator = ColumnIterator.Down;
}
}

for (int I = 0; I < Width; ++I) {
if (I == 0) {
RowIterator.Up = new Node();
RowIterator.Up.Down = RowIterator;
if (RowIndex == 0) {
Reference = Reference.Up;
}
else {
ColumnIterator.Down = RowIterator.Up;
}
RowIterator = RowIterator.Right;
}
else {
RowIterator.Up = new Node();
RowIterator.Up.Down = RowIterator;
RowIterator.Up.Left = RowIterator.Left.Up;
RowIterator.Up.Left.Right = RowIterator.Up;
RowIterator = RowIterator.Right;
}
}
}