Great Deal! Get Instant $10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

Program 2: Command Design Pattern Java API KeyedItem, CD, Song Documentation FileIO Documentation The Iterator design pattern provides a way for the user to visit all of the items in a data structure,...

1 answer below »
Program 2: Command Design Pattern
Java API
KeyedItem, CD, Song Documentation
FileIO Documentation
The Iterator design pattern provides a way for the user to visit all of the items in a data structure, performing
an operation on each item. The user performs the loop and operates on the data, so this technique is
called external iteration.
As useful as this is, it is possible for the user to add or remove elements while the iteration is being
performed. Taking a snapshot of the data when the iterator is requested or throwing an exception when an
attempt is made to change the data in the collection are possible ways of handling this potential problem.
However, the Expert pattern suggests that the data structure holding the items should be performing the
iteration over the data that it contains. This technique is called internal iteration, and is commonly
implemented using the Command Design Pattern.
Lab:
• Interfaces
o Command Interface
o Execute Interface
Part I: For-Each and Iterable
The for-each statement requires that the collection being iterated over implement the built-
in Iterable interface. The only method in this interface is public Iterator iterator(). In order to use the for-
each statement with your AVLTree, your SearchTreeInterface must extend the Iterable interface. However,
you will need to comment out the iterator() method cu
ently in SearchTreeInterface.
Modify the old iterator method in BinaryTreeBasis to conform to the new method signature. Use setInorder
as your method to traverse the tree. Now, when working with the Command design pattern, you can use the
convenience of the for-each statement.
Part II: Command Interface, Execute Interface
The Command interface contains one method that accepts a single Object.
• public void execute(Object item)
The Execute interface also contains one method, but it accepts Objects that implement the Command
interface.
• public void execute(Command command)
Part III: Command Design Pattern
Objects implementing the Execute interface are objects that store a collection of other objects. When the
method in the Execute interface is invoked, the collection object will iterate over the items in the collection,
calling the method in the Command interface on each object in the collection. Thus, it is not possible for the
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/APIdocs/api/index.html
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/12-Command%20Design%20Pattern/javadoc/CD/index.html
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/12-Command%20Design%20Pattern/javadoc/FileIO/index.html
user to manipulate the collection while the internal iteration is performed, and the collection maintains control
over the data that it is responsible for.
Modify AVLTree from Lab 10 to implement the Execute interface, performing an inorder traversal over the
items in the tree. Call the Command interface method on each item visited.
Part IV: WorstCDs
• Song.java
• KeyedItem.java
• CD.java
• FileIO.java
• FileIOException.java
Implement the Command interface using a class (WorstCDs). This class should figure out the lowest rating
of the CDs in the AVLTree, collecting all of the CDs with this rating in an A
ayList. Allow a driver class to
have access to the resulting A
ayList of worst CDs (A
ayList getWorstCDs()). Display the results,
which should be in sorted order by CD title.
Part V: Longest Song
Implement the Command interface with another class (LongestSong). Process the CDs to find the overall
single longest song. Allow a driver class to have access to the longest song (Song getLongestSong()).
Display the longest song in your driver.
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/12-Command%20Design%20Pattern/Lab12/Song.java
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/12-Command%20Design%20Pattern/Lab12/KeyedItem.java
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/12-Command%20Design%20Pattern/Lab12/CD.java
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/12-Command%20Design%20Pattern/Lab12/FileIO.java
file:
C:/Users/luke3/Desktop/OOP/Programs/Program02/12-Command%20Design%20Pattern/Lab12/FileIOException.java
qfile_636778888101464564_123216_1.pdf qfile_636778888101464564_123216_2.zip
Answered Same Day Nov 15, 2020

Solution

