source: golgotha/src/i4/memory/binary_tree.hh @ 80

Last change on this file since 80 was 80, checked in by Sam Hocevar, 12 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 2.5 KB
Line 
1/********************************************************************** <BR>
2  This file is part of Crack dot Com's free source code release of
3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for
4  information about compiling & licensing issues visit this URL</a>
5  <PRE> If that doesn't help, contact Jonathan Clark at
6  golgotha_source@usa.net (Subject should have "GOLG" in it)
7***********************************************************************/
8
9#ifndef I4_BINARY_TREE_HH
10#define I4_BINARY_TREE_HH
11
12/*
13pretty simple, uses linear_allocator for quick allocation
14two methods, ::insert & ::find so far, you need to define the > & <
15  operators for the type if they don't exsist.
16
17example ussage:
18-------------------
19
20i4_binary_tree<int> tree;
21tree.insert(6);
22tree.insert(10);
23if (tree.find(12))  x=5;
24 
25or for user defined structs :
26
27struct complex
28{
29  float a;
30  float b;
31
32  i4_bool operator>(const command_matchup c) const { return (i4_bool)(a>c.b); }
33  i4_bool operator<(const command_matchup b) const { return (i4_bool)(a<c.b); }
34};
35
36i4_binary_tree<complex> tree2;
37tree2.insert(complex(3.1, 4.5));
38tree2.find(complex(3.1,0));
39*/
40
41#include "memory/lalloc.hh"
42
43template <class T>
44class i4_binary_tree
45{
46  void recursive_delete(T * node)
47  {
48    if (node->right)
49      recursive_delete(node->right);
50    if (node->left)
51      recursive_delete(node->left);
52    delete node;
53  }
54
55public:
56  T *root;
57
58  i4_binary_tree()   { root=0; }
59
60
61  // insert return a previous instance if already in tree
62  T *insert(T *x)
63  {   
64    x->left=x->right=0;
65
66    if (!root)
67      root=x;
68    else
69    {
70      T *p=root;
71             
72      while (1)
73      {
74        int cmp=x->compare(p);
75        if (cmp<0)
76        {
77          if (!p->left)
78          {
79            p->left=x;
80            return x;
81          }
82          else p=p->left;
83        }
84        else if (cmp>0)
85        {
86          if (!p->right)
87          {
88            p->right=x;
89            return x;
90          }
91          else p=p->right;
92        }
93        else return p;
94      }
95    }
96
97    return x;
98  }
99
100  T *find(const T *x)
101  {
102    T *p=root;
103    while (1)
104    {
105      if (!p) return 0;
106
107      int cmp=x->compare(p);
108      if (cmp<0)
109        p=p->left;
110      else if (cmp>0)
111        p=p->right;
112      else return p;
113    }
114  }
115
116  void delete_tree()
117  {
118    if (root)
119      recursive_delete(root);
120  }
121
122};
123
124#endif
Note: See TracBrowser for help on using the repository browser.