From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,5c7d7b754dfe430e
X-Google-Attributes: gid103376,public
From: "Matthew Heaney" <matthew_heaney@acm.org>
Subject: Re: Help needed: Access type to functions in generic package
Date: 1999/09/13
Message-ID: <37dda46e@news1.prserv.net>#1/1
X-Deja-AN: 524713256
Content-transfer-encoding: 7bit
References: <37DBA86F.3805AA69@deathsdoor.com> <37dbe7da@news1.prserv.net>
 <37DBFEBF.B74D1958@deathsdoor.com> <37dc1a3f@news1.prserv.net>
 <7ri82a$45l$1@nnrp1.deja.com>
Content-Type: text/plain; charset="US-ASCII"
X-Complaints-To: abuse@prserv.net
X-Trace: 14 Sep 1999 01:27:10 GMT, 32.101.8.102
Organization: Global Network Services - Remote Access Mail & News Services
Mime-version: 1.0
Newsgroups: comp.lang.ada
Date: 1999-09-13T00:00:00+00:00
List-Id: <comp.lang.ada>

In article <7ri82a$45l$1@nnrp1.deja.com> , zeiram@deathsdoor.com  wrote:

> By "dynamic implementation", I meant a definition of my maze with
> access types to the components of my maze. A bit "a la" sparse
> matrix. With that, the memory space is allocated only when a new
> corridor is created at run time.

You've seen the static implementation of the matrix in a previous post.
Now, here's an idea for a dynamic implementation:

generic

   type Item_Type is private;

package P is

   type T (X, Y, Z : Positive) is private;

   procedure Set_Item
     (O       : in out T;
      X, Y, Z : in     Positive;
      Item    : in     Item_Type);

   function Get_Item
     (O       : T;
      X, Y, Z : Positive) return Item_Type;


private

   type Node_Type;
   type Node_Access is access Node_Type;

   type Node_Type is
      limited record
         Index : Positive;
         Item  : Item_Type;
         Next  : Node_Access;
      end record;

   type Array_2D_Type is
      array (Positive range <>, Positive range <>) of Node_Access;

   type T (X, Y, Z : Positive) is
      record
         Array_2D : Array_2D_Type (1 .. X, 1 .. Y);
      end record;

end P;


This is a sort of sparse matrix.  You statically allocate an array for the
first 2 dimensions, but the 3rd dimension is dynamically allocated.

Here, I've implemented the 3rd dimension as a linked list.  To find an item,
you'll have to traverse the list until you find the Index you're interested
in.

This is space efficient, but grows more time inefficient as the number of
items in the column increases.

An alternative approach is to allocate the 3rd dimension as an array.
Fetching an item then requires only O(1) time, although it's not as space
efficient as the linked list (for large values of Z).

Is something like this what you had in mind?

(Je ne parle qu'un peu de francais.  Peut-etre vous pouvez demander les
autres francais sur le newsgroup fr.comp.lang.ada.)

Matt