1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- llvm/ADT/Trie.h ---- Generic trie structure --------------*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This class defines a generic trie structure. The trie structure 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// is immutable after creation, but the payload contained within it is not. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ADT_TRIE_H 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ADT_TRIE_H 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/GraphTraits.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/DOTGraphTraits.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cassert> 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <vector> 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// FIXME: 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// - Labels are usually small, maybe it's better to use SmallString 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// - Should we use char* during construction? 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// - Should we templatize Empty with traits-like interface? 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class Payload> 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass Trie { 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman friend class GraphTraits<Trie<Payload> >; 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman friend class DOTGraphTraits<Trie<Payload> >; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class Node { 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman friend class Trie; 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<Node*> NodeVectorType; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename NodeVectorType::iterator iterator; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename NodeVectorType::const_iterator const_iterator; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman enum QueryResult { 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Same = -3, 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StringIsPrefix = -2, 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LabelIsPrefix = -1, 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DontMatch = 0, 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman HaveCommonPart 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct NodeCmp { 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator() (Node* N1, Node* N2) { 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return (N1->Label[0] < N2->Label[0]); 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator() (Node* N, char Id) { 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return (N->Label[0] < Id); 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string Label; 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Payload Data; 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodeVectorType Children; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Do not implement 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node(const Node&); 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node& operator=(const Node&); 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline void addEdge(Node* N) { 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Children.empty()) 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Children.push_back(N); 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else { 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator I = std::lower_bound(Children.begin(), Children.end(), 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N, NodeCmp()); 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: no dups are allowed 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Children.insert(I, N); 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline void setEdge(Node* N) { 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char Id = N->Label[0]; 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator I = std::lower_bound(Children.begin(), Children.end(), 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Id, NodeCmp()); 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I != Children.end() && "Node does not exists!"); 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman *I = N; 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman QueryResult query(const std::string& s) const { 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned i, l; 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned l1 = s.length(); 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned l2 = Label.length(); 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Find the length of common part 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman l = std::min(l1, l2); 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman i = 0; 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while ((i < l) && (s[i] == Label[i])) 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++i; 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i == l) { // One is prefix of another, find who is who 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (l1 == l2) 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Same; 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (i == l1) 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return StringIsPrefix; 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return LabelIsPrefix; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else // s and Label have common (possible empty) part, return its length 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return (QueryResult)i; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline explicit Node(const Payload& data, const std::string& label = ""): 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Label(label), Data(data) { } 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const Payload& data() const { return Data; } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline void setData(const Payload& data) { Data = data; } 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const std::string& label() const { return Label; } 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#if 0 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline void dump() { 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman llvm::cerr << "Node: " << this << "\n" 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << "Label: " << Label << "\n" 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << "Children:\n"; 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (iterator I = Children.begin(), E = Children.end(); I != E; ++I) 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman llvm::cerr << (*I)->Label << "\n"; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Node* getEdge(char Id) { 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* fNode = NULL; 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator I = std::lower_bound(Children.begin(), Children.end(), 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Id, NodeCmp()); 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I != Children.end() && (*I)->Label[0] == Id) 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman fNode = *I; 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return fNode; 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline iterator begin() { return Children.begin(); } 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const_iterator begin() const { return Children.begin(); } 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline iterator end () { return Children.end(); } 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const_iterator end () const { return Children.end(); } 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline size_t size () const { return Children.size(); } 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline bool empty() const { return Children.empty(); } 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const Node* &front() const { return Children.front(); } 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Node* &front() { return Children.front(); } 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const Node* &back() const { return Children.back(); } 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Node* &back() { return Children.back(); } 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<Node*> Nodes; 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Payload Empty; 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Node* addNode(const Payload& data, const std::string label = "") { 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* N = new Node(data, label); 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Nodes.push_back(N); 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return N; 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Node* splitEdge(Node* N, char Id, size_t index) { 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* eNode = N->getEdge(Id); 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(eNode && "Node doesn't exist"); 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const std::string &l = eNode->Label; 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(index > 0 && index < l.length() && "Trying to split too far!"); 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string l1 = l.substr(0, index); 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string l2 = l.substr(index); 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* nNode = addNode(Empty, l1); 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman N->setEdge(nNode); 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman eNode->Label = l2; 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman nNode->addEdge(eNode); 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return nNode; 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Do not implement 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Trie(const Trie&); 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Trie& operator=(const Trie&); 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline explicit Trie(const Payload& empty):Empty(empty) { 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman addNode(Empty); 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline ~Trie() { 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman delete Nodes[i]; 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline Node* getRoot() const { return Nodes[0]; } 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool addString(const std::string& s, const Payload& data); 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Payload& lookup(const std::string& s) const; 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Define this out-of-line to dissuade the C++ compiler from inlining it. 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class Payload> 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool Trie<Payload>::addString(const std::string& s, const Payload& data) { 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* cNode = getRoot(); 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* tNode = NULL; 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string s1(s); 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (tNode == NULL) { 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char Id = s1[0]; 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Node* nNode = cNode->getEdge(Id)) { 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename Node::QueryResult r = nNode->query(s1); 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (r) { 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::Same: 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::StringIsPrefix: 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Currently we don't allow to have two strings in the trie one 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // being a prefix of another. This should be fixed. 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(0 && "FIXME!"); 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::DontMatch: 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(0 && "Impossible!"); 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::LabelIsPrefix: 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman s1 = s1.substr(nNode->label().length()); 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cNode = nNode; 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman nNode = splitEdge(cNode, Id, r); 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman tNode = addNode(data, s1.substr(r)); 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman nNode->addEdge(tNode); 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman tNode = addNode(data, s1); 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cNode->addEdge(tNode); 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class Payload> 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanconst Payload& Trie<Payload>::lookup(const std::string& s) const { 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* cNode = getRoot(); 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node* tNode = NULL; 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::string s1(s); 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (tNode == NULL) { 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman char Id = s1[0]; 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Node* nNode = cNode->getEdge(Id)) { 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename Node::QueryResult r = nNode->query(s1); 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (r) { 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::Same: 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman tNode = nNode; 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::StringIsPrefix: 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Empty; 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::DontMatch: 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(0 && "Impossible!"); 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Empty; 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Node::LabelIsPrefix: 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman s1 = s1.substr(nNode->label().length()); 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cNode = nNode; 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Empty; 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Empty; 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return tNode->data(); 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class Payload> 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstruct GraphTraits<Trie<Payload> > { 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef Trie<Payload> TrieType; 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename TrieType::Node NodeType; 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename NodeType::iterator ChildIteratorType; 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline NodeType *getEntryNode(const TrieType& T) { 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return T.getRoot(); 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_begin(NodeType *N) { 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return N->begin(); 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename std::vector<NodeType*>::const_iterator nodes_iterator; 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline nodes_iterator nodes_begin(const TrieType& G) { 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return G.Nodes.begin(); 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline nodes_iterator nodes_end(const TrieType& G) { 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return G.Nodes.end(); 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<class Payload> 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstruct DOTGraphTraits<Trie<Payload> > : public DefaultDOTGraphTraits { 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename Trie<Payload>::Node NodeType; 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename GraphTraits<Trie<Payload> >::ChildIteratorType EdgeIter; 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static std::string getGraphName(const Trie<Payload>& T) { 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return "Trie"; 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static std::string getNodeLabel(NodeType* Node, const Trie<Payload>& T) { 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (T.getRoot() == Node) 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return "<Root>"; 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Node->label(); 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static std::string getEdgeSourceLabel(NodeType* Node, EdgeIter I) { 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NodeType* N = *I; 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return N->label().substr(0, 1); 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static std::string getNodeAttributes(const NodeType* Node, 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Trie<Payload>& T) { 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Node->data() != T.Empty) 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return "color=blue"; 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return ""; 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // end of llvm namespace 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif // LLVM_ADT_TRIE_H 337