Snehil answered on Nov 19 2020
147 Votes
Program02/AVLDriver.java
Program02/AVLDriver.java
import java.util.A
ayList;
import java.util.Iterator;
public class AVLDrive
{
    public static void main(String[] args)
    {
        AVLTree avlTree = new AVLTree();
        FileIO file = new FileIO("cds.txt", ",");
        
        try 
        {
            while(file.EOF()==false)
            {
                String artist = file.readLine();
                if(artist==null)
                {
                    
eak;
                }
                String title = file.readLine();
                int year = Integer.parseInt(file.readLine());
                int rating = Integer.parseInt(file.readLine());
                int tracks = Integer.parseInt(file.readLine());
                CD cd = new CD(title, artist, year, rating, tracks);
                for(int i=0;i                {
                    Iterato
String> iter = file.getTokens();
                    String length = iter.next();
                    String songTitle = iter.next();
                    cd.addSong(songTitle, length);
                }
                avlTree.insert(cd);
            }
        }
        catch (FileIOException e) {
            System.out.println(e.getMessage());
        }
        catch (TreeException e) {
            System.out.println(e.getMessage());
        }
        catch (Exception e) {
            System.out.println(e.getMessage());
        }
        
        WorstCDs worstCDsCommand = new WorstCDs();      
        avlTree.execute(worstCDsCommand);       
        A
ayList worstCDs = worstCDsCommand.getWorstCDs();
        if(worstCDs.size()==0)
        {
            System.out.println("No CDs found");
        }
        else
        {
            System.out.println("CD(s) with lowest rating of "+worstCDs.get(0).getRating()+" are:");
            for(int i = 0;i            {
                System.out.println( (i+1) + ". " +worstCDs.get(i).getKey());
            }
        }
        
        System.out.println();
        LongestSong longestSongCommand = new LongestSong();
        avlTree.execute(longestSongCommand);
        Song longestSong = longestSongCommand.getLongestSong();
        if(longestSong==null)
        {
            System.out.println("No CDs/songs found");
        }
        else
        {
            System.out.println("The longest song is: "+longestSong.getTitle()+", with length " + (longestSong.getLength()/60)+":"+(longestSong.getLength()%60));
        }
    }
}
Program02/AVLTree.java
Program02/AVLTree.java
import java.util.Iterator;
should consider not extending BST as a lot of knowledge about parent class implementation 
is necessary to write this class
public final class AVLTree extends BinarySearchTree implements Execute
{
   private boolean avlFlag;
   public AVLTree()  
   {
      super();
   } 
   public void insert(KeyedItem item) throws TreeException
   {
      super.insert(item);
      avlFlag = false;
      assert isBalanced() : "tree is not balanced after insertion of key: " + item.getKey();
   } 
   public void delete(Comparable sk) throws TreeException
   {
      super.delete(sk);
      avlFlag = false;
      assert isBalanced() : "tree is not balanced after deletion of key: " + sk;
   }
   
ove
iding these protected methods requires knowledge of the parent class' implementation
   protected TreeNode createNode(KeyedItem item)
   {
      TreeNode tNode = new AVLTreeNode(item);
      avlFlag = true;
      return tNode;
   }
   protected TreeNode insertLeft(TreeNode tNode, KeyedItem item)
   {
      tNode = super.insertLeft(tNode, item);
      AVLTreeNode avltn = (AVLTreeNode) tNode;
      if (avlFlag)
      {
         avltn = avlFixAddLeft(avltn);  
      }
      return avltn;
   }
   protected TreeNode insertRight(TreeNode tNode, KeyedItem item)
   {
      tNode = super.insertRight(tNode, item);
      AVLTreeNode avltn = (AVLTreeNode) tNode;
      if (avlFlag)
      {
         avltn = avlFixAddRight(avltn);  
      }
      return avltn;
   }
   
sets balance factors and calls the inherited rotate right method
   private AVLTreeNode singleRight(AVLTreeNode tNode)
   {
      AVLTreeNode left = tNode.getLeft();
      tNode.setBalanceFactor(AVL.BALANCED);
      left.setBalanceFactor(AVL.BALANCED);
      tNode = (AVLTreeNode) rotateRight(tNode);
      
System.out.println("SR");
      return tNode;
   }
   private AVLTreeNode singleLeft(AVLTreeNode tNode)
   {
      AVLTreeNode right = tNode.getRight();
      tNode.setBalanceFactor(AVL.BALANCED);
      right.setBalanceFactor(AVL.BALANCED);
      tNode = (AVLTreeNode) rotateLeft(tNode);
      
System.out.println("SL");
      return tNode;
   }
   private AVLTreeNode doubleLeftRight(AVLTreeNode tNode)
   {
      AVLTreeNode left = tNode.getLeft();
      AVLTreeNode leftRight = left.getRight();
      
next line determines the rotation
      AVL bF = leftRight.getBalanceFactor();
      leftRight.setBalanceFactor(AVL.BALANCED);
      tNode.setBalanceFactor(AVL.BALANCED);
      left.setBalanceFactor(AVL.BALANCED);
      if (bF == AVL.RIGHT)
      {
         
tNode.setBalanceFactor(AVL.BALANCED);
         left.setBalanceFactor(AVL.LEFT);
      }
      else if (bF == AVL.LEFT)
      {
         tNode.setBalanceFactor(AVL.RIGHT);  
         
left.setBalanceFactor(AVL.BALANCED);  
      }
      
do the rotation
      AVLTreeNode temp = (AVLTreeNode) rotateLeft(left);
      tNode.setLeft(temp);
      tNode = (AVLTreeNode) rotateRight(tNode);  
      
System.out.println("DLR");
      return tNode;
   }
   private AVLTreeNode doubleRightLeft(AVLTreeNode tNode)
   {
      AVLTreeNode right = tNode.getRight();
      AVLTreeNode rightLeft = right.getLeft();
      
next line determines the rotation
      AVL bF = rightLeft.getBalanceFactor();
      rightLeft.setBalanceFactor(AVL.BALANCED);
      tNode.setBalanceFactor(AVL.BALANCED);
      right.setBalanceFactor(AVL.BALANCED);
      if (bF == AVL.RIGHT)
      {
         tNode.setBalanceFactor(AVL.LEFT);
         
ight.setBalanceFactor(AVL.BALANCED);
      }
      else if (bF == AVL.LEFT)
      {
         
tNode.setBalanceFactor(AVL.BALANCED);
         right.setBalanceFactor(AVL.RIGHT);
      }
      AVLTreeNode temp = (AVLTreeNode) rotateRight(right);
      tNode.setRight(temp);
      tNode = (AVLTreeNode) rotateLeft(tNode);
      
System.out.println("DRL");
      return tNode;
   }
   private AVLTreeNode avlFixAddLeft(AVLTreeNode tNode)
   {
      
, l, and lu are the only possible balance factors
      tNode.insertLeft();
      AVL factor = tNode.getBalanceFactor();
      if (factor == AVL.BALANCED)
      {
         avlFlag = false; 
no more to do this time around
         return tNode;
      }
      else if (factor == AVL.LEFT)
      {
         return tNode;  
no rotation necessary at this node, but need to keep checking upwards
      }
      
the balance factor must be lu
      AVLTreeNode left = tNode.getLeft();
      if (left.getBalanceFactor() == AVL.RIGHT)
      {
         tNode = doubleLeftRight(tNode);
      }
      else 
      {
         tNode = singleRight(tNode);
      }
      avlFlag = false; 
asically, stop checking (return the replacement node for this position)
      return tNode;
   }
   private AVLTreeNode avlFixAddRight(AVLTreeNode tNode)
   {
      tNode.insertRight();
      AVL factor = tNode.getBalanceFactor();
      if (factor == AVL.BALANCED)
      {
         avlFlag = false; 
no more to do this time around
         return tNode;
      }
      else if (factor == AVL.RIGHT)
      {
         return tNode;  
no rotation necessary at this node, but need to keep checking upwards
      }
      AVLTreeNode right = tNode.getRight();
      if (right.getBalanceFactor() == AVL.LEFT)
      {
         tNode = doubleRightLeft(tNode);
      }
      else
      {
         tNode = singleLeft(tNode);
      }
      avlFlag = false;
      return tNode;
   }
   protected TreeNode deleteLeft(TreeNode tNode, Comparable sk)
   {
      tNode = super.deleteLeft(tNode, sk);
      AVLTreeNode avltn = (AVLTreeNode) tNode;
      if (avlFlag)
      {
         avltn = avlFixDeleteLeft(avltn); 
      }
      return avltn;
   }
   protected TreeNode deleteRight(TreeNode tNode, Comparable sk)
   {
      tNode = super.deleteRight(tNode, sk);
      AVLTreeNode avltn = (AVLTreeNode) tNode;
      if (avlFlag)
      {
         avltn = avlFixDeleteRight(avltn);  
      }
      return avltn;
   }
   protected TreeNode deleteNode(TreeNode tNode) 
   {
      avlFlag = true;
      tNode = super.deleteNode(tNode);
      return tNode;
   } 
   protected TreeNode deleteInorderSuccessor(TreeNode tNode)
   {
      tNode = super.deleteInorderSuccessor(tNode);
      AVLTreeNode avltn = (AVLTreeNode) tNode;
      if (avlFlag)
      {
         avltn = avlFixDeleteRight(avltn);  
came from right
      }
      return avltn;
   }
   protected TreeNode deleteLeftmostt(TreeNode tNode)
   {
      tNode = super.deleteLeftmostt(tNode);
      AVLTreeNode avltn = (AVLTreeNode) tNode;
      if (avlFlag)
      {
         avltn = avlFixDeleteLeft(avltn);  
      }
      return avltn;
   }
   
will be doing left rotations if coming back from the left on a delete
   private AVLTreeNode avlFixDeleteLeft(AVLTreeNode tNode)
   {
      AVL factor = tNode.getBalanceFactor();
      tNode.deleteLeft();
      if (factor == AVL.BALANCED)  
change from zero--  STOP
      {
         avlFlag = false; 
no more to do this time around
         return tNode;
      }
      factor = tNode.getBalanceFactor();
      if (factor == AVL.RIGHT || factor == AVL.BALANCED)
      {
         return tNode;  
need to keep checking, but no rotations necessary as yet
      }
      
otations necessary for deleting a node
      AVLTreeNode right = tNode.getRight();
      AVL bF = right.getBalanceFactor();
      if (bF == AVL.BALANCED)
      {
         tNode = singleLeft0(tNode);
      }
      else if (bF == AVL.RIGHT)
      {
         tNode = singleLeft(tNode);
      }
      else 
      {
         tNode = doubleRightLeft(tNode);
      }
      return tNode;
   }
   private AVLTreeNode avlFixDeleteRight(AVLTreeNode tNode)
   {
      AVL factor = tNode.getBalanceFactor();
      tNode.deleteRight();
      if (factor == AVL.BALANCED) 
change from zero--  STOP
      {
         avlFlag = false; 
no more to do this time around
         return tNode;
      }
      factor = tNode.getBalanceFactor();
      if (factor == AVL.LEFT || factor == AVL.BALANCED)
      {
         return tNode;  
need to keep checking, but no rotations necessary as yet
      }
      
otations necessary for deleting a node
      AVLTreeNode left = tNode.getLeft();
      AVL bF = left.getBalanceFactor();
      if (bF == AVL.BALANCED)
      {
         tNode = singleRight0(tNode);
      }
      else if (bF == AVL.LEFT)
      {
         tNode = singleRight(tNode);
      }
      else 
      {
         tNode = doubleLeftRight(tNode);
      }
      return tNode;
   }
   private AVLTreeNode singleLeft0(AVLTreeNode tNode)
   {
      AVLTreeNode right = tNode.getRight();
      tNode.setBalanceFactor(AVL.RIGHT);
      right.setBalanceFactor(AVL.LEFT);
      tNode = (AVLTreeNode) rotateLeft(tNode);
      avlFlag = false;  
STOP
      
System.out.println("SL0");
      return tNode;
   }
   private AVLTreeNode singleRight0(AVLTreeNode tNode)
   {
      AVLTreeNode left = tNode.getLeft();
      tNode.setBalanceFactor(AVL.LEFT);
      left.setBalanceFactor(AVL.RIGHT);
      tNode = (AVLTreeNode) rotateRight(tNode);
      avlFlag = false;  
STOP
      
System.out.println("SR0");
      return tNode;
   }
   
   public void execute(Command command)
    {
          BinaryTreeIterator iter = iterator();
          for(Iterator i =iter;i.hasNext();)
          {
              command.execute(i.next());
          }
    }
}  
Program02/AVLTreeNode.java
Program02/AVLTreeNode.java
enum AVL {LEFT_HEAVY, LEFT, BALANCED, RIGHT, RIGHT_HEAVY};
public class AVLTreeNode extends TreeNode
{
   private AVL balanceFactor;
   public AVLTreeNode(Object item) 
   {
      super(item);
      balanceFactor = AVL.BALANCED;
   }  
   public AVLTreeNode getLeft() 
   {
      return (AVLTreeNode) super.getLeft();
   } 
   public AVLTreeNode getRight() 
   {
      return (AVLTreeNode) super.getRight();
   } 
   public void setBalanceFactor(AVL avl)
   {
       balanceFactor = avl;
   }
   public AVL getBalanceFactor()
   {
       return balanceFactor;
   }
   public void insertLeft()
   {
      switch (balanceFactor)
      {
         case RIGHT:
            balanceFactor = AVL.BALANCED;
            
eak;
         case BALANCED:
            balanceFactor = AVL.LEFT;
            
eak;
         case LEFT:
            balanceFactor = AVL.LEFT_HEAVY;
            
eak;
      }
   }
   public void insertRight()
   {
      switch (balanceFactor)
      {
         case RIGHT:
            balanceFactor = AVL.RIGHT_HEAVY;
            
eak;
         case BALANCED:
            balanceFactor = AVL.RIGHT;
            
eak;
         case LEFT:
            balanceFactor = AVL.BALANCED;
            
eak;
      }
   }
   public void deleteLeft()
   {
      switch (balanceFactor)
      {
         case RIGHT:
            balanceFactor = AVL.RIGHT_HEAVY;
            
eak;
         case BALANCED:
            balanceFactor = AVL.RIGHT;
            
eak;
         case LEFT:
            balanceFactor = AVL.BALANCED;
            
eak;
      }
   }
   public void deleteRight()
   {
      switch (balanceFactor)
      {
         case RIGHT:
            balanceFactor = AVL.BALANCED;
            
eak;
         case BALANCED:
            balanceFactor = AVL.LEFT;
            
eak;
         case LEFT:
            balanceFactor = AVL.LEFT_HEAVY;
            
eak;
      }
   }
}  
Program02/BinarySearchTree.java
Program02/BinarySearchTree.java
**
 * This class stores KeyedItem data in a reference based binary search tree.
 * A binary search tree is a binary tree (each node has 0, 1, or 2 children).
 * In addition, all items on the left of a given node have search keys that are "less than" the item at the specified node.
 * All items on the right of a given node have search keys that are "greater than" the item at the specified node.
 *
public class BinarySearchTree extends BinaryTreeBasis implements SearchTreeInterface
{   
   /** The number of KeyedItems stored in the binary search tree.
    *  Class invariant: should be the same as the number of nodes in the tree.
    *
   private int size;
   /**  Constructs an empty binary search tree. *
   public BinarySearchTree()
   {
      super();
   }
   public KeyedItem retrieve(Comparable sk) 
   {
      return retrieveItem(getRootNode(), sk);
   }  
   public void insert(KeyedItem item) throws TreeException
   {
      setRootNode(insertItem(getRootNode(), item));
      size++;
      assert validateBSTProperty() : "not a binary search tree after insertion of key: " + item.getKey();
      assert validateSize() : "size is not co
ect after insertion of key: " + item.getKey();
   }  
   public void delete(Comparable sk) throws TreeException 
   {
      setRootNode(deleteItem(getRootNode(), sk));
      size--;
      assert validateBSTProperty() : "not a binary search tree after deletion of key: " + sk;
      assert validateSize() : "size is not co
ect after deletion of key: " + sk;
   }  
   /**
    * Recursive method to retrieve an item from the binary search tree. 
    * Preconditions: tNode is not null, sk is not null
    * Postconditions: the KeyedItem with the specified search key is returned, or null is returned if an item with the specified search key cannot be found
    *
   protected KeyedItem retrieveItem(TreeNode tNode, Comparable sk)
   {
      
disallow duplicates so that you always know which object to retrieve (or delete)
      
you could return a list with all duplicate search keys (but delete is still a problem)
      KeyedItem treeItem;
      if (tNode == null) 
      {
         treeItem = null;
      }
      else 
      {
         KeyedItem nodeItem = (KeyedItem) tNode.getItem();
         int comparison = sk.compareTo(nodeItem.getKey());
         if (comparison == 0) 
         {
            treeItem = nodeItem;
         }
         else if (comparison < 0) 
         {
            treeItem = retrieveItem(tNode.getLeft(), sk);
         }
         else  
         { 
            treeItem = retrieveItem(tNode.getRight(), sk);
         }  
      }  
      return treeItem;
   }  
   /**
    * Creates and returns a new TreeNode to be linked into the tree. 
    * Precondition: item is not null
    * Postcondition: a new TreeNode containing item is returned.
    * Note: Should be ove
idden by child classes to create TreeNodes of the co
ect type.
    *
   protected TreeNode createNode(KeyedItem item)
   {
      TreeNode tNode = new TreeNode(item);
      return tNode;
   }
   /**
    * Throws an exception if an attempt to insert an item with a search key that matches the
    * search key of an item already in the tree.
    * Ove
ide this method if duplicates are allowed in child classes.
    * Throws: TreeException as an attempt to insert a duplicate was detected.
    *
   protected TreeNode insertDuplicate(TreeNode tNode, KeyedItem item) throws TreeException
   {
      throw new TreeException ("Cannot add duplicate.");
   }
   /**
    * Searches for the leaf insertion location for item. 
    * Precondition: item is not null
    * Postcondition: returns the cu
ent node so that it can be linked (or relinked) to its parent
    * depending on whether a left or a right was taken in obtaining the leaf insertion location.
    * Throws: TreeException if an attempt to insert a duplicate is detected.
    * Calls: insertLeft, insertRight, insertDuplicate depending on the item's sk
    *
   protected TreeNode insertItem(TreeNode tNode, KeyedItem item) throws TreeException
   {
      if (tNode == null) 
      {
         return createNode(item);
      }  
      KeyedItem nodeItem = (KeyedItem) tNode.getItem();
      int comparison = item.getKey().compareTo(nodeItem.getKey());
      if (comparison == 0)
      {
         tNode = insertDuplicate(tNode, item);
      }
      else if (comparison < 0) 
      {
         tNode = insertLeft(tNode, item);
      }
      else 
      { 
         tNode = insertRight(tNode, item);
      }  
      return tNode;
   }  
   /**
    * A left hand turn must be dealt with to insert a node.
    * Preconditions: tNode is not null, item is not null
    * Postcondition: the child node is linked to tNode on the left, and tNode is returned to be linked in to its parent
    * Note: this method makes a recursive call to insertItem
    *
   protected TreeNode insertLeft(TreeNode tNode, KeyedItem item)
   {
      TreeNode subtree = insertItem(tNode.getLeft(), item);
      tNode.setLeft(subtree);
      return tNode;
   }
   protected TreeNode insertRight(TreeNode tNode, KeyedItem item)
   {
      TreeNode subtree = insertItem(tNode.getRight(), item);
      tNode.setRight(subtree);
      return tNode;
   }
   protected TreeNode deleteLeft(TreeNode tNode, Comparable sk)
   {
      TreeNode subtree = deleteItem(tNode.getLeft(), sk);
      tNode.setLeft(subtree);
      return tNode;
   }
   protected TreeNode deleteRight(TreeNode tNode, Comparable sk)
   {
      TreeNode subtree = deleteItem(tNode.getRight(), sk);
      tNode.setRight(subtree);
      return tNode;
   }
   protected TreeNode deleteItem(TreeNode tNode, Comparable sk) throws TreeException
   {
      if (tNode == null) 
      {
         throw new TreeException("Item not found");
      }
      TreeNode subtree;
      KeyedItem nodeItem = (KeyedItem)tNode.getItem();
      int comparison = sk.compareTo(nodeItem.getKey());
      if (comparison == 0) 
      {
         
 item is in the root of some subtree
         tNode = deleteNode(tNode);  
 delete the item
      }
      
 else search for the item
      else if (comparison < 0) 
      {
         tNode = deleteLeft(tNode, sk);
      }
      else 
      { 
         tNode = deleteRight(tNode, sk);
      } 
      return tNode;
   }  
   protected TreeNode deleteNode(TreeNode tNode) 
   {
      TreeNode left = tNode.getLeft();
      TreeNode right = tNode.getRight();
      if (left == null) 
      {
         return tNode.getRight();
      } 
      else if (right == null) 
      {
         return tNode.getLeft();
      } 
      
 there are two children:
      
 retrieve and delete the inorder successo
      else 
      {
         return deleteInorderSuccessor(tNode);
      } 
   }  
   protected TreeNode deleteInorderSuccessor(TreeNode tNode)
   {
      TreeNode right = tNode.getRight();
      KeyedItem replacementItem = findLeftmost(right);
      tNode.setItem(replacementItem);
      TreeNode subtree = deleteLeftmost(tNode.getRight());
      tNode.setRight(subtree);
      return tNode;
   }
   protected KeyedItem findLeftmost(TreeNode tNode)  
   {
      if (tNode.getLeft() == null) 
      {
         return (KeyedItem) tNode.getItem();
      }
      else 
      {
         return findLeftmost(tNode.getLeft());
      }  
   } 
   protected TreeNode deleteLeftmostt(TreeNode tNode)
   {
      TreeNode subtree = deleteLeftmost(tNode.getLeft());
      tNode.setLeft(subtree);
      return tNode;
   }
   protected TreeNode deleteLeftmost(TreeNode tNode) 
   {
      if (tNode.getLeft() == null) 
      {
         return tNode.getRight();
      }
      else 
      {
         return deleteLeftmostt(tNode);
      }  
   } 
   protected TreeNode rotateLeft(TreeNode tNode)
   {
      TreeNode right = tNode.getRight();
      TreeNode rightleft = right.getLeft();
      tNode.setRight(rightleft);
      right.setLeft(tNode);
      return right;
   }
   protected TreeNode rotateRight(TreeNode tNode)
   {
      TreeNode left = tNode.getLeft();
      TreeNode leftright = left.getRight();
      tNode.setLeft(leftright);
      left.setRight(tNode);
      return left;
   }
   public boolean isBalanced()
   {
      return isBalanced(getRootNode());
   }
   private boolean isBalanced(TreeNode tNode)
   {
      if (tNode == null)
      {
         return true;
      }
      boolean balanced = isBalanced(tNode.getLeft());
      if (!balanced) return balanced;
      balanced = isBalanced(tNode.getRight());
      if (!balanced) return balanced;
      int leftHeight = getHeight(tNode.getLeft());
      int rightHeight = getHeight(tNode.getRight());
      if (Math.abs(leftHeight - rightHeight) > 1)
      {
         balanced = false;
      }
      return balanced;
   }
   public int height()
   {
      return getHeight(getRootNode());
   }
   private int getHeight(TreeNode tNode)
   {
      if (tNode == null)
      {
         return 0;
      }
      int height = 0;
      int leftHeight = getHeight(tNode.getLeft());
      int rightHeight = getHeight(tNode.getRight());
      if (leftHeight >= rightHeight)
      {
         height = leftHeight + 1;
      }
      else
      {
         height = rightHeight + 1;
      }
      return height;
   }
   public int size()
   {
      return size;
   }
   public int computeSize()
   {
      int num = 0;
      TreeIterator iter = iterator();
      iter.setInorder();
      while (iter.hasNext())
      {
         KeyedItem item = (KeyedItem) iter.next();
         num++;
      }
      return num;
   }
   public boolean validateSize()
   {
      return size() == computeSize();
   }
   public boolean validateBSTProperty()
   {
      TreeIterator iter = iterator();
      iter.setInorder();
      boolean valid = true;
      
an empty tree satisfies the BST property by definition
      if (!iter.hasNext()) return true;
      KeyedItem item1 = (KeyedItem) iter.next();
      Comparable key1 = item1.getKey();
      while (iter.hasNext())
      {
         KeyedItem item2 = (KeyedItem) iter.next();
         Comparable key2 = item2.getKey();
         
key1 must be <= key2 for BST property
         if (key1.compareTo(key2) > 0)
         {
            valid = false;
            
eak;
         }
         item1 = item2;
         key1 = key2;
      }
      return valid;
   }
} 
Program02/BinaryTreeBasis.java
Program02/BinaryTreeBasis.java
import java.util.Iterator;
public abstract class BinaryTreeBasis
{
   private TreeNode root;
   public BinaryTreeBasis() 
   {
      root = null;
   }  
   public boolean isEmpty() 
   {
      return root == null;
   }  
   public void makeEmpty() 
   {
      root = null;
   }  
   public Object getRootItem() throws TreeException 
   {
      if (root == null) 
      {
         throw new TreeException("Empty tree");
      }
      else 
      {
         return root.getItem();
      } 
   }  
   protected TreeNode getRootNode()
   {
      return root;
   }
   protected void setRootNode(TreeNode tNode)
   {
      root = tNode;
   }
   public BinaryTreeIterator iterator()
   {
       BinaryTreeIterator bti = new BinaryTreeIterator(root);
       bti.setInorder();
       return bti;
   }
}  
Program02/BinaryTreeIterator.java
Program02/BinaryTreeIterator.java
import queue.*;
class BinaryTreeIterator implements TreeIterato
{
   private TreeNode root;  
   private QueueInterface items;       
   public BinaryTreeIterator(TreeNode root) 
   {
      this.root = root;
      items = new QueueLinked();
   } 
   public boolean hasNext() 
   {
      return !items.isEmpty();
   }  
   public Object next() throws TreeException
   {
      try 
      {
         return items.dequeue();
      }  
      catch (QueueException e) 
      {
         throw new TreeException("End of tree traversal.");
      }  
   }  
   public void remove() throws UnsupportedOperationException 
   {
      throw new UnsupportedOperationException();
   }  
   public void setPreorder() 
   {
      items.dequeueAll();
      preorder(root);
   } 
   public void setInorder() 
   {
      items.dequeueAll();
      inorder(root);
   }  
   public void setPostorder() 
   {
      items.dequeueAll();
      postorder(root);
   }   
   private void preorder(TreeNode tNode) 
   {
      if (tNode != null) 
      {  
         items.enqueue(tNode.getItem());
         preorder(tNode.getLeft());
         preorder(tNode.getRight());
      } 
   } 
   private void inorder(TreeNode tNode) 
   {
      if (tNode != null) 
      {  
         inorder(tNode.getLeft());
         items.enqueue(tNode.getItem());
         inorder(tNode.getRight());
      }
   }  
   private void postorder(TreeNode tNode) 
   {
      if (tNode != null) 
      {  
         postorder(tNode.getLeft());
         postorder(tNode.getRight());
         items.enqueue(tNode.getItem());
      } 
   } 
   public void setLevelorder()
   {
      if (root != null)
      {
         QueueInterface q = new QueueLinked();
         q.enqueue(root);
         while (!q.isEmpty())
         {
            TreeNode tNode = q.dequeue();
            items.enqueue(tNode.getItem());
            TreeNode left = tNode.getLeft();
            TreeNode right = tNode.getRight();
            if (left != null)
            {
               q.enqueue(left);
            }
            if (right != null)
            {
               q.enqueue(right);
            }
         }
      }
   }
}  
Program02/CD.java
Program02/CD.java
import java.util.A
ayList;
public class CD extends KeyedItem{
   private int year;
   private String img;
   private A
ayList songs;
   private int numTracks;  
used by addSong
   private int rating;
   public CD (String title, String artist, int year, int rating, int tracks)
   {
      super(title);
      this.year = year;
      img = artist + " - " + getKey() + ".jpg";
      numTracks = tracks;
      songs = new A
ayList();
      if (rating > 0 && rating <= 10)
      {
         this.rating = rating;
      }
      else
      {
         this.rating = 5;
      }
   }
   public int getNumberOfTracks()
   {
      return songs.size();
   }
   public int getYear()
   {
      return year;
   }
   public int getRating()
   {
      return rating;
   }
   
Song is immutable, so this is safe
   public Song getSong(int index)
   {
      if (index >= 0 && index < songs.size())
      {
         return songs.get(index);
      }
      else
      {
         return null;
      }
   }
   public void addSong(String title, String length)
   {
      if (songs.size() < numTracks)
      {
         songs.add(new Song(title, length));
      }
   }
   public String toString()
   {
      return getKey() + "  " + year + "  " + rating + "  " + getNumberOfTracks();
   }
   public void writeCD(FileIO file)
   {
      if (rating == 10)
      {
         file.writeLine("         
  • " + "
    " + getKey() + "
    " + "
    li>");
          }
          else
          {
             file.writeLine("         
  • " + getKey() + "
    li>");
          }
          file.writeLine("         img src = \"art\\" + img + "\"
    cente
    ");
          file.writeLine("         
      ");
            file.writeLine("            
    • Year: " + year + "
      li>");
            file.writeLine("            
    • Rating: " + rating + "
      li>");
            file.writeLine("            
    • Tracks:
      li>");
            file.writeLine("");
            file.writeLine("td>Track   
      td
      td>Title
      td
      td>Length  
      td
      t
      ");
            int count = 0;
            for (Song song : songs)
            {
               file.writeLine("");
               song.writeSong(file, ++count);
               file.writeLine("
      t
      ");
            }
            file.writeLine("
      table>");
            file.writeLine("         
      ul>");
         }
      }
      Program02/cds.txt
      Dark Tranquillity
      We Are The Void
      2010
      8
      13
      3:46,Shadow in Our Blood
      3:48,Dream Oblivion
      4:32,The Fatalist
      4:46,In My Absence
      4:55,The Grandest Accusation
      3:52,At the Point of Ignition
      3:33,Her Silent Language
      3:56,Arkhangelsk
      3:59,I Am the Void
      3:50,Surface the Infinite
      6:43,Iridium
      2:07,Star of Nothingness
      3:53,To Where Fires Cannot Feed
      Asphyx
      Death...The Brutal Way
      2009
      7
      10
      4:26,Sco
      utics
      3:33,The Herald
      3:56,Bloodswamp
      3:52,Death...The Brutal Way
      6:40,Asphyx II (They Died As They Marched)
      5:42,Eisenbahnmörse
      5:35,Black Hole Storm
      5:04,Riflegun Redeeme
      6:53,Cape Horn
      3:11,The Saw, The Torture, The Pain
      Kalmah
      12 Gauge
      2010
      9
      10
      5:16,Rust Never Sleeps
      4:10,One Of Fail
      4:27,Bullets Are Blind
      4:19,Swampwa
      3:58,Better Not To Tell
      4:04,Hook The Monste
      4:25,Godeye
      5:50,12 Gauge
      6:28,Sacramentum
      3:10,Cold Sweat
      Absu
      Absu
      2009
      9
      13
      4:08,Between The Absu Of Eridu & Erech
      3:19,Night Fire Canonization
      4:54,Amy
      3:05,Nunbarshegunu
      4:46,13 Globes
      7:03,...Of The Dead Who Never Rest In Their Tombs Are The Attendance Of Familiar Spirits...
      4:48,Magic(K) Square Ciphe
      3:25,In The Name Of Auebothiabathabaithobeuee
      2:38,Gi
      a's Temple
      4:56,Those Of The Void Will Re-Ente
      5:00,Sceptre Command
      4:41,Ye Uttuku Spells
      0:58,Twix Yesterday The Day & The Mo
      ow
      Augury
      Fragmentary Evidence
      2009
      9
      9
      4:18,Aetheral
      5:37,Simian Cattle
      5:10,Orphans of Living
      8:24,Jupiter to Ignite
      5:12,Sovereigns Unknown
      6:29,Skyless
      4:06,Faith Puppeteers
      4:30,Brimstone Landscapes
      11:12,Oversee the Rebirth
      Immolation
      Majesty And Decay
      2010
      9
      12
      1:19,Intro
      3:18,The Purge
      2:41,A Token Of Malice
      4:29,Majesty And Decay
      3:38,Divine Code
      4:04,In Human Form
      4:37,A Glorious Epoch
      2:04,Interlude
      3:58,A Thunderous Consequence
      5:19,The Rapture Of Ghosts
      3:44,Power And Shame
      5:53,The Comfort Of Cowards
      Skyfire
      Esoteric
      2009
      7
      11
      1:26,Deathlike Overture
      4:44,Esoteric
      6:10,Rise and Decay
      4:10,Let the Old World Burn
      7:09,Darkness Descending
      3:56,Seclusion
      7:10,Misery's Supremacy
      4:52,Under A Pitch Black Sky
      5:18,Linger in Doubt
      7:21,The Legacy of the Defeated
      3:36,Within Reach
      Neuraxis
      Trilateral Progression
      2005
      8
      10
      0:38,Introspect
      3:30,Clarity
      5:15,Thought Adjuste
      4:27,Shatter The Wisdom
      3:42,Monitoring The Mind
      3:42,A Curative Struggle
      4:25,Chamber Of Gaurdians
      1:39,Caricature
      1:52,Axioms
      6:00,The Apex
      Insomnium
      Across The...
    • SOLUTION.PDF
    SOLUTION.PDF

    Answer To This Question Is Available To Download

    Related Questions & Answers

    More Questions »

    Submit New Assignment

    Copy and Paste Your Assignment Here
    Attach File