BFOIT - Introduction to Computer Programming

Arrays

Introduction

Like sentences and lists, arrays are collections of data.

In this lesson, you will learn:

  1. What an array is and why they are useful,
  2. how to access something in an array,
  3. how to put something into an array, and
  4. how to create an array.

Like we have been doing throughout these lessons, we are going to learn about arrays while writing some interesting programs.

TurtleSpace Pixels

In the first lesson, where we looked at how stuff is represented inside of a computer, there was an overview of pixels.  I am now going to explore pixels a bit more because they are an excellent example of the usefulness of arrays.

So... here is the TG applet.  How many pixels are in its graphics canvas subwindow, in its TurtleSpace?

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag! TG - TurtleGraphics Applet

Hint: there are operators that will tell you...

Before reading on, try to figure out how many pixels the graphics canvas consists of.

The actual number can vary a bit because of differences in browser support for Java.  In any case, you should have arrived at a little more than one hundred and seventy thousand pixels... I computed 172,870 pixels!  And this TG applet's graphics canvas is small; a 1080i/1080p HDTV image consists of 2,073,600 pixels.

Representing Lots of Pixels in a Program

As far as a computer is concerned, a pixel is a number.  But this collection of numbers, the contents of TG's graphics canvas, is big, very BIG.  So far you have only learned about one way to represent a collection of numbers - as a sentence (which is a kind of list).  The sentences you've been working with so far have been small.  As it turns out, using a list to represent hundreds of thousands of numbers is not a good idea.

To prove this to you, I played around a bit, creating lists of tens of thousands of numbers in them.  Then I created arrays of the equivilent sizes.  Table 19.1 shows the results of running simple procedures that constructed lists of numbers and then arrays of numbers.

Number
of
 Members 
Lists
 MacBook 
Seconds
Lists
 HP Desktop 
Seconds
Arrays
 HP Desktop 
Seconds
10,000 2.783 1.178 .043
15,000 10.379 2.986  - 
20,000 42.557 4.888 .049
25,000 76.214 7.852  - 
30,000  -  11.652 .067
40,000  -  22.843  - 
50,000  -  37.369 .086
Table 19.1
  • The first column is the number of members created in the lists and arrays.
  • The second column is the time it took to create lists on my Apple MacBook.
  • The third column is the time it took to create lists on my HP Desktop.
  • The fourth column is the time it took to create arrays on my HP Desktop.

On my 2009 Apple MacBook, a procedure output a list of 10,000 numbers in 2.783 seconds.  So, it should take 20 times this amount, or just under a minute to construct a list of 200,000 members (20 times 10,000).  Right?

Wrong.  The third row of the table shows that it took over 40 seconds to build a list of only 20,000 members.  The task of building lists in not a linear process.

Next I ran the same procedures on my 2011 HP desktop.  I did get better times as the third column shows.  But, it also confirms that the time it takes is non-linear.  And, we also see that the time it would take to construct a list of hundreds of thousands of pixel values is still much too long for it to be practical.

But look at the fourth column.  It only takes a few hundredths of a second to create an array and set all of its members to numbers.  Out of curiosity I created an array with two million (2,000,000) numbers a few times.  Each time it took a little less than two and a half seconds.

So... arrays are something you should want to know more about, especially when working with the graphics canvas' pixels.

Accessing Graphics Canvas Pixels

Let's look at some pixels.  Table 19.2 contains a few new operators we'll use to get a bunch of pixels (provided in an array) and access the pixels individually.

Name Input(s) Description
COUNT array Outputs the number of members in its input, an array.
GETPIXELS rectangleList Outputs an array of pixel values specified by the input rectangleList, a List of four numbers. The first number is the left-most X edge of the rectangle, the second number is the top Y edge of the rectangle, the third number is the width of the rectangle, and the fourth number is the height of the rectangle, e.g., (sentence :leftX :topY :width :height).
ITEM index
array
Outputs the indexth member of array.
Table 19.2

GETPIXELS

The description of GETPIXELS appears to be a bit complex.  Figure 19.1 should help you see what GETPIXELS does.  I'll use it to walk you through the description.

Figure 19.1
GETPIXELS outputs an array of pixel values

The top-right grid in Figure 19.1, consisting of one row of nine columns, represents an array output by GETPIXELS.  This array is composed of nine members, each a pixel.  The ITEM operator can be used to access the members.  Its first input, the index, should be one of the numbers shown in the grid, one for the first pixel, two for the second pixel, etc... 

