- Forward


Look-up Arrays
A Programming Pattern


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • Obvious Reasons to Use Arrays:
    • They make it easy to have fixed-size "collections" of homogeneous elements
    • They make it easy to perform the same operation(s) on each element
  • A Less Obvious Reason to Use Arrays:
    • In some situations, they make it easy to "look up" information
An Example: Highway Exit Numbers
Back SMYC Forward
  • Two Systems:
    • In the old system, highway exit numbers were consecutive integers (e.g., 1, 2, ...)
    • In the new system, highway exit numbers are based on mileage markers
  • The Problem:
    • Find the new exit number corresponding to an old exit number
An Example: Highway Exit Numbers (cont.)
Back SMYC Forward
ExitNumbers
The Pattern
Back SMYC Forward
  1. Create an array in which the indexes correspond to the key that will be used to perform the look-up, and the elements correspond to the value that is to be determined.
  2. Create a method that validates the key and returns the appropriate element of the array for any valid key (and an error status for any invalid key).
An Example: Highway Exit Numbers (cont.)
Back SMYC Forward
javaexamples/programmingpatterns/LookupArrays.java (Fragment: newExitNumberFor)
 
An Example: Highway Exit Names (cont.)
Back SMYC Forward
javaexamples/programmingpatterns/LookupArrays.java (Fragment: exitNameFor)
 
Learning from the Previous Example
Back SMYC Forward
  • A Nice Characteristic of the Previous Example:
    • The index of the lookup array corresponded exactly to the old exit number
  • An Observation:
    • This won't always be the case
From a Key to an Index
Back SMYC Forward
  • Large Contiguous Keys:
    • The keys are contiguous but don't start at 0 in which case you can subtract the key from the smallest possible key (e.g., if you have annual data starting in 2015 then index = year - 2015;
  • An Example:
    • javaexamples/programmingpatterns/LookupArrays.java (Fragment: sales)
       
From a Key to an Index (cont.)
Back SMYC Forward
  • Non-Contiguous, Regular Keys:
    • More complicated calculations may be needed (sometimes using other programming patterns like divisibility and digit manipulation)
  • An Example:
    • javaexamples/programmingpatterns/LookupArrays.java (Fragment: letterGrade)
       
From a Key to an Index (cont.)
Back SMYC Forward
Pass/Fail Grading
javaexamples/programmingpatterns/LookupArrays.java (Fragment: passFail)
 
From a Key to an Index (cont.)
Back SMYC Forward
  • U.S. Population:
    • Population data are collected every 10 years
  • The Problem:
    • Find the population for the previous census year
An Example: Population (cont.)
Back SMYC Forward
javaexamples/programmingpatterns/LookupArrays.java (Fragment: population)
 
There's Always More to Learn
Back -