001 package lab1;
002 import java.util.*;
003
004 /**
005 * This is the file you will edit for this lab. It contains four functions,
006 * each of which is buggy.
007 */
008 public class BugRidden {
009 /**
010 * Does a binary search for <code>key</code> in a sorted List<Integer> <code>list
011 * </code> using the IntegerComparator <code>comp</code>
012 *
013 * This code contains three bugs. To find them, you may want to use
014 * breakpoints and monitor the local variables.
015 *
016 * @requires list != null && key != null && comp != null &&
017 * list is sorted in ascending order by comp
018 * @return an integer i such that list.get(i).equals(key),
019 * or -1 if no such index i exists.
020 */
021 public static int binarySearch(List<Integer> list, Integer key, IntegerComparator comp)
022 {
023 int low, mid, high, result;
024 low = 0;
025 high = list.size() - 1;
026 while (low < high) {
027 mid = (low + high)/2;
028 result = comp.compare(key, list.get(mid));
029 if (result == 0) { // key.equals(list.get(mid))
030 return mid;
031 } else if (result < 0) { // key < list.get(mid)
032 high = mid;
033 } else { // key > list.get(mid)
034 low = mid;
035 }
036 }
037 return -1;
038 }
039
040 /**
041 * Does a binary search for <code>key</code> in a sorted array <code>arr
042 * </code> using the IntegerComparator <code>comp</code>, limiting its search to
043 * the sub-array whose indices are <= low or >= high.
044 *
045 * This code contains three bugs. To find them, you may want to use
046 * breakpoints and monitor the local variables. This version of binarySearch
047 * is recursive, so you might want to try examining the stack traces.
048 *
049 * @requires arr != null && key != null && comp != null &&
050 * arr is sorted in ascending order by comp
051 * @return an integer i such that key.equals(arr[i]),
052 * or -1 if no such index i exists.
053 */
054 public static int binarySearch(Integer[] arr, Integer key, IntegerComparator comp, int low, int high)
055 {
056 int mid, result;
057 if (low > high) {
058 return -1;
059 }
060 mid = (low + high)/2;
061 result = comp.compare(arr[mid], key);
062 if (result == 0) { // key.equals(arr[mid])
063 return mid;
064 } else if (result < 0) { // key < arr[mid]
065 return BugRidden.binarySearch(arr, key, comp, low, mid);
066 } else { // key > arr[mid]
067 return BugRidden.binarySearch(arr, key, comp, mid, high);
068 }
069 }
070
071 /**
072 * Does a binary search for <code>key</code> in a sorted array <code>arr
073 * </code> using the Comparator <code>comp</code>
074 *
075 * @requires arr != null && key != null && comp != null &&
076 * arr is sorted in ascending order by comp
077 * @return an integer i such that key.equals(arr[i]),
078 * or -1 if no such index i exists.
079 */
080 public static int binarySearch(Integer[] arr, Integer key, IntegerComparator comp)
081 {
082 return BugRidden.binarySearch(arr, key, comp, 0, arr.length-1);
083 }
084
085 /**
086 * Removes each of the elements in the argument list, and puts them into
087 * a new array.
088 *
089 * This function contains two bugs that are easily found when looking at the
090 * values of the local variables during its execution.
091 *
092 * @effects: Empties l, and creates a new array arr that is a copy of l.
093 * @return: arr
094 */
095 public static Integer[] convertToArray(List<Integer> l)
096 {
097 Integer[] arr = new Integer[l.size()];
098 for (int i=0; i < l.size(); i++) {
099 arr[i] = l.remove(i);
100 }
101 return arr;
102 }
103
104 /**
105 * Returns the double 22.0
106 * @return 22.0
107 */
108 public static double return22(){
109 return 22.001;
110 }
111
112 }