[iAmir]

NOTE

This tutorial is done by Y_Less about 6years ago.
I am just re-posting it because there's no place to find this tutorial about jagged arrays (y_jaggedarray) anymore.
This is a good include in YSI, which can be very useful in many ways. ( Random messages, multi-language messages in arrays, question messages and much more. )

Thanks to Y_Less for this great tutorial and include.

Introduction

Have you ever made an array like this:

Code:

new gArray[4][3] = {{1}, {2}, {3}, {4, 5, 6}};

The first three slots only use 1 cell each, and you may never need more than that. It would be much more memory efficient if you could do:

Code:

new gArray[4][1, 1, 1, 3] = {{1}, {2}, {3}, {4, 5, 6}};

You would save 6 cells. And in actual fact, the way multi-dimensional arrays are represented internally means that this is in theory possible, but there's no compiler support for it.

Or maybe you build up an array, say an array of questions in a quiz, but some quizes are shorter than others. You need each slot to be large enough to hold the biggest quiz allowed, but most will never be that big and if you could reuse those spare slots you could make even bigger quizes!

Jagged_Resize

This include allows you to resize array slots. It provides one main function "Jagged_Resize":

Code:

#include <YSI\y_jaggedarray>

new gArray[4][2];

main()
{
	Jagged_Resize(gArray, {0, 1}, {1, 1}, {2, 1});
}

The function takes an array (here "gArray") and a series of "tuples" (pairs of values, as many as you want). Each pair is a slot and new size. After the function call above you will end up with "gArray" having 4 slots, the first three one cell large and the last one the remainder - you can't manually resize the last slot as it is the one that gets stretched and shrunk to accomodate other movements. This will mean that slot 3 (or index 3) is 5 cells large (because 4*2-3 is 5), rather than the 3 we need, but the whole array is still 4 cells smaller than the original version.

Now obviously 4 cells isn't a massive saving, but that's just an example.

jaggedsizeof

This include actually modifies the underlying PAWN array headers, you don't just make "gArray[0]" LOOK like it is 1 cell big, it really IS 1 cell big! However, this means you can no longer use "sizeof" very well:

Code:

#include <YSI\y_jaggedarray>

new gArray[4][4];

main()
{
	Jagged_Resize(gArray, {0, 1});
	printf("%d", sizeof (gArray[])); // Will always print "4".
}

"sizeof" is done at compile-time and will represent the original size of the slots, so we need a new function that is done at run-time to get the size of the slot at that exact moment. What's more, because PAWN doesn't support jagged arrays by default, "sizeof" doesn't specify a slot - they are all the same so you just do "gArray[]". We need more control to specify WHICH slot we want the size of:

Code:

#include <YSI\y_jaggedarray>

new gArray[4][4];

main()
{
	Jagged_Resize(gArray, {0, 1});
	printf("%d", jaggedsizeof (gArray[0])); // Will currently print "1".
	printf("%d", jaggedsizeof (gArray[3])); // Will currently print "7".
}

As I said, the last slot in an array is the buffer - when you resize a slot the last slot changes size as well (and if you make a slot too big others will be compressed to - the TOTAL size of an array remains constant). Hence in the code above the size of "gArray[3]" ends up as 7 (its original 4 plus the spare 3 from "gArray[0]").

Use

Once you have a resized array you can use it like any other:

Code:

#include <YSI\y_jaggedarray>

new gArray[4][2] = {{1}, {2}, {3}, {4, 5}};

main()
{
	Jagged_Resize(gArray, {0, 1}, {1, 1}, {2, 1});
	Print(gArray[0], jaggedsizeof(gArray[0]));
	Print(gArray[1], jaggedsizeof(gArray[1]));
	Print(gArray[2], jaggedsizeof(gArray[2]));
	Print(gArray[3], jaggedsizeof(gArray[3]));
}

Print(arr[], size)
{
	for (new i = 0; i != size; ++i)
	{
		printf("slot %d = %d", i, arr[i]);
	}
}

That will give:

Code:

slot 0 = 1
slot 0 = 2
slot 0 = 3
slot 0 = 4
slot 1 = 5
slot 2 = 0
slot 3 = 0
slot 4 = 0

When you expand any part of an array the new bits are ALWAYS set to 0 - you don't get garbage memory and you can't specify the default currently.

Drawbacks

There are a couple of drawbacks to this system:

1) The compiler tries to be clever:

Code:

#include <YSI\y_jaggedarray>

new gArray[4][4];

main()
{
	Jagged_Resize(gArray, {0, 1});
	printf("%d", gArray[3][5]);
}

Because we have resized the array, this is entirely valid and "gArray[3]" has a slot 5 (because it now has 7). However, the compiler doesn't know that you can resize arrays and will flag this as an error. By default the highest index would be 3, and 5 is larger than that, so you shouldn't be able to do it (but obviously we can now).

2) The run-time system tries to be clever:

The obvious solution to the first problem is this:

Code:

#include <YSI\y_jaggedarray>

new gArray[4][4];

main()
{
	new
		idx = 5;
	Jagged_Resize(gArray, {0, 1});
	printf("%d", gArray[3][idx]);
}

The compiler isn't clever enough to spot that code as a potential out-of-bounds error, so will compile it quite hapilly. Unfortunately, it will add a "BOUNDS" check to your code so that when you try run the code it will fail. You CAN bypass this by using the "-d0" compile flag (generally good on production code, but not common).

The only other way around this issue is to confuse your code so that it doesn't know how big the array is meant to be, this is actually quite simple:

Code:

#include <YSI\y_jaggedarray>

new gArray[4][4];

Func(arr[][], slot1, slot2)
{
	printf("%d", arr[slot1][slot2]);
}

main()
{
	Jagged_Resize(gArray, {0, 1});
	Func(gArray, 3, 5);
}

Because "Func" has a parameter of "arr[][]", neither the compiler nor the runtime can know how big the array should be (you could call it with two different size arrays). This means it can add any bounds checks and we can access our extra slots perfectly hapilly.

3) You can't sort these arrays.

Slice's multi-dimensional array sort include relies on VERY similar techniques to modify the underlying array header for fast rearranging. This means the two systems are entirely incompatible, but sorting jagged arrays makes no sense anyway.

4) Currently only 2D.

For this to be really useful I need to support 2D enum arrays (i.e. 3D arrays), but it doesn't quite yet.

Download

YSI-Includes


Extra

There are a few other functions available:

Code:

bool:Jagged_ResizeOne(array[][], size1, size2, slot, newSize);

That will resize just one slot to the given new size, but this is more complex to call that "Jagged_Resize" as you have to manually pass all the original slot sizes, i.e.:

Code:

Jagged_ResizeOne(gArray, sizeof (gArray), sizeof (gArray[]), 0, 8);

This can be simplified with the "_Jagged()" macro:

Code:

Jagged_ResizeOne(_Jagged(gArray), 0, 8);

And if you would like more internal information about arrays, you can call:

Code:

stock _Jagged_PrintHeader(array[][], size1, size2);

Again you can use the "_Jagged" macro and this will print the current state of the array header (i.e. the offsets in to memory of each main slot).