Debian Codegraph @

src/xml/davix_ptree.hpp

raw
1 /*
2 * This File is part of Davix, The IO library for HTTP based protocols
3 * Copyright (C) CERN 2013
4 * Author: Adrien Devresse <[email protected]>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 *
20 */
21
22 #ifndef DAVIX_PTREE_HPP
23 #define DAVIX_PTREE_HPP
24
25 #include <algorithm>
26 #include <functional>
27 #include <iostream>
28 #include <vector>
29
30 namespace Davix {
31
32 template <class KeyType, class DataType, class PredEqualKey = std::equal_to<KeyType>, class PredEqualData = std::equal_to<DataType> >
33 class BasicPtree{
34 public:
35 typedef BasicPtree<KeyType, DataType, PredEqualKey, PredEqualData> tree_type;
36 typedef tree_type* ptr_type;
37 typedef std::vector<tree_type> ChildrenList;
38 typedef typename ChildrenList::const_iterator const_iterator;
39 typedef typename ChildrenList::iterator iterator;
40
41
42 BasicPtree() :
43 _key(KeyType()),
44 _data(DataType()),
45 _children(ChildrenList()),
46 _meta_data(NULL),
47 _data_cmp(PredEqualData()),
48 _key_cmp(PredEqualKey())
49 {}
50 BasicPtree(const KeyType & key, const DataType & data, const ChildrenList & l = ChildrenList(), void* meta = NULL) :
51 _key(key), _data(data), _children(l), _meta_data(meta){}
52 BasicPtree(const BasicPtree & orig) : _key(orig._key), _data(orig._data), _children(orig._children), _meta_data(orig._meta_data) {}
53 ~BasicPtree(){}
54
55 inline const_iterator beginChildren() const{
56 return _children.begin();
57 }
58
59 inline iterator beginChildren(){
60 return _children.begin();
61 }
62
63
64 inline const_iterator endChildren() const{
65 return _children.end();
66 }
67
68 inline iterator endChildren(){
69 return _children.end();
70 }
71
72 inline void clearChildren(){
73 _children.clear();
74 }
75
76 inline const KeyType & getKey() const {
77 return _key;
78 }
79
80 inline const DataType & getData() const {
81 return _data;
82 }
83
84 inline void* getMeta(){
85 return _meta_data;
86 }
87
88 inline void setMeta(void* meta){
89 _meta_data = meta;
90 }
91
92 inline BasicPtree & addChild(const BasicPtree & child){
93 _children.push_back(child);
94 return _children.back();
95 }
96
97 inline bool compareData(const BasicPtree & other) const{
98 return ( _data_cmp(_data, other._data));
99 }
100
101 inline bool compareKey(const BasicPtree & other) const{
102 return ( _key_cmp(_key, other._key));
103 }
104
105 inline int compareNode(const BasicPtree & other) const{
106 return (compareKey(other) && compareData(other));
107 }
108
109 inline bool matchTree(const BasicPtree & rtree) const{
110 if(compareNode(rtree) == false){
111 return false;
112 }
113
114 for(const_iterator it_rtree = rtree.beginChildren(); it_rtree != rtree.endChildren(); ++it_rtree){
115 bool found=false;
116 for(const_iterator it = beginChildren(); it != endChildren(); ++it){
117 if(it->matchTree(*it_rtree) ){
118 found = true;
119 break;
120 }
121 }
122 if(!found){ // failed to find rtree node in main tree
123 return false;
124 }
125 }
126 std::cout << " end node " << rtree._data << std::endl;
127 return true;
128 }
129
130 ///
131 /// Match an order chain of node as a subtree
132 /// return the chain matched
133 inline std::vector<ptr_type> findChain(const std::vector<tree_type> & chain){
134 std::vector<ptr_type> res;
135 res.reserve(chain.size());
136 _findChainRec(chain.begin(), chain.end(), res);
137 return res;
138 }
139
140 protected:
141 // members
142 KeyType _key;
143 DataType _data;
144 ChildrenList _children;
145 void* _meta_data;
146 // cmp
147 PredEqualData _data_cmp;
148 PredEqualKey _key_cmp;
149
150 bool _findChainRec(typename std::vector<tree_type>::const_iterator begin,
151 typename std::vector<tree_type>::const_iterator end,
152 std::vector<tree_type::ptr_type> & res){
153 if(begin == end)
154 return true;
155
156 if( compareNode(*begin)){
157 res.push_back(this);
158 begin++;
159 for(iterator it = beginChildren(); it != endChildren(); ++it){
160 if( it->_findChainRec(begin, end, res) == true){
161 return true;
162 }
163 }
164 }
165 return false;
166 }
167 };
168
169
170 namespace Xml{
171
172 enum NodeType{
173 ElementStart=0x01,
174 CData=0x02,
175 Attribute=0x03,
176 Comment=0x04
177 };
178
179
180 typedef BasicPtree<NodeType, std::string> XmlPTree;
181
182
183 } // namespace Xml
184
185 } // namespace Davix
186
187 #endif // DAVIX_PTREE_HPP