blob: a566701fb5604835c1e91b56f8ff9c3c570784ce (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Copyright (c) 1989 Microsoft Corporation
Module Name:
pdict.cxx
Abstract:
This file contains the definition for splay tree self
adjusting binary trees.
History:
1990 Dov Harel Created
----------------------------------------------------------------------------*/
#ifndef __DICT_HXX__
#define __DICT_HXX__
#ifndef Nil
#define Nil 0
#endif
#ifndef DICT_MYSPLAY
#define VIRT_SPLAY
#else
#define VIRT_SPLAY virtual
#endif
typedef void * pUserType;
class TreeNode {
public:
TreeNode *left; /* left child pointer */
TreeNode *right; /* right child pointer */
pUserType item; /* pointer to some structure */
TreeNode(pUserType itemI)
{
left = right = Nil;
item = itemI;
}
};
typedef int (* CompareFN)(pUserType, pUserType);
typedef enum {
SUCCESS,
ITEM_ALREADY_PRESENT,
ITEM_NOT_FOUND,
FIRST_ITEM,
LAST_ITEM,
EMPTY_DICTIONARY,
NULL_ITEM
} Dict_Status;
class Dictionary {
TreeNode * root; // pointer to the root of a SAT
long fCompare; // value of last compare
pUserType itemCur; // the current item
long size; // number of records in dictionary/
public:
Dictionary()
{
root = Nil;
size = 0;
}
long SplayUserType(pUserType);
// default comparison is (signed) comparison of pointers to entries
virtual
int Compare (pUserType p1, pUserType p2)
{
long l1 = (long)p1;
long l2 = (long)p2;
return l1 - l2;
}
pUserType Dict_Curr_Item ()
{ // return the top of the tree
return ((root)? root->item: Nil);
}
pUserType Dict_Item ()
{ // return item from Find/Next/Prev methods
return (itemCur);
}
long Dict_Empty ()
{ // Is the tree empty
return (root == Nil);
}
Dict_Status Dict_Find(pUserType); // Item searched for
Dict_Status Dict_Init() // First item of a Type
{
return Dict_Next( (pUserType) 0 );
}
Dict_Status Dict_Next(pUserType = Nil); // Next item of a Type
Dict_Status Dict_Prev(pUserType = Nil); // Previous item of a Type
Dict_Status Dict_Insert(pUserType); // Add a new item to the tree
Dict_Status Dict_Delete(pUserType *); // Delete an item form the tree
// returns the item just deleted
};
#endif // __DICT_HXX__
|
