Reference - Homunculus84/Binder GitHub Wiki

Binder

Variables

Public variables of a Binder instance.

Variable Type Readonly Description
data Array True The array containing the source data
map_fn Function True Callback function passed on creation (see constructor)
index Array True Sorted index of references (array indexes) to the source data
size Integer True Size of the index

Constructor

(data, map_fn, [build])

Creates a new Binder from the provided array.

Important things to consider when creating Binder:

  • You should not change your data after building the Binder index, or if you do, remember to also rebuild the index (see Concepts in the wiki homepage)
  • Building the index is expensive, especially on large datasets. Consider building the index on the first game run and storing it to file, or even better, ship the game with a pre-built index
Argument Type Description
data Array The array containing the source data
map_fn Function Callback function that takes an item from your array and returns the value to index / sort by
[build] Boolean Whether to build the sorted index at creation (true) or not (false). Default: false

Returns: Binder

Example:

dictionary = [
    {word: "binary", score: 4},
    {word: "search", score: 7},
]

// Creates a Binder with the dictionary entries sorted (and searchable) by word
word_binder = new Binder(dictionary, function(_entry) { return _entry.word; });

// Creates a Binder with the dictionary entries sorted (and searchable) by word
score_binder = new Binder(items, function(_entry) { return _entry.score; });

.build_index

()

Generates (or re-generates) the sorted index of your data for this Binder.

Returns: N/A

Example:

word_binder = new Binder(dictionary, function(_entry) { return _entry.word; });
word_binder.build_index();

.find

(value, [map_value], [eval_fn])

Performs a binary search for a single value on a Binder, returning the value if found, or undefined otherwise.

This function works exactly like .search(), but returns the first matching result directly instead of a BinderResult. Please refer to that function for details.

Argument Type Description
value Any The value to search for
[map_value] Boolean Wheter to transform the value based on the map_fn of the Binder (true) or not (false). Default: false
[eval_fn] Function Transformation function to apply to the entries

Returns: Any

Example:

fruits = ["Mango", "Apple", "Papaya", "Pear", "Kiwi", "Orange", "Banana", "Peach"];

// Creates a Binder for fruits sorted by lower case name, and builds the index
fruits_alpha = new Binder(fruits, function(_fruit) { return string_lower(_fruit); }, true);

// Look for "apple"
var _result = fruits_alpha.find("apple");

if(is_undefined(_result)) {
    show_debug_message("Not found!");
} 
else {
    show_debug_message($"{_result} found!");
}

.from_buffer

(buffer)

Loads the Binder from a pre-built index stored in a buffer (as result of to_buffer()). Returns true if successful, false otherwise.

This function will not destroy the buffer, just load its contents into the Binder.

Argument Type Description
buffer Buffer Buffer containing the binder data

Returns: Boolean

.from_json

(json_string)

Loads the Binder index from a pre-built index stored as JSON string (using to_json()). Returns true if successful, false otherwise.

Argument Type Description
json_string String JSON data as string

Returns: Boolean

Example:

// Creates a Binder indexed by word, and builds the index from a previously stored json string.

word_binder = new Binder(dictionary, function(_entry) { return _entry.word; });
word_binder.from_json(json);

.get_ref

(pos)

Returns the reference (array position) to the source data at position pos of the index.

Argument Type Description
pos Real Position in the Binder index

Returns: Real

Example:

// Gets the first dictionary entry in the Binder, and retrieves its value in the dictionary.

var _i = word_binder.get_ref(0);
var _first_entry = dictionary[_i];

.get_val

(pos)

Gets the reference at position pos in the Binder index, and returns its value from the source data, as mapped by the Binder map_fn function. In short, gets the corresponding value, and returns the result of map_fn(value).

Argument Type Description
pos Real Position in the Binder index

Returns: Any

Example:

// Gets the first entry in the Binder, and retrieves its (mapped) value in the source data.

var _word = word_binder.get_val(0);

.get_val_raw

(pos)

Gets the reference at position pos in the Binder index, and returns its raw (unmodified by map_fn) value from the source data.

Argument Type Description
pos Real Position in the Binder index

Returns: Any

Example:

// Gets the first dictionary entry in the Binder, and retrieves its raw value in the dictionary.

var _entry = word_binder.get_val_raw(0);

.is_built

Returns whether the index is built (true) or not (false)

Returns: Boolean

.load

(filename)

