/* FamilyForest.java
**
** An instance of this class represents a forest of family trees 
** (i.e., a collection of one or more such trees).  Each node is 
** identified by a natural number.
**
** Authors: R. McCloskey and < STUDENTS' NAMES >
** Known Defects: ...
*/

public class FamilyForest {

   // class constant
   // --------------

   private static final int DEFAULT_NUM_NODES = 100;


   // instance variable
   // -----------------
   private int[] parent;    // parent[i] == j means that j is i's parent 
                            // parent[i] == -1 if i has no parent


   // constructors
   // ------------

   /* Initializes this forest to have the default number of nodes, 
   ** each of which (initially) has no parent. 
   */
   public FamilyForest() { this(DEFAULT_NUM_NODES); }

   /* Initializes this forest to have the specified number of nodes, 
   ** each of which (initially) has no parent.
   */
   public FamilyForest(int numNodes) { 
      parent = new int[numNodes];
      for (int i=0; i != numNodes; i++) {
         parent[i] = -1;       // Initially, no node has a parent
      }
   }


   // observers
   // ---------

   /* Returns the number of nodes in this forest of trees.
   */
   public int numberOfNodes() { return parent.length; }


   /* Returns the ID of the d-ancestor of node k (or -1 if such an
   ** ancestor does not exist). 
   ** Definition:  The 0-ancestor of k is k itself.
   **    For d > 0, the d-ancestor of k is the parent of the (d-1)-ancestor
   **    of k, or, equivalently, the (d-1)-ancestor of the parent of k.
   ** pre: d >= 0  &&  0 <= k < numberOfNodes()
   */
   public int ancestorOf(int k, int d) {
      // loop invariant: k is the (D-d)-ancestor of K, where K and D refer 
      //    to the initial values of k and d, respectively
      while (k != -1  &&  d != 0) {
         k = parentOf(k);
         d = d-1;
      }
      return k;
   }
   
   /* Returns the ID of the parent of node k, or -1 if k has no parent.
   */
   public int parentOf(int k) { return parent[k]; }

   /* Returns the ID of the root of the tree containing node k (i.e., the 
   ** ancestor of k having no parent).
   ** pre: 0 <= k < numberOfNodes()
   */
   public int rootOf(int k) {
      return -1;   // STUB
   }

   /* Returns the ID of the nearest common ancestor (NCA) of the two
   ** specified nodes.  If none exists, -1 is returned.
   ** pre: 0 <= k,m < numberOfNodes()
   **
   ** Note: The key to making this work --in the case that k and m are 
   **       in the same tree-- is to start the search for their NCA at 
   **       ancestors of k and m, respectively, that are the same distance
   **       from the root of that tree.
   */
   public int nearestCommonAncestor(int k, int m) {
      return -1;  // STUB
   }

   /* If m is an ancestor of k, d is returned, where m is the d-ancestor of k.
   ** Otherwise, -1 is returned.
   ** (Examples: The distance from a node to its grandparent is 2.)
   ** pre: 0 <= k,m < numberOfNodes()
   */
   public int distance(int k, int m) {
      int d = 0;
      // loop invariant: k is the d-ancestor of K, where K refers to 
      //    the initial value of k
      while (k != -1  &&  k != m) {
         k = parent[k];
         d++;
      }
      if (k == -1) { return -1; }
      else { return d; }
   }

   /* Reports whether or not node m is an ancestor of node k.
   */
   public boolean isAncestorOf(int m, int k) {
      return distance(k,m) != -1;
   }


   // mutators
   // --------

   /* Assuming that node k is not an ancestor of node m, 
   ** makes m the parent of k and returns true (for success).
   ** Otherwise, makes no changes to the forest and returns false
   ** (for failure).
   */
   public boolean setParent(int k, int m) {
      boolean result = false;
      if (k != m  &&  !isAncestorOf(k,m)) {
         parent[k] = m;
         result = true;
      }
      return result;
   }

}