Board index » delphi » Deleting item from collection

Deleting item from collection

Hi...

I've a small problem.

I need to delete collection's item from procedure coled by ForEach
method. For example:

procedure MyColl.Example;
  procedure DoSth(Item : pointer); far;
  begin
    if .... then Delete(Item);
  end;
begin
  ForEach(@DoSth);
end;

When I'm calling this proc, I get Coll index out of range error.
I thing thats becouse ForEach loop is repeated Count times, and after
DoSth proc Count:=Count-1
I hope there is other way to delete coll item.

Could anybody help me, please ............. :))))

-------------------------------------------------------------------------------
   Maciek Grzyb                                 E-Mail: gr...@i-lo.tarnow.pl
-------------------------------------------------------------------------------

 

Re:Deleting item from collection


how about that:

procedure MyColl.Example;

function Matches(Item : Pointer):Boolean; far;
begin
  if .... then Matches := True else Matches := False;
end;

var
  P : PObject;
  Ok: Boolean;
begin
  Ok := True;

  while Ok do
  begin
    P  := FirstThat(@Matches);
    Ok := P<>Nil;
    if Ok then Delete(P);   { will not free memory ! }
                            { use Free(P) instead !  }
  end;
end;

--
Robert Mayer                                  Phone: (49) 9131 85 7211
University of Erlangen                        Fax  : (49) 9131 85 7293
Institut fuer Technische Physik I
Erwin-Rommel-Str. 1
D-91058 Erlangen
Germany

Re:Deleting item from collection


Quote
In article <1996Nov26.174809.15...@arl.mil> Maciej Grzyb wrote:

>Hi...

>I've a small problem.

>I need to delete collection's item from procedure coled byForEach
>method. For example:

As you suspect, the ForEach iterator is designed to apply an
action procedure to each item in a collection. If I tell you
how the iterator works, it may help you understand why it
fails.  

ForEach starts by taking the count and using it as a loop
variable.  It also establishes a pointer to the first item
in the collection's ItemList.  With the cpu registers set,
the loop process begins.  The loop counter and item reference
are saved to the stack, and the item being referenced is
pushed onto the stack to satisfy the formal parameter and the
action procedure is called.  Upon return, the referenced and
loop variable are recovered.  The reference is incremented by
the size of a pointer, and the loop counter is decremented.
If the counter is not zero the loop is re-entered.

