Adding functions to generic package

Adding functions to generic package

[Preben Randhol]

Hi

I'm using the charles library which has a generic list package. I would
like to add two procedures Randomise and Move so that all my lists can
use them. I cannot modify the library itself, so what choices do I have?
Is making a child package the only way to add the procedures in a
generic way?

Thanks in advance 

Preben

Re: Adding functions to generic package

[Matthew Heaney]

Preben Randhol <randhol+cla@pvv.org> writes:

> I'm using the charles library which has a generic list package. I
> would like to add two procedures Randomise and Move so that all my
> lists can use them. I cannot modify the library itself, so what
> choices do I have?  Is making a child package the only way to add the
> procedures in a generic way?

If you want to take advantage of the representation of the list
container type, then you would have to create a child.  Otherwise, if
your algorithm can be implemented in terms of the already-existing
(primitive) operations of the type, then it doesn't have to be a child.

You could do something like:

with Charles.Lists.Double.Unbounded;

generic
   with package P is new Charles.Lists.Double.Unbounded (<>);
  use P;
package Generic_List_Ops is
   procedure Randomize (Container : in out Container_Type);
   procedure Move (...);
end;


If these are truly generic algorithms, then you could implement them as,
well, generic algorithms, and then either use those as is, or use them
to implement the generic package above.

What do Randomize and Move do?  If you have a tentative implementation,
then post it (or just mail it to me) and we can figure what is the best
option for you.

-Matt

Re: Adding functions to generic package

[Preben Randhol]

On 2005-05-28, Matthew Heaney <matthewjheaney@earthlink.net> wrote:
> Preben Randhol <randhol+cla@pvv.org> writes:
> If you want to take advantage of the representation of the list
> container type, then you would have to create a child.  Otherwise, if
> your algorithm can be implemented in terms of the already-existing
> (primitive) operations of the type, then it doesn't have to be a child.
>
> You could do something like:
>
> with Charles.Lists.Double.Unbounded;
>
> generic
>    with package P is new Charles.Lists.Double.Unbounded (<>);
>   use P;
> package Generic_List_Ops is
>    procedure Randomize (Container : in out Container_Type);
>    procedure Move (...);
> end;

I see.

> If these are truly generic algorithms, then you could implement them as,
> well, generic algorithms, and then either use those as is, or use them
> to implement the generic package above.
>
> What do Randomize and Move do?  If you have a tentative implementation,
> then post it (or just mail it to me) and we can figure what is the best
> option for you.

It should be called Randomize_Container and be equivelent to the
Reverse_Container procedure except that it makes the order of the
elements random. I guess this doesn't seem to make sense for a List, but
I need it for a program that is asking questions from a list.

