#!/usr/bin/env python # Copyright (C) 2011 # Brett Alistair Kromkamp - brettkromkamp@gmail.com # Copyright (C) 2012-2017 # Xiaming Chen - chenxm35@gmail.com # and other contributors. # All rights reserved. # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. """ Node structure in treelib. A :class:`Node` object contains basic properties such as node identifier, node tag, parent node, children nodes etc., and some operations for a node. """ from __future__ import unicode_literals import copy import uuid from collections import defaultdict from warnings import warn from .exceptions import NodePropertyError from .misc import deprecated class Node(object): """ Nodes are elementary objects that are stored in the `_nodes` dictionary of a Tree. Use `data` attribute to store node-specific data. """ #: Mode constants for routine `update_fpointer()`. (ADD, DELETE, INSERT, REPLACE) = list(range(4)) def __init__(self, tag=None, identifier=None, expanded=True, data=None): """Create a new Node object to be placed inside a Tree object""" #: if given as a parameter, must be unique self._identifier = None self._set_identifier(identifier) #: None or something else #: if None, self._identifier will be set to the identifier's value. if tag is None: self._tag = self._identifier else: self._tag = tag #: boolean self.expanded = expanded #: identifier of the parent's node : self._predecessor = {} #: identifier(s) of the soons' node(s) : self._successors = defaultdict(list) #: User payload associated with this node. self.data = data # for retro-compatibility on bpointer/fpointer self._initial_tree_id = None def __lt__(self, other): return self.tag < other.tag def set_initial_tree_id(self, tree_id): if self._initial_tree_id is None: self._initial_tree_id = tree_id def _set_identifier(self, nid): """Initialize self._set_identifier""" if nid is None: self._identifier = str(uuid.uuid1()) else: self._identifier = nid @property @deprecated(alias="node.predecessor") def bpointer(self): """Use predecessor method, this property is deprecated and only kept for retro-compatilibity. Parents of a node are dependant on a given tree. This implementation keeps the previous behavior by keeping returning bpointer of first declared tree. """ if self._initial_tree_id not in self._predecessor.keys(): return None return self._predecessor[self._initial_tree_id] @bpointer.setter @deprecated(alias="node.set_predecessor") def bpointer(self, value): self.set_predecessor(value, self._initial_tree_id) @deprecated(alias="node.set_predecessor") def update_bpointer(self, nid): self.set_predecessor(nid, self._initial_tree_id) @property @deprecated(alias="node.successors") def fpointer(self): """Use successors method, this property is deprecated and only kept for retro-compatilibity. Children of a node are dependant on a given tree. This implementation keeps the previous behavior by keeping returning fpointer of first declared tree. """ if self._initial_tree_id not in self._successors: return [] return self._successors[self._initial_tree_id] @fpointer.setter @deprecated(alias="node.update_successors") def fpointer(self, value): self.set_successors(value, tree_id=self._initial_tree_id) @deprecated(alias="node.update_successors") def update_fpointer(self, nid, mode=ADD, replace=None): """Deprecated""" self.update_successors(nid, mode, replace, self._initial_tree_id) def predecessor(self, tree_id): """ The parent ID of a node in a given tree. """ return self._predecessor[tree_id] def set_predecessor(self, nid, tree_id): """Set the value of `_predecessor`.""" self._predecessor[tree_id] = nid def successors(self, tree_id): """ With a getting operator, a list of IDs of node's children is obtained. With a setting operator, the value can be list, set, or dict. For list or set, it is converted to a list type by the package; for dict, the keys are treated as the node IDs. """ return self._successors[tree_id] def set_successors(self, value, tree_id=None): """Set the value of `_successors`.""" setter_lookup = { "NoneType": lambda x: list(), "list": lambda x: x, "dict": lambda x: list(x.keys()), "set": lambda x: list(x), } t = value.__class__.__name__ if t in setter_lookup: f_setter = setter_lookup[t] self._successors[tree_id] = f_setter(value) else: raise NotImplementedError("Unsupported value type %s" % t) def update_successors(self, nid, mode=ADD, replace=None, tree_id=None): """ Update the children list with different modes: addition (Node.ADD or Node.INSERT) and deletion (Node.DELETE). """ if nid is None: return def _manipulator_append(): self.successors(tree_id).append(nid) def _manipulator_delete(): if nid in self.successors(tree_id): self.successors(tree_id).remove(nid) else: warn("Nid %s wasn't present in fpointer" % nid) def _manipulator_insert(): warn("WARNING: INSERT is deprecated to ADD mode") self.update_successors(nid, tree_id=tree_id) def _manipulator_replace(): if replace is None: raise NodePropertyError( 'Argument "repalce" should be provided when mode is {}'.format(mode) ) ind = self.successors(tree_id).index(nid) self.successors(tree_id)[ind] = replace manipulator_lookup = { self.ADD: "_manipulator_append", self.DELETE: "_manipulator_delete", self.INSERT: "_manipulator_insert", self.REPLACE: "_manipulator_replace", } if mode not in manipulator_lookup: raise NotImplementedError("Unsupported node updating mode %s" % str(mode)) f_name = manipulator_lookup.get(mode) f = locals()[f_name] return f() @property def identifier(self): """ The unique ID of a node within the scope of a tree. This attribute can be accessed and modified with ``.`` and ``=`` operator respectively. """ return self._identifier def clone_pointers(self, former_tree_id, new_tree_id): former_bpointer = self.predecessor(former_tree_id) self.set_predecessor(former_bpointer, new_tree_id) former_fpointer = self.successors(former_tree_id) # fpointer is a list and would be copied by reference without deepcopy self.set_successors(copy.deepcopy(former_fpointer), tree_id=new_tree_id) def reset_pointers(self, tree_id): self.set_predecessor(None, tree_id) self.set_successors([], tree_id=tree_id) @identifier.setter def identifier(self, value): """Set the value of `_identifier`.""" if value is None: print("WARNING: node ID can not be None") else: self._set_identifier(value) def is_leaf(self, tree_id=None): """Return true if current node has no children.""" if tree_id is None: # for retro-compatilibity if self._initial_tree_id not in self._successors.keys(): return True else: tree_id = self._initial_tree_id if len(self.successors(tree_id)) == 0: return True else: return False def is_root(self, tree_id=None): """Return true if self has no parent, i.e. as root.""" if tree_id is None: # for retro-compatilibity if self._initial_tree_id not in self._predecessor.keys(): return True else: tree_id = self._initial_tree_id return self.predecessor(tree_id) is None @property def tag(self): """ The readable node name for human. This attribute can be accessed and modified with ``.`` and ``=`` operator respectively. """ return self._tag @tag.setter def tag(self, value): """Set the value of `_tag`.""" self._tag = value if value is not None else None def __repr__(self): name = self.__class__.__name__ kwargs = [ "tag={0}".format(self.tag), "identifier={0}".format(self.identifier), "data={0}".format(self.data), ] return "%s(%s)" % (name, ", ".join(kwargs))