- 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
images/ExitNumbers.svg
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 -