0

Hey guys I'm having trouble figuring this out. Here is the code:

  package apps;

import java.util.Iterator;
import java.util.NoSuchElementException;

import structures.Vertex;


public class PartialTreeList implements Iterable<PartialTree> {

    /**
     * Inner class - to build the partial tree circular linked list 
     * 
     */
    public static class Node {
        /**
         * Partial tree
         */
        public PartialTree tree;

        /**
         * Next node in linked list
         */
        public Node next;

        /**
         * Initializes this node by setting the tree part to the given tree,
         * and setting next part to null
         * 
         * @param tree Partial tree
         */
        public Node(PartialTree tree) {
            this.tree = tree;
            next = null;
        }
    }

    /**
     * Pointer to last node of the circular linked list
     */
    private Node rear;

    /**
     * Number of nodes in the CLL
     */
    private int size;

    /**
     * Initializes this list to empty
     */
    public PartialTreeList() {
        rear = null;
        size = 0;
    }

    /**
     * Adds a new tree to the end of the list
     * 
     * @param tree Tree to be added to the end of the list
     */
    public void append(PartialTree tree) {
        Node ptr = new Node(tree);
        if (rear == null) {
            ptr.next = ptr;
        } else {
            ptr.next = rear.next;
            rear.next = ptr;
        }
        rear = ptr;
        size++;
    }

    /**
     * Removes the tree that is at the front of the list.
     * 
     * @return The tree that is removed from the front
     * @throws NoSuchElementException If the list is empty
     */
    public PartialTree remove() 
    throws NoSuchElementException {

            Node temp = new Node(Node.tree);
            return null;
    }

    /**
     * Removes the tree in this list that contains a given vertex.
     * 
     * @param vertex Vertex whose tree is to be removed
     * @return The tree that is removed
     * @throws NoSuchElementException If there is no matching tree
     */
    public PartialTree removeTreeContaining(Vertex vertex) 
    throws NoSuchElementException {
            /* COMPLETE THIS METHOD */

            return null;
     }

    /**
     * Gives the number of trees in this list
     * 
     * @return Number of trees
     */
    public int size() {
        return size;
    }

    /**
     * Returns an Iterator that can be used to step through the trees in this list.
     * The iterator does NOT support remove.
     * 
     * @return Iterator for this list
     */
    public Iterator<PartialTree> iterator() {
        return new PartialTreeListIterator(this);
    }

    private class PartialTreeListIterator implements Iterator<PartialTree> {

        private PartialTreeList.Node ptr;
        private int rest;

        public PartialTreeListIterator(PartialTreeList target) {
            rest = target.size;
            ptr = rest > 0 ? target.rear.next : null;
        }

        public PartialTree next() 
        throws NoSuchElementException {
            if (rest <= 0) {
                throw new NoSuchElementException();
            }
            PartialTree ret = ptr.tree;
            ptr = ptr.next;
            rest--;
            return ret;
        }

        public boolean hasNext() {
            return rest != 0;
        }

        public void remove() 
        throws UnsupportedOperationException {
            throw new UnsupportedOperationException();
        }

    }
}

I'm having trouble on writing the remove() method. I know all I need to do is set tree to tree.next and return what I removed from the linked list, but for the life of my I can't figure out how to access the tree when I don't have a parameter.

I get an error on the Node temp = new Node(Node.tree); line.

PM 77-1
  • 12,933
  • 21
  • 68
  • 111
Laugh7
  • 167
  • 2
  • 2
  • 16
  • 2
    `tree` is not `static ` in `Node`. `Node.tree` cannot possibly work. – Boris the Spider Dec 04 '15 at 20:20
  • 1
    make new instance of `Node` using same `tree` object which is already in `Node` class?! what are you trying to do? – Yazan Dec 04 '15 at 20:24
  • What is the relationship between `Node` and `PartialTree`? You don't show us what a `PartialTree` is. – Erick G. Hagstrom Dec 04 '15 at 20:25
  • What you want is basically `Node temp=rear.next; if (temp==rear) rear=null else rear.next=temp.next; size--; return temp;` - this is not really a dupe IMHO, because the answers to the general question don't really help much here – CupawnTae Dec 04 '15 at 20:28
  • To explain, you need the head of the list and you have a reference to the rear. Because it's a circular linked list (like a snake biting its own tail), `rear.next` is pointing back to the head of the list, which is the one you want to remove. So you extract that one, join up the new ends of the list, and return what you extracted. – CupawnTae Dec 04 '15 at 20:35
  • Thanks Cupawn, that makes sense. So just to clarify, there is NO other way I can reach the front of the tree? edit: this doesn't work because it is trying to return a Node object but the return calls for a PartialTree – Laugh7 Dec 04 '15 at 20:41
  • As it stands, no. You *could* add another instance variable (similar to `rear`) to keep a reference to the front, but there's really no need since `rear.next` will always get you there, and if I were scoring the exercise, I'd prefer the solution I suggested to one that introduced a redundant variable. – CupawnTae Dec 04 '15 at 20:49
  • @Laugh7 sorry, `return temp.tree;` - btw, use `@CupawnTae` in a comment if you want it to notify me. Otherwise I may never know you replied – CupawnTae Dec 04 '15 at 20:50

0 Answers0