Extending arrays

Figure 426. Lack of extendability Slide presentation
final String[] member = {"Eve", "John", "Peter", "Jill"};

final String newCourseMember = "Ernest";

member.length = 5; // Error: Size unchangeable

member[4] =  newCourseMember;

Figure 427. Extending an array Slide presentation
public static void main(String[] args) {
  String[] member = {"Eve", "John", "Peter", "Jill"};
  final String newMember = "Ernest";
  member = append(member, newMember);
}
static String[] append (final String[] values, final String newValue) {
  final String[] copy =  new String[values.length + 1];
  for (int i = 0; i < values.length; i++) { 
    copy[i] = values[i]; 
  }
  copy[copy.length - 1] = newValue; 
  return copy;
}

No final here: Reference will be re-assigned.

Assigning reference to enlarged array.

Creating an empty array capable of holding one more value.

Looping over existing values.

Assigning old values one by one to corresponding index positions.

Assigning new value to last index position before returning newly created array's reference.


Figure 428. Extension result Slide presentation
final String[] member = {"Eve", "John", "Peter", "Jill"};
System.out.println("Original array: " + Arrays.toString(member));
final String newMember = "Ernest";
member = append(member, newMember);
System.out.println("Extended array: " + Arrays.toString(member));
Original array: [Eve, John, Peter, Jill]
Extended array: [Eve, John, Peter, Jill, Ernest]

Figure 429. Using Arrays.copyOf() Slide presentation
public static void main(String[] args) {
    final int [] start = {1,7,-4},
    added = append(start, 77);
    System.out.println("added: " + Arrays.toString(added));
  }
static public int[] append(final int[] values, final int newValue) {
  final int[] result = Arrays.copyOf(values, values.length + 1);
  result[values.length] = newValue;
  return result;}

Result:

added: [1, 7, -4, 77]

exercise No. 149

Implementing append directly

Q:

We reconsider our append(...) method:

/**
 * <p>Create a new array consisting of given array values and new value at its end. Example:</p>
 *
 * <p>Given Array {1, 3, 0} and new value 77 results in {1, 3, 0, 77}. </p>
 *
 * @param values Given values
 * @param newValue Value to be appended
 * @return A new array prepending the input array values to the new value .
 */
static public int[] append(final int[] values, final int newValue) {
  final int[] result = Arrays.copyOf(values, values.length + 1);
  result[values.length] = newValue;
  return result;
}

Change the implementation. Do not use methods from Arrays but just for loops and other elementary Java constructs. Employ the following (minimal) unit test:

public class AppendTest {
  @Test
  public void appendTest() {
    Assert.assertArrayEquals(new int[]{1, 2, 5}, MyArray.append(new int[]{1, 2}, 5));
    Assert.assertArrayEquals(new int[]{6}, MyArray.append(new int[]{}, 6));
  }
}

A:

/**
 * <p>Create a new array consisting of given array values and new value at its end. Example:</p>
 *
 * <p>Given Array {1, 3, 0} and new value 77 results in {1, 3, 0, 77}. </p>
 *
 * @param values Given values
 * @param newValue Value to be appended
 * @return A new array prepending the input array values to the new value .
 */
static public int[] append(final int[] values, final int newValue) {
  final int[] result = new int[values.length + 1]; 
  for (int i = 0; i < values.length; i++) { 
    result[i] = values[i];
  }
  result[values.length] = newValue; 
  return result;
}

Create a new array by extending the given array's size by 1.

Copy the given array's values into the new array.

Copy the new int value to the last array element.

exercise No. 150

Purge duplicates

Q:

Consider the following int[] array:

final int[] values = {6, 1, 5, 1, 6, 1}

This array contains duplicates to be purged leaving us with a sorted result containing distinct values:

int[] result={1, 5, 6}

Implement a corresponding distinct(...) method:

/**
 * <p>Turn a list of value into a sorted set not containing any duplicates. Example:</p>
 *
 * <pre>{6, 1, 5, 1, 6, 1} to {1, 5, 6}</pre>
 *
 * <p>The array of input values is to be left untouched.</p>
 *
 * @param values Unsorted values possibly containing duplicates.
 * @return An ordered set of distinct values.
 */
