From 11ffccf2a5aa5fb652945ffc8dda9b8dfdf58ae8 Mon Sep 17 00:00:00 2001 From: Anton Korobeynikov Date: Sun, 16 Dec 2007 01:27:04 +0000 Subject: [PATCH] Provide GraphTraits and DOTGraphTraits interface for Trie. Retoss private/public stuff. Make copy ctor and operator= private. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@45067 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/Trie.h | 163 +++++++++++++++++++++++++++------------- 1 file changed, 109 insertions(+), 54 deletions(-) diff --git a/include/llvm/ADT/Trie.h b/include/llvm/ADT/Trie.h index 21cc5fe17f4..71a0c8ea94b 100644 --- a/include/llvm/ADT/Trie.h +++ b/include/llvm/ADT/Trie.h @@ -15,7 +15,9 @@ #ifndef LLVM_ADT_TRIE_H #define LLVM_ADT_TRIE_H -#include +#include "llvm/ADT/GraphTraits.h" +#include "llvm/Support/DOTGraphTraits.h" + #include namespace llvm { @@ -24,12 +26,15 @@ namespace llvm { // - Labels are usually small, maybe it's better to use SmallString // - Should we use char* during construction? // - Should we templatize Empty with traits-like interface? -// - GraphTraits interface template class Trie { + friend class GraphTraits >; + friend class DOTGraphTraits >; +public: class Node { friend class Trie; + friend class GraphTraits >; typedef enum { Same = -3, @@ -53,43 +58,10 @@ class Trie { std::string Label; Payload Data; NodeVector Children; - public: - inline explicit Node(const Payload& data, const std::string& label = ""): - Label(label), Data(data) { } - - inline Node(const Node& n) { - Data = n.Data; - Children = n.Children; - Label = n.Label; - } - inline Node& operator=(const Node& n) { - if (&n != this) { - Data = n.Data; - Children = n.Children; - Label = n.Label; - } - - return *this; - } - - inline bool isLeaf() const { return Children.empty(); } - - inline const Payload& getData() const { return Data; } - inline void setData(const Payload& data) { Data = data; } - - inline void setLabel(const std::string& label) { Label = label; } - inline const std::string& getLabel() const { return Label; } - -#if 0 - inline void dump() { - std::cerr << "Node: " << this << "\n" - << "Label: " << Label << "\n" - << "Children:\n"; - for (NodeVectorIter I = Children.begin(), E = Children.end(); I != E; ++I) - std::cerr << (*I)->Label << "\n"; - } -#endif + // Do not implement + Node(const Node&); + Node& operator=(const Node&); inline void addEdge(Node* N) { if (Children.empty()) @@ -102,16 +74,6 @@ class Trie { } } - inline Node* getEdge(char Id) { - Node* fNode = NULL; - NodeVectorIter I = std::lower_bound(Children.begin(), Children.end(), - Id, NodeCmp()); - if (I != Children.end() && (*I)->Label[0] == Id) - fNode = *I; - - return fNode; - } - inline void setEdge(Node* N) { char Id = N->Label[0]; NodeVectorIter I = std::lower_bound(Children.begin(), Children.end(), @@ -141,13 +103,42 @@ class Trie { } else // s and Label have common (possible empty) part, return its length return (QueryResult)i; } + + public: + inline explicit Node(const Payload& data, const std::string& label = ""): + Label(label), Data(data) { } + + inline const Payload& data() const { return Data; } + inline void setData(const Payload& data) { Data = data; } + + inline const std::string& label() const { return Label; } + +#if 0 + inline void dump() { + std::cerr << "Node: " << this << "\n" + << "Label: " << Label << "\n" + << "Children:\n"; + + for (NodeVectorIter I = Children.begin(), E = Children.end(); I != E; ++I) + std::cerr << (*I)->Label << "\n"; + } +#endif + + inline Node* getEdge(char Id) { + Node* fNode = NULL; + NodeVectorIter I = std::lower_bound(Children.begin(), Children.end(), + Id, NodeCmp()); + if (I != Children.end() && (*I)->Label[0] == Id) + fNode = *I; + + return fNode; + } }; +private: std::vector Nodes; Payload Empty; - inline Node* getRoot() const { return Nodes[0]; } - inline Node* addNode(const Payload& data, const std::string label = "") { Node* N = new Node(data, label); Nodes.push_back(N); @@ -172,6 +163,10 @@ class Trie { return nNode; } + // Do not implement + Trie(const Trie&); + Trie& operator=(const Trie&); + public: inline explicit Trie(const Payload& empty):Empty(empty) { addNode(Empty); @@ -181,6 +176,8 @@ public: delete Nodes[i]; } + inline Node* getRoot() const { return Nodes[0]; } + bool addString(const std::string& s, const Payload& data) { Node* cNode = getRoot(); Node* tNode = NULL; @@ -202,7 +199,7 @@ public: assert(0 && "Impossible!"); return false; case Node::LabelIsPrefix: - s1 = s1.substr(nNode->getLabel().length()); + s1 = s1.substr(nNode->label().length()); cNode = nNode; break; default: @@ -239,7 +236,7 @@ public: assert(0 && "Impossible!"); return Empty; case Node::LabelIsPrefix: - s1 = s1.substr(nNode->getLabel().length()); + s1 = s1.substr(nNode->label().length()); cNode = nNode; break; default: @@ -249,11 +246,69 @@ public: return Empty; } - return tNode->getData(); + return tNode->data(); + } + +}; + +template +struct GraphTraits > { + typedef typename Trie::Node NodeType; + typedef typename std::vector::iterator ChildIteratorType; + + static inline NodeType *getEntryNode(const Trie& T) { + return T.getRoot(); + } + + static inline ChildIteratorType child_begin(NodeType *N) { + return N->Children.begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { + return N->Children.end(); + } + + typedef typename std::vector::const_iterator nodes_iterator; + + static inline nodes_iterator nodes_begin(const Trie& G) { + return G.Nodes.begin(); + } + static inline nodes_iterator nodes_end(const Trie& G) { + return G.Nodes.end(); + } + +}; + +template +struct DOTGraphTraits > : public DefaultDOTGraphTraits { + typedef typename Trie::Node NodeType; + typedef typename GraphTraits >::ChildIteratorType EdgeIter; + + static std::string getGraphName(const Trie& T) { + return "Trie"; + } + + static std::string getNodeLabel(NodeType* Node, const Trie& T) { + if (T.getRoot() == Node) + return ""; + else + return Node->label(); + } + + static std::string getEdgeSourceLabel(NodeType* Node, EdgeIter I) { + NodeType* N = *I; + return N->label().substr(0, 1); + } + + static std::string getNodeAttributes(const NodeType* Node, + const Trie& T) { + if (Node->data() != T.Empty) + return "color=blue"; + + return ""; } }; -} +} // end of llvm namespace #endif // LLVM_ADT_TRIE_H -- 2.34.1