/*----------------------------------------------------------------------------*-YAdmin system - Binary Tree CoreProvides functions to generate balanced binary search trees for efficientsearching of large arrays by value. Left branch is less than, right branchis greater than or equal to for multiple matching values.Changelog:24/03/07:First version.-*----------------------------------------------------------------------------*/#define BINTREE_NO_BRANCH -1#define BINTREE_NOT_FOUND -1enum E_BINTREE_TREE{ E_BINTREE_TREE_VALUE, E_BINTREE_TREE_LEFT, E_BINTREE_TREE_RIGHT, E_BINTREE_TREE_PARENT, E_BINTREE_TREE_POINTER}enum E_BINTREE_INPUT{ E_BINTREE_INPUT_VALUE, E_BINTREE_INPUT_POINTER}/*----------------------------------------------------------------------------*-Function: Bintree_SortParams: input[][E_BINTREE_INPUT] - Data to sort. size - Size of data to sort.Return: -Notes: Entry point for Bintree_QSort.-*----------------------------------------------------------------------------*/#define Bintree_Sort(%1,%2) \ Bintree_QSort((%1), 0, (%2) - 1)/*----------------------------------------------------------------------------*-Function: Bintree_FillParams: Bintree:output[][E_BINTREE_TREE] - Destination for balanced tree. data[][E_BINTREE_INPUT] - Source data. size - Size of data.Return: Bintree_SortHalf.Notes: Entry point for Bintree_SortHalf.-*----------------------------------------------------------------------------*/#define Bintree_Fill(%1,%2,%3) \ Bintree_SortHalf((%1), (%2), 0, (%3), 0, BINTREE_NO_BRANCH)/*----------------------------------------------------------------------------*-Function: Bintree_GenerateParams: Bintree:output[][E_BINTREE_TREE] - Binary tree to store the data in. input[][E_BINTREE_INPUT] - Input data to get the data from. size - Number of items to sort.Return: -Notes: Just calls the sort and fill routines.-*----------------------------------------------------------------------------*/Bintree_Generate(Bintree:output[][E_BINTREE_TREE], input[][E_BINTREE_INPUT], size){ Bintree_Sort(input, size); Bintree_Fill(output, input, size); return 1;}/*----------------------------------------------------------------------------*-Function: Bintree_ResetParams: Bintree:tree[][E_BINTREE_TREE] - Array to reset. size - Size of array.Return: -Notes: Initialises the array for use.-*----------------------------------------------------------------------------*/Bintree_Reset(Bintree:tree[][E_BINTREE_TREE], pointer = 0){ tree[pointer][E_BINTREE_TREE_VALUE] = 0; tree[pointer][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH; tree[pointer][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH; tree[pointer][E_BINTREE_TREE_PARENT] = BINTREE_NO_BRANCH; tree[pointer][E_BINTREE_TREE_POINTER] = BINTREE_NOT_FOUND;}/*----------------------------------------------------------------------------*-Function: Bintree_FindValueParams: Bintree:tree[][E_BINTREE_TREE] - Tree to find the data in. value - Value to search for. &cont - Start point.Return: -Notes: Itterates through the array following the various paths till it locates the value provided or reaches a dead end. If the current value is greater than the search value, the search goes left, otherwise right. If cont is not -1 the search will start from the data pointed to by the data pointed to by conts' right path, this is to allow collisions to be passed over if you want a subsequent one.-*----------------------------------------------------------------------------*/Bintree_FindValue(Bintree:tree[][E_BINTREE_TREE], value, &cont = 0, &old = 0){ new treeValue; while (cont != BINTREE_NO_BRANCH) { old = cont; treeValue = tree[old][E_BINTREE_TREE_VALUE]; printf("%d: %d = %d", value, cont, treeValue); if (value < treeValue) cont = tree[old][E_BINTREE_TREE_LEFT]; else { cont = tree[old][E_BINTREE_TREE_RIGHT]; if (value == treeValue) { return tree[old][E_BINTREE_TREE_POINTER]; } } } return BINTREE_NOT_FOUND;}/*----------------------------------------------------------------------------*-Function: Bintree_QSortParams: numbers[][E_BINTREE_INPUT] - Data to sort. left - Start index. right - End index.Return: -Notes: Custom version of QSort (see YSI_misc) allows for E_BINTREE_INPUT data types, preserving the relative pointers for the sorted data.-*----------------------------------------------------------------------------*/Bintree_QSort(numbers[][E_BINTREE_INPUT], left, right){ new pivot = numbers[left][E_BINTREE_INPUT_VALUE], pointer = numbers[left][E_BINTREE_INPUT_POINTER], l_hold = left, r_hold = right; while (left < right) { while ((numbers[right][E_BINTREE_INPUT_VALUE] >= pivot) && (left < right)) right--; if (left != right) { numbers[left][E_BINTREE_INPUT_VALUE] = numbers[right][E_BINTREE_INPUT_VALUE]; numbers[left][E_BINTREE_INPUT_POINTER] = numbers[right][E_BINTREE_INPUT_POINTER]; left++; } while ((numbers[left][E_BINTREE_INPUT_VALUE] <= pivot) && (left < right)) left++; if (left != right) { numbers[right][E_BINTREE_INPUT_VALUE] = numbers[left][E_BINTREE_INPUT_VALUE]; numbers[right][E_BINTREE_INPUT_POINTER] = numbers[left][E_BINTREE_INPUT_POINTER]; right--; } } numbers[left][E_BINTREE_INPUT_VALUE] = pivot; numbers[left][E_BINTREE_INPUT_POINTER] = pointer; pivot = left; left = l_hold; right = r_hold; if (left < pivot) Bintree_QSort(numbers, left, pivot - 1); if (right > pivot) Bintree_QSort(numbers, pivot + 1, right);}/*----------------------------------------------------------------------------*-Function: Bintree_SortHalfParams: Bintree:output[][E_BINTREE_TREE] - Destination array. data[][E_BINTREE_INPUT] - Source array. index - Start index of the source for processing. upper - End index of the source for processing. offset - Current offset in the destination array for writing.Return: Size of balanced tree.Notes: Recursively calls itself. Bisects the passed array and passed each half back to itself, with the middle value of each half being the left and right branches of the middle value of the passed array (which isn't included in either bisected half). This is itterative so those are again split and again split. If the passed array is only one or two elements big the behaviour is set and hardcoded. Equal values SHOULD branch right, the code is designed for this however the generation is not fully tested (it mostly branches right but adjacent after bisecting values haven't been tested). Based on code written for PHP by me.-*----------------------------------------------------------------------------*/Bintree_SortHalf(Bintree:output[][E_BINTREE_TREE], data[][E_BINTREE_INPUT], index, upper, offset, parent){ new num = upper - index; if (!num) return offset; if (num == 1) { output[offset][E_BINTREE_TREE_VALUE] = data[index][E_BINTREE_INPUT_VALUE]; output[offset][E_BINTREE_TREE_POINTER] = data[index][E_BINTREE_INPUT_POINTER]; output[offset][E_BINTREE_TREE_PARENT] = parent; output[offset][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH; output[offset][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH; } else if (num == 2) { output[offset][E_BINTREE_TREE_VALUE] = data[index][E_BINTREE_INPUT_VALUE]; output[offset][E_BINTREE_TREE_POINTER] = data[index][E_BINTREE_INPUT_POINTER]; output[offset][E_BINTREE_TREE_PARENT] = parent; output[offset][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH; output[offset][E_BINTREE_TREE_RIGHT] = ++offset; output[offset][E_BINTREE_TREE_VALUE] = data[++index][E_BINTREE_INPUT_VALUE]; output[offset][E_BINTREE_TREE_POINTER] = data[index][E_BINTREE_INPUT_POINTER]; output[offset][E_BINTREE_TREE_PARENT] = offset - 1; output[offset][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH; output[offset][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH; } else { new half = num / 2, off = half + index, right; while (off && data[off][E_BINTREE_INPUT_VALUE] == data[off - 1][E_BINTREE_INPUT_VALUE]) off--; right = Bintree_SortHalf(output, data, index, off, offset + 1, offset); output[offset][E_BINTREE_TREE_VALUE] = data[off][E_BINTREE_INPUT_VALUE]; output[offset][E_BINTREE_TREE_POINTER] = data[off][E_BINTREE_INPUT_POINTER]; output[offset][E_BINTREE_TREE_PARENT] = parent; output[offset][E_BINTREE_TREE_LEFT] = offset + 1; output[offset][E_BINTREE_TREE_RIGHT] = right; return Bintree_SortHalf(output, data, off + 1, upper, right, offset); } return offset + 1;}/*----------------------------------------------------------------------------*-Function: Bintree_AddParams: Bintree:data[][E_BINTREE_TREE] - Array to add to. input[][E_BINTREE_INPUT] - Data to add. offset - Location in the array to store the data. maxsize - Size of data.Return: Next free locationNotes: --*----------------------------------------------------------------------------*/Bintree_Add(Bintree:data[][E_BINTREE_TREE], input[E_BINTREE_INPUT], offset, maxsize = sizeof (data)){ if (offset >= maxsize) return BINTREE_NOT_FOUND; new leaf, old, value = input[E_BINTREE_INPUT_VALUE]; while (Bintree_FindValue(data, value, leaf, old) != BINTREE_NOT_FOUND) continue; Bintree_Reset(data, offset); if (value < data[old][E_BINTREE_TREE_VALUE]) data[old][E_BINTREE_TREE_LEFT] = offset; else data[old][E_BINTREE_TREE_RIGHT] = offset; data[offset][E_BINTREE_TREE_PARENT] = old; data[offset][E_BINTREE_TREE_VALUE] = value; data[offset][E_BINTREE_TREE_POINTER] = input[E_BINTREE_INPUT_POINTER]; return offset + 1;}/*----------------------------------------------------------------------------*-Function: Bintree_DeleteParams: Bintree:tree[][E_BINTREE_TREE] - Data. index - Index to remove. count - Number of binary tree items.Return: -Notes: The left branch is usually larger due to the division method used so we start there. Even though right is >= and left is only < in even sized arrays the greater chunk (unless there's only 2 items) goes left. Called itteratively to ensure branches are maintained.-*----------------------------------------------------------------------------*/Bintree_Delete(Bintree:source[][E_BINTREE_TREE], index, count){ new branch; if ((branch = source[index][E_BINTREE_TREE_LEFT]) != BINTREE_NO_BRANCH) branch = Bintree_FindMax(source, branch); else if ((branch = source[index][E_BINTREE_TREE_RIGHT]) != BINTREE_NO_BRANCH) branch = Bintree_FindMin(source, branch); else { if ((branch = source[index][E_BINTREE_TREE_PARENT]) != BINTREE_NO_BRANCH) { if (source[branch][E_BINTREE_TREE_LEFT] == index) source[branch][E_BINTREE_TREE_LEFT] = BINTREE_NO_BRANCH; else source[branch][E_BINTREE_TREE_RIGHT] = BINTREE_NO_BRANCH; source[index][E_BINTREE_TREE_PARENT] = BINTREE_NO_BRANCH; } return Bintree_Compress(source, index); } new value = source[index][E_BINTREE_TREE_VALUE], pointer = source[index][E_BINTREE_TREE_POINTER]; source[index][E_BINTREE_TREE_VALUE] = source[branch][E_BINTREE_TREE_VALUE]; source[index][E_BINTREE_TREE_POINTER] = source[branch][E_BINTREE_TREE_POINTER]; source[branch][E_BINTREE_TREE_VALUE] = value; source[branch][E_BINTREE_TREE_POINTER] = pointer; return Bintree_Delete(source, branch);}/*----------------------------------------------------------------------------*-Function: Bintree_CompressParams: Bintree:tree[][E_BINTREE_TREE] - Array to compress. index - Point to start at. count - Number of items total.Return: -Notes: --*----------------------------------------------------------------------------*/Bintree_Compress(Bintree:data[][E_BINTREE_TREE], index, count){ new index2 = index + 1; while (index < count) { new left = (data[index][E_BINTREE_TREE_LEFT] = data[index2][E_BINTREE_TREE_LEFT]), right = (data[index][E_BINTREE_TREE_RIGHT] = data[index2][E_BINTREE_TREE_RIGHT]), parent = (data[index][E_BINTREE_TREE_PARENT] = data[index2][E_BINTREE_TREE_PARENT]); data[index][E_BINTREE_TREE_VALUE] = data[index2][E_BINTREE_TREE_VALUE]; data[index][E_BINTREE_TREE_POINTER] = data[index2][E_BINTREE_TREE_POINTER]; if (left != BINTREE_NO_BRANCH) data[left][E_BINTREE_TREE_PARENT] = index; if (right != BINTREE_NO_BRANCH) data[right][E_BINTREE_TREE_PARENT] = index; if (parent != BINTREE_NO_BRANCH) { if (data[parent][E_BINTREE_TREE_LEFT] == index2) data[parent][E_BINTREE_TREE_LEFT] = index; else if (data[parent][E_BINTREE_TREE_RIGHT] == index2) data[parent][E_BINTREE_TREE_RIGHT] = index; } index++; index2++; } return count - 1;}/*----------------------------------------------------------------------------*-Function: Bintree_FindMinParams: Bintree:data[][E_BINTREE_TREE] - Array to search. offset - Start of branch to search.Return: -Notes: Finds the smallest value on a branch-*----------------------------------------------------------------------------*/Bintree_FindMin(Bintree:data[][E_BINTREE_TREE], offset){ new branch; while ((branch = source[offset][E_BINTREE_TREE_LEFT]) != BINTREE_NO_BRANCH) offset = branch; return offset;}/*----------------------------------------------------------------------------*-Function: Bintree_FindMaxParams: Bintree:data[][E_BINTREE_TREE] - Array to search. offset - Start of branch to search.Return: -Notes: Finds the largest value on a branch-*----------------------------------------------------------------------------*/Bintree_FindMax(Bintree:data[][E_BINTREE_TREE], offset){ new branch; while ((branch = source[offset][E_BINTREE_TREE_RIGHT]) != BINTREE_NO_BRANCH) offset = branch; return offset;}