Computer Science 15-110, Spring 2010
Class Notes:  One-Dimensional Arrays

1. Part 1
   1. Allocation
      1. Fixed-Size Array
      2. Variable-Sized Array
      3. Statically-Allocated Array
      4. Statically-Reallocated Array
   2. Default Values
   3. Array Parameters
      1. Simple Case
      2. Modifying array contents is visible to caller
      3. Modifying array reference is not visible to caller
   4. Array Return Types
   5. Traversal
      1. Forward Traversal
      2. Backward Traversal
      3. Alternative Backward Traversal
   6. Arrays Methods
      1. equals
      2. toString
      3. fill
      4. sort
      5. Online Arrays API
2. Part 2
   1. Swap
      1. Broken Swap
      2. Working Swap
   2. Copy
      1. Broken Copy
      2. Working Copy
   3. Equals
      1. Broken Equals
      2. Working Equals
   4. Insertion
   5. Deletion
   6. Examples
      1. The Locker Problem
      2. Anagrams

One-Dimensional Arrays

1. Part 1
    
   1. Allocation
       
      1. Fixed-Size Array

         import java.util.Scanner;
         class MyCode {
           public static void main(String[] args) {
             Scanner scanner = new Scanner(System.in);
             int[] a = new int[5];

             System.out.print("Enter 5 integers: ");
             for (int i=0; i<5; i++)
               a[i] = scanner.nextInt();

             System.out.println("Here are the 5 integers in reverse:");
             for (int i=4; i>=0; i--)
               System.out.println(a[i]);
           }
         }

      2. Variable-Sized Array

         import java.util.Scanner;
         class MyCode {
           public static void main(String[] args) {
             Scanner scanner = new Scanner(System.in);
             System.out.print("Enter # of integers: ");
             int n = scanner.nextInt();

             int[] a = new int[n];

             System.out.print("Enter " + n + " integers: ");
             for (int i=0; i<n; i++)
               a[i] = scanner.nextInt();

             System.out.println("Here are the " + n + " integers in reverse:");
             for (int i=n-1; i>=0; i--)
               System.out.println(a[i]);
           }
         }

      3. Statically-Allocated Array

         class MyCode {
           public static void main(String[] args) {
             int[] a = { 5, 2, 1, 3, 6, 4 };
             int n = a.length;

             System.out.println("Here are the " + n + " integers in reverse:");
             for (int i=n-1; i>=0; i--)
               System.out.println(a[i]);
           }
         }
         
         Or:

         class MyCode {
           public static void main(String[] args) {
             int[] a = new int[] {5, 2, 1, 3, 6, 4 };
             int n = a.length;

             System.out.println("Here are the " + n + " integers in reverse:");
             for (int i=n-1; i>=0; i--)
               System.out.println(a[i]);
           }
         }

      4. Statically-Reallocated Array

         class MyCode {
           public static void main(String[] args) {
             int[] a = { 5, 2, 1, 3, 6, 4 };
         
             // now reallocate the array
             a = { 1, 3, 5 };  // WILL NOT COMPILE!
         
             int n = a.length;
             System.out.println("Here are the " + n + " integers in reverse:");
             for (int i=n-1; i>=0; i--)
               System.out.println(a[i]);
           }
         }
         
         Fixed:

         class MyCode {
           public static void main(String[] args) {
             int[] a = { 5, 2, 1, 3, 6, 4 };
         
             // now reallocate the array
             a = new int[]{1, 3, 5 };  // Works!!!
         
             int n = a.length;
             System.out.println("Here are the " + n + " integers in reverse:");
             for (int i=n-1; i>=0; i--)
               System.out.println(a[i]);
           }
         }

   2. Default Values
      
      import java.util.Scanner;
      class MyCode {
        public static void main(String[] args) {
          int[] ai = new int[1];
          double[] ad = new double[1];
          boolean[] ab = new boolean[1];
          char[] ac = new char[1];
          String[] as = new String[1];
          System.out.println("Array default values for:");
          System.out.println("  int:     " + ai[0]);
          System.out.println("  double:  " + ad[0]);
          System.out.println("  boolean: " + ab[0]);
          System.out.println("  char:    (Unicode " + (int)ac[0] + ")");
          System.out.println("  String:  " + as[0]);
        }
      }
       
   3. Array Parameters
       
      1. Simple Case

         class MyCode {
           public static void printInReverse(int[] a) {
             int n = a.length;
             System.out.println("Here are the " + n + " integers in reverse:");
             for (int i=n-1; i>=0; i--)
               System.out.println(a[i]);
           }

           public static void main(String[] args) {
             int[] a = { 5, 2, 1, 3, 6, 4 };
             printInReverse(a);
           }
         }

      2. Modifying array contents is visible to caller

         class MyCode {
           public static void modifyArrayContents(int[] a) {
              a[0] = 99;  // this change IS visible to caller!
           }
           
           public static void print(int[] a) {
              for (int i=0; i<a.length; i++) System.out.print(a[i] + " ");
              System.out.println();
           }
           
           public static void main(String[] args) {
             int[] a = { 1, 2, 3 };
             print(a); // prints 1, 2, 3
             modifyArrayContents(a); // works as expected
             print(a); // prints 99, 2, 3
           }
         }

      3. Modifying array reference is not visible to caller

         class MyCode {
           public static void modifyArrayReference(int[] a) {
              a = new int[]{ 99, 100 };  // this change IS NOT visible to caller!
           }  
         
           public static void print(int[] a) {
              for (int i=0; i<a.length; i++) System.out.print(a[i] + " ");
              System.out.println();
           }  
         
           public static void main(String[] args) {
             int[] a = { 1, 2, 3 };
             print(a); // prints 1, 2, 3
             modifyArrayReference(a); // does NOT work as expected
             print(a); // prints 1, 2, 3
           }
         }

   4. Array Return Types
      
      import java.util.*;
      class MyCode {
        public static final Random random = new Random();
        public static int[] getArrayOfRandoms(int n) {
          int[] a = new int[n];
          for (int i=0; i<n; i++)
            a[i] = random.nextInt(100);
          return a;
        }
        public static void main(String[] args) {
          int[] a = getArrayOfRandoms(10);
          System.out.println("Here are the randoms: ");
          for (int i=0; i<a.length; i++)
            System.out.println(a[i]);
        }
      }
       
   5. Traversal
       
      1. Forward Traversal

         class MyCode {
           public static void main(String[] args) {
             int[] a = { 3, 2, 4, 1 };
             System.out.println("Forward Traversal:");
             for (int i=0; i<a.length; i++)
               System.out.println(a[i]);
           }
         }

      2. Backward Traversal

         class MyCode {
           public static void main(String[] args) {
             int[] a = { 3, 2, 4, 1 };
             System.out.println("Backward Traversal:");
             for (int i=a.length-1; i>=0; i--)
               System.out.println(a[i]);
           }
         }

      3. Alternative Backward Traversal

         class MyCode {
           public static void main(String[] args) {
             int[] a = { 3, 2, 4, 1 };
             System.out.println("Alternative Backward Traversal:");
             for (int i=0; i<a.length; i++)
               System.out.println(a[(a.length-1)-i]);
           }
         }

   6. Arrays Methods
       
      1. equals

         import java.util.Arrays;
         class MyCode {
           public static void main(String[] args) {
             int[] a = { 3, 4, 2, 1 };
             int[] b = { 3, 4, 2, 1 };
             int[] c = { 3, 4, 2 };
             System.out.println(Arrays.equals(a, b));
             System.out.println(Arrays.equals(a, c));
           }
         }

      2. toString

         import java.util.Arrays;
         class MyCode {
           public static void main(String[] args) {
             int[] a = { 3, 4, 2, 1 };
             System.out.println(a);  // surprised?
             System.out.println(Arrays.toString(a));
           }
         }

      3. fill

         import java.util.Arrays;
         class MyCode {
           public static void main(String[] args) {
             int[] a = { 3, 4, 2, 1 };
             System.out.println(Arrays.toString(a));
             Arrays.fill(a, 9);
             System.out.println(Arrays.toString(a));
           }
         }

      4. sort

         import java.util.Arrays;
         class MyCode {
           public static void main(String[] args) {
             int[] a = { 3, 4, 2, 1 };
             System.out.println(Arrays.toString(a));
             Arrays.sort(a);
             System.out.println(Arrays.toString(a));
           }
         }

      5. Online Arrays API
         http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html
          
