Indexed list

Indexed list

[Alex Crivat]

Say I have a generic package wich implements a doubly linked list.
What I want to do, and I could not find a way to do it, is to use this
list as an array with the posibility of using the index operator "()"
(I know, in ada this is not used as an operator).
For example in C++ language I can do this by overloading the "[]"
operator. So when I call the list with this operator and a interer
index as parameter it returns the element coresponding to that index.

Example:
A : ITEM;
L : DLIST; -- DLIST is a list of ITEM type elements;

And I want to be able to do something like:
A := L(3); -- wich will put in A the fourth element of my list.

Is there a way of doing this in Ada using operators or should I use a
custom function;

Re: Indexed list

[Lutz Donnerhacke]

* Alex Crivat wrote:
> Is there a way of doing this in Ada using operators or should I use a
> custom function;

You should use a custom function, but if you really need this, there is a
trick.  The '()' syntax is used in two contexts.  First as an array
subscript, as you like to recognise it.  And second as a function call.
Using access variables to function calls the same syntax applies.

So you have to set a variable either to an array or a function. Because a
variable can't be of type function, use access to function instead. You only
need a slight modification to set the initial value.

I'll provide you the short and the generic solution:
------------------------------------------------------------------------
with Ada.Text_IO;

procedure t is
   function Get(i : Natural) return Natural is
   begin
      return i + 4;
   end Get;
   
   type List is access function (i : Natural) return Natural;
   
   a : Natural;
   f : List := Get'Access;
begin
   a := f(3);
   Ada.Text_IO.Put_Line("a =" & Natural'Image(a));
end t;
------------------------------------------------------------------------
with Ada.Text_IO;

procedure t is
   generic
      type Item (<>) is limited private;
      type Offset (<>) is limited private;
      with function Get(i : Offset) return Item is <>;
   package GenList is
      type List is access function (i : Offset) return Item;
      Current : constant List;
   private
      function MyGet (i : Offset) return Item renames Get;
      Current : constant List := MyGet'Access;
   end GenList;
   
   function Get(i : Natural) return Natural is
   begin
      return i + 4;
   end Get;
   
   package MyList is new GenList(Natural, Natural);
   use MyList;
   
   a : Natural;
   f : List := Current;
begin
   a := f(3);
   Ada.Text_IO.Put_Line("a =" & Natural'Image(a));
end t;
------------------------------------------------------------------------

Have fun.

Re: Indexed list

[Matthew Heaney]

"Alex Crivat" <axu@rdsnet.ro> wrote in message
news:3922594d.0308150346.65657e94@posting.google.com...
> Say I have a generic package wich implements a doubly linked list.
> What I want to do, and I could not find a way to do it, is to use this
> list as an array with the posibility of using the index operator "()"
> (I know, in ada this is not used as an operator).
> For example in C++ language I can do this by overloading the "[]"
> operator. So when I call the list with this operator and a interer
> index as parameter it returns the element coresponding to that index.
>
> Example:
> A : ITEM;
> L : DLIST; -- DLIST is a list of ITEM type elements;
>
> And I want to be able to do something like:
> A := L(3); -- wich will put in A the fourth element of my list.
>
> Is there a way of doing this in Ada using operators or should I use a
> custom function;

You can't really use an operator.  You can do it this way in the latest
version of Charles:

procedure Op (L : List_Subtype) is
   I : Iterator_Type := Succ (First (L), Offset => 3);
   E : Element_Subtype := Element (I);
begin
   ...
end;

Of course, as with your example, this implies a linear search.  Another
option for you would be to use a map, instantiated with subtype Natural as
the key subtype.  In fact the hashed maps in Charles are implemented using a
doubly-linked list, allowing you do this:

procedure Op (M : Map_Subtype) is
   E : Element_Type := Element (M, Key => 3);
begin

This doesn't use an operator, but the syntax isn't that much different.

Hash table searches have constant time complexity of average, so lookups are
fast.  You could also use a sorted map, which has logarithmic time
complexity.

Depending on your requirements, you might also consider the vector and deque
containers, too.  Those containers support random access directly.

Charles has both doubly- and singly-linked list containers.

I just released a new version of Charles a couple of days ago:

URL:http://home.earthlink.net/~matthewjheaney/charles/

URL:http://home.earthlink.net/~matthewjheaney/charles/charles-20030813.zip

-Matt