Advanced Array Types

v One-dimensional arrays:

SUBTYPE OneDSize IS 

 Integer RANGE 1..10;

TYPE OneDArray IS

 ARRAY( OneDSize ) OF Integer;

IntegerArray: OneDArray :=

 ( OTHERS => 0 );

Multidimensional Arrays

 

SUBTYPE TableRange IS 

 Integer RANGE 1..12;

TYPE TableType IS

 ARRAY( TableRange, TableRange ) OF Positive;

TwelveTable: TableType :=

 ( OTHERS => 0 );

 

FOR Row IN TableRange LOOP

 FOR Col IN TableRange LOOP

 TwelveTable( Row, Col ) :=

 Row * Col;

 END LOOP;

END LOOP;

 

Indices Other Than Integers

v Airline Example:

TYPE Cities IS ( BOS, ORD, EWR,

 PHL, SEA, DCA );

v List of Flights leaving each city:

TYPE FlightTable IS ARRAY( Cities )

 OF Natural;

CNAFlightsLeaving : FlightTable;

Flights From and To Each City

TYPE RouteMap IS

 ARRAY( Cities, Cities ) OF Natural;

CNACityPairs : RouteMap;

 

CNACityPairs( BOS, EWR ) := 2;

or

CNACityPairs( From, To ) := 3;

Different Index Types

v Number of flights leaving each city on each day

 

TYPE Days IS( Mon, Tue, Wed, Thu, Fri,

 Sat, Sun );

TYPE DailyFlights IS

 ARRAY( Cities, Days )OF Natural;

CNADailyFlights : DailyFlights;

v  

v Fares for each city pair

SUBTYPE Classes IS Integer RANGE 1..2;

SUBTYPE FareRange IS Float RANGE

 0.00..2000.00;

TYPE FareTable IS ARRAY( Cities,

 Cities, Classes ) of FareRange;

CNAFareTable : FareTable;

Examples of Using the Tables

v Average Total Number of Flights Leaving Boston

 

Examples of Using the Tables

v Average Total Number of Flights Departing from Boston

 

TotalFlights := 0;

FOR Dest IN Cities LOOP

 TotalFlights := TotalFlights +

 CNACityPairs( BOS, Dest );

END LOOP;

 

Examples of Using the Tables (cont.)

v Average Number of Flights Arriving at Chicago

 

v Average Number of Flights Arriving at Chicago

 

TotalFlights := 0;

FOR Origin IN Cities LOOP

 TotalFlights := TotalFlights +

 CNACityPairs( Origin, ORD );

END LOOP;

 

v Total Number of Legs Flown by CNA

v  

v  

v  

v  

v Total Number of Legs Flown by CNA

TotalLegs := 0;

FOR Origin IN Cities LOOP

 FOR Dest IN Cities LOOP

 TotalLegs := TotalLegs +

 CNACityPairs( Origin, Dest );

 END LOOP;

END LOOP;

Unconstrained Arrays

v What if we donÕt know at compile time how many elements we will have?

TYPE ListType IS

 ARRAY( Integer RANGE <> ) OF

 Float;

L1 : ListType( 1..50 );

L2 : ListType( -10..10 );

L3 : ListType( 0..20 );

v Assignment?

L1 := L2; -- Constraint_Error

L2 := L3; -- OK

L1( 20É40 ):= L2; -- OK

L2( 1..5 ) := L1( 6..10 ); -- OK

v String is just defined as:

TYPE String IS ARRAY( Positive

 RANGE <> ) OF Character;

v Attributes:

L2ÕFirst; -- Returns: -10

L2ÕLast; -- Returns: 10

L2ÕLength; -- Returns: 21

L2ÕRange; -- Returns: -10..10

 

FOR Elem IN L2ÕRange LOOP

 Ada.Float_Text_IO.Put(

 Item => L2( Elem ), Fore => 1,

 Aft =>2, Exp => 0 );

 Ada.Text_IO.New_Line;

END LOOP;

A General Sorting Program 

v How can we make a sorting routine for arrays of different sizes?

v Example: Number of Customer Support Calls

v Sort them in increasing order

v Display:

? All Days

? Weekdays

? Weekend Days

Unconstrained Arrays

TYPE Days IS ( Mon, Tue, Wed, Thu, Fri, Sat, Sun );

SUBTYPE DayRange IS Natural RANGE 0..6;

TYPE CallRecord IS RECORD

 DayOfWeek : Days;

 NumberOfCalls : Natural;

END RECORD;

TYPE Callers IS ARRAY( DayRange RANGE <> ) OF CallRecord;

Sorting Algorithm

v Fill each position in array, starting from the beginning of the array, with the smallest element in the subarray from that position to the end.

v Code?

 

Mathematical Vectors

v Definition of a Vector:

? A vector of N components is a set of N values that is ordered in the sense that each value is assigned a specific position in the set.

u U = <3, 5, -1> is different from V = <5, 3, -1>

v Develop a package to do vector arithmetic

v Make it so we can manipulate vectors of any length using the same package

? Make the definition general

 

 

TYPE Vector IS

 ARRAY( Integer RANGE <> ) OF Float;

 

V: Vector( 1..5 );

Q: Vector( -5..6 );

 

v Code?

Mathematical Matrices

v General package for multidimensional array arithmetic

TYPE Matrix IS ARRAY( Integer RANGE <>, Integer RANGE <> ) OF Float;

 

v Specify both ranges in declaration

MyMatrix : Matrix( 1..3, 1..4 );

 

 

FUNCTION Ò+Ó (K: ElementType; M : IN Matrix) RETURN Matrix IS

 Result: Matrix(MÕRange(1),MÕRange(2));

BEGIN

 FOR R IN MÕRange(1) LOOP

 FOR C IN MÕRange(2) LOOP

 Result (R, C) := K + M(R, C);

 END LOOP;

 END LOOP;

 RETURN Result;

END Ò+Ó;

v  

v How would you write Transpose?

 

LetÕs Look Under the Hood...

v How are arrays and matrices actually implemented?

v Consider:

 

T: ARRAY( 1..10 ) OF Integer;

 

v The compiler arranges to set aside 10 integer values

Storage Mappings

v After this, we can do things like:

 

T( 2 ) := 3;

Y := T( 3 );

 

v This looks straightforward, but something interesting is going on...

v How do compilers support subscripting?

v Other variables just address a particular piece of memory.

v An array (matrix, etc.) is just a single, big piece of memory.

v When generating instructions, the compiler must encode an address as being relative to the start of the array

v This is called Address (or Storage) Mapping

v Let add(T) be the machine address of the start of the array memory, and EUNITS be the number of storage units per array element.

v To address the i^th element, we need to skip over i - 1 elements.

v This gives us what?

v T(i) = add(T) + (i - 1) X EUNITS

v What about two-dimensional arrays?

v Given M having dimension R X C

v M(r,c)

v How is the addressing done here?

Two-Dimensional Arrays

v M(r,c)

 

add(M) +

 (r - 1)C X EUNITS +

 (c - 1) X EUNITS