2. Part 2
    
   1. Swap
       
      1. Broken Swap

         import java.util.Arrays;
         class MyCode {
           public static void brokenSwap(int x, int y) {
             int temp = x;
             x = y;
             y = temp;
           }
           public static void main(String[] args) {
             int[] a = { 3, 4, 2, 1 };
             System.out.println(Arrays.toString(a));
             brokenSwap(a[0], a[1]);
             System.out.println(Arrays.toString(a));
           }
         }

      2. Working Swap

         import java.util.Arrays;
         class MyCode {
           public static void swap(int[] a, int i, int j) {
             int temp = a[i];
             a[i] = a[j];
             a[j] = temp;
           }
           public static void main(String[] args) {
             int[] a = { 3, 4, 2, 1 };
             System.out.println(Arrays.toString(a));
             swap(a,0,1);
             System.out.println(Arrays.toString(a));
           }
         }

   2. Copy
       
      1. Broken Copy

         import java.util.Arrays;
         class MyCode {
           public static void main(String[] args) {
             int[] a = { 1, 2, 3};
             int[] copy = a; // BROKEN!!!  Not a COPY of a!

             // After we copy the array, we change the original
             // and the copy, but what happens...?
             a[0] = 99;
             copy[1] = -99;

             System.out.println(Arrays.toString(a));
             System.out.println(Arrays.toString(copy));
           }
         }

      2. Working Copy

         import java.util.Arrays;
         class MyCode {
           public static int[] copy(int[] a) {
             int[] copy = new int[a.length];
             for (int i=0; i<a.length; i++)
               copy[i] = a[i];
             return copy;
           }

           public static void main(String[] args) {
             int[] a = { 1, 2, 3};
             int[] copy = copy(a);

             // After we copy the array, we change the original
             // and the copy, but what happens...?
             a[0] = 99;
             copy[1] = -99;

             System.out.println(Arrays.toString(a));
             System.out.println(Arrays.toString(copy));
           }
         }

   3. Equals
       
      1. Broken Equals

         class MyCode {
           public static void main(String[] args) {
             int[] a = { 1, 2, 3};
             int[] b = { 1, 2, 3};
             System.out.println(a == b);  // surprised?
           }
         }

         Working Equals

         import java.util.Arrays;
         class MyCode {
           public static void main(String[] args) {
             int[] a = { 1, 2, 3};
             int[] b = { 1, 2, 3};
             System.out.println(Arrays.equals(a,b));
           }
         }

   4. Insertion
      
      import java.util.Arrays;
      class MyCode {
        public static int[] add(int[] a, int newValue) {
          int[] result = new int[a.length+1];
          for (int i=0; i<a.length; i++)
            result[i] = a[i];
          result[a.length] = newValue;
          return result;
        }
        public static void main(String[] args) {
          int[] a = new int[0];
          System.out.println(Arrays.toString(a));
          a = add(a, 3);
          System.out.println(Arrays.toString(a));
          a = add(a, 5);
          System.out.println(Arrays.toString(a));
        }
      }
       
   5. Deletion
      
      import java.util.Arrays;
      class MyCode {
      
        // Removes every occurrence of value, if any, in the array "a"
        public static int[] remove(int[] a, int value) {
          int[] result = new int[a.length - count(a,value)];
          int resultI = 0;
          for (int i=0; i<a.length; i++)
            if (a[i] != value) {
              result[resultI] = a[i];
              resultI++;
            }
          return result;
        }
        // Helper method for remove.  Returns the number of times that
        // value occurs in the array a.
        public static int count(int[] a, int value) {
          int count = 0;
          for (int i=0; i<a.length; i++)
            if (a[i] == value)
              count++;
          return count;
        }
        public static void main(String[] args) {
          int[] a = { 2, 3, 5, 3, 1, 4 };
          System.out.println(Arrays.toString(a));
          a = remove(a, 1);
          System.out.println(Arrays.toString(a));
          a = remove(a, 3);
          System.out.println(Arrays.toString(a));
        }
      }
       
   6. Examples
       
      1. The Locker Problem

         import java.util.*;
         class MyCode {
           public static void main(String[] args) {
             // 1. Read in # of lockers
             Scanner scanner = new Scanner(System.in);
             System.out.print("How many lockers: ");
             int lockers = scanner.nextInt();
         
             // 2. Allocate array of lockers, all closed at first
             //    (We will ignore locker[0].)
             boolean[] isOpen = new boolean[lockers+1];
         
             // 3. Student N visits every Nth locker
             int student, locker;
             for (student=1; student<=lockers; student++) {
                 for (locker=student; locker<=lockers; locker += student)
                     isOpen[locker] = !isOpen[locker];
             }
         
             // 4. Print out open lockers
             System.out.println("Open lockers:");
             for (locker=1; locker<=lockers; locker++)
                 if (isOpen[locker])
                     System.out.println(locker);
           }
         }

      2. Anagrams

         import java.util.*;
         class MyCode {

           // Returns an array of size 26 containing the counts
           // of each of the 26 letters in the given string.
           public static int[] charCounts(String s) {
             s = s.toUpperCase();
             int[] counts = new int[26];
             for (int i=0; i<s.length(); i++) {
               char c = s.charAt(i);
               if ((c >= 'A') && (c <= 'Z'))
                 ++counts[(c - 'A')];
             }
             return counts;
           }

           // Two strings are anagrams if the all the counts
           // of each of the 26 letters in each string are the same.
           public static boolean isAnagram(String s1, String s2) {
             int[] counts1 = charCounts(s1);
             int[] counts2 = charCounts(s2);
             return (Arrays.equals(counts1, counts2));
           }

           public static void main(String[] args) {
             Scanner scanner = new Scanner(System.in);
             System.out.print("Enter two strings: ");
             String s1 = scanner.next();
             String s2 = scanner.next();
             System.out.println("isAnagram(" + s1 + "," + s2 + ") = " +
                                 isAnagram(s1,s2));
           }
         }

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem