Routines in array.bast

Size, Capacity, IsEmpty, Append, Insert, Erase, Remove, RemoveIf, Resize, Clear, ClearUnused, ShrinkToFit, Unique, Copy, IncreaseCapacity, ReplaceRange

Routines in algo.bast

All, Any, Iif, InList, BinaryFind, BinaryFindFirst, BinaryFindLast, LowerBound, UpperBound, Count, CountIf, Fill, Find, FindIf, ForEach, Transform, InsertionSort, IsSorted, Max?, Min?, MinItem, MaxItem, PrintArray, PrintIf, QSort, Random, Replace, ReplaceIf, Reverse, Shuffle, Swap

Comparison functions

Overview
Ascending, Descending, IgnoreCaseAsc, IgnoreCaseDesc, iEquals, StartsWith, iStartsWith, EndsWith, iEndsWith, InRange

String algorithms

Split, Join, Replace, AlignCenter, AlignLeft, AlignRight, BuildString, FormatString, FindLast, FindFirstOf, FindFirstNotOf, FindLastOf, FindLastNotOf, WrapLeft, WrapRight, WrapCenter

Heap routines

HeapTop, InsertToHeap, RemoveFromHeap, HeapSort, MakeHeap, IsHeap

Dictionary

Dict.Insert, Dict.Erase, Dict.GetValue

Routines in array.bast

This file contains routines that are primarily meant to manipulate arrays created with the CREATE_ARRAY macro.

The first three arguments are always ARRAY_NAME and two numeric parameters (size and capacity), and therefore you can simply only use the special array's name when calling these routines (this will automatically expand into the three correct arguments. E.g:


CREATE_ARRAY names$(10) = "One", "Two"

print Size(names$) 'Should print 2

function Size(ARRAY_NAME array?, size, capacity)

returns how many elements array? contains. For example, use the return value to loop over all the items in the array:


CREATE_ARRAY names$()

'fill names$ with values

for i = 1 to Size(names$)

    print names$(i)

next i

function Capacity(ARRAY_NAME array?, size, capacity)

returns how many elements the array can currently hold (this function shouldn't normally be needed because usually indices beyond Size won't be accessed).

function IsEmpty(ARRAY_NAME array?, size, capacity)

This function returns non-zero if the Size of array? is 0.





sub Append ARRAY_NAME array?, byref size, byref capacity, value?

adds an item value? to the end of array?, resizing its capacity if needed.



function Insert(ARRAY_NAME array?, byref size, byref capacity, value?, position)

inserts value? at index position, moving all following items up. If position is larger than size + 1, value will not be inserted and the function returns 0. Otherwise the function returns non-zero to indicate that insertion occurred.



function Erase(ARRAY_NAME array?, byref size, capacity, position)

removes the item at index position and moves all the following items down. Returns non-zero if position is in range, and zero otherwise. 
This function – like most routines that remove items from the array – will not overwrite items at indices beyond size. To set the unused items to 0 or empty string (necessary if the array is used in a combobox or a listbox), call ClearUnused.



sub Remove ARRAY_NAME array?, byref size, capacity, value?

sub Remove ARRAY_NAME array?, byref size, capacity, value?, FUNC_NAME equal

The first version removes all items that are equal to value? from the array.
The second version removes all items that are equal to value? using a function to compare for equality. The function equal takes two arguments and returns non-zero if the arguments should be considered equal. For example,

call Remove codelines$, "rem ", FUNC_NAME IStartsWith

 

function IStartsWith(what$, with$)

    if lower$(left$(what$, len(with$))) = lower$(with$) then IStartsWith = 1

end function




sub RemoveIf ARRAY_NAME array?, byref size, capacity, FUNC_NAME condition

passes all items of array?, one by one, to function condition and removes items for which the supplied function returns zero.



sub Resize ARRAY_NAME array?, byref size, byref capacity, newsize

sub Resize ARRAY_NAME array?, byref size, byref capacity, newsize, fillvalue?

