path: root/XTree.py

# Copyright (c) 2001 - 2005
#     Yuan Wang. All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright 
# notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
# notice, this list of conditions and the following disclaimer in the 
# documentation and/or other materials provided with the distribution.
# 3. Redistributions in any form must be accompanied by information on
# how to obtain complete source code for the X-Diff software and any
# accompanying software that uses the X-Diff software.  The source code
# must either be included in the distribution or be available for no
# more than the cost of distribution plus a nominal fee, and must be
# freely redistributable under reasonable conditions.  For an executable
# file, complete source code means the source code for all modules it
# contains.  It does not include source code for modules or files that
# typically accompany the major components of the operating system on
# which the executable file runs.
# 
# THIS SOFTWARE IS PROVIDED BY YUAN WANG "AS IS" AND ANY EXPRESS OR IMPLIED
# WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT,
# ARE DISCLAIMED.  IN NO EVENT SHALL YUAN WANG BE LIABLE FOR ANY DIRECT,
# INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
# STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
# IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.

MATCH = 0
CHANGE = 1
NO_MATCH = -1
INSERT = -1
DELETE = -1
NULL_NODE = -1
NO_CONNECTION = 1048576

_TOP_LEVEL_CAPACITY = 16384
_BOT_LEVEL_CAPACITY = 4096


