21 #ifndef TRIE_WITH_POLICY_H_
22 #define TRIE_WITH_POLICY_H_
30 template<
typename FullKey,
31 typename PayloadTraits,
37 typedef trie< FullKey,
39 typename PolicyTraits::policy_hook_type >
parent_trie;
44 typedef typename PolicyTraits::template policy<
47 typename PolicyTraits::template container_hook<parent_trie>::type >::type policy_container;
56 inline std::pair< iterator, bool >
57 insert (
const FullKey &key,
typename PayloadTraits::insert_type payload)
59 std::pair<iterator, bool> item =
60 trie_.insert (key, payload);
64 bool ok = policy_.insert (s_iterator_to (item.first));
68 return std::make_pair (end (),
false);
73 return std::make_pair (s_iterator_to (item.first),
false);
80 erase (
const FullKey &key)
84 boost::tie (foundItem, reachLast, lastItem) = trie_.
find (key);
86 if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
95 if (node == end ())
return;
97 policy_.erase (s_iterator_to (node));
108 template<
typename Modifier>
110 modify (
iterator position, Modifier mod)
112 if (position == end ())
return false;
113 if (position->payload () == PayloadTraits::empty_payload)
return false;
115 mod (*position->payload ());
116 policy_.update (position);
128 boost::tie (foundItem, reachLast, lastItem) = trie_.
find (key);
130 if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
144 boost::tie (foundItem, reachLast, lastItem) = trie_.
find (key);
145 if (foundItem != trie_.end ())
147 policy_.lookup (s_iterator_to (foundItem));
155 template<
class Predicate>
161 boost::tie (foundItem, reachLast, lastItem) = trie_.
find_if (key, pred);
162 if (foundItem != trie_.end ())
164 policy_.lookup (s_iterator_to (foundItem));
187 boost::tie (foundItem, reachLast, lastItem) = trie_.
find (key);
190 if (lastItem == trie_.end ())
195 if (foundItem == trie_.end ())
197 foundItem = lastItem->
find ();
199 policy_.lookup (s_iterator_to (foundItem));
211 template<
class Predicate>
217 boost::tie (foundItem, reachLast, lastItem) = trie_.
find (key);
220 if (lastItem == trie_.end ())
225 foundItem = lastItem->
find_if (pred);
226 if (foundItem == trie_.end ())
230 policy_.lookup (s_iterator_to (foundItem));
245 template<
class Predicate>
251 boost::tie (foundItem, reachLast, lastItem) = trie_.
find (key);
254 if (lastItem == trie_.end ())
260 if (foundItem == trie_.end ())
264 policy_.lookup (s_iterator_to (foundItem));
273 iterator end ()
const
279 getTrie ()
const {
return trie_; }
282 getTrie () {
return trie_; }
284 const policy_container &
285 getPolicy ()
const {
return policy_; }
288 getPolicy () {
return policy_; }
290 static inline iterator
291 s_iterator_to (
typename parent_trie::iterator item)
301 mutable policy_container policy_;
308 #endif // TRIE_WITH_POLICY_H_
boost::tuple< iterator, bool, iterator > find(const FullKey &key)
Perform the longest prefix match.
iterator longest_prefix_match_if(const FullKey &key, Predicate pred)
Find a node that has the longest common prefix with key (FIB/PIT lookup)
const iterator find_if_next_level(Predicate pred)
Find next payload of the sub-trie satisfying the predicate.
iterator deepest_prefix_match_if(const FullKey &key, Predicate pred)
Find a node that has prefix at least as the key.
iterator longest_prefix_match(const FullKey &key)
Find a node that has the longest common prefix with key (FIB/PIT lookup)
boost::tuple< iterator, bool, iterator > find_if(const FullKey &key, Predicate pred)
Perform the longest prefix match satisfying preficate.
iterator deepest_prefix_match_if_next_level(const FullKey &key, Predicate pred)
Find a node that has prefix at least as the key.
Class to representing binary blob of NDN name component.
iterator deepest_prefix_match(const FullKey &key)
Const version of the longest common prefix match (semi-const, because there could be update of the po...
iterator erase()
Removes payload (if it exists) and if there are no children, prunes parents trie. ...
iterator find_exact(const FullKey &key)
Find a node that has the exact match with the key.