001: // Copyright (c) 2003 Cunningham & Cunningham, Inc.
002: // Read license.txt in this directory.
003:
004: package eg;
005:
006: import fit.*;
007:
008: import java.util.*;
009:
010: public class BinaryChop extends ColumnFixture {
011:
012: // Test Fixture /////////////////////////////////
013:
014: public int key, array[];
015:
016: public void execute() {
017: int empty[] = {};
018: if (array == null)
019: array = empty;
020: }
021:
022: public int result() {
023: return chopFriday(key, array);
024: }
025:
026: public int mon() {
027: return chopMonday(key, array);
028: }
029:
030: public int tue() {
031: return chopTuesday(key, array);
032: }
033:
034: public int wed() {
035: return chopWednesday(key, array);
036: }
037:
038: public int thr() {
039: return chopThursday(key, array);
040: }
041:
042: public int fri() {
043: return chopFriday(key, array);
044: }
045:
046: // Search Methods ///////////////////////////////
047:
048: int chopMonday(int key, int array[]) {
049: int min = 0;
050: int max = array.length - 1;
051: while (min <= max) {
052: int probe = (min + max) / 2;
053: if (key == array[probe]) {
054: return probe;
055: } else if (key > array[probe]) {
056: min = probe + 1;
057: } else {
058: max = probe - 1;
059: }
060: }
061: return -1;
062: }
063:
064: int chopTuesday(int key, int array[]) {
065: int min = 0;
066: int max = array.length - 1;
067: while (min <= max) {
068: int probe = (min + max) / 2;
069: switch (new Integer(key)
070: .compareTo(new Integer(array[probe]))) {
071: case (0):
072: return probe;
073: case (1):
074: min = probe + 1;
075: break;
076: case (-1):
077: max = probe - 1;
078: break;
079: default:
080: throw new Error("unexpected result from compareTo");
081: }
082: }
083: return -1;
084: }
085:
086: int chopWednesday(int key, int array[]) {
087: if (array.length == 0)
088: return -1;
089: int probe = array.length / 2;
090: if (key == array[probe])
091: return probe;
092: if (key < array[probe])
093: return chopWednesday(key, subarray(array, 0, probe));
094: int result = chopWednesday(key, subarray(array, probe + 1,
095: array.length - (probe + 1)));
096: return result < 0 ? result : result + probe + 1;
097: }
098:
099: int chopThursday(int key, int array[]) {
100: int min = 0;
101: int max = array.length - 1;
102: Random gen = new Random();
103:
104: while (min <= max) {
105: int probe = (int) (gen.nextDouble() * (max - min)) + min;
106: if (key == array[probe]) {
107: return probe;
108: } else if (key > array[probe]) {
109: min = probe + 1;
110: } else {
111: max = probe - 1;
112: }
113: }
114: return -1;
115: }
116:
117: int chopFriday(int key, int array[]) {
118: for (int i = 0; i < array.length; i++) {
119: if (key == array[i])
120: return i;
121: }
122: return -1;
123: }
124:
125: // Utilities ////////////////////////////////////
126:
127: int[] subarray(int[] source, int pos, int length) {
128: int dest[] = new int[length];
129: for (int i = 0; i < length; i++)
130: dest[i] = source[pos + i];
131: return dest;
132: }
133:
134: }
|