/usr/share/pyshared/larch/nodes.py is in python-larch 1.20131130-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 | # Copyright 2010 Lars Wirzenius
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
import bisect
import larch
class FrozenNode(larch.Error):
'''User tried to modify node that is frozen.'''
def __init__(self, node):
self.msg = 'Node %s is frozen against modifications' % node.id
class Node(object):
'''Abstract base class for index and leaf nodes.
A node may be initialized with a list of (key, value) pairs. For
leaf nodes, the values are the actual values. For index nodes, they
are references to other nodes.
A node can be indexed using keys, and give the corresponding value.
Setting key/value pairs cannot be done using indexing. However,
``key in node`` does work, as does iteration over a key's values.
``len(node)`` returns the number if keys.
Two nodes compare equal if they have the same key/value pairs.
The node ids do not need to match.
Nodes can be modified, bt only if the ``frozen`` property is false.
If it is set to true, any attempt at modifying the node causes
the ``FrozenNode`` exception to be raised.
'''
def __init__(self, node_id, keys, values):
self._keys = list(keys)
self._values = list(values)
self._dict = dict()
for i in range(len(keys)):
self._dict[keys[i]] = values[i]
self.id = node_id
self.size = None
self.frozen = False
def __getitem__(self, key):
return self._dict[key]
def __contains__(self, key):
return key in self._dict
def __eq__(self, other):
return self._keys == other._keys and self._values == other._values
def __iter__(self):
for key in self._keys:
yield key
def __len__(self):
return len(self._keys)
def __nonzero__(self):
return True
def keys(self):
'''Return keys in the node, sorted.'''
return self._keys
def values(self):
'''Return value in the node, in same order as keys.'''
return self._values
def first_key(self):
'''Return smallest key in the node.'''
return self._keys[0]
def find_potential_range(self, minkey, maxkey):
'''Find pairs whose key is in desired range.
``minkey`` and ``maxkey`` are inclusive.
We take into account that for index nodes, a child's key
really represents a range of keys, from the key up to (but
not including) the next child's key. The last child's key
represents a range up to infinity.
Thus we return the first child, if its key lies between
``minkey`` and ``maxkey``, and the last child, if its key is at most
``maxkey``.
'''
def helper(key, default):
x = bisect.bisect_left(self._keys, key)
if x < len(self._keys):
if self._keys[x] > key:
if x == 0:
x = default
else:
x -= 1
else:
if x == 0:
x = None
else:
x -= 1
return x
i = helper(minkey, 0)
j = helper(maxkey, None)
if j is None:
i = None
return i, j
def _error_if_frozen(self):
if self.frozen:
raise FrozenNode(self)
def add(self, key, value):
'''Insert a key/value pair into the right place in a node.'''
self._error_if_frozen()
i = bisect.bisect_left(self._keys, key)
if i < len(self._keys) and self._keys[i] == key:
self._keys[i] = key
self._values[i] = value
else:
self._keys.insert(i, key)
self._values.insert(i, value)
self._dict[key] = value
self.size = None
def remove(self, key):
'''Remove a key from the node.
Raise KeyError if key does not exist in node.
'''
self._error_if_frozen()
i = bisect.bisect_left(self._keys, key)
if i >= len(self._keys) or self._keys[i] != key:
raise KeyError(key)
del self._keys[i]
del self._values[i]
del self._dict[key]
self.size = None
def remove_index_range(self, lo, hi):
'''Remove keys given a range of indexes into pairs.
lo and hi are inclusive.
'''
self._error_if_frozen()
del self._keys[lo:hi+1]
del self._values[lo:hi+1]
self.size = None
class LeafNode(Node):
'''Leaf node in the tree.
A leaf node contains key/value pairs (both strings), and has no children.
'''
def find_keys_in_range(self, minkey, maxkey):
'''Find pairs whose key is in desired range.
``minkey`` and ``maxkey`` are inclusive.
'''
i = bisect.bisect_left(self._keys, minkey)
j = bisect.bisect_left(self._keys, maxkey)
if j < len(self._keys) and self._keys[j] == maxkey:
j += 1
return self._keys[i:j]
class IndexNode(Node):
'''Index node in the tree.
An index node contains pairs of keys and references to other nodes
(node ids, which are integers).
The other nodes may be either index nodes or leaf nodes.
'''
def find_key_for_child_containing(self, key):
'''Return key for the child that contains ``key``.'''
i = bisect.bisect_left(self._keys, key)
if i < len(self._keys):
if self._keys[i] == key:
return key
elif i:
return self._keys[i-1]
elif i:
return self._keys[i-1]
def find_children_in_range(self, minkey, maxkey):
'''Find all children whose key is in the range.
``minkey`` and ``maxkey`` are inclusive. Note that a child might
be returned even if not all of its keys are in the range,
just some of them. Also, we consider potential keys here,
not actual keys. We have no way to retrieve the children
to check which keys they actually have, so instead we
return which keys might have the desired keys, and the
caller can go look at those.
'''
i, j = self.find_potential_range(minkey, maxkey)
if i is not None and j is not None:
return self._values[i:j+1]
else:
return []
|