The array appears to be a line of pixels.  But, the group of pixels we want were described as a rectangle, as the description continues

specified by the input rectangleList, a list of four numbers.
...left-most X, ...top Y, ...width, and height

In Figure 19.1, the lower-left grid, consisting of three rows each with three columns, represents the rectangular area of pixels we want.  In this example, the rectangleList provided was [-1 1 3 3]. Left-X is -1, top-Y is 1, and width and height are 3.

The lines joining the two grids show how the two dimensional rectangle of pixels is represented in the single dimensional line of pixels.  The pixels are stored left-to-right, top-to-bottom.  The pixel at -1,1 is the first member in the array, the pixel at 0,1 is the second member, the pixel at 0,0 is the fifth member, and the pixel at 1,-1 is the ninth member - the last.

Let's play in order to understand what's going on.

ShowGetPixels

I've written a little program named ShowGetPixels which demonstrates how the COUNT, GETPIXELS and ITEM operators can be used.  Here is most of it.  Let me walk you through it.

 1.   to printPixelRow :pixels :startIdx :rowWid
 2.     localmake "lastIdx sum :startIdx (difference :rowWid 1)
 3.     repeat (sentence :startIdx :lastIdx) ~
 4.            [printPixelValue (ITEM repcount :pixels) print "| |]
 5.     println "||
 6.     end
 7.
 8    to main
 9.     home clean cleartext
10.     setbackground 1     ; set background color to be blue
11.     setshape [2 11]     ; set turtle's image to be a ball, diameter = 11 pixels
12.     setpencolor 32      ; set pen color (inner pixels of the ball), to deep blue
13.     stamp               ; paint turtle's image onto the graphics canvas
14.     ; get pixels in rectangle with top-left corner at -7,8 and width & height = 15  
15.     make "pixels GETPIXELS [-7 8 15 15]
16.     ; pretty print the values of the rectangle of pixels in the CommandCenter
17.     repeat (sentence 1 (COUNT :pixels) 15) [printPixelRow :pixels repcount 15]
18.     end 

I'll start with the main procedure.

main

Line 10 sets the background color of the graphics canvas to blue.

Line 11 sets the shape of the turtle, its image, to a ball with a diameter of 11 pixels.

Line 12 sets the color of the turtle's pen to a very deep shade of blue (appoaching black). This changes the turtle's image. The perimeter pixels of the ball stay black but its interior pixels are set to deep blue.

Line 13 stamps the turtle's image onto the graphics canvas.

Line 15 gets an array of pixels contained in a rectangular area of the graphics canvas. The top-left corner of the rectangle is -7 on the X axis and 8 on the Y axis. The width and height of the rectangle are 15 pixels.

The remaining line of main (17) makes use of an advanced REPEAT command and the printPixelRow procedure to print rows of pixel values from the array obtained with GETPIXELS.

The SENTENCE constructor in the REPEAT command provides indexes into the pixels array for the first pixel of each row.  It starts with an index value of 1, the first pixel in the array.  The maximum value the index can be is (count :pixels) which is the number of members in the array - the last pixel value.  The final number in the sentence is the number of pixels in a row, and this is the amount the REPCOUNT value is increased after the REPEAT's command list is performed. 

Given this explanation, take a little time and think about what values REPCOUNT will have as this REPEAT command is performed.  Do NOT read ahead until you've given this a bit of thought.

To see if you have the right values, type the following code into the TG applet above.

   make "ary array (product 15 15)
   repeat (sentence 1 (count :ary) 15) [println repcount]  

printPixelRow

The procedure printPixelRow prints the numeric values of one row of pixels, separating them with a space.  Each pixel is printed as three characters, padded on its left with space.  This lines the pixels up in columns for easy reading.

printPixelRow has three inputs: (1) an array of pixels, (2) the index for the first pixel in the row to be printed, and (3) the number of pixels in the row.

Line 2 computes the index of the last pixel to be printed.  The index is stored in a local variable named lastIdx.

Line 3 is the start of an advanced REPEAT command with a sentence for its first input.  The two-number sentence provides starting and ending values for REPCOUNT.  REPCOUNT will be used as the index input to the ITEM operator.

Line 4 completes the REPEAT command, providing its second input, a command list.  The first command is a user-defined procedure, printPixelValue, which prints its input.&nsp; The second command prints a single space.

The only difference between printPixelValue and a PRINT command is that it insures that at least three characters are printed.  This allows the printed pixel values to line up nicely into columns.

Look at the ITEM operator which provides printPixelValue's input.  ITEM has two inputs, the index of a member and an array.  It outputs the value of the indexth member in the array.  As I described above, REPCOUNT supplies the index input.

Line 5 completes the printing by adding a newline with a PRINTLN command. 

ShowGetPixels Output in the CommandCenter

Figure 19.1 shows the results of running ShowGetPixels in the TG applet above.

Figure 19.2

Look at all those numbers... how are we to make sense of them?

First of all, count the number of rows and columns... 15 in each case.  This matches the width and height values we gave the GETPIXELS operator (line 15 of the program).

Now look at the center; do you see the pixel values of 32.  Those pixels are the inner pixels of the ball we STAMPed onto the canvas.  Remember... we set the color of the ball to 32 (line 12 of the program).  Count the number of pixels in the rows and columns at the center of the ball - 9.  WAIT!  We requested a ball with the diameter of 11 (line 11 of the program).  Well, look at the circle of pixel values of 0 that surround the deep blue inner pixels.  These black pixels are part of the ball - its outer edge.  If you include these black pixels, we have a ball of size 11.

One last thing... what are all the pixel values of 255 doing surrounding the ball?  Didn't we set the background color to blue (line 10 of the program)?

Well, the color numbers one through fifteen (1 - 15) that you use with SETBACKGROUND and SETPENCOLOR are abbreviations for the real colors.  Color number one, blue, is actually a pixel with a red value equal to zero, a green value equal to zero, and a blue value of 255.  So, that is where all of the 255 values come from.  They are the blue pixels of the background.

Just for fun, play with the pixel color applet ; set the red and green values to zero and the blue value to 255.  See that you get blue... Change the blue value to zero and see that you get black.  Finally set the blue value to 32 and watch closely as you click on the "Show Color" button; the color will change ever so slightly to deep, DEEP, blue.

Play with the ShowGetPixels Program...

You can try out and play with ShowGetPixels yourself.  If you are using the TG application, here is the source code you can copy/paste into TG's editor. If you would rather play in the TG applet above, choose the File->New option in its menu system and then type loadcode ShowGetPixels.jlogo" into the CommandCenter.

Play with the program...

  • Change the background and pen colors, keeping them in the range of 32 through 255.
  • Change the shape of the turtle's image, keeping the sides short, 11 or less pixels.

Just out of curiosity...

Do you know why I only used shades of blue in the ShowGetPixels program?

Changing Graphics Canvas Pixels

So we now know how to get a rectangular area of pixels from the graphics canvas into an array.  Let's go the other way; let's create an empty array, fill it with pixel values, and paint the graphics canvas with its contents.

Table 19.3 contains a few new operators we'll use.

Name Input(s) Description
ARRAY size Outputs an array of size members, each of which is initially an empty sentence. Size must be a positive integer.
SETITEM index
array
value
Replaces the indexth member of array with value.
SETPIXELS rectangleList
pixelArray
Paints the values of pixels in pixelArray onto the area of the graphics canvas specified by rectangleList. Pixel values are color numbers. A rectangleList has the form [leftX, topY, width, height].
Table 19.3

Here is a program that draws a rectangle - one pixel at a time. 

 1.   to setPerimeterPixels :pixAry :linWid :color
 2.     repeat :linWid [SETITEM repcount :pixAry :color]
 3.     repeat (sentence 1 (count :pixAry) :linWid) [SETITEM repcount :pixAry :color]
 4.     repeat (sentence (count :pixAry) 1 (minus :linWid)) [SETITEM repcount :pixAry :color]
 5.     repeat (sentence (difference (count :pixAry) (difference :linWid 1)) (count :pixAry)) ~ 
 6.            [SETITEM repcount :pixAry :color]
 7.     end
 8.
 9.   to main
10.     home clean hideturtle
11.     localmake "pixAry ARRAY pixArySz
12.     setPerimeterPixels :pixAry pixAryWd blue
13.     SETPIXELS pixAryRectList :pixAry
14.     end 

MagnifyPixels

A fun little program that will demonstrate how to do this is one which acts as a pixel magnifying glass.  We will get a rectangular area of pixels from the graphics canvas, magnify them in a new array we construct, and then paint the magnified pixels onto the graphics canvas.

Time to sketch out our MagnifyPixels program.  Here is the approach I arrived at after writing the program a couple of times.

Figure 19.3 shows a very simple way in which we can do magnification. 

Figure 19.3

In this approach, each pixel in the top grid is replicated into a four-by-four pixel rectangle in the bottom grid.  We will convert each row of pixels in the original rectangle of pixels into four identical rows of pixels in the new rectangle of pixels.  AND each column of pixels in the original rectangle become four columns in the expanded rectangle.  Each pixel becomes sixteen pixels.

   A. Use GETPIXELS to obtain the array of pixels to be magnified.
   B. Iterate through each line of pixels in the array. For each line we will
      1. Store magnified images of the line in the new array, one after another.
         The number of copies of it stored is the magnification factor.
         a. To create each magnified image, for each pixel in an original line,
            store it a number of times into the new array. The number of copies
            of each pixel is the magnification factor.
   C. Use SETPIXELS to store the new array of pixels on the graphics canvas.
                        

You can try out and play with MagnifyPixels yourself.  Use the TG applet above, choose the File->New option in its menu system and then type loadcode MagnifyPixels.jlogo" into the CommandCenter.

 1.  to getMagnifiedPixels :pixAry
 2.    localmake "bigPixAry ARRAY (product bigBoxSideLen bigBoxSideLen)
 3.    localmake "putIdx 1
 4.    repeat (sentence 1 boxNumPix boxSideLen) ~
 5.           [localmake "linePixIdx repcount ~
 6.            repeat magnification ~
 7.                   [repeat (sentence :linePixIdx (sum :linePixIdx (decr boxSideLen))) ~
 8.                           [localmake "pixel item repcount :pixAry ~
 9.                            repeat magnification ~
10.                                  [SETITEM :putIdx :bigPixAry :pixel make "putIdx incr :putIdx]]]] 
11.    output :bigPixAry
12.    end
13.
14.   to main
15.     clean hideturtle
16.     loadpict "yoshiamon.bmp
17.     localmake "pixels getpixels boxRectList
18.     SETPIXELS bigBoxRectList (getMagnifiedPixels :pixels)
19.     end 

If you are using the TG application, here is some source code you can copy/paste into TG's editor.  I've modified the way it paints an initial image onto the graphics canvas so that it runs without any changes.  Instead of loading the yoshiamon.bmp image, it sets the turtle's pen color to forest and stamps its image onto the graphics canvas.  If you have a .bmp image file in the same directory as where you run TG, you can modify the program to load it.

More Pixels

Name Input(s) Description
SHAPEPIXELS Outputs a list containing two members. The first is the number of pixels in each row of the turtle's shape. The second is an array containing all of the pixels that make up the shape's image.
Table 19.4

The Game of Life

John Conway's Game of Life is an example of Cellular Automaton.

A cellular automaton is a collection of "colored" cells on a grid of
specified shape that evolves through a number of discrete time steps
according to a set of rules based on the states of neighboring cells.
The rules are then applied iteratively for as many time steps as
desired. (from http://mathworld.wolfram.com/CellularAutomaton.html).

The "Game of Life" is played on a grid.  The squares of the grid are called cells.  A cell that is alive is colored in.  The rules for Life are simple.  They are:

  1. In order for a cell to remain alive, it must have two or three neighbors.
  2. If a live cell has less than two neighbors, it dies (loneliness).
  3. If a live cell has more than three neighbors, it dies (over-crowdedness).
  4. If an empty cell has exactly two neighbors, it comes to life.

A cell's neighbors are the eight cells which surround it (to its north, northeast, east, etc...).

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag! Life Applet

Here is a Java applet that implements a subset of the Game of Life.  Draw some patterns by clicking the left mouse button on squares to bring them to life.  Then click on the [Step] button to watch what happens as the rules are applied in one cycle of Life.

Other Procedures for Working With Arrays

Name Input(s) Description
ARRAY?
ARRAYP
thing Outputs true if the input thing is an array, else outputs false.
ARRAYTOLIST array Outputs a list whose members are the members of the input array.
LISTTOARRAY list Outputs an array whose members are the members of the input list.
Table 19.3

Summary


Back to Turtles As Actors
Go to the Table of Contents
On to File Input/Output

Public Domain Mark
This work (BFOIT: Introduction to Computer Programming, by Guy M. Haas),
identified by Berkeley Foundation for Opportunities in IT (BFOIT),
is free of known copyright restrictions.