Fix the compilation errors.

1 import java.util.Iterator; 2 import java.util.NoSuchElementException; 3 import java.util.Arrays; 4 5 /** 6 * ArraySet.java. 7 * 8 * Provides an implementation of the Set interface using an 9 * array as the underlying data structure. Values in the array 10 * are kept in ascending natural order and, where possible, 11 * methods take advantage of this. Many of the methods with parameters 12 * of type ArraySet are specifically designed to take advantage 13 * of the ordered array implementation. 14 * 15 * @version 2016-03-01 16 * 17 */ 18 public class ArraySet> implements Set { 19 20 //////////////////////////////////////////// 21 // DO NOT CHANGE THE FOLLOWING TWO FIELDS // 22 //////////////////////////////////////////// 23 T[] elements; 24 int size; 25 26 //////////////////////////////////// 27 // DO NOT CHANGE THIS CONSTRUCTOR // 28 //////////////////////////////////// 29 /** 30 * Instantiates an empty set. 31 */ 32 @SuppressWarnings("unchecked") 33 public ArraySet() { 34 elements = (T[]) new Comparable[1]; 35 size = 0; 36 } 37 38 @SuppressWarnings("unchecked") 39 private ArraySet(T[] a, int arraySize) { 40 elements = (T[]) new Comparable[arraySize]; 41 System.arraycopy(a, 0, elements, 0, arraySize); 42 size = arraySize; 43 } 44 45 46 47 /////////////////////////////////// 48 // DO NOT CHANGE THE SIZE METHOD // 49 /////////////////////////////////// 50 /** 51 * Returns the current size of this collection. 52 * 53 * @return the number of elements in this collection. 54 */ 55 public int size() { 56 return size; 57 } 58 59 ////////////////////////////////////// 60 // DO NOT CHANGE THE ISEMPTY METHOD // 61 ////////////////////////////////////// 62 /** 63 * Tests to see if this collection is empty. 64 * 65 * @return true if this collection contains no elements, 66 * false otherwise. 67 */ 68 public boolean isEmpty() { 69 return size == 0; 70 } 71 72 /////////////////////////////////////// 73 // DO NOT CHANGE THE TOSTRING METHOD // 74 /////////////////////////////////////// 75 /** 76 * Return a string representation of this ArraySet. 77 * 78 * @return a string representation of this ArraySet 79 */ 80 @Override 81 public String toString() { 82 if (isEmpty()) { 83 return "[]"; 84 } 85 StringBuilder result = new StringBuilder(); 86 result.append("["); 87 for (T element : this) { 88 result.append(element + ", "); 89 } 90 result.delete(result.length() - 2, result.length()); 91 result.append("]"); 92 return result.toString(); 93 } 94 95 private boolean isArraySetFull() { 96 if (size == elements.length) { 97 return true; 98 } 99 return false; 100 } 101 102 private void resizeArraySet(int c) { 103 T[] b = Arrays.copyOf(elements, c); 104 elements = b; 105 } 106 107 /** 108 * Ensures the collection contains the specified element. Elements are 109 * maintained in ascending natural order at all times. Neither duplicate nor 110 * null values are allowed. 111 * 112 * @param element The element whose presence is to be ensured. 113 * @return true if collection is changed, false otherwise. 114 */ 115 public boolean add(T element) { 116 if (this.contains(element)) { 117 return false; 118 } 119 if (isArraySetFull()) { 120 resizeArraySet(elements.length * 2); 121 } 122 123 int i = 0; 124 125 while (i < size && element.compareTo(elements) > 0) { 126 i++; 127 } 128 129 for (int a = size; i < a; a--) { 130 elements[a] = elements[a - 1]; 131 } 132 133 size++; 134 return true; 135 136 } 137 138 private int find(T element) { 139 int low = 0; 140 int mid = 0; 141 int high = size - 1; 142 143 while (low <= high) { 144 mid = (high + low) / 2; 145 int compareElements = elements[mid].compareTo(element); 146 if (compareElements > 0) { 147 high = mid - 1; 148 } 149 if (compareElements < 0) { 150 low = mid + 1; 151 } 152 else { 153 return mid; 154 } 155 } 156 return -1; 157 } 158 159 /** 160 * Ensures the collection does not contain the specified element. 161 * If the specified element is present, this method removes it 162 * from the collection. Elements are maintained in ascending natural 163 * order at all times. 164 * 165 * @param element The element to be removed. 166 * @return true if collection is changed, false otherwise. 167 */ 168 public boolean remove(T element) { 169 int i = find(element); 170 171 if (i >= size || i == -1) { 172 return false; 173 } 174 175 for (int b = i; b < size; b++) { 176 elements[b] = elements[b + 1]; 177 } 178 179 size--; 180 181 182 if (size > 0 && size < (elements.length / 4)) { 183 resizeArraySet(elements.length / 2); 184 } 185 186 return true; 187 } 188 189 /** 190 * Searches for specified element in this collection. 191 * 192 * @param element The element whose presence in this collection 193 * is to be tested. 194 * @return true if this collection contains the specified element, 195 * false otherwise. 196 */ 197 public boolean contains(T element) { 198 int i = 0; 199 while (this.size > i) { 200 if (!elements.equals(element)) { 201 i++; 202 } 203 204 if (i == size) { 205 break; 206 } 207 if (elements.equals(element)) { 208 return true; 209 } 210 211 212 } 213 return false; 214 } 215 216 /** 217 * Tests for equality between this set and the parameter set. 218 * Returns true if this set contains exactly the same elements 219 * as the parameter set, regardless of order. 220 * 221 * @return true if this set contains exactly the same elements 222 * as the parameter set, false otherwise 223 */ 224 public boolean equals(Set s) { 225 if (s.size() != this.size) { 226 return false; 227 } 228 229 for (int i = 0; i < this.size(); i++) { 230 if (!s.contains(elements)) { 231 return false; 232 } 233 } 234 235 return true; 236 } 237 238 /** 239 * Tests for equality between this set and the parameter set. 240 * Returns true if this set contains exactly the same elements 241 * as the parameter set, regardless of order. 242 * 243 * @return true if this set contains exactly the same elements 244 * as the parameter set, false otherwise 245 */ 246 public boolean equals(ArraySet s) { 247 if (s.size() != this.size) { 248 return false; 249 } 250 for (int i = 0; i < this.size; i++) { 251 if (s.elements.compareTo(this.elements) != 0) { 252 return false; 253 } 254 } 255 256 return true; 257 } 258 259 /** 260 * Returns a set that is the union of this set and the parameter set. 261 * 262 * @return a set that contains all the elements of this set and 263 * the parameter set 264 */ 265 public Set union(Set s) { 266 T[] list = Arrays.copyOf(elements, size); 267 ArraySet as = new ArraySet(); 268 for (T value : list) { 269 as.add(value); 270 } 271 272 if (s.isEmpty()) { 273 return as; 274 } 275 276 for (T value : s) { 277 as.add(value); 278 } 279 280 return as; 281 } 282 283 /** 284 * Returns a set that is the union of this set and the parameter set. 285 * 286 * @return a set that contains all the elements of this set and 287 * the parameter set 288 */ 289 public Set union(ArraySet s) { 290 T[] list = Arrays.copyOf(elements, size); 291 ArraySet as = new ArraySet(); 292 for (T value : list) { 293 as.add(value); 294 } 295 296 if (s.isEmpty()) { 297 return as; 298 } 299 300 for (T otherValue : s) { 301 as.add(otherValue); 302 } 303 return as; 304 } 305 306 /** 307 * Returns a set that is the intersection of this set 308 * and the parameter set. 309 * 310 * @return a set that contains elements that are in both 311 * this set and the parameter set 312 */ 313 @SuppressWarnings("unchecked") 314 public Set intersection(Set s) { 315 ArraySet as = new ArraySet(); 316 for (T value : elements) { 317 if (s.contains(value)) { 318 as.add(value); 319 } 320 } 321 return as; 322 } 323 324 /** 325 * Returns a set that is the intersection of this set and 326 * the parameter set. 327 * 328 * @return a set that contains elements that are in both 329 * this set and the parameter set 330 */ 331 public Set intersection(ArraySet s) { 332 ArraySet as = new ArraySet(); 333 for (T value : elements) { 334 if (s.contains(value)) { 335 as.add(value); 336 } 337 } 338 return as; 339 } 340 341 /** 342 * Returns a set that is the complement of this set and 343 * the parameter set. 344 * 345 * @return a set that contains elements that are in this 346 * set but not the parameter set 347 */ 348 public Set complement(Set s) { 349 if (s == null || s.isEmpty()) { 350 return this; 351 } 352 if (isEmpty()) { 353 return this; 354 } 355 if (this == null) { 356 return this; 357 } 358 359 ArraySet as = new ArraySet(); 360 361 for (T value : this) { 362 if (!s.contains(value)) { 363 as.add(value); 364 } 365 } 366 367 return as; 368 } 369 370 /** 371 * Returns a set that is the complement of this set and 372 * the parameter set. 373 * 374 * @return a set that contains elements that are in this 375 * set but not the parameter set 376 */ 377 @SuppressWarnings("unchecked") 378 public Set complement(ArraySet s) { 379 if (s == null || s.isEmpty()) { 380 return this; 381 } 382 if (isEmpty()) { 383 return this; 384 } 385 if (this == null) { 386 return this; 387 } 388 389 T[] output = (T[]) new Comparable[this.size + s.size]; 390 int i = 0; 391 int j = 0; 392 int k = 0; 393 int outputSize = 0; 394 395 while (i < s.size && j < this.size) { 396 if (this.elements[j].compareTo(s.elements) < 0) { 397 output[k++] = this.elements[j++]; 398 outputSize++; 399 } 400 else if (this.elements[j].compareTo(s.elements) > 0) { 401 i++; 402 } 403 else if (this.elements[j].compareTo(s.elements) == 0) { 404 j++; 405 } 406 } 407 408 ArraySet as = new ArraySet(output, outputSize); 409 as.size = outputSize; 410 411 return as; 412 } 413 414 private class MyIterator implements Iterator { 415 private T[] items; 416 private int count; 417 private int current; 418 419 public MyIterator(T[] elements, int size) { 420 items = elements; 421 count = size; 422 current = 0; 423 } 424 425 @Override 426 public boolean hasNext() { 427 return (current < count); 428 } 429 430 @Override 431 public T next() { 432 if (!hasNext()) { 433 throw new NoSuchElementException(); 434 } 435 return items[current++]; 436 } 437 438 @Override 439 public void remove() { 440 throw new UnsupportedOperationException(); 441 } 442 } 443 444 445 /** 446 * Returns an iterator over the elements in this ArraySet. 447 * No specific order can be assumed. 448 * 449 * @return an iterator over the elements in this ArraySet 450 */ 451 public Iterator iterator() { 452 return new MyIterator(elements, size); 453 } 454 455 private class DescendingIterator implements Iterator { 456 private T[] items; 457 private int count; 458 private int current; 459 460 public DescendingIterator(T[] elements, int size) { 461 items = elements; 462 count = 0; 463 current = size - 1; 464 } 465 466 @Override 467 public boolean hasNext() { 468 return (current >= count); 469 } 470 471 @Override 472 public T next() { 473 if (!hasNext()) { 474 throw new NoSuchElementException(); 475 } 476 477 return items[current--]; 478 } 479 480 @Override 481 public void remove() { 482 throw new UnsupportedOperationException(); 483 } 484 } 485 486 /** 487 * Returns an iterator over the elements in this ArraySet. 488 * The elements are returned in descending order. 489 * 490 * @return an iterator over the elements in this ArraySet 491 */ 492 public Iterator descendingIterator() { 493 return new DescendingIterator(elements, size()); 494 } 495 496 private class MyPowerSetIterator { 497 private T[] items; 498 private int count; 499 private int current; 500 private int b; 501 502 public MyPowerSetIterator(T[] elements, int size) { 503 items = elements; 504 count = size; 505 current = 0; 506 b = 0; 507 } 508 509 public boolean hasNext() { 510 return (current < (int) Math.pow(2, size)); 511 } 512 513 public Set next() { 514 Set output = new ArraySet(); 515 int a = 1; 516 for (int i = 0; i < size; i++) { 517 if ((b & a) != 0) { 518 output.add(elements); 519 } 520 } 521 current++; 522 b = 0; 523 return output; 524 } 525 526 public void remove() { 527 throw new UnsupportedOperationException(); 528 } 529 } 530 531 /** 532 * Returns an iterator over the members of the power set 533 * of this ArraySet. No specific order can be assumed. 534 * 535 * @return an iterator over members of the power set 536 */ 537 public Iterator> powerSetIterator() { 538 return null; 539 } 540 541 }

Compilation errors:

ArraySet.java:127: error: incompatible types: T[] cannot be converted to CAP#1 while (i < size && element.compareTo(elements) > 0) { ^ where T is a type-variable: T extends Comparable declared in class ArraySet where CAP#1 is a fresh type-variable: CAP#1 extends Object super: T from capture of ? super T ArraySet.java:232: error: incompatible types: T[] cannot be converted to T if (!s.contains(elements)) { ^ where T is a type-variable: T extends Comparable declared in class ArraySet ArraySet.java:253: error: cannot find symbol if (s.elements.compareTo(this.elements) != 0) { ^ symbol: method compareTo(T[]) location: variable elements of type T[] where T is a type-variable: T extends Comparable declared in class ArraySet ArraySet.java:398: error: incompatible types: T[] cannot be converted to CAP#1 if (this.elements[j].compareTo(s.elements) < 0) { ^ where T is a type-variable: T extends Comparable declared in class ArraySet where CAP#1 is a fresh type-variable: CAP#1 extends Object super: T from capture of ? super T ArraySet.java:402: error: incompatible types: T[] cannot be converted to CAP#1 else if (this.elements[j].compareTo(s.elements) > 0) { ^ where T is a type-variable: T extends Comparable declared in class ArraySet where CAP#1 is a fresh type-variable: CAP#1 extends Object super: T from capture of ? super T ArraySet.java:405: error: incompatible types: T[] cannot be converted to CAP#1 else if (this.elements[j].compareTo(s.elements) == 0) { ^ where T is a type-variable: T extends Comparable declared in class ArraySet where CAP#1 is a fresh type-variable: CAP#1 extends Object super: T from capture of ? super T ArraySet.java:520: error: incompatible types: T[] cannot be converted to T output.add(elements); ^ where T is a type-variable: T extends Comparable declared in class ArraySet Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output 7 errors