TABLES
version 1.5
by Dmitry A. Kazakov

(mailbox@dmitry-kazakov.de)
[Home]

This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

As a special exception, if other files instantiate generics from this unit, or you link this unit with other files to produce an executable, this unit does not by itself cause the resulting executable to be covered by the GNU General Public License. This exception does not however invalidate any other reasons why the executable file might be covered by the GNU Public License.

Download tables_1_5.tgz (tar + gzip, Windows users may use WinZip) [Download]

[TOC][Next]

1. Tables

The generic package Tables provides tables searched using string keys. The binary search is used for names of known length. It is also possible to search a table for names of unknown length, i.e. to parse a string using the table. In this case the search time is near to logarithmic, but in worst case can be linear (when table contains tokens like "a", "aa", "aaa" and so on). The package is generic. The instantiation parameter is the type of the data tag associated with a table item. A table is initially empty. It is automatically enlarged as new items are added. Upon destruction the memory used by the the table is reclaimed. Items in the table can be accessed either by their offsets (in alphabetical order) or by names. Text parsing is also supported. Table assignment makes a deep copy.

generic
   type
Tag is private;
package Tables is
   type
Table is new Ada.Finalization.Controlled with private;

The following subroutines are provided by the package:

Add   Insert item
Delete   Remove item
Erase Remove all items
Find   Find item by name
IsIn Membership test
Get   Parse string
GetName   Get name of an item
GetSize   Get number of items
GetTag   Get tag of an item
Replace   Replace item

procedure Add (Folder : in out Table; Name : String; Data : Tag);

The procedure Add inserts an item into the table Folder. The value of the parameter Name is the item name. The parameter Data defines the data associated with the inserted item. The procedure raises the exception Name_Error if an item with the same name is already in the table. See also Replace.

procedure Delete (Folder : in out Table; Name : String);

The procedure Delete removes the item Name from the table Folder. Nothing happens when there is no item with the given name. See also Replace.

procedure Delete (Folder : in out Table; Offset : Positive);

This procedure removes an item by its offset. End_Error is propagated when there is no item with such offset.

procedure Erase (Folder : in out Table);

The procedure Erase removes all items from the table Folder.

function Find (Folder : Table; Name : String) return Tag;

The function Find returns the data associated with the item Name of the table Folder. The exception End_Error is propagated when there no such item in the table. See also Get.

procedure Get
          (  Source  : String;
             Pointer : in out Integer;
             Folder  : Table;
             Data    : out Tag
          );

The procedure Get is used to parse the string specified by the parameter Source using the table Folder. The procedure tries to find the item with the longest name that matches the string Source starting from the position defined by the parameter Pointer. On success Pointer is advanced to the first position following the name of the found item. I.e. Source (OldPointer..Pointer - 1) is the name of the found item. Note that unlike Find that searches tables in logarithmic time, Get could require linear time in some pathological cases. The exception End_Error is propagated when no table item matches the string. The exception Layout_Error is propagated when the value of Pointer is not in the range Source'First..Source'Last+1.

function GetName (Folder : Table; Offset : Positive) return String;

The function GetName returns the name of a table item. The parameter Offset specifies the item offset. All items in the table are enumerated in alphabetical order. The first item has the offset 1. The exception End_Error is propagated when there is no item with such offset. See also GetSize and GetTag.

function GetSize (Folder : Table) return Natural;

The function GetSize returns the number of items in the table Folder.

function GetTag (Folder : Table; Offset : Positive) return Tag;

The function GetTag returns the data associated with a table item. The parameter Offset specifies the item offset. All items in the table are enumerated in alphabetical order. The first item has the offset 1. The exception End_Error is propagated when there is no item with such offset. See also GetSize and GetName.

function IsIn (Folder : Table; Name : String) return Boolean;

The function IsIn returns true if Folder contains an item under the name Name.

procedure Replace (Folder : in out Table; Name : String; Data : Tag);

The procedure Replace inserts new or replaces an existing item of the table Folder. The value of the parameter Name is the item name. The parameter Data defines the data associated with the inserted item. See also Add.


[Back][TOC][Next]

2. Case-insensitive tables

The child package Tables.Names

generic
   with procedure
Check_Spelling (Name : String) is <>;
   with function
     
Check_Matched (Source : String; Pointer : Integer)
         return Boolean is <>;
   Blanks : Ada.Strings.Maps.Character_Set :=
      Ada.Strings.Maps.To_Set (' ' & Ada.Characters.Latin_1.HT); 
