Vectors

From OHRRPGCE-Wiki
Jump to navigationJump to search

This page is for engine developers, and describes the vector.bi interface, which is a replacement, written in C, for FreeBasic's awful arrays.

These arrays are called vectors (as in the C++ STL) to avoid confusion with normal arrays. They are 0-based resizeable 1-D arrays of homogenous type which may be zero-length. UDTs may contain vectors, and they can be returned from functions. A set of generic functions for manipulating them is provided. Each has a header (hidden before the 0th index), which contains a pointer to a 'type table', the length, and a 'temporary' flag (unlike C++ which stores only the length and amount of reserved memory. On the other hand, vectors currently don't reserve more memory than they need). Vectors containing different types are different, just like vector<class> is templated by element type in C++.

You gain something, you lose something. Vectors require manual initialisation and destruction, and there's no out-of-bounds checking (use valgrind instead).

Documentation of the functions is in vector.bi, and examples are in vectortest.bas. Most the functions are also listed on this page.

Declarations[edit]

To declare a vector of integers, for example:

dim vec as integer vector

vector is really just an alias for ptr, so you can access the elements using pointer index notation: vec[i].

Each type from which you want to be able to form vectors needs to have a set of v_* function overloads and a type table variable declared:

DECLARE_VECTOR_OF_TYPE(type name, type_name)

And then the type table must defined, just once in some module. The type table tells what length each element of the vector is, and how to create, copy, delete, compare and print them. Vectors of the basic types integer, string, double are already decalred and defined. To declare vectors of some UDT which doesn't contain strings (or any other UDTs which contain strings:

DEFINE_VECTOR_OF_TYPE(type name, type_name)

If the UDT contains strings, then they need to be copied and deleted correctly, and instead we use:

DEFINE_VECTOR_OF_TYPE(type name, type_name)

If the UDT contains pointers to memory or vectors which require deep copying (which you are unlikely to want, actually), then the complicated DEFINE_CUSTOM_VECTOR_TYPE must be used instead.

Vector Vectors[edit]

Forming a Foo vector vector (where Foo might itself be a vector) is easy. Just use DEFINE_VECTOR_VECTOR_OF(Foo, Foo) instead of DEFINE_VECTOR_OF_TYPE(), and make sure that Foo vector is also declared and defined. From vectortest.bas:

'First we need to create 'string vector vector' overloads/typetable
DECLARE_VECTOR_OF_TYPE(string vector, string_vector)
DEFINE_VECTOR_VECTOR_OF(string, string)

'string vector vector vector
DECLARE_VECTOR_OF_TYPE(string vector vector, string_vector_vector)
DEFINE_VECTOR_VECTOR_OF(string vector, string_vector)

'...
dim arr as string vector vector vector
v_new arr
'...
print arr[1][2][3]


Basic Usage[edit]

All vector operations happen in-place.

Vector variables have to be initialised with v_new, v_copy or v_move, and freed with v_free (or returned from a function, or passed as 2nd argument to one of the 'destructive' vector functions).

dim as integer vector arr, arr2
v_new arr, 5       ' arr := [0, 0, 0, 0, 0]
arr[2] = 10        ' arr := [0, 0, 10, 0, 0]
v_copy arr2, arr   ' arr2 := [0, 0, 10, 0, 0]
arr[2] = 9         ' arr := [0, 0, 9, 0, 0]
v_sort arr         ' arr := [0, 0, 0, 0, 9]

v_free arr         ' delete vector, set arr = NULL
v_free arr2

If a function can change the length of an vector, then the vector can be realloced, and might be moved in memory, so the variable holding the pointer to it must be updated. So most vector functions take at least their first argument BYREF. Therefore:

The first argument to any vector manipulation function (including v_copy, v_move) must be either a variable or a temporary vector. Exceptions are simple functions like v_len and v_type which do not modify their arguments.

Returning from functions[edit]

Vectors which are marked as temporary are automatically freed after they appear as the second argument to any function, ie. they are appended or extended onto or spliced into another vector, or assigned (vector_move/vector_copy, which remove the temporary flag).

Always mark an vector as temporary when you return it from a function, and use v_copy (or equivalently v_move) to place it in a variable:

function range(byval n as integer) as integer vector
	dim ret as integer vector
	v_new ret, n
	for i as integer = 0 to n - 1
		ret[i] = i
	next
	return v_ret(ret)
end function

dim arr as integer vector
v_move arr, range(5)

The benefit of this convention is functional programming:

v_move arr, v_reverse(range(5))

Admittedly this is a bit awkward, and we may look into changing it in future.

Returning an empty vector from a function[edit]

The correct way to return an empty vector is as follows:

dim ret as string vector
v_new ret
return v_ret(ret)

Remember, NULL isn't a valid vector. And you need to DIM and init a vector in order to set the pointer to the type table.

Valgrind[edit]

There is no bounds checking on indexing vectors. You'll have to run under valgrind to catch these. If you compile with scons valgrind=1 then valgrind can also catch reading/writing to the -1th index, provided that the element size is greater than 2 bytes (eg. 32 bit int)

Functions[edit]

The vector functions mimic the methods for the Python list data type, but in imperative style. The table below gives equivalences. The actual function prototypes are documented in #MACRO DECLARE_VECTOR_OF_TYPE near the top of vector.bi, plus the "utilities" section at the bottom, and won't be replicated here.

Generic functions
Python FreeBASIC Uninitialised
vectors allowed?
Notes
a = [] v_new a Yes
a = [Elem() for i in range(n)] v_new a, n Yes Where Elem is the element type
a = None (kinda) v_free a Yes
a[x]

(x >= 0):

a[x]

(x < 0):

v_end(a)[x]
No Negative indices as in Python not are supported directly, but you can use v_end which points to one past the last element in the vector, so that indexing with -1 gives the last element, -2 the second last, and so on.
len(a) v_len(a) Yes
a = b[:] v_copy a, b Yes
a = b
b = None
v_move a, b Destination (a) only Similar to just a = b : b = NULL, except it clears the temporary flag, and deletes a if it contained anything. b is passed BYREF.
return a return v_ret(a) No Marks an vector as temporary; see above
return [] dim ret as string vector
v_new ret
return v_ret(ret)
N/A See above
a = returns_list() v_move a, returns_list() Destination (a) only Or use v_copy instead. Both unset the temporary flag.
a.append(b) v_append(a, b) No
a.extend(b) v_extend(a, b) No
a.extend(b)
b = None
v_extend_d(a, b) No b is passed BYREF.
a = a[0:n] + [Elem() for i in range(len(a), n)] v_resize a, n No Where Elem is the element type
a = a + [Elem() for i in range(0, n)] (kinda) elemptr = v_expand(a, n) No Where Elem is the element type
a == b v_equal(a, b) No
a.index(val) if val in a else -1 v_find(a, val) No
a.insert(i, val) v_insert(a, i, val) No Unlike Python, i must be in range 0 to len(a)
if val in a:
  temp = a.index(val)
  a.remove(val)
else:
  temp = -1
return temp
v_remove(a, val) No Returns index of the item, or -1 if not found
x = a.pop() x = v_end(a)
v_shrink a
No
a.pop() #Throw away return v_shrink a [, amount] No Can shrink by multiple elements
a.sort([cmp=sort_func]) v_sort(a [, sort_func]) No In-place sort using qsort, NOT stable. If the data type doesn't have a compare function specified, then a fatal error is thrown at runtime.
a[from:to] = [] v_delete_slice(a, from, to) No Unlike Python, from and to > len(a) is not allowed
str(a) v_str(a) Yes Returns e.g. '[["foo", "bar"], []]'
type(a[0]) (kinda) v_type(a) Yes Returns type table
Non-generic functions
sum(a) intvec_sum(a) Yes Only for integer vector
array_to_vector(a, array()) Yes Only for integer vector and string vector
vector_to_array(array(), a) No Only for integer vector and string vector

A note on temporary UDTs[edit]

Given context where a value of a certain type is expected, eg.

TYPE MyType :  foo as integer : bar as integer : END TYPE
DIM a as MyType
a = <something>

FB lets you use a temporary UDT.

a = Type(12, 13)

However it turns out that these are broken: you can't use them for types containing strings unless you create a constructor with the same signature (of course impossible in -lang deprecated)

See Also[edit]