Dynamic lists. Resizes at multiples of 2. Probably preferable to
this.
arr = new_MArray()
for i = 0 to 9
arr = MArray_add(arr, i, random(1500, 3000)/100.0)
next i
oarr = MArray_copy(arr)
MArray_bubbleSort(arr)
do
size = MArray_size(arr)
print(\"New Values (\"+str(size)+\")[\"+str(MArray_space(arr))+\"]\")
for i = 0 to size-1
print(MArray_get(arr, i))
next i
print(\"Old Values (\"+str(size)+\")[\"+str(MArray_space(oarr))+\"]\")
for i = 0 to size-1
print(MArray_get(oarr, i))
next i
sync()
loop
function new_MArray() \'{ returns MArray O(1)
ID = createMemblock(4+4)
setMemblockInt(ID, 0, 0) //number of elements
endfunction ID \'}
function MArray_add(ID, index, num#) \'{ returns MArray O(n)
ID = MArray_resize(ID)
if index = MArray_size(ID)
setMemblockFloat(ID, 4+MArray_size(ID)*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4))
next i
setMemblockFloat(ID, 4+index*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID \'}
function MArray_remove(ID, index) \'{ returns MArray O(n)
if index = MArray_size(ID)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
exitfunction ID
endif
for i = index+1 to MArray_size(ID)-1
setMemblockFloat(ID, 4+(i-1)*4, getMemblockFloat(ID, 4+i*4))
next i
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
endfunction ID \'}
function MArray_set(ID, index, num#) \'{ returns MArray O(1)
setMemblockFloat(ID, 4+index*4, num#)
endfunction ID \'}
function MArray_get(ID, index) \'{ returns float O(1)
out# = getMemblockFloat(ID, 4+index*4)
endfunction out# \'}
function MArray_size(ID) \'{ returns integer O(1)
out = getMemblockInt(ID, 0)
endfunction out \'}
function MArray_space(ID) \'{ returns integer O(1)
out = (getMemblockSize(ID)-4)/4
endfunction out \'}
function MArray_resize(ID) \'{ returns MArray O(n)
out = ID
size = MArray_size(ID)
space = MArray_space(ID)
if size < space/2 //reduce size
out = createMemblock(4+space/2*4)
for i = 0 to getMemblockSize(out)-1
setMemblockByte(out, i, getMemblockByte(ID, i))
next i
deleteMemblock(ID)
endif
if size >= space //increase size
out = createMemblock(4+space*2*4)
for i = 0 to getMemblockSize(ID)-1
setMemblockByte(out, i, getMemblockByte(ID, i))
next i
deleteMemblock(ID)
endif
endfunction out \'}
function MArray_copy(ID) \'{ returns MArray O(n)
size = MArray_size(ID)
space = MArray_space(ID)
out = createMemblock(4+space*4)
for i = 0 to getMemblockSize(out)-1
setMemblockByte(out, i, getMemblockByte(ID, i))
next i
endfunction out \'}
function MArray_bubbleSort(ID) \'{ returns MArray O(n^2)
i = 0
while i < MArray_size(ID)-1
geti# = MArray_get(ID, i)
geti1# = MArray_get(ID, i+1)
if geti# > geti1#
MArray_set(ID, i, geti1#)
MArray_set(ID, i+1, geti#)
if i <> 0 then i = i-1
else
i = i+1
endif
endwhile
endfunction ID \'}
From my testing it looks like these are about 2 times slower than normal arrays with constant time operations. It grew to 5 times adding 1000 elements using the same style of array growth (I assume it\'s because the interpreted code to copy over values is slower than dim\'s. I have since made a slight adjustment to increase the copy speed). So I have to say, this seems like a pretty strong alternative in those times when you can\'t use arrays (and these won\'t run into problems with shrinking in size
).
Some Notes:
-You need to reassign pointers to memblocks from any functions that may resize the MArray. It\'s simply because resizing memblocks demands that you discard the old one. For example, add should be used as such
arr = MArray_add(arr, index, value)
. It is not needed with functions like set, but for convention you can still write your code that way.
-I don\'t catch any bounds errors here. You will most likely receive a memblock offset error if you violate the bounds of your MArray. I decided to leave the code that way because AppGameKit doesn\'t have a standard for throwing your own errors.
-Adding to the end is usually O(1) because no shifting is needed. If order doesn\'t matter add to the end to max out efficiency.
Edit: Updated version. This example shows how you can mix floats and ints into the same array (if you are careful
)
arr = new_MArray()
for i = 0 to 9
if mod(i,2) = 0
arr = MArray_add_int(arr, i, random(0, 30))
else
arr = MArray_add_float(arr, i, random(0, 30000)/1000.0)
endif
next i
do
size = MArray_size(arr)
print(\"Values (\"+str(size)+\")[\"+str(MArray_space(arr))+\"]\")
for i = 0 to size-1
if mod(i,2) = 0
print(MArray_get_int(arr, i))
else
print(MArray_get_float(arr, i))
endif
next i
sync()
loop
function new_MArray() \'{ returns MArray O(1)
ID = createMemblock(4+4)
setMemblockInt(ID, 0, 0) //number of elements
endfunction ID \'}
function delete_MArray(ID) '{ returns void O(1)
deleteMemblock(ID)
endfunction '}
function MArray_add_float(ID, index, num#) \'{ returns MArray O(n)
ID = MArray_resize(ID)
if index = MArray_size(ID)
setMemblockFloat(ID, 4+MArray_size(ID)*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4))
next i
setMemblockFloat(ID, 4+index*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID \'}
function MArray_add_int(ID, index, num) \'{ returns MArray O(n)
ID = MArray_resize(ID)
if index = MArray_size(ID)
setMemblockInt(ID, 4+MArray_size(ID)*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4)) //regardless of whether or not these values are actually floats 4 bytes are copied
next i
setMemblockInt(ID, 4+index*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID \'}
function MArray_remove(ID, index) \'{ returns MArray O(n)
if index = MArray_size(ID)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
exitfunction ID
endif
for i = index+1 to MArray_size(ID)-1
setMemblockFloat(ID, 4+(i-1)*4, getMemblockFloat(ID, 4+i*4))
next i
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
endfunction ID \'}
function MArray_set_float(ID, index, num#) \'{ returns MArray O(1)
setMemblockFloat(ID, 4+index*4, num#)
endfunction ID \'}
function MArray_set_int(ID, index, num) \'{ returns MArray O(1)
setMemblockInt(ID, 4+index*4, num)
endfunction ID \'}
function MArray_get_float(ID, index) \'{ returns float O(1)
out# = getMemblockFloat(ID, 4+index*4)
endfunction out# \'}
function MArray_get_int(ID, index) \'{ returns float O(1)
out = getMemblockInt(ID, 4+index*4)
endfunction out \'}
function MArray_size(ID) \'{ returns integer O(1)
out = getMemblockInt(ID, 0)
endfunction out \'}
function MArray_space(ID) \'{ returns integer O(1)
out = (getMemblockSize(ID)-4)/4
endfunction out \'}
function MArray_resize(ID) \'{ returns MArray O(n)
out = ID
size = MArray_size(ID)
space = MArray_space(ID)
if size < space/2 //reduce size
out = createMemblock(4+space/2*4)
for i = 0 to getMemblockSize(out)-1 step 4
setMemblockInt(out, i, getMemblockInt(ID, i))
next i
deleteMemblock(ID)
endif
if size >= space //increase size
out = createMemblock(4+space*2*4)
for i = 0 to getMemblockSize(ID)-1 step 4
setMemblockInt(out, i, getMemblockint(ID, i))
next i
deleteMemblock(ID)
endif
endfunction out \'}
function MArray_copy(ID) \'{ returns MArray O(n)
size = MArray_size(ID)
space = MArray_space(ID)
out = createMemblock(4+space*4)
for i = 0 to getMemblockSize(out)-1 step 4
setMemblockInt(out, i, getMemblockInt(ID, i))
next i
endfunction out \'}
function MArray_bubbleSort_float(ID) \'{ returns MArray O(n^2)
i = 0
while i < MArray_size(ID)-1
geti# = MArray_get_float(ID, i)
geti1# = MArray_get_float(ID, i+1)
if geti# > geti1#
MArray_set_float(ID, i, geti1#)
MArray_set_float(ID, i+1, geti#)
if i <> 0 then i = i-1
else
i = i+1
endif
endwhile
endfunction ID \'}
function MArray_bubbleSort_int(ID) \'{ returns MArray O(n^2)
i = 0
while i < MArray_size(ID)-1
geti = MArray_get_int(ID, i)
geti1 = MArray_get_int(ID, i+1)
if geti > geti1
MArray_set_int(ID, i, geti1)
MArray_set_int(ID, i+1, geti)
if i <> 0 then i = i-1
else
i = i+1
endif
endwhile
endfunction ID \'}
Just the functions.
function new_MArray() \'{ returns MArray O(1)
ID = createMemblock(4+4)
setMemblockInt(ID, 0, 0) //number of elements
endfunction ID \'}
function delete_MArray(ID) '{ returns void O(1)
deleteMemblock(ID)
endfunction '}
function MArray_addEnd_float(ID, num#) \'{ returns MArray O(1)
ID = MArray_resize(ID)
setMemblockFloat(ID, 4+MArray_size(ID)*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID \'}
function MArray_addEnd_int(ID, num) \'{ returns MArray O(1)
ID = MArray_resize(ID)
setMemblockInt(ID, 4+MArray_size(ID)*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID \'}
function MArray_add_float(ID, index, num#) \'{ returns MArray O(n)
ID = MArray_resize(ID)
if index = MArray_size(ID)
setMemblockFloat(ID, 4+MArray_size(ID)*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4))
next i
setMemblockFloat(ID, 4+index*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID \'}
function MArray_add_int(ID, index, num) \'{ returns MArray O(n)
ID = MArray_resize(ID)
if index = MArray_size(ID)
setMemblockInt(ID, 4+MArray_size(ID)*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4)) //regardless of whether or not these values are actually floats 4 bytes are copied
next i
setMemblockInt(ID, 4+index*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID \'}
function MArray_remove(ID, index) \'{ returns MArray O(n)
if index = MArray_size(ID)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
exitfunction ID
endif
for i = index+1 to MArray_size(ID)-1
setMemblockFloat(ID, 4+(i-1)*4, getMemblockFloat(ID, 4+i*4))
next i
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
endfunction ID \'}
function MArray_set_float(ID, index, num#) \'{ returns MArray O(1)
setMemblockFloat(ID, 4+index*4, num#)
endfunction ID \'}
function MArray_set_int(ID, index, num) \'{ returns MArray O(1)
setMemblockInt(ID, 4+index*4, num)
endfunction ID \'}
function MArray_get_float(ID, index) \'{ returns float O(1)
out# = getMemblockFloat(ID, 4+index*4)
endfunction out# \'}
function MArray_get_int(ID, index) \'{ returns float O(1)
out = getMemblockInt(ID, 4+index*4)
endfunction out \'}
function MArray_size(ID) \'{ returns integer O(1)
out = getMemblockInt(ID, 0)
endfunction out \'}
function MArray_space(ID) \'{ returns integer O(1)
out = (getMemblockSize(ID)-4)/4
endfunction out \'}
function MArray_resize(ID) \'{ returns MArray O(n)
out = ID
size = MArray_size(ID)
space = MArray_space(ID)
if size < space/2 //reduce size
out = createMemblock(4+space/2*4)
for i = 0 to getMemblockSize(out)-1 step 4
setMemblockInt(out, i, getMemblockInt(ID, i))
next i
deleteMemblock(ID)
endif
if size >= space //increase size
out = createMemblock(4+space*2*4)
for i = 0 to getMemblockSize(ID)-1 step 4
setMemblockInt(out, i, getMemblockint(ID, i))
next i
deleteMemblock(ID)
endif
endfunction out \'}
function MArray_copy(ID) \'{ returns MArray O(n)
size = MArray_size(ID)
space = MArray_space(ID)
out = createMemblock(4+space*4)
for i = 0 to getMemblockSize(out)-1 step 4
setMemblockInt(out, i, getMemblockInt(ID, i))
next i
endfunction out \'}
function MArray_bubbleSort_float(ID) \'{ returns MArray O(n^2)
i = 0
while i < MArray_size(ID)-1
geti# = MArray_get_float(ID, i)
geti1# = MArray_get_float(ID, i+1)
if geti# > geti1#
MArray_set_float(ID, i, geti1#)
MArray_set_float(ID, i+1, geti#)
if i <> 0 then i = i-1
else
i = i+1
endif
endwhile
endfunction ID \'}
function MArray_bubbleSort_int(ID) \'{ returns MArray O(n^2)
i = 0
while i < MArray_size(ID)-1
geti = MArray_get_int(ID, i)
geti1 = MArray_get_int(ID, i+1)
if geti > geti1
MArray_set_int(ID, i, geti1)
MArray_set_int(ID, i+1, geti)
if i <> 0 then i = i-1
else
i = i+1
endif
endwhile
endfunction ID \'}
new_MArray()
delete_MArray(ID)
MArray_addEnd_float(ID, num#)
MArray_addEnd_int(ID, num)
MArray_add_float(ID, index, num#)
MArray_add_int(ID, index, num)
MArray_remove(ID, index)
MArray_set_float(ID, index, num#)
MArray_set_int(ID, index, num)
MArray_get_float(ID, index)
MArray_get_int(ID, index)
MArray_get_size(ID)
MArray_copy(ID)
...
MArray_space(ID) returns the number of indexes the current memblock can hold. Only important if you\'re counting memory space.
MArray_resize(ID) is called by add and remove. I\'d warn against playing with it outside of those commands. You can modify it to change the conditions under which the array resizes.
MArray_bubbleSort_float(ID)/MArray_bubbleSort_int(ID) only work if you have a homogeneous array when it comes to data type. You can use these functions but if your array is of considerable size find a better sort
Edit2: Strings!! The newest new command set -
function new_MArray() '{ returns MArray O(1)
ID = createMemblock(4+4)
setMemblockInt(ID, 0, 0) //number of elements
endfunction ID '}
function delete_MArray(ID) '{ returns void O(1)
deleteMemblock(ID)
endfunction '}
function MArray_addEnd_float(ID, num#) '{ returns MArray O(1)
ID = MArray_resize(ID)
setMemblockFloat(ID, 4+MArray_size(ID)*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID '}
function MArray_addEnd_int(ID, num) '{ returns MArray O(1)
ID = MArray_resize(ID)
setMemblockInt(ID, 4+MArray_size(ID)*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID '}
function MArray_addEnd_str(ID, st$) '{ returns MArray O(1)
ID = MArray_resize(ID)
st = createMemblockFromString(st$)
setMemblockInt(ID, 4+MArray_size(ID)*4, st)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID '}
function MArray_add_float(ID, index, num#) '{ returns MArray O(n)
ID = MArray_resize(ID)
if index = MArray_size(ID)
setMemblockFloat(ID, 4+MArray_size(ID)*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4))
next i
setMemblockFloat(ID, 4+index*4, num#)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID '}
function MArray_add_int(ID, index, num) '{ returns MArray O(n)
ID = MArray_resize(ID)
if index = MArray_size(ID)
setMemblockInt(ID, 4+MArray_size(ID)*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4)) //regardless of whether or not these values are actually floats 4 bytes are copied
next i
setMemblockInt(ID, 4+index*4, num)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID '}
function MArray_add_str(ID, index, st$) '{ returns MArray O(n)
ID = MArray_resize(ID)
st = createMemblockFromString(st$)
if index = MArray_size(ID)
setMemblockInt(ID, 4+MArray_size(ID)*4, st)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
exitfunction ID
endif
for i = MArray_size(ID) to index+1 step -1
setMemblockFloat(ID, 4+i*4, getMemblockFloat(ID, 4+(i-1)*4)) //regardless of whether or not these values are actually floats 4 bytes are copied
next i
setMemblockInt(ID, 4+index*4, st)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)+1)
endfunction ID '}
function MArray_remove(ID, index) '{ returns MArray O(n)
if index = MArray_size(ID)-1
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
exitfunction ID
endif
for i = index+1 to MArray_size(ID)-1
setMemblockFloat(ID, 4+(i-1)*4, getMemblockFloat(ID, 4+i*4))
next i
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
endfunction ID '}
function MArray_remove_str(ID, index) '{ returns MArray O(n)
if index = MArray_size(ID)-1
MArray_delete_str(ID, index)
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
exitfunction ID
endif
MArray_delete_str(ID, index)
for i = index+1 to MArray_size(ID)-1
setMemblockFloat(ID, 4+(i-1)*4, getMemblockFloat(ID, 4+i*4))
next i
setMemblockInt(ID, 0, getMemblockInt(ID, 0)-1)
ID = MArray_resize(ID)
endfunction ID '}
function MArray_set_float(ID, index, num#) '{ returns MArray O(1)
setMemblockFloat(ID, 4+index*4, num#)
endfunction ID '}
function MArray_set_int(ID, index, num) '{ returns MArray O(1)
setMemblockInt(ID, 4+index*4, num)
endfunction ID '}
function MArray_set_str(ID, index, st$) '{ returns MArray O(1)
st = createMemblockFromString(st$)
setMemblockInt(ID, 4+index*4, st)
endfunction ID '}
function MArray_get_float(ID, index) '{ returns float O(1)
out# = getMemblockFloat(ID, 4+index*4)
endfunction out# '}
function MArray_get_int(ID, index) '{ returns float O(1)
out = getMemblockInt(ID, 4+index*4)
endfunction out '}
function MArray_get_str(ID, index) '{ returns string O(1)
mem = getMemblockInt(ID, 4+index*4)
out$ = createStringFromMemblock(mem)
endfunction out$ '}
function MArray_delete_str(ID, index) '{ returns void O(1)
mem = getMemblockInt(ID, 4+index*4)
deleteMemblock(mem)
endfunction '}
function MArray_size(ID) '{ returns integer O(1)
out = getMemblockInt(ID, 0)
endfunction out '}
function MArray_space(ID) '{ returns integer O(1)
out = (getMemblockSize(ID)-4)/4
endfunction out '}
function MArray_resize(ID) '{ returns MArray O(n)
out = ID
size = MArray_size(ID)
space = MArray_space(ID)
if size < space/2 //reduce size
out = createMemblock(4+space/2*4)
for i = 0 to getMemblockSize(out)-1 step 4
setMemblockInt(out, i, getMemblockInt(ID, i))
next i
deleteMemblock(ID)
endif
if size >= space //increase size
out = createMemblock(4+space*2*4)
for i = 0 to getMemblockSize(ID)-1 step 4
setMemblockInt(out, i, getMemblockint(ID, i))
next i
deleteMemblock(ID)
endif
endfunction out '}
function MArray_copy(ID) '{ returns MArray O(n)
size = MArray_size(ID)
space = MArray_space(ID)
out = createMemblock(4+space*4)
for i = 0 to getMemblockSize(out)-1 step 4
setMemblockInt(out, i, getMemblockInt(ID, i))
next i
endfunction out '}
function createMemblockFromString(st$)
length = len(st$)
out = createMemblock(length*4)
for i = 0 to length-1
setMemblockInt(out, i*4, asc(mid(st$, i+1, 1)))
next i
endfunction out
function createStringFromMemblock(mem)
length = getMemblockSize(mem)/4
st$ = ""
for i = 0 to length-1
st$ = st$+chr(getMemblockInt(mem, i*4))
next i
endfunction st$
function MArray_bubbleSort_float(ID) '{ returns MArray O(n^2)
i = 0
while i < MArray_size(ID)-1
geti# = MArray_get_float(ID, i)
geti1# = MArray_get_float(ID, i+1)
if geti# > geti1#
MArray_set_float(ID, i, geti1#)
MArray_set_float(ID, i+1, geti#)
if i <> 0 then i = i-1
else
i = i+1
endif
endwhile
endfunction ID '}
function MArray_bubbleSort_int(ID) '{ returns MArray O(n^2)
i = 0
while i < MArray_size(ID)-1
geti = MArray_get_int(ID, i)
geti1 = MArray_get_int(ID, i+1)
if geti > geti1
MArray_set_int(ID, i, geti1)
MArray_set_int(ID, i+1, geti)
if i <> 0 then i = i-1
else
i = i+1
endif
endwhile
endfunction ID '}
Keep in mind that
-Strings must be converted into memblocks and recreated, so this is certainly slower than using normal strings.
-Strings are not automatically garbage collected, you have to delete them yourself or you'll run into memory leakage. I put in a MArray_remove_str() command which does call the cleanup command(MArray_delete_str), but if you plan on overwriting other strings, be sure to delete the old one
String Commands:
MArray_addEnd_str(ID, st$)
MArray_add_str(ID, index, st$)
MArray_set_str(ID, index, st$)
MArray_get_str(ID, index)
MArray_delete_str(ID, index)