public static int[] distinct (final int[] values) {
  ...
  return ...; // TODO: Implement me!
}

Use (at least) these unit tests:

@Test
public void testUnique() {
  unique(new int[]{});
  unique(new int[]{-11});
  unique(new int[]{1, 4});
  unique(new int[]{6, 1, 4});
  unique(new int[]{12, 6, 1, 4});
  unique(new int[]{-99, 4, 333, 17, 0, 3, 55});
}
@Test
public void testTwoDuplicate() {
  Assert.assertArrayEquals(new int[]{6}, MyArray.distinct(new int[]{6, 6}));
}
@Test
public void testThreeDuplicate() {
  Assert.assertArrayEquals(new int[]{-1, 6}, MyArray.distinct(new int[]{-1, 6, 6}));
  Assert.assertArrayEquals(new int[]{-1, 6}, MyArray.distinct(new int[]{6, -1, 6}));
  Assert.assertArrayEquals(new int[]{-1, 6}, MyArray.distinct(new int[]{6, 6, -1}));
}
@Test
public void testFourDuplicate() {
  Assert.assertArrayEquals(new int[]{-1, 3, 6}, MyArray.distinct(new int[]{-1, 6, 6, 3}));
  Assert.assertArrayEquals(new int[]{-1, 3, 6}, MyArray.distinct(new int[]{3, 6, -1, 6}));
  Assert.assertArrayEquals(new int[]{-1, 3, 6}, MyArray.distinct(new int[]{6, 6, 3, -1}));

  Assert.assertArrayEquals(new int[]{1, 6}, MyArray.distinct(new int[]{1, 6, 1, 6}));
  Assert.assertArrayEquals(new int[]{1, 6}, MyArray.distinct(new int[]{1, 6, 1, 6, 6, 6, 1 ,1, 6}));
}
static void unique(final int[] values) {
final int[] sortedValues = Arrays.copyOf(values, values.length);
  Arrays.sort(sortedValues);
  Assert.assertArrayEquals(sortedValues, MyArray.distinct(values));
}

Tip

You may follow these steps:

  1. Create a copy of incoming array.

  2. Sort the copied array.

  3. Loop over the sorted values. Due to sorting duplicates now appear in sequence:

    {1, 1, 1, 5, 6, 6}

    You may create a secondary array holding only distinct index values. In the given example this would contain index values {0, 3, 4} with respect to above array example.

  4. Create a result array containing only distinct values:

    {1, 5, 6}

A:

Following the steps outlined in the hints we may:

public class MyArray {

  /**
   * <p>Turn a list of values into a sorted set not containing any duplicates. Example:</p>
   *
   * <pre>{6, 1, 5, 1, 6, 1} to {1, 5, 6}</pre>
   *
   * <p>The array of input values is to be left untouched.</p>
   *
   * @param values Unsorted values possibly containing duplicates.
   * @return An ordered set of distinct values.
   */
  public static int[] distinct (final int[] values) {

    if (0 == values.length) {
      return values; // Special case: Empty array
    }

    // Step 1: Cloning incoming array
    final int[] sortedValues = Arrays.copyOf(values, values.length);

    // Step 2: Sort copied array.
    Arrays.sort(sortedValues);

    // Step 3: Create helper array containing distinct index positions
    final int[] uniqueValuesIndex = new int[values.length];
    int uniqueValueIndexTop = 0;
    uniqueValuesIndex[uniqueValueIndexTop++] = 0; // Include first array element unconditionally

    for (int i = 1; i < sortedValues.length; i++) {
      if (sortedValues[i - 1] != sortedValues[i]) { // current value different from predecessor?
        uniqueValuesIndex[uniqueValueIndexTop++] = i; // Add to set of distinct index values
      }
    }
    // Step 4: Create and copy to result array
    final int[] result = new int[uniqueValueIndexTop]; // We found uniqueValueIndexTop distinct values


    for (int i = 0; i < uniqueValueIndexTop; i++) { // Copy distinct values to result array
      result[i] = sortedValues[uniqueValuesIndex[i]];
    }
    return result;
  }
}