C++ like rotate

General FreeBASIC programming questions.
Post Reply
Provoni
Posts: 439
Joined: Jan 05, 2014 12:33
Location: Belgium

C++ like rotate

Post by Provoni »

Here's what I believe to be a C++ rotate like SUB I wrote:

* 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
Post Reply