Now, consider what happens when you delete an entry.  The
item is removed from the ItemList array, and all items above
it are moved down one position (to fill the gap, and the
count is decremented.  This causes the iterator to "skip"
the next item.

In the past when I've needed to do something similar, I've
used a tBitSet (see BITSET Unit available from my home page,
<http://members.gnn.com/RDonais/>) in something like:

procedure MyColl.Example;
VAR Idx: Longint;
    List: tpBitSet;

  procedure DoSth(Item : pointer); far;
  begin
    { --- what ever --- }
    if .... then List^.Include(Idx);
    Inc(Idx);
  end;

begin
  New(List, Init(Self.Count+1));
  Idx := 0;
  ForEach(@DoSth);
  While List^.Prev(Idx, Idx) Do
     Self.AtFree(Idx);
  Dispose(List, Done);
end;

I haven't tried either of the following, so I can't say
whether they actually work.  But they appear to have a
reasonable chance, so you might want to try them out:

procedure MyColl.Example;
VAR Idx: Integer;

  procedure DoSth(Item : pointer); far;
  begin
    Dec(Idx);
    if .... then AtDelete(Idx);
    DoSth := FALSE;
  end;

begin
  Idx := Count;
  LastThat(@DoSth);
end;

procedure MyColl.Example;
VAR Idx: Integer;

  procedure DoSth(Item : pointer); far;
  begin
    if .... then Begin
       FreeItem(Item);     { dispose of item }
       AtPut(Idx) := NIL;  { place holder }
    End;
    Inc(Idx);
  end;

begin
  Idx := 0;
  ForEach(@DoSth);
  Pack;
end;

Both solutions us an Idx variable so that the item will not
have to be searched.  This would probably be an important
point in the second method as the NIL pointers would more
than likely cause a search on a sorted collection to fail.
The first method uses the LastThat iterator to process the
list in reverse. Since the next item to be processed is
"below", we just might get away with adjusting "above".
The second uses ForEach to process the list in a forward
direction, but rather than alter the list, it marks items
to be deleted with a NIL pointer.  Once the iteration has
been completed, "Pack" is called to consolidate the list
and remove all NIL pointers.

Looks like they might work, but as I said earlier, I haven't
tried either one.  Let me know how you make out.

    ...red

Re:Deleting item from collection


In article <57np4h$...@news-c1.gnn.com> of Fri, 29 Nov 1996 16:51:27 in

Quote
comp.lang.pascal.misc, "R.E.Donais" <RDon...@gnn.com> wrote:

>ForEach starts by taking the count and using it as a loop
>variable.  It also establishes a pointer to the first item
>in the collection's ItemList.  With the cpu registers set,
>the loop process begins.  The loop counter and item reference
>are saved to the stack, and the item being referenced is
>pushed onto the stack to satisfy the formal parameter and the
>action procedure is called.  Upon return, the referenced and
>loop variable are recovered.  The reference is incremented by
>the size of a pointer, and the loop counter is decremented.
>If the counter is not zero the loop is re-entered.

>Now, consider what happens when you delete an entry.  The
>item is removed from the ItemList array, and all items above
>it are moved down one position (to fill the gap, and the
>count is decremented.  This causes the iterator to "skip"
>the next item.

How about using not TCollection itself but a TCollection descendant with
an additional ForEvery method?

ForEach's loop appears in essence to be
        for J := 1 to Count do action-on-element[J] ;
ForEvery's would be
        J := 1 ;
        while J<=Count do begin action-on-element[J] ; Inc(J) end ;
thus getting round the problem that action-on-element[J] may reduce
Count.  In fact, the new routine could be called ForEach, I think.

Alas, my PC assembler skills are weak.  
--
John Stockton, Surrey, UK.  J...@merlyn.demon.co.uk  Turnpike v1.12  MIME
    http://www.merlyn.demon.co.uk/

Re:Deleting item from collection


John,

Quote
> ForEach's loop appears in essence to be
>         for J := 1 to Count do action-on-element[J] ;
> ForEvery's would be
>         J := 1 ;
>         while J<=Count do begin action-on-element[J] ; Inc(J) end ;
> thus getting round the problem that action-on-element[J] may reduce
> Count.  In fact, the new routine could be called ForEach, I think.

You should start from 0 instead from 1.

--
Tom Wellige
(ITK internal: GB-PD-ISW  [PT-CAPI], -293)
well...@itk.de
http://www.kst.dit.ie/people/twellige

Re:Deleting item from collection


Dr John Stockton <j...@merlyn.demon.co.uk> wrote in article
<mQAd9GAwHHoyE...@merlyn.demon.co.uk>...

Quote
> In article <57np4h$...@news-c1.gnn.com> of Fri, 29 Nov 1996 16:51:27 in
> comp.lang.pascal.misc, "R.E.Donais" <RDon...@gnn.com> wrote:

> >Now, consider what happens when you delete an entry.  The
> >item is removed from the ItemList array, and all items above
> >it are moved down one position (to fill the gap, and the
> >count is decremented.  This causes the iterator to "skip"
> >the next item.

> How about using not TCollection itself but a TCollection descendant with
> an additional ForEvery method?
[...]
> ForEvery's would be
>         J := 1 ;
>         while J<=Count do begin action-on-element[J] ; Inc(J) end ;
> thus getting round the problem that action-on-element[J] may reduce
> Count.  In fact, the new routine could be called ForEach, I think.

This would get around the change in Count, but the problem is
bigger than that. Consider the sequence of items [1], [2], [3], ...
If the loop-counter =2 and the current item is deleted, the sequence
becomes [1], [3], ....If you now increment the loop counter from 2 to 3
then item [3] is skipped.

I believe that this is Red's point.

Chris.

Re:Deleting item from collection


In article <01bbe063$cb4e21a0$6295e...@meyerm.logica.co.uk> of Mon, 2
Dec 1996 15:18:46 in comp.lang.pascal.misc, Chris Rankin

Quote
<Rank...@Logica.com> wrote:
>Dr John Stockton <j...@merlyn.demon.co.uk> wrote in article
><mQAd9GAwHHoyE...@merlyn.demon.co.uk>...
>> In article <57np4h$...@news-c1.gnn.com> of Fri, 29 Nov 1996 16:51:27 in
>> comp.lang.pascal.misc, "R.E.Donais" <RDon...@gnn.com> wrote:

>> >Now, consider what happens when you delete an entry.  The
>> >item is removed from the ItemList array, and all items above
>> >it are moved down one position (to fill the gap, and the
>> >count is decremented.  This causes the iterator to "skip"
>> >the next item.

>> How about using not TCollection itself but a TCollection descendant with
>> an additional ForEvery method?
>[...]
>> ForEvery's would be
>>         J := 1 ;
>>         while J<=Count do begin action-on-element[J] ; Inc(J) end ;
>> thus getting round the problem that action-on-element[J] may reduce
>> Count.  In fact, the new routine could be called ForEach, I think.

>This would get around the change in Count, but the problem is
>bigger than that. Consider the sequence of items [1], [2], [3], ...
>If the loop-counter =2 and the current item is deleted, the sequence
>becomes [1], [3], ....If you now increment the loop counter from 2 to 3
>then item [3] is skipped.

>I believe that this is Red's point.

Yes, on rereading it I see that he does put it like that; he wisely
focussed on the primary error, of skipping one, whereas I had my mind
too much on the manifest symptom, of falling off the end (before
noticing the skip).

Nevertheless, it must be possible to do better than
        repeat firstthat maybe-delete until didn't-delete

How about using a TCollection descendant with an additional DeleteSome
method?

DeleteSome would be
        J := 1 ;
        while J<=Count do
             if unwanted then remove-element[J] else Inc(J);
thus getting round the problem that action-on-element[J] may reduce
Count.

In article <01bbe027$a48ef800$bd9562c1@itk_ms_wellige.itk.de> of Mon, 2
Dec 1996 08:04:52 in comp.lang.pascal.misc, Wellige <Well...@itk.de>
wrote:

Quote
>You should start from 0 instead from 1.

I'm sure you're right : my assembler skills are poor.  The elements are
numbered 0 to Count-1, and my "<=" should become "<".

My points remain :
    somebody could produce an effective method ; somebody <> me.
--
John Stockton, Surrey, UK.  J...@merlyn.demon.co.uk  Turnpike v1.12  MIME
    http://www.merlyn.demon.co.uk/

Re:Deleting item from collection


Quote
Maciej Grzyb wrote:
> I hope there is other way to delete coll item.

One solution to your problem is to loop over a copy of your collection
and delete each item that matches certain conditions from the original
collection. For example, in Smalltalk you would write something similar
to

        collection copy do: [ :each |
          each matchConditions ifTrue: [
            collection remove: each]]

However, in Turbo Vision there is no mechanism of creating shallow
copies of collections, that is copying only the collection structure and
not all of its items. But I think such a method could be added to class
TCollection.

To give you an example of what I mean, look at the following source code
parts (or maybe I should call them pseudo code parts?). Unfortunately,
at the moment I have no access to the TV library, so this code is
untested and written out of memory. Thus, please don't expect that the
code will work immediately.

Anyway, every collection holds a pointer to a dynamic array in instance
variable Items. In this array pointers to collection items are stored.
So copying a collection really means creating a new instance of the same
collection class (method createNewInstance) and set its Item pointer
(method setItems) to a copy of the original collection's Items array.

I hope this will help you at least a bit. If you have further questions,
please send me an email.

Kai

====================== source code example =========================

procedure TCollection.setItems (newItems:Pointer; newCount:Integer);
  (* should be absolutely private! *)
begin
  FreeMem(Items, Count * 4);
  Items:=newItems;
  Count:=newCount;
end;

function TCollection.createNewInstance: PCollection;
  (* should be overwritten by each TCollection descendant *)
begin
  createNewInstance:=New(PCollection, Init(Count, Delta));
end;

function TCollection.copy: PCollection;
var
  collCopy : PCollection;
  itemCopy : Pointer;
  itemSize : Word;
begin
  collCopy:=createNewInstance;
  itemSize:=SizeOf(Pointer) * Count;
  GetMem(itemSize, itemCopy);
  Move(Items^, itemCopy^, itemSize);
  collCopy.setItems(itemCopy, Count);
  copy:=collCopy;
end;

Re:Deleting item from collection


Hi All.

Quote
> > >Now, consider what happens when you delete an entry.  The
> > >item is removed from the ItemList array, and all items above
> > >it are moved down one position (to fill the gap, and the
> > >count is decremented.  This causes the iterator to "skip"
> > >the next item.

> > How about using not TCollection itself but a TCollection descendant with
> > an additional ForEvery method?
> [...]
> > ForEvery's would be
> >         J := 1 ;
> >         while J<=Count do begin action-on-element[J] ; Inc(J) end ;
> > thus getting round the problem that action-on-element[J] may reduce
> > Count.  In fact, the new routine could be called ForEach, I think.

> This would get around the change in Count, but the problem is
> bigger than that. Consider the sequence of items [1], [2], [3], ...
> If the loop-counter =2 and the current item is deleted, the sequence
> becomes [1], [3], ....If you now increment the loop counter from 2 to 3
> then item [3] is skipped.

> I believe that this is Red's point.

> Chris.

        Maybe the easiest way to do this kind of thing is to use the
following:

        scanning := True;
        While Scanning do
          begin
            Itm2Delete := FirstThat(@ShouldBeDeleted);
            If Itm2Delete <> NIL then
             Free(Itm2Delete)
            else
             Scanning := False;
          end;

        However this scans the collection many times and is inefficient.
The other thing I suggest is that it may be done in the one cycle using
loop where the loop maximum and loop counter are modified in the loop:

        LoopCounter := 0
        Repeat  
         If ShouldBeDeleted(At(LoopCounter)) then
          Free(At(LoopCounter))
         else
          Inc(LoopCounter);
        Until LoopCounter < Count - 1

    This should be at least the same thingy as the foreach loop would
be. Anyone?

        Raul Rebane.

Re:Deleting item from collection


Dr John Stockton <j...@merlyn.demon.co.uk> wrote:

Quote

Skip

>How about using not TCollection itself but a TCollection descendant with
>an additional ForEvery method?
>ForEach's loop appears in essence to be
>        for J := 1 to Count do action-on-element[J] ;

         for J := 0 to Count-1 do action-on-element[J] ;
Quote
>ForEvery's would be
>        J := 1 ;
         J := 0 ;
>        while J<=Count do begin action-on-element[J] ; Inc(J) end ;

         while J<Count do begin action-on-element[J] ; Inc(J) end ;
Quote
>thus getting round the problem that action-on-element[J] may reduce
>Count.  In fact, the new routine could be called ForEach, I think.

No, no and no.
If in the procedure action-on-element [J] is deleted item, following
for them item will not be processed all the same.
Unintelligibly, what for the assembler is necessary?
If not arranges ForEach, can be try
    for J := Count-1 downto 0 do action-on-element(J) ;

Vladimir Stepanov.

Re:Deleting item from collection


In article <581tc7$...@news.sovam.com> of Wed, 4 Dec 1996 07:49:13 in
comp.lang.pascal.misc, Vladimir Stepanov <np...@online.ru> wrote:

Quote

>If not arranges ForEach, can be try
>    for J := Count-1 downto 0 do action-on-element(J) ;

That seems a most excellent idea, and I am deeply disappointed that it
was not mine.  IMHO, it ought to be programmed in ASM, like ForEach,
and, if OK after testing, posted as a new, useful, method for use when
the action may remove the element.

--
John Stockton, Surrey, UK.  J...@merlyn.demon.co.uk  Turnpike v1.12  MIME
    http://www.merlyn.demon.co.uk/

Re:Deleting item from collection


On Wed, 4 Dec 1996 23:03:58 +0000,  Dr John Stockton

Quote
<j...@merlyn.demon.co.uk> wrote:
>In article <581tc7$...@news.sovam.com> of Wed, 4 Dec 1996 07:49:13 in
>comp.lang.pascal.misc, Vladimir Stepanov <np...@online.ru> wrote:

>>If not arranges ForEach, can be try
>>    for J := Count-1 downto 0 do action-on-element(J) ;

>That seems a most excellent idea, and I am deeply disappointed that it
>was not mine.  IMHO, it ought to be programmed in ASM, like ForEach,
>and, if OK after testing, posted as a new, useful, method for use when
>the action may remove the element.

If you are going to process the list in reverse then why not simply
use LastThat and have the action function return FALSE?  LastThat is
already coded in assembly.  

Since the iterators load the count and a "walking" pointer to the item
list into the cpu registers, LastThat is immune to changes that occur
to the current item or items that have already been processed. (Just
don't set new limits).

OTH, ForEach is sensitive to movement in the list.  But I don't think
it too difficult to have the action procedure "AtPut" a nil pointer as
a place maker and call "FreeItem" to dispose the object/record.
Invoking "Pack" immediately after ForEach compresses the list.

Anyway it's all a matter of preference. :-)

    ...red

Go to page: [1] [2]

Other Threads