Vector in Vector... Java

Question

I have vector in vector in vector .... . But I don't know how many of them (what the depth is). How can I change the last vector's content?

Answer 1

in response to seth, here's how you'd do it wih a stac. pseudocode, probably replete with typos, just to describe the idea...

note: sufferes from the exact same problem as recursive solutions where backwards links can cause infinite loops. if memory is not an issue, keep a list of all lins ever followed (or maybe a flag in each item to indicate if followed), or use the intersecting loops of incr & skip 1 if memory is a problem. or just set. maximum lomit on the depth you'll traverse.

// breadth first search to find deepest element
FIND_DEEPEST:
GIVEN tree; // vector of vectors
DECLARE current, previous  // stacks for the current depth and one level up
DECLARW node, children, child // temp vars

current = COPY( tree);
WHILE current != NIL
  previous = current;
  current = nil;
  WHILE previous IS NOT empty
    node = POP(previous);    
    APPEND CHILDREN(node) TO current;  // CHILDREN just pops all elements of node
                                        // APPEND operates on lists, like in Perl    

Answer 2

You are going to HAVE to use... wait for it... RECURSION!

Here is an example with a linked list

public Node<E> go_deep(Node<E> nodeRef) {
  // base case
  if(nodeRef.next == NULL)
    return nodeRef;

  return go_deep(nodeRef.next);
}

Then you can get the "last" node by:

public static void main(String[] args) {
  Node<E> lastNode = go_deep(head);
}

Where head is your first item (vector in this case). You may have different methods for next and previous too...

I'm writing this from the top of my head, and you have to define a Node if you really want this to work, its just the basic idea...

If Vector (Node in my example) isn't passed by reference:

// if you have two-way references
public static void main(String[] args) {
  Node<E> lastNode = go_deep(head); //returns the last Node
  Node<E> prevNode = lastNode.prev; //returns the Node before
  Node<E> newNode = new Node<E>();      

  // update newNode with lastNode's values
  newNode.foo = lastNode.foo;
  newNode.bar = lastNode.bar + 7;

  prevNode.next = newNode; //newNode is inserted into the structure - lastNode dies :(
}

If you have one-way references, we modify go_deep to return an array of the node and its parent:

public Node<E>[] go_deep(Node<E> nodeRef) {
  // base case
  // THERE ARE EDGE CASES THAT I'M IGNORING BECAUSE I'M NOT PROGRAMMING FOR YOU!
  if(nodeRef.next.next == NULL) {
    Node<E>[] arr = new Node<E>[2];
    arr[0] = nodeRef; // the "prev" node
    arr[1] = nodeRef.next; // the "last" node
    return arr;
  }

  return go_deep(nodeRef.next);
}

then in main:

public static void main(String[] args) {
  Node<E>[] nodes = go_deep(head); //returns the array of nodes
  Node<E> lastNode = nodes[1]; // returns the last Node
  Node<E> prevNode = nodes[0]; //returns the Node before
  Node<E> newNode = new Node<E>();      

  // update newNode with lastNode's values
  newNode.foo = lastNode.foo;
  newNode.bar = lastNode.bar + 7;

  prevNode.next = newNode; //newNode is inserted into the structure - lastNode dies :(
}