



Sequential Search In An Unordered List





	The linear search program can, and should, be modified to contain a "while" loop instead of a "for" loop, as fol-
lows:





	I : Integer;

begin



	I := List'First;

	Found := False;

	while (I<=List'Last) and (not Found) loop

		if (List(I) <> Item) then

			I := I + 1;

		else

			Found := true;

			Index := I;

		end if;

	end loop;	



end Search;





Sequential Search In An Unordered List, Cont.





	Note that the "if" statement could also be eliminated as follows:





	I : Integer;

begin



	I := List'First;

	Found := False;

	while (I<=List'Last) and (List(I) <> Item) loop

		I : = I + 1;

	end loop;	



	if (I <= List'Last) then

		Found := true;

		Index := I;

	else

		Found := false;

	end if;



end Search;





Sequential Search In An Unordered List, Cont.





	Note that the last "if" statement can be simplified as follows:





	I : Integer;

begin



	I := List'First;

	while (I<=List'Last) and (List(I) <> Item) loop

		I : = I + 1;

	end loop;	



	Found := (I <= List'Last);

	Index := I;



end Search;





Sequential Search In An Unordered List, Cont.





	Note, however, that there is still a problem with the "while" loop; specifically, if the item to be searched for is not 
in the list, then Constraint_Error will be raised.



	To avoid this problem, Ada provides short-circuit evaluation operators: and then and or else.





	I : Integer;

begin



	I := List'First;

	while (I<=List'Last) and then (List(I) <> Item) loop

		I : = I + 1;

	end loop;	



	Found := (I <= List'Last);

	Index := I;



end Search;





Sequential Search In An Unordered List, Cont.





	Finally, note that this general linear-search algorithm can be used for virtually any item type.



type Item_Type is ...



type Item_Array_Type is array (Integer range <>) of Item_Type;



procedure Search         (				List : in Item_Array_Type;

				Item : in Item_Type;

				Index : out Integer;

				Found : out Boolean) is

	I : Integer;

begin

	I := List'First;

	while (I<=List'Last) and then (List(I) <> Item) loop

		I : = I + 1;

	end loop;	



	Found := (I <= List'Last);

	Index := I;

end Search;





Sequential Search In A Sorted List





	A version of order.adb that does not have a return statement in the middle of a loop is as follows:





begin

	I := List'First;

	while (I<=List'Last) and then (List(I)<Item) 

		I := I + 1;

	end loop;



	if (I>List'Last)

		Found := false;

	else if (List(I)<>Item)

		Found := false;

	else

		Found := true;

		Index := I;

	end if;

end Search;





Selection & Insertion Sorting





	Selection sort scans an array to select the item to be placed in a specific position I.



	Insertion sort inserts a single element at position I into it's proper position in the already sorted subarray in posi-
tions A'First..I-1.





Another Way To Store A List

(page 637)





	In contrast to the previous example, the following array type allows variable length lists:





			Max_List : constant := 100; 



			subtype Item_Type  is Integer;

			type Item_Array is array (Integer range <>) of Item_Type;



			subtype Index_Type  is Integer range 1..Max_List;

			subtype Length_Type is Integer range 0..Max_List;

			subtype List_Array  is Item_Array(Index_Type);



			type List_Type is

				record

					Length			: Length_Type;

					Items  			: List_Array;

				end record;





Inputting Data





				Number_List : List_Type;



				Input_Loop:

				loop

					exit Input_Loop when Text_IO.End_Of_File(Data_File);

					Number_List.Length := Number_List.Length + 1;

					Integer_IO.Get(					File => Data_File,

										Item => Number_List.Items(Number_List.Length));

					Text_IO.Skip_Line(Data_File);

				end Input_Loop;



				Selection_Sort(List => Number_List.Item(1..Number_List.Length));



				for Index in 1..Number_List.Length loop

					Integer_IO.Put(Item => Number_List.Items(Index));

					Text_IO.New_Line;

				end loop;





Inserting Into An Ordered List

(page 640)



		procedure Insert (					List : in out List_Type; Item : in Item_Type) is

			Place_Found : Boolean;

			Index : Integer;



			procedure Search_Ord (							List		:  in 		Item_Array;

										Item  		:  in 		Item_Type;

										Found 		: out 		Boolean;

										Index 		: out 		Integer) is separate;



		begin  -- Insert

			Search_Ord(				List  => List.Items(1..List.Length),

							Item  => Item,

							Found => Place_Found,

							Index => Index);

			for Count in reverse Index..List.Length loop

				List.Items(Count + 1) := List.Items(Count);

			end loop;

			-- List.Items(Index+1..List.Length+1) := List.Items(Index..List.Length)

			List.Items(Index) := Item;

			List.Length := List.Length + 1;

		end Insert;





The Search Procedure





				separate(Insert);

				procedure Search_Ord (								List		:  in 		Item_Array;

												Item  		:  in 		Item_Type;

												Found 		: out 		Boolean;

												Index 		: out 		Integer) is



					Position : Integer;

				begin

						Position :=  List'First;

						Search_Loop:

						loop

							exit Search_Loop when 							(Position > List'Last) or else

														(Item <= List(Position));

							Position := Position + 1;

						end loop Search_Loop;



						Found :=  Position <= List'Last;

						Index :=  Position;

				end Search_Ord;





Binary Search





	Assumes that the array is sorted.



	Eliminates half of the sub-array with each comparison.



	Two special cases occur: either the element is in the array or it is not in the array.



Binary Search (page 643)



		with Ada.Text_IO, Ada.Integer_Text_IO;

		use Ada;

		procedure Binary_Main is

			type Item_Array_Type is array (Integer range <>) of Integer;



			procedure Binary_Search (								List		: in 		Item_Array_Type;

											Item		: in 		Integer;

											Index		: out 		Integer;

											Found		: out		Boolean) is separate;



			A: Item_Array_Type (-3..11) := (-3=>1, -2=>2, -1=>3, 0=>5, 1=>23, 2=>77, others=>416);

			Found 			: Boolean;

			Index 			: Integer;

			Item  			: Integer := 77;

		begin

			Binary_Search (A, Item, Index, Found);

			if Found then

				Text_IO.Put ("The item ");

				Integer_Text_IO.Put (Item=>Item, Width=>2);

				Text_IO.Put (" was found at index ");

				Integer_Text_IO.Put (Item=>Index, Width=>2);

				Text_IO.Put_Line (".");

			else

				Text_IO.Put ("The item");

				Integer_Text_IO.Put (Item=>Item, Width=>2);

				Text_IO.Put_Line ("was not found.");

			end if;

		end Binary_Main;





Binary Search, Cont.





			separate(Binary_Main);

			procedure Binary_Search (								List		: in 		Item_Array_Type;

											Item		: in 		Integer;

											Index		: out 		Integer;

											Found		: out 		Boolean) is

				First_Index				: Integer := List'First;

				Last_Index 				: Integer := List'Last;

				Midpoint   				: Integer;

			begin

				Found := False;

				Index := 0;

				while (First_Index <= Last_Index) and not Found loop

					Midpoint := (First_Index + Last_Index) / 2;

					if (List(Midpoint) = Item) then

						Found := True;

						Index := Midpoint;

					elsif (Item < List(Midpoint)) then

						Last_Index := Midpoint - 1;

					else

						First_Index := Midpoint + 1;

					end if;

				end loop;

			end Binary_Search;





Algorithm Running Time Analysis





	The objective of a running time analysis is to determine the amount of time required by an algorithm.



	The running time for any particular algorithm is relative (to the language, computer, temperature, etc).



	The total number of operations (or statements) executed by a particular algorithm is only relative to it's parame-
ters.



	Consequently, running time analysis are done, and specified, in terms of the total number of operations.



	Running time analysis are typically based on the  worst case, but can also be done for the average case.



	Running times are specified using "big Oh" notation.





Example: Sequential Search





		procedure Search    (							List		: in Item_Array_Type;

									Item		: in Item_Type;

									Index		: out Integer;

									Found		: out Boolean) is

				I : Integer;

		begin

			I := List'First;

			Found := False;

			while (I<=List'Last) and then (List(I) <> Item) loop

				I : = I + 1;

			end loop;	



			Found := (I <= List'Last);

		end Search;







Total # of operations performed is (approximately):											T(n) = 4n + 5, where n is the length of the array.



Running time is therefore: O(n).





Other Examples





		procedure Output (List : in Item_Array_Type) is

		begin

			for i in List'Range loop

				Integer_Text_IO.Put(List(i));

			end loop;

			Text_IO.Put("All Done!");

		end Output;





Total # of operations performed is (approximately):											T(n) = 2n + 2



Running time is therefore: O(n).





Other Examples, Cont.





		procedure Output_Double (List : in Item_Array_Type) is

		begin

			for i in List'Range loop

				for j in List'Range loop

					Integer_Text_IO.Put(List(i));

					Integer_Text_IO.Put(List(j));

				end loop;

				Text_IO.Put("Done inner loop!");

			end loop;

			Text_IO.Put("Done outer loop!");

		end Output;





Total # of operations performed is (approximately):																	T(n) = 3n2 + 3n + 2



Running time is therefore: O(n2).





Other Examples, Cont.





		procedure Output_Triple (List : in Item_Array_Type) is

		begin

			for i in List'Range  loop

				for j in List'Range  loop

					for k in List'Range loop

						Integer_Text_IO.Put(List(i));

						Integer_Text_IO.Put(List(j));

						Integer_Text_IO.Put(List(k));

					end loop;

					Text_IO.Put("Done inner loop!");

				end loop;

				Text_IO.Put("Done middle loop!");

			end loop;

			Text_IO.Put("Done outer loop!");

		end Output;





Total # of operations performed is (approximately):																	T(n) = 4n3 + 3n2+ 3n + 2



Running time is therefore: O(n3).





Other Examples, Cont.





		procedure Output_Constant (y : in Integer) is

			x : Integer;

		begin

			x := 1;

			x := x + y;

			Integer_Text_IO.Put(x);

		end Output;





Total # of operations performed is (approximately):																	T(n) = 4



Running time is therefore: O(1).





Definitions For "big Oh" Notation





Let f(n) and g(n) be functions (with no negative coefficients).









Definitions For "big Oh" Notation, Cont.





Definition #1: f(n) is said to be L(g(n)) if f(n)<=g(n) for all n.









Intuitively, we simply say that n2 is less than n4.





Definitions For "big Oh" Notation, Cont.





Example:



		Suppose that:

				f(n) = n2

				g(n) = n4



Claim:



		f(n) is L(g(n)), or rather, n2 is L(n4)



Proof:



		Clearly, n2 <= n4.





Definitions For "big Oh" Notation, Cont.





Definition #2: f(n) is said to be CL(g(n)) if there exists a positive constant c such that f(n) <= cg(n) for all n.









Intuitively, we say that, to within a constant factor, f(n) is less than g(n).





Definitions For "big Oh" Notation, Cont.





Examples:



		f(n) = 3n + 2

		g(n) = 6n + 3



Claim:



		3n + 2 is CL(6n + 3)



Proof:



		If we let  c = 1 then we see that:



		3n + 2 <= 1(6n + 3) 

				    = 6n + 3



		Consequently, 3n + 2 is CL(6n+3).





Definitions For "big Oh" Notation, Cont.





Note that it may be the case that f(n) >= g(n).



Another Example:



		f(n) = 6n2 + 3

		g(n) = n2 + 2



Claim:



		6n2 + 3 is CL(n2 + 2)



Proof:



		If we let c = 6 then we see that:



		6n2 + 3 <= 6(n2 + 2)

					  = 6n2 + 12



		Consequently, 6n2 + 3 is CL(n2 + 2).





Definitions For "big Oh" Notation, Cont.





Definition #3: f(n) is O(g(n)) if there exists two positive constants c and n0 such that f(n) <= cg(n) for all n >= n0.







Intuitively, as n goes to infinity, f(n) is, to within a constant factor, less than g(n).



Stated another way, as n goes to infinity, f(n) is, to within a constant factor, bounded from above by g(n).





Definitions For "big Oh" Notation, Cont.





Example:



		f(n) = n2 + 1

		g(n) = n2



Claim:



		n2 + 1 is O(n2)



Proof:



		If we let c = 2 and n0 = 1 then we see that:



		 n2 + 1 <= 2n2  for all n >= n0 = 1.



		Consequently, n2 + 1 is O(n2).





Definitions For "big Oh" Notation, Cont.











Examples:



		f(n) = n2 + 1														r(n) = (1/2)n + 300

		g(n) = n + 6														s(n) = 4n2 + 2n + 25

		h(n) = n35 + n16 + n4 + 3n2 + 1035





Definitions For "big Oh" Notation, Cont.





In general, if 



			f(n) = am-1nm-1 + am-2nm-2 + ... + a1n1 + a0





Then f(n) is O(nm-1).



If we let:



			c = |am-1| + |am-2| + ... + |a1| + |a0|

			n0 = 1



Then we get:



			f(n) <= cnm-1



			for all n>=n0





Searching & Sorting Running Times





								Search								O(n)



								Search_Ord								O(n)



								Bin_Search								O(logn)



								Selection_Sort								O(n2)



								Insertion_Sort								O(n2)





Binary Search Analysis





	Note that each iteration of the main loop reduces the number of elements in the subarray to be searched by half.



	How long can this continue?  More formally, how many times can you divide a number N by 2 and still get a 
number >= 1?



	The answer is log2N



	Consequently, the total number of operations performed by Bin_Search is O(logn).



	*Note that the base 2 has been dropped from log2n





Analysis Rules







Rule #1:



Suppose that 					T(n) = k, for some constant k >= 1



Example:		



				Text_IO.Put(s);

				Text_IO.Get(str);

				x := x + 1;

				y := x;

				z := x;



				T(n) = 6



Convention:



		We say that T(n) is O(1)





Analysis Rules, Cont.





Rule #2:





Suppose that P1 and P2 are two program fragments that have running times that are O(f(n)) and O(g(n)).  Then the 
worst case running time for P1 followed by P2, is O(max(f(n),g(n)).





Analysis Rules, Cont.





Example:



			Integer_Text_IO.Get(n);													O(n)

			for i in 1..n loop

				Text_IO.Put("hello world");

			end loop;



			for i in 1..n loop													O(n2)

				for j in 1..n loop

					Text_IO.Put("hello world");

				end loop;

			end loop;





			T(n) is O(max(n,n2)) = O(n2)





Analysis Rules, Cont.







Rule #3:





Suppose a conditional statement consists of m conditions with running times O(f1(n)), O(f2(n)),....,O(fm(n)), and m 
options with running times O(g1(n)), O(g2(n)),...,O(gm(n)).  Then the worst case running time for the conditional 
statement is O(max(f1(n),f2(n),...,fm(n),g1(n),g2(n),...,gm(n)).





Analysis Rules, Cont.





Example:





			if (x = 1) then

					Text_IO.Put("hello world");

			elsif (x > y) then

					for i in 1..n loop

						for j in 1..n loop

							Text_IO.Put("hello world");

						end loop;

					end loop;

			else

					Text_IO.Put("hello world");





			T(n) is O(n2)





Analysis Rules, Cont.





Rule #4: (preliminary)



If a loop iterates f(n) times and the body of the loop on a single iteration has a running time of O(g(n)) then the entire 
loop has running time O(f(n)g(n)).



Generally, this is true, however



1.	It assumes that the loop termination test is O(1).

2.	It can be overly pessimistic.





Analysis Rules, Cont.





Example:



				for i in 1..n loop

						if (i = 1)

							for j in 1..n loop

								Text_IO.Put("hello world");

							end loop;	

						else

							Text_IO.Put("hello world");

						end if;

				end loop;



				Rules #3 and #4 would suggest that the running time is O(n2).

				However, in all actuality it is O(n).





Two-Dimensional Arrays





	A one dimensional array can be used to represent a list.

	A two dimensional array can be used to represent a table.



	Example:



	subtype Row_Type is Integer range 1..100;

	subtype Column_Type is Character range `A'..'I';

	type Table_Type is array (Row_Type,Column_Type) of Integer;



	Map : Table_Type;





Two-Dimensional Arrays, Cont.





	An individual component in a two dimentional array is accessed by indexing, which requires both a row and col-
umn index.

	Example:



	Map(1,'A')



	The indexed component can be used in the same way as any other variable or value of the component type.





Two-Dimensional Arrays, Cont.





	Another Example: (for representing high temperatures for each day of the year)

	subtype Weeks is Integer range 1..52;

	subtype Days is Integer range 1..7;

	type Year_Type is array (Weeks,Days) of Integer;



	Year : Year_Type;





	Another representation of basically the same thing:

	type Day_Type is

			(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

	subtype Weeks is Integer range 1..52;

	type Year_Type is array (Weeks, Day_Type) of Integer;



	Year : Year_Type;





	What is the difference between the above Year_Type and the following Year_Type?

	type Year_Type is array (Day_Type, Weeks) of Integer;





Two-Dimensional Arrays, Cont.





	One more example:

	type Color_Type is (Red, Orange, Yellow, Green, Blue, Indigo, Violet);

	type Make_Type is (Ford, Toyota, Hyundai, Jaguar, Citroen, BMW, Fiat);

	type Car_Type is array (Color_Type, Make_Type) of Float;





Processing Two-Dimensional Arrays





	Two dimensional arrays are typically processed along a row, column, or both.

	Occasionally, elements will be accessed "randomly."

	Consider the following declarations:

	Number_Of_Rows							: constant := 4;

	Number_Of_Columns							: constant := 4;



	subtype Row_Range								is Integer range 1..Number_Of_Rows;

	subtype Column_Range								is Integer range 1..Number_Of_Columns;

	type Table_Type								is array (Row_Range,Column_Range) of Integer;



	Table					: Table_Type;

	Total					: Integer;

	Row_Length					: Integer;

	Column_Length					: Integer;





Processing Two-Dimensional Arrays, Cont.





	Summing row #2 could be done as follows:

	Total := 0;

	for Column in Column_Range loop

		Total := Total + Table(2, Column);

	end loop;

	Integer_IO.Put(Item => Total, Width => 10);





Processing Two-Dimensional Arrays, Cont.





	Similarly for row #3:

	Total := 0;

	for Column in Column_Range loop

		Total := Total + Table(3, Column);

	end loop;

	Integer_IO.Put(Item => Total, Width => 10);







	These two loops could be combined in a doubly-nested loop:



	for Row in 2..3 loop

		Total := 0;

		for Column in Column_Range loop

			Total := Total + Table(Row, Column);

		end loop;

		Integer_IO.Put(Item => Total, Width => 10);

		Text_IO.New_Line;

	end loop





Processing Two-Dimensional Arrays, Cont.





	In general, if we wanted to do this for the first "Num_Rows" rows and first "Num_Columns," then this could be 
done as follows:



	for Row in 1..Num_Rows loop

		Total := 0;

		for Column in 1..Num_Columns loop

			Total := Total + Table(Row, Column);

		end loop;

		Integer_IO.Put(Item => Total, Width => 10);

		Text_IO.New_Line;

	end loop





Processing Two-Dimensional Arrays, Cont.





	Similarly, each column could be summed as follows:



	for Column in 1..Num_Columns loop

		Total := 0;

		for Row in 1..Num_Rows loop

			Total := Total + Table(Row, Column);

		end loop;

		Integer_IO.Put(Item => Total, Width => 10);

		Text_IO.New_Line;

	end loop





Processing Two-Dimensional Arrays, Cont.





	The array could be output as follows:



	for Row in 1..Num_Rows loop

		for Column in 1..Num_Columns loop

			Integer_IO.Put(Item => Table(Row, Column), Width => 15);

		end loop;

		Text_IO.New_Line;

	end loop







	Or as follows:



	for Column in 1..Num_Columns loop

		for Row in 1..Num_Rows loop

			Integer_IO.Put(Item => Table(Row, Column), Width => 15);

		end loop;

		Text_IO.New_Line;

	end loop





Processing Two-Dimensional Arrays, Cont.





	In general, rows can be processed as follows:



	for Row in Row_Range loop

		for Column in Column_Range loop

			-- Process Table(Row,Column) as necessary

		end loop;

	end loop







	In general, columns can be processed as follows:





	for Column in Column_Range loop

		for Row in Row_Range loop

			-- Process Table(Row,Column) as necessary

		end loop;

	end loop





Intializing A Two-Dimensional Array &

Array Aggregates





	A two-dimensional array can be initialized using a doubly nested loop:



	for Row in Row_Range loop

		for Column in Column_Range loop

			Table(Row,Column) := 0;

		end loop;

	end loop





Intializing A Two-Dimensional Array &

Array Aggregates





	As with one-dimentional arrays, array aggregates can be used with two-dimensional arrays.



	A value for every component must be provided in an aggregate.



	Consider the following declarations:

	Number_Of_Rows							: constant := 4;

	Number_Of_Columns							: constant := 5;        -- Note value of "5" here!!!!



	subtype Row_Range								is Integer range 1..Number_Of_Rows;

	subtype Column_Range								is Integer range 1..Number_Of_Columns;

	type Table_Type								is array (Row_Range,Column_Range) of Integer;



	Table					: Table_Type;





Intializing A Two-Dimensional Array &

Array Aggregates, Cont.





	The following aggregates would all assign the table to all zeros:

	All Elements By Position:



	Table		:=	(	( 0, 0, 0, 0, 0),

					( 0, 0, 0, 0, 0),

					( 0, 0, 0, 0, 0),

					( 0, 0, 0, 0, 0)  );



	Table		:=	(	( 0, 0, 0, 0, 0, 0), ( 0, 0, 0, 0, 0), ( 0, 0, 0, 0, 0), ( 0, 0, 0, 0, 0));





	Rows By Name, Columns By Position:



	Table		:=	(	1	=>	(0, 0, 0, 0, 0),

					2	=>	(0, 0, 0, 0, 0),

					3	=>	(0, 0, 0, 0, 0),

					4	=>	(0, 0, 0, 0, 0)  );





Intializing A Two-Dimensional Array &

Array Aggregates, Cont.





	Rows By Position, Columns By Name:



	Table		:=	(	(1 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0),

					(2 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0),

					(3 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0),

					(4 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0)  );



	Table		:=	(	(1..5 => 0),

					(1..5 => 0),

					(1..5 => 0),

					(1..5 => 0)  );





Intializing A Two-Dimensional Array &

Array Aggregates, Cont.





	All Elements By Name:



	Table		:=	(	1 => (1 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0),

					2 => (2 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0),

					3 => (3 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0),

					4 => (4 => 0, 2 => 0, 3 => 0, 4 => 0, 5 => 0)  );



	Table		:=	(	1 => (1..5 => 0),

					2 => (1..5 => 0),

					3 => (1..5 => 0),

					4 => (1..5 => 0)  );



	Table		:=	(	1..4  => (1..5 => 0)  );



	Table		:=	(Row_Range => (Column_Range => 0) );



*Note that many of these are possible only because all elements are being set to 0!





Intializing A Two-Dimensional Array &

Array Aggregates, Cont.



	The reserved word others may appear at the end of any list of the aggregate.

	Table		:=	(	1 => ( 2 | 3 => 34, others => 17),

					3 => ( 1 => 58, others => 26),

					others => ( 0, 0, 0, 0));



	Table := ( others => ( others => 0 ) );





Arrays of Arrays





	Another way to get a similar structure is to declare an array whose component type is an array.



	Hours_Per_Day : constant := 24;



	subtype Degrees is Integer;

	subtype Hour_Index is Integer range 1..Hours_Per_Day;

	type Hourly_Temperature is array (Hour_Index) of Degrees;



	Days_Per_Week : constant := 7;



	type Day_Type is

			(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

	type Daily_Temperatures is array (Day_Type) of Hourly_Temperatures;



	Week : Daily_Temperatures;





Arrays of Arrays, Cont.





	An individual component in such an array is accessed by indexing, which requires both a row and column index.

	Example:



	Week (Tuesday) (8)



	Note how this differs from how a two-dimensional array is indexed.

	The indexed component can be used in the same way as any other variable or value of the component type.





Arrays of Arrays, Cont.





	Except for the syntax of indexing, processing arrays of arrays and two-dimensional arrays is almost identical.



	Sum := 0;

	for Day in Day_Type loop

		for Hour in Hour_Index loop

			Sum := Sum + Week (Day)(Hour);

		end loop;

	end loop;

	Average_Hourly_Temperature := Sum / (Days_Per_Week * Hours_Per_Day);





Arrays of Arrays, Cont.





	Another approach:



	function Average_For_Day (Readings : in Hourly_Temperatures  ) return Degrees is

		Sum : Integer;

	begin

		Sum := 0;

		for Hour in Hour_Index loop

			Sum := Sum + Readings (Hour);

		end loop;

		return Sum / Hours_Per_Day;

	end Average_For_Day;



	Total := 0;

	for Day in Day_Type loop

		Total := Total + Average_For_Day ( Week (Day) );

	end loop;





Multidimensional Arrays





	Ada does not place a limit on the number of dimensions that an array can have.



	Number_Of_Items						: constant := 100;

	Number_Of_Stores						: constant := 10;



	subtype Item_Range is Integer range 1..Number_Of_Items;

	subtype Store_Range is Integer range 1..Number_Of_Stores;

	subtype Month_Range is Integer range 1..12;



	type Sales_Array is array (Store_Range, Month_Range, Item_Range) of Integer;	



	Sales					: Sales_Array;

	Current_Month					: Month_Range;

	Number_Sold					: Integer;





	See page 661 for a graphic view of Sales.





Multidimensional Arrays, Cont.





	Summing and printing the total number of each item sold by all stores, this year, to date:



	for Item in Item_Range loop

		Number_Sold := 0;

		for Store in Store_Range loop

			for Month in 1..Current_Month loop

				Number_Sold := Number_Sold + Sales(Store, Month, Item);

			end loop;

		end loop;

		Text_IO.Put("Item #");

		Integer_IO.Put(Item => Item, Width => 3);

		Text_IO.Put("Sales to date = ");

		Integer_IO.Put(Item => Number_Sold, Width => 6);

		Text_IO.New_Line;

	end loop;





	Note how any particular array item is accessed:

					Sales(Store,Month,Item);





Multidimensional Arrays, Cont.





	Summing and printing the total sales for each store:



	for Store in Store_Range loop

		Number_Sold := 0;

		for Item in Item_Range loop

			for Month in 1..Current_Month loop

				Number_Sold := Number_Sold + Sales(Store, Month, Item);

			end loop;

		end loop;

		Text_IO.Put("Store #");

		Integer_IO.Put(Item => Item, Width => 3);

		Text_IO.Put("Sales to date = ");

		Integer_IO.Put(Item => Number_Sold, Width => 6);

		Text_IO.New_Line;

	end loop;





Multidimensional Arrays, Cont.



	How would we output total sales for each month?

	Does the order of the dimensions in the declaration matter?

	How would we output total sales for each item and store?

	As stated previously, Ada places no limit on the number of dimensions.

	If we want to keep track of departments, we can add another dimension.

	subtype Dept_Range is Character range `A'..'Z';

	type Sales_Array is array (Store_Range, Month_Range, Item_Range, Dept_Range) of Integer;



	How would we visualize the array?

	How would an individual entry be accessed?

						Sales(1,5,4,'C')'





	What about aggregates?





Unconstrained Arrays



	A constrained array type is an array type with a specific index range.

	An unconstrained array type is an array type without a specific index range.

	All arrays are constrained to a specific index range.

	subtype Degrees is Integer;

	subtype Hour_Index is Integer range 1..24;

	subtype AM_Range is Hour_Index range 1..12;

	subtype PM_Range is Hour_Index range 13..14;

	type Day_Type is (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

	subtype Month_Type is Integer range 1..12;



	Unconstrained array type

	type Hourly_Array is array (Hour_Index range <>) of Degrees;



	Declarations:

	A : Hourly_Array (1..10);										- Legal

	A : Hourly_Array;										- Illegal





Unconstrained Arrays, Cont.





	Constrained array subtypes

	subtype Morning_Temperatures is Hourly_Array (AM_Range);

	subtype Daily_Temperatures is Hourly_Array (Hour_Index);



	Declarations:

	A : Morning_Temperatures;

	B : Daily_Temperatures;



	Unconstrained array types; arrays of arrays

	type Daily_Array is array (Day_Type range <>) of Daily_Temperatures;

	type Morning_Array is array (Day_Type range <>) of Hourly_Array (AM_Range);



	Declarations:

	A : Daily_Array (Tuesday..Friday);													- Legal

	B : Morning_Array (Tuesday..Friday);													- Legal

	A : Daily_Array;													- Illegal

	B : Morning_Array;													- Illegal





Unconstrained Arrays, Cont.



	Constrained array subtype

	subtype Daily_Temperatures is Daily_Array (Day_Type);



	Unconstrained two-dimensional array

	type Temperature_Array is array (Integer range <>, Integer range <>) of Degrees;



	Declarations:

	A : Temperature_Array (1..10,-5..0);													- Legal

	B :  Temperature_Array;													- Illegal



	Constrained two-dimensional array subtypes

	subtype This_Century_Temps is Temperature_Array (1..12, 1900..1999);

	subtype Last_Centery_Temps is Temperature_Array (1..12, 1800..1899);



	Declarations:

	A : This_Century_Type;

	B : Last_Century_Type;





Unconstrained Arrays, Cont.



	Unconstrained three-dimensional array type

	type Float_Array is array (Integer range <>, Integer range <>, Character range <>) of Float;

	subtype Cost_Array is Float_Array (1..20, 1..50, `A'..'E');

	subtype Pressure_Array is Float_Array (1..5, 12..22, `x'..'z');



	Declarations

	A : Float_Array (1..5, 15..20, -3..0);													- Legal

	B : Float_Array;													- Illegal

	A : Cost_Array;													- Legal

	B : Pressure_Array													- Legal



	Note that the component type must be a constrained type.

	Illegal array type declaration:

	type Weather_Array is array (Day_Type range <>) of Hourly_Array;





Array Attributes



	Recall the array attributes `First, `Last, `Range, and `Length defined for one-dimensional arrays.

	These can be generalized for multi-dimensional arrays.



	function Average (Value : in Float_Array) return Float is

		Sum : Float;

	begin

		Sum := 0.0;

		for Dimension_1 in Value'First(1)..Value'Last(1) loop

			for Dimension_2 in Value'First(2)..Value'Last(2) loop

				for Dimension_3 in Value'First(3)..Value'Last(3) loop

					Sum := Sum + Value (Dimension_1, Dimension_2, Dimension_3);

				end loop;

			end loop;

		end loop;

		return Sum / Float (Value'Length(1) * Value'Length(2) * Value'Length(3));

	end Average;



Aggregates

One More Crazy, Yet Realistic Example





	MAX : constant Natural := 4;

	type Class_Type is (Freshman, Sophomore, Junior, Senior);

	type Dept_Type is (MTH,CSE,EE,CHM);



	type Name_Type is

		record

			First : String(1..16);

			Last : String(1..16);

		end record;



	type Student_Type is

		record

			Name : Name_Type;

			Class : Class_Type;

			Major : Dept_Type;

		end record;



	type Student_List is array (Natural range <>) of Student_Type;



	type Faculty_Type is

		record

			Name : Name_Type;

			Dept : Dept_Type;

		end record;



Aggregates

One More Crazy, Yet Realistic Example, Cont.





	type Course_Type is

		record

			Instructor : Faculty_Type;

			Students : Student_List(1..MAX);

		end record;



	type Offerings_Type is array(1..10) of Course_Type;



Chapter 13

Software Engineering Tip





	Use arrays when storing a list of values that are all of the same type.

	Use records when storing a collection of values that are of differring types.

	Combine and nest arrays and records for more complex data structures.

	Data structures used should accurately represent the data, processing, and problem to be solved.

	Use the simplest data structures and algorithms that are appropriate (don't use arrays or records if they are not 
necessary); simplify! simplify! simplify!
