"""
FtpCube
Copyright (C) Michael Gilfix
This file is part of FtpCube.
You should have received a file COPYING containing license terms
along with this program; if not, write to Michael Gilfix
(mgilfix@eecs.tufts.edu) for a copy.
This version of FtpCube is open source; you can redistribute it and/or
modify it under the terms listed in the file COPYING.
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.
"""
import utils
class DirectoryCacheNode:
"""A node in the cached tree.
Each node holds a reference to its parent node, a set of children, and node
data. The name of the node corresponds to the name of the name in the cached
directory structure."""
def __init__(self):
"""Creates an empty cache node with no children."""
self.name = None
self.parent = None
self.data = None
self.children = { }
class DirectoryCacheTree:
"""A directory tree caching structure.
This provides a cache for storing hierarchical file paths. Paths are given by
node names separated by a delimiter (the '/' separator is used by default). The
directory cache tree allows for operations such as node creation, searching,
and deletion."""
def __init__(self, delim='/'):
"""Creates the cache by initializing the root element.
'delim' is the character delimiter that separates the hierarchical path
between node names."""
self.root = DirectoryCacheNode()
self.root.name = delim
self.delim = delim
def getDelimiter(self):
"""Returns the delimiter for the cache tree."""
return self.delim
def pathToList(self, path):
"""Takes the hierarchical 'path' and splits it into a list using the
delimiter.
Blank entries are then filtered from the path."""
if utils.isStrOrUnicode(path):
names = [ x for x in path.split(self.delim) if x ]
elif isinstance(path, list):
names = [ x for x in list if x ]
else:
raise TypeError, _("Expected either string or list")
return names
def findNode(self, path):
"""Finds the cached node associated with the specified path.
Returns the node if found and None otherwise."""
found = None
node_list = self.getNodeList(path)
if node_list is not None:
found = node_list[-1]
return found
def getNodeList(self, path):
"""Returns a list of nodes along the specified path.
If the path is not in the cache, None is returned."""
names = self.pathToList(path)
node = self.root
node_list = [ node ]
for node_name in names:
try:
node = node.children[node_name]
node_list.append(node)
except KeyError:
node_list = None
break
return node_list
def getRoot(self):
"""Returns the root node."""
return self.root
def getChildren(self, node):
"""Returns the list of child nodes associated with the specified node.
No order is preserved here."""
children = None
if node is not None:
children = node.children.keys()
return children
def getChildNode(self, node, child):
"""Returns the object node 'child' who is a valid child of 'node'.
Otherwise, None is returned."""
try:
return node.children[child]
except KeyError:
return None
def removeChild(self, node, child):
"""Removes the named child from the cache tree with the specified node as
its parent."""
child = None
if node.children.has_key(child):
child = node.children[child]
del node.children[child]
return child
def removeNode(self, path):
"""Removes the node found at the specified path from the cache tree."""
node = self.findNode(path)
if node.parent is not None:
del node.parent.children[node.name]
return node
def addNode(self, path):
"""Adds a node whose entry in the cache tree corresponds to the specified
path.
If sub nodes are missing during the creation of the leaf node, they are
created along the way, with their children set accordingly."""
new_node = DirectoryCacheNode()
node = self.root
names = self.pathToList(path)
if not names:
return node
new_name = names.pop()
for entry_name in names:
if not node.children.has_key(entry_name):
path_node = DirectoryCacheNode()
path_node.name = entry_name
node.children[entry_name] = path_node
node = node.children[entry_name]
new_node.name = new_name
new_node.parent = node
node.children[new_name] = new_node
return new_node
|