Nested Types / Parented Types / Whatever

Blitz3D Forums/Blitz3D Programming/Nested Types / Parented Types / Whatever

Adam Novagen(Posted 2011) [#1]
Dunno what to call 'em. xD

Anyway, I recently found that it's possible to "nest" Types, that is, make a Type field actually BE another Type. e.g.:

Type Parent
    Field Name$
    Field Kid.Child
End Type

Type Child
    Field ParentName$
End Type


This would be followed later in the code by something like:

Thing.Parent = New Parent
    Thing\Name = "Derp"
    Thing\Kid.Child = New Child
        Thing\Kid\ParentName = "Derp"


The main use for this, THEORETICALLY, is that it allows you to create a LIST of fields within a Type, without it having to be a preset number. Say, for example, that you wanted to make a bunch of planets, so you make a Type for them. Then, each planet can have moons, but you don't know how many. You could do something like:

Type Planet
    Field Moons[100]
End Type

Trouble is, what if you wanted MORE than 100 moons? Also, if you have LESS than 100 moons, you'll have to have some sort of marker - probably 0 - to designate which elements of Moons[x] do NOT contain entities.

With nested Types, you should THEORETICALLY be able to make this nice and simple. You create a Type-in-a-field for each moon, for each planet. Like this:

Type Planet
    Field NumOfMoons
    Field Moon.Moon
End Type

Type Moon
    ;etc
End Type

;Planet creation here

For Planet.Planet = Each Planet
    For i = 1 To Planet\NumOfMoons
        Planet\Moon.Moon = New Moon
    Next
Next

Nice and neat. You SHOULD now be able to loop through the planets, and for each planet, loop through its moons and ONLY its moons, like this:

For Planet.Planet = Each Planet
    For Planet\Moon.Moon = Each Moon
        ;Do stuff
    Next
Next

Trouble is, it apparently doesn't work this way. Have a look at the following working experiment (no media needed):



Now, as we discussed before, this SHOULD work. The program loops through all the Parent Types, then for each one, it loops through its Child Types. UNFORTUNATELY, the results in the program clearly show that instead, the loop counts through ALL the Child Types EVERY TIME. To fix, I put in a little If statement, shown here:

    ;COUNT THE NUMBER OF CHILDREN FOR EACH TYPE
    For Thing\Kid.Child = Each Child
        If Thing\Kid\ParentName = Thing\Name
            Children = Children + 1
        EndIf
    Next

Run the example with THIS in there, and the child count comes out correct. However, this completely defeats the purpose of nested Types, since the exact same method could be using ORDINARY Types. This isn't a problem per se, but it means that for EACH of the parent Types, ALL the child Types will be looped through, even though only a few of them belong to each individual parent.

Am I missing something blatantly obvious here, or is this "nesting" method literally just a way of making code a little more "readable?"

Last edited 2011

Last edited 2011


Warner(Posted 2011) [#2]
You could use nested lists of user type instances. However, in that case, you should not rely on the default For..Each, First/Last/Before/After operators in Blitz3D.
You could create your own linked list instead. This is more flexible.

The idea is this: each Type instance holds a Field that points to another Type instance. Using this system, the Type instances form a chain. The last one in the chain points to "Null":
Object1 -> points to -> Object 2 -> points to -> Object 3 -> points to -> Null
Objects are linked to each other (points to->link) and form a list (chain->list). Hence linked list

If you want to delete one of these objects from this list, you should make Object 1 point to Object 3. Object 2 is then no longer part of the chain.
(Note: in Blitz3D you might want to Delete the object as well)

Beside the internal links, you need to store which object is the first one in the list.
If you want to iterate through the list, you start off with this first object (Object 1), and then follow it's link to the next object. (Object 2) Then follow the link to the next object. (Object 3) Repeat this until the next object is Null.

Here is an example using planets and moons:


Last edited 2011


Yasha(Posted 2011) [#3]
Am I missing something blatantly obvious here


I hate to be so blunt, but... yes. I don't think you've correctly understood the B3D type system.

First things first: let's clear up some terminology, so that there's no confusion. The Blitz3D manual gets a lot of the terms wrong, which makes Types a difficult topic to discuss clearly.

- A variable: a name in the program that can hold a value. You know these from ints and floats.

- A type: a property of a variable that determines what data it can hold. There are four main types in Blitz3D: ints, floats, strings (you know these three), and pointers. A type can also be a property of an object, describing its memory structure. These are separate concepts, but they map 1:1 in Blitz3D so let's say that they're one thing: type forms an exclusive link between a memory structure and a variable that can hold it or a reference to it.

In either case, the concept is purely abstract and doesn't exist in any form at runtime. There is no way to "nest" types (notice above how you defined "Child" below "Parent", not within the same block).

- An object is a block of memory. You create a new object with New and free it with Delete. Entities and images and whatnot are also objects, but they don't have any role in the B3D type system (but they're useful to keep in mind as they can help you understand by-reference semantics).

- An instance of a type is an object whose memory structure matches that type's pattern description, and was created with the New operator for that type. The main distinction between the terms "object" and "instance" is that "instance" is used to refer to an "object" of one specific type. (Note that the machine doesn't actually know this at runtime - this doesn't matter to us though).

- A field is exactly the same thing as a variable; it happens to name a location inside a dynamically allocated object, instead of part of a function's frame or the main program's frame. So you have to "qualify" the location within that object: this is what the instance\field syntax means. Fields can also be called member variables.

- A pointer is what a variable stores to act as a reference to an object. Entity "handles" are pointers, converted to integer form to store in int variables; you will remember that when you assign one image or entity handle to another variable, it doesn't copy that image or entity; it just means two variables are referencing it. Instances of B3D custom types work the same way, except they can't interchange freely with integers they way "handles" can. Functionally, and at runtime, they are however exactly the same thing.

OK, that down:

When you store a "type in a type" as so many people on here erroneously call it, what you've done is declare a member variable within that type's structure. That member variable can hold an instance of whatever type you declared it with, exactly the same way as a variable outside can. This means that the value of that field will start as Null, and isn't constrained in any way by the rest of the type structure. Therefore, it can hold any instance of the right type. It's just a four-byte slot, same as an int variable, at runtime; assigning an instance to it is no different than assigning an entity to an integer field.

When you instantiate a type with New <typename>, it is added to a hidden "global list" of objects of that type. (This is... frankly an odd choice on the part of Mark, and isn't normal for most programming languages.) Elements of that list are controlled with the After, Before, First, Insert, and Last operators. When you use For/Each, you're iterating over the whole of that list, again without any kind of qualification or control based on where you're calling For/Each from. There is exactly one list per type, and all instances of the type go on that list, and you cannot create any other lists that work with For/Each.

So, to finally explain what's going on above: When you nest the two For/Each loops, the inner loop isn't controlled by the outer loop, as it describes something that the compiler doesn't know you want to be conceptually linked. Instead it loops over all the Moons, regardless of planet (You're also using Planet\Moon as an iterator, which means the value stored in that field is actually changing with each iteration of the loop - this is definitely not what you want to do!).

There are a few ways to do what you want, but the best is probably not to work with For/Each at all and instead control your loop manually. You could arrange the Moons in linear groups (you'd have to either create them in blocks for each planet, or rearrange them with Insert), and store in Planet the first Moon and the number of Moons; then you could set the iterator variable to that stored first Moon and use a For/Next loop over the number of Moons, manually incrementing the Moon variable with After.

Or you could avoid use of the global list altogether, and add a "nextMoon.Moon" field to the end of the Moon type; point this to the next Moon in the list and at the end of the loop, read the next Moon from that. When you encounter a Moon where m\nextMoon = Null, then you're done with that Planet. (EDIT: This is the "linked list" Warner describes above.)

...this was long and repetitive, but I hope it helps.

Last edited 2011


Charrua(Posted 2011) [#4]
you are right

there is a "Collection Lib" (made by Mahan) to handle multiple lists of same Type individually: There is an example of usage by me:
http://blitzbasic.com/Community/posts.php?topic=86730#983964
the lib is free

(sorry for my english, hope didn't use wrong terminollogy)

Juan

Last edited 2011

Last edited 2011


Adam Novagen(Posted 2011) [#5]
You could create your own linked list instead. This is more flexible.

Hmm... Looks interesting, though a bit overly complicated for what I need at the moment. I'll keep it in mind though, might need that in future.

I hate to be so blunt, but... yes.

Blunt is good, I like blunt. The sooner the point is delivered, the better; much appreciated.

So, Yasha, that information was enormously helpful. If I understand correctly, everything variable in Blitz - short of the actual data in banks and media resources - is pretty much the exact same data, just with different cosmetics applied pre-compiler to allow the programmer to handle the data in the most Humanly manageable way. Alright then, good to know; with that in mind, I have the exact method to deal with this little hiccup. Thanks again!


Rroff(Posted 2011) [#6]
Nest child groups of types is really really easy to do.

You simply make some objects in the type collection "dummy" objects that denote the demarcation point between groups of objects and then do something like:

Type uiWindow
	Field buttons.uiButton
End Type

Type uiButton
	Field bookmark
	Field uiParent
End Type

; create a new UI window

this.uiWindow = New uiWindow




; add a "pointer" into the button collection for child grouping

this\buttons = New uiButton
this\buttons\bookmark = True ; mark this as a "dummy" demarcation object
this\buttons\uiParent = Handle(this) ; 2 way link
Insert this\buttons Before First uiButton ; start a new group of button objects



; add a new button to this window

mybutton.uiButton = New uiButton
mybutton\bookmark = False ; its an actual button
mybutton\uiParent = Handle(this)
Insert mybutton After this\buttons ; place it after our demarcation object



; now delete all buttons on this window as an example of useage

Local button.uibutton
Local tempbutton.uibutton

button.uiButton = After this\buttons

While (button <> Null) ; while we have valid button objects - if we hit another bookmark abort

	If (button\bookmark = True) Then
		Exit
	EndIf

	tempbutton = button
	button = After button
	
	Delete tempbutton

Wend



This is also really really fast compared to comparing against the parent object in B3D to check what group an object belongs to, you can have 10,000s of type objects and walk a child group belonging to a parent object within that type collection in no time at all without having to even touch the rest of the objects in that collection. Also doesnt' have the issues where child objects point to other child objects within a group in a chain which is really easy to break if you don't re-attach the chain on deleting a child object.




you can also add a 2nd entry point something like this:

Type uiWindow
	Field buttons.uiButton
	Field buttonsEnd.uiButton
End Type


and insert the buttonsEnd object after the buttons object as a bookmark so you can walk the child collection backwards.

Last edited 2011

Last edited 2011


_PJ_(Posted 2011) [#7]
Hey Adam!
What you have got there shows the important ifferences between arrays and types in blitz.
Arrays are good for when you have a limited and known limit to the members of a set, whereas types allow for (memory allowing) unlimited members to be created.
There are advantages and disadvantages to both, and using one or the other should be dependant on the circumstance and desired result.

It's possible to combine types and arrays too, making complex, but ordered data collection feasible, though the more complex, the harder it becomes to see what's going on ;)

When you have a situation such as:
Global Moon[100]

Type Planets
Field PlanetName$ 
Field Moon[100]
End Type

Type Moons
 Field MoonName$
End Type

MyPlanet.planets=New Planets
 MyPlanet\PlanetName$="Earth"
 MyMoon.moons=New moons
 MyMoon\MoonName$="Luna"
 MyPlanet\Moon[0]=Handle(MyMoon)




 MoonHandle=MyPlanet\Moon[0]
 ThisMoon.Moons=Object.Moons(MoonHandle)
 
 Print Moon[0]
 Print ThisMoon\MoonName


Firstly, note that the global array Moon[100] alone plays NO PART in the data structure. The duplicated name as a Field of the Type Planets also called Moon[] is specific to that Type and, once MyPlanet is creaated, MyPlanet\Moon[] is specific ONLY to the MyPlanet instance.
There is no conflict or relationships between the Moon[] field(s) of any instance of Planets and the Moon[] array declared at the top!

Later it is necessary to create the 'space' for the instance ThisMoon.Moons* as the compiler cannot work with Object.CustomType(Instance.CustomType) inline:

[Code]
Object.Moons(MyPlanet\Moon[0])[/code]
or even more extrapolated:
Object.Moons(MyPlanet\Moon[0])\MoonName$

Just wont work.

So
MoonHandle=MyPlanet\Moon[0]
 ThisMoon.Moons=Object.Moons(MoonHandle)

Is used to reference the required instance in order to pick out
ThisMoon\MoonName$ for printing.

Since there IS an upper limit (so far, no planet has 100 moons or more), it is sensical to use an array for each moon of a planet, ensuring there is a separate array for each planet, and that there is no danger of accidentally obtaining "Ganymede" as a result for Earth's moon etc. The array could instead just be a string, but with the handle to the Moons type, we have the ability to provide more Fields containing more information relevant to each individual moon.
With this in mind, too, cases where there are no moons, or fewer than 101 moons(!), invalid or null entries for the object Handles in Planet\Moons[] will be 0, clearly distinguising them from values where there are

This whole approach collects the Moon information for a planet together with its parent, The Moon data for a Planet is accessed VIA THE PLANET INSTANCE. However, it's a little "awkward"

Alternatively, since the NUMBER OF MOONS PER PLANET varies so greatly from each planet to the next, directly 'linking' the types of Planets and theior satellites might be better suited for this excercise. There can be no issues with Null instances here, aside from the default where instances have not been created or the end of a list (during iteraation etc) has been reached.
It is important, however, to ensure that the correct Moons are linked to their correct parent, this can be achieved by a Type Field for the Moons instance containing the Handle of its parent object, or the actual Type Object instance object. THIS WAY, IT I IMPOSSIBLE TO ACCESS A MOON OF A PLANET DIRECTLY FROM THE PLANET! The parent of a Moon must be verified from the Moon's information.

The advantage of using Handles allow for ease of use, since a handle is an integer, whereas the Type Object Instances are more specific. The specification of Type Objects instances DO help[ prevent any incorrect usage, though and can help with understanding/readability of the code and its purpose.

EXAMPLE USING HANDLES:


SIMILAR EXAMPLE USING OBJECT INSTANCES:




*(Admittedly, since it's still wthin scope, MyMoon.Moons would work here, but assuming you'd want to reference the type instance from elsewhere, you can't rely on the re-use of previous instance names!)
________________________________________________________



Personally, I have gotten into the habit of including things such as a SelfHandle Field for Type instances, containing the Handle(Instance.Type) value. It may be overkill in some cases, but it's nevertheless helpful.


Rroff(Posted 2011) [#8]
Arrays are potentially costly in terms of cleaning up and house keeping - more complex to handle within B3D, whereas the method I used in the example above makes use of the native C++ functionality B3D was developed with so is mostly very fast.


The nice thing about the method I use as well... in conjunction with fastpointer and some advanced coding you can implement full polymorphic OOP with only a minor performance loss in B3D.

Last edited 2011


_PJ_(Posted 2011) [#9]
Yeah, that's a very good point. The ability to construct/deconstruct (i.e. Instantise and Delete) Types makes them nice ly efficent, whereas I understand, "empty" arrays still require the memory space to store the '0' ?


Adam Novagen(Posted 2011) [#10]
Yeah, I believe that an array always takes up a certain amount of data depending on its elements, whether it contains any data or not.

Malice, that parenting example is... A little convoluted for my brain that only got out of bed about twenty minutes ago, BUT I see how it works, and it's great. Funnily enough it's an amazingly similar principle to what I was doing using strings instead; the parent Type had a \Name$ field, and the "child" Type had a \ParentName$ field; I would then loop through the child Types, working on only the ones whose \ParentName matched the \Name of the active parent. A little clunky by comparison, and I realize strings are most likely much slower than direct-object-referencing, but for my present purposes it works because I never have to loop though more than about 100~200 possible parents and children TOTAL, and there's only ever one active "parent" at a time.

I'll keep a note of that object method though, as it may become useful should I need more elaborate nesting in the future.

Last edited 2011


Charrua(Posted 2011) [#11]
asuming that each element of a type is in a Global collection handled by blitz, and, that they are stored in the order in wich we crete them. I use to store the handle of the first item in a particular sub group of objects, and then use AFTER to get the next until the end of the subgroup.
In this way i only scans a portion of the entire Blitz collection.
(using For each blitz start from the first until it reaches the las one)

an example:


Type tRoom
	Field Id
	Field Name$
	Field FirstChair
End Type

Type tChair
	Field Id
	Field Name$
	Field RoomId
End Type


Local Room1.tRoom
Local Room2.tRoom
Local Room3.tRoom

Room1 = CreateRoom("Main",3)
Room2 = CreateRoom("Teachers",5)
Room3 = CreateRoom("Students",9)

DumpRoom(Room2)
DumpRoom(Room1)
DumpRoom(Room3)

WaitKey
End


Function CreateRoom.tRoom(name$,nChairs)
	Local room.tRoom = New tRoom
	room\id = Handle(room)	;just an Id, but BTW it's handle
	room\name = name
	For i=1 To nChairs
	
		chair.tChair = New tChair
		
		If i=1 Then room\FirstChair = Handle(Chair)
		
		chair\RoomId = room\Id	;any Chari has the handle of it's father and so the room is easily accecible:
								;via:  room.tRoom = Object.tRoom(Chair\RoomId)
								
		chair\name = room\name+" chair:"+Str(i)
		
	Next
	Return room
End Function

Function DumpRoom(room.tRoom)
	Print Room\name
	chair.tChair = Object.tChair(room\FirstChair)	;get the first in the Room's collection
	While chair\RoomId = room\id
		Print chair\name
		Chair = After Chair			;get next
		If chair=Null Then Exit		;check if it's the last one in the Blitz collection
	Wend
End Function


Juan

Last edited 2011


Rroff(Posted 2011) [#12]
My method means you don't have to loop through 100s of child objects.

For working with a lot of strings I use these functions - its not a true hash exactly but easier to call it that - you have to precompute the "hash" when you name an object and then its a lot faster to do integer to integer comparisons until you get something thats close to matching and then use string checking to get an exact match.

Obviously doesn't work so well if all your strings have very similiar names.



So you'd do something like:

this.type = new type
this\name$="blah"
this\hash = fasthash(this\name$)

then in your loop you'd calculate the "hash" for the string you wanted to compare and use fastcmp to check them - if your only checking 2-3 strings then its slower - but not by any amount that matters - if your checking against say 200 strings then its ~40x faster.

EDIT: And not to sound like a petulant child... but can people please look at the sample I posted earlier (post #6) on how to do nested types as people keep posting hideously inefficent (relatively speaking) alternative methods.

Last edited 2011


Charrua(Posted 2011) [#13]
hmmm
interesting
at first i saw no real difference with your #6, but then i realize that using the dummy object (wich you has a reference to it) and being useless for data storing, is almost imposible that you Delete this element. In my implementation, i store the handle to the first, but, if this first element get deleted : the Loop will fail just because i can't get the first element.
is there any advantage in using a type field instead of an integer that holds the handle?,
say, has your system a downgrade if you Declare Buttons in uiWindows as an integer (to store the handle of the dummy button) instead of as a uiButton?

Juan

Last edited 2011

Last edited 2011


Rroff(Posted 2011) [#14]
Your system is very similiar but mine takes the idea a bit further and works without having to sanity check stuff every time you delete or manipulate children.

You can use either integer handle or type fields both work fine, just one or other may be more useful for your needs - directly pointing to a type object has slightly lower overheads performance wise but fairly insignificant for most projects.

Last edited 2011


Matty(Posted 2011) [#15]
Personally I prefer to use banks over arrays, I can resize them without losing the data already stored, I can store a handle for a bank in a field of a type and then iterate through that bank, I can create my own data structures unlike an array where the datatype is fixed, and I can return multiple values from a function by returning a bank containing each value in a format I decide upon as long as I remember to free it after use.

Types in combination with banks are great..in my opinion. Arrays have their uses (they're much simpler to manage) but banks are more flexible. Banks require a bit more programming effort than an array but are worth it.