The Ecere SDK - sdk/blob - ecere/src/com/BinaryTree.ec

   1 namespace sys;
   2
   3 //#undef _DEBUG
   4
   5 import "BTNode"
   6
   7 // TODO: FIX THIS
   8 static BinaryTree dummy;
   9
  10 public struct BinaryTree
  11 {
  12    BTNode root;
  13    int count;
  14
  15    void OnSerialize(IOChannel channel)
  16    {
  17       channel.Serialize(root);
  18    }
  19
  20    void OnUnserialize(IOChannel channel)
  21    {
  22       channel.Unserialize(root);
  23       count = root ? root.count : 0;
  24    }
  25
  26    int CompareInt(uint a, uint b)
  27    {
  28       return (a > b) ? 1 : ((a < b) ? - 1 : 0);
  29    }
  30
  31    int CompareString(char * a, char * b)
  32    {
  33       return (a && b) ? strcmp(a, b) : -1;
  34    }
  35
  36    void ::FreeString(char * string)
  37    {
  38       delete string;
  39    }
  40
  41    int (*CompareKey)(BinaryTree tree, uint a, uint b);
  42    void (*FreeKey)(void * key);
  43
  44    void Free()
  45    {
  46       if(root)
  47           root.Free(FreeKey);
  48       root = null;
  49       count = 0;
  50    }
  51
  52    bool Add(BTNode node)
  53    {
  54       if(!CompareKey) CompareKey = CompareInt;
  55         if(!root)
  56                 root = node;
  57         else if(root.Add(this, node))
  58          root = node.Rebalance();
  59       else
  60                 return false;
  61         count++;
  62       // Check();
  63         return true;
  64    }
  65
  66    BTNode Find(uint key)
  67    {
  68       if(!CompareKey) CompareKey = CompareInt;
  69       // Check();
  70       return root ? root.Find(this, key) : null;
  71    }
  72
  73    BTNode FindString(char * key)
  74    {
  75       return root ? root.FindString(key) : null;
  76    }
  77
  78    BTNode FindPrefix(char * key)
  79    {
  80       return root ? root.FindPrefix(key) : null;
  81    }
  82
  83    BTNode FindAll(uint key)
  84    {
  85       return root ? root.FindAll(key) : null;
  86    }
  87
  88    void Remove(BTNode node)
  89    {
  90       BTNode parent = node.parent;
  91
  92 #ifdef _DEBUG
  93       if(!root || !root.FindNode(node))
  94       {
  95          printf("Removing node not in binary tree\n");
  96       }
  97 #endif
  98       /*BTNode swap = node.RemoveSwapRight();
  99       if(node == root)
 100               root = swap;
 101          */
 102       if(parent || root == node)
 103       {
 104          root = node.RemoveSwapRight();
 105          count--;
 106          /*
 107          if(swap)
 108             root = swap.Rebalance();
 109          else if(parent)
 110             root = parent.Rebalance();
 111          else
 112             root = root.Rebalance();
 113          */
 114          // Check();
 115          node.parent = null;
 116       }
 117    }
 118
 119    void Delete(BTNode node)
 120    {
 121       void * voidNode = node;
 122       Remove(node);
 123       delete voidNode;
 124    }
 125
 126    char * Print(char * output, TreePrintStyle tps)
 127    {
 128       output[0] = 0;
 129       if(root) root.Print(output, tps);
 130       return output;
 131    }
 132
 133    bool Check()
 134    {
 135       return root ? root.Check(this) : true;
 136    }
 137
 138    property BTNode first { get { return root ? root.minimum : null; } }
 139    property BTNode last { get { return root ? root.maximum : null; } }
 140 };
 141
 142 public struct StringBinaryTree : BinaryTree
 143 {
 144    void OnSerialize(IOChannel channel)
 145    {
 146       channel.Serialize((StringBTNode)root);
 147    }
 148
 149    void OnUnserialize(IOChannel channel)
 150    {
 151       StringBTNode root = null;
 152       channel.Unserialize(root);
 153       this.root = (BTNode)root;
 154       count = root ? this.root.count : 0;
 155    }
 156 };