source: golgotha/src/make/array_tree.hh @ 484

Last change on this file since 484 was 80, checked in by Sam Hocevar, 15 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: 1.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
10template <class T, int MAX_SIZE>
11class i4_array_tree
12{
13  int used;
14  T nodes[MAX_SIZE];
15
16public:
17
18  i4_array_tree()
19  {
20    used=0;
21  }
22
23  void add(T &x)
24  {
25    int i=0;
26
27    if (used+1==MAX_SIZE)
28      mk_error("array_tree full");
29    else if (used)
30    {
31      int parent=0, found=0;
32
33      while (i!=-1)
34      {
35        parent=i;
36        if (x<nodes[i])
37          i=nodes[i].left;
38        else if (x>nodes[i])
39          i=nodes[i].right;
40        else
41          return;      // already in tree               
42      }
43
44      i=used;
45
46      if (x<nodes[parent])
47        nodes[parent].left=i;
48      else
49        nodes[parent].right=i;
50     
51
52    }
53
54    nodes[i]=x;
55    nodes[i].left=-1;
56    nodes[i].right=-1;   
57    used++;
58  }
59
60
61  int find(T &x)
62  {
63    if (!used) return -1;
64    for (int i=0; ;)
65    {
66      if (x<nodes[i])
67        i=nodes[i].left;
68      else if (x>nodes[i])
69        i=nodes[i].right;
70      else return i;
71      if (i==-1)
72        return -1;
73    }   
74  }
75
76  T &get(int x) { return nodes[x]; }
77
78};
Note: See TracBrowser for help on using the repository browser.