Sets a new size for the array. If new size is larger than old size then the first version will make added items equal to 0 or empty string, the second version assigns fillvalue? to added items.



sub Clear ARRAY_NAME array?, byref size, capacity

sets the size of array? to zero.



sub ClearUnused ARRAY_NAME array?, size, capacity

sets the value of all items from size + 1 to capacity equal to 0 or empty string. (When items are removed from the array, the value of size is reduced but the items beyond size may not be overwritten.)
Clearing unused items shouldn't mostly be needed, unless the array is used for a listbox or a combobox.



sub ShrinkToFit ARRAY_NAME array?, size, byref capacity

resizes the array so that size equals capacity.



sub Unique ARRAY_NAME array?, byref size, capacity

sub Unique ARRAY_NAME array?, byref size, capacity, FUNC_NAME LessThan

removes duplicate items from a sorted array.
The second version accepts a function that takes two arguments and returns non-zero if the first argument should be ordered before the second argument. (The array should be in sorted in the same order. For example, if the array is sorted in ascending order, LessThan shouldn't be a function that defines descending order.)



sub Copy ARRAY_NAME from?, fromsize, fromcapacity, ARRAY_NAME into?, byref intosize, byref intocapacity

copies the contents of from? over to into?, resizing the destination as needed.



sub IncreaseCapacity ARRAY_NAME array?, size, byref capacity, newcapacity

mainly a helper function for Append and Insert. Redim's the array to newcapacity.




sub ReplaceRange ARRAY_NAME into?, byref size, byref capacity, Start, Finish, DYNAMIC_ARRAY with?
used for replacing part of an array into? (from Start to Finish) with the contents of another array (with?).
For example, the following code replaces contents of array a between indices 2 and 5 with the contents of array b. (Note that the replament array does not need to have the same length as the range to be replaced.)

create_array a() = 1, 2, 3, 4, 5, 6, 7, 8, 9

create_array b() = 12, 13, 14



call ReplaceRange a, 2, 5, b

'produces the sequence: 1, 12, 13, 14, 6, 7, 8, 9


This routine can also be used for other tasks.
It can be used to insert the contents of another array into the target array. If the value of Finish is one less than Start the array is inserted before the index Start.

'insert before the 5th item in a

call ReplaceRange a, 5, 4, b

'produces the sequence: 1, 2, 3, 4, 12, 13, 14, 5, 6, 7, 8, 9


Similarly the contents can be inserted to the beginning or end of the array (prepending and appending):

'prepend a with b

call ReplaceRange a, 1, 0, b

'produces the sequence: 12, 13, 14, 1, 2, 3, 4, 5, 6, 7, 8, 9



'append a with b

call ReplaceRange a, Size(a)+1, Size(a), b

'produces the sequence: 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14


By replacing a range with an empty array, it is also possible to clear these items:

create_array a() = 1, 2, 3, 4, 5, 6, 7, 8, 9

create_array empty()



'remove items 4, 5 and 6 by replacing them with an empty array

call ReplaceRange a, 4, 6, empty

'produces the sequence: 1, 2, 3, 7, 8, 9



   
 


Routines in algo.bast

While "array.bast" contains routines that modify the size or capacity of an array, "algo.bast" has routines that don't do that, and therefore are usually called on a range (the algorithms are applied to items between Start and Finish.
To apply these routines to arrays declared with CREATE_ARRAY, use ARRAY_NAME to obtain only the name of these arrays and the Size() function to get the last valid index.
For example, this is how you might sort the whole array names:


CREATE_ARRAY names$()

'Fill names$() with values

'and quicksort it

call QSort ARRAY_NAME names$, 1, Size(names$)





function All(ARRAY_NAME array?, Start, Finish, value?)

function All(ARRAY_NAME array?, Start, Finish, FUNC_NAME condition)



The first version returns non-zero if all items in array? are equal to value?.
The second version passes each item in array? to function condition and returns non-zero if condition returned non-zero every time.




function Any(ARRAY_NAME array?, Start, Finish, value?)

function Any(ARRAY_NAME array?, Start, Finish, FUNC_NAME condition)



The first version returns non-zero if at least one item in array? is equal to value?.
The second version passes each item in array? to function condition and returns non-zero if condition returned non-zero for at least one item.
Note: there is no "None" algorithm, since None would be simply Not(Any).





function Iif?(Condition?, IfTrue?, IfFalse?)

This function returns IfTrue? if Condition? is non-zero (or not an empty string), otherwise it returns IfFalse?.





function InList(what?, VAR_ARGUMENTS list?)

function InList(what?, FUNC_NAME equal, VAR_ARGUMENTS list?)

returns non-zero if what? is equal to any of the variable number of arguments in list?
The second version is similar but takes a function to compare two items for equality.



function BinaryFind(ARRAY_NAME array?, Start, Finish, value?)


function BinaryFind(ARRAY_NAME array?, Start, Finish, value?, FUNC_NAME LessThan)


finds value? in a sorted array between Start and Finish and returns the index of a found value or -1 if value does not exist in array.
The second version accepts a function that describes the sorting ordering. 
NB! BinaryFind, as well as the related functions (BinaryFindFirst, BinaryFindLast, LowerBound and UpperBound) will only work if the array is sorted (and if the sorting order is the same as defined by LessThan). To search unsorted arrays, use Find and FindIf.




function BinaryFindFirst(ARRAY_NAME array?, Start, Finish, value?)

function BinaryFindFirst(ARRAY_NAME array?, Start, Finish, value?, FUNC_NAME LessThan)



Like BinaryFind, except they return the lowest index where value? is found.




function BinaryFindLast(ARRAY_NAME array?, Start, Finish, value?)

function BinaryFindLast(ARRAY_NAME array?, Start, Finish, value?, FUNC_NAME LessThan)


Like BinaryFind, except they return the highest index where value? is found.




function LowerBound(ARRAY_NAME array?, Start, Finish, value?)

function LowerBound(ARRAY_NAME array?, Start, Finish, value?, FUNC_NAME LessThan)


finds the smallest index in a sorted array where value? could be inserted while keeping the array sorted. The second version accepts a function that determines how values are compared.




function UpperBound(ARRAY_NAME array?, Start, Finish, value?)

function UpperBound(ARRAY_NAME array?, Start, Finish, value?, FUNC_NAME LessThan)


Like LowerBound, except returns the largest index where value? could be inserted in a sorted array.




function Count(ARRAY_NAME array?, Start, Finish, value?)

function Count(ARRAY_NAME array?, Start, Finish, value?, FUNC_NAME equal)

returns the number of items in array that are equal to value.

The second version uses function equal to compare the items.

function CountIf(ARRAY_NAME array?, Start, Finish, FUNC_NAME condition)

returns the number of items in array, for which the function condition returns non-zero.

sub Fill(ARRAY_NAME array?, Start, Finish, value?)

sub Fill(ARRAY_NAME array?, Start, Finish, FUNC_NAME func?)


The first version assigns value? to all items in the array from Start to Finish.

The second version assigns the return value of function func?. This function takes no arguments. For example, this is a way to fill an array with random numbers:



call Fill ARRAY_NAME numbers, 1, NumberCount, FUNC_NAME rnd(1)




function Find(ARRAY_NAME array?, Start, Finish, value?)

function Find(ARRAY_NAME array?, Start, Finish, value?, FUNC_NAME equal)


returns the index where value was first found in an unsorted array or -1 if not found. (For sorted arrays, BinaryFind may be more efficient.)
The second version uses function equal to compare items.




function FindIf(ARRAY_NAME array?, Start, Finish, FUNC_NAME condition)


returns the index of the first item for which the function condition returns non-zero, or -1 if such item was not found.




sub ForEach ARRAY_NAME array?, Start, Finish, FUNC_NAME func?


passes each item in array? to the user-supplied function (func?) and returns the return value.



sub Transform ARRAY_NAME array?, Start, Finish, FUNC_NAME func?


passes each item in array? to user-supplied function func? and assigns the returned value back to the array item.
For example, this is how you could modify each item of the array numbers to contain the square roots of the previous values.


call Transform ARRAY_NAME numbers, 1, size, FUNC_NAME sqr()




sub InsertionSort ARRAY_NAME array?, Start, Finish

sub InsertionSort ARRAY_NAME array?, Start, Finish, FUNC_NAME LessThan


A sorting routine for small arrays (up to a few dozen elements), mainly included as an optimization for QSort routines.

The second takes a function that takes two arguments and should return non-zero, if the first argument should be ordered before the second. 




sub IsSorted ARRAY_NAME array?, Start, Finish

sub IsSorted ARRAY_NAME array?, Start, Finish, FUNC_NAME order

The first version returns non-zero if the array is in sorted ascending order.
The second version uses passed function to check for ordering.



function Max?(a?, b?)


returns the larger of the two values.




function Min?(a?, b?)


returns the smaller of the two values




function MinItem(ARRAY_NAME array?, Start, Finish)

function MinItem(ARRAY_NAME array?, Start, Finish, FUNC_NAME LessThan)


returns the index of the smallest value in an unsorted array.
The second version lets you specify the sorting order.




function MaxItem(ARRAY_NAME array?, Start, Finish)

function MaxItem(ARRAY_NAME array?, Start, Finish, FUNC_NAME LessThan)


returns the index of the largest value in an unsorted array.
The second version lets you specify the sorting order.




sub PrintArray ARRAY_NAME array?, Start, Finish, delimiter$

prints the array, using delimiter between array items.




sub PrintIf ARRAY_NAME array?, Start, Finish, delimiter$, FUNC_NAME condition

similar to PrintArray except prints only those items for which the function condition returns non-zero.




sub QSort ARRAY_NAME array?, Start, Finish

sub QSort ARRAY_NAME array?, Start, Finish, FUNC_NAME LessThan


more efficient sort routines for larger arrays than InsertionSort.
The second version accepts a function that takes two arguments, and returns non-zero if the first argument should come before the second. 




function Random(Min, Max?)


returns a random integer in range Min to Max.




sub Replace ARRAY_NAME array?, Start, Finish, old?, new?

sub Replace ARRAY_NAME array?, Start, Finish, old?, new?, FUNC_NAME equal


replaces all items between Start and Finish that are equal to old? with new?.
The second version uses the user-supplied function two compare array items and old? for equality.




sub ReplaceIf ARRAY_NAME array?, Start, Finish, FUNC_NAME condition, new?


passes each item in array to function condition and replaces it with new? if the function returns non-zero.




sub Reverse ARRAY_NAME array?, Start, Finish


reverses the array contents between Start and Finish.




sub Shuffle ARRAY_NAME array?, Start, Finish


randomly mixes up the ordering of the items between Start and Finish.




sub Swap byref a?, byref b?


swaps the two arguments.
NB! Due to a peculiarity of JustBasic, this routine only works if the passed arguments are plain variables. This routine cannot swap array items.


 

Comparison functions
Overview

The files array.bast and algo.bast contain several routines that accept a user-defined function that modifies the routines' behaviour. These functions are of three types:


conditions – these functions accept a single argument and return non-zero if the condition is true for the argument, and zero if false;
equality functions - these functions accept two arguments and return non-zero if the two supplied values should be considered equal;
ordering functions - these are used to define the ordering of array elements and are used by sorting routines (such as QSort), or routines that expect a sorted array (such as BinaryFind or Unique). These functions take two arguments and should return non-zero if the first argument should come before the second in the sorted array.

JBExtensions, however, allows to use any number of additional arguments with these functions, as long as the first (two) argument(s) are the same as the routine assumes. See the tutorial.

Some comparison functions are already provided in the file "predicates.bast".



function Ascending(a?, b?)


defines the normal ascending order.
This function is only included for completeness, as the simple versions of routines already sort in / assume ascending order.




function Descending(a?, b?)


defines the descending order. Reverse of Ascending




function IgnoreCaseAsc(a$, b$)


defines case insensitive ascending order for strings.




function IgnoreCaseDesc(a$, b$)


defines case insensitive descending order for strings.




function iEquals(a$, b$)


case insensitive comparison for equality of two strings.




function StartsWith(what$, with$)


returns non-zero if the string what$ begins with the string with$.
Note that StartsWith is not symmetrical, i.e. the order of arguments matters. Routines in array.bast and algo.bast, for which the equality predicates are relevant (such as Remove or Find), always pass the array item as the first argument and the user-provided value to compare against as the second argument.




function iStartsWith(what$, with$)


case insensitive version of StartsWith.




function EndsWith(what$, with$)


returns non-zero if the string what$ ends with the string with$




function iEndsWith(what$, with$)


case insensitive version of EndsWith.




function InRange(what?, min?, max?)


returns 1 if what? is in range min? to max? inclusive and 0 otherwise.


 

String algorithms
Import string_algo.bast to use the following string functions.



sub Split string$, DYNAMIC_ARRAY list$, delimiter$, ignoreEmpty

sub Split string$, DYNAMIC_ARRAY list$, delimiter$

sub Split string$, DYNAMIC_ARRAY list$


Splits the string and stores the substrings in the provided dynamic array.
The first version lets you specify the delimiter sequence as well as choose whether empty substrings (where delimiters follow each other) should be discarded or not.
The second version ignores empty substrings by default.
The third version splits the string at any kind of whitespace.




function Join$(DYNAMIC_ARRAY list$, delimiter$)

Joins all the strings in list$ into a single string, using delimiter$ as a separator between the substrings.




function Replace$(string$, old$, new$)

Replaces all occurrences of substring old$ with new$ in string$.




function AlignCenter$(string$, width)

function AlignCenter$(string$, width, padding$)

function AlignRight$(string$, width)

function AlignRight$(string$, width, padding$)

function AlignLeft$(string$, width)

function AlignLeft$(string$, width, padding$)


A group of functions to pad string$ from the left, right or both ends, so that its length is at least width. By default the strings are padded with spaces.




function BuildString$(what$, n)

Returns a string consisting of string what$ repeated n times.




function FormatString$(format$, VAR_ARGUMENTS args?)

Returns a string combined of any number of values that are formatted according to the format string.
Placeholder begins with "%"
followed optionally by "<" - align left, "=" - align center, ">" - align right (the default is align right)
followed optionally by a number showing minimum field width (alignment has no effect if this is omitted)
followed optionally by "." and a number showing how many decimal places to print
followed by "n" or "s" which ends the placeholder (use n for numeric values and s for strings, although this is not checked)

Example:

print FormatString$("%s, %s!", "Hello", "world")

'==> Hello, world!

print FormatString$("'%=6s' '%7.2n'", "Mark", 34.231)

'==> ' Mark ' '  34.23'


To print a % symbol in the string, escape it by placing another % in front of it.
The format string must contain the same number of placeholders as arguments to the function.




function FindLast(s$, substring$)

function FindLast(s$, substring$, lastPos)

Similar to the built-in Instr function, except returns the place of the last occurrence of substring.




function FindFirstOf(s$, what$)

function FindFirstNotOf(s$, what$)

function FindLastOf(s$, what$)

function FindLastNotOf(s$, what$)

function FindFirstOf(s$, what$, startPos)

function FindFirstNotOf(s$, what$, startPos)

function FindLastOf(s$, what$, lastPos)

function FindLastNotOf(s$, what$, lastPos)


Returns the first/last position in string s$ where any of the characters in what$ is either found or not found. 




function WrapLeft$(text$, width)

function WrapRight$(text$, width)

function WrapCenter$(text$, width)


Inserts linebreaks into the string so that each line is no longer than width character. Each version positions the lines differently.



 

CountingSort.bast
Import this file to use the CountingSort routine.



sub CountingSort ARRAY_NAME array, Start, Finish, MinValue, MaxValue
Very fast sorting routine for numeric arrays which contains integral values in a limited range, from MinValue to MaxValue (these can be found with the MinItem and MaxItem functions).
 

QSort2D.bast

This file contains quicksort routines for two-dimensional arrays which sorts the array according to the selected column.


sub QSort2D ARRAY_NAME array2d?, Height, Width, ByCol

sub QSort2D ARRAY_NAME array2d?, Height, Width, ByCol, FUNC_NAME LessThan

 



Heap routines
A heap is a data structure that is in a particular order where the parent node is smaller (or larger) than its two child nodes. The smallest (largest) item is always on the top (at array index 1) and routines that add and remove items must keep this order. Read more from the Wikipedia article.
A heap is a suitable data structure for implementing a priority queue where items are enlisted (pushed) in any order and then removed (popped) one by one in the order of priority. The "Examples" folder contains a demo program "HeapTest.bast" which stores jobs in a heap sorted by date and displays them one by one.
IMPORT heap.bast to use the following routines. Note, all these functions expect the array to be created with CREATE_ARRAY macro.
Note: these functions have two versions. By default they implement a min-heap, but you can also (consistently) pass the comparison function to change that, e.g Descending to obtain a max-heap ordering.




function HeapTop?(DYNAMIC_ARRAY array?)

returns the top item in the heap but doesn't remove it. Before calling this function make sure that array? is not empty (with Size or IsEmpty functions in "array.bast").




sub InsertToHeap DYNAMIC_ARRAY array?, value?

sub InsertToHeap DYNAMIC_ARRAY array?, value?, FUNC_NAME order)


