Topics

Topics to be covered in part 2

Arrays (V) - You’ve already seen variables

var firstNumber = 2;
var secondNumber = 10;

But how to store 500 numbers?

Functions (VI) - You’ve already been using "built in" functions:

prompt( "enter a number" );
alert( "Hello World" );
eval( firstNumber + secondNumber );

But how to write new functions that do what you need?

Topics

And, finally:

Problem solving and developing programs (VII)
Introduction to Object-oriented programming (VIII)

Notes

The timetables, group allocation for practicals and tutorials are unchanged.
There is the same expectation for attendence
Please respect your fellow students and do not disrupt the lectures
- Arrive on time
- Mobiles on silent, please leave the room if you need to use them
- Likewise, if you want or need to talk.
You can contact my through email: phillip.lord@newcastle.ac.uk

Notes on notes

These notes are available in a few different forms.

HTML: The slide show version. This has all the essential information for the module.
Expanded: An HTML version laid out like a book. This has some additional supplementary material, providing some background. The javascript examples should work directly in this version.
PDF: This version is printed for the handouts. It has the same material as the expanded version. Obviously, the javascript examples will not run.

All of these versions are missing some questions and answers which I will uncover during the lectures. These missing parts are marked so you know where they are, and look like this: uncovered .

Notes on notes

There are many examples in these slides. These come in three forms.

Good code — if there in an error, it is not intentional!:

alert( "Hello World" );

Broken code — will always be marked, normally, although not always before the error. Broken does not (only) mean "will not run":

// BROKEN
alert("Goodbye World");

Bad code — sometimes I won’t be able to explain yet why it is bad:

// BAD -- this is hard to read and performs badly
alert( "H" + "e" + "l" + "l" + "o" + " " +
       "W" + "o" + "r" + "l" + "d" );

Arrays (V)

Why are simple variables not enough?
How do arrays answer the need?
Introduce arrays in Javascript
- The new Array(x) keywords
Introduce the for .. in loops are used
Multi-dimensional arrays (briefly!)
Examples!

Why Arrays?

If you do not know a value when you write your code, you can use a variable.

For example:

How many students are in the room?

How many students are awake?
How many students are listening?

var studentsInRoom = 200
var studentsAwake = 150
var studentsListening = 100

Why Arrays?

But what if you need to store several values?

What are the names of the students in the room?

One solution would be to create several variables.

var studentOne = "John"
var studentTwo = "Paul"
var studentThree = "George"
var studentFour = "Ringo"

Caution

This is not a good solution!

We have to come up with several names, all very similar.
The code is very ugly

Most importantly, as well as not knowing the names when we write the code, we don’t know how many names there will be.

Why Arrays?

Another solution would be to put multiple values into a single variable.

var studentNames = "John" + "Paul" + "George" + "Ringo"

Caution

This is really not a good solution!

But, now we can’t get the values back out, so we need a separator.

var studentNames = "John" + ";" + "Paul" + ";" + "George" + ";" + "Ringo"

What is the problem with solution?

Lists

If you go shopping, you write a list.

Taken from: http://www.flickr.com/photos/whiskeytango/2098182380/ CC by 2.0

The solution in javascript is much the same; You use an Array.

What is an array

An array is an object that can contain any number of values
Like other values, arrays can be stored in a variable
Arrays have a number of elements which can store values
Arrays are ordered — they have a start, middle and end
Each element has an index, describing the position in the array
Mental model — a set of pidgeon holes

Arrays are an example of an object. We will be talking more about objects later on.

Making an array

Before you use an array, you need to make one.

Stretching the metaphor, you need a blank sheet of paper, to write a shopping list.

There are two main ways to declare an array

// declare a new array with the new keyword
var students = new Array();
// declare a new array with 10 empty elements
var students2 = new Array(10);

// declare an empty array, using the literal syntax
var students3 = [];
// declare an array with some initial values
var students4 = ["John", "Paul", "George", "Ringo"];

The "literal" syntax is more compact, and can be useful if you know the values you want to add.

Properties of an array

Arrays have a number of properties. Considering this array.

// declare an array
var student = ["John", "Paul", "George", "Ringo"];

// we can access the size like this...
alert( "Size of array: " + student.length );

// we can access elements like this...
alert( "2nd Element of array: " + student[2] );

What is the length or size of this array?
What is the second element?
- We use the [] notation to access this element.

In javascript, the elements of an array start at 0, or the zeroth element.

Iterating through a list

Iteration means doing something to every element in the list.

When shopping, you buy the first item, then the next and so on.

