Computer Science 15-100, Fall 2008
Class Notes:  One-Dimensional Arrays

1. Allocation
   1. Fixed-Size Array
   2. Variable-Sized Array
   3. Statically-Allocated Array
2. Default Values
3. Array Parameters
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]);
        }
      }

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

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

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