Note

The wasBinarySearchTreeSearch function takes as arguments:

  • a binary search tree (BST) as a flattened list as per binary_trees.
  • the root of the binary search tree (root)
  • the node (node) to search for in the binary search tree.

and returns the node in the binary search tree, or the empty string otherwise.

Code

This script was tested and works on OpenSim version 0.7.5!

// Ord() function, written by Pedro Oval, 2010-05-28
// Inlined by Wizardry and Steamworks
integer Ord(string chr) {
    if (chr == "") return 0;
    string hex = llEscapeURL(chr);
    if (llGetSubString(hex, 0, 0) != "%") 
        return llBase64ToInteger("AAAA" + 
            llStringToBase64(llGetSubString(chr, 0, 0)));
    integer b = (integer)("0x" + llGetSubString(hex, 1, 2));
    if (b < 194 || b > 244) return b;
    if (b < 224) return ((b & 0x1F) << 6) | 
        (integer)("0x" + llGetSubString(hex, 4, 5)) & 0x3F;
    if (b < 240) return (b & 0x0F) << 12 + 
        ((integer)("0x" + llGetSubString(hex, 4, 5)) & 0x3F) << 6 + 
        (integer)("0x" + llGetSubString(hex, 7, 8)) & 0x3F;
    return (b & 0x07) << 18 + 
        ((integer)("0x" + llGetSubString(hex, 4, 5)) & 0x3F) << 12 + 
        ((integer)("0x" + llGetSubString(hex, 7, 8)) & 0x3F) << 6 + 
        (integer)("0x" + llGetSubString(hex, 10, 11)) & 0x3F;
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
integer wasOrdCompare(string chra, string chrb) {
    // numerical
    float fa = (float)chra;
    float fb = (float)chrb;
    if(fa != 0 && fb != 0) {
        if(fa > fb) return 1;
        if(fa < fb) return -1;
        return 0;
    }
    // lexical
    if(llStringLength(chra) == 0 && llStringLength(chrb) == 0) return 0;
    if(llStringLength(chra) && llStringLength(chrb) == 0) return 1;
    if(llStringLength(chra) == 0 && llStringLength(chrb)) return -1;
    string a = llGetSubString(chra, 0, 0);
    chra = llDeleteSubString(chra, 0, 0);
    string b = llGetSubString(chrb, 0, 0);
    chrb = llDeleteSubString(chrb, 0, 0);
    integer oa = Ord(a);
    integer ob = Ord(b);
    if(oa > ob) return 1;
    if(oa < ob) return -1;
    return wasOrdCompare(chra, chrb);
}
 
///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
string wasBinaryTreeSearch(list BST, string root, string node) {
    integer i = llListFindList(BST, (list)root);
    string pivotRoot = llList2String(BST, i);
    string left = wasBinaryTreeLeft(BST, pivotRoot);
    string right = wasBinaryTreeRight(BST, pivotRoot);
    integer compare = wasOrdCompare(node, pivotRoot);;
    if(compare > 0) {
        if(right == "") return "";
        return wasBinaryTreeSearch(BST, right, node);
    }
    if(compare < 0) {
        if(left == "") return "";
        return wasBinaryTreeSearch(BST, left, node);
    }
    return pivotRoot;
}

secondlife/binary_trees/binary_search_trees/search.txt ยท Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor


For the copyright, license, warranty and privacy terms for the usage of this website please see the license and privacy pages.