Algorithms

ext/Algorithms provides various generic algorithms for manipulating ranges of elements, that is, elements that are stored in memory contiguously, generally denoted by a pointer to the first element in the range, and a pointer to just past the end of the range. The algorithms are generic in the sense that they can work with ranges of elements of various kinds -- even UDT objects -- though, in general, the algorithms have certain minimum requirements of the elements they manipulate.

As a simple example, the following code uses ext.QuickSort to rearrange elements in an array:

# include once "ext/algorithms/quicksort.bi"

dim array
(1 to 5) as integer = { 4, 1, 3, 5, 2 }

ext
.QuickSort(array())

for i as integer = 1 to 5
   
print "(" & array(i) & ")" ;
next : print

and produces the following output:

(1)(2)(3)(4)(5)

As another example, the following code uses ext.ReplaceIf to replace numeric characters in a string with the character x:

# include once "ext/algorithms/replaceif.bi"

function IsNumeric ( byref elem as const ubyte ) as ext.bool
   
return 0 < instr( "0123456789", chr(elem) )
end function

var text = "abc 123 def"
   
dim first
as ubyte ptr = strptr(text)
dim
last as ubyte ptr = first + len(text)
   
ext
.ReplaceIf( first, last, @IsNumeric, asc("x") )
print text

and produces the following output:

abc xxx def

Obviously not the most efficient way of replacing numeric characters in a string, but strings provide an easy way to demonstrate what an algorithm is doing. The process is similar for working with UDT type elements, as the following code uses ext.Transform to modify a range ofPerson objects, and ext.ForEach to output them:

# include once "ext/algorithms/transform.bi"
# include once "ext/algorithms/foreach.bi"

type
Person
    name
as zstring ptr
    age
as ubyte
    ismale
as integer
end type

sub OutputPerson ( byref p as Person )
   
var result = "( " & *p.name
    result
&= ", " & p.age
    result
&= ", " & *iif( p.ismale, @"male )", @"female )" )
   
print result
end sub

function ChangeGender ( byref p as Person ) as Person
   
var tmp = p
    tmp
.ismale = not tmp.ismale
   
return tmp
end function

fbext_Instanciate
( fbext_ForEach, ((Person)) )
fbext_Instanciate
( fbext_Transform, ((Person)) )

const N = 5
dim people
(1 to N) as Person = _
{ _
   
( @"John", 34, -1 ), _
   
( @"Jacob", 12, -1 ), _
   
( @"Jennifer", 24, 0 ), _
   
( @"Joseph", 55, -1 ), _
   
( @"Jasmine", 18, 0 ) _
}

ext
.ForEach( @people(1), @people(1) + N, @OutputPerson )
ext
.Transform( @people(1), @people(1) + N, @people(1), @ChangeGender )
ext
.ForEach( @people(1), @people(1) + N, @OutputPerson )

The fbext_Instanciate( ..., ((Person)) ) lines are part of the Ext Template Library covered by it's own tutorial here. For now it's enough to know that those lines make it possible for ext.Transform and ext.ForEach to work with ranges of Person elements. By default, all algorithms work with built-in numeric (such as IntegerDouble, etc.) and String elements.

Tags: