Jump to content
A.M. Hoornweg

Generics: weird problem with backward running enumerator

Recommended Posts

Hello all,

 

I'm stumbling on an unexpected generics-related problem here (Delphi XE).

I'm trying to implement a backward-running enumerator for a generic tList<T>.  I believe I did everything correctly but still the enumerator runs forward unless I make a modification that really shouldn't be necessary.

 

TYPE
 tListEnumReversed<T> = CLASS(tEnumerator<T>)
  PROTECTED
    fowner: tlist<T>;
    fListIndex: integer;
    FUNCTION DoGetCurrent: T; OVERRIDE;
    FUNCTION DoMoveNext: Boolean; OVERRIDE;
  PUBLIC
    CONSTRUCTOR Create(owner: tlist<T>);
  END;
   
  tListReversed<T> = CLASS(tlist<T>)
  PROTECTED
    FUNCTION DoGetEnumerator: tEnumerator<T>; OVERRIDE;
  END;   
   

CONSTRUCTOR tListEnumReversed<T>.Create(owner: tlist<T>);
BEGIN
  fowner := owner;
  fListIndex := owner.count;
END;

FUNCTION tListEnumReversed<T>.DoGetCurrent: T;
BEGIN
  Result := fowner[fListIndex];
END;

FUNCTION tListEnumReversed<T>.DoMoveNext: Boolean;
BEGIN
  Result := fListIndex > 0;
  IF Result THEN
    Dec(fListIndex);
END;

FUNCTION tListReversed<T>.DoGetEnumerator: tEnumerator<T>;
BEGIN
  Result := tListEnumReversed<T>.Create(Self);
END;
   
   
   

 

 

This is the code I used for testing:

 

 

...
Var t:tListReversed<Integer>; 
    i:integer;
  begin
    t:=tListReversed<Integer>.Create;
	t.Add(1);	 
	t.Add(2);
	t.Add(3); 	
  	For i in T do
  	   	   memo1.lines.add(inttostr(i)) 
    t.free;   
  end;

 

 

The weird thing is, the code runs correctly if I make the following change....

 

And I have literally no idea why that is the case!  As far as I can see, the base class tEnumerable<T> already has a method GetEnumerator which should call my overridden virtual Method DoGetEnumerator. What am I missing here ???

 

 tListReversed<T> = CLASS(tlist<T>)
  PROTECTED
    FUNCTION DoGetEnumerator: tEnumerator<T>; OVERRIDE;
  PUBLIC
    FUNCTION GetEnumerator: TEnumerator<T>;
  END;
   
   
   ...
function tListReversed<T>.GetEnumerator: TEnumerator<T>;
begin
  result:=DoGetEnumerator;
end;

 

Share this post


Link to post

TList<T>.GetEnumerator does not call DoGetEnumerator but directly creates its TEnumerator - so overriding it is pointless.

 

Considering the design in TEnumerable<T>.GetEnumerator to use the virtual DoGetEnumerator I would call this a defect that TList<T> does not stick to this pattern but has its own GetEnumerator.

 

Anyhow why make a new list class just to enumerate stuff in reverse order?

Edited by Stefan Glienke
  • Like 1

Share this post


Link to post

Hi Stefan,

 

these were just my first trials with generic lists having enumerators, I'm totally unexperienced with that matter .... I have now separated the enumerator from the list by writing a generic class factory for it. No more inheritance needed. It now works like this:

 

Type

    intList=tList<integer>; 

    Reversed: ReverseList<integer>; // class factory, class function "enum" returns an interface

 

Var ints:intlist;

      i:integer;

begin

    ints:=intList.create;

    ints.add(1);

    ints.add(2);

   FOR i IN Reversed.Enum(ints)  Do 

  begin

      ...

  end;

  ints.free;

end;

 

 

The reason why I'm experimenting with backward iterators is that it is intended for a list in which elements may get deleted during the enumeration.

For .. in is simply much more legible than For .. downto IMHO and also less error-prone .

 

 

 

 

// Interface Part:

TYPE
iListEnumFactory < T >= INTERFACE
  FUNCTION GetEnumerator: TEnumerator<T>;
END;

tListEnumReversed<T> = CLASS(TEnumerator<T>)
  PROTECTED
    fowner: tlist<T>;
    fListIndex: integer;
    FUNCTION DoGetCurrent: T; OVERRIDE;
    FUNCTION DoMoveNext: Boolean; OVERRIDE;
  PUBLIC
    CONSTRUCTOR Create(owner: tlist<T>);
  END;


