Ada Programming/Libraries/Ada.Containers.Doubly Linked Lists

This language feature is only available from Ada 2005 on.

Ada.Containers.Doubly_Linked_Lists is a unit of the Predefined Language Environment since Ada 2005.

Introduction

One of the major additions to Ada 2005 is the container library. This library enables the Ada developer to manipulate data structures such as doubly linked lists, maps, sets and vectors. This page will show how the Ada.Containers.Doubly_Linked_Lists library works.

A doubly linked list is merely a linked list where each element is not only linked to the next, but also the previous. For more information, see doubly linked list.

Example

This is example usage is from an existing project.

worm.ads

This file represents the specification of a worm. 

with Ada.Containers.Doubly_Linked_Lists;
with Wormlevel, Protocol; -- , Handlers;
 
package Worm is
  
  use Wormlevel, Protocol; -- , Handlers;
  
  package Worm_Position_Container is new Ada.Containers.Doubly_Linked_Lists(Position);
  use Worm_Position_Container;
  
  type Worm_State is (Alive,Dead,Observing);
 
  type Worm_Type is
     record
        Worm_Body : List;
        Direction : Course  := North;
        Points    : Natural := 0;
        Number    : Positive;
        State     : Worm_State := Alive;
        Full      : Boolean := False;
     end record;
  type Worm_Type_Access is access Worm_Type;
  procedure Update_Worm (Worm : in Worm_Type_Access;
                         Lvl  : in Level_Access);
  procedure Turn_Left   (Worm : in Worm_Type_Access);
  procedure Turn_Right  (Worm : in Worm_Type_Access);
  procedure Kill        (Worm : in Worm_Type_Access);
 
end Worm;

As you can see, Ada.Containers.Doubly_Linked_Lists is instantiated with a type called “Position”. This type represents a tile type in a 2-dimensional array. The worm body is now represented by a doubly linked list, meaning we can loop through each element in either direction, by using the Next and Previous functions.

For those interested, the game can be found at GitHub.

Specification

--                     Standard Ada library specification
--   Copyright (c) 2003-2018 Maxim Reznik <reznikmm@gmail.com>
--   Copyright (c) 2004-2016 AXE Consultants
--   Copyright (c) 2004, 2005, 2006 Ada-Europe
--   Copyright (c) 2000 The MITRE Corporation, Inc.
--   Copyright (c) 1992, 1993, 1994, 1995 Intermetrics, Inc.
--   SPDX-License-Identifier: BSD-3-Clause and LicenseRef-AdaReferenceManual
-- -------------------------------------------------------------------------

generic
   type Element_Type is private;

   with function "=" (Left  : in Element_Type;
                      Right : in Element_Type)
                     return Boolean is <>;

package Ada.Containers.Doubly_Linked_Lists is

   pragma Preelaborate (Doubly_Linked_Lists);

   type List is tagged private;
   pragma Preelaborable_Initialization (List);

   type Cursor is private;
   pragma Preelaborable_Initialization (Cursor);

   Empty_List : constant List;

   No_Element : constant Cursor;

   function "=" (Left  : in List;
                 Right : in List)
                return Boolean;

   function Length (Container : in List) return Count_Type;

   function Is_Empty (Container : in List) return Boolean;

   procedure Clear (Container : in out List);

   function Element (Position : in Cursor) return Element_Type;

   procedure Replace_Element (Container : in out List;
                              Position  : in     Cursor;
                              New_Item  : in     Element_Type);

   procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Element : in Element_Type));

   procedure Update_Element
     (Container : in out List;
      Position  : in     Cursor;
      Process   : not null access procedure (Element : in out Element_Type));

   procedure Move (Target : in out List;
                   Source : in out List);

   procedure Insert (Container : in out List;
                     Before    : in     Cursor;
                     New_Item  : in     Element_Type;
                     Count     : in     Count_Type := 1);

   procedure Insert (Container : in out List;
                     Before    : in     Cursor;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Count     : in     Count_Type := 1);

   procedure Insert (Container : in out List;
                     Before    : in     Cursor;
                     Position  :    out Cursor;
                     Count     : in     Count_Type := 1);

   procedure Prepend (Container : in out List;
                      New_Item  : in     Element_Type;
                      Count     : in     Count_Type := 1);

   procedure Append (Container : in out List;
                     New_Item  : in     Element_Type;
                     Count     : in     Count_Type := 1);

   procedure Delete (Container : in out List;
                     Position  : in out Cursor;
                     Count     : in     Count_Type := 1);

   procedure Delete_First (Container : in out List;
                           Count     : in     Count_Type := 1);

   procedure Delete_Last (Container : in out List;
                          Count     : in     Count_Type := 1);

   procedure Reverse_Elements (Container : in out List);

   procedure Swap (Container : in out List;
                   I         : in     Cursor;
                   J         : in     Cursor);

   procedure Swap_Links (Container : in out List;
                         I         : in     Cursor;
                         J         : in     Cursor);

   procedure Splice (Target : in out List;
                     Before : in     Cursor;
                     Source : in out List);

   procedure Splice (Target   : in out List;
                     Before   : in     Cursor;
                     Source   : in out List;
                     Position : in out Cursor);

   procedure Splice (Container : in out List;
                     Before    : in     Cursor;
                     Position  : in     Cursor);

   function First (Container : in List) return Cursor;

   function First_Element (Container : in List) return Element_Type;

   function Last (Container : in List) return Cursor;

   function Last_Element (Container : in List) return Element_Type;

   function Next (Position : in Cursor) return Cursor;

   function Previous (Position : in Cursor) return Cursor;

   procedure Next (Position : in out Cursor);

   procedure Previous (Position : in out Cursor);

   function Find (Container : in List;
                  Item      : in Element_Type;
                  Position  : in Cursor := No_Element)
                 return Cursor;

   function Reverse_Find (Container : in List;
                          Item      : in Element_Type;
                          Position  : in Cursor := No_Element)
                         return Cursor;

   function Contains (Container : in List;
                      Item      : in Element_Type)
                     return Boolean;

   function Has_Element (Position : in Cursor) return Boolean;

   procedure Iterate
     (Container : in List;
      Process   : not null access procedure (Position : in Cursor));

   procedure Reverse_Iterate
     (Container : in List;
      Process   : not null access procedure (Position : in Cursor));

   generic
      with function "<" (Left  : in Element_Type;
                         Right : in Element_Type)
                        return Boolean is <>;

   package Generic_Sorting is

      function Is_Sorted (Container : in List) return Boolean;

      procedure Sort (Container : in out List);

      procedure Merge (Target : in out List;
                       Source : in out List);

   end Generic_Sorting;

private

   type List is tagged null record;

   Empty_List : constant List := (null record);

   type Cursor is null record;

   No_Element : constant Cursor := (null record);

end Ada.Containers.Doubly_Linked_Lists;

See also

Wikibook

External examples

Ada Reference Manual

Ada 2005

Ada 2012

Open-Source Implementations

FSF GNAT

drake

This article is issued from Wikibooks. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.