parsetree.h

Linux下比较早的基于命令行的DVD播放器

//
// Copyright (c) 2003 by Istv醤 V醨adi
//
// This file is part of dxr3Player, a DVD player written specifically 
// for the DXR3 (aka Hollywood+) decoder card.

// 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 2 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, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#ifndef DXR3PLAYER_UTIL_PARSETREE_H
#define DXR3PLAYER_UTIL_PARSETREE_H
//------------------------------------------------------------------------------

#include "util/DefaultAllocator.h"

#include <map>

#include <cassert>

//------------------------------------------------------------------------------

/**
 * Generic parse tree. It can be used to parse "strings" of a given
 * type of objects and retrieve a value if a valid string is found.
 */
template <typename charT, typename valueT>
class ParseTree
{
private:
    class Node;
    class NodeList;
    
public:
    /**
     * Parser for the tree. You can add individual "characters" to
     * it. If the character can be a continuation of the previous
     * ones, but not leads to a value yet, it is stored. If it leads
     * to value, the value is returned, and the current sequence is
     * discarded. If the character is invalid, the current sequence is
     * discarded too.
     */
    class Parser
    {
    private:
        /**
         * The parse tree we belong to.
         */
        const ParseTree<charT, valueT>& parseTree;

        /**
         * The current node list.
         */
        const NodeList* nodeList;

    public:
        /**
         * Construct a parser for the given tree.
         */
        explicit Parser(const ParseTree<charT, valueT>& parseTree);

        /**
         * Add a character and return a value if valid.
         */
        valueT add(charT c);
    };

    friend class Parser;

private:
    /**
     * A list of nodes, i.e. mapping from characters to subsequent
     * nodes.
     */
    class NodeList
    {
    private:
        /**
         * The mapping from characters to nodes.
         */
        std::map<charT, Node*, std::less<charT>, DefaultAllocator > nodes;

    public:
        /**
         * Destroy the node list.
         */
        ~NodeList();

        /**
         * Reset the node list by deleting all nodes.
         */
        void reset();

        /**
         * Find a node for the given character.
         */
        Node* findNode(charT c) const;

        /**
         * Get a node with the given character. If it does not exist,
         * create it.
         */
        Node& getNode(charT c, valueT invalidValue);
    };

    /**
     * A character node.
     */
    class Node {
    private:
        /**
         * The value belonging to this node.
         */
        valueT value;

        /**
         * The child nodes.
         */
        NodeList* children;

    public:
        /**
         * Construct a node with the given character.
         */
        Node(valueT value);

        /**
         * Destroy the node.
         */
        ~Node();

        /**
         * Set the value of the node.
         */
        void setValue(valueT v);

        /**
         * Get the value of the node.
         */
        valueT getValue() const;

        /**
         * Find the children node list.
         */
        NodeList* findChildren() const;

        /**
         * Get the children node list.
         */
        NodeList& getChildren();
    };

    /**
     * The root of the nodes.
     */
    NodeList root;
    
    /**
     * The invalid value.
     */
    valueT invalidValue;

public:
    /**
     * Construct the parse tree.
     */
    ParseTree(valueT invalidValue);

    /**
     * Reset the tree.
     */
    void reset();

    /**
     * Add a value for the given string.
     */
    void addValue(const charT* str, size_t len, valueT value);

    /**
     * Find the first value for the given string. It finishes the
     * search as soon as a node with a valid value is found. If no
     * node is found, invalidValue is returned. Otherwise str will be
     * set to point after the character which stopped the search, and
     * len will be adjusted accordingly
     */
    valueT findFirstValue(const charT*& str, size_t& len) const;
};

//------------------------------------------------------------------------------
// Template definitions
//------------------------------------------------------------------------------

template <typename charT, typename valueT>
ParseTree<charT, valueT>::NodeList::~NodeList()
{
    reset();
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
void ParseTree<charT, valueT>::NodeList::reset()
{
    for(typename std::map<charT, Node*>::const_iterator i = nodes.begin();
        i!=nodes.end(); ++i)
    {
        delete i->second;
    }

    nodes.clear();
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
typename ParseTree<charT, valueT>::Node* 
ParseTree<charT, valueT>::NodeList::findNode(charT c) const
{
    typename std::map<charT, Node*>::const_iterator i = nodes.find(c);
    return (i==nodes.end()) ? 0 : i->second;
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
typename ParseTree<charT, valueT>::Node& 
ParseTree<charT, valueT>::NodeList::getNode(charT c, valueT invalidValue)
{
    Node* node = findNode(c);
    
    if (node==0) {
        node = new Node(invalidValue);
        nodes[c] = node;
    }

    return *node;
}

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template <typename charT, typename valueT>
ParseTree<charT, valueT>::Node::Node(valueT value) :
    value(value),
    children(0)
{
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
ParseTree<charT, valueT>::Node::~Node() 
{
    delete children;
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
void ParseTree<charT, valueT>::Node::setValue(valueT v)
{
    value = v;
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
inline valueT ParseTree<charT, valueT>::Node::getValue() const
{
    return value;
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
inline typename ParseTree<charT, valueT>::NodeList*
ParseTree<charT, valueT>::Node::findChildren() const
{
    return children;
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
typename ParseTree<charT, valueT>::NodeList& 
ParseTree<charT, valueT>::Node::getChildren()
{
    if (children==0) children = new NodeList();
    return *children;
}

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template <typename charT, typename valueT>
ParseTree<charT, valueT>::ParseTree(valueT invalidValue) :
    invalidValue(invalidValue)
{
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
void ParseTree<charT, valueT>::reset()
{
    root.reset();
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
void ParseTree<charT, valueT>::addValue(const charT* str, size_t len,
                                        valueT value)
{
    assert(value!=invalidValue);

    Node* node = 0;
    for(; len>0; ++str, --len) {
        NodeList& nodeList = (node==0) ? root : node->getChildren();
        node = &nodeList.getNode(*str, invalidValue);
    }
    assert(node!=0);

    node->setValue(value);
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
valueT ParseTree<charT, valueT>::
findFirstValue(const charT*& str, size_t& len) const
{
    const char* str1 = str;
    size_t len1 = len;

    const Node* node = 0;

    for(; len1>0; ++str1, --len1) {
        const NodeList* nodeList = (node==0) ? &root : node->findChildren();
        if (nodeList==0) return invalidValue;
        
        node = nodeList->findNode(*str1);
        if (node==0) return invalidValue;
        
        valueT value = node->getValue();
        if (value!=invalidValue) {
            str = ++str1;
            len = --len1;
            return value;
        }
    }

    return invalidValue;
}

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template <typename charT, typename valueT>
inline ParseTree<charT, valueT>::Parser::
Parser(const ParseTree<charT, valueT>& parseTree) :
    parseTree(parseTree),
    nodeList(&parseTree.root)
{
}

//------------------------------------------------------------------------------

template <typename charT, typename valueT>
valueT ParseTree<charT, valueT>::Parser::add(charT c)
{
    const Node* node = nodeList->findNode(c);
    if (node==0) {
        if (nodeList!=&parseTree.root) {
            nodeList = &parseTree.root;
            return add(c);
        } else {
            return parseTree.invalidValue;
        }
    } else {
        nodeList = node->findChildren();
        if (nodeList==0) {
            nodeList = &parseTree.root;
            return node->getValue();
        } else {
            return parseTree.invalidValue;
        }
    }
}

//------------------------------------------------------------------------------
#endif // DXR3PLAYER_UTIL_PARSETREE_H

// Local variables:
// mode: c++
// End: