Feature request : tListOf (tList/Array hybrid)

BlitzMax Forums/BlitzMax Programming/Feature request : tListOf (tList/Array hybrid)

Difference

(Posted 2010) [#1]

I often end up using tList and putting only one type in it.

I'd like to benefit from the strong typecasting of arrays, but still have the easy insert and remove features of tList, therefore:

I'd like a tList type that only accepted only one userdefined type, and did automatic typecasting when using first() last(), ListToArray() etc.

Is it possible to add this feature to blitzmax?

I can't really think of a notation for such a variable type, but maybe someone knows this feature from another programming language and can suggest a syntax?

Sort of like this:

Local lo:tListOf[myType] = new tListOf

matibee

(Posted 2010) [#2]

I'm not sure how well you know C++ and the Sandard Template Library for containers like this.

Is it possible to add this feature to blitzmax?

Probably not without template support, which imho, would be a major and unlikely leap.

Brucey

(Posted 2010) [#3]

You want generics? Cool :-)

That'll keep you busy for a while I'm sure!

Difference

(Posted 2010) [#4]

After a little googling: yes I think what I'm after might be generics, but just for the tList type

http://msdn.microsoft.com/en-us/library/0zk36dx2%28v=VS.80%29.aspx shows the missing syntax I was looking for.

The c# version seems to be evaluating at runtime, I was imagining something that was resolved at compile time.

Local lo:tListOf<myType> = new tListOf<myType>

Function MyFunc:tListOf<myType>()
End Function

ziggy

(Posted 2010) [#5]

I have something similar in a BLIde template. I'll look for it later and post it. It is hardcoded, not generics, but a workaround.

Mahan

(Posted 2010) [#6]

If it's just TList you could write a utility that generates source-code for types that inherit TList and adds "type casted overrides" of the usual content accessor methods.

I've made similar things for other languages that didn't have generics, and it worked great.

edit: made it (hopefully) more understandable.

Difference

(Posted 2010) [#7]

Thanks guys, I've used the utility approach before, but I keep coming back to thinking that it would be a nice feature to have in the language.

It is of cause a "Nice To Have" rather than a "Need to Have", but I still thought I'd put it out here.

slenkar

(Posted 2010) [#8]

i use arrays but have background code that resizes the array if it is too small, - to make the array act like a list.

Jesse

(Posted 2010) [#9]

i use arrays but have background code that resizes the array if it is too small, - to make the array act like a list.

that doesn't sound too efficient.

Mahan

(Posted 2010) [#10]

@slenkar: Just as Jesse said that is inefficient, and it gets worse the bigger the arrays grow. (that is unless you use elaborate logic to optimize the growt of the arrays)

Not only does each "growt" on an array force a reallocation of the array + time to copy all the original contents: It might also lead to heavy memory fragmentation, which may lead to very strange "out of memory" errors when your application clearly does not use up all the available ram in the machine.

Note: If you're normal array sizes are low like some 10s or 100s you'll normally get away with it. But one day you use that app on a huge dataset or something and hell breaks lose =) (slower, slower, slower and finally app crash)

Kurator

(Posted 2010) [#11]

Hm, what about extending the current TList, overriding the various add methods, that the compare the actual type of the parameter with the type of the element first putted in.

Easy to implement, but the disadvantage is, that you don not have type safety at compiletime.

slenkar

(Posted 2010) [#12]

i made it so that the array grows by 50 if it is too small,
so it doesnt change size much

xlsior

(Posted 2010) [#13]

Programs like Microsoft SQL grows its transaction logs by 10% when it runs out of space -- that way you can sort of limit the number of re-allocations, because you do have some room for growth that is based on realistic usage.

If there *is* a lot of growth, simply adding 50 each time may lead to a LOT or re-allocations in memory.

Dreamora

(Posted 2010) [#14]

Normally you make arrays grow by *2 and shrink by *2.
Grow when you try to add the first element post its size. Shrink when you use less than 0.3 - 0.45 * arraySize.

That way you have near constant costs for grow / shrink and copy, making it realistically usable.
Above a given size you can make it grow / shrink differently but that "given size" should be quite large, past the 10k elements for sure.

theHand

(Posted 2010) [#15]

Peter, are you sure you're not looking for a hash table?

Difference

(Posted 2010) [#16]

@theHand : Yes , but now that you mention hash tables/maps, I'm thinking an "at compiletime typecasted" tMap would be very nice too.

MyTypeMap:tMap<myType> = Createmap(myType)

Otus	(Posted 2010) [#17]

You can Extend the TList type for automatic type checks in return types for First and the like (covariance):

Type TMyTypeList Extends TList
  Method First:TMyType()
    Return TMyType( Super.First() )
  End Method
  ' Etc.
End Type

However, you will still be without compile time type safety in Add methods, unless you actually rename the methods...

Difference

(Posted 2010) [#18]

@Otus: Yes, that seems to be the most consistent solution as the BlitzMax language is now.

It can't however be done with typecasted objects for all methods, because some methods can only be overridden with the object type:

SuperStrict

Type tMyType
	Field somevalue:Int = Rand(10000000)
End Type

Type tListOfMyType Extends TList
	Method First:tMyType()
		Return tMyType( Super.First() )
	End Method

	Method Last:tMyType()
		Return tMyType( Super.Last() )
	End Method

	Method AddFirst:TLink(value:Object)
		Assert tMyType(value) Else "tListOfMyType AddFirst() only accepts tMyType"
		Return Super.AddFirst(value) 
	End Method

	Method AddLast:TLink(value:Object)
		Assert tMyType(value) Else "tListOfMyType AddLast() only accepts tMyType"
		Return Super.AddLast(value) 
	End Method

	Method Remove(value:Object)
		Assert tMyType(value) Else "tListOfMyType Remove() only accepts tMyType"
		Super.Remove(value)
	End Method
	
	Method RemoveFirst:tMyType()
		Return tMyType(Super.RemoveFirst())
	End Method
	
	Method RemoveLast:tMyType()
		Return tMyType(Super.RemoveLast())
	End Method	
	

	
End Type




Local ml:tListOfMyType = New tListOfMyType

Local mt1:tMyType = New tMyType
Local mt2:tMyType = New tMyType


ml.addLast(mt1)
ml.addFirst(mt2)

'ml.addlast("Cheese")

Local d:tMytype = ml.RemoveLast()
Print d.somevalue


Print ml.last().somevalue
Print ml.first().somevalue

Otus	(Posted 2010) [#19]

Yeah, exactly what I meant. Argument types are contravariant, so you need to declare as Object.

It's not very pretty and causes unnecessary function calls and casts compared to writing your own list type (or generics support).

Difference

(Posted 2010) [#20]

yes, or not extending and having a list field instead, which I guess makes it cleaner:

SuperStrict

Type tMyType
	Field somevalue:Int = Rand(10000000)
End Type

Type tListOfMyType
	Field list:TList
	
	Method New()
		list = New TList
	End Method
	
	Method First:tMyType()
		Return tMyType( list.First() )
	End Method

	Method Last:tMyType()
		Return tMyType( list.Last() )
	End Method

	Method AddFirst:TLink(value:tMyType)
		Return list.AddFirst(value) 
	End Method

	Method AddLast:TLink(value:tMyType)
		Return list.AddLast(value) 
	End Method

	Method Remove(value:tMyType)
		list.Remove(value)
	End Method
	
	Method RemoveFirst:tMyType()
		Return tMyType(list.RemoveFirst())
	End Method
	
	Method RemoveLast:tMyType()
		Return tMyType(list.RemoveLast())
	End Method	
	

	
End Type




Local ml:tListOfMyType = New tListOfMyType

Local mt1:tMyType = New tMyType
Local mt2:tMyType = New tMyType


ml.addLast(mt1)
ml.addFirst(mt2)

'ml.addlast("Cheese")

Local d:tMytype = ml.RemoveLast()
Print d.somevalue


Print ml.last().somevalue
Print ml.first().somevalue

Czar Flavius

(Posted 2010) [#21]

Either make your own list (or copy and paste the TList code and change all Objects to your type), or live with the casting, as this not something to spend a long time worrying about :)