Developing a small sorting algorithm library on G'MIC

Software G'MIC
1

After playing with merge sort, and looking at timsort, I realized that tim sort is just merge sort with the difference of how initial subarrays are sorted. And I looked up smoothsort, and it seems easy to implement. So, I thought of an algorithm that use insertion sort and smoothsort depending on subarray size, and then just merge them together (Timsort, but with either insertion sort or smoothsort at the very beginning). This makes me realize that I could make a small sorting algorithm library for the purpose of solving this problem.

The thing is that G’MIC has no built-in way to sort parts of images effectively. I do plan to make a pixelsorting filters that’s a little bit more advanced than the G’MIC stdlib version, so hence why I’m doing this. Another reason is that I might experiment with multi-threaded sorting as merging lends itself to parallelization naturally.

Problem is that I hit a limitation:

foo_test_sort_lib:
5,1,1,3,u ({expr('u',5)})

eval ""${-rep_sort_lib}"insertion_sort(0,0,0,0,0,'x',
                                       1,0,0,0,0,'x',5);"


#@cli rep_sort_lib
#@cli : Return strings which is code of sorting algorithms to be used in math parser.
#@cli : $ echo ${-rep_sort_lib}
rep_sort_lib:
status "
	const _x=0;const _y=1;const _z=2;const _c=3;

	insertion_sort(destination_ind,destination_x,destination_y,destination_z,destination_c,destination_axis,source_ind,source_x,source_y,source_z,source_c,source_axis,length)=(
		if(size(source_axis)==1
		,axis_src_choice=source_axis[0]
		,run('error invalid_arg_source_axis');
		);
		if(!inrange(axis_src_choice,0,4,1,0),run('error invalid_arg_source_axis'););

		if(size(destination_axis)==1
		,axis_des_choice=destination_axis[0]
		,run('error invalid_arg_source_axis');
		);
		if(!inrange(axis_des_choice,0,4,1,0),run('error invalid_arg_source_axis'););

		axis_des_choice==_c?(
			sorting_array=crop(#source_ind,source_x#,source_y#,source_z#,source_c#,length#,1,1,1);
		):
		axis_des_choice==_z?(
			sorting_array=crop(#source_ind,source_x#,source_y#,source_z#,source_c#,1,length#,1,1);
		):
		axis_des_choice==_y?(
			sorting_array=crop(#source_ind,source_x#,source_y#,source_z#,source_c#,1,1,length#,1);
		):
		axis_des_choice==_x?(
			sorting_array=crop(#source_ind,source_x#,source_y#,source_z#,source_c#,1,1,1,length#);
		);
		sorting_array;
	);
	"

C:\Windows\System32>gmic foo_test_sort_lib
[gmic]./ Start G'MIC interpreter (v.3.5.0).
[gmic] *** Error in ./foo_test_sort_lib/ (file 'C:\Users\Miguel\user.gmic', line #11) *** Command 'eval': When substituting function 'insertion_sort()': Function 'crop()': Fifth argument (of type 'const scalar' and value 0) is not a strictly positive integer constant, in expression 'axis_des_choice==_c?( sorting_array=crop(1,(0),(0),(0),(0),(...)'.
[gmic] Command 'eval' has the following description:

  eval (+):
      expression

    Evaluate specified math expression.
     * If no command selection is specified, the expression is evaluated once
    and its result is set to status.
     * If command selection is specified, the evaluation is looped over
    selected images. Status is unchanged. In this case, 'eval' is similar to
    fill without assigning the image values.
2

Now, I made new progress on this library of mine:

#@cli rep_sort_lib
#@cli : Return string which is code of sorting algorithms to be used in math parser.
#@cli : $ echo ${-rep_sort_lib}
rep_sort_lib:
status "
	const __x=0;
	const __y=1;
	const __z=2;
	const __xy=3;
	const __xyz=4;

	_value_of_axis(string)=(
		__size_string=size(string);
		__size_string==3?(
			if(!same(string,'xyz'),run('error inval_arg_axis'););
			__xyz;
		):
		__size_string==2?(
			__LI=__size_string-1;
			string[0]==_'x'?(
				if(!inrange(string[__LI],_'x',_'z',0,1),run('error inval_arg_axis'););
				3+(string[0]-_'x')+(string[__LI]-_'y');
			):(run('error inval_arg_axis');0;);
		):
		__size_string==1?(
			if(!inrange(__output=string[0]-_'x',__x,__z,1,1),run('error inval_arg_axis'););
			__output;
		):(run('error inval_arg_axis');0;);
	);

	_coordinates_in_place(coordinates,max_indexes)=(
		isint(coordinates[0],0,max_indexes[0])&&
		isint(coordinates[1],0,max_indexes[1])&&
		isint(coordinates[2],0,max_indexes[2])&&
		isint(coordinates[3],0,max_indexes[3])
	);

	_validate_args(crop_ind,crop_length,axis,xpos,ypos,zpos,cpos)=(
		axis<__xy?(
			ref([xpos,ypos,zpos,cpos],_positions);
			ref([w##crop_ind,h##crop_ind,d##crop_ind,s##crop_ind]-1,_boundary);
			_positions[axis]+=crop_length;
			++_boundary[axis];
			_bool_out=_coordinates_in_place(_positions,_boundary);
			unref(_positions,_boundary);
		):(
			_bool_out=_coordinates_in_place([xpos,ypos,zpos,cpos],[w##crop_ind,h##crop_ind,d##crop_ind,s##crop_ind]-1)?(
				if(axis==__xyz
				,c2o(##crop_ind,xpos,ypos,zpos,cpos)+crop_length<=c2o(##crop_ind,w##crop_ind-1,h##crop_ind-1,d##crop_ind-1,cpos)
				,c2o(##crop_ind,xpos,ypos,zpos,cpos)+crop_length<=c2o(##crop_ind,w##crop_ind-1,h##crop_ind-1,zpos,cpos)
				);
			);
		);

		if(!_bool_out,
			run('error \"Invalid Inputs for crop.\"');
		);
	);

	_crop_from_image(crop_ind,crop_length,axis,xpos,ypos,zpos,cpos)=(
		ref([w##crop_ind,h##crop_ind,d##crop_ind,s##crop_ind]-1,_dimensions);

		_validate_args(crop_ind,crop_length,axis,xpos,ypos,zpos,cpos);

		 axis==__x?(crop(##crop_ind,xpos,ypos,zpos,cpos,crop_length,1,1,1);)
		:axis==__y?(crop(##crop_ind,xpos,ypos,zpos,cpos,1,crop_length,1,1);)
		:axis==__z?(crop(##crop_ind,xpos,ypos,zpos,cpos,1,1,crop_length,1);)
		:(
			__result=vector(##crop_length,nan);
			copy(__result[0],i(##crop_ind,xpos,ypos,zpos,cpos),crop_length,1,1);
			__result;
		);
	);

	_insertion_sort(pnt_ref_arg,length)=(
		ref(pnt_ref_arg,ref_arr);
		for(_p=1,_p<length,++_p,
			_arr_offset=_p;
			while(_arr_offset,
				ref_arr[_arr_offset]<ref_arr[_arr_offset-1]?(
					swap(ref_arr[_arr_offset],ref_arr[_arr_offset-1]);
					swap_pixels();
				):(break(););
				--_arr_offset;
			);
		);
		unref(ref_arr);
	);

	insertion_sort(destination_ind,destination_x,destination_y,destination_z,destination_c,destination_axis,source_ind,source_x,source_y,source_z,source_c,source_axis,length)=(
		_arg_src_axis=_value_of_axis(source_axis);
		_arg_des_axis=_value_of_axis(destination_axis);
		_validate_args(destination_ind,length,_arg_des_axis,destination_x,destination_y,destination_z,destination_c);
		_adj_vec=_crop_from_image(source_ind,length,_arg_src_axis,source_x,source_y,source_z,source_c);
		_arg_des_axis==__x?(swap_pixels()=swap(I(##destination_ind,destination_x+_arr_offset,1,1,1),I(##destination_ind,destination_x+_arr_offset-1,1,1,1))):
		_arg_des_axis==__y?(swap_pixels()=swap(I(##destination_ind,1,destination_y+_arr_offset,1,1),I(##destination_ind,1,destination_y+_arr_offset-1,1,1))):
		_arg_des_axis==__z?(swap_pixels()=swap(I(##destination_ind,1,1,destination_z+_arr_offset,1),I(##destination_ind,1,1,destination_z+_arr_offset-1,1)))
		:(
		 _offset=c2o(##destination_ind,destination_x,destination_y,destination_z,0);
		 swap_pixels()=swap(I[##destination_ind,_offset+_arr_offset],I[##destination_ind,_offset+_arr_offset-1]);
		);
		_insertion_sort(_adj_vec,length);
	);"

Things to do before the next step, add const length, and possible override macros to limit amount of sorting for partial sorting result. After that, I’ll add smoothsort, and merge_pixels(). merge_pixels() merges sorted pixels and the sorting is dependent on channel to use.

Test the sort_lib code with this:

foo_test_sort_lib:
5,1,1,3,v(10) 5,5,5,1,v(0,100) [0]

eval ""${-rep_sort_lib}"
		insertion_sort(0,0,0,0,0,'x',
					   1,0,0,0,0,'y',5);"