JASS Challenge

JASS is missing one important thing: pointers. That makes advanced data structures difficult to implement. Also you cannot pass arrays to functions which causes ugly copy/paste/rename stuff to use a data structure repeatedly in a map.
This challenge will try to fix that.

The main point is to implement a heap on a JASS array. A heap is a "data structure" that allows to reserve memory space and free it at another point. Integers will serve as pointers where 0 is the null pointer. These pointers can then be easily passed to functions and returned by them.

It should implement this interface:

function HeapNew takes integer length returns integer
This function takes the length of the connected memory space you want and returns a pointer to the beginning of that space. Already reserved and not freed memory areas must not be returned by this function. If no more memory can be found then 0 is returned.

function HeapDelete takes integer pointer, integer length returns nothing
This function takes the pointer to an allocated memory area and its length and frees this area so it can be allocated again by HeapNew.

function HeapGet takes integer pointer returns integer
This function dereferences the passed pointer and returns the value at that point.

function HeapSet takes integer pointer, integer value returns nothing
This function dereferences the passed pointer and sets the value at that point to value.


Since the max array size of JASS is rather low for such a purpose the implementation should use two arrays and the structure used should be extendable to use more if necessary. Note that code outside of these functions should not have to care about that. So to the outside the heap presents one virtual memory space.


To test the functionality of the heap a linked list should be implemented with the following interface:

function ListNew takes nothing returns integer
This function returns an empty list.

function ListIsEmpty takes integer list returns boolean
This function takes a list and returns if it is empty.

function ListAddItem takes integer list, integer item_to_add returns integer
This function adds a new node with the content item_to_add to the beginning of the list and returns the new list.

function ListGetHead takes integer list returns integer
This function returns the head of the list (the content of the first node).

function ListGetTail takes integer list returns integer
This function returns the tail of the list (the list without the first node).
EDIT: Rename this function to ListGetNext.

function ListSetHead takes integer list, integer head returns nothing
This function sets the head of the list to the specified value.

function ListSetTail takes integer list, integer tail returns nothing
This function sets the tail of the list to the specified value.
EDIT: Rename this function to ListSetNext.

function ListDeleteHead takes integer list returns integer
This function deletes the first node and returns the rest list.

function ListDeleteAll takes integer list returns nothing
Deletes the entire list.

function ListAddList takes integer list1, integer list2 returns integer
Adds list2 at the end of list1.


Useful utility functions for both the heap and the list are welcome and give bonus points.

Submissions will be rated in 3 areas:

1) Utility, meaning how good it does what it is supposed to do

2) Efficiency, meaning how fast it is

3) Maintainability / Extendability / Reusability, meaning how easy it is to extend, reuse and maintain the code

In each of these areas 10 points are available. Apart from that there are 10 bonus points available.
Try to use variable names that tell what they are supposed to do, especially for global variables. Also add comments to potentially hard to understand code parts.

Submissions cost 20 points. These points will be put in a pot and divided among the best submissions. I also put any of my points above 200 I have until then into this pot.
To participate donate the 20 points to me and send the map with the code to [email protected] or PM me the location of the submission.
If you make any functions to test the list and the heap send them along too. They will not be rated but they will allow easier and more complete testings of all submissions.
Deadline is the night from Friday, 5th December to Saturday.

That seems to be a good system. I will look into it, but I fear that I don't have the time to do it.

It seems your are trying the Create your own class in jass . That is one of the best ideas I have heard in while. I ams use to C++ and java class structure it will be very inresting how this looks when finally done. I hope this works for you all.

There are many things that can be done with a heap and the longer I think about it the more I can think of.

Some more feedback would be nice. Are the instructions understandable? Who thinks that he will participate?

Just one thing, the list itself seems to have a heap style functionality because you will to build in a poiter style functionality into the list functions to refer to each seperate list.

The list should be based on the heap. It should not contain heap functionality itself. So each node of the list will probably be created with HeapNew.

I'm in! Me thinks the task is a terrific one.:D

How on earth do I donate points? emote_confused

Through the store.

First it seems like tail is every element of the list except the head (head, [tail]).

Then it seems like tail actually is the last element of the list (head, [elem], tail).
emote_sweat

Also linked lists ussually have no functionality for getting the tail, you find it by going through the list until there's nothing else that the list is pointing too.

Well, I read some specifications in English now of linked lists and it seems I confused the words here. In English the last element of the list is called the tail so I guess what I meant here should better have been called ListSetNext and ListGetNext.
What I want is a function to get the list without the first node and one that allows to set that rest list.
That means that ListSetNext(a, b) should take the head of list a and put list b behind that.

Is it important that the list implementation follows the specification, or is it good enogh that it's a good implementation? If it's the latter we could just leave the specification problem to the contestants, otherwisa there might be a few more things to sort out (like if a head and a list is the same thing, and if it should be single, double or circularly linked and the possibilities for traversal)... emote_confused

The specification was made with a single linked list in mind. But I agree that it is good to have a bit of specification on the contestant side. So if you like to make a double and / or circular linked list, feel free to do so.
The most important part of the challenge is the heap anyway and that specification should be followed as the heap should be exchangable (although additional functionality can be implemented of course).

Technically speaking all jass variables are pointers.

You can assign a variable x to variable y and change variable y, which will also change variable x.

I'm not sure of how useful this will be as a challenge, as I'm not really sure how to reference memory in jass (IS IT EVEN POSSIBLE?) but if you happen to have this thing already running I praise you and would like to see it.

Jass is missing classes and structs, the ability to override/overload functions and operators, if you really want to say what jass is missing. Interestingly enough though Common.j gets away with overloading functions...

Only handles work that way. They are pointers but their usage is limited as they cannot be freely used.

There is no way to access memory directly in JASS. Because of that an array is used as a kind of pseudo memory.

Structs can be used with a working heap (without support by the compiler of course, you will have to use pointer arithmetic). That reminds me that it would be great if someone would write a precompiler that takes high level code that allows for classes and structs and translates it into low level JASS with pointer arithmetic using the heap.
Where in common.j is overloading used ?