// also works fine for tObjectlist<T>
ReverseList <T>= CLASS(tinterfacedobject, iListEnumFactory<T>)
PROTECTED 
  fowner: tlist<T>; 
PUBLIC
  CONSTRUCTOR Create(aOwner: tlist<T>); 
  FUNCTION GetEnumerator: TEnumerator<T>; 
  CLASS FUNCTION Enum(aOwner: tlist<T>): iListEnumFactory<T>; 
END; 

IMPLEMENTATION

CONSTRUCTOR tListEnumReversed<T>.Create(owner: tlist<T>);
BEGIN
  INHERITED Create;
  fowner := owner;
  fListIndex := owner.count;
END;

FUNCTION tListEnumReversed<T>.DoGetCurrent: T;
BEGIN
  result := fowner[fListIndex];
END;

FUNCTION tListEnumReversed<T>.DoMoveNext: Boolean;
BEGIN
  result := fListIndex > 0;
  IF result THEN
    Dec(fListIndex);
END;


CONSTRUCTOR ReverseList<T>.Create(aOwner: tlist<T>);
BEGIN
  INHERITED Create;
  fowner := aOwner;
END;

CLASS FUNCTION ReverseList<T>.Enum(aOwner: tlist<T>): iListEnumFactory<T>;
BEGIN
  result := Create(aOwner);
END;

FUNCTION ReverseList<T>.GetEnumerator: TEnumerator<T>;
BEGIN
  result := tListEnumReversed<T>.Create(fowner);
END;

end.

 

Share this post


Link to post
5 minutes ago, A.M. Hoornweg said:

The reason why I'm experimenting with backward iterators is that it is intended for a list in which elements may get deleted during the enumeration.

For .. in is simply much more legible than For .. downto IMHO and also less error-prone .

That is why in my lists (inspired by the behavior of .NET) it causes an exception when the source changes during enumeration causing the enumerator to be possible invalid.

I also have a Remove method where I can pass a delegate that determines what elements to remove. IME much more robust than handwriting loops and keeping track of such things.

  • Like 1

Share this post


Link to post

I'm using this in a publisher/subscriber/event pattern.  The event, the subscriber and the publisher classes are all implemented as generics; my idea was to make the code 100% re-usable for multiple purposes.  By using generics I can "fill in the details" at implementation time.

 

Anyway; the Publisher publishes the Event to all Subscribers, but of course a subscriber may decide to unsubscribe() during this notification,  thus causing the element to be deleted from the list that was being enumerated during the Publish().   But since this is happening synchronously (single-threaded) and just for one subscriber at a time, it should be 100% safe to simply iterate the list backward and allow it to happen.  And if during the Publish() a new subscriber gets appended to the end of the list, he'll simply miss the notification, which is also perfectly correct behavior (a subscriber shouldn't receive a notification that predates his subscription).  So I think that a backward enumerator will do perfectly for my purpose.

Share this post


Link to post
1 hour ago, A.M. Hoornweg said:

Anyway; the Publisher publishes the Event to all Subscribers, but of course a subscriber may decide to unsubscribe() during this notification,  thus causing the element to be deleted from the list that was being enumerated during the Publish().   But since this is happening synchronously (single-threaded) and just for one subscriber at a time, it should be 100% safe to simply iterate the list backward and allow it to happen.  And if during the Publish() a new subscriber gets appended to the end of the list, he'll simply miss the notification, which is also perfectly correct behavior (a subscriber shouldn't receive a notification that predates his subscription).  So I think that a backward enumerator will do perfectly for my purpose.

I predict that any time in the future the publisher does not want to block until all subscribers have processed their events and thus you will need to do that asynchronously which requires a less naive approach to iterate the subscribers.

I know from my multicast events that this can cause a major headache trying to keep performance (not locking all the time) and still being able to detach subscribers in the middle of handling a publish without running into an off by one.

Share this post


Link to post

Nobody said that Subscriber.OnNotify() needs to be blocking.  In my case the subscriber base class is generic and I've implemented the asynchronicity in the derived classes.  The current subscribers simply queue the information and perform a Postmessage() for asynchronous processing in the main VCL thread. 

 

The only limitation of the publisher is that it is single threaded by design, so calls to subscribe/unsubscribe & Publish must be done in one thread.

 

 

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×