* For what I need it, speed is of the essence. Can anyone improve upon it?
* Does anyone have a valid working rotate of their own to compare the validity of my implementation?
* I don't really know how C++'s rotate behaves.
https://en.cppreference.com/w/cpp/algorithm/rotate
Thanks
Code: Select all
declare sub rotate_short(array()as short,byval f as integer,byval t as integer,byval a as integer)
screenres 640,480,32
#include "crt.bi"
randomize timer
dim as integer i,j,f,t,a
dim shared as integer l=10
dim as long state=int(rnd*31^2)or 1
dim as short array(l)
for i=1 to l
array(i)=i
print array(i);
next i
print:print
dim as double tim=timer
for i=1 to 100000000
state=48271*state and 2147483647
f=1+l*state shr 31
state=48271*state and 2147483647
t=1+l*state shr 31
state=48271*state and 2147483647
a=1+l*state shr 31
rotate_short(array(),f,t,a)
''print f,t,a
'rotate_short(array(),11,12,7)
'rotate_short(array(),12,11,7)
'rotate_short(array(),5,10,5)
'rotate_short(array(),1,2,9) 'simple rotate left
'rotate_short(array(),2,1,9) 'simple rotate right
next i
for i=1 to l
print array(i);
next i
print:print:print timer-tim
sleep
sub rotate_short(array()as short,byval f as integer,byval t as integer,byval a as integer)
'f=from position
't=to position
'a=amount to move
dim as integer i
static as short temp(1000) 'optimization
if f=t then exit sub 'equal from-to
if f+a>l+1 or t+a>l+1 then exit sub 'out of bound
if a=1 then 'optimization
swap array(f),array(t)
exit sub
end if
if t>f then 'to > from
if t-f=a then 'optimization
for i=0 to a-1
swap array(f+i),array(t+i)
next i
exit sub
end if
if i>a then 'store a, rotate i (optimization)
memmove(@temp(0),@array(f),a*2) 'store part
memmove(@array(f),@array(f+a),(t-f)*2) 'rotate
memmove(@array(t),@temp(0),a*2) 'restore part
else 'store i, rotate a (optimization)
memmove(@temp(0),@array(f+a),(t-f)*2) 'store part
memmove(@array(t),@array(f),a*2) 'rotate
memmove(@array(f),@temp(0),(t-f)*2) 'restore part
end if
else 'from > to
if f-t=a then 'optimization
for i=0 to a-1
swap array(t+i),array(f+i)
next i
exit sub
end if
if i>a then 'store a, rotate i (optimization)
memmove(@temp(0),@array(f),a*2) 'store part
memmove(@array(t+a),@array(t),(f-t)*2) 'rotate
memmove(@array(t),@temp(0),a*2) 'restore part
else 'store i, rotate a (optimization)
memmove(@temp(0),@array(t),(f-t)*2) 'store part
memmove(@array(t),@array(f),a*2) 'rotate
memmove(@array(t+a),@temp(0),(f-t)*2) 'restore part
end if
end if
end sub