Gem #5: Key-Based Searching In Set Containers

by Matthew Heaney —On2 Technologies

Let's get started…

This example demonstrates how to use hashed set containers.

We are given the task of implementing a game in which a user navigates among components in a maze. These map-sites comprise walls, rooms, and doors. One of the features of the game is the ability to find room objects given a room number, and we implement that feature using a set container.

The map-site objects in our simulation are members of a common class. We use a tagged type declared as follows:

  type Map_Site is abstract tagged limited null record;

The (abstract) type has a single (abstract) operation to provide navigation to a site object:

  procedure Enter (Site : in out Map_Site) is abstract;

Next we implement concrete type Room, which derives from Map_Site. The declaration of the Room type looks like this:

  type Room (<>) is limited new Map_Site with private;

The room type is limited and indefinite (because it has “unknown discriminants”), which means that objects of the type must be explicitly initialized by calling a constructor-style function, declared as follows:

  not overriding
  function New_Room (Number : Positive) return not null access Room;

There is no way to create a room object other than to call New_Room, which is where we insert new room objects into the set used to find instances. Now we turn to the package body and the instantiation of the set package. The generic actual type is just a simple named access type (the same one we use to allocate instances):

   type Room_Access is not null access Room;

To instantiate the (hashed) set package, we need both a hash function and an equivalence function. The hash function for sets is a mapping of element value to hash value. So how do we make a hash value from a room object? The natural choice is to use the room number as the hash value for a room object, so our hash function for rooms looks like this:

   function Hash (R : Room_Access) return Hash_Type is
   begin
      return Hash_Type (R.Number);
   end;

For the equivalence function, we can just use the predefined equality operator for type Room_Access, since set elements are access values, and access values are unique for distinct room objects.

We now have everything we need to instantiate the generic hashed set container:

   package Room_Sets is new Ada.Containers.Hashed_Sets
     (Element_Type        => Room_Access,
      Hash                => Hash,
      Equivalent_Elements => “=”);

   Room_Set : Room_Sets.Set;

We are finally in a position to implement the Room constructor function, which looks like this:

   function New_Room (Number : Natural) 
     return not null access Room 
   is
     R : constant Room_Access := new Room (Number);
   begin
     Room_Set.Insert (R);
     return R;
   end New_Room;

Now that we have implemented the necessary infrastructure for creating room objects, we have to implement the function for looking up room objects using the room number as the key. Our function is declared as follows:

   
   function Find_Room (Number : Natural) return access Room;

Now comes the interesting part. The set records all Room objects that have been created, so if a room with that number exists, it will be in the set. Our problem is that we have no immediate way to search for room objects given a room number. Remember that this is a set of rooms (not a map with room number as the key) and the search function for the instantiation looks like this:

   function Find (Container : Set; Item : Room_Access) return Cursor;

The issue is that we have a room number, not a room object, so how do we look up a room object according to its number?

The solution is to take advantange of the nested generic package Generic_Keys provided by the sets, which allows you to view a set element in terms of its key. It has generic formals very similar to the set package itself, except that the operations apply to a generic formal Key_Type instead of to the element type.

One requirement for using that package is that the generic actuals for keys must deliver the same values as the generic actuals for elements. For example, the function to return the hash value of a room number (the key) must return the same value as the function that returns the hash value of the room object (the element) with that room number. So we instantiate the nested package as follows:

   function Get_Room_Number (R : Room_Access) return Natural is
   begin
      return R.Number;
   end;

   function Room_Number_Hash (N : Natural) return Hash_Type is
   begin
      return Hash_Type (N);
   end;

   package Room_Number_Keys is new Room_Sets.Generic_Keys 
    (Key_Type        => Natural, 
     Key             => Get_Room_Number, 
     Hash            => Room_Number_Hash, 
     Equivalent_Keys => “=”);

We are now ready to implement the Find_Room function. The package Room_Number_Keys provides a key-based search function, so we call that to search the set for a room object with the given room number:

   function Find_Room (Number : Natural) return access Room is
      C : constant Room_Sets.Cursor :=
            Room_Number_Keys.Find (Room_Set, Number);
   begin
      if Has_Element (C) then
         return Element (C);
      else
         return null;
      end if;
   end Find_Room;

The search function returns a cursor, and the cursor value indicates whether the search was successful. If a room object having that room number is in the set, Has_Element returns True and so we return the Room object designated by the cursor. If that number was not found (because no room object having that number was in the set), we simply return null.

The package Generic_Keys has a few other interesting features, including the ability to modify set elements, but we'll defer that discussion until a future time. In the meantime, have fun with the containers!

Related Source Code

Ada Gems example files are distributed by AdaCore and may be used or modified for any purpose without restrictions.