Lines Matching defs:node
126 // TRIE node for suffix strings in the label reference sequence.
129 // as necessary. The trie node for a (possibly) empty string of label
131 // roots node (for the empty string) thus contains the simple distribution of
134 struct Node {
135 Node(LabelInfo* in_edge, Node* prev)
141 Node* prev_; // Node at shorter length.
144 typedef std::map<LabelInfo*, Node*> Edges;
147 std::list<Node*> edges_in_frequency_order;
157 static std::string ToString(Node* node) {
159 for (Node* n = node; n->prev_; n = n->prev_)
172 s += base::StringPrintf("%u", node->count_);
174 s += base::Uint64ToString(node->edges_in_frequency_order.size());
182 bool operator()(Node* a, Node* b) const {
190 bool operator()(Node* a, Node* b) const {
191 // (Maybe tie-break on total count, followed by lowest assigned node indexes
203 typedef std::set<Node*, OrderNodeByWeightDecreasing> NodeQueue;
226 Node* node = *worklist_.begin();
227 node->in_queue_ = false;
228 worklist_.erase(node);
229 TrySolveNode(node);
237 void AddToQueue(Node* node) {
238 if (node->length_ >= 10) {
239 VLOG(4) << "Length clipped " << ToString(node->prev_);
242 if (node->in_queue_) {
243 LOG(ERROR) << "Double add " << ToString(node);
247 ExtendNode(node, p_trace_);
248 // SkipCommittedLabels(node);
249 if (node->edges_in_frequency_order.empty())
251 node->in_queue_ = true;
252 worklist_.insert(node);
255 void SkipCommittedLabels(Node* node) {
256 ExtendNode(node, p_trace_);
258 while (!node->edges_in_frequency_order.empty() &&
259 node->edges_in_frequency_order.front()->in_edge_->assignment_) {
261 node->edges_in_frequency_order.pop_front();
264 VLOG(4) << "Skipped " << skipped << " at " << ToString(node);
267 void TrySolveNode(Node* p_node) {
268 Node* front = p_node->edges_in_frequency_order.front();
277 // assignment(s) or move node to unsolved list
279 Node* m_node = FindModelNode(p_node);
282 VLOG(2) << "Can't find model node";
297 Node* m_match = m_node->edges_in_frequency_order.front();
298 Node* p_match = p_node->edges_in_frequency_order.front();
323 AddToQueue(p_node); // and more matches within this node
495 Node* FindModelNode(Node* node) {
496 if (node->prev_ == NULL)
499 Node* m_parent = FindModelNode(node->prev_);
506 LabelInfo* p_label = node->in_edge_;
513 Node::Edges::iterator e = m_parent->edges_.find(m_label);
522 Node* MakeRootNode(const Trace& trace) {
523 Node* node = new Node(NULL, NULL);
524 all_nodes_.push_back(node);
526 ++node->count_;
527 node->places_.push_back(i);
529 return node;
532 void ExtendNode(Node* node, const Trace& trace) {
533 // Make sure trie is filled in at this node.
534 if (node->Extended())
536 for (size_t i = 0; i < node->places_.size(); ++i) {
537 uint32 index = node->places_.at(i);
540 Node*& slot = node->edges_[item];
542 slot = new Node(item, node);
544 node->edges_in_frequency_order.push_back(slot);
550 node->edges_in_frequency_order.sort(OrderNodeByCountDecreasing());
555 Node* m_root_;
556 Node* p_root_;
561 std::vector<Node*> all_nodes_;
