/
fuzzystack.py
97 lines (84 loc) · 2.86 KB
/
fuzzystack.py
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
# Fuzzy stack
# 10 Jan 2009 kmill
# Something between a stack, a priority queue, and a dictionary
# Hopefully useful for NLP
class FuzzyStack :
def __init__(self, depth=4) :
self.data = list()
self.depth = depth
#returns a string representing the data in dictionary form.
def __str__(self):
d = self.makeDict()
p = ""
for key in d.keys():
p = p + str(key) + ": "
if isinstance(d[key], dict):
p = p + str(d[key].keys()) + "\n"
else:
p = p + str(d[key]) + "\n"
return p
# Pushes a new key/value pair onto the dictionary
def push(self, symbol, value) :
# Truncate the stack to the desired length if necessary
if len(self.data) == self.depth :
self.rpop(symbol)
if len(self.data) == self.depth :
self.popoldest()
self.data.insert(0, (symbol, value));
# Returns a dictionary of the most relevant keys
def makeDict(self) :
output = dict()
for d in reversed(self.data) :
output[d[0]] = d[1]
return output
# Retrieve a key
def read(self, symbol) :
d = self.makeDict()
if d.has_key(symbol): return d[symbol]
return None
# Count the number of records with the given key
def countSymbols(self, symbol) :
return len([0 for d in self.data if d[0] == symbol])
# get index^th record with a given key
def readIndex(self, symbol, index) :
return [d[1] for d in self.data if d[0] == symbol][index]
# An iterator to do the previous function
def values(self, symbol) :
return [d[1] for d in self.data if d[0] == symbol].__iter__()
# Sees what's on top of the stack
def peek(self) :
return self.data[0];
# Pop off the data of a given key
def pop(self, symbol) :
for d in self.data :
if(symbol == d[0]) :
self.data.remove(d)
return d
return False
# Pop off the oldest occurrance of a key
def rpop(self, symbol) :
index = -1
for i in range(0, len(self.data)) :
if(symbol == self.data[i][0]) :
index = i
if index >= 0 :
return self.data.pop(index)
else :
return None
# Pop off the key which is farthest down and has the most siblings
def popoldest(self) :
index = -1
maxnum = 0
keys = dict()
for i in range(0, len(self.data)) :
if not keys.has_key(self.data[i][0]) :
keys[self.data[i][0]] = 0
else :
keys[self.data[i][0]] += 1
if keys[self.data[i][0]] >= maxnum :
maxnum = keys[self.data[i][0]]
index = i
if index >= 0 :
return self.data.pop(index)
else :
return None