PartialTreeList.java

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 {
    		
    		/* COMPLETE THIS METHOD */
    	if(size <= 0){
    		throw new NoSuchElementException();
    	}
    		
    		if(size != 1){
    			Node firstNode = rear.next;
    			rear.next = firstNode.next;
    			size--;
    			firstNode.next = null;
    			return firstNode.tree;
    			
    		} else {
    			Node retNode = rear;
    			rear = null;
    			size = 0;
    			retNode.next = null;
    			return retNode.tree;
    		}
   
    }

    /**
     * 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 */
    	PartialTree ptRemove = null;
    	
    	if(rear == null){
    		throw new NoSuchElementException();
    	}
    	
    	if (rear.next == rear){
    		if(rear.tree.getRoot().name.equals(vertex.getRoot().name)){
    			PartialTree returnedTree = rear.tree;
    			rear = null;
    			size --;
    			return returnedTree;
    		} else {
    			throw new NoSuchElementException();
    		}
    	}
    	
    	Node pt = rear.next;
    	Node prev = rear;
    	PartialTree treeLL = null;
    	
    	/* if(vertexFound){
    			ptRemove = tmptree;
    			removeNode(tmp);
    			break;
    		}
    		
    		tmp = tmp.next;
    		
    	} while (tmp != rear);
    	
    	if (ptRemove == null){
    		return null;
    		
    	} else {
    		return ptRemove;
    	}
    	
     } */
    	
    	do {
    		Vertex tmp = pt.tree.getRoot();
    		Vertex check = vertex.getRoot();
    		
    		
    		if(tmp.name.equals(check.name)){
    			treeLL = pt.tree;
    			
    			if(pt == rear){
    				rear = prev;
    			}
    			
    			prev.next = pt.next;
    			size--;
    			return treeLL;
    		}
    		
    		prev = pt;
    		pt = pt.next;
    		
    	} while(pt != rear.next);
    	
    	throw new NoSuchElementException();
    }
    		
    	/*	boolean vertexFound = vertexCheck(tmptree, vertex);
  
    
    private boolean vertexCheck(PartialTree partialTree, Vertex vertex){
    	Vertex pTree = vertex;
    	while(pTree.parent != pTree){
    		pTree = pTree.parent;
    	}
    	
    	return pTree == partialTree.getRoot();
    }
    
     */
    
    /**
     * 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();
    	}
    	
    }
}