1
/** Holds an ascending sequence, and provides various handy methods
2
  * to initialise and manipulate the sequence.
3
  *
4
  * The sequence can vary in length, up to a maximum capacity max.
5
  *
6
  * The datatype invariant for this ascending sequence is as follows:
7
  *     0 <= size <= max
8
  *     and for all j in the range 1 to size-1,  a[j-1] <= a[j]
9
  *
10
  */
11
public class AscendingSequence {
12
    private int[] a;  // note the datatype invariant above
13
    private int max;  // for storing the maximum length of the sequence
14
    private int size; // the current length of the sequence
15

16
    /** Constructs an empty ascending sequence.
17
      *
18
      * @param max   the max capacity of this sequence
19
      * @pre         max >= 0
20
      * @post        empty ascending sequence of capacity max has been created
21
      */
22
    public AscendingSequence(int max) {
23
        this.max = max;
24
        a = new int[max];
25
        size = 0;
26
    }
27

28
    /** Inserts an integer into the correct place in the sequence.
29
      *
30
      * @param x   the integer to be inserted
31
      * @pre       size != max
32
      * @post      x has been inserted into correct place in a
33
      */
34
    public void insert(int x) {
35
        assert size != max;
36
        int i = size;
37
        while (i != 0 && a[i - 1] > x) {
38
            a[i] = a[i - 1];
39
            i--;
40
        }
41
        assert i == 0 || a[i - 1] <= x;
42
        a[i] = x;
43
        size++;
44
    }
45

46
    /** Empties the sequence.
47
      *
48
      * @pre   true
49
      * @post  sequence is now empty
50
      */
51
    public void clear() {
52
        size = 0;
53
    }
54

55
    /** Inserts all integers from an array into the sequence.
56
      *
57
      * @param xs    the array containing the integers to insert
58
      * @pre         size + xs.length <= max
59
      * @post        all integers from xs have been inserted into the correct places in a
60
      */
61
    public void insertLots(int[] xs) {
62
        assert size + xs.length <= max;
63
        int i = 0;
64
        while (i != xs.length) {
65
            this.insert(xs[i]);
66
            i++;
67
        }
68
    }
69

70
    /** Removes the element at a given position.
71
      *
72
      * @param i     the index from which to remove the element
73
      * @pre         0 <= i && i < size
74
      * @post        element at position i has been removed from a
75
      */
76
    public void remove(int i) {
77
        assert 0 <= i && i < size;
78
        while (i < size - 1) {
79
            a[i] = a[i + 1];
80
            i++;
81
        }
82
        size--;
83
    }
84

85
    /** Returns a string representation of this sequence.
86
      *
87
      * @pre    true
88
      * @post   returned value is string representation of this
89
      * @return a string representation of this sequence
90
      */
91
    public String toString() {
92
        int i = 0;
93
        String out = "[";
94
        while (i < size - 1) {
95
            out += a[i] + ", ";
96
            i++;
97
        }
98
        if (i == size - 1) {
99
            out += a[i];
100
        }
101
        return out + "]";
102
    }
103

104
    /** Returns a string representation of the entire array, not just
105
      * the sequence within the array.
106
      *
107
      * @pre     true
108
      * @post    returned value is string representation of entire array
109
      * @return  a string representation of the entire array
110
      */
111
    public String containerArrayAsString() {
112
        int i;
113
        String out;
114
        i = 0;
115
        out = "Container array: max=" + max + " and size=" + size + "\n [";
116
        while (i < max - 1) {
117
            out += a[i] + ", ";
118
            i++;
119
        }
120
        if (i == max - 1) {
121
            out += a[i];
122
        }
123
        return out + "]";
124
    }
125

126
    /* Searches for a given value in the sequence.
127
     *
128
     * @param val   the value to search for in the sequence
129
     * @pre         true
130
     * @post        the return value indicates whether val is in the sequence
131
     * @return      true precisely when the sought value is in the sequence
132
     */
133
    /*
134
    public boolean search(int val) {
135
    // uses a binary search to look for the value
136

137
        int low = 0;
138
        int high = size-1;
139
        int middle = -1;
140
        boolean found = false;
141

142
        while (!found && low < high) {
143
            middle = low + (high-low)/2;
144
            if (a[middle]==val)
145
               found = true;
146
            else if (a[middle] < val)
147
               low = middle + 1;
148
            else // (a[middle] > val)
149
               high = middle - 1;
150
        }
151
        return found;
152
    }
153
    */
154
    public int search(int val) {
155
        // uses a binary search to look for the value
156

157
        int low = 0;
158
        int high = size-1;
159
        int num, middle;
160

161
        while (low <= high) { // Pay attention to <=
162
            middle = low + (high-low)/2;
163
            num = a[middle];
164
            if (num == val) {
165
                return middle;
166
            }
167
            else if (num < val)
168
                low = middle + 1;
169
            else // (a[middle] > val)
170
                high = middle - 1;
171
        }
172
        return -1;
173
    }
174
}

1
/** A class for testing a binary search method.
2
  *
3
  *
4
  */
5
public class Tester {
6
    /** Carries out tests on a binary search method in the AscendingSequences class.
7
     *
8
     * @param args not used
9
     */
10
    public static void main(String[] args) {
11
        // First need to set up a sequence with some data:
12
        AscendingSequence as = new AscendingSequence(25);
13
        System.out.println("Adding some elements to the sequence:");
14
        int[] somexs = {7, 4, 6, 3, 20, -12, -5};
15
        as.insertLots(somexs);
16
        System.out.println(as);
17
        // Now to a test with this particular sequence:
18
        System.out.println("Can the binary search find the middle element?");
19
        System.out.println("Result of search for 4: " + as.search(4));
20
        // Now do some more tests of your own. Include at least six examples.
21
    // Remember that you can clear the sequence and insertLots to make a new sequence to test
22
    // You can search also for elements that have been deleted etc
23
        System.out.println("Can the binary search find the first element?");
24
        System.out.println("Result of search for -12: " + as.search(-12));
25
        System.out.println("Can the binary search find the last element?");
26
        System.out.println("Result of search for 20: " + as.search(20));
27
        System.out.println("Can the binary search find an element that is not in the sequence?");
28
        System.out.println("Result of search for 0: " + as.search(0));
29
    }
30
}