public enum TreePrintStyle { inOrder, postOrder, preOrder, depthOrder };
-public void strcatf(char * string, char * format, ...)
+// WARNING: This function has no boundary check!
+public void strcatf(char * string, const char * format, ...)
{
va_list args;
va_start(args, format);
{
class_fixed
public:
- uint key;
+ uintptr key;
BTNode parent, left, right;
int depth;
{
bool truth = true;
channel.Serialize(truth);
- channel.Serialize(key);
+ channel.Serialize((uint)key); // Serialize/Deserialize as 32 bit for compatibility (e.g. EDB)
channel.Serialize(left);
channel.Serialize(right);
}
{
// TODO: Fix typed_object issues
this = eInstance_New(class(BTNode));
- channel.Unserialize(key);
+ { uint k; channel.Unserialize(k); key = k; }
channel.Unserialize(left);
- if(left) { left.parent = (void *)this; }
+ if(left) { left.parent = this; }
channel.Unserialize(right);
- if(right) { right.parent = (void *)this; }
- depth = ((BTNode)(void *)this).depthProp;
+ if(right) { right.parent = this; }
+ depth = ((BTNode)this).depthProp;
}
else
this = null;
private:
void Free(void (*FreeKey)(void * key))
- {
+ {
if (left) left.Free(FreeKey);
if (right) right.Free(FreeKey);
if(FreeKey) FreeKey((void *)key);
bool Add(BinaryTree tree, BTNode node)
{
- uint newKey = node.key;
+ uintptr newKey = node.key;
while(true)
{
//int result = (newKey > key) ? 1 : ((newKey < key) ? - 1 : 0);
return false;
}
- BTNode Find(BinaryTree tree, uint key)
+ BTNode Find(BinaryTree tree, uintptr key)
{
while(this)
{
return this;
}
- public BTNode FindString(char * key)
+ public BTNode FindString(const char * key)
{
while(this)
{
int result;
if(key && this.key)
- result = strcmp(key, (char *)this.key);
+ result = strcmp(key, (const char *)this.key);
else if(key && !this.key)
result = 1;
else if(!key && this.key)
return this;
}
- BTNode FindAll(uint key)
+ public BTNode FindPrefix(const char * key)
+ {
+ BTNode subString = null;
+ int len = key ? strlen(key) : 0;
+ while(this)
+ {
+ int result;
+ if(key && this.key)
+ result = strcmp(key, (const char *)this.key);
+ else if(key && !this.key)
+ result = 1;
+ else if(!key && this.key)
+ result = -1;
+ else
+ result = 0;
+
+ if(result < 0)
+ {
+ if(!strncmp(key, (const char *)this.key, len))
+ subString = this;
+ this = left;
+ }
+ else if(result > 0)
+ this = right;
+ else
+ {
+ subString = this;
+ break;
+ }
+ }
+ return subString;
+ }
+
+ BTNode FindAll(uintptr key)
{
BTNode result = null;
if(this.key == key) result = this;
}
}
- //if(!swap.left)
+ //if(!swap.left)
{
swap.left = left;
if(left)
left.parent = swap;
}
- //if(!swap.right)
+ //if(!swap.right)
{
swap.right = right;
if (right)
return parent.Rebalance();
else
return null;
- }
+ }
BTNode RemoveSwapRight()
{
#define NUMSIZE 4
- char * Print(char * output, TreePrintStyle tps)
+ char * Print(char * output, TreePrintStyle tps)
{
switch(tps)
{
if(tps == postOrder) strcatf(output, "%d ", key);
- return output;
+ return output;
}
case depthOrder:
{
return null;
}
- void PrintDepth(char * output, int wantedDepth, int curDepth, int maxDepth, bool last)
+ void PrintDepth(char * output, int wantedDepth, int curDepth, int maxDepth, bool last)
{
int c;
if(wantedDepth == curDepth)
int len;
if(this)
- sprintf(nodeString, "%d", key);
+ sprintf(nodeString, "%d", (int)key);
len = strlen(nodeString);
for(c = 0; c<(NUMSIZE - len)/2; c++)
{
if(left.parent != this)
{
- printf("Parent not set properly at node %d\n", left.key);
+ printf("Parent not set properly at node %d\n", (int)left.key);
valid = false;
}
valid *= left.Check(tree);
{
if(right.parent != this)
{
- printf("Parent not set properly at node %d\n", right.key);
+ printf("Parent not set properly at node %d\n", (int)right.key);
valid = false;
}
valid *= right.Check(tree);
if(depth != depthProp)
{
- printf("Depth value at node %d (%d) doesn't match depth property (%d)\n", key, depth, depthProp);
+ printf("Depth value at node %d (%d) doesn't match depth property (%d)\n", (int)key, depth, depthProp);
valid = 0;
}
if (diffHeight < -1 || diffHeight > 1)
{
valid = 0;
- printf("Height difference is %d at node %d\n", diffHeight, key);
+ printf("Height difference is %d at node %d\n", diffHeight, (int)key);
}
// Verify that balance-factor is correct
if (diffHeight != balanceFactor)
{
valid = 0;
- printf("Height difference %d doesnt match balance-factor of %d at node \n", diffHeight, balanceFactor, key);
+ printf("Height difference %d doesnt match balance-factor of %d at node %d\n", diffHeight, balanceFactor, (int)key);
}
// Verify that search-tree property is satisfied
if (left && tree.CompareKey(tree, left.key, key) > 0)
{
valid = false;
- printf("Node %d is *smaller* than left subtree %d\n", key, left.key);
+ printf("Node %d is *smaller* than left subtree %d\n", (int)key, (int)left.key);
}
if (right && tree.CompareKey(tree, right.key, key) < 0)
{
valid = false;
- printf("Node %d is *greater* than right subtree %d\n", key, right.key);
+ printf("Node %d is *greater* than right subtree %d\n", (int)key, (int)right.key);
}
return valid;
}
};
-// TODO: WHY CAN'T WE HAVE THIS ABOVE?
-
public class StringBTNode : struct // BTNode
{
class_fixed
channel.Unserialize(truth);
if(truth)
{
- // TODO: Fix typed_object issues
- this = eInstance_New(class(StringBTNode));
+ this = { };
channel.Unserialize(key);
channel.Unserialize(left);
- if(left) { left.parent = (void *)this; }
+ if(left) { left.parent = this; }
channel.Unserialize(right);
- if(right) { right.parent = (void *)this; }
+ if(right) { right.parent = this; }
- // TODO: Precomp errors without extra brackets
- depth = ((BTNode)((void *)this)).depthProp;
+ depth = ((BTNode)this).depthProp;
}
else
this = null;