Extending arrays

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

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

member[4] =  "Ernest";

Figure 420. Extend array using a block Slide presentation
Code 
String[] member = {"Eve", "John", "Peter", "Jill"};

  {
    String[] memberCopy = new String[member.length + 1];

    for (int i = 0; i < member.length; i++) {
      memberCopy[i] = member[i];
    }
    memberCopy[member.length] = "Ernest";
    member = memberCopy;  // Switching to new array, releasing old
  }

IO.println(Arrays.toString(member));
Result 
[Eve, John, Peter, Jill, Ernest]

Figure 421. Replacing extending block by method Slide presentation 
void main() {
 ❶ String[] member = {"Eve", "John", "Peter", "Jill"};

  member ❷= append(member, "Ernest");
}

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[values.length] = 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 422. Extension result Slide presentation
Code 
final String[] member = {"Eve", "John", "Peter", "Jill"};
IO.println("Original array: " + Arrays.toString(member));
member = append(member, "Ernest");
IO.println("Extended array: " + Arrays.toString(member));
Result 
Original array: [Eve, John, Peter, Jill]
Extended array: [Eve, John, Peter, Jill, Ernest]

Figure 423. Replacing copying loop by Arrays.copyOf() Slide presentation
Code 
void main() {
    final int [] start = {1, 7, -4},
    start = append(start, 77);
    IO.println("added: " + Arrays.toString(start));
}

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. 157

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() {
    Assertions.assertArrayEquals(new int[]{1, 2, 5}, MyArray.append(new int[]{1, 2}, 5));
    Assertions.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. 158

Purging 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() {
  Assertions.assertArrayEquals(new int[]{6}, MyArray.distinct(new int[]{6, 6}));
}
@Test
public void testThreeDuplicate() {
  Assertions.assertArrayEquals(new int[]{-1, 6}, MyArray.distinct(new int[]{-1, 6, 6}));
  Assertions.assertArrayEquals(new int[]{-1, 6}, MyArray.distinct(new int[]{6, -1, 6}));
  Assertions.assertArrayEquals(new int[]{-1, 6}, MyArray.distinct(new int[]{6, 6, -1}));
}
@Test
public void testFourDuplicate() {
  Assertions.assertArrayEquals(new int[]{-1, 3, 6}, MyArray.distinct(new int[]{-1, 6, 6, 3}));
  Assertions.assertArrayEquals(new int[]{-1, 3, 6}, MyArray.distinct(new int[]{3, 6, -1, 6}));
  Assertions.assertArrayEquals(new int[]{-1, 3, 6}, MyArray.distinct(new int[]{6, 6, 3, -1}));

  Assertions.assertArrayEquals(new int[]{1, 6}, MyArray.distinct(new int[]{1, 6, 1, 6}));
  Assertions.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);
  Assertions.assertArrayEquals(sortedValues, MyArray.distinct(values));
}

Tip

You may follow these steps:

  1. Create a copy of the »incoming« array.

  2. Sort the copied array using Arrays.sort(int[]).

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

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

    Derive a secondary array holding index values of distinct array values. In the given example this array of indexes would contain {0, 3, 4} corresponding to {1, 5, 6} in the above array.

  4. Use this array of indexes to create the final result: 

    {1, 5, 6}

A:

Following the steps outlined in the hints we may:

/**
 * <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 input array 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;
}
Prev  Up  Next
java.util.Arrays helpers  Home  Storing integer values