Synchronously load Binder index in the specified file (as saved from save()).

Please consider that on console platforms synchronous saving and loading should not be used. Instead, you should provide your own async load by using the result of to_json() and from_json() or to_buffer() and from_buffer().

Returns whether the loading was successful.

Argument Type Description
filename String Name and path of the file to load from, incl. extension

Returns: Boolean

Example:

// Creates a new Binder (without building it), and loads the index from file
word_binder = new Binder(dictionary, function(_entry) { return _entry.word; }, false);
word_binder.load("words_binder.json");

.save

(filename)

Synchronously save a Binder index in the specified file.

Please consider that on console platforms synchronous saving and loading should not be used. Instead, you should provide your own async load by using the result of to_json() and from_json() or to_buffer() and from_buffer().

Argument Type Description
filename String Name and path of the file to save to, incl. extension

Returns: N/A

Example:

// Creates (and builds) a new Binder, and saves it to file
word_binder = new Binder(dictionary, function(_entry) { return _entry.word; }, true);
word_binder.save("words_binder.json");

.search

(value, [map_value], [eval_fn])

Performs a search for multiple values on a Binder, returning a BinderResult instance with the entries that match the provided value.

By default, the value is passed as-is to the search function, meaning that if your Binder has been indexed (in the case of a words array for example) by string_length, you should pass a number representing the string length you are searching for.

Alternatively, you may tell the search function to apply the same transformation (map_fn) of the Binder to the value by setting map_value to true.

Lastly, you may pass a function (eval_fn) that further transforms the entries before comparing them to the value. This is useful for example when looking for prefixes in a list of strings, by extracting only the first N characters of the entries for comparison.

Note that _eval_fn may not fundamentally change the natural order of the entries in the index, value < > entry should produce the same result as value < > eval_fn(entry) .

Argument Type Description
value Any The value to search for
[map_value] Boolean Wheter to transform the value based on the map_fn of the Binder (true) or not (false). Default: false
[eval_fn] Function Transformation function to apply to the entries

Returns: BinderResult

Example:

fruits = ["Mango", "Apple", "Papaya", "Pear", "Kiwi", "Orange", "Banana", "Peach"];

// Creates a Binder of fruits sorted by lower case name, and builds the index
fruits_alpha = new Binder(fruits, function(_fruit) { return string_lower(_fruit); }, true);

// Creates a Binder of fruits sorted by the number of letters in the name
// Note: string_length already takes a single string and returns the char count, so we can pass the function directly
fruits_length = new Binder(fruits, string_length, true);

// Search for all fruits with 5 letters
var _result1 = fruits_length.search(5);

// Search for a specific fruit
var _result2 = fruits_alpha.search("Kiwi");

// Search for all fruits that start with "Pe"
var _result3 = fruits_alpha.search("Pe", true, function(_fruit) {
    return string_copy(_fruit, 1, 2);
});

.to_buffer

Returns a new buffer with a binary representation of a Binder. Can be loaded afterwards in an existing binder using from_buffer().

Returns: Buffer

.to_json

([pretty])

Returns the Binder representation in JSON format. Can be used to rebuild a Binder later by using from_json().

Argument Type Description
[pretty] Boolean Whether to prettify the result for human readability

Returns: String

Example:

// Creates (and builds) a new Binder, and stores its json representation into a variable
word_binder = new Binder(dictionary, function(_entry) { return _entry.word; }, true);
var _json_string = word_binder.to_json();

BinderResult

Performing a binary search on a binder using .search() does not return the data directly, but instead always BinderResult struct, that exposes the following variables and methods.

Variable Type Readonly Description
binder Binder True The Binder instance that generated the search result
count Real True The total number of results found

.fetch_indexes

([limit], [offset])

Works exactly like fetch_values(), but returns the result of the search as an array of indexes to the source data array, instead of the values.

Argument Type Description
[limit] Real Limit on the number of results to fetch. -1 or less means no limit
[offset] Real Offset the returned data by the specified amount

Returns: Array

Example:

var _result = words_by_length.search(5);
var _indexes = _result.fetch_values();

// Print the amount of words found
show_debug_message($"Found {_result.count} words of length 5");

// Print each word by getting it from the original data array
for(var _i = 0; _i < array_length(_indexes); _i++) {
    var _index = _indexes[_i];
    show_debug_message(dictionary[_index]);
}

.fetch_values

([limit], [offset])

