1// TwoKeyAVLTree.h
2//
3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4//
5// Permission is hereby granted, free of charge, to any person obtaining a
6// copy of this software and associated documentation files (the "Software"),
7// to deal in the Software without restriction, including without limitation
8// the rights to use, copy, modify, merge, publish, distribute, sublicense,
9// and/or sell copies of the Software, and to permit persons to whom the
10// Software is furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21// DEALINGS IN THE SOFTWARE.
22//
23// Except as contained in this notice, the name of a copyright holder shall
24// not be used in advertising or otherwise to promote the sale, use or other
25// dealings in this Software without prior written authorization of the
26// copyright holder.
27
28#ifndef TWO_KEY_AVL_TREE_H
29#define TWO_KEY_AVL_TREE_H
30
31#include "AVLTree.h"
32
33// TwoKeyAVLTreeKey
34template<typename PrimaryKey, typename SecondaryKey>
35class TwoKeyAVLTreeKey {
36public:
37	inline TwoKeyAVLTreeKey(const PrimaryKey &primary,
38							const SecondaryKey &secondary)
39		: primary(primary),
40		  secondary(secondary),
41		  use_secondary(true)
42	{
43	}
44
45	inline TwoKeyAVLTreeKey(const PrimaryKey *primary)
46		: primary(primary),
47		  secondary(NULL),
48		  use_secondary(false)
49	{
50	}
51
52	PrimaryKey		primary;
53	SecondaryKey	secondary;
54	bool			use_secondary;
55};
56
57// TwoKeyAVLTreeKeyCompare
58template<typename PrimaryKey, typename SecondaryKey,
59		 typename PrimaryKeyCompare, typename SecondaryKeyCompare>
60class TwoKeyAVLTreeKeyCompare {
61private:
62	typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key;
63
64public:
65	inline TwoKeyAVLTreeKeyCompare(const PrimaryKeyCompare &primary,
66								   const SecondaryKeyCompare &secondary)
67		: fPrimaryKeyCompare(primary), fSecondaryKeyCompare(secondary) {}
68
69	inline int operator()(const Key &a, const Key &b) const
70	{
71		int result = fPrimaryKeyCompare(a.primary, b.primary);
72		if (result == 0 && a.use_secondary && b.use_secondary)
73			result = fSecondaryKeyCompare(a.secondary, b.secondary);
74		return result;
75	}
76
77private:
78	PrimaryKeyCompare	fPrimaryKeyCompare;
79	SecondaryKeyCompare	fSecondaryKeyCompare;
80};
81
82// TwoKeyAVLTreeGetKey
83template<typename Value, typename PrimaryKey, typename SecondaryKey,
84		 typename GetPrimaryKey, typename GetSecondaryKey>
85class TwoKeyAVLTreeGetKey
86{
87private:
88	typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key;
89
90public:
91	TwoKeyAVLTreeGetKey(const GetPrimaryKey &getPrimary,
92						const GetSecondaryKey &getSecondary)
93		: fGetPrimaryKey(getPrimary),
94		  fGetSecondaryKey(getSecondary)
95	{
96	}
97
98	inline Key operator()(const Value &a) const
99	{
100		return Key(fGetPrimaryKey(a), fGetSecondaryKey(a));
101	}
102
103private:
104	GetPrimaryKey	fGetPrimaryKey;
105	GetSecondaryKey	fGetSecondaryKey;
106};
107
108// for convenience
109#define TWO_KEY_AVL_TREE_TEMPLATE_LIST template<typename Value, \
110	typename PrimaryKey, typename PrimaryKeyCompare, \
111	typename GetPrimaryKey, typename SecondaryKey, typename Node, \
112	typename SecondaryKeyCompare, typename GetSecondaryKey, \
113	typename NodeAllocator, typename GetValue>
114#define TWO_KEY_AVL_TREE_CLASS_NAME TwoKeyAVLTree<Value, PrimaryKey, \
115	PrimaryKeyCompare, GetPrimaryKey, SecondaryKey, Node, \
116	SecondaryKeyCompare, GetSecondaryKey, NodeAllocator, GetValue>
117
118// TwoKeyAVLTree
119template<typename Value, typename PrimaryKey,
120		 typename PrimaryKeyCompare, typename GetPrimaryKey,
121		 typename SecondaryKey = Value,
122		 typename Node = AVLTreeStandardNode<Value>,
123		 typename SecondaryKeyCompare = AVLTreeStandardCompare<SecondaryKey>,
124		 typename GetSecondaryKey = AVLTreeStandardGetKey<Value, SecondaryKey>,
125		 typename NodeAllocator = AVLTreeStandardNodeAllocator<Value, Node>,
126		 typename GetValue = AVLTreeStandardGetValue<Value, Node> >
127class TwoKeyAVLTree : private AVLTree<Value,
128	TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey>, Node,
129	TwoKeyAVLTreeKeyCompare<PrimaryKey, SecondaryKey, PrimaryKeyCompare,
130							SecondaryKeyCompare>,
131	TwoKeyAVLTreeGetKey<Value, PrimaryKey, SecondaryKey, GetPrimaryKey,
132						GetSecondaryKey>,
133	NodeAllocator, GetValue> {
134private:
135	typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key;
136	typedef TwoKeyAVLTreeKeyCompare<PrimaryKey, SecondaryKey,
137									PrimaryKeyCompare, SecondaryKeyCompare>
138			KeyCompare;
139	typedef TwoKeyAVLTreeGetKey<Value, PrimaryKey, SecondaryKey, GetPrimaryKey,
140								GetSecondaryKey>
141			GetKey;
142	typedef AVLTree<Value, Key, Node, KeyCompare, GetKey, NodeAllocator,
143					GetValue> BaseClass;
144public:
145	typedef typename BaseClass::Iterator Iterator;
146
147public:
148	TwoKeyAVLTree();
149	TwoKeyAVLTree(const PrimaryKeyCompare &primaryCompare,
150				  const GetPrimaryKey &getPrimary,
151				  const SecondaryKeyCompare &secondaryCompare,
152				  const GetSecondaryKey &getSecondary,
153				  const NodeAllocator &allocator,
154				  const GetValue &getValue);
155	~TwoKeyAVLTree();
156
157	inline int CountItems() const	{ return BaseClass::CountItems(); }
158
159	Value *FindFirst(const PrimaryKey &key, Iterator *iterator = NULL);
160	Value *FindLast(const PrimaryKey &key, Iterator *iterator = NULL);
161	inline Value *Find(const PrimaryKey &primaryKey,
162					   const SecondaryKey &secondaryKey,
163					   Iterator *iterator = NULL);
164
165	inline void GetIterator(Iterator *iterator, bool reverse = false);
166
167	inline status_t Insert(const Value &value, Iterator *iterator = NULL);
168	inline status_t Remove(const PrimaryKey &primaryKey,
169						   const SecondaryKey &secondaryKey);
170	inline void Remove(Iterator &iterator);
171
172private:
173	PrimaryKeyCompare	fPrimaryKeyCompare;
174	GetPrimaryKey		fGetPrimaryKey;
175};
176
177
178// constructor
179TWO_KEY_AVL_TREE_TEMPLATE_LIST
180TWO_KEY_AVL_TREE_CLASS_NAME::TwoKeyAVLTree()
181	: BaseClass(KeyCompare(PrimaryKeyCompare(), SecondaryKeyCompare()),
182						   GetKey(GetPrimaryKey(), GetSecondaryKey()),
183						   NodeAllocator(), GetValue())
184{
185}
186
187// constructor
188TWO_KEY_AVL_TREE_TEMPLATE_LIST
189TWO_KEY_AVL_TREE_CLASS_NAME::TwoKeyAVLTree(
190	const PrimaryKeyCompare &primaryCompare, const GetPrimaryKey &getPrimary,
191	const SecondaryKeyCompare &secondaryCompare,
192	const GetSecondaryKey &getSecondary, const NodeAllocator &allocator,
193	const GetValue &getValue)
194	: BaseClass(KeyCompare(primaryCompare, secondaryCompare),
195						   GetKey(getPrimary, getSecondary),
196						   allocator, getValue),
197	  fPrimaryKeyCompare(primaryCompare),
198	  fGetPrimaryKey(getPrimary)
199
200{
201}
202
203// destructor
204TWO_KEY_AVL_TREE_TEMPLATE_LIST
205TWO_KEY_AVL_TREE_CLASS_NAME::~TwoKeyAVLTree()
206{
207}
208
209// FindFirst
210TWO_KEY_AVL_TREE_TEMPLATE_LIST
211Value *
212TWO_KEY_AVL_TREE_CLASS_NAME::FindFirst(const PrimaryKey &key,
213									   Iterator *iterator)
214{
215	Node *node = BaseClass::fRoot;
216	while (node) {
217		int cmp = fPrimaryKeyCompare(key, fGetPrimaryKey(fGetValue(node)));
218		if (cmp == 0) {
219			// found a matching node, now get the left-most node with that key
220			while (node->left && fPrimaryKeyCompare(key,
221				   		fGetPrimaryKey(fGetValue(node->left))) == 0) {
222				node = node->left;
223			}
224			if (iterator)
225				_InitIterator(iterator, node);
226			return &fGetValue(node);
227		}
228		if (cmp < 0)
229			node = node->left;
230		else
231			node = node->right;
232	}
233	return NULL;
234}
235
236// FindLast
237TWO_KEY_AVL_TREE_TEMPLATE_LIST
238Value *
239TWO_KEY_AVL_TREE_CLASS_NAME::FindLast(const PrimaryKey &key,
240									  Iterator *iterator)
241{
242	Node *node = BaseClass::fRoot;
243	while (node) {
244		int cmp = fPrimaryKeyCompare(key, fGetPrimaryKey(fGetValue(node)));
245		if (cmp == 0) {
246			// found a matching node, now get the right-most node with that key
247			while (node->right && fPrimaryKeyCompare(key,
248				   		fGetPrimaryKey(fGetValue(node->right))) == 0) {
249				node = node->right;
250			}
251			if (iterator)
252				_InitIterator(iterator, node);
253			return &fGetValue(node);
254		}
255		if (cmp < 0)
256			node = node->left;
257		else
258			node = node->right;
259	}
260	return NULL;
261}
262
263// Find
264TWO_KEY_AVL_TREE_TEMPLATE_LIST
265Value *
266TWO_KEY_AVL_TREE_CLASS_NAME::Find(const PrimaryKey &primaryKey,
267								  const SecondaryKey &secondaryKey,
268								  Iterator *iterator)
269{
270	return BaseClass::Find(Key(primaryKey, secondaryKey), iterator);
271}
272
273// GetIterator
274TWO_KEY_AVL_TREE_TEMPLATE_LIST
275void
276TWO_KEY_AVL_TREE_CLASS_NAME::GetIterator(Iterator *iterator, bool reverse)
277{
278	BaseClass::GetIterator(iterator, reverse);
279}
280
281// Insert
282TWO_KEY_AVL_TREE_TEMPLATE_LIST
283status_t
284TWO_KEY_AVL_TREE_CLASS_NAME::Insert(const Value &value, Iterator *iterator)
285{
286	return BaseClass::Insert(value, iterator);
287}
288
289// Remove
290TWO_KEY_AVL_TREE_TEMPLATE_LIST
291status_t
292TWO_KEY_AVL_TREE_CLASS_NAME::Remove(const PrimaryKey &primaryKey,
293									const SecondaryKey &secondaryKey)
294{
295	return BaseClass::Remove(Key(primaryKey, secondaryKey));
296}
297
298// Remove
299TWO_KEY_AVL_TREE_TEMPLATE_LIST
300void
301TWO_KEY_AVL_TREE_CLASS_NAME::Remove(Iterator &iterator)
302{
303	BaseClass::Remove(iterator);
304}
305
306#endif	// TWO_KEY_AVL_TREE_H
307