You have already seen the for loop.

// a simple for loop in javascript
var alertString = "";
for(var i = 0;i < 4; i++){
    alertString = alertString + i + "\n";
}
alert(alertString);

By combining the counter variable from the for loop, with an array, we can iterate.

// declare an array with some initial values
var students = ["John", "Paul", "George", "Ringo"];

var alertString = "Array values are:\n";
for(var i = 0; i < students.length;i++){
    alertString = alertString + i + ":" + " " + students[i] + "\n";
}
alert(alertString);

Filling an array

You can also put values into an array in the same way:

// declare an array with no initial values
var students = new Array( 4 );

// ask the user for values
for(var i = 0;i < students.length;i++){
    // users count from 1
    students[ i ] =  prompt( "Please enter student number "
                             + (i + 1) + ":", "" );
}

// print the results out -- this is the same code as before.
var alertString = "Array values are:\n";
for(var i = 0; i < students.length;i++){
    alertString = alertString + i + ":" + " " + students[i] + "\n";
}
alert(alertString);

Exercise (alphabets)

Given an set of student names as an array, how do I find the first one in the alphabet?

Think about this for five minutes.

To solve this problem, we need to break things up:
First, how do we know if one name is earlier in the alphabet?
How do we move through every student name?
How do we store the results?

Exercise (alphabets)

Finding out which of two strings is earliest in the alphabet is straight-forward.

alert("John" < "Paul");
alert("John" > "Paul");

Now, we need to know how to compare the first two names.

// declare an array with some initial values
var students = ["John", "Paul", "George", "Ringo"];
var firstInAlphabet = students[ 0 ];

if( firstInAlphabet > students[ 1 ] ){
        firstInAlphabet = students[ 1 ];
}

alert( firstInAlphabet );

Exercise (alphabets)

Finally, we need a loop to finish off.

// declare an array with some initial values
var students = ["John", "Paul", "George", "Ringo"];
var firstInAlphabet = students[ 0 ];

for( var i = 1; i < students.length; i++ ){
    if( firstInAlphabet > students[ i ] ){
        firstInAlphabet = students[ i ];
    }
}

alert( "First in alpabet is: " + firstInAlphabet );

This is an usual loop because it doesn’t start at the beginning of the array; the example still works in this case.

Can you modify this example, so that it asks the users for input first?

General Confusion!!!

What do these loops do?

var students = ["John", "Paul", "George", "Ringo"];


// BROKEN!!!
var alertString = "Array values are:\n";
for(var i = 1; i < students.length;i++){
    alertString = alertString + i + ":" + " " + students[i] + "\n";
}
alert(alertString);

// Ok, but wierd
alertString = "Array values are:\n";
for(i=1; !(i>students.length); i++){
    alertString = alertString + (i-1) + ":" + " " + students[i-1] + "\n";
}
alert(alertString);

// OK, but different
alertString = "Array values are:\n";
for(i = 0; i != students.length;i++){
    alertString = alertString + i + ":" + " " + students[i] + "\n";
}
alert(alertString);

for loops look easy, but they are very easy to get wrong.

The `for … in` loop

Javascript also has a for … in loop.
This is a special version of the for loop.

// declare an array with some initial values
var students = ["John", "Paul", "George", "Ringo"];

var alertString = "Array values are:\n";
for(i in students){
    alertString = alertString + students[i] + "\n";
}
alert(alertString);

This version of the for loop makes off-by-one errors much harder.

Making things simpler

So, can we see a more real example?

Yes, but the code snippets will get longer. So in future slides, I am going to miss some bits out.

// the line before this is
// var alertString = "";

alertString="Hello World";

// the line after this is
// alert( alertString );

You can check the source for the HTML version of the slides if you do not believe me; the missing bits are there!

The slides of the talk

Here is a slightly more useful example.

We can count all the slide numbers for this talk.
This example uses some object syntax that you haven’t seen yet.
We could do something more useful.

// set up the display
alertString = "Slides in talk:";

// get a copy of the slides from the browser
var slides = w3c_slidy.slides;

// collect all the slides in this talk, and count them.
for( i in slides ){
    alertString = alertString + i + " ";
}

What could we do which might be more useful?

Exercise (counting)

This code counts the slides start to finish. How could you achieve the same, but counting backward?

// set up the display
alertString = "Slides in talk:";

// get a copy of the slides from the browser
var slides = w3c_slidy.slides;

// collect all the slides in this talk, and count them.
for( i in slides ){
    alertString = alertString + i + " ";
}

Exercise (counting)