package
Tables.Names is
   type
Dictionary is new Table with private;

provides the type Dictionary, a descendant of Table. An instance of Dictionary has the same primitive operations (methods) as Table. The difference is that it is intended for dealing with case-insensitive names. So only one of "name", "Name", "namE" can be put into Dictionary. When matched by Find or Get the case of a token plays no role. However, the original case is preserved by the table, so GetName would return the name of an token exactly as it was given in Add or Replace. The parameter Blanks is the set of characters considered blank. All non-empty chains of characters from Blanks are considered equivalent when matched and compared. The original appearance of names containing blank characters is preserved by the table. By default Blanks contains space and horizontal tabulator.

The spelling of a name is checked before it is placed into a Dictionary. For this the procedure Check_Spelling is called. It may raise Constraint_Error to indicate a wrong spelling, which will then propagate out of Add or Replace.

The function Check_Matched is called by Get to ensure that the matched name ends correctly. For example, when the table contains a token black then Get would call Check_Matched on the string "Blackbird" with the parameter Pointer pointing to bird. Check_Matched could then discard this matching returning false. Check_Matched is never called with Pointer outside Source'Range.


[Back][TOC][Next]

3. Example

The following small example illustrates instantiation of the package Tables using a data type declared in another package. First we declare the type Employee, instances of which will be used as the data associated with the tokens of the table. File data.ads:

with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Calendar;          use Ada.Calendar;

package Data is
   type Employee is record
      HomeAddress : Unbounded_String;
      DateOfBirth : Time;
   end record;
   function Create
            (  Name  : String;
               Year  : Year_Number;
               Month : Month_Number;
               Day   : Day_Number
            )  return Employee;
   procedure Put (Data : Employee);
end Data;

Implementation, file data.adb:

with Text_IO; use Text_IO;

package body Data is
   function Create
            (  Name  : String;
               Year  : Year_Number;
               Month : Month_Number;
               Day   : Day_Number
            )  return Employee is
   begin
      return
      (  To_Unbounded_String (Name),
         Time_Of (Year, Month, Day)
      );
   end Create;
   procedure Put (Data : Employee) is
      Year  : Year_Number;
      Month : Month_Number;
      Day   : Day_Number;
      Sec   : Day_Duration;
   begin
      Split (Data.DateOfBirth, Year, Month, Day, Sec);
      Put ("Address : " & To_String (Data.HomeAddress));
      New_Line;
      Put ("Birth   :");
      Put (Year_Number'Image (Year));
      Put (Month_Number'Image (Month));
      Put (Day_Number'Image (Day));
      New_Line;
   end Put;
end Data;

Now the package Tables is instantiated with the type Data.Employee as the parameter. Note that this shall be done at library level, so it is a separate file employee_list.ads:

with Tables;
with Data;

package Employee_List is new Tables (Data.Employee);

Here we build a small data base of employees using the package Employee_List to keep it. Then the TOC of the list is printed and the user is asked to enter a name. The list is searched for the name and if such an employee exists, his data are printed. File table_example.adb:

with Data;          use Data;
with Employee_List; use Employee_List;
with Text_IO;       use Text_IO;

procedure Table_Example is
   List : Table;
   Name : String (1..80);
   Last : Natural;
   Data : Employee;
begin
   Add
   (  List,
      "Lou Harris",
      Create
      ( "10 Midway St., New Yourk, N.Y. 73371",
         1960, 12, 1
   )  );
   Add
   (  List,
      "John M.Knight",
      Create
      ( "12 West 42 Rd.A-844, Brooklin, N.Y. 27457",
         1971, 5, 8
   )  );
   Add
   (  List,
      "Alice Clark",
      Create
      ( "141 Penns. Avenue, Washington, D.C. 10399",
         1965, 10, 24
   )  );
   for Index in 1..GetSize (List) loop
      Put (GetName (List, Index));
      New_Line;
   end loop;
   loop
      Put ("Enter a name:");
      Get_Line (Name, Last);
      exit when Last = 0;
      begin
         Data := Find (List, Name (1..Last));
         Put (Data);
      exception
         when
End_Error =>
            Put ("Unknown");
            New_Line;
      end;
   end loop;
end
Table_Example;

[Back][TOC][Next]

4. Changes log

Changes to the version 1.4:

Changes to the version 1.3:

Changes to the version 1.2:

Changes to the version 1.1:


[Back][TOC]

5. Table of Contents

1. Tables
2. Case-insensitive tables
3. Example
4. Table of contents