Set of templatable collections

[paul doe]

Seeing as some members asked for a set of collections in native FreeBasic, here's a small set I coded a while back:

https://github.com/glasyalabolas/fb-collections

They are part of a bigger framework, but they can be used standalone as well, so here they are. Collections included:

• Array
• List
• Doubly Linked List
• Dictionary (aka Hash Table or Associative Array)
• Priority Queue (ascending and descending)
• Stack
• Unordered map (like an Array but the order of the elements is not guaranteed to be contiguous)

All of them are templatable. To template them, you just issue template( <collection>, <datatype>), like this (the of() macro is just syntactic sugar):

Code: Select all

template( List, of( string ) ) '' Templates a list of strings
template( Dictionary, of( string ), of( string ) ) '' Templates a dictionary that associates strings to strings

All data types can be templated, including custom and abstract ones. In fact, you can template them to accept other collections as well:

Code: Select all

#include once "../inc/collections.bi"

'' This is how you template them for basic data types
'' Templates a list of strings
template( List, string )
'' Templates a dictionary that associates a string to a number
template( Dictionary, of( integer ), of( string ) )

'' More advanced templating can be done also. This templates a dictionary that
'' associates lists of strings to a string.
template( Dictionary, of( string ), of( List( of( string ) ) ) )

sub show( l as List( of( string ) ) ptr )
  if( l <> 0 ) then
    for i as integer = 0 to l->count - 1
      ? ( *l )[ i ]
    next
  else
    ? "Not found!"
  end if
end sub

dim as string items( ... ) = { _
  "Pears", "Apples", "Milk", "Meat", "Paul", "Jane" }

var d = Dictionary( of( string ), of( List( of( string ) ) ) )

d.add( "fruits", new List( of( string ) )->add( items( 0 ) ).add( items( 1 ) ) )
d.add( "groceries", new List( of( string ) )->add( items( 2 ) ).add( items( 3 ) ) )
d.add( "people", new List( of( string ) )->add( items( 4 ) ).add( items( 5 ) ) )

? "Fruits:"
show( d[ "fruits" ] )
?
? "Groceries:"
show( d[ "groceries" ] )
?
? "People:"
show( d[ "people" ] )
?
? "Whatever:"
show( d[ "whatever" ] )

sleep()

An important peculiarity to take into account is that they operate in two 'modes': if you want the collection to own an item, pass it a pointer to the item (or add it directly with new(), see the example above), and when the collection instance is destroyed, it will collect the item as well. Otherwise, if you pass them a reference to an item, it will aggregate it to the collection but it will not collect it when the instance is destroyed. This allows one to have the same item in different collections, but only the one you want will own them. Very useful to implement more advanced data structures, and to index the same set of data in different ways.
This trait is important when working with some collections like the Priority Queue, so pay attention and you won't have any troubles.

A small set of examples is included in the repo, but I can add more as requested. Any comments (especially bug reports) are appreciated and encouraged.

[badidea]

Interesting, I have been programming in freebasic for some years now, but when I see code like:
#define of( TType ) ##TType
... I have absolutely no idea what it does or how to read it.

[Imortis]

See: https://www.freebasic.net/wiki/KeyPgOpPpConcat

As he said it is just syntactic sugar. It just drops in whatever you put in the ().

[paul doe]

Update:

• Added forEach() overloads for collections missing them.
• Small bug fix in Dictionary collection (forEach() was not working properly).

[paul doe]

Update:

• I'll refactor the Stack and Unordered maps soon, as they work way too differently to the other collections. Don't use them for now.

[adeyblue]

All data types can be templated

That's not strictly true. It has the same limitations as every other token pasting solution - the dots in namespaced type names and the space in Ptr types break it. You can allow those things now, but then you have to fudge the declaration syntax in other ways.

Considering we "don't have any" of these things, I wonder how many there are. Mine, yours, the ones in Xusinboy's Framework, the ones in FBExt library, the Irrlicht translation probably has a few, there's a generic linked list at the top of the source code forum...

[paul doe]

...
That's not strictly true. It has the same limitations as every other token pasting solution - the dots in namespaced type names and the space in Ptr types break it.
...

Yes, but you can easily work around those with type aliases. What I'm talking about is any data type, even custom ones, types with abstract methods included. They also respect namespaces, and use a consistent interface (you use the same code to template any collection). The dictionaries also support any key (even custom types), not only strings. So far, none of the solutions I've checked support all these things combined.

There has been some work on the preprocessor as of lately, so I hope these quirks can be addressed soon as well. A preprocessor directive that mangles a symbol (converting dots and spaces to underscores, for example) would be really useful.

[paul doe]

Update:

• Fixed a bug in certain collections where a collection of function pointers would crash the app.
• Refactored the base class: now all collections derive from the same class, allowing for polymorphism between different collections and improving code generation size.