Brl.linkedlist: TLink.Remove() bypasses TList._count-cache about brl.mod HOT 5 OPEN

Maybe we could keep the "cache" by having the count cached in the "head"-TLink too?

Of course any manual adjustment to "_head" is then borking the whole thing again. Also it smells a bit "dirty/hacked".

from brl.mod.

Yeah, may as well throw away the cache and do a full count every time - if someone wants to cache it they can implement their own version.

from brl.mod.

from brl.mod.

bump.

This is still valid.
It could be circumvented if a TLink would know about the list it is stored in (so it could invalidate the _count value).
With the new GC shouldn't a "circular reference" no longer create trouble?
Also: as TLink objects are just for TList and and nothing else we should be able to "guarantee" that they are just used there (but maybe referenced multiple times). I mean: a TLink is connected to a single List and not multiple.

from brl.mod.

Was about to create a new issue when I found this.

Since TList manages the count itself at the moment ...

	bbdoc: Remove an object from a linked list
	about: Remove scans a list for the specified value and removes its link.
	End Rem
	Method Remove( value:Object )
		Local link:TLink=FindLink( value )
		If Not link Return False
		link.Remove
		If _count > -1 Then
			_count :- 1
		End If
		Return True
	End Method

... the link interface is misleading.

I found myself in a situation where I wanted to filter a list for a condition and then remove a value. This was easy by obtaining FirstLink() and then calling link.Remove().

I think this is a problem, and would like to solve this one way or another. Since TLink#Remove is public and seems useful, here's some ideas:

1. Try to make the call impossible. Add a warning to the docs like "Do not call this!" and rename Remove to _Remove and make this a more obvious programmer error.
2. Offer a better alternative. Add RemoveLink to TList so you can work with the link and don't have to first search for the link, then iterate the list again to remove the value it represents. Can work together with (1).
3. Update list counters when removing links. E.g. make links unique per list, give lists an ID, and reference the source list by ID to avoid circular references. Upon removal, trigger an Invalidate event so the list updates its counter later if necessary. (That's be a lot of overhead and quite odd.) @GWRon's suggestion aligns with this: TLink has to be unique per list.
4. Do not cache the count. The time it takes to compute the count is O(n) instead of O(1) in that case, but an extension to TList with a cache added back in is simple. In fact, we could provide both.

I would prefer to go ahead and create a PR with a combination of (1), (2), and (4). :)

from brl.mod.