1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "utils/grammar/parsing/parse-tree.h"
18
19 #include <algorithm>
20 #include <stack>
21
22 namespace libtextclassifier3::grammar {
23
Traverse(const ParseTree * root,const std::function<bool (const ParseTree *)> & node_fn)24 void Traverse(const ParseTree* root,
25 const std::function<bool(const ParseTree*)>& node_fn) {
26 std::stack<const ParseTree*> open;
27 open.push(root);
28
29 while (!open.empty()) {
30 const ParseTree* node = open.top();
31 open.pop();
32 if (!node_fn(node) || node->IsLeaf()) {
33 continue;
34 }
35 open.push(node->rhs2);
36 if (node->rhs1 != nullptr) {
37 open.push(node->rhs1);
38 }
39 }
40 }
41
SelectAll(const ParseTree * root,const std::function<bool (const ParseTree *)> & pred_fn)42 std::vector<const ParseTree*> SelectAll(
43 const ParseTree* root,
44 const std::function<bool(const ParseTree*)>& pred_fn) {
45 std::vector<const ParseTree*> result;
46 Traverse(root, [&result, pred_fn](const ParseTree* node) {
47 if (pred_fn(node)) {
48 result.push_back(node);
49 }
50 return true;
51 });
52 return result;
53 }
54
55 } // namespace libtextclassifier3::grammar
56