How to overload the operator Next?

[yzfwsf]

Code: Select all

Type Node
    ID As Long          
    nxt As Node Ptr
    Area As Long
    Declare Destructor()
    Declare Constructor(As Long)
    Declare Constructor(As Long, As Node Ptr)
End Type
Constructor Node(index As Long)
  Area = 0
  id = index
  nxt = 0
End Constructor
Constructor Node(index As Long, p As Node Ptr)
  Area = 0                
  id = index
  nxt = p
End Constructor
Destructor Node
  If nxt Then delete nxt
End Destructor
Dim head(324) as Node ptr
for p as Node ptr=head(0) To 0
	...
Next

I would like to ask the experts, how to overload the operator Next to achieve the functions in the above code, thank you!

[fxm]

When overloading the operator For...Next in the 'Node' type, the used iterator must be an instance of Node.
(the type must also have an implicit constructor)

Example (simplistic, just for the syntax):

Code: Select all

Type Node
    ID As Long         
    nxt As Node Ptr
    Area As Long
    Declare Destructor()
    Declare Constructor()
    Declare Constructor(Byval As Long)
    Declare Constructor(Byval As Long, Byval As Node Ptr)
    
    declare Operator For()
    declare Operator Next(byref cond as Node) as Integer
    declare Operator Step()
End Type
Constructor Node()
End Constructor
Constructor Node(Byval index As Long)
    Area = 0
    id = index
    nxt = 0
End Constructor
Constructor Node(Byval index As Long, Byval p As Node Ptr)
    Area = 0               
    id = index
    nxt = p
End Constructor
Destructor Node
    If nxt Then delete nxt
End Destructor

Operator Node.For()
End Operator
Operator Node.Next ( byref cond as Node ) as Integer
    Return This.nxt <> cond.nxt
End Operator
Operator Node.Step()
    This = *This.nxt  '' copy of the pointed instance
End Operator

Dim as Node Ptr phead1 = New Node, phead2 = New Node, phead3 = New Node, phead4 = New Node, phead = New Node
phead1->ID = 1
phead1->nxt = phead2
phead2->ID = 2
phead2->nxt = phead3
phead3->ID = 3
phead3->nxt = phead4
phead4->ID = 4
phead4->nxt = phead

for n as Node = *phead1 To Node()  '' unchain the nodes until the last
    print n.ID  '' but n is only a copy of headx
Next

Delete phead1

Sleep