We start with an easier version first.

// declare an array with some initial values
var students = ["John", "Paul", "George", "Ringo"];

// set up the display
var alertString = "Array values are:\n";
for(var i = students.length - 1; i >= 0;i--){
    alertString = alertString + i + ":" + " " + students[i] + "\n";
}

alert( alertString );

// set up the display
alertString = "Slides in talk:";

// get a copy of the slides from the browser
var slides = w3c_slidy.slides;

// collect all the slides in this talk, and count them.
for(var i = slides.length - 1; i >= 0;i--){
    alertString = alertString + i + " ";
}

alert( alertString )

In this case, we need to use for loop. You may be able to work out how to do this with a for … in loop later in the module.

Changing the value of an array

Like any variable, we can also assign new values to an array element.

// declare an array with some initial values
var students = ["John", "Paul", "George", "Ringo"];

var alertString = "Array values are:\n";
for(i in students){
    alertString = alertString + students[i] + "\n";
}
alert(alertString);

// we can change the value with the normal "=" operator.
students[ 2 ] = "Georgina";

alertString = "Array values are now:\n";
for(i in students){
    alertString = alertString + students[i] + "\n";
}
alert(alertString);

Dealing with edge cases

An edge case is a problem or situation that occurs only at an extreme (maximum or minimum) operating parameter.

— Wikipedia

Writing programs which deal with expected cases is okay
- But "extremes" happen more often than they should
- You have to know how to deal with these also.
- Edge case handling is one of the marks of good programming.

What edge cases are there for for loops?

Adding too many objects

What happens if you add more objects to an array element that doesn’t exist?

var array = new Array( 2 );

alertString = "Before: " +  array.length + "\n";

// array indexes start from 0!
array[2] = "Broken?";

alertString = alertString + "After: " + array.length;

Javascript copes with this without complaining.

Growable arrays of this sort are often very convienient, but are they always good?

Non-existent elements

What happens if you access an element that does not exist?

var students = ["John", "Paul", "George", "Ringo"];

// array indexes start with 1!
alertString = "Element value is: " + students[ 4 ];

Any array element which has not been explicitly given a value, has an undefined value.

Undefined values != "undefined"

Undefined is a special value in Javascript.

In some cases it looks like a string
But it isn’t

var array = [];

alertString = "String Comparison: "
if( "undefined" == "undefined" ){
    alertString =  alertString + "==";
}
else{
    alertString =  alertString + "!=";
}

alertString = alertString + "\nUndefined Comparison: "

if( array[0] == "undefined" ){
    alertString =  alertString + "==";
}
else{
    alertString =  alertString + "!=";
}

Undefined is not a number

Undefined is not a number either
What will this code produce?

// This is BROKEN code to sum the numbers in an array
var array = [ 1, 2, 3 ];
var total = 0;

for( var i = 0; i <= array.length;i++ ){
    total = total + array[ i ];
}
alertString = "Total is: " + total;

When combined with an off-by-one error, this can produce unexpected results.

Example (Alphabetize)

We will now look at longer example:

Many parts of this you have seen before
There is only one new idea in this example

Given an array of students, sort them alphabetically.

There are many sorting algorithms in existance
We are going to use a selection sort, as it is easy
It is not, however, a good sorting algorithm to use in general
We shall see a better way of sorting an array later in the module

Example (Alphabetize)

How might you do this, if the names were written on paper.

Find the earliest in the alphabet.
Put this at the beginning.
- The first in the list is now sorted
Find the next earliest, in those unsorted that remain
Put this next
And so on.

We take the same approach, with one minor change.

At the start, position 0 is current
Find any earliest value by comparing to the rest of the array
Swap the earliest with current
- If the current is the earlist, then this does not do anything!
Position 0 is now sorted, so repeat from position 1.

Example (Alphabetize)

// declare an array with some initial values
var students = ["John", "Paul", "George", "Ringo"];

// you have seen how to print the elements of an array many times, so we take
// a short cut here. We will investigate ".join" more later.
alert( "Before:\n" + students.join( "\n" ) );

var indexOfEarlist;
var temp;

// iterate through the array
for(var current = 0; current < students.length - 1; current++){
    indexOfEarliest = current;
    // find the earlist in the alphabet of the rest of the array
    for(var next = current + 1; next < students.length; next++){
        if( students[ next ] < students[ indexOfEarliest ] ){
            indexOfEarliest = next;
        }
    }

    // now swap them. This may swap a element with itself!
    temp = students[ current ];
    students[ current ] = students[ indexOfEarliest ];
    students[ indexOfEarliest ] = temp;
}