# <code>XTree</code> provides a DOM-like interface but somehow simplified
# Ideally, it can be replaced by any other DOM parser output tree structures.
class XTree:
#    private     _topCap, _botCap
#    private     _elementIndex, _tagIndex, self._valueCount
#    private        self._firstChild[][], self._nextSibling[][]
#    private     self._childrenCount[][], _valueIndex[][]
#    private boolean        self._isAttribute[][]
#    private     self._matching[][]
#    private long        self._hashValue[][]
#    private String        _value[][]
#    private Hashtable    self._tagNames, _cdataTable
    _root = 0
    _firstChild = []
    _nextSibling = []
    _isAttribute = []
    _valueIndex = []
    _matching = []
    _childrenCount = []
    _hashValue = []
    _value = []
    
    _value.append([])
    _tagNames = []
    
    # This hashtable is used to record CDATA section info.
    # The key is the text node id, the value is the list of 
    # (start,end) position pair of each CDATA section.
    _cdataTable = {}
    
    _elementIndex = -1
    _tagIndex = -1
    _valueCount = 0



    def __init__(self, topcap=None, botcap=None):
        self._topCap = _TOP_LEVEL_CAPACITY
        self._botCap = _BOT_LEVEL_CAPACITY
        if topcap:
            self._topCap = topcap
        if botcap:
            self._botCap = botcap
        self._initialize()

    # Initialization.
    def _initialize(self):
        self._root = 0
        self._firstChild = []
        self._nextSibling = []
        self._isAttribute = []
        self._valueIndex = []
        self._matching = []
        self._childrenCount = []
        self._hashValue = []
        self._value = []

        self._value.append([])
        self._tagNames = []

        # This hashtable is used to record CDATA section info.
        # The key is the text node id, the value is the list of 
        # (start,end) position pair of each CDATA section.
        self._cdataTable = {}

        self._elementIndex = -1
        self._tagIndex = -1
        self._valueCount = self._botCap - 1

    # ID Expansion
    def _expand(self, topid):
        self._firstChild[topid] = []
        self._nextSibling[topid] = []
        self._childrenCount[topid] = []
        self._matching[topid] = []
        self._valueIndex[topid] = []
        self._hashValue[topid] = []
        self._isAttribute[topid] = []

        for i in range(self._botCap):
            self._firstChild[topid][i] = NULL_NODE
            self._nextSibling[topid][i] = NULL_NODE
            self._childrenCount[topid][i] = 0
            self._matching[topid][i] = MATCH
            self._valueIndex[topid][i] = -1
            self._isAttribute[topid][i] = False

    # Start  -- methods for constructing a tree.
    # Add a new element to the tree.
    # @param    pid        parent id
    # @param    lsid        left-side sibling id
    # @param    tagName        element name
    # @return    the element id in the tree.
    def addElement(self, pid, lsid, tagName):
        self._elementIndex += 1

        topid = self._elementIndex / self._botCap
        botid = self._elementIndex % self._botCap
        if (botid == 0):
            self._expand(topid)

        # Check if we've already had the tag
        tagID = self._tagNames[tagName]
        if (tagID != None):
            self._valueIndex[topid][botid] = tagID.intValue()
        else:
            self._tagIndex += 1
            tagID = int(self._tagIndex)
            self._value[0][self._tagIndex] = tagName
            self._tagNames.append(tagName, tagID)
            self._valueIndex[topid][botid] = self._tagIndex

        if (pid == NULL_NODE):
            return self._elementIndex

        ptopid = pid / self._botCap
        pbotid = pid % self._botCap
        # parent-child relation or sibling-sibling relation
        if (lsid == NULL_NODE):
            self._firstChild[ptopid][pbotid] = self._elementIndex
        else:
            self._nextSibling[lsid / self._botCap][lsid % self._botCap] = self._elementIndex

        # update children count
        self._childrenCount[ptopid][pbotid] += 1

        return self._elementIndex

    # Add a text node.
    # @param    eid    element id
    # @param    lsid    the sibling id on the left
    # @param    text    text value
    # @param    value    hash value
    def addText(self, eid, lsid, text, value):
        self._elementIndex += 1
        topid = self._elementIndex / self._botCap
        botid = self._elementIndex % self._botCap
        if (botid == 0):
            self._expand(topid)

        etopid = eid / self._botCap
        ebotid = eid % self._botCap
        if (lsid == NULL_NODE):
            self._firstChild[etopid][ebotid] = self._elementIndex
        else:
            self._nextSibling[lsid / self._botCap][lsid % self._botCap] = self._elementIndex

        self._childrenCount[etopid][ebotid] += 1
        self._hashValue[topid][botid] = value

        self._valueCount += 1
        vtopid = self._valueCount / self._botCap
        vbotid = self._valueCount % self._botCap
        if (vbotid == 0):
            self._value[vtopid] = str[self._botCap]

        self._value[vtopid][vbotid] = text
        self._valueIndex[topid][botid] = self._valueCount

        return self._elementIndex

    # Add an attribute.
    # @param    eid    element id
    # @param    lsid    the sibling id on the left
    # @param    name    attribute name
    # @param    value    attribute value
    # @param    valuehash    hash value of the value
    # @param    attrhash    hash value of the entire attribute
    # @return    the element id of the attribute
    def addAttribute(self, eid, lsid, name, value, valuehash, attrhash):
        # attribute name first.
        aid = self.addElement(eid, lsid, name)

        # attribute value second.
        self.addText(aid, NULL_NODE, value, valuehash)

        # hash value third
        atopid = aid / self._botCap
        abotid = aid % self._botCap
        self._isAttribute[atopid][abotid] = True
        self._hashValue[atopid][abotid] = attrhash

        return aid

    # Add more information (hash value) to an element node.
    # @param    eid    element id
    # @param    value    extra hash value
    def addHashValue(self, eid, value):
        self._hashValue[eid / self._botCap][eid % self._botCap] = value

    # Add a CDATA section (either a start or an end) to the CDATA
    # hashtable, in which each entry should have an even number of
    # position slots.
    # @param    eid        The text node id
    # @param    position    the section tag position
    def addCDATA(self, eid, position):
        key = int(eid)
        value = self._cdataTable[key]
        if (value == None):
            elem_list = []
            elem_list.append(position)
            self._cdataTable[key] = elem_list
        else:
            elem_list = value
            elem_list.append(position)
            self._cdataTable[key] = elem_list

    # Add matching information.
    # @param    eid    element id
    # @param    match    ?match and matched element id
    def addMatching(self, eid, match):
        if (match[0] == NO_MATCH):
            self._matching[eid / self._botCap][eid % self._botCap] = NO_MATCH
        elif (match[0] == MATCH):
            self._matching[eid / self._botCap][eid % self._botCap] = MATCH
        else:
            self._matching[eid / self._botCap][eid % self._botCap] = match[1] + 1

    # End  -- methods for constructing a tree.

    # Start -- methods for accessing a tree.

    # Get matching information.
    # @param    eid    element id
    # @param    match    ?change and matched element id 
    def getMatching(self, eid, match):
        mid = self._matching[eid / self._botCap][eid % self._botCap]
        if (mid == NO_MATCH):
            match[0] = NO_MATCH
        elif (mid == MATCH):
            match[0] = MATCH
        else:
            match[0] = CHANGE
            match[1] = mid - 1

    # Get the root element id.
    def getRoot(self):
        return self._root

    # Get the first child of a node.
    # @param    eid    element id
    def getFirstChild(self, eid):
        cid = self._firstChild[eid / self._botCap][eid % self._botCap]
        while (cid > self._root):
            ctopid = cid / self._botCap
            cbotid = cid % self._botCap
            if (self._isAttribute[ctopid][cbotid]):
                cid = self._nextSibling[ctopid][cbotid]
            else:
                return cid

        return NULL_NODE

    # Get the next sibling of a node.
    # @param    eid    element id
    def getNextSibling(self, eid):
        return self._nextSibling[eid / self._botCap][eid % self._botCap]

    # Get the first attribute of a node.
    # @param    eid    element id
    def getFirstAttribute(self, eid):
        aid = self._firstChild[eid / self._botCap][eid % self._botCap]
        if ((aid > self._root) and (self._isAttribute[aid / self._botCap][aid % self._botCap])):
            return aid
        else:
            return NULL_NODE

    # Get the next attribute of a node.
    # @param    aid    attribute id
    def getNextAttribute(self, aid):
        aid1 = self._nextSibling[aid / self._botCap][aid % self._botCap]
        if ((aid1 > self._root) and (self._isAttribute[aid1 / self._botCap][aid1 % self._botCap])):
            return aid1
        else:
            return NULL_NODE

    # Get the attribute value.
    # @param    aid    attribute id
    def getAttributeValue(self, aid):
        cid = self._firstChild[aid / self._botCap][aid % self._botCap]
        index = self._valueIndex[cid / self._botCap][cid % self._botCap]
        if (index > 0):
            return self._value[index / self._botCap][index % self._botCap]
        else:
            return ""

    # Get the hash value of a node.
    # @param    eid    element id
    def getHashValue(self, eid):
        return self._hashValue[eid / self._botCap][eid % self._botCap]

    # Get the CDATA section position list of a text node.
    # @param    eid    element id
    # @return    position list which is a vector or None if no CDATA
    def getCDATA(self, eid):
        return self._cdataTable[eid]

    # Get the childern count of a node.
    # @param    eid    element id
    def getChildrenCount(self, eid):
        return self._childrenCount[eid / self._botCap][eid % self._botCap]

    # Get the # of all decendents of a node.
    # @param    eid    element id
    def getDecendentsCount(self, eid):
        topid = eid / self._botCap
        botid = eid % self._botCap
        count = self._childrenCount[topid][botid]
        if (count == 0):
            return 0

        cid = self._firstChild[topid][botid]
        while (cid > NULL_NODE):
            count += self.getDecendentsCount(cid)
            cid = self._nextSibling[cid / self._botCap][cid % self._botCap]

        return count

    # Get the value index of a node
    # @param    eid    element id
    def getValueIndex(self, eid):
        return self._valueIndex[eid / self._botCap][eid % self._botCap]

    # Get the value of a leaf node
    # @param    index    value index
    def getValue(self, index):
        return self._value[index / self._botCap][index % self._botCap]

    # Get the tag of an element node
    # @param    eid    element id
    def getTag(self, eid):
        index = self._valueIndex[eid / self._botCap][eid % self._botCap]
        return    self._value[0][index]

    # Get the text value of a leaf node
    # @param    eid    element id
    def getText(self, eid):
        index = self._valueIndex[eid / self._botCap][eid % self._botCap]
        if (index >= self._botCap):
            return self._value[index / self._botCap][index % self._botCap]
        else:
            return ""

    # Check if a node an element node.
    # @param    eid    element id
    def isElement(self, eid):
        vindex = self._valueIndex[eid / self._botCap][eid % self._botCap]
        if (vindex < self._botCap):
            return True
        else:
            return False

    # Check if a node is an attribute node.
    # @param    eid    element id
    def isAttribute(self, eid):
        return self._isAttribute[eid / self._botCap][eid % self._botCap]

    # Check if a node an leaf text node.
    # @param    edi    element id
    def isLeaf(self, eid):
        index = self._valueIndex[eid / self._botCap][eid % self._botCap]
        if (index < self._botCap):
            return False
        else:
            return True

    # End  -- methods for accessing a tree.

    # For testing purpose.
    def dump(self, eid=None):
        if eid:
            topid = eid / self._botCap
            botid = eid % self._botCap
            vid = self._valueIndex[topid][botid]
            vtopid = vid / self._botCap
            vbotid = vid % self._botCap
            print eid + "\t" + \
                       self._firstChild[topid][botid] + "\t" + \
                       self._nextSibling[topid][botid] + "\t" + \
                       self._isAttribute[topid][botid] + "\t" + \
                       self._childrenCount[topid][botid] + "\t" + \
                       self._hashValue[topid][botid] + "\t" + \
                       self._matching[topid][botid] + "\t" + \
                       self._value[vtopid][vbotid]
        else:
            print "eid\tfirstC\tnextS\tattr?\tcCount\thash\tmatch\tvalue"
            for i in range(self._root, self._elementIndex + 1):
                topid = i / self._botCap
                botid = i % self._botCap
                vid = self._valueIndex[topid][botid]
                vtopid = vid / self._botCap
                vbotid = vid % self._botCap
                print i + "\t" + \
                           self._firstChild[topid][botid] + "\t" + \
                           self._nextSibling[topid][botid] + "\t" + \
                           self._isAttribute[topid][botid] + "\t" + \
                           self._childrenCount[topid][botid] + "\t" + \
                           self._hashValue[topid][botid] + "\t" + \
                           self._matching[topid][botid] + "\t" + \
                           self._value[vtopid][vbotid]