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) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
// This code is distributed under MIT X11 license (for details please see \doc\license.txt)
using System;
using System.Globalization;
namespace ICSharpCode.NRefactory.VB.Parser
{
/// <summary>
/// This class implements a keyword map. It implements a digital search trees (tries) to find
/// a word.
/// </summary>
internal class LookupTable
{
Node root = new Node(-1, null);
bool casesensitive;
int length;
/// <value>
/// The number of elements in the table
/// </value>
public int Count {
get {
return length;
}
}
/// <summary>
/// Inserts an int in the tree, under keyword
/// </summary>
public int this[string keyword] {
get {
Node next = root;
if (!casesensitive) {
keyword = keyword.ToUpper(CultureInfo.InvariantCulture);
}
for (int i = 0; i < keyword.Length; ++i) {
int index = ((int)keyword[i]) % 256;
next = next.leaf[index];
if (next == null) {
return -1;
}
if (keyword == next.word) {
return next.val;
}
}
return -1;
}
set {
Node node = root;
Node next = root;
if (!casesensitive) {
keyword = keyword.ToUpper(CultureInfo.InvariantCulture);
}
++length;
// insert word into the tree
for (int i = 0; i < keyword.Length; ++i) {
int index = ((int)keyword[i]) % 256; // index of curchar
bool d = keyword[i] == '\\';
next = next.leaf[index]; // get node to this index
if (next == null) { // no node created -> insert word here
node.leaf[index] = new Node(value, keyword);
break;
}
if (next.word != null && next.word.Length != i) { // node there, take node content and insert them again
string tmpword = next.word; // this word will be inserted 1 level deeper (better, don't need too much
int tmpval = next.val; // string comparisons for finding.)
next.val = -1;
next.word = null;
this[tmpword] = tmpval;
}
if (i == keyword.Length - 1) { // end of keyword reached, insert node there, if a node was here it was
next.word = keyword; // reinserted, if it has the same length (keyword EQUALS this word) it will be overwritten
next.val = value;
break;
}
node = next;
}
}
}
/// <summary>
/// Creates a new instance of <see cref="LookupTable"/>
/// </summary>
public LookupTable(bool casesensitive)
{
this.casesensitive = casesensitive;
}
class Node
{
public Node(int val, string word)
{
this.word = word;
this.val = val;
}
public string word;
public int val;
public Node[] leaf = new Node[256];
}
}
}
|