alert( "After:\n" + students.join( "\n" ) );

Multi-dimensional arrays

Originally, we considered the motivation for an array, compared to a variable.

A variable stores a single value
An array allows us to store many

So far, we have considered arrays containing the names of students.

But what if we want to store more information?
We might want to store DOB also.
There are a number of ways we could achieve this

Multi-dimensional arrays

var students = ["John", "Paul", "George", "Ringo" ];
var dob = [ "1940", "1942", "1943", "1940"];

This work till, we want to add other important information.

We might want to add gender
Or whether the person were still alive

var gender = ["male", "male", "male", "male"];
var living = [false, true, false, true];

Caution

This is not a good solution!

Multi-dimensional arrays

Another solution!

var students = [ "John:1940:male:dead",
    "Paul:1942:male:alive",
    "George:1943:male:dead",
    "Ringo:1940:male:alive" ];

Hopefully, most of you will be getting a feeling of deja-vu by now.

The solution

A two-dimensional array:

The implementation
- There is actually nothing special about two-dimensional arrays
- Variables can store a value which can be an array
- Like a variable, an array element can store a value
- This value can also be an array
This gives us the ability to make a two-dimensional array.
- This is a classic trick of computing science
- We are doing nothing new here
- We are reusing the same idea repeatedly

The solution

So, how to retrieve the values?
- For a single dimensional array we use: students[ 0 ]
- For two dimensions, we reuse the same syntax again!
- For example, students[ 0 ][ 0 ]

Example (2D)

var students = [ 4 ];

students[ 0 ] = new Array( 3 );
students[ 0 ][ 0 ] = "John";
students[ 0 ][ 1 ] = "1940";
students[ 0 ][ 2 ] = "Dead";

students[ 1 ] = new Array( 3 );
students[ 1 ][ 0 ] = "Paul";
students[ 1 ][ 1 ] = "1940";
students[ 1 ][ 2 ] = "Alive";

// etc....

It can be confusing which order the elements come in
Although when declared like this, it is okay
The syntax is pretty long winded (as you see I got bored before the end)

Example (2D)

Fortunately there is a literal syntax, which is more compact.

It is harder to remember which dimension is which though

var students =
    [
     ["John", "1940", "Dead"],
     ["Paul", "1942", "Alive"],
     ["George", "1943", "Dead"],
     ["Ringo", "1940", "Alive"]
     ];

Example (2D)

How to print this array out?

Again, we reuse an idea repeatedly
In this case, we put one loop inside another

var students =
    [
     ["John", "1940", "Dead"],
     ["Paul", "1942", "Alive"],
     ["George", "1943", "Dead"],
     ["Ringo", "1940", "Alive"]
     ];

for( i in students ){
    for( j in students[ i ] ){
        alertString = alertString + students[ i ][ j ] + "\t";
    }
    alertString = alertString + "\n";
}

Multi-dimensional arrays

Can be very useful
We have only covered two-dimensions, but you should see how it is possible to have more
But can also be confusing (it took me 3 attempts to get the last example working)
If you have many kinds of information, objects may be better
We will cover objects briefly at the end of the module

Arrays Summary

Introduced the need for arrays
An array is an object that can be stored in a variable
An array has a number of elements
Each element has an index, and can contain a value
An array has a .length property, which is the number of elements it currently has.
The for … in loop is very useful with array
There are pitfalls to catch the unwary
You can make multi-dimensional arrays

Closing Material

This material is copyright by Newcastle University. It is written by Phillip Lord, modified from original lectures by Jennie Palmer.

CSC1011: Arrays

Topics

Topics

Notes

Notes on notes

Notes on notes

Arrays (V)

Why Arrays?

Why Arrays?

Why Arrays?

Lists

What is an array

Making an array

Properties of an array

Iterating through a list

Filling an array

Exercise (alphabets)

Exercise (alphabets)

Exercise (alphabets)

General Confusion!!!

The for … in loop

Making things simpler

The slides of the talk

Exercise (counting)

Exercise (counting)

Changing the value of an array

Dealing with edge cases

Adding too many objects

Non-existent elements

Undefined values != "undefined"

Undefined is not a number

Example (Alphabetize)

Example (Alphabetize)

Example (Alphabetize)

Multi-dimensional arrays

Multi-dimensional arrays

Multi-dimensional arrays

The solution

The solution

Example (2D)

Example (2D)

Example (2D)

Multi-dimensional arrays

Arrays Summary

Closing Material

The `for … in` loop