Arrays
Arrays: Declaring, Attributes, Looping, Aggregates, Iterators
Our First Array - Java Equivalent
- Java:
int[] a = new int[10];
- Ada:
a: array(0 .. 9) of Integer;
- Java:
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);;
Ada:
for i in 0 .. 9 loop
put(a(i));
More looping options available (see below)
Improvment: Bounds Can Start Anywhere
-
a: array(0 .. 9) of Integer;
-
b: array(1 .. 10) of Integer;
-
c: array(-10 .. 10) of Integer;
- Motivations: Concern for programmer and Reliability
- Write program at level of problem, not of machine
Arrays Have Attributes: Length, ...
int[] a = new int[100];
System.out.println(a.length);
Ada:
a : array(-10 .. 10) of Integer;
...
put(a'length); -- What is it?
More Attributes: First, Last, ...
- Problem: How can code determine index bounds?
- Related problem: How to make code independent of index range?
- If bounds change, don't want to change code
- Attributes: first, last, range
b: array(1 .. 20) of Integer;
...
for i in 1 .. 20 loop -- Must change code if change bounds
b(i) := 0;
end loop;
for i in b'first .. b'last loop -- No need to change code
b(i) := 0;
end loop;
for i in b'range loop
b(i) := 0;
end loop;
What happens here?
put( b(1) );
put( b(b'first) );
put( b(b'last) );
put( b'first );
put( b'last );
put( b(-1) );
-- Notice: First index vs first value
-- What if these statements are prior to the loop?
More Attributes: Range, and others
- Even easier than b'first .. b'last
if j in b'first .. b'last then -- Good
...
if j in b'range then -- Better
-- We will see other uses
...
Other attributes exist:
- 'Component_Size - Number of bits in array element
- 'Size - Number of bits in array
- 'Address - Location of array
In Operator
- Remember: Operator
in can be used in if statements
- Example:
if x in 1 .. 10 then
-- Using in is easier than:
if 1 <= 1 and x <= 10 then
Very flexible syntax:
if x in 1 | 3 | 5 .. 7 | 21 | 100 .. 110 then
Question: Can ranges overlap:
- Answer: Here, yes. But in some contexts, ranges can't overlap.
Notation essentially defines a set of values
Notation can also be used for dynamic predicate:
subtype Small_Odd is Natural with
static_predicate => Small_Odd in 1 | 3 | 5 | 7 | 9;
Aggregate Assignment
- Aggregates: a convenient way to assign array elements as a whole
- Use parentheses to construct an aggregate value
squares: array(1 .. 5) of Natural := (1, 4, 9, 16, 25);
Can assign specific values:
c: array(1 .. 10) of Integer;
c := (1 | 3 | 5 | 7 | 9 => 0, 2 | 4 | 6 | 8 | 10 => 1);
Can use ranges too:
c := (1 .. 5 => 0, 6 .. 10 => 1);
-- Can ranges overlap? No.
-- Must cover all values, or use others
Others:
c := (1 .. 5 => 0, others => 1);
c := (1 | 3 | 5 | 7 | 9 => 0, others => 1);
c := (1|3|5, 11 .. 15 => 3, others => 1);
-- Syntax error?
Can specify all values using just others
b := (others => 0); -- Initialize all to 0
Question: In (1|3|5..15), is 3 a shorthand for 3..3? A:Technically no, but it doesn't hurt to think that
Syntax used for in operator and case statement
Aggregate Assignment in Java
- Java - comparable operation only in declaration:
int[] a = {11, 22, 33};
Less reliable: no explicit specification of size
Does this compile? If so, what is b.length?
int[] b = {11, 22, 33, };
Array Iterator
- One more way to access all elements
- Ada 2012 introduced a new Iterator notation:
pragma Ada_2012; -- top line of file
...
b: array(1 .. 10) of Integer;
...
for x of b loop
put(x); -- Access each element
end loop;
...
for x of b loop
x := -x; -- access and modify each element
end loop;
Also works for 2D arrays and for collections such as lists and trees
New Array Types and Arrays as Parameters
New Array Types
- Ada allows us to create new array types
type Int_10 is array(1 .. 10) of Integer;
a: Int_10;
...
for i in Int_10'range loop
put( a(i) );
end loop;
Nothing comparable in Java
- Well, you can create a new class containing an array
Array Types have Attributes, too
- Array types have same attributes as array variables:
type Int_Array is array(1 .. 10) of Integer;
b: Int_Array;
...
for i in Int_Array'first .. Int_Array'last loop -- first index, not first element
b(i) := 0;
end loop;
if i in Int_Array'range then -- is i a valid index?
...
put(Int_Array'length);
Why New Array Types
- Benefit 1: Required for passing arrays as parameters
- Benefit 2: Better type checking
- Benefit 3: Required for array operations:
- Assignment
- Relational ops (eg =, /=, <)
- Concatenation (ie &)
Formal Parameters cannot have an Anonymous Type
procedure foo(p: array(1 .. 10) of integer) is -- COMPILE ERROR
...
end foo;
a: array(1 .. 10) of integer;
...
foo(a); -- Nice idea, but won't compile
Anonymous type: type with no name
- Example: array(1 .. 10) of integer
Formal and Actual Parameters:
- Formal parameter: found in procedure declaration (p in the above)
- Actual parameter: found in procedure call (a in the above)
Formal Parameters must have a Named Type
- Formal parameters must be of named type:
type Int_10 is array(1 .. 10) of Integer;
procedure foo(p: Int_10) is -- OKAY
begin
for i in p'range loop
...
end foo;
a: Int_10;
...
foo(a);
Where is memory actually allocated?
Nothing comparable in Java
Array Types Improve Type Checking
- Formal and Actual parameters must have same named type
type Int_10 is array(1 .. 10) of Integer;
type Int_20 is array(1 .. 20) of Integer;
procedure foo(p: Int_10; q: Int_20) is
...
end foo;
a: Int_10;
b: Int_20;
c: array(1 .. 10) of integer;
...
-- Which of these compile?
foo(a, b);
foo(b, a);
foo(c, b);
Anything comparable in Java?
Array Operations
- Named array types make type-checked array operations possible:
- Operands must have SAME NAMED type
type Int_10 is array(1 .. 10) of Integer;
type Int_20 is array(1 .. 20) of Integer;
a, b: Int_10;
c: Int_20;
s1: String := "Hi";
s2: String := " Mom!";
...
if a /= b then -- array comparison
a := b; -- array assignment
end if;
-- if a = c then -- Compile error
-- a := c; -- Compile error
put_line(s1 & s2); -- array concatenation!
Strings are arrays! See below.
Warning: Semantics Array Operations
- Assignment and comparison have different semantics from Java
- Look at the difference later
Arrays are Fixed Length
Arrays are Fixed Length
- Once an array is declared, it's length can't change
type Int_3 is array(1 .. 3) of Integer;
type Int_5 is array(1 .. 5) of Integer;
a: Int_3;
b: Int_5;
s1: String := "Hi";
begin
-- All are errors:
s1 := "Hello";
a := (11, 22, 33, 44, 55);
b := (66, 77, 88, 99);
Memory Allocation
- In the above code, where is memory allocated?
Strings are Arrays
Strings are Arrays
- A String is an array of characters
s: String := "Hi Mom!";
t: String := "Hello There";
...
for i in reverse s'range loop
put(s(i)); -- Output: !moM iH
end loop;
for c of s loop -- Iterator. C is of type Character
put(c); -- Output: Hi Mom!
end loop;
s(4) := 'T';
put_line(s); -- Output: Hi Tom!
put_line(t); -- Output: Hello there
What length string does put_line expect?
What About Put_line??
- Earlier we saw
procedure foo(p: Int_10; q: Int_20);
- Parameter lengths defined and checked at compile time
- Hmmm, what length string does put_line expect???
-
put_line works for any length string
- Above:
put_line(s) and
put_line(t) and
put_line(s & t)
- Answer: Type String is defined as an an unconstrained array
- Put_line's parameter is a String
- Let's look at unconstrained array types before looking more at strings
More Information on Strings
- Look here for more information on strings
Unconstrained Array Types
Constrained and Unconstrained
- The array and array types examples we've seen are all constrained
- Their bounds are known at compile time
- Example - A constrained array and a constrained array type:
a: array(1 .. 10) of Integer;
type A_Type is array(1 .. 10) of Integer;
Array types can also be unconstrained
Bounds will be specified later when the unconstrained type is
used to create
Type String is Unconstrained
- Example: Type String is unconstrained
-- Type String is PRE-DEFINED in package Ada.Standard
type String is array(Positive range <>) of Character; -- Unconstrained
s1: String := "Hi Mom!"; -- Constrained Array of length 7
s2: String(1 .. 10); -- Constrained Array of length 10
s3: String := s1 & s2; -- Length?
Allows creating Strings of any size
DO NOT define type String yourself.
-
It's predefined in
Package Standard, which is automatically available for every program.
Contents of s2?
Using Unconstrained Types: Size Required
- An unconstrained type must be give a size to declare a variable
- Invalid example
-- Attempt to make unconstrained variable
-- s3: String; -- Compile error
s4: String(1 .. 10); -- Okay - Explicit size 10
s5: String := "Hi"; -- Okay - Implicit size 2
Unconstrained Array Types for Formal Parameters
- Unconstrained array types allow flexible formal parameters
- Example - String parameters:
- Let's write a string rev function: ...
-- Reminder: String definition from package Ada.Standard
-- Don't define String yourself!!
type String is Array(Positive range <>) of Character;
function rev(S: String) returns String is
-- Solution below
...
put_line(rev("abc")); -- cba
put_line(rev("defghi")); -- ihgfed
Parameters can be any length
Unconstrained Array Types for Formal Parameters
- Unconstrained array types provide flexibility for formal parameters
- Example - String parameters:
- Let's write a string rev function: ...
declare
function rev(S: String) returns String is
t: String(1 .. s'length);
begin
for i in 1 .. t'range loop
t(i) := s(s'last - i + 1); -- Is this right? Maybe not!
-- What if s'first /= 1?
end loop;
return t;
end rev;
p: String := "Hi Mom!";
q: String := rev(p);
...
Notice the String parameter and return type: Can be any size!
Subtypes of Unconstrained Array Types
- We can create a constrained subtype of an unconstrained type
type Int_Array is array(natural range <>) of Integer;
subtype IA3 is Int_Array(1 .. 3);
subtype IA5 is Int_Array(1 .. 5);
a3: IA3 := (31, 32, 33);
a5: IA5 := (51, 52, 53, 54, 55);
if a3 = a5 then -- Legal?
We will see benefits of this later
Where are Constrained and Unconstrained Array Types Allowed
- Array variables and actual parameters MUST be constrained!
- Formal parameters can be either constrained or unconstrained
declare
subtype Bit_String is String(1 .. 32);
procedure put(b: Bit_String) is -- Constrained parameter
begin
for i in b'range loop put(b(i), 1); end loop;
end put;
function rev(S: String) returns String is
t: String(1 .. s'length);
begin
for i in 1 .. t'range loop
t(i) := s(s'last - i + 1);
end loop;
return t;
end rev;
p: String := "Hi Mom!";
q: String := rev(p);
Imagine having to write separate put_reverse for each size string!
Side note: Stroustrup liked Pascal's strong type checking, but
disliked its lack of anything like unconstrained arrays.
Unconstrained Array Types and Declare Blocks
...
declare
s: String := ada.text_io.get_line; -- Return type?
begin
put_reverse(s(2 .. s'last));
-- Can also do this:
put_reverse(get_line);
end;
Example 2:
get(n);
declare
s: String(1 .. n);
begin
put(s);
end;
Array Operations: Concatenate, Slice, Comparison
Array Operations
- Here are some additional operations on arrays:
- Concatenation: join two arrays together
- Slice: treat a part of an array as a whole array
- Comparison: copare values of two arrays
- Assignment: copy values of one array into another
- These operations are more useful because of unconstrained array types
- These operations work on ALL (single dimension) ARRAYS!
Concatenation
- Concatenation joins two arrays into one:
s1: String := "Hi ";
s2: String := "Mom!";
...
put_reverse(s1 & s2); -- Actual param is array of length 7
put_reverse("Hi " & "Mom!"); -- Length 7 here too
Unconstrained types make this possible
This operation works on ALL (single dimension) ARRAYS!
Slice
- A slice of an array is treated as an entire array:
s: String := "Madam Im Adam!";
...
put_reverse(s(2 .. s'last-2); -- Output?
Unconstrained array types!
Not Just Strings
- These array operations work on any 1D array type!
- Example:
type Int_Array is array(natural range <>) of Integer;
procedure put_reverse(a: Int_Array) is
begin
for i in reverse a'range loop
put(a(i));
end loop;
end put_reverse;
a1: Int_Array(1 .. 5) := (1, 2, 3, 4, 5);
subtype IA3 is Int_Array(1 .. 3);
a2: IA3 := (11, 12, 13);
a3: IA3 := (21, 22, 23);
put_reverse(a1 & a2 & a3); -- Output?
put_reverse(a1(2 .. 4)); -- Output?
Can we combine concatenate and slice? Don't think so.
Slices: Parameter Passing, Dynamic Bounds, and Assignment
We can gain flexibility by passing a slice
to a parameter that's an unconstrained array
- Slices can also be used in assignments :
- Postpone until we've seen array assignment
- Slice bounds can be dynammic and can be used in assignment
- Example: slicedemo.adb and prettified
Comparison
- Relational operators operate elementwise on arrays:
s1: String := "car";
s2: String := "cat";
s3: String := "catenate";
-- Which are true?
b1: Boolean := s1 < s2;
b2: Boolean := s1 < s3;
b3: Boolean := s2 < s3;
b4: Boolean := s1 >= s2;
b5: Boolean := s1 >= s3;
b6: Boolean := s2 >= s3;
b7: Boolean := s2 = s3(1 .. 3);
Works for any 1D array type
Array Operations: Type Checking
- Array comparisons require same named types for operands
with ada.text_io; use ada.text_io;
procedure demo is
type IntArray5 is array(1 .. 5) of Natural;
squares: IntArray5 := (1, 4, 9, 16, 25);
cubes: IntArray5 := (1, 8, 27, 64, 125);
type IntArray is array(Natural range <>) of Integer;
ones5: IntArray(1 .. 5) := (others => 1);
ones6: IntArray(1 .. 6) := (others => 1);
twos5: IntArray(1 .. 5) := (others => 2);
begin
put_line(boolean'image( squares = cubes )); -- False
put_line(boolean'image( squares < cubes )); -- True
put_line(boolean'image( squares <= cubes )); -- True
put_line(boolean'image( ones5 < twos5 )); -- True
put_line(boolean'image( ones5 < ones6 )); -- True
-- put_line(boolean'image( cubes = ones )); -- Compile error
end demo;
Similar rule for slicing, concatenation, and assignment
Array Operation: Assignment
Array Assignment: Type Checking
- Arrays can be assigned
- Must have same named type on both sides
- Must have same length on both sides
- RT error of not same length
- Example
with ada.text_io; use ada.text_io;
procedure demo is
type IntArray5 is array(1 .. 5) of Natural;
squares: IntArray5 := (1, 4, 9, 16, 25);
cubes: IntArray5 := (1, 8, 27, 64, 125);
type IntArray is array(Natural range <>) of Integer;
ones5: IntArray(1 .. 5) := (others => 1);
ones6: IntArray(1 .. 6) := (others => 1);
twos5: IntArray(1 .. 5) := (others => 2);
begin
squares := cubes; -- Compiles, but silly!
ones5 := twos5; -- Also compiles, but silly
ones5 := ones6; -- Compile warning. RT Constraint_Error
ones6 := ones5; -- Compile warning. RT Constraint_Error
-- squares := ones5; -- Compile error
end demo;
What happens with the assignment: Different from Java!
Java Array Operations
- What happens with this Java code:
int i = 1;
int j = 2;
i = j;
j = 4;
Sop(i); // 2, of course
What happens with this Java code:
int[] a = {10, 20, 30};
int[] b = {10, 20, 30};
if (a == b) ... // T/F ?
b = a;
if (a == b) ... // T/F ?
b[0] = 99;
Sop(a[0]); -- What is printed
if (a == b) ... // T/F ?
What does the memory allocation look like?
Array Assignment and Equality Tests
type Myarray is array (1 .. 3) of Integer;
a, b: Myarray;
...
a := (10, 20, 30);
b := (others => 0);
if a = b then ... -- T/F ?
b := a;
if a = b then ... -- T/F ?
b(1) = 99;
sop(a(1)); -- What is printed
if (a = b) ... // T/F ?
Equality test and assignment:
- Equality test and assignment are element by element
- Only allowed if both operands are of the same named type
Reference and Value Semantics
- For arrays we say that Ada has value semantics
- Ada has value semantics
- Java has reference semantics
- Meaning
- Assignment and equality operate on values vs references
- In Ada, an array variable holds an array value,
in Java an array variable holds a reference.
- Semantics refers to the meaning of a statement
- Also true for other structured types
- Java objects have reference sementics
- Ada records have value semantics
Arrays: Enumerated Types for Indices
Enumerated Types
- Create new set of literals
- Example:
type Color is (red, blue, green);
room: color := red;
...
if room = blue then
...
for c in color loop
put(c'img)
Enumerated Types for Array Indices
- An array can have an enumerated type as indices
- Example:
type Color is (red, blue, green);
type Color_Values is array(Color) of Integer
CV1: Color_Values := (100, 200, 300);
CV2: Color_Values := (others => 100);
CV3: Color_Values := (red => 100, green => 300, blue => 222);
type days is (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday);
hours: array(Sunday .. Saturday) of Integer;
subtype weekdays is days range Monday .. Friday;
work_hours: array(weekdays) of Integer;
...
put(hours(Friday));
put(CV1(blue)); -- 200
put(CV2(blue)); -- 100
put(CV3(blue)); -- 222
for c in color loop
put(CV1(c));
end loop;
Arrays Components Must Have Known Size
Array Components Must Have Known Size
- Compiler must know the size of an array component.
- Thus, if the component is an array, it must be constrained.
- Remember:
type String is Array (Positive range <>) of Character;
Thus, this is illegal
type MyArray is Array(1 .. 10) of String;
Why: Size of string is not known
- Compiler does not know how big to make each element
Solutions
- Allocate strings of some maximum size and keep track of lengths
- Example problem: Read in 1000 strings, each of length up to 100
Max_String_Size: Constant := 100;
subtype Max_String is String(1 .. Max_String_Size);
Num_Strings: Constant := 1_000;
type String_Array is array(1 .. Num_Strings) of Max_String;
type String_Size is natural range 0 .. Max_String_Size;
type Size_Array is array(1 .. Num_Strings) of String_Size;
strings: String_Array;
sizes: Size_Array;
...
for i in 1 .. Num_Strings loop
getblock: declare
s: String := get_line;
begin
sizes(i) := s'length;
strings(i)(1 .. s'length) := s;
end getblock;
end loop;
- Later we see use records to package a string and a length so that
only one array is needed
type My_String is record
the_string: Max_String;
size: String_Size;
end record;
type String_Array is array(1 .. Num_Strings) of My_String;
Use Pointers as the array component
MaxSize: Constant := 100;
NumStrings: Constant := 10;
type StringArray is array(1 .. NumStrings) of access String;
These techniques work for any type of array
- For strings, of course, you can also use Bounded_String and
Unbounded_String
Subtypes for Indices and New Numeric Types and Subtypes
Subtype Definition
- A subtype restricts the values of a type
- Examples:
subtype Natural is Integer range 0 .. Integer'Last; -- Predefined
subtype Grade_Range is Integer range 0 .. 100;
g: Grade_Range; -- g must be in 0 .. 100
Subtype as Array Index
- A subtype is useful for specifying array indices
- Example:
-- Assume 10 students in the class
subtype Student_Range is Integer range 1 .. 10;
type Student_List is array(Student_Range) of Student;
sl: Student_List;
sr: Student_Range;
...
put(sl(sr));
for i in Student_Range loop
put(sl(i));
end loop;
Subtypes for Count and Array Index
- Array index subtypes provide a powerful mechanism for reliability
- Example:
Max_Students : Constant 100;
subtype Student_Count is Natural range 0 .. Max_Students;
subtype Student_Index is Student_Count range 1 .. Student_Count'Last;
type Student_List is array(Student_Index) of Student;
num_Students : Student_Count := 0;
i : Student_Index;
sl: Student_List;
...
-- Calculate a value for i. Constraint error raised if i out of range.
put(sl(i)); -- Can never get out of range error from i!
Can also use new types instead of subtypes ...
Type Checking New Integer Types
- Remember: Strong typing requires same named type (or subtype)
type Temperature is range -20 .. 120;
type pressure is range 0 .. 100;
t: Temperature;
p: Pressure;
...
t := p; --- error!
Types and Subtypes for Count and Array Index
Max_Students : Constant 100;
type Student_Count is range 0 .. Max_Students; -- New numeric type
subtype Student_Index is Student_Count range 1 .. Student_Count'Last;
type Student_List is array(Student_Index) of Student;
num_Students : Student_Count := 0;
i : Student_Index;
sl: Student_List;
notsogood : Natural;
...
-- Calculate a value for i. Constraint error raised if i out of range.
put(sl(i)); -- Can never get out of range error from i!
put(sl(notsogood)); -- Logic mistakes causes a compile error
Types are safer, but subtypes are a little easier.
- Need to know how to work with new numeric types, for example:
-
package Stdt_List_IO is new Ada.Text_IO.Integer_IO(Student_Count);
-
use Stdt_List_IO;
Subtypes Attributes
- Subtypes have attributes like arrays: first, last, range
- Subtypes do NOT have a 'length attribute
- Examples:
subtype Student_Range is Integer range 1 .. 10;
type Student_List is array(Student_Range) of Student;
sl: Student_List;
...
for i in Student_Range'first .. Student_Range'last loop
put(sl(i));
end loop;
for i in Student_Range'range loop
put(sl(i));
end loop;
-- put(Student_Range'length); -- Error: No 'length attribute
Subtypes: Type Checking
- Types and their subtypes are type compatible
- They can be freely mixed, despite having different names.
- Constraint Error raised if value is out of bound
- Example - where can Constraint Error be raised in the following:
n: Natural;
i: Integer;
...
ada.integer_text_io.get(n);
i := n;
ada.integer_text_io.get(i);
n := i;
All of the above compile.
Arrays of Arrays and Multi-Dimensional Arrays
Arrays of Arrays
- Java and Ada both have arrays of arrays:
int[][] a = new int[3][4]
...
Sop(a[1][2]);
type IA4 is array(1 .. 4) of Integer;
a: array(1..3) of IA4;
-- Components must have a named type and a known size
...
put(a(1)(3));
Ada has 2D Arrays
- Ada allows creation of 2D arrays (and higher dimension as well)
type A2D is array(1 .. 3, 1 .. 4) of Integer;
a: A2D;
...
put(a(1, 3);
These are significantly different from Java arrays of arrays
- Consider initializing all values to 0
for i in 1 .. 3 loop
for j in 1 .. 4 loop
a(i, j) := 0;
end loop;
end loop;
-- 'range avoids having to know bounds
for i in a'range(1) loop
for j in a'range(2) loop
a(i, j) := 0;
end loop;
end loop;
for x of a loop -- Iterator: Ada 2012 only
x := 0;
end loop;
When working with 2D arrays, it helps to know whether the array is
stored by row or by column
- AKA Row Major (ie first row, then second, ...)
or Column Major (ie first column, then second, ...)
- Speed of accessing
- Passing among languages
Another example is in Ada By Example
Arrays of any Dimension
- Not limited to 2 dimensions
Max_Size: Constant := 100;
type World is array(0 .. Max_Size, 0 .. Max_Size, 0 .. Max_Size)
of Integer;
w: World := (others => (others => (others => 0)));
Careful, these can become large fast!