Brl.linkedlist: TLink.Remove() bypasses TList._count-cache

[GWRon]

In short:

If you manipulate a TList via TLink.Remove() you bypass any adjustment to the cached _count-property.

So "list.count()" stays the same - even with entries getting removed.

SuperStrict
Framework Brl.Retro
Import Brl.LinkedList

Local entry:TList = New TList 'just an object to add
Local l:TList = New TList
For Local i:Int = 0 Until 10
    l.AddLast(entry)
Next

Print l.Count()
l.FirstLink().Remove()
Print l.Count()

For details: http://www.blitzmax.com/Community/posts.php?topic=107656#1334461

[GWRon]

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".

[woollybah]

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.

[GWRon]

Caching is always insecure if you allow an external modification.

Yes best thing is to remove it.

[GWRon]

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.

[DivineDominion]

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). :)