Computer Science 15-100, Spring 2009
Class Notes:  One-Dimensional Arrays

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
7. Swap
   1. Broken Swap
   2. Working Swap
8. Copy
   1. Broken Copy
   2. Working Copy
9. Equals
   1. Broken Equals
   2. Working Equals
10. Insertion
11. Deletion
12. Examples
    1. The Locker Problem
    2. Anagrams

One-Dimensional Arrays

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
       
7. 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));
        }
      }

8. 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));
        }
      }

9. 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));
        }
      }

10. 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));
      }
    }

11. 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));
      }
    }

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