package vnt;
/**
 * Node_LinkedList.java - v1.0
 * Began: July 11, 2005
 * Last Updated: July 21, 2005 
 * 
 * Copyright (C) 2005 - Michael D. Miller - mdm162@truman.edu
 * Truman State University
 * 100 E. Normal
 * Kirksville, MO - 63501
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */


/**
 * <p>A standard doubly-linked list. Generally used by the Node 
 * structure primarily to store and manipulate information for 
 * the adjacency lists.</p>
 * 
 * <p>The goal for this class is for the adjacency list to 
 * behave like a set:</p>
 * <ul>
 * <li>no duplicate items</li>
 * <li>order doesn't matter</li>
 * <li>easy unions</li>
 * </ul>
 *  
 * <p>Note: This class is used heavily by the Node_Analysis
 * plug-in, which is still very recent and needs significant
 * testing. As a result, this class has a large number of print
 * statements for debugging purposes.</p> 

 * @author Michael Miller - Truman State University
 * @version 1.0
 * @since 1.0
 */
class Node_LinkedList {
    private Node_LinkedList before;
    private Node_LinkedList after;
    private Node myNode;
    
    /**
     * Simple constructor. No adjacencies by default.
     * <p>Pre: None.
     * <br />Post: This node exists. It has an origin (itself) and no adjacencies.
     * @param creator The node with which this adjacency list this is associated. 
     */
    public Node_LinkedList (Node creator) {
        before = null;
        after = null;
        myNode = creator;
    }

    /**
     * Constructor. Will also link the nodes given. 
     * <p>Pre: None.
     * <br />Post: This node exists. It has an origin (itself) and possibly connections. These connections can lead to any number of adjacencies. 
     * @param bef The Node before. Its after parameter will change to this. Can be null.
     * @param aft The Node after. Its before parameter will change to this. Can be null.
     */
    public Node_LinkedList (Node creator, Node_LinkedList bef, Node_LinkedList aft) {
        myNode = creator;
        if (bef != null)
            bef.setAfter(this);
        if (aft != null)
            aft.setBefore(this);
        before = bef;
        after = aft;
    }
    
    /**
     * Attempts to insert the node insertMe. If no duplicates are
     * found, then the insertion is performed.
     *
     * <p>Pre: Assumes insertMe is a valid node to search for.
     * <br />Post:  Either adds the node if it is new, or does not if it was found in the adjacency list.
     * @param insertMe The node to attempt to insert.
     * @return Returns true if the node was added successfully. Otherwise false if the node already existed in the list.
     */
    public boolean listInsert (Node insertMe) {
        if (insertMe == null) {
            return false;
        }
        // search to make sure no duplicate node is inserted
        if (isAdjacent(insertMe)) {
            // the node was found, abort the insert
            return false;
        }
        // still here, add the node
        this.addBefore(insertMe);
        return true;
    }

    /**
     * Unions a given linked list into this linked list.
     * Elements of the union are node adjacencies.
     * 
     * <p>Pre: Requires that the given Node_LinkedList exists.
     * <br />Post: All connections in the given Node_LinkedList that are not in this list are added to this list. Symmetry depends on the second parameter. 
     * @param unionMe The list to be merged onto this one.
     * @param preserveSymmetry If true, the symmetric connections will also be added. If false, the only changes will be to this linked list.
     * @return The number of new nodes added to this list. Duplicates do not count.
     */ 
    public int listUnion (Node_LinkedList unionMe, boolean preserveSymmetry) {
        if (unionMe == null) {
            return 0;
        }
        int count = 0;
        Node_LinkedList search = unionMe;
        Node target;
        // get the "first" element
        while (search.getBefore() != null)
            search = search.getBefore();
        // traverse through each element and add elements this list doesn't have
        while (search != null) {
            // add all new nodes and keep track of how many
            // either preserve symmetry or only change locally
            if (preserveSymmetry) {
                if ((search.getNode()).addAdjacency(myNode))
                    count++;
            } else {
                // add all new nodes and keep track of how many
                if (listInsert(search.getNode()))
                    count++;
            }
            search = search.getAfter();
        }
        // return the number of nodes that were successfully added
        return count;
    }

    /**
     * Searches the adjacency list for the target node.
     * If it is found, the links around it are deleted and 
     * Java's natural garbage collection deletes it. 
     * 
     * <p>Pre: Assumes that the given node exists.
     * <br />Post: If the given node was found in this adjacency list, removes it. Symmetry is not preserved by this method alone. Otherwise, no change is made.
     * @param deleteMe The node to search for to delete. 
     * @return Returns true if the node was found (and consequently deleted), otherwise false.
     */
    public boolean listDeleteItem (Node deleteMe) {
        if (deleteMe == null) {
            return false;
        }
        // search to make sure no duplicate node is inserted
        Node_LinkedList target = findAdjacent(deleteMe) ;

        if (target == null) {
            // the node was not found, abort the insert
            return false;
        }
        // still here, delete the node from the adjacency list
        target.deleteMe();
        return true;
    }
    
    /**
     * Iteratively deletes the entire linked list.
     *
     * <p>Pre:  Assumes the connections are well formed (no broken links, no endless loops, etc). 
     * <br />Post: Deletes all connections to this node's adjacency. Symmetry preservation is determined by the second parameter.
     * @param preserveSymmetry If true, the symmetric connections will also be added. If false, the only changes will be to this linked list.
     * @return Returns the number of nodes that were deleted.
     */
    public int listDissolve (boolean preserveSymmetry) {
        int count = 0;
        Node_LinkedList search = this;
        Node_LinkedList target;
        // get the "first" element
        while (search.getBefore() != null)
            search = search.getBefore();
        // traverse through each element and add elements this list doesn't have
        while (search != null) {
            target = search;
            search = search.getAfter();
            // delete the node
            // either preserve symmetry or only change locally
            if (target == this) {
                break;
            }
            if (preserveSymmetry) {
                if ((target.getNode()).removeAdjacency(this.getNode())) {
                    count++;
                }
            } else {
                target.deleteMe();
                count++;
            }
        }
        // return the number of nodes that were successfully deleted
        return count;
    }

    /**
     * Searches [preorder] this, before (iteratively), and after (iteratively) for the
     * given node.
     *  
     * <p>Pre: Requires that the given node exists. Assumes all connections are well formed.
     * <br />Post: Returns true or false if the given node compareNode()'d to one of the nodes in this adjacency list.  
     * @param findMe The node's coordinate data to search for.
     * @return Returns true if compareNode(findMe) is true for this or any connected adjacency list item. Otherwise returns false if it was not found. 
     */
    public boolean isAdjacent (Node findMe) {
        if (findMe == null) {
            return false;
        }
        // check this node first
        if (this.compareNode(findMe))
            return true; // duplicate found, quit
        // check all nodes before this node
        Node_LinkedList search = before;
        while (search != null) {
            if (search.compareNode(findMe))
                return true; // duplicate found, quit
            search = search.getBefore();
        }
        // if still here, check all nodes after this one
        search = after;
        while (search != null) {
            if (search.compareNode(findMe))
                return true; // duplicate found, quit
            search = search.getAfter();
        }
        return false;
    }

    /**
     * Searches [preorder] this, before (iteratively), and after (iteratively) for the
     * given node.
     *  
     * <p>Pre: Requires that the given node exists. Assumes all connections are well formed.
     * <br />Post: Returns the LinkedList associated with the given node in this particularly adjacency list if it compareNode()'d to one of the nodes in this adjacency list.  
     * @param findMe The node's coordinate data to search for.
     * @return Returns the linked list pointer if findMe matches it. Otherwise returns null. 
     */
    public Node_LinkedList findAdjacent (Node findMe) {
        if (findMe == null) {
            return null;
        }
        // check this node first
        if (this.compareNode(findMe))
            return this; // duplicate found, quit
        // check all nodes before this node
        Node_LinkedList search = before;
        while (search != null) {
            if (search.compareNode(findMe))
                return search; // duplicate found, quit
            search = search.getBefore();
        }
        // if still here, check all nodes after this one
        search = after;
        while (search != null) {
            if (search.compareNode(findMe))
                return search; // duplicate found, quit
            search = search.getAfter();
        }
        return null;
    }
    
    /**
     * Removes this node from the list. Cleans up connections
     * with before and after (keeps them linked if they exist).
     * 
     * <p>Pre: This adjacency node exists and may or may not have connections to other adjacency list elements.
     * <br />Post: This particular adjacency node is removed from it's neigboring connections. If before or after existed, their connections are updated to maintain proper connectivity.
     */
    public void deleteMe() {
        if (before != null)
            before.setAfter(after);
        if (after != null)
            after.setBefore(before);
        
        before = null;
        after = null;
    }
    
    /**
     * Accessor to the node variable.
     * <p>Pre: This node adjacency exists.
     * <br />Post: No changes.
     * @return Returns the node associated with this adjacency list.
     */
    public Node getNode() {
        return myNode;  
    }
    
    /**
     * Compares a given node's X and Y coordinates to this node.
     * 
     * <p>Pre: This node adjacency exists. Assumes compare exists.
     * <br />Post: No changes.
     * @param compare The node to compare to this node.
     * @return Returns true if the compare node's x and y matches this node. Returns false otherwise.
     */
    public boolean compareNode(Node compare) {
        if (compare == null) {
            return false;
        }
        if ((myNode.getX() == compare.getX()) && (myNode.getY() == compare.getY())) {
            return true;
        }
        return false;
    }
    
    /**
     * Inserts a Node into the list before the current node.
     * Note: There is no addAfter() intentionally.
     * Since adjacency list information is to be treated like a set,
     * order has no meaning and therefore there is no reason to
     * specify adding before or after the present node.
     * (In the future, an index could be assigned for speeded searching,
     * however this is trivial due to the small size of these adjacency lists.
     * The typical adjacency list for a vascular network will not exceed
     * three connections.)
     * 
     * <p>Pre: This node adjacency exists.
     * <br />Post: A new node adjacency is added
     * @param insertMe The node to be inserted.
     */
    public void addBefore (Node insertMe) {
        Node_LinkedList target = new Node_LinkedList (insertMe, before, this);
    }

    /**
     * Simple mutator to before variable.
     * <p>Pre: This node adjacency exists.
     * <br />Post: No change.
     * @param target What the before variable will be changed to.
     */
    public void setBefore (Node_LinkedList target) {
        before = target;
    }

    /**
     * Simple Mutator to after variable. 
     * <p>Pre: This node adjacency exists.
     * <br />Post: No change.
     * @param target What the after variable will be changed to.
     */
    public void setAfter (Node_LinkedList target) {
        after = target;
    }

    /**
     * Accessor to the linked node before this one.
     * 
     * <p>Pre: This node adjacency exists.
     * <br />Post: No change.
     * @return The linked node in the list before this one. Can be null.
     */
    public Node_LinkedList getBefore () {
        return before;
    }

    /**
     * Accessor to the linked node after this one.
     * 
     * <p>Pre: This node adjacency exists.
     * <br />Post: No change.
     * @return The linked node in the list after this one. Can be null.
     */
    public Node_LinkedList getAfter () {
        return after;
    }
}