By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,737 Members | 1,989 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,737 IT Pros & Developers. It's quick & easy.

need assistance

P: 28
The others classes


Expand|Select|Wrap|Line Numbers
  1. public class OrderedArrayList extends ArrayListClass
  2. {
  3.         //default constructor
  4.     public OrderedArrayList()
  5.     {
  6.         super();
  7.     }
  8.  
  9.         //constructor with a parameter
  10.     public OrderedArrayList(int size)
  11.     {
  12.         super(size);
  13.     }
  14.  
  15.         //copy constructor
  16.     public OrderedArrayList(OrderedArrayList otherList)
  17.     {
  18.         super(otherList);
  19.     }
  20.  
  21.  
  22.         //Method to insert insertItem in the list at the proper
  23.         //place. However, first the list is searched to
  24.         //see if the item to be inserted is already in the list.
  25.         //Postcondition: insertItem is inserted and length++
  26.         //           If insertItem is already in the list or the list
  27.         //           is full, an appropriate message is output.
  28.     public void insert(DataElement insertItem)
  29.     {
  30.         int first = 0;
  31.         int last = length - 1;
  32.         int mid = 0;
  33.  
  34.         boolean found = false;
  35.  
  36.         if(length == 0)   //list is empty
  37.         {
  38.             list[0] = insertItem.getCopy();
  39.             length++;
  40.         }
  41.         else
  42.             if(length == maxSize)
  43.                 System.err.println("Cannot insert into a full list.");
  44.             else
  45.             {
  46.                 while(first <= last && !found)
  47.                 {
  48.                     mid = (first + last) / 2;
  49.  
  50.                     if(list[mid].equals(insertItem))
  51.                         found = true;
  52.                     else
  53.                         if(list[mid].compareTo(insertItem) > 0)
  54.                             last = mid - 1;
  55.                         else
  56.                             first = mid + 1;
  57.                 }//end while
  58.  
  59.                 if(found)
  60.                     System.err.println("The insert item is already in the list. "
  61.                                      + "Duplicates are not allowed.");
  62.                 else
  63.                 {
  64.                     if(list[mid].compareTo(insertItem) < 0)
  65.                         mid++;
  66.  
  67.                     insertAt(mid, insertItem);
  68.                 }
  69.             }
  70.     }//end insert
  71.  
  72.  
  73.     public int binarySearch(DataElement[] list, DataElement item)
  74.     {
  75.         return binarySearch(list, item, 0, list.length - 1);
  76.      }
  77.  
  78.      private int binarySearch(DataElement[] list, DataElement item, int first, int last)
  79.     {
  80.         if (first > last)
  81.         return -1;        //base case for unsuccessful search
  82.  
  83.             int mid = (first + last) / 2;  //index for next probe
  84.  
  85.             if (list[mid].compareTo(item) < 0)
  86.             return binarySearch(list, item, first, mid + 1);   //base case for successful search
  87.             else
  88.                 if (list[mid].compareTo(item) > 0)
  89.  
  90.             return binarySearch(list, item, first, mid -1);
  91.  
  92.             else
  93.  
  94.             return mid;
  95.  
  96.     }
  97.  
  98. }//end binarySearch
  99.  
  100.  
  101.  
  102. public class IntElement extends DataElement
  103. {
  104.     protected int num;
  105.  
  106.       //default constructor
  107.     public IntElement()
  108.     {
  109.         num = 0;
  110.     }
  111.  
  112.       //constructor with a parameter
  113.     public IntElement(int x)
  114.     {
  115.         num = x;
  116.     }
  117.       //copy constructor
  118.     public IntElement(IntElement otherElement)
  119.     {
  120.         num = otherElement.num;
  121.     }
  122.  
  123.       //Method to set the value of the instance variable num.
  124.       //Postcondition: num = x;
  125.     public void setNum(int x)
  126.     {
  127.         num = x;
  128.     }
  129.  
  130.       //Method to return the value of the instance variable num.
  131.       //Postcondition: The value of num is returned.
  132.     public int getNum()
  133.     {
  134.         return num;
  135.     }
  136.  
  137.     public boolean equals(DataElement otherElement)
  138.     {
  139.         IntElement temp = (IntElement) otherElement;
  140.         return (num == temp.num);
  141.     }
  142.  
  143.     public int compareTo(DataElement otherElement)
  144.     {
  145.         IntElement temp = (IntElement) otherElement;
  146.         return (num - temp.num);
  147.     }
  148.  
  149.     public void makeCopy(DataElement otherElement)
  150.     {
  151.         IntElement temp = (IntElement) otherElement;
  152.         num = temp.num;
  153.     }
  154.  
  155.     public DataElement getCopy()
  156.     {
  157.         IntElement temp = new IntElement(num);
  158.         return temp;
  159.     }
  160.  
  161.     public String toString()
  162.     {
  163.         return String.valueOf(num);
  164.     }
  165. }
  166.  
  167.  
  168.  
  169. public abstract class DataElement
  170. {
  171.     public abstract boolean equals(DataElement otherElement);
  172.       //Method to determine whether two objects contain the 
  173.       //same data.
  174.       //Postcondition: Returns true if this object contains the 
  175.       //               same data as the object otherElement;
  176.       //               otherwise, it returns false.
  177.  
  178.     public abstract int compareTo(DataElement otherElement);
  179.       //Method to compare two objects.
  180.       //Postcondition: Returns a value < 0 if this object is 
  181.       //                    less than the object otherElement;
  182.       //               Returns 0 if this object is the same as 
  183.       //                    the object otherElement.
  184.       //               Returns a value > 0 if this object is 
  185.       //                  greater than the object otherElement.
  186.  
  187.     public abstract void makeCopy(DataElement otherElement);
  188.       //Method to copy otherElement into this object.
  189.       //Postcondition: The data of otherElement is copied into
  190.       //               this object.
  191.  
  192.     public abstract DataElement getCopy();
  193.       //Method to return a copy of this object.
  194.       //Postcondition: A copy of this object is created and
  195.       //               a reference of the copy is returned.
  196. }
  197.  
  198.  
  199.  
  200.  
  201. import java.io.*;
  202. import java.util.*;
  203.  
  204. public class TestProgRecursiveBinarySearch
  205. {
  206.     static BufferedReader keyboard = new
  207.            BufferedReader(new InputStreamReader(System.in));
  208.  
  209.     public static void main(String[] args) throws IOException
  210.     {
  211.         OrderedArrayList intList
  212.                           = new OrderedArrayList();
  213.         OrderedArrayList temp =
  214.                             new OrderedArrayList();
  215.  
  216.         IntElement num = new IntElement();
  217.  
  218.         int counter;
  219.         int position;
  220.  
  221.         StringTokenizer tokenizer;
  222.  
  223.         System.out.print("Enter 16 integers on the " + "same line: ");
  224.  
  225.         System.out.flush();
  226.  
  227.         tokenizer = new
  228.                    StringTokenizer(keyboard.readLine());
  229.  
  230.         for(counter = 0; counter < 16; counter++)
  231.         {
  232.             num.setNum(Integer.parseInt(tokenizer.nextToken()));
  233.             intList.insert(num);
  234.         }
  235.  
  236.         temp.copyList(intList);
  237.  
  238.         System.out.println();
  239.         System.out.print("The list you " + "entered is: ");
  240.         intList.print();
  241.         System.out.println();
  242.  
  243.         System.out.print("Enter the num to " + "be deleted: ");
  244.         System.out.flush();
  245.         num.setNum(Integer.parseInt(keyboard.readLine()));
  246.         System.out.println();
  247.  
  248.         System.out.print("Enter the position of " + "the num to be deleted: ");
  249.         System.out.flush();
  250.         position = Integer.parseInt(keyboard.readLine());
  251.         System.out.println();
  252.  
  253.         intList.removeAt(position);
  254.         System.out.println("After removing the " + "element at position "
  255.                           + position
  256.                           + ", intList:");
  257.  
  258.         intList.print();
  259.  
  260.         System.out.println();
  261.  
  262.         System.out.print("Enter the search " +  "item: ");
  263.         System.out.flush();
  264.  
  265.         num.setNum(Integer.parseInt(keyboard.readLine()));
  266.         System.out.println();
  267.  
  268.           for (int i = 0; i < 16; i++)
  269.  
  270.           System.out.println("Item found" + i + " at " + binarySearch(intList  num));        
  271.  
  272.  
  273.     }
  274. }
Nov 21 '06 #1
Share this question for a faster answer!
Share on Google+

Post your reply

Sign in to post your reply or Sign up for a free account.