This installment in my Ada tutorial series is designed to show how to use records, pointers and exceptions. Every C and C++ programmer probably remembers one of the first milestones in coming to grasp with pointers is the successful implementation of the linked list data structure.
First of all, after analyzing the source code of other Ada code on the Internet, it seems that the preferred method for naming variables and functions is The_Name and not TheName; use underscores instead of camel case. Also make sure you use uppercase at the beginning of a word too. This seems to be Ada style, so we might as well adopt it.
The program below should speak for itself, but I’ll just mention a few things.
- Records like structures in C, and that is all there is to them. In C++ structures are really just classes and the keyword is only there for C language compatibility.
- Recursive data structures, such as lists and trees, require forward declaration of the types. See the program below for details, but this should not be too much of a shock as C++ requires the same unless your working with templates, and even then…
- Exceptions will be covered more in a later tutorial, but I thought I would add it to the linked list code just to demonstrate the concept.
- The type keyword is also introduced, but we will cover it later. For now just know that it declares a new data type.
- Pointers in Ada are declared using the access keyword. I particularly like this keyword, because if you read the code, it makes sense in English. For example, “type Link is access Node;” can be read “type Link is access to a Node.”
- Pointers in Ada are implicitly dereferenced. If you want to explicitly dereference the pointer, use Ptr.all, but let’s not worry about it for now.
- GNAT implements garbage collection, so we can create objects and let the run-time worry about cleaning up the memory. Note that Ada implementations are not required to support garbage collection, and most have options for disabling the garbage collection.
- Finally, not-equal is /=, but due to Ada’s readability, you can probably figure that out from the code
So, with no further delay, the source code is below. I did test it with some simple scenarios, but I did not exhaustively test every possibility. (possible unit testing topic in the future?) Hopefully there are no bugs!
with Ada.Text_IO; use Ada.Text_IO; procedure ListMech is -- -- Define the list data structures -- Note: recursive data structs require forward declaration type Node; -- forward declare type Link is access Node; -- read literally: a "Link" accesses a "Node" type Node is -- now declare the Node type record Node_Id: Integer; -- prefer underbar to camel-case Next: Link; end record; type List is record Head: Link; -- first node in list Tail: Link; -- last node in list Length: Integer := 0; -- number of nodes in the list end record; Empty_Exception: exception; -- -- Inserts an ID into the linked list -- procedure Insert( Id: in Integer; Linked_List: in out List) is begin if Linked_List.Head = null then Linked_List.Head := new Node'(Id, null); Linked_List.Tail := Linked_List.Head; Linked_List.Length := 1; Put_Line("List empty => creating head node: " & Integer'Image(Id)); else Put_Line("Creating node: " & Integer'Image(Id)); Linked_List.Tail.Next := new Node'(Id, null); Linked_List.Length := Linked_List.Length + 1; Linked_List.Tail := Linked_List.Tail.Next; end if; end Insert; -- -- Removes and ID from the linked list (if available) -- procedure Remove( Id: in Integer; Linked_List: in out List ) is Curr_Link: Link := Linked_List.Head; Prev_Link: Link := null; Found_Flag: Boolean := False; begin -- make sure list is not empty if Linked_List.Head = null then raise Empty_Exception; end if; while Curr_Link /= null loop if Curr_Link.Node_Id = Id then Put_Line("Removing node: " & Integer'Image(Curr_Link.Node_Id)); if Curr_Link = Linked_List.Head then Linked_List.Head := Curr_Link.Next; else Prev_Link.Next := Curr_Link.Next; end if; Found_Flag := true; Linked_List.Length := Linked_List.Length - 1; exit; else Prev_Link := Curr_Link; Curr_Link := Curr_Link.Next; end if; end loop; if Found_Flag /= true then Put_Line("Node not in list: " & Integer'Image(Id)); end if; end Remove; -- -- Traverses the linked list and prints out the IDs at each node -- procedure Walk( Linked_List: in List ) is Link_Index: Link := Linked_List.Head; begin Put_Line("Walking the list(" & Integer'Image(Linked_List.Length)& "): "); loop exit when Link_Index = null; Put_Line("--> " & Integer'Image(Link_Index.Node_Id)); Link_Index := Link_Index.Next; end loop; end Walk; -- local variables Id_List: List; TestVector: array(Positive range <>) of Integer := (1, 2, 3, 4, 5); begin for Index in TestVector'Range loop Insert( TestVector(Index), Id_List ); end loop; New_Line; Walk( Id_List ); New_Line; Remove( 1, Id_List ); New_Line; Walk( Id_list ); New_Line; for Index in TestVector'Range loop Remove( TestVector(Index), Id_List ); end loop; -- list should be empty now New_Line; Remove( 9, Id_List ); exception when Empty_Exception => Put_Line("*** List is empty ***"); end ListMech;
The code is significantly longer this time, but I think we’re ready to move away from trivial programs. After all, we’re programmers, right? We fear nothing!
C:\work\ada\listmech>listmech.exe List empty => creating head node: 1 Creating node: 2 Creating node: 3 Creating node: 4 Creating node: 5 Walking the list( 5): --> 1 --> 2 --> 3 --> 4 --> 5 Removing node: 1 Walking the list( 4): --> 2 --> 3 --> 4 --> 5 Node not in list: 1 Removing node: 2 Removing node: 3 Removing node: 4 Removing node: 5 *** List is empty ***
Copy the source code into an editor and try it out for yourself. I am a better programmer than I was when I started with C++ years ago, but it felt very easy to develop this linked list code. I’m starting to appreciate the verbosity of the syntax, the rigidity of the compiler, and the elegance of the language. I hope you’re enjoying our endeavor too.