Inserts (pushes) value? into the heap array? (using order to compare values).




sub RemoveFromHeap DYNAMIC_ARRAY array?

sub RemoveFromHeap DYNAMIC_ARRAY array?, value?, FUNC_NAME order 


Removes (pops) the top value from the heap array? (using order to compare values). Before calling this routine make sure that the array is not empty.




sub HeapSort DYNAMIC_ARRAY array?

sub HeapSort DYNAMIC_ARRAY array?, FUNC_NAME order


sorts an unordered array using the heap-sort algorithm.




sub MakeHeap DYNAMIC_ARRAY array?

sub MakeHeap DYNAMIC_ARRAY array?, FUNC_NAME order


rearranges an unordered array into a heap structure.




function IsHeap(DYNAMIC_ARRAY array?)

function IsHeap(DYNAMIC_ARRAY array?, FUNC_NAME order)


returns whether the contents of the array make up a heap or not.

 

Dictionary
A dictionary lets you associate string keys (the key$ parameter) with string or numeric values and look up the values according to the key. The effect is somewhat similar to an array where the indices are strings instead of numbers.
Import the file dict.bast to use the following routines. These routines expect that the array to store the dictionary is created with the CREATE_ARRAY extension.




sub Dict.Insert DYNAMIC_ARRAY dict$, key$, value?

Add a new key-value pair to the dictionary. If the key already exists in the dictionary, the value will be replaced.




sub Dict.Erase DYNAMIC_ARRAY dict$, key$

Remove the entry corresponding to key$ from the dictionary.




function Dict.GetValue?(DYNAMIC_ARRAY dict$, key$, byref success)

Function returns the value corresponding to the key. The success parameter indicates whether the key existed in the dictionary or not. The value can be retrieved as a string or a number, but it is up to the user to know how the value is supposed to be interpreted.

 

Type conversions
The types.bast contains routines to perform arbitrary conversions between string or numeric types. It is useful in situations where (one of) the types are not known at the time of writing the code, and therefore it is unknown whether the str$( function is required or whether no conversion should occur.
The file contains two different ways. The first uses a more convenient function-call syntax. However, it relies on the second sub version to get the job done, and using it leads to more routines being generated.
NB! Since version 1.5 of JBExtensions, it is preferable to use the TYPE_ keyword instead of the following routines.




function ConvertTo?(what?)



sub asTypeOf byref into?, what?

Contents

Routines in array.bast

Routines in algo.bast

Comparison functions

Overview

String algorithms

CountingSort.bast

Heap routines

Dictionary

Type conversions