Arrays
Arrays: Declaring, Attributes, Looping, Aggregates, Iterator
Java Array and Ada Equivalent
-
Two arrays of size 10, both with indices 0 .. 9
// Java
int[] arr1;
arr1 = new int[10];
...
S.o.p (arr1[0]);
-- Ada
arr2: array(0 .. 9) of Integer;
...
put( arr(0) ); -- Parens, not []
Syntax: (), not []
- Same syntax as a function call (both take and return a value)
Java version has two statements. Why?
What memory is allocated:
-
arr1 is a reference to an array
-
arr2 is the array itself
A Loop to Print the Array
for (int i = 0; i < 10; i++)
System.out.print(arr1[i]);
Ada:
for i in 0 .. 9 loop
put(arr2(i));
end loop;
More looping options below ('range and iterator)
Array Index Bounds Are Checked, Of Course
put( arr2(-1) );
get(i);
put( arr2(i) );
Bounds are checked
- At compile time, if possible
- At runtime, if necessary
Bounds Can Start Anywhere
a: array(0 .. 9) of Integer; -- Like C/Java.
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
Use attributes to find the bounds
Array Attributes: 'Length, 'First, 'Last
- Attributes provide information about the array
a : array(-10 .. 10) of Integer;
...
put(a'length); -- What is it?
for i in -10 .. 10 loop -- Must change code if change bounds
a(i) := 0;
end loop;
for i in a'first .. a'last loop -- Can change bounds without changing code
put(a(i));
end loop;
put( a(a'first) ); -- What's the difference?
put( a'first );
a'first is the first index, not the first value
Array types have attributes too (see below)
Attribute 'Range
- 'range is equivalent to 'first .. 'last
a : array(-10 .. 10) of Integer;
...
for i in a'range loop
put(i);
end loop;
It is not a single value (like 'first and 'last)
Some Other Attributes
- 'Component_Size - Number of bits in array element
- 'Size - Number of bits in array
- 'Address - Location of array
Aggregate Assignment
- Assign an entire array
- Java:
int[] a = {11, 22, 33}; -- Only in declaration
Ada:
squares: array(1 .. 5) of Natural := (1, 4, 9, 16, 25);
...
squares := (36, 49, 64, 81, 100);
Use parentheses to construct an aggregate value
Lengths of bounds and aggregate must match (but can use Others,
as shown below)
Can use aggregate anywhere, not only in declaration
Aggregate Assignment - Options
- 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:
c := (1 .. 5 => 0, 6 .. 10 => 1);
-- Can ranges overlap? No.
-- Must cover all values, or use others
Can use 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);
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
Case statement and in operator (but not for loop) allow similar syntax
Java Aggregate Assignment: Reliability
- Less reliable: no explicit specification of size
- No way to know whether the correct number of values are given
- And does this compile? If so, what is b.length?
int[] b = {11, 22, 33, };
Subtypes for the Index Range (and a Count)
- An array for holding up to 100 People
Max_Persons: Constant := 100;
subtype Person_Count_Type is Natural range 0 .. Max_Persons;
subtype Person_Index_Type is Person_Count_Type range 1 .. Max_Persons;
the_people: array(Person_Index_Type) of Person; -- Subtype for index
person_count: Person_Count_Type := 0;
max_age_index: Person_Index_Type := 1; -- Constrained to legal values
...
max_age_index := 1;
max_age := the_people(1).age;
for j in 2 .. person_count loop
if max_age > the_people(j) then
max_age_index := j;
max_age := the_people(j).age;
end if;
end loop;
put( the_people(max_age_index) );
Person_Count and max_age_index will have valid values
A New Type for the Count
- Same example as above, with a new Integer type
- An array for holding up to 100 People
Max_Persons: Constant := 100;
type Person_Count_Type is range 0 .. Max_Persons
with Default_Value => 0;
subtype Person_Index_Type is Person_Count_Type range 1 .. Max_Persons;
the_people: array(Person_Index_Type) of Person; -- Subtype for index range
person_count: Person_Count_Type := 0;
max_age_index: Person_Index_Type := 1; -- Guaranteed to be a legal index
...
max_age_index := 1;
max_age := the_people(1).age;
for j in 2 .. person_count loop -- j is of type Person_Index_Type
if max_age > the_people(j).age then
max_age_index := j;
max_age := the_people(j).age;
end if;
end loop;
put(Integer(person_count)); -- Cast person_count into an integer
put( the_people(max_age_index).age );
Person_Count and max_age_index will have valid values
Array Iterator
- One more way to loop through all elements
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; -- Can also modify each element!
end loop;
Also works for 2D arrays and for collections such as lists and trees
Array Types: Anonymous and Named
Anonymous Array Types
-
The arrays we've seen so far have had anonymous types
arr: array(1 .. 10) of Integer; -- Anonymous
Anonymous types have no name:
-
: array(1 .. 10) of Integer is an anonymous type
Arrays with named types are required in some places
Named Array Types
- Ada has named array types
type Int_10 is array(1 .. 10) of Integer;
a, b, sum: Int_10;
...
for i in a'range loop
sum(i) := a(i) + b(i);
end loop;
Nothing comparable in Java
- Well, you can create a new class containing an array
Named Array Types have Attributes, Of Course
type Int_10 is array(1 .. 10) of Integer;
a, b, sum: Int_10;
...
for i in Int_Array'range loop
sum(i) := a(i) + b(i);
end loop;
...
for i in Int_Array'first .. Int_Array'last loop
put(sum(i));
end loop;
put(Int_Array'length);
Why Have Named Array Types?
- Strong typing for:
- Parameters that are arrays
- Operations using arrays:
- Assignment
- Relational and equality operations (eg =, /=, <)
- Concatenation (ie &)
- Named types are required in these contexts
Array Parameters Require Named Types
Remember: 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 be of a Named Type
type Int_10 is array(1 .. 10) of Integer;
procedure okay(p: Int_10) is
begin
...
end okay;
a: Int_10;
...
okay(a);
This does not compile:
procedure problem(p: array(1 .. 10) of integer) is -- COMPILE ERROR
...
end problem;
b: array(1 .. 10) of integer;
...
problem(b); -- Nice idea, but COMPILE ERROR
Strong Type Checking
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;
...
-- Which of these compile?
foo(a, b);
foo(b, a);
Named parameter types provide strong type checking
Anything comparable in Java?
Array Operations - Also Strongly Typed
- Named array types make the following operations possible, with strong typing:
- Assignment
- Relational and equality
- Concatenation
- Operands must have SAME NAMED type
- We will look at these operations later
- After: fixed length, unconstrained array types, and strings
Arrays are Fixed Length
Arrays are Fixed Length
- Once an array is declared, its length can't change
type Int_4 is array(1 .. 3) of Integer;
a: Int_4;
begin
-- Both are errors:
a := (11, 22, 33, 44, 55);
a := (66, 77, 88, 99);
Array a is always length 4.
Array a cannot grow or shrink
Array Types and Memory Allocation
- Think for a second about memory allocation
- On what statement(s) is memory allocated?
type Int_10 is array(1 .. 10) of Integer;
a, b: Int_10;
sum: Int_10;
...
for i in a'range loop
sum(i) := a(i) + b(i);
end loop;
How much is allocated?
Problem with Fixed Length and Named Types: Not Flexible
- Distinct, identical version of sum_first_and_last is required for each types:
type Int_10 is array(1 .. 10) of Integer;
type Int_20 is array(1 .. 20) of Integer;
function sum_first_and_last(a: Int_10) return Integer is
(a(a'first) + a(a'last));
function sum_first_and_last(a: Int_20) return Integer is
(a(a'first) + a(a'last));
To get both flexibility and strong typing: Unconstrained array types
Unconstrained Array Types
Unconstrained Array Type: Both Strongly Typed and Flexible
type Int_Array is array(Natural range <>) of Integer;
function sum_first_and_last(a: Int_Array) return Integer is
(a(a'first) + a(a'last));
-- Constrained subtypes
subtype Int_10 is Int_Array(1 .. 10);
subtype Int_20 is Int_Array(1 .. 20);
-- Constrained arrays, all of type Int_Array
a: Int_Array(1 .. 5);
b: Int_10;
c: Int_20;
...
-- All compile
put( sum_first_and_last(a) );
put( sum_first_and_last(b) );
put( sum_first_and_last(c) );
Read as "Natural range box"
Bounds can be any natural type
One version of sum_first_and_last
Arrays a, b, and c are different sizes and of the same type
Unconstrained Array Types and Declare Blocks
...
type Int_Array is array(Natural range <>) of Integer;
n: Natural;
begin
get(n);
declare
a: Int_Array(1 .. n);
begin
for i in a'range loop
put(a(i));
end loop;
end;
Allows creation of dynamically sized arrays
Allocated on stack, not on heap
- Automatically deallocated, without garbage collection
Additional examples in notes on declare blocks
Actual Arrays Must be Constrained
- Types can be unconstrained, but ...
- Actual arrays cannot be of unconstrained type
- Actual arrays must be constrained
- Compiler must know how large to make an actual array
type Int_Array is array(Natural range <>) of Integer;
a: Int_Array; -- Compile error
-- Compiles
b: Int_Array(1 .. 5); -- Constrained array
subtype Int_10 is Int_Array(1 .. 10);
b: Int_10; -- Constrained array
Strings are Arrays of Characters
Strings are Arrays
- A String is an array of characters
s: String := "Hi Mom!";
t: String := "Hello There!";
u: String(1 .. 10);
...
for i in s'range loop
put(s(i)); -- Output: Hi Mom!
end loop;
s(4) := 'T';
put_line(s); -- Output: Hi Tom!
put_line(t); -- Output: Hello There!
put_line(u); -- What is output?
What memory is allocated?
What is output for t?
Put_Line and Type String?
-
Put_line takes strings of any length
-
String must be what king of type?
- Answer: Type String is defined as an an unconstrained array
Type String is Unconstrained (and Predefined)
- Example: Type String is unconstrained
-- Type String is PRE-DEFINED in package 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
Strings can be any size
- But once created, the size is fixed
DO NOT define type String yourself.
-
It's predefined in
Package Standard, which is automatically available for every program.
More Information on Strings
- Look here for more information on strings
- And here for information on input
of strings
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 (see below)!
Concatenation
- Concatenation joins two arrays into one:
procedure put_reverse(s: String) is
begin
for i in reverse s'range loop
put(s(i));
end loop;
...
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
This operation works on ALL (single dimension) ARRAYS (see below)!
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?
Question: Can we combine concatenate and slice? Yes:
put_reverse(Int_Array'(a1 & a2 & a3)(2..3));
-- Name needed for a slice, so use qualified expression
-- which explicitly gives the type of the expression
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
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!
Some Other Notes
Range and in Operator, More Attributes
- Is a variable in the range 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
Review: 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 static or dynamic predicate:
subtype Small_Odd is Natural with
static_predicate => Small_Odd in 1 | 3 | 5 | 7 | 9;
subtype Weird is Natural with
static_predicate => weird in 1 .. 5 | 10 | 15;
w: weird;
...
w := 6; -- ERROR
for i in weird loop
put(i); -- Output: 1 2 3 4 5 10 15
end loop;
- Constraint error if value other than 1, 2, 3, 4, 5, 10, 15 is put in 2
- Can be used for: in operator, loops
- Can NOT be used, unfortunately, for: declaring arrays
- Example with complete program: statpred.adb (and prettified)