What Move does it to move element number 2 to number 4. If you have a
list perhaps the user wants to rearrange the order and drags one element
to another place in the list (I'm not talking GUI-wise). Then I noticed
it is a bit cumbersome not to have a move routine.

The procedures are give below:

-----------------------

   procedure Move
         (Container : in out Container_Type;
          From      : Natural;
          To        : Natural)
   is
      From_Iterator : Iterator_Type;
      To_Iterator   : Iterator_Type;
      Iter          : Iterator_Type := First (Container);
      Last_Element  : Natural;
   begin
      if To > From then
         Last_Element := To;
      elsif From > To then
         Last_Element := From;
      end if;

      if To /= From and then Last_Element <= Length (Container) then
         for I in 1 .. Last_Element loop
            if I = To then
               To_Iterator := Iter;
            elsif I = From then
               From_Iterator := Iter;
            end if;

            Increment (Iter);
         end loop;

         if To = Length (Container) then
            Append (Container, Element (From_Iterator));
         elsif To > From then
            Insert (Container, Succ (To_Iterator),
               Element (From_Iterator));
         elsif To < From then
            Insert (Container, To_Iterator,
               Element (From_Iterator));
         end if;

         Delete (Container, From_Iterator);
      end if;

   end Move;

-----------------------

   procedure Randomise_Container
         (Container : in out Container_Type;
          Loops : Natural)
   is
      subtype Container_Range is Integer range 1 .. Length (Container);

      package Random_Container is new
         Ada.Numerics.Discrete_Random (Container_Range);
      use Random_Container;

      Seed     : Generator;
      Number   : Natural;
   begin

      Reset (Seed);
      for I in 1 .. loops loop
         Reset (Seed);
         Reset (Seed);
         for Current in Container_Range loop
            Number := Random (Seed);
            Move (Container, From => Current, To => Number);
         end loop;
      end loop;

   end Randomise_Container;

-----------------------

Re: Adding functions to generic package

[Preben Randhol]

On 2005-05-28, Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> wrote:
> What Move does it to move element number 2 to number 4. 

for example.

> list perhaps the user wants to rearrange the order and drags one element
> to another place in the list (I'm not talking GUI-wise). Then I noticed

Should be: (I'm now  talking GUI-wise)...


Preben

Re: Adding functions to generic package

[Matthew Heaney]

Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> writes:

> On 2005-05-28, Matthew Heaney <matthewjheaney@earthlink.net> wrote:
> > What do Randomize and Move do?  If you have a tentative implementation,
> > then post it (or just mail it to me) and we can figure what is the best
> > option for you.
> 
> It should be called Randomize_Container and be equivelent to the
> Reverse_Container procedure except that it makes the order of the
> elements random. I guess this doesn't seem to make sense for a List,
> but I need it for a program that is asking questions from a list.





> What Move does it to move element number 2 to number 4. 

How is that different from Splice?


> If you have a list perhaps the user wants to rearrange the order and
> drags one element to another place in the list (I'm not talking
> GUI-wise). Then I noticed it is a bit cumbersome not to have a move
> routine.

That's what Splice does.


> The procedures are give below:
> 
> -----------------------
> 
>    procedure Move
>          (Container : in out Container_Type;
>           From      : Natural;
>           To        : Natural)


I see that the positions are integer indexes.  That means you'll have to
search for the iterator designating those nodes.  But once you have
iterator objects, just pass them to Splice.


>          if To = Length (Container) then
>             Append (Container, Element (From_Iterator));
>          elsif To > From then
>             Insert (Container, Succ (To_Iterator),
>                Element (From_Iterator));
>          elsif To < From then
>             Insert (Container, To_Iterator,
>                Element (From_Iterator));
>          end if;
> 
>          Delete (Container, From_Iterator);
>       end if;


Use Splice for this.


>    end Move;
> 
> -----------------------
> 
>    procedure Randomise_Container
>          (Container : in out Container_Type;
>           Loops : Natural)
>    is
>       subtype Container_Range is Integer range 1 .. Length (Container);
> 
>       package Random_Container is new
>          Ada.Numerics.Discrete_Random (Container_Range);
>       use Random_Container;
>
>       Seed     : Generator;
>       Number   : Natural;
>    begin
> 
>       Reset (Seed);
>       for I in 1 .. loops loop
>          Reset (Seed);
>          Reset (Seed);
>          for Current in Container_Range loop
>             Number := Random (Seed);
>             Move (Container, From => Current, To => Number);
>          end loop;
>       end loop;
> 
>    end Randomise_Container;


This is going to be way too expensive, since Move is implemented in
terms of integer indexes.  You definitely want to implement Randomize in
terms of iterators, not indexes.

I would implement the loop something like:

procedure Randomize (C : in out CT) is
   ...
   I : IT := First (C);
   J : IT;
   N : Natural := Length (C);

   procedure Get_Random_Iterator is ...;  -- see below
begin
   while I /= Last (C) loop  -- or: while N > 1 loop
      Get_Random_Iterator; -- get value of J
      Splice (C, Before => I, Iterator => J);
      I := Succ (J);
   end loop;
end Randomize;

Get_Random_Iterator returns an iterator (J) in the range [I, Back):

procedure Get_Random_Iterator is
   M : constant Natural := Random (G) mod N;
begin
   J := I;
   for Index in 1 .. M loop
      Succ (J);
   end loop;
   N := N - 1;
end Get_Random_Iterator;

The expression Random (G) is a call to the Generator function Random,
from an instantiation of Discrete_Random on type Integer.

This should perform much better than the algorithm you posted.

-Matt

Re: Adding functions to generic package

[Preben Randhol]

On 2005-05-29, Matthew Heaney <matthewjheaney@earthlink.net> wrote:
> Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> writes:
>
>> On 2005-05-28, Matthew Heaney <matthewjheaney@earthlink.net> wrote:
>> > What do Randomize and Move do?  If you have a tentative implementation,
>> > then post it (or just mail it to me) and we can figure what is the best
>> > option for you.
>> 
>> It should be called Randomize_Container and be equivelent to the
>> Reverse_Container procedure except that it makes the order of the
>> elements random. I guess this doesn't seem to make sense for a List,
>> but I need it for a program that is asking questions from a list.
>
>
>
>
>
>> What Move does it to move element number 2 to number 4. 
>
> How is that different from Splice?

I see now. By glancing at the procedure name I thought Splice meant that
one joined say two containers (as I read the first Splice and then
skipped the rest). Didn't think it was moving an element. I
didn't read the adb file for documentation. I'll have a look now and
change the code.

> This is going to be way too expensive, since Move is implemented in
> terms of integer indexes.  You definitely want to implement Randomize in
> terms of iterators, not indexes.

Yes I can agree with you on that. And since I can use Splice I don't need
to make a new Move. I think I'm also going to make a Find where Position
is Natural in stead of Iterator_Type.

> Get_Random_Iterator returns an iterator (J) in the range [I, Back):

Not sure I understand this. Wouldn't this mean that the randomisation
only will be able to put element further back in the list?

> This should perform much better than the algorithm you posted.

Yes I'll have a look and replace my quick and dirty procedure.

Preben

Re: Adding functions to generic package

[Matthew Heaney]

Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> writes:

> > Get_Random_Iterator returns an iterator (J) in the range [I, Back):
> 
> Not sure I understand this. Wouldn't this mean that the randomisation
> only will be able to put element further back in the list?

No, since J is moved (spliced) from the range [I, Back) to position I
(elements are thus moved from the back to the front).

There are two ranges: [front, I), which stores the randomized elements,
and [I, back), which stores the non-randomized elements.

The list starts out completely non-randomized, so [front, I) is empty
and [I, back) represents the entire list.

During iteration, Get_Random_Iterator is used to randomly select an
element from [I, back), then it gets moved (spliced) at the end of the
randomized range (just before I).  This means that every pass through
the loop, the range [front, I) grows and [I, back) shrinks.

The iteration terminates when [I, back) has only a single element.

Re: Adding functions to generic package

[Preben Randhol]

On 2005-05-29, Matthew Heaney <matthewjheaney@earthlink.net> wrote:
> No, since J is moved (spliced) from the range [I, Back) to position I
> (elements are thus moved from the back to the front).
>
> There are two ranges: [front, I), which stores the randomized elements,
> and [I, back), which stores the non-randomized elements.
>
> The list starts out completely non-randomized, so [front, I) is empty
> and [I, back) represents the entire list.
>
> During iteration, Get_Random_Iterator is used to randomly select an
> element from [I, back), then it gets moved (spliced) at the end of the
> randomized range (just before I).  This means that every pass through
> the loop, the range [front, I) grows and [I, back) shrinks.
>
> The iteration terminates when [I, back) has only a single element.

Yes after some careful reading I understood the code.

I have two different questions. How can one splice an element to the end
of the list? Mustn't one then Append it and Delete or call Splice twice;
first moving the element to the second last place and then move the last
place in front of it?

Reading the source code I find that the Splice function can only splice
an element before a given position.

Another question. Why isn't there a Swap function in the library like
the one that you have in the Reverse_Container? I can make something
using two splices although a bit less effective I should imagine?

Best wishes

Preben

Re: Adding functions to generic package

[Preben Randhol]

On 2005-05-29, Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> wrote:
> Another question. Why isn't there a Swap function in the library like
> the one that you have in the Reverse_Container? I can make something
> using two splices although a bit less effective I should imagine?

I ment not the same as it would have to be:

   procedure Swap (L,R : Iterator_Type);


Best wishes

Preben

Re: Adding functions to generic package

[Matthew Heaney]

Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> writes:

> I have two different questions. How can one splice an element to the end
> of the list? 

Just splice the element prior to the distinguished iterator value Back:

C : Container_Type;

procedure Op (I : Iterator_Type) is
begin
   Splice (C, Before => Back (C), Iterator => I);
end;

Back is the iterator that designates the virtual element
one-beyond-the-end of the list.


> Mustn't one then Append it and Delete or call Splice twice; first
> moving the element to the second last place and then move the last
> place in front of it?

No; just splice the element to the position before Back.  See above.


> Reading the source code I find that the Splice function can only
> splice an element before a given position.

Yes.  But if you splice an element before Back, that's the same as
appending it.


> Another question. Why isn't there a Swap function in the library like
> the one that you have in the Reverse_Container? I can make something
> using two splices although a bit less effective I should imagine?

Hmmm, not sure what you're asking for.  Swap exchanges the internal
linked lists of a pair of list containers.  Reverse_Container reverses
the nodes on the internal linked lists of a single list container.

The list container has both of the these operations, so what operation
do you need, that you want to implement using splice?

Thinking about it more, I think that what you're asking for is an
operation to swap a pair of nodes in the list, a la the Swap_Links
operation in the Ada 200Y container library.  I can add that operation,
if that's what you need.  (I just need to make sure I understand your
request.)

Note that I would probably just implement it using Splice.  That's what
I did in the standard container library reference implementation.

-Matt

Re: Adding functions to generic package

[Matthew Heaney]

Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> writes:

> On 2005-05-29, Preben Randhol wrote:
> > Another question. Why isn't there a Swap function in the library
> > like the one that you have in the Reverse_Container? I can make
> > something using two splices although a bit less effective I should
> > imagine?
> 
> I meant not the same as it would have to be:
> 
>    procedure Swap (L,R : Iterator_Type);


OK, that makes sense.  There's an operation like that (Swap_Links) in
the Ada 200Y standard container library.  I can add that to Charles.

-Matt

Re: Adding functions to generic package

[Preben Randhol]

On 2005-05-29, Matthew Heaney <matthewjheaney@earthlink.net> wrote:
> Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> writes:
>
>> On 2005-05-29, Preben Randhol wrote:
>> > Another question. Why isn't there a Swap function in the library
>> > like the one that you have in the Reverse_Container? I can make
>> > something using two splices although a bit less effective I should
>> > imagine?
>> 
>> I meant not the same as it would have to be:
>> 
>>    procedure Swap (L,R : Iterator_Type);
>
>
> OK, that makes sense.  There's an operation like that (Swap_Links) in
> the Ada 200Y standard container library.  I can add that to Charles.

I guess it must be: 

   procedure Swap (Container : in out Container_Type; L,R : Iterator_Type); 

as I want the Swap to Swap say element in position 4 with element in
postion 2 in the list but by using iterators to point at them.


Preben

Re: Adding functions to generic package

[Marius Amado Alves]

> I guess it must be:
>
>    procedure Swap (Container : in out Container_Type; L,R : 
> Iterator_Type);
>
> as I want the Swap to Swap say element in position 4 with element in
> postion 2 in the list but by using iterators to point at them.

No need. Cursors know their containers.

Re: Adding functions to generic package

[Matthew Heaney]

Preben Randhol <randhol+valid_for_reply_from_news@pvv.org> writes:

> I guess it must be: 
> 
>    procedure Swap (Container : in out Container_Type; L,R : Iterator_Type); 
> 
> as I want the Swap to Swap say element in position 4 with element in
> postion 2 in the list but by using iterators to point at them.

Yes, you need to pass the container too, since moving a node can change
the head and foot pointers, which are part of the representation of the
Container type.

Re: Adding functions to generic package

[Matthew Heaney]

Marius Amado Alves <amado.alves@netcabo.pt> writes:

> > I guess it must be:
> >
> >    procedure Swap (Container : in out Container_Type; L,R :
> > Iterator_Type);
> >
> > as I want the Swap to Swap say element in position 4 with element in
> > postion 2 in the list but by using iterators to point at them.
> 
> No need. Cursors know their containers.

No, this is wrong.

In Charles, iterators do *not* carry a pointer to container (they only
hold a pointer to the node containing the element), and so (in Charles)
you'd need to pass the container too.

But moving a node can change the value of the head and foot pointers,
which are part of the representation of the container type, so you need
to pass the container anyway.  The rule is that whenever an operation
manipulates the container object itself, the container is passed a
parameter.

Mario is probably thinking of the Ada 2005 standard container library.
Cursor types do indeed hold a pointer to the container, in addition to
the node.  However, the rule about manipulation of the container object
still applies (what a coincidence!), so the container is passed as a
parameter too (see the operation named Swap_Links).

-Matt

Re: Adding functions to generic package

[Marius Amado Alves]

>>> I guess it must be:
>>>
>>>    procedure Swap (Container : in out Container_Type; L,R :
>>> Iterator_Type);
>>
>> No need. Cursors know their containers. (Marius)
>
> No, this is wrong.
>
> In Charles, iterators do *not* carry a pointer to container...
> Mario is probably thinking of the Ada 2005 standard container library. 
> (Matthew)

Yes. Sorry.

> Cursor types do indeed hold a pointer to the container, in addition to
> the node.  However, the rule about manipulation of the container object
> still applies (what a coincidence!), so the container is passed as a
> parameter too (see the operation named Swap_Links).

Ada.Containers has this operation for Lists and Vectors:

procedure Swap (I, J      : in Cursor);

with semantics

"If either I or J is No_Element, then Constraint_Error is propagated. 
If I and J
designate elements in different containers, then Program_Error is 
propagated.
Otherwise Swap exchanges the values of the elements designated by I and 
J."

(cf. http://www.softdevelcoop.org/software/ada_containers)

Is "exchanging values" not "manipulating the container?"

Re: Adding functions to generic package

[Matthew Heaney]

Marius Amado Alves <amado.alves@netcabo.pt> writes:

> Is "exchanging values" not "manipulating the container?"

No.  Exchanging values implies that you're manipulating elements in the
container without changing the container object itself.

In the case of a list, the "container object itself" is a record
comprising pointers to the head and foot of the internal linked list,
and the number of elements.

When you "manipulate the container object itself," that means you're
changing the value of a head or foot pointer, or changing the length.  

That's why operation Swap_Links passes the container, since the head or
foot can change.

Swap does not pass the container, since it only exchanges element
values.  It doesn't manipulate the actual container object.

-Matt