You can also read the article that I wrote:
Iterators (in the Programmer's Guide / User Defined Types)

[paul doe]

Moved topic to 'General'; 'Tips and Tricks' is for completed snippets and/or techniques, not for asking questions.

[yzfwsf]

Hi fxm:
Thank you,Your code has achieved my wish, but I vaguely feel that the solution is not perfect. Does it require calling the constructor or memcpy for each iteration?
C++ for loop can be like the following, I wonder if FB can be realized?

Code: Select all

for (Node* p = head_s[now]; p; p = p->next)

[fxm]

for n as Node = ...
'For' implicitly constructs a local 'n' instance of Node, and assigns it ...

Other syntax:
dim n As Node
for n = ...
'For' only assigns the 'n' instance of Node ...

For both syntaxes, a same single iterator (an instance of Node) is used to copy at each iteration the different nodes.

[coderJeff]

C++ for loop can be like the following, I wonder if FB can be realized?

Code: Select all

for (Node* p = head_s[now]; p; p = p->next)

If you want to use pointers and type members directly:

Code: Select all

	var p = head_s[now]
	while( p )
		'' some code that uses p->members
		p = p->next
	wend

[yzfwsf]

I don’t know if my understanding is correct? C++ only needs to modify the pointer for each iteration, while FB needs to copy the Node instance every time.

[yzfwsf]

C++ for loop can be like the following, I wonder if FB can be realized?

Code: Select all

for (Node* p = head_s[now]; p; p = p->next)

If you want to use pointers and type members directly:

Code: Select all

	var p = head_s[now]
	while( p )
		'' some code that uses p->members
		p = p->next
	wend

Thank you,This is what I do now.

[coderJeff]

Here's a more complex example that uses an iterator type with pointers only so there's no extra copies of objects made. Which might be desirable if the objects are large. Obviously still have the overhead of calling the for/next/step overloads. For fun I used an overloaded -> operator to access the node from an instance of the iterator.

This should work on any fbc 1.00.0 or later:

Code: Select all

#ifndef NULL
	const NULL = cast( any ptr, 0 )
#endif

type node
	id as long
	nxt as node ptr
	area as long
	declare constructor( byval index as long, byval stk as node ptr = NULL )
	declare destructor( )
end type

constructor node( byval index As long, byval stk as node ptr = NULL )
	id = index
	nxt = stk
	area = 0
end constructor

destructor node
	'' delete all linked nodes (rescursive)
	'' FYI, be careful, double free on lists with common tails
	'' there's no protection against that here'
	if nxt then delete nxt
end destructor

type nodeIterator
	item as node ptr
	public:
		declare constructor( byval start as node ptr )
		declare operator for( )
		declare operator step( )
		declare operator next( byref cond as nodeIterator ) as integer
end type

declare operator ->( byref iterator as nodeIterator ) byref as node

constructor nodeIterator( byval start as node ptr )
	item = start
end constructor

operator nodeIterator.for( )
end operator

operator nodeIterator.step( )
	item = item->nxt 
end operator

operator nodeIterator.next( byref cond as nodeIterator ) as integer
	if( cond.item ) then
		return( item <> cond.item->nxt )
	end if
	'' cond is NULL, assume going to the end of the list
	return( item <> NULL )
end operator

operator ->( byref iterator as nodeIterator ) byref as node
	return *(iterator.item)
end operator

'' build a list
var head = new node( 1 )
head = new node( 2, head )
head = new node( 3, head )
head = new node( 4, head )

print "head to last"
for item as nodeIterator = head to NULL
   print item->id
next

print "head to head->nxt->nxt"
for item as nodeIterator = head to head->nxt->nxt
	print item->id
next

print "head->nxt to head->nxt->nxt"
for item as nodeIterator = head->nxt to head->nxt->nxt
	print item->id
next

delete head

[coderJeff]

I don’t know if my understanding is correct? C++ only needs to modify the pointer for each iteration, while FB needs to copy the Node instance every time.

FOR/NEXT in fbc is not as generic as C/C++ statement for( init-statement; conditions; loop-statements ), which is fancy wrapper for a while() loop.

There needs to be an instance of some kind of data type to be the iterator. If the NODE type overloads FOR/NEXT, then the iterator must be an instance of NODE type - which means copying / destructing an instance of NODE on each iteration.

fbc FOR/NEXT statements and therefore FOR/NEXT overloads for TYPESs work best with data types that have a value that can be compared with each other to know if it is higher or lower.

It is trickier for something like a singly-linked list. At some point the iterator in the FOR/NEXT loop has to be incremented to something that is larger or past the highest iteration value possible. In the case of a linked list it would be NULL or some kind of sentinel instance.

The only way I can think of to avoid an extra instance of NODE when used in a FOR/NEXT overload is to work with an instance of NODEITERATOR which could be a simple pointer to the NODE instance. And I've given an example in my last post.

[yzfwsf]

I don’t know if my understanding is correct? C++ only needs to modify the pointer for each iteration, while FB needs to copy the Node instance every time.

FOR/NEXT in fbc is not as generic as C/C++ statement for( init-statement; conditions; loop-statements ), which is fancy wrapper for a while() loop.

There needs to be an instance of some kind of data type to be the iterator. If the NODE type overloads FOR/NEXT, then the iterator must be an instance of NODE type - which means copying / destructing an instance of NODE on each iteration.

fbc FOR/NEXT statements and therefore FOR/NEXT overloads for TYPESs work best with data types that have a value that can be compared with each other to know if it is higher or lower.

It is trickier for something like a singly-linked list. At some point the iterator in the FOR/NEXT loop has to be incremented to something that is larger or past the highest iteration value possible. In the case of a linked list it would be NULL or some kind of sentinel instance.

The only way I can think of to avoid an extra instance of NODE when used in a FOR/NEXT overload is to work with an instance of NODEITERATOR which could be a simple pointer to the NODE instance. And I've given an example in my last post.

Thank you for learning new knowledge. It seems that I still use while...Loop at this stage, which is better, simple and efficient.

[fxm]

We always try to answer the question posed anyway before proposing an alternative.