Returns the result of the search as an array of entries from your source data.

You can optionally apply a limit and an offset. This is useful especially in case of a large amount of results, since only the minimum amount of data is actually fetched from the source array and returned, speeding things up considerably.

Consider that there's no caching involved, running this function twice will fetch the data twice.

Argument Type Description
[limit] Real Limit on the number of results to fetch. -1 or less means no limit
[offset] Real Offset the returned data by the specified amount

Returns: Array

Example:

var _result = words_by_length.search(5);
var _words = _result.fetch_values();

// Print the amount of words found
show_debug_message($"Found {_result.count} words of length 5");

// Print each word
for(var _i = 0; _i < array_length(_words); _i++) {
    show_debug_message(_words[_i]);
}

Merging results

One limitation of binary search is that you can only search by one condition at a time. For example, in a dictionary, you can search for a specific word or for all words of a certain length, but not both at once.

To work around this, Binder provides two helper functions that let you combine results from different searches. This makes it possible to apply basic logic like AND (&&) or OR (||) by merging multiple BinderResult structs together.

binder_results_intersection

(result, ...results)

Given from 1 to N BinderResult structs, returns a new BinderResult where only the entries belonging to all results are kept, without duplicates.

Argument Type Description
result BinderResult Result of a search
...result BinderResult Any number of results to intersect, as separate arguments

Returns: BinderResult

Example:

fruits = ["Mango", "Apple", "Papaya", "Pear", "Kiwi", "Orange", "Banana", "Peach"];

// Generate two binder, indexed by fruit name and length
fruits_alpha = new Binder(fruits, binder_pass_through, true);
fruits_length = new Binder(fruits, string_length, true);

// Search for all fruits with 5 letters
var _result1 = fruits_length.search(5);

// Search for all fruits that start with "Pe"
var _result2 = fruits_alpha.search("Pe", true, function(_fruit) {
    return string_copy(_fruit, 1, 2);
});

// Intersect the results, returning a BinderResult with only the 5 letter words starting with "Pe"
var _result3 = binder_results_intersection(_result1, _result2);

binder_results_union

(result, ...results)

Given from 1 to N BinderResult structs, returns a new BinderResult with the entries of all results merged together and duplicates removed.

Argument Type Description
result BinderResult Result of a search
...result BinderResult Any number of results to merge, as separate arguments

Returns: BinderResult

Example:

fruits = ["Mango", "Apple", "Papaya", "Pear", "Kiwi", "Orange", "Banana", "Peach"];

// Generate two binder, indexed by fruit name and length
fruits_alpha = new Binder(fruits, binder_pass_through, true);
fruits_length = new Binder(fruits, string_length, true);

// Search for all fruits with 4 letters
var _result1 = fruits_length.search(4);

// Search for all fruits with 6 letters
var _result2 = fruits_length.search(6);

// Merge the results in a single one with all words having 5 or 8 letters
var _result3 = binder_results_union(_result1, _result2);

Helpers

binder_pass_through

(value)

Also know as identity function, this simply returns the unchanged value passed as argument.

While it may look pointless, it's nice shorthand for function(_v) { return _v; } , which can be used when creating a binder that simply indexes its element by its natural order.

Argument Type Description
value Any Value to be returned

Returns: Any

Example:

fruits = ["Mango", "Apple", "Papaya", "Pear", "Kiwi", "Orange", "Banana", "Peach"];

// Get a binder of fruits indexed in their natural (alphabetical) order
fruits_by_name = new Binder(fruits, binder_pass_through, true);

binder_string_reverse

(string)

Returns the string with its characters in reverse order. Useful for suffix searches.

Argument Type Description
string Any String to be reversed

Returns: String

Example:

fruits = ["Mango", "Apple", "Papaya", "Pear", "Kiwi", "Orange", "Banana", "Peach"];

// Get a binder of fruits indexed by their reversed order
fruits_by_reverse_name = new Binder(fruits, binder_string_reverse, true);

binder_string_sort

(string)

Returns the string with its characters sorted. This is the kind of transformation required for finding anagrams.

Argument Type Description
string Any String to be sorted

Returns: String

Example:

fruits = ["Mango", "Apple", "Papaya", "Pear", "Kiwi", "Orange", "Banana", "Peach"];

// Get a binder of fruits indexed by their characters sorted order
fruits_by_sorted_name = new Binder(fruits, binder_string_sort, true);