Login | Register
My pages Projects Community openCollabNet

Discussions > issues > Question about Delete

charles
Discussion topic

Back to topic list

Question about Delete

Reply

Author Matthew Heaney <mheaney at on2 dot com>
Full name Matthew Heaney <mheaney at on2 dot com>
Date 2004-05-20 07:58:39 PDT
Message The latest release of the AI draft is here:

<http://www.ada-auth.​org/cgi-bin/cvsweb.c​gi/AIs/AI-20302.TXT?​rev=1.5>


Delete is described as follows:

procedure Delete (Container : in out Map;
                   Position : in out Cursor);

If Position equals No_Element, this operation has no effect. Otherwise,
Delete removes the node from the map and deallocates the node. Position
is set to No_Element on return.

The cursor-based delete in the ordered set has the same behavior:

procedure Delete (Container : in out Set;
                   Position : in out Cursor);

If Position equals No_Element, the operation has no effect. Otherwise,
Delete removes the element designated by Position from Container.
Position is set to No_Element on return.


The reason for this behavior is that computing the successor of an
element is not an O(1) operation.

For a map, there are empty buckets between each bucket (unless the map
is very full), so to compute the successor you must search

   Size (M) / (Length (M) + 1)

number of buckets, on average.

In the case of a set, you must either descend the right subtree (if this
is an anterior node) or ascend the tree (if this is a leaf node). The
cost is O(log n) in the worst case.

If you want the successor of a node, you must compute it prior to
calling Delete, like this:

declare
    C2 : Cursor := Next (C);
begin
    Delete (Map => M, Position => C);
    C := C2;
end;


Note that in the case of the list container, Delete really does return
the successor of the node deleted.






> --------------------​--------------------​--------------------​------------
>
> Subject:
> Question about Delete
> From:
> Pascal Obry <pascal at obry dot org>
> Date:
> Thu, 20 May 2004 10:53:27 +0200
> To:
> issues at charles dot tigris dot org
>
> To:
> issues at charles dot tigris dot org
>
>
> I have read in a document (maybe an old one) that Delete (Map, Cursor) should
> return the next element in Cursor or No_Element if Cursor point to the last
> element in the container.
>
> The following program shows that this is not the case:
>
> with AI302.Containers.Ind​efinite_Hashed_Maps;​
> with AI302.Strings.Hash;
>
> package Strings_Maps is
>
> package Containers is
> new AI302.Containers.Ind​efinite_Hashed_Maps
> (String, Integer, AI302.Strings.Hash, "=", "=");
>
> end Strings_Maps;
>
> with Ada.Text_IO;
>
> with AI302.Containers;
> with Strings_Maps;
>
> procedure Test_Delete is
>
> use Ada.Text_IO;
> use AI302.Containers;
> use Strings_Maps.Containers;
>
> Hash : Map;
> C : Cursor;
> Success : Boolean;
> begin
> Insert
> (Container => Hash,
> Key => "key1",
> New_Item => 1,
> Position => C,
> Success => Success);
>
> Insert
> (Container => Hash,
> Key => "key2",
> New_Item => 2,
> Position => C,
> Success => Success);
>
> if Length (Hash) /= 2 then
> Put_Line ("Number of items in Hash should be 2");
> end if;
>
> C := First (Hash);
>
> Delete (Hash, C);
>
> if C = No_Element then
> Put_Line ("Error, this should point to the next element");
> end if;
>
> Delete (Hash, C);
>
> if C /= No_Element then
> Put_Line ("Error, there is no more element, should be No_Element");
> end if;
> end Test_Delete;
>
> Can somebody clarify the proper semantic for Delete ? What is the very
> last document about the AI302 ?
>
> Thanks,
> Pascal.
>

--------------------​--------------------​--------------------​---------
To unsubscribe, e-mail: issues-unsubscribe@c​harles.tigris.org
For additional commands, e-mail: issues-help at charles dot tigris dot org

« Previous message in topic | 1 of 2 | Next message in topic »

Messages

Show all messages in topic

Question about Delete Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-20 07:58:39 PDT
     Re: Question about Delete Pascal Obry <pascal at obry dot org> Pascal Obry <pascal at obry dot org> 2004-05-20 08:15:19 PDT
Messages per page: