I am trying to understand the concept of "position", as it relates to data structures and as it is defined in the book "Data Structures and Algorithms in Java", 2nd. Ed., by Goodrich & Tomassia. For those who don't have access to this textbook, the concept is also explained in an article by same authors at the following link:
http://www.cs.brown.edu/cgc/jdsl/papers/access.pdf I am a little confused and I was wondering if someone could help me out.
Sorry for the long post but I wanted to provide background for those who don't have the textbook.
Reference 1
--------------
According to the textbook, "A position is itself an abstract data type that supports the following simple method:
element():Return the element stored at this position
Input: NoneOutput: Object
Reference 2
---------------
Code fragment 5.3 (p.199) in the textbook shows a class called DNode that realizes a node of a doubly-linked list and implements Position.
class DNode implements Position {
private DNode prev, next;// References to the nodes before and after
private Object element;// Element stored in this position
// Constructor
public DNode(DNode newPrev, DNode newNext, Object elem) {
prev = newPrev;
next = newNext;
element = elem;
}
// Method from interface Position
public Object element() throws InvalidPositionException {
if ((prev == null) && (next == null))
throw new InvalidPositionException("Position is not in a list!");
return element;
}
// get and set methods.....
}
Reference 3
---------------
In Section 5.3.3 (p.209), in section entitled "Implementing a Sequence with an Array", the book defines a soultion where "..we store a new kind of position object in each cell of A, and we store elements in positions. The new position object p holds the index i, and the element e associated with p."
Reference 4
---------------
In section 6.4.1, a section entitled "A Vector-Based Structure for Binary Trees", on page 264, states:
"The level numbering function p suggests a representation of a binary tree T by means of a vector S such that node v of T is associated with the element of S at rank p(v). ........
Such an implementation is simple and efficient, for we can use it to easily perform the methods root, parent, leftChild, ......... by using simple arithmetic operations on the numbers p(v) associated with each node v involved in the operation. That is, each position object v is simply a wrapper for the index p(v) into the vector S."
Reference 5
---------------
In Section 12.2 entitled "Data Structures for Graphs", subsection 12.2.1 entitled "The Edge List Structure", on page 547, it states:
"In this representation, a vertex v of G storing an element o is explicitly represented as a vertex object. All such vertex objects ares tored in a container V, which would typically be a list, vector, or dictionary. If we represent V as a vector, for example, we would automatically think of the vertices as being numbered. ..... Note that the elements of container V are the vertex positions of graph G.
Vertex Objects
The vertex object for a vertex v storing element o has instance variables for:
- A reference to o
- Counters for the numbers of incident undirected edges, incoming directed edges, and outgoing edges
- A reference to the position of the vertex object in container V.
End of references
-----------------
I am tryng to set up
Java classes to implement a graph using a vector implementation of an edge-list data structure.
My first step is to set up a class representing a Vertex. I will ignore the instance variables for edge counters mentioned above to keep it simple. I also want to add an instance variable to give the Vertex a name (e.g., vA, vB, etc.).
So following fromt he textbook (see Ref.5 above) I have set up the following class:
public class Vertex implements Position{
private
String vName;
private Object vCargo;
private Position vPos;
//constructor
public Vertex(String n, Object o, Position p) {
vName = n;
vCargo = o;
vPos = p;
}
//get and set methods go here
//implementation of element() method of Position interface goes here
}
At some point I am going to have to use the constructor to create new vertex objects.
Question 1: What I will be passing to the constructor to represent parameter p ?
Question 2: What exactly should the element() method return? Just vCargo? or an object that includes vName and vCargo? Or an object that includes vname, vCargo and vPos?
I think I understand the concept of Position as it is used in the doubly-linked-list context, where you have to define nodes in relation to previous and next position. But when it comes to a vector context, where you can make direct reference to cells, I feel like I just don't have a full grip of the Position concept.
I would really appreciate if someone could help me, both conceptually and practically as it is applied above.