Question

In: Computer Science

public class CDLL_Node<T> { private T data; private CDLL_Node<T> prev, next; // EACH CDLL_Node PTS TO...

public class CDLL_Node<T>
{
  private T data;
  private CDLL_Node<T> prev, next; // EACH CDLL_Node PTS TO ITS PREV  & NEXT

  public CDLL_Node()
  {
    this( null, null, null );  // 3 FIELDS TO INIT
  }

  public CDLL_Node(T data)
  {
    this( data, null, null);
  }

  public CDLL_Node(T data, CDLL_Node<T> prev, CDLL_Node<T> next)
  {
    setData( data );
        setPrev( prev );
    setNext( next );
  }

  public T getData()
  {
    return data;
  }

  public CDLL_Node<T> getPrev()
  {
    return prev;
  }
  public CDLL_Node<T> getNext()
  {
    return next;
  }

  public void setData(T data)
  {
     this.data = data;
  }

  public void setNext(CDLL_Node<T> next)
  {
    this.next = next;
  }
  
  public void setPrev(CDLL_Node<T> prev)
  {
    this.prev = prev;
  }
 
  public String toString()
  {
          return ""+getData();
  } 
         
} //EOF
import java.io.*;
import java.util.*;

public class CDLL_List<T>
{
        private CDLL_Node<T> head;  // pointer to the front (first) element of the list
        private int count=0;
        
        public CDLL_List()
        {
                head = null; // compiler does this anyway. just for emphasis
        }

        // LOAD LINKED LIST FROM INCOMING FILE
        @SuppressWarnings("unchecked")
        public CDLL_List( String fileName, boolean orderedFlag )
        {       head = null;
                try
                {
                        BufferedReader infile = new BufferedReader( new FileReader( fileName ) );
                        while ( infile.ready() )
                        {
                                if (orderedFlag)
                                        insertInOrder( (T)infile.readLine() );  // WILL INSERT EACH ELEM INTO IT'S SORTED POSITION
                                else
                                        insertAtTail( (T)infile.readLine() );  // TACK EVERY NEWELEM ONTO END OF LIST. ORIGINAL ORDER PRESERVED
                        }
                        infile.close();
                }
                catch( Exception e )
                {
                        System.out.println( "FATAL ERROR CAUGHT IN C'TOR: " + e );
                        System.exit(0);
                }
        }

        //-------------------------------------------------------------



        // ########################## Y O U   W R I T E    T H E S E    M E T H O D S ########################

        // inserts new elem at front of list - pushing old elements back one place

        public void insertAtFront(T data)
        {
                // WRITE THE LINES OF CODE TO DO THE INSERT
        }
        public void insertAtTail(T data)
        {
                // CALL INSERT AT FRONT HERE 
                // THEN ADJUST THE HEAD POINTER 
        }
        public boolean removeAtTail()   // RETURNS TRUE IF THERE WAS NODE TO REMOVE
        {
                return false; // YOUR CODE HERE. TRY TO DO CODE RE-USE SIMILAR TO FRONT
        }

        public boolean removeAtFront() // RETURNS TRUE IF THERE WAS NODE TO REMOVE
        {
                return false; // YOUR CODE HERE.  // TRY TO DO CODE RE-USE SIMILAR TO FRONT
        }

        public String toString()
        {
                String toString = "";  // NO <=> DELIMITERS REQUIRED ANYWHERE IN OUTPUT

                return toString;  // JUST A SPACE BETEEN ELEMENTS LIKE IN LAB3
        }

        public int size() // OF COURSE MORE EFFICIENT to KEEP COUNTER BUT YOU  MUST WRITE LOOP
        {
                return 0; // YOUR CODE HERE
        }

        public boolean empty()
        {
                return false;  // YOUR CODE HERE
        }

        public boolean contains( T key )
        {
                return false;  // YOUR CODE HERE
        }

        public CDLL_Node<T> search( T key )
        {
                return null;  // YOUR CODE HERE
        }

