Mercurial > ~dholland > hg > ag > index.cgi

comparison anagram/support/agbaltree.h @ 0:13d2b8934445

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import AnaGram (near-)release tree into Mercurial.
author David A. Holland
date Sat, 22 Dec 2007 17:52:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:13d2b8934445
1 /**********************************************************
2
3 The AnaGram Class Library
4
5 The AgBalancedTree Class
6 Copyright 1997 Parsifal Software. All Rights Reserved.
7 See the file COPYING for license and usage terms.
8
9 ***********************************************************/
10
11 #ifndef AGBALTREE_H
12 #define AGBALTREE_H
13
14 #include <stdlib.h>
15 #include "port.h"
16
17 #include "agcontainer.h"
18
19
20 template <class T>
21 class AgBalancedTree : public AgIndexedContainer<T> {
22 public:
23
24 // Define Node
25 class Node {
26 public:
27 Node *left, *right;
28 T data;
29 unsigned count;
30 Node (const T &t);
31 ~Node();
32 void resetCount();
33 T &locate(const unsigned x) const;
34 void *operator new(size_t);
35 void operator delete(void *);
36 };
37
38 Node *root;
39 virtual int compare(const T &x, const T &y) const;
40
41 // Process methods
42 int insert(const T &target, Node *&node);
43 int identify(T &target, Node *&node);
44 int identify(T *&target, Node *&node);
45 int remove(const T &target, Node *&node);
46 int includes(const T &target, Node *node) const;
47 int lookup(T &target, Node *node) const;
48
49 void rotateLeft(Node *&node);
50 void rotateRight(Node *&node);
51
52 Node *extractMin(Node *&node);
53 Node *extractMax(Node *&node);
54
55 // default comparison function
56
57 public:
58 AgBalancedTree() : AgIndexedContainer<T>(), root(0) {}
59 virtual ~AgBalancedTree();
60 int insert(const T &t);
61 int identify(T &t);
62 int identify(T *&t);
63 int remove(const T &t);
64 int includes(const T &t) const;
65 int lookup(T &t) const;
66 AgBalancedTree<T> &reset();
67 unsigned size() const;
68 void *operator new(size_t n) { return malloc(n); }
69 void operator delete(void *p) { free(p); }
70 const T &operator [] (const unsigned x) const { return root->locate(x); }
71 T &operator [] (const unsigned x) { return root->locate(x); }
72 AgBalancedTree<T> operator + (AgBalancedTree<T> &x);
73 AgBalancedTree<T> operator * (AgBalancedTree<T> &x);
74 AgBalancedTree<T> &operator *= (AgBalancedTree<T> &x);
75 AgBalancedTree<T> operator - (AgBalancedTree<T> &x);
76 int operator < (const AgBalancedTree<T> &) const;
77 };
78
79
80 #endif /* AGBALTREE_H */