-
Notifications
You must be signed in to change notification settings - Fork 0
/
Trie.cs
162 lines (124 loc) · 4.91 KB
/
Trie.cs
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.Linq;
namespace Spotlight
{
class Trie
{
//root of our Trie
public TrieNode root;
//This is our final map/Index .Each key in the map represents a prefix and its value is a list of all files who has this string as its prefix , but the array/list is sorted by rank , which is assigned by recently added file first.
public Dictionary<string, List<FileObj>> map = new Dictionary<string, List<FileObj>>();
public Trie(TrieNode root)
{
this.root = root;
}
//basic trie insertion
public void Insert(TrieNode node, FileObj file, int index)
{
if (index == file.name.Length)
{
//if reached the end of the string , simply add the current file to the list of current node's files
node.files.Add(file);
return;
}
char cur = file.name[index];
//if child does not exist yet, then create it.
if (!node.children.ContainsKey(cur))
{
node.children[cur] = new TrieNode(cur);
}
//recur for every chaaracter of the file
Insert(node.children[cur], file, index + 1);
}
void DfsHelper(TrieNode node, string s)
{
//index the current prefix with the list of files
map[s] = node.files;
//recur for all nodes in the trie
foreach (KeyValuePair<char, TrieNode> child in node.children)
{
DfsHelper(child.Value, s + child.Key);
}
}
public void Dfs(TrieNode node, string str, int index)
{
while (index != str.Length)
{
node = node.children[str[index++]];
}
DfsHelper(node, str);
}
public class Ranksort : IComparer
{
int IComparer.Compare(Object a, Object b)
{
FileObj x = (FileObj)a;
FileObj y = (FileObj)b;
return (y.rank - x.rank);
}
}
//this is an interesting function. Basically , a trienode will call upon its children and tell them to return a list of sorted files upto their prefix
//Then it will combine and assign it self the sorted list of all files which could be formed from current prefix(formed by the current character as the end point) .
public List<FileObj> Update(TrieNode node)
{
//if reached the end
if (node.children.Count == 0)
{
//sort in descending order of rank and return the list
node.files.Sort((a, b) => b.rank - a.rank );
return node.files;
}
//combine all the list of its children
List<FileObj> tmp = new List<FileObj>();
foreach (KeyValuePair<char, TrieNode> child in node.children)
{
tmp.AddRange(Update(child.Value));
}
node.files.AddRange(tmp);
node.files.Sort((a, b) => b.rank - a.rank);
//return the sorted list
return node.files;
}
public void printMap()
{
foreach (KeyValuePair<String, List<FileObj>> comp in map)
{
Console.Write(comp.Key + " => ");
foreach (FileObj file in comp.Value)
{
Console.Write(file.name + " " + file.rank + " ");
}
Console.WriteLine("");
}
}
//serliazing and desearlizing the which was eventually given up because it was too time consuming
public void SerializeNow()
{
Console.WriteLine("Serialising now");
var f_fileStream = new FileStream(@"C:\\Users\\gunny\\source\\repos\\Spotlight\\tp.xml", FileMode.Create, FileAccess.Write);
var f_binaryFormatter = new BinaryFormatter();
f_binaryFormatter.Serialize(f_fileStream, map);
f_fileStream.Close();
}
public void DeSerializeNow()
{
Dictionary<string, ArrayList> tp;
Console.WriteLine("DE-Serialising now");
var f_fileStream = File.OpenRead(@"C:\\Users\\gunny\\source\\repos\\Spotlight\\tp.xml");
var f_binaryFormatter = new BinaryFormatter();
tp = (Dictionary<string, ArrayList>)f_binaryFormatter.Deserialize(f_fileStream);
f_fileStream.Close();
while (true)
{
string q = Console.ReadLine();
foreach (FileObj x in tp[q])
Console.WriteLine(x.name + " " + x.location + " " + x.rank);
}
}
}
}