        @SuppressWarnings("unchecked")  //CAST TO COMPARABLE THROWS WARNING
        public void insertInOrder(T  data)
        {
                // YOUR CODE HERE
        }

        public boolean remove(T key)
        {
                return false; //  REPLACE WITH YOUR CODE 
        }


        public CDLL_List<T> union( CDLL_List<T> other )
        {
                CDLL_List<T> union = new CDLL_List<T>();

                // YOUR CODE HERE

                return union;
        }
        public CDLL_List<T> inter( CDLL_List<T> other )
        {
                CDLL_List<T> inter = new CDLL_List<T>();

                // YOUR CODE HERE

                return inter;
        }
        public CDLL_List<T> diff( CDLL_List<T> other )
        {
                CDLL_List<T> diff = new CDLL_List<T>();

                // YOUR CODE HERE

                return diff;
        }
        public CDLL_List<T> xor( CDLL_List<T> other )
        {
                return  null;  // REPLACE WITH YOUR CODE 
        }

} //END CDLL_LIST CLASS

// A D D   C D L L  N O D E   C L A S S  D O W N   H E R E 
// R E M O V E  A L L  P U B L I C  &  P R I V A T E (except toString)
// R E M O V E  S E T T E R S  &  G E T T E R S 
// M A K E  T O  S T R I N G  P U B L I C
import java.io.*;
import java.util.*;

public class CDLL_Tester
{
        public static void main( String args[] ) throws Exception
        {
                CDLL_List<String> list1 = new CDLL_List<String>( args[0], false );  // false = INSERTATTAIL CALLED ON EACH T READ FROM FILE
                System.out.format("list1 %s size %d unordered %s\n",args[0],list1.size(),list1 ); // invokes toString
                
                list1.remove( "charlie" ); list1.remove("echo"); list1.remove("zebra"); // HEAD, TAIL, NOWHERE
                System.out.format("list1 (after remove charlie, echo & zebra) %s\n",list1 ); // invokes toString
                
                CDLL_List<String> list2 = new CDLL_List<String>( args[0], true );  // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
                System.out.format("list2 %s size %d ordered %s\n",args[0],list2.size(),list2 ); // invokes toString

                CDLL_List<String> list3 = new CDLL_List<String>( args[1], true );  // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
                System.out.format("list3 %s size %d ordered %s\n",args[1],list3.size(),list3 ); // invokes toString     
                
                // MUST RETURN ALL SET OP LISTS IN SORTED ORDER NO DUPES 
                CDLL_List<String> unionList = list2.union(list3);
                System.out.println("list2.union(list3) " + unionList);  
                
                CDLL_List<String> interList = list2.inter(list3); 
                System.out.println("list2.inter(list3) " + interList); 
                
                CDLL_List<String> diffList = list2.diff(list3);           
                System.out.println("list2.diff(list3)  " + diffList); 
                
                CDLL_List<String> xorList = list2.xor(list3);                             
                System.out.println("list2.xor(list3)   " + xorList); 
                
                // ECHO LISTS 2 & 3  TO PROVE THEY WERE NOT MODIFIED
                
                System.out.println();
                System.out.println( "list2 after set ops: " + list2 );
                System.out.println( "list3 after set ops: " + list3 );
                
                // DESTROY LIST2 BY REPEATEDLY CALLING REMOVE AT TAIL UNTIL EMPTY
                while ( ! list2.empty() ) list2.removeAtTail();

                // DESTROY LIST3 BY REPEATEDLY CALLING REMOVE AT FRONT
                while ( ! list3.empty() ) list3.removeAtFront();
                
        // ECHO LISTS 2 & 3  TO PROVE THEY WERE DESTROYED
                
                System.out.println();
                System.out.println( "list2 after all nodes removedAtTail: " + list2 );
                System.out.println( "list3 after all nodes removedAtFront: " + list3 );
        } // END MAIN
} // EOF

set1.txt

charlie
bravo
delta
alpha
golf
india
hotel
echo

set2.txt

foxtrot
baker
xray
zebra
charlie
victor

Solutions

Expert Solution

//============CDLL_Node.java======================
public class CDLL_Node<T>
{
private T data;
private CDLL_Node<T> prev, next; // EACH CDLL_Node PTS TO ITS PREV & NEXT

public CDLL_Node()
{
this( null, null, null ); // 3 FIELDS TO INIT
}

public CDLL_Node(T data)
{
this( data, null, null);
}

public CDLL_Node(T data, CDLL_Node<T> prev, CDLL_Node<T> next)
{
setData( data );
setPrev( prev );
setNext( next );
}

public T getData()
{
return data;
}

public CDLL_Node<T> getPrev()
{
return prev;
}
public CDLL_Node<T> getNext()
{
return next;
}

public void setData(T data)
{
this.data = data;
}

public void setNext(CDLL_Node<T> next)
{
this.next = next;
}
  
public void setPrev(CDLL_Node<T> prev)
{
this.prev = prev;
}

public String toString()
{
return ""+getData();
}

} //EOF CDLL_Node.java
//==================================

//============CDLL_List.java======================
import java.io.*;

public class CDLL_List<T>
{
private CDLL_Node<T> head; // pointer to the front (first) element of the list
private int count=0;
//________________________________
public CDLL_List()
{
head = null; // compiler does this anyway. just for emphasis
}

// LOAD LINKED LIST FROM INCOMING FILE
//________________________________
@SuppressWarnings("unchecked")
public CDLL_List( String fileName, boolean orderedFlag )
{ head = null;
try
{
BufferedReader infile = new BufferedReader( new FileReader( fileName ) );
while ( infile.ready() )
{
if (orderedFlag)
insertInOrder( (T)infile.readLine() ); // WILL INSERT EACH ELEM INTO IT'S SORTED POSITION
else
insertAtTail( (T)infile.readLine() ); // TACK EVERY NEWELEM ONTO END OF LIST. ORIGINAL ORDER PRESERVED
}
infile.close();
}
catch( Exception e )
{
System.out.println( "FATAL ERROR CAUGHT IN C'TOR: " + e );
System.exit(0);
}
}
//________________________________
public void insertAtFront(T data)
{
   CDLL_Node<T> node=new CDLL_Node<T>(data);   
   if(head==null) {
       node.setNext(node);
       node.setPrev(node);
       head=node;
       return;
}
   node.setNext(head);
   node.setPrev(head.getPrev());
   head.getPrev().setNext(node);
   head.setPrev(node);
   head=node;

}
//________________________________
public void insertAtTail(T data)
{
   insertAtFront(data);
   head=head.getNext();
}
//________________________________
public T removeAtFront() // RETURNS TRUE IF THERE WAS NODE TO REMOVE
{
if(head==null)
   return null;
//only one item
if(head.getNext()==head.getPrev()) {
   T key=head.getData();
   head=null;
   return key;
}
T key=head.getData();
head.getNext().setPrev(head.getPrev());
head.getPrev().setNext(head.getNext());
head=head.getNext();
return key;
}
//________________________________
public boolean removeAtTail() // RETURNS TRUE IF THERE WAS NODE TO REMOVE
{
   if(head==null)
   return false;
//only one item
if(head.getNext()==head.getPrev()) {
   head=null;
   return true;
}
head=head.getPrev();
removeAtFront();
return true;
}
//________________________________
public String toString()
{
String toString = ""; // NO <=> DELIMITERS REQUIRED ANYWHERE IN OUTPUT
CDLL_Node<T> temp=head;
if(head==null)
   return toString;
//only one item
if(head.getNext()==head.getPrev()) {
   toString=toString+head.getData();
   return toString;
}
toString=toString+temp.getData()+" ";
temp=temp.getNext();
while(temp!=head) {
   toString=toString+temp.getData()+" ";
temp=temp.getNext();
}
return toString; // JUST A SPACE BETEEN ELEMENTS LIKE IN LAB3
}
//________________________________
public int size() // OF COURSE MORE EFFICIENT to KEEP COUNTER BUT YOU MUST WRITE LOOP
{
int count=0;
CDLL_Node<T> temp=head;
if(head==null)
   return count;
//only one item
if(head.getNext()==head.getPrev()) {
   count++;
   return count;
}
count++;
temp=temp.getNext();
while(temp!=head) {
   count++;
temp=temp.getNext();
}
return count;
}
//________________________________
public boolean empty()
{
return head==null; // YOUR CODE HERE
}
//________________________________
public boolean contains( T key )
{
   CDLL_Node<T> temp=head;
  
if(head==null)
   return false;
//only one item
if(head.getNext()==head.getPrev()) {
   if(key==head.getData())
       return true;
   else
       return false;
}
//check the first node
if(key==head.getData())
       return true;
//check rest of the nodes
temp=temp.getNext();
while(temp!=head) {
   if(key==head.getData())
       return true;
temp=temp.getNext();
}
return false; // YOUR CODE HERE
}
//________________________________
public CDLL_Node<T> search( T key )
{
   CDLL_Node<T> temp=head;
   if(head==null)
   return null;
   //only one item
if(head.getNext()==head.getPrev()) {
   if(key==head.getData())
       return temp;
   else
       return null;
}
//check the first node
if(key==temp.getData())
       return temp;
//check rest of the nodes
temp=temp.getNext();
while(temp!=head) {
   if(key==head.getData())
       return temp;
temp=temp.getNext();
}
return null; // YOUR CODE HERE
}
//________________________________
//@SuppressWarnings("unchecked") //CAST TO COMPARABLE THROWS WARNING
public void insertInOrder(T data)
{
if(head==null) {
   insertAtFront(data);
   return;
}
CDLL_Node<T> node=new CDLL_Node<T>(data);
CDLL_Node<T> temp=head;
if(head.getNext()==head.getPrev()) {
   if(data.toString().compareTo(head.getData().toString())<=0)
                       insertAtFront(data);
               else {
                   node.setNext(head.getNext());
                   node.setPrev(head);
                   head.setNext(node);
               }
               return;
}
do {
   if(data.toString().compareTo(temp.getData().toString())>=0 && data.toString().compareTo(temp.getNext().getData().toString())<0) {
       node.setNext(temp.getNext());
       node.setPrev(temp);
       temp.getNext().setPrev(node);
       temp.setNext(node);
       return;
   }
   temp=temp.getNext();
  
}while(temp!=head);
//insert at the tail of the list
insertAtTail(data);
}
//________________________________
public boolean remove(T key)
{
if(head==null)
   return false;
if(head.getData()==key) {
   removeAtFront();
   return true;
}
CDLL_Node<T> temp=head;
do {
   if(temp.getData()==key) {
       temp.getPrev().setNext(temp.getNext());
       temp.getNext().setPrev(temp.getPrev());
       return true;
   }
   temp=temp.getNext();
}while(temp!=head);
  
   return false; // REPLACE WITH YOUR CODE
}
//________________________________
public CDLL_List<T> union( CDLL_List<T> other )
{
CDLL_List<T> union = new CDLL_List<T>();
CDLL_List<T> tempList = new CDLL_List<T>();

if(!empty()) {
   CDLL_Node<T> temp=head;
   do {
       union.insertAtFront(temp.getData());
       temp=temp.getNext();
   }while(temp!=head);
}
while(!other.empty()) {
   T key=other.removeAtFront();
   if(union.contains(key)==false)
       union.insertAtFront(key);
   tempList.insertAtTail(key);
}
other=tempList;
return union;
}
//________________________________
public CDLL_List<T> inter( CDLL_List<T> other )
{
CDLL_List<T> inter = new CDLL_List<T>();

if(!empty()) {
    CDLL_Node<T> temp=head;
    do {
        if(other.contains(temp.getData())==true) {
            inter.insertAtFront(temp.getData());
        }
        temp=temp.getNext();
    }while(temp!=head);
}

return inter;
}
//________________________________
public CDLL_List<T> diff( CDLL_List<T> other )
{
CDLL_List<T> diff = new CDLL_List<T>();

if(!empty()) {
   CDLL_Node<T> temp=head;
   do {
       if(other.contains(temp.getData())==false) {
           diff.insertAtFront(temp.getData());
       }
       temp=temp.getNext();
   }while(temp!=head);
}

return diff;
}
//________________________________
       public int getCount() {
           size();
           return count;
       }
       //________________________________
}

//=====end of CDLL_List.java====================================

//============CDLL_Tester.java========================
public class CDLL_Tester
{
public static void main( String args[] ) throws Exception
{
CDLL_List<String> list1 = new CDLL_List<String>( args[0], false ); // false = INSERTATTAIL CALLED ON EACH T READ FROM FILE
System.out.format("list1 %s size %d unordered %s\n",args[0],list1.size(),list1 ); // invokes toString
  
list1.remove( "charlie" ); list1.remove("echo"); list1.remove("zebra"); // HEAD, TAIL, NOWHERE
System.out.format("list1 (after remove charlie, echo & zebra) %s\n",list1 ); // invokes toString
  
CDLL_List<String> list2 = new CDLL_List<String>( args[0], true ); // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
System.out.format("list2 %s size %d ordered %s\n",args[0],list2.size(),list2 ); // invokes toString

CDLL_List<String> list3 = new CDLL_List<String>( args[1], true ); // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
System.out.format("list3 %s size %d ordered %s\n",args[1],list3.size(),list3 ); // invokes toString   
  
// MUST RETURN ALL SET OP LISTS IN SORTED ORDER NO DUPES
CDLL_List<String> unionList = list2.union(list3);
System.out.println("list2.union(list3) " + unionList);
  
CDLL_List<String> interList = list2.inter(list3);
System.out.println("list2.inter(list3) " + interList);
  
CDLL_List<String> diffList = list2.diff(list3);   
System.out.println("list2.diff(list3) " + diffList);
  
  
// ECHO LISTS 2 & 3 TO PROVE THEY WERE NOT MODIFIED
  
System.out.println();
System.out.println( "list2 after set ops: " + list2 );
System.out.println( "list3 after set ops: " + list3 );
  
// DESTROY LIST2 BY REPEATEDLY CALLING REMOVE AT TAIL UNTIL EMPTY
while ( ! list2.empty() ) list2.removeAtTail();

// DESTROY LIST3 BY REPEATEDLY CALLING REMOVE AT FRONT
while ( ! list3.empty() ) list3.removeAtFront();
  
// ECHO LISTS 2 & 3 TO PROVE THEY WERE DESTROYED
  
System.out.println();
System.out.println( "list2 after all nodes removedAtTail: " + list2 );
System.out.println( "list3 after all nodes removedAtFront: " + list3 );
} // END MAIN
} // EOF
//===========end of CDLL_Tester.java=================

venereology answered 3 years ago
Next > < Previous

Related Solutions

public class StringNode { private String item; private StringNode next; } public class StringLL { private...
public class StringNode { private String item; private StringNode next; } public class StringLL { private StringNode head; private int size; public StringLL(){ head = null; size = 0; } public void add(String s){ add(size,s); } public boolean add(int index, String s){ ... } public String remove(int index){ ... } } In the above code add(int index, String s) creates a StringNode and adds it to the linked list at position index, and remove(int index) removes the StringNode at position...
public class Node<T> { Public T Item { get; set; } Public Node<T> Next; { get;...
public class Node<T> { Public T Item { get; set; } Public Node<T> Next; { get; set; } public Node (T item, Node<T> next) { … } } public class Polynomial { // A reference to the first node of a singly linked list private Node<Term> front; // Creates the polynomial 0 public Polynomial ( ) { } // Inserts term t into the current polynomial in its proper order // If a term with the same exponent already exists...
public class IntNode               {            private int data;            pri
public class IntNode               {            private int data;            private IntNode link;            public IntNode(int data, IntNode link){.. }            public int     getData( )          {.. }            public IntNode getLink( )           {.. }            public void    setData(int data)     {.. }            public void    setLink(IntNode link) {.. }         } All questions are based on the above class, and the following declaration.   // Declare an empty, singly linked list with a head and a tail reference. // you need to make sure that head always points to...
I have the following code: //Set.java import java.util.ArrayList; public class Set<T> { //data fields private ArrayList<T>...
I have the following code: //Set.java import java.util.ArrayList; public class Set<T> { //data fields private ArrayList<T> myList; // constructors Set(){ myList = new ArrayList<T>(); } // other methods public void add(T item){ if(!membership(item)) myList.add(item); } public void remove(T item){ if(membership(item)) myList.remove(item); } public Boolean membership(T item){ for (T t : myList) if (t.equals(item)) return true; return false; } public String toString(){ StringBuilder str = new StringBuilder("[ "); for(int i = 0; i < myList.size() - 1; i++) str.append(myList.get(i).toString()).append(", "); if(myList.size()...
Using this BubbleSort implementation in Java: public class BubbleSort<T extends Comparable<T>> {    private static <T...
Using this BubbleSort implementation in Java: public class BubbleSort<T extends Comparable<T>> {    private static <T extends Comparable<T>>    void swap(T[] data, int index1, int index2)    {       T temp = data[index1];       data[index1] = data[index2];       data[index2] = temp;    }    public void sort(T[] data)    {       int position, scan;       for (position = data.length - 1; position >= 0; position--)       {          for (scan = 0; scan <= position - 1; scan++)          {...
1. public class MyString { private char[] data; MyString(String string) { data = string.toCharArray(); } public...
1. public class MyString { private char[] data; MyString(String string) { data = string.toCharArray(); } public int compareTo(MyString other) { /* code from HW1 here */ } public char charAt(int i) { return data[i]; } public int length() { return data.length; } public int indexOf(char c) { /* code from HW1 here */ } public boolean equals(MyString other) { /* code from HW1 here */ } /* * Change this MyString by removing all occurrences of * the argument character...
public class SinglyLikedList {    private class Node{        public int item;        public...
public class SinglyLikedList {    private class Node{        public int item;        public Node next;        public Node(int item, Node next) {            this.item = item;            this.next = next;        }    }       private Node first;    public void addFirst(int a) {        first = new Node(a, first);    } } 1. Write the method add(int item, int position), which takes an item and a position, and...
3. Assume that binary trees are defined as public class BTNode<E> { private E data; private...
3. Assume that binary trees are defined as public class BTNode<E> { private E data; private BTNode<E> left, right; } We say that a binary tree t1 is a prefix of a binary tree t2 if t2 can be made identical to t1 by removing zero or more leaves of t2. Write a method
public class Clock { private int hr; private int min; private int sec; public Clock() {...
public class Clock { private int hr; private int min; private int sec; public Clock() { setTime(0, 0, 0); } public Clock(int hours, int minutes, int seconds) { setTime(hours, minutes, seconds); } public void setTime(int hours, int minutes, int seconds) { if (0 <= hours && hours < 24) hr = hours; else hr = 0; if (0 <= minutes && minutes < 60) min = minutes; else min = 0; if(0 <= seconds && seconds < 60) sec =...
Consider the following class definition:                   public class Parent {               private
Consider the following class definition:                   public class Parent {               private int varA;               protected double varB;               public Parent(int a, double b){ varA = a; varB = b;               }               public int sum( ){                    return varA + varB;               } public String toString( ){                    return "" + varA + "   " + varB;               }         } Consider that you want to extend Parent to Child. Child will have a third int instance data varC....
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT