TABLES
version 1.11
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.


Tables project is a part of the simple components for Ada project and can be obtained with it. Alternatively the latest version can be here.

Download Tables     Platform:   64- 32bit
Fedora packages   precompiled and packaged using RPM     [Download page] [Download page]
Debian packages   precompiled and packaged for dpkg   [Download page] [Download page]
Source distribution (any platform)   tables_1_11.tgz (tar + gzip, Windows users may use WinZip)   [Download]

See also changes log.


[TOC][Next]

1. Tables

The generic package Tables provides tables searched using string keys. The binary search is used for names of known length (see Find). It is also possible to search a table for names of unknown length, i.e. to parse a string using the table (Get). In this case the search time is near to logarithmic, but in the worst case can be linear (when the 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 each table item. The table is initially empty. It is automatically enlarged as new items are added. Upon destruction the memory used by 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 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
Locate   Find item or parse string returning an offset to
Replace   Replace item

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

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. When the parameter Offset is specified it is set to the offset of the inserted item. All table items have offsets starting from 1. Items are alphabetically ordered. 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.

function Locate (Folder : Table; Name : String) return Natural;

The function Locate returns the positive offset to item specified by Name. The result 0 when no item is found. The offset can be used in operations GetName, GetTag. Note that the offset indicates the item no longer Folder is updated.

procedure Locate
          (  Source  : String;
             Pointer : in out Integer;
             Folder  : Table;
             Offset  : out Natural
          );

This procedure is similar to Get except that it returns offset to the matched item or else 0. The exception Layout_Error is propagated when the value of Pointer is not in the range Source'First..Source'Last+1.

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

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. When used, the parameter Offset will be set to the offset of the item. See also Add.

procedure Replace
          (  Folder : in out Table;
             Offset : Positive;
             Data   : Tag
          );

This procedure replaces the data of an existing item specified by its Offset. The offset shall be in 1..GetSize (Folder) range, otherwise End_Error is propagated. The parameter Data is the new data to be associated with the item.


[Back][TOC][Next]

2. Case-insensitive tables

2.1. Latin-1 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 a 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 procedure Replace does not change the spelling of the replaced name with regard to the case of its letters and blank characters.

The function Check_Matched is called by Get to ensure that the matched name ends correctly. For example, when the table contains a token for 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.

2.2. UTF-8 case-insensitive tables

Implementation nodes. The package described in this section is a part of the distribution of Simple Components for Ada, which is necessary in order to be able to use this package. Note that Simple Components for Ada contains the Tables software as an integral part, so you don't need to install Tables separately from Simple Components for Ada if you plan to use this package.

The child package Tables.UTF8_Names

generic
   with procedure
Check_Spelling (Name : String) is <>;
   with function
     
Check_Matched (Source : String; Pointer : Integer)
         return Boolean is <>;
   Blanks : Unicode_Set :=  -- Tabulator and spaces
      To_Set (16#09#) or Strings_Edit.UTF8.Maps.Constants.Space_Set;
   Ignored : Unicode_Set := -- Hyphen and others
      Strings_Edit.UTF8.Maps.Constants.Other_Format_Set;
package
Tables.UTF8_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 UTF-8 encoded names. The case as defined by the Unicode standard plays no role when upon matching (such as by Find or Get). However, the original case is preserved by the table, so GetName would return the name of a token exactly as it was given in Add or Replace. The parameter Blanks is the set of code points 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 parameter Ignored is the set of code points which are ignored upon matching. They are also removed when a name is stored in the table. The default value of Ignored is the set of Unicode other format code points, which contains soft hyphen, for example.

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 procedure Replace does not change the spelling of the replaced name with regard to the case of its letters and blank characters. When Name is an invalid UTF-8 string then it is recommended to propagate Constraint_Error out of Check_Spelling. Otherwise Add, Replace will propagate Data_Error.

When Name is not a valid UTF-8 string in Find, End_Error is propagated. For such a string IsIn returns false.When Soruce is not a valid UTF-8 string in Get its valid substring starting with Source (Pointer) is matched.

The function Check_Matched is called by Get to ensure that the matched name ends correctly. For example, when the table contains a token for 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.

Additionally the package provides:

function Canonize (Name : String) return String;

This function returns Name with all code points from the set Ignored removed. Constraint_Error is propagated when Name is an invalid UTF-8 string. All names put in a Dictionary go through this function after being checked using Check_Spelling.


[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. Installation

The software does not require special installation. The archive's content can be put in a directory and used as-is. For users of GNAT compiler the software provides gpr project files, which can be used in the Gnat Programming Studio (GPS).

To ease use of the software with GPS, it can be integrated into the GPS using the GPS Library Installer (gps_installer). Start the gps_installer as root (or with the corresponding administrative rights to the GNAT installation directory) specifying the source directory as the argument. Follow the instructions.

Project files Provides Use in custom project
tables Tables for Ada with "tables.gpr";

For Fedora and Debian Linux and their derivates packages are provided: see Debian and Fedora packages.

4.1. Fedora packages repository

The Fedora packages of this library are located in a yum software package manager repository. They can be searched, installed and updated automatically using yum. In order to do so, the file dmitry-kazakov.repo can be put into the directory /etc/yum.repos.d.

4.2. Debian packages repository

In order to use apt Debian repository for automatic install and update these packages add the following line to /etc/apt/sources.list:

deb http://dmitry-kazakov.de/distributions sid main

[Back][TOC][Next]

5. Changes log

Changes to the version 1.10:

Changes to the version 1.9:

Changes to the version 1.8:

Changes to the version 1.7:

Changes to the version 1.6:

Changes to the version 1.5:

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]

6. Table of Contents

1. Tables
2. Case-insensitive tables
   2.1. Latin-1 case-insensitive tables
   2.2. UTF-8 case-insensitive tables
3. Example
4. Installation
   4.1. Fedora packages repository
   4.2. Debian packages repository
5. Changes log
6. Table of contents