NewsForumsCodeLogsGallerySpecsSearch

Container Class Primer

Blitz3D Forums/Blitz3D Tutorials/Container Class Primer

octothorpe(Posted 2005) [#1]
What?

Container classes hold collections of object pointers. They are an alternative to typed arrays (e.g. Dim monster_list.monster(5) or Field monster_list.monster[5]) and the builtin linked-lists of objects (e.g. For m.monster=Each monster). Unlike builtin lists, you can have multiple collections per type and put only the objects you want in each. Unlike typed basic arrays (Dim m.m(x)) containers do not have to be global, and can be passed to functions. Unlike typed field arrays (Field m.m[x]) containers are not limited to a static number of elements.

Container classes also provide encapsulation: the logic of how containers work is separated from your code. Using containers properly can greatly simplify your code.

Using container classes to store objects involves using Handle() and Object(), since the container classes only store integers. It's quite easy to do this.

Each container class has advantages and disavantages, primarily in indexing, but also in performance:

Container: double-linked list
(In C++, this is called a list.)
- an ordered list, unindexed
- quick to add or remove elements from the front, back, or anywhere in the middle
- slow to find an element based on its numerical position in the list (i.e. find the Nth element)
- can also be used as a FILO queue or a FIFO stack

Container: hash table
(In C++, this is called a hash_map.)
- also known as a "dictionary" or "map"
- an unordered look-up table, indexed by strings
- quick to add, remove, and retrieve entries
- can replace an enum (a list of Consts) as a slower but more programmer-friendly solution
- unordered!

Container: vector
(In C++, this is called a vector. Note that this has nothing to do with spatial vectors - Vector Containers are similar to arrays.)
- an ordered list, indexed by position
- quick to find an element based on its numerical position in the list (i.e. find the Nth element)
- quick to add or remove elements from the back
- slow to add or remove elements from the front or middle
- slow to add lots of elements without knowing how many beforehand
- can also be used as a FIFO stack

There's no limit to the number of elements any container of any class can store - there are no Consts to change when you need to create more objects. In fact, you shouldn't need to even look at the code, but if you do, I've kept it nice and tidy. :)

A pitfall to keep in mind when using containers is that - when you delete an object - you have to remember to remove container elements that point to that object. If you don't, the abandoned elements will result in Null when you call Object() on them. Sometimes, cleaning up properly can involve adding field(s) to your type to keep track of the element(s) which will need to be removed later.

These container classes are heavily based on the C++ STL container classes.


Why?

- keeps your code clean and readable
- enables you to code faster
- avoid the drawbacks of typed arrays or builtin lists

Here are some examples of scenarios in which containers really shine:

1. You have a bunch of room objects and wall_socket objects. wall_sockets are only found in rooms. If you want to be able to loop over all the wall_sockets
for a room without looping over all the wall_sockets everywhere, you could use a list or vector container as a field in your room type.

2. Keeping track globally of all the "damaged" wall_sockets in all the rooms could be accomplished with a list container, this time a global one. When you want to loop through the damaged wall_sockets, you won't have to loop through all the wall_sockets.

3. Let's say you have animation information for different poses described in a file and have created a type to store the data for each one. If you use a hash container to store the poses by their names, you can later refer to the objects by name. Adding new poses to your file won't require any code changes for you to use them.


How?

First, make sure you're familiar with Object() and Handle().

Here's a sample type we'll be playing with:
	type foo
		field value$
	end type

Instead of calling New and Delete directly, we'll use constructor and destructor functions. Right now, they serve no real purpose. Later, if we need to do something special to initialize or clean up after our objects, we won't need to hunt around in our code to make sure those tasks are done every time objects are created or destroyed, we can simply add that functionality to the constructor and destructor functions. It also keeps the examples a little more concise.
	function foo_new.foo(value$)
		f.foo = new foo
		f\value$ = value$
		return f
	end function
	
	function foo_destroy(f.foo)
		delete f
	end function

I. Lists

Let's examine List Containers first. A list is an ordered container which provides many ways to insert and remove elements. It's probably also the most used and useful of the containers.

Creating a new list container is done by calling list_new():
	include "listC.bb"
	
	foo_list.listC = list_new()

"push" adds integers to the end of the list. Instead of an integer, we want to add pointers to objects. To do so, simply specify the object's Handle() for a value:
	x.foo = foo_new("cheese")
	list_push(foo_list, handle(x))
	y.foo = foo_new("danish")
	list_push(foo_list, handle(y))

To retrieve (and remove) elements from the back of the list, we call list_pop(). Since we want to retrieve a pointer to our object, we call Object() on the value returned:
	f.foo = object.foo(list_pop(foo_list))
	print f\value$
	f.foo = object.foo(list_pop(foo_list))
	print f\value$

The list is now empty and we've printed "danish" then "cheese". Note that this is because "push" and "pop" both work with the back of a list. "shift" and "unshift" work with the front of a list.

To clean up, let's delete our objects:
	foo_destroy(x)
	foo_destroy(y)

And the list:
	list_destroy(foo_list)


II. Iterating

When you need to walk through all the elements in a container, you use an iterator. The bad news is that using iterators is quite wordy - three lines just for the equivilent of a For..Each! The good news is that you can copy and paste the same lines whenever you need to use an iterator - you just need to change the type (foo), container name (sample_list), and variable name (item):
	; for item.foo = each sample_list
	it.listC_iter = list_iterator_begin( sample_list )
	while list_iterator_next(it)
		item.foo = object.foo(list_iterator_get(it))
	
		; code here
	wend

While iterating, it's safe to remove the current element. Let's remove probably my favourite animal from the list:
	; for item.foo = each sample_list
	it.listC_iter = list_iterator_begin( sample_list )
	while list_iterator_next(it)
		item.foo = object.foo(list_iterator_get(it))
	
		if item\value$ = "liger" then list_remove_node(it\current_node)
	wend

Note that it's not safe to remove the element after the current element! For this reason, you should probably never remove any elements other than the current element.


III. List Nodes

A list is comprised of a collection of nodes. When you add an element to a list, the node that was created is returned. Nodes are used when you want to remove a specific element. They're also used to specify a position in the list when you want to add a new element via list_insert_after() or list_insert_before().
	fixins.listC = list_new()
	n1.listC_node = list_push(fixins, handle(foo_new("ketchup")))
	n2.listC_node = list_push(fixins, handle(foo_new("mayo")))

We've created a new list and added two objects to it. We've stored the nodes for these objects in the variables n1 and n2.
	n3.listC_node = list_insert_after(n1, handle(foo_new("relish")))

By referencing ketchup's node, we were able to add relish after it (and before mayo.)

list_remove_node() returns the value of the node it removes. Let's use it to remove the mayo fixin from the list, and ultimately delete the mayo object.
	mayo.foo = object( list_remove_node(n2) )
	print mayo\value
	foo_destroy(mayo)


IV. Subscribing to Lists

For many uses of lists, list nodes are not required. If your list "owns" the objects it contains, and those objects will be destroyed when and only when the elements are removed from the list, there's no need to keep track of list nodes.

If your objects will be destroyed some other way, or belong to multiple lists, it becomes important to clean up elements which point to objects being destroyed. The cleanest solution is to keep track of the nodes you add. Add a listC_node Field to your type for each list your object might belong to, then in the destructor call list_remove_node() on each field.
	global favourite_foos.listC = list_new()


	type foo
		field value$
		field favourite_node.listC_node ; our entry in favourite_foos
	end type

	function foo_destroy(f.foo)
		foo_unsubscribe_from_favourites(f)
		delete f
	end function

	function foo_subscribe_to_favourites(f.foo)
		if f\favourite_node <> null then return ; we're already subscribed!
		f\favourite_node = list_push(favourite_foos, handle(f))
	end function

	function foo_unsubscribe_from_favourites(f.foo)
		if f\favourite_node = null then return ; we're not subscribed!
		list_remove_node(f\favourite_node)
		f\favourite_node = null
	end function


V. Lists Continued

To see all the operations you can perform on lists, see the code archive page for Container: double-linked list.


VI. Hash Tables

Hashes are very easy to use. The two most important functions are hash_set() and hash_get().
	include "hashC.bb"

	fruit_hash.hashC = hash_new()

	hash_set(fruit_hash, "apple",  handle(foo_new("the fleshy usually rounded and red, yellow, or green edible pome fruit of a tree")))
	hash_set(fruit_hash, "orange", handle(foo_new("a globose berry with a yellowish to reddish orange rind and a sweet edible pulp")))

	picked_fruit.foo = object( hash_get(fruit_hash, "orange") )
	print picked_fruit\value

Hash iteration is similar to list iteration, except that you also get the key$.
	it.hashC_iter = hash_iterator_begin(fruit_hash)
	while hash_iterator_next(it)
		key$ = hash_iterator_get_key$(it)
		fruit.foo = object.foo( hash_iterator_get_value(it) )

		print key$ + " => " + fruit\value
	wend

Removing elements from a hash is done via key$. There's no need to store nodes.
	hash_delete(fruit_hash, "apple")

The hash destroy function, like the list destroy function, will clean up all the elements remaining in the container, but will not delete the objects those elements point to.
	hash_destroy(fruit_hash)

To see all the operations you can perform on hashes, see the code archive page for Container: hash table.


VII. Vectors

It's helpful to think of Vector Containers as arrays. They can be used as arrays:
	ordinal_names.vectorC = vector_new(10)
	
	vector_set(ordinal_names, 0, handle( foo_new("first") ))
	vector_set(ordinal_names, 1, handle( foo_new("second") ))
	vector_set(ordinal_names, 2, handle( foo_new("third") ))
	
	vector_resize(ordinal_names, 100)

	vector_destroy(ordinal_names)

Vector iteration is similar to list iteration.
	; for item.foo = each sample_vector
	it.vectorC_iter = vector_iterator_begin(sample_vector)
	while vector_iterator_next(it)
		item.foo = object.foo(vector_iterator_get(it))
	wend

Or, if you prefer the concise approach:
	for i = 0 to vector_count(sample_vector)-1
		item.foo = object.foo(vector_get(sample_vector, i))
	wend

Vectors can also be used as a stack, with push and pop:
	todo.vectorC = vector_new()
	
	vector_push(todo, handle( foo_new("do laundry") ))
	vector_push(todo, handle( foo_new("make dinner") ))
	vector_push(todo, handle( foo_new("play video games") ))

	activity.foo = object.foo( vector_pop(todo) )

A couple things to note about using a vector as a stack: if you know how many elements you'll be adding beforehand, you can call vector_alloc() to prevent the vector from being automatically enlarged several times; also, memory is currently not reclaimed after popping - the expectation is that the vector will grow again to that size later. A call to vector_resize() with the result from vector_count() will free up unused space, but at 4 bytes per element, it's probably not that important unless you have a lot of vectors!

For completeness, the other list operations are provided for vectors: shift, unshift, insert_before, insert_after, remove_element. It's important to note that these operations require some or all of the data stored in the vector to be moved, and are therefore probably slow.

To see all the operations you can perform on vectors, see the code archive page for Container: vector.


Grovesy(Posted 2005) [#2]
Hi octothorpe,

This looks like exactly what im after. Most specifically the Hash Table bit, but im having a problem using it tho ! I followed the "Container: hash table" link and downloaded the code, but in that source code it includes "../common/listC.bb", but where is this listC.bb?

Cheers


octothorpe(Posted 2005) [#3]
listC.bb is Container: double-linked list which the hash table library is dependant upon (also the only dependancy with these libraries.) Sorry for the relative path - that's a byproduct of my own development, and I must have forgotten to remove "../common/" from the source. I'll go fix that now and add a comment to the Include line to let people know where to find listC.bb if the code gets separated from this tutorial.

Edit: just realized that nowhere did I specify recommended filenames for these libraries. I'll add a line to the top of each file with recommended filenames in their next revision. I use: listC.bb, hashC.bb, and vectorC.bb.

Great to hear someone's interested in using this stuff! :) Let me know if you have any more trouble or questions.


Jams(Posted 2005) [#4]
"Great to hear someone's interested in using this stuff! :)"

I really can't fathom why many more people aren't all over this immensely useful library!! Truly one of the best code contributions to the B3D community ever!!!


Blitzplotter(Posted 2006) [#5]
This looks potentially very useful material. I will be slowly digesting it in time, keep up the good work.


Sir Gak(Posted 2006) [#6]
Blitzplotter, re: your sig,
exactly how long DID it take to build Rome?


H&K(Posted 2006) [#7]
Is Rome finished? Last Time I was in Rome there seem a load of building work going on.

Mindyou maybe its like BattleCrusier 3000, it was finished when the publisher said it was.