diff --git a/ndn-cpp/trie/detail/functor-hook.h b/ndn-cpp/trie/detail/functor-hook.h
new file mode 100644
index 0000000..f34969c
--- /dev/null
+++ b/ndn-cpp/trie/detail/functor-hook.h
@@ -0,0 +1,70 @@
+/* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef FUNCTOR_HOOK_H_
+#define FUNCTOR_HOOK_H_
+
+#include <boost/intrusive/parent_from_member.hpp>
+
+namespace ns3 {
+namespace ndn {
+namespace ndnSIM {
+namespace detail {
+
+template<class BaseHook, class ValueType, int N>
+struct FunctorHook
+{
+  typedef typename BaseHook::template index<N>::type hook_type;
+  typedef hook_type*            hook_ptr;
+  typedef const hook_type*      const_hook_ptr;
+  
+  typedef ValueType             value_type;
+  typedef value_type*           pointer;
+  typedef const value_type*     const_pointer;
+  
+  //Required static functions
+  static hook_ptr to_hook_ptr (value_type &value)
+  {  return &value.policy_hook_.template get<N> (); }
+  
+  static const_hook_ptr to_hook_ptr(const value_type &value)
+  {  return &value.policy_hook_.template get<N> (); }
+  
+  static pointer to_value_ptr(hook_ptr n)
+  {
+    return
+      boost::intrusive::get_parent_from_member<value_type>
+      (static_cast<BaseHook*> (boost::intrusive::get_parent_from_member< wrap<hook_type> >(n, &wrap<hook_type>::value_)),
+       &value_type::policy_hook_);
+  }
+  static const_pointer to_value_ptr(const_hook_ptr n)
+  {
+    return
+      boost::intrusive::get_parent_from_member<value_type>
+      (static_cast<const BaseHook*> (boost::intrusive::get_parent_from_member< wrap<hook_type> >(n, &wrap<hook_type>::value_)),
+       &value_type::policy_hook_);
+  }
+};
+
+} // detail
+} // ndnSIM
+} // ndn
+} // ns3
+
+#endif // FUNCTOR_HOOK_H_
diff --git a/ndn-cpp/trie/detail/multi-policy-container.h b/ndn-cpp/trie/detail/multi-policy-container.h
new file mode 100644
index 0000000..c1251e9
--- /dev/null
+++ b/ndn-cpp/trie/detail/multi-policy-container.h
@@ -0,0 +1,175 @@
+/* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef MULTI_POLICY_CONTAINER_H_
+#define MULTI_POLICY_CONTAINER_H_
+
+#include <boost/mpl/inherit_linearly.hpp>
+#include <boost/mpl/at.hpp>
+
+namespace ns3 {
+namespace ndn {
+namespace ndnSIM {
+namespace detail {
+
+template< class Base, class Value >
+struct policy_wrap
+{
+  policy_wrap (Base &base) : value_ (base) { }
+  Value value_;
+};
+
+template< class Base, class Super/*empy_wrap/previous level*/, class Value/*policy_wrap< element in vector >*/ >
+struct inherit_with_base : Super, Value
+{
+  inherit_with_base (Base &base) : Super (base), Value (base) { }
+
+  void
+  update (typename Base::iterator item)
+  {
+    Value::value_.update (item);
+    Super::update (item);
+  }
+
+  bool
+  insert (typename Base::iterator item)
+  {
+    bool ok = Value::value_.insert (item);
+    if (!ok)
+      return false;
+
+    ok = Super::insert (item);
+    if (!ok)
+      {
+        Value::value_.erase (item);
+        return false;
+      }
+    return true;
+  }
+
+  void
+  lookup (typename Base::iterator item)
+  {
+    Value::value_.lookup (item);
+    Super::lookup (item);
+  }
+
+  void
+  erase (typename Base::iterator item)
+  {
+    Value::value_.erase (item);
+    Super::erase (item);
+  }  
+
+  void
+  clear ()
+  {
+    Value::value_.clear ();
+    Super::clear ();
+  }
+};
+
+template< class Base >
+struct empty_policy_wrap
+{
+  empty_policy_wrap (Base &base) { }
+
+  void update (typename Base::iterator item) {}
+  bool insert (typename Base::iterator item) { return true; }
+  void lookup (typename Base::iterator item) {}
+  void erase (typename Base::iterator item) {}
+  void clear () {}
+};
+
+template< class Base, class Vector >
+struct multi_policy_container
+  : public boost::mpl::fold< Vector,
+                      empty_policy_wrap<Base>,
+                      inherit_with_base<Base,
+                                        boost::mpl::_1/*empty/previous*/,
+                                        policy_wrap<Base, boost::mpl::_2>/*element in vector*/>
+                      >::type
+{
+  typedef typename boost::mpl::fold< Vector,
+                              empty_policy_wrap<Base>,
+                              inherit_with_base<Base,
+                                                boost::mpl::_1/*empty/previous*/,
+                                                policy_wrap<Base, boost::mpl::_2>/*element in vector*/>
+                              >::type super;
+
+  typedef typename boost::mpl::at_c<Vector, 0>::type::iterator iterator;
+  typedef typename boost::mpl::at_c<Vector, 0>::type::const_iterator const_iterator;
+
+  iterator begin ()             { return this->get<0> ().begin (); }
+  const_iterator begin () const { return this->get<0> ().begin (); }
+
+  iterator end ()             { return this->get<0> ().end (); }
+  const_iterator end () const { return this->get<0> ().end (); }
+
+  size_t size () const { return this->get<0> ().size (); }
+  
+  multi_policy_container (Base &base)
+  : super (base)
+  { }
+
+  template<int N>
+  struct index
+  {
+    typedef typename boost::mpl::at_c<Vector, N>::type type;
+  };
+  
+  template<class T>
+  T &
+  get ()
+  {
+    return static_cast< policy_wrap<Base, T> &> (*this).value_;
+  }
+
+  template<class T>
+  const T &
+  get () const
+  {
+    return static_cast< const policy_wrap<Base, T> &> (*this).value_;
+  }
+
+  template<int N>
+  typename boost::mpl::at_c<Vector, N>::type &
+  get ()
+  {
+    typedef typename boost::mpl::at_c<Vector, N>::type T;
+    return static_cast< policy_wrap<Base, T> &> (*this).value_;
+  }
+
+  template<int N>
+  const typename boost::mpl::at_c<Vector, N>::type &
+  get () const
+  {
+    typedef typename boost::mpl::at_c<Vector, N>::type T;
+    return static_cast< const policy_wrap<Base, T> &> (*this).value_;
+  }
+};
+
+
+} // detail
+} // ndnSIM
+} // ndn
+} // ns3
+
+#endif // MULTI_POLICY_CONTAINER_H_
diff --git a/ndn-cpp/trie/detail/multi-type-container.h b/ndn-cpp/trie/detail/multi-type-container.h
new file mode 100644
index 0000000..d4971c4
--- /dev/null
+++ b/ndn-cpp/trie/detail/multi-type-container.h
@@ -0,0 +1,86 @@
+/* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2011 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef MULTI_TYPE_CONTAINER_H_
+#define MULTI_TYPE_CONTAINER_H_
+
+#include <boost/mpl/inherit_linearly.hpp>
+#include <boost/mpl/inherit.hpp>
+#include <boost/mpl/at.hpp>
+
+namespace ns3 {
+namespace ndn {
+namespace ndnSIM {
+namespace detail {
+
+template <class T>
+struct wrap
+{
+  T value_;
+};
+
+template< class Vector >
+struct multi_type_container
+  : public boost::mpl::inherit_linearly< Vector, boost::mpl::inherit<wrap<boost::mpl::_2>, boost::mpl::_1 >
+  >::type
+{
+  template<int N>
+  struct index
+  {
+    typedef typename boost::mpl::at_c<Vector, N>::type type;
+  };
+  
+  template<class T>
+  T &
+  get ()
+  {
+    return static_cast< wrap<T> &> (*this).value_;
+  }
+
+  template<class T>
+  const T &
+  get () const
+  {
+    return static_cast< const wrap<T> &> (*this).value_;
+  }
+  
+  template<int N>
+  typename boost::mpl::at_c<Vector, N>::type &
+  get ()
+  {
+    typedef typename boost::mpl::at_c<Vector, N>::type T;
+    return static_cast< wrap<T> &> (*this).value_;
+  }
+
+  template<int N>
+  const typename boost::mpl::at_c<Vector, N>::type &
+  get () const
+  {
+    typedef typename boost::mpl::at_c<Vector, N>::type T;
+    return static_cast< const wrap<T> &> (*this).value_;
+  }
+};
+  
+} // detail
+} // ndnSIM
+} // ndn
+} // ns3
+
+#endif // MULTI_TYPE_CONTAINER_H_
diff --git a/ndn-cpp/trie/payload-traits/pointer.h b/ndn-cpp/trie/payload-traits/pointer.h
new file mode 100644
index 0000000..8290fbe
--- /dev/null
+++ b/ndn-cpp/trie/payload-traits/pointer.h
@@ -0,0 +1,40 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef NDN_TRIE_PAYLOAD_TRAITS_POINTER_H
+#define NDN_TRIE_PAYLOAD_TRAITS_POINTER_H
+
+namespace ndn {
+namespace trie {
+
+template<typename Payload, typename BasePayload = Payload>
+struct pointer_payload_traits
+{
+  typedef Payload         payload_type; // general type of the payload
+  typedef Payload*        storage_type; // how the payload is actually stored
+  typedef Payload*        insert_type;  // what parameter is inserted
+
+  typedef Payload*        return_type;  // what is returned on access
+  typedef const Payload*  const_return_type; // what is returned on const access
+
+  typedef BasePayload*       base_type;       // base type of the entry (when implementation details need to be hidden)
+  typedef const BasePayload* const_base_type; // const base type of the entry (when implementation details need to be hidden)
+
+  static Payload* empty_payload;
+};
+
+template<typename Payload, typename BasePayload>
+Payload*
+pointer_payload_traits<Payload, BasePayload>::empty_payload = NULL;
+
+} // trie
+} // ndn
+
+#endif // NDN_TRIE_PAYLOAD_TRAITS_POINTER_H
diff --git a/ndn-cpp/trie/payload-traits/ptr.h b/ndn-cpp/trie/payload-traits/ptr.h
new file mode 100644
index 0000000..3caf020
--- /dev/null
+++ b/ndn-cpp/trie/payload-traits/ptr.h
@@ -0,0 +1,40 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef NDN_TRIE_PAYLOAD_TRAITS_PTR_H
+#define NDN_TRIE_PAYLOAD_TRAITS_PTR_H
+
+namespace ndn {
+namespace trie {
+
+template<typename Payload, typename BasePayload = Payload>
+struct ptr_payload_traits
+{
+  typedef Payload            payload_type;
+  typedef Ptr<Payload>       storage_type;
+  typedef Ptr<Payload>       insert_type;
+
+  typedef Ptr<Payload>       return_type;
+  typedef Ptr<const Payload> const_return_type;
+
+  typedef Ptr<BasePayload> base_type;
+  typedef Ptr<const BasePayload> const_base_type;
+
+  static Ptr<Payload> empty_payload;
+};
+
+template<typename Payload, typename BasePayload>
+Ptr<Payload>
+ptr_payload_traits<Payload, BasePayload>::empty_payload; // = Ptr<Payload> ();
+
+} // trie
+} // ndn
+
+#endif // NDN_TRIE_PAYLOAD_TRAITS_PTR_H
diff --git a/ndn-cpp/trie/policies/counting-policy.h b/ndn-cpp/trie/policies/counting-policy.h
new file mode 100644
index 0000000..d27f915
--- /dev/null
+++ b/ndn-cpp/trie/policies/counting-policy.h
@@ -0,0 +1,101 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef COUNTING_POLICY_H_
+#define COUNTING_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for policy that just keeps track of number of elements
+ * It's doing a rather expensive job, but just in case it needs to be extended later
+ */
+struct counting_policy_traits
+{
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName () { return "Counting"; }
+
+  struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+  template<class Container>
+  struct container_hook
+  {
+    // could be class/struct implementation
+    typedef boost::intrusive::member_hook< Container,
+                             policy_hook_type,
+                             &Container::policy_hook_ > type;
+  };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy 
+  {
+    typedef typename boost::intrusive::list< Container, Hook > policy_container;
+    
+    // could be just typedef
+    class type : public policy_container
+    {
+    public:
+      typedef Container parent_trie;
+
+      type (Base &base)
+        : base_ (base)
+      {
+      }
+
+      inline void
+      update (typename parent_trie::iterator item)
+      {
+        // do nothing
+      }
+  
+      inline bool
+      insert (typename parent_trie::iterator item)
+      {
+        policy_container::push_back (*item);
+        return true;
+      }
+  
+      inline void
+      lookup (typename parent_trie::iterator item)
+      {
+        // do nothing
+      }
+  
+      inline void
+      erase (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+      }
+
+      inline void
+      clear ()
+      {
+        policy_container::clear ();
+      }
+
+    private:
+      type () : base_(*((Base*)0)) { };
+
+    private:
+      Base &base_;
+    };
+  };
+};
+
+} // trie
+} // ndn
+
+#endif // COUNTING_POLICY_H_
diff --git a/ndn-cpp/trie/policies/empty-policy.h b/ndn-cpp/trie/policies/empty-policy.h
new file mode 100644
index 0000000..0cfe962
--- /dev/null
+++ b/ndn-cpp/trie/policies/empty-policy.h
@@ -0,0 +1,50 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef EMPTY_POLICY_H_
+#define EMPTY_POLICY_H_
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for empty (bogus) replacement policy
+ */
+struct empty_policy_traits
+{
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName () { return ""; }
+
+  typedef void* policy_hook_type;
+
+  template<class Container> struct container_hook { typedef void* type; };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy 
+  {
+    struct type
+    {
+      inline type (Base &base) {}
+      
+      inline void update (typename Container::iterator) { }
+      inline bool insert (typename Container::iterator) { return true; }
+      inline void lookup (typename Container::iterator item) { }
+      inline void erase (typename Container::iterator item) { }
+      inline void clear () { }
+    };
+  };
+};
+
+} // trie
+} // ndn
+
+#endif // EMPTY_POLICY_H_
diff --git a/ndn-cpp/trie/policies/fifo-policy.h b/ndn-cpp/trie/policies/fifo-policy.h
new file mode 100644
index 0000000..7acad2b
--- /dev/null
+++ b/ndn-cpp/trie/policies/fifo-policy.h
@@ -0,0 +1,119 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef FIFO_POLICY_H_
+#define FIFO_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for First In First Out replacement policy
+ */
+struct fifo_policy_traits
+{
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName () { return "Fifo"; }
+
+  struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+  template<class Container>
+  struct container_hook
+  {
+    // could be class/struct implementation
+    typedef boost::intrusive::member_hook< Container,
+                             policy_hook_type,
+                             &Container::policy_hook_ > type;
+  };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy 
+  {
+    typedef typename boost::intrusive::list< Container, Hook > policy_container;
+    
+    // could be just typedef
+    class type : public policy_container
+    {
+    public:
+      typedef Container parent_trie;
+
+      type (Base &base)
+        : base_ (base)
+        , max_size_ (100)
+      {
+      }
+
+      inline void
+      update (typename parent_trie::iterator item)
+      {
+        // do nothing
+      }
+  
+      inline bool
+      insert (typename parent_trie::iterator item)
+      {
+        if (max_size_ != 0 && policy_container::size () >= max_size_)
+          {
+            base_.erase (&(*policy_container::begin ()));
+          }
+      
+        policy_container::push_back (*item);
+        return true;
+      }
+  
+      inline void
+      lookup (typename parent_trie::iterator item)
+      {
+        // do nothing
+      }
+  
+      inline void
+      erase (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+      }
+
+      inline void
+      clear ()
+      {
+        policy_container::clear ();
+      }
+
+      inline void
+      set_max_size (size_t max_size)
+      {
+        max_size_ = max_size;
+      }
+
+      inline size_t
+      get_max_size () const
+      {
+        return max_size_;
+      }
+
+    private:
+      type () : base_(*((Base*)0)) { };
+
+    private:
+      Base &base_;
+      size_t max_size_;
+    };
+  };
+};
+
+} // trie
+} // ndn
+
+#endif
diff --git a/ndn-cpp/trie/policies/lfu-policy.h b/ndn-cpp/trie/policies/lfu-policy.h
new file mode 100644
index 0000000..802f64b
--- /dev/null
+++ b/ndn-cpp/trie/policies/lfu-policy.h
@@ -0,0 +1,149 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef LFU_POLICY_H_
+#define LFU_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/set.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for LFU replacement policy
+ */
+struct lfu_policy_traits
+{
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName () { return "Lfu"; }
+
+  struct policy_hook_type : public boost::intrusive::set_member_hook<> { double frequency; };
+
+  template<class Container>
+  struct container_hook
+  {
+    typedef boost::intrusive::member_hook< Container,
+                                           policy_hook_type,
+                                           &Container::policy_hook_ > type;
+  };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy
+  {
+    static double& get_order (typename Container::iterator item)
+    {
+      return static_cast<policy_hook_type*>
+        (policy_container::value_traits::to_node_ptr(*item))->frequency;
+    }
+
+    static const double& get_order (typename Container::const_iterator item)
+    {
+      return static_cast<const policy_hook_type*>
+        (policy_container::value_traits::to_node_ptr(*item))->frequency;
+    }
+
+    template<class Key>
+    struct MemberHookLess
+    {
+      bool operator () (const Key &a, const Key &b) const
+      {
+        return get_order (&a) < get_order (&b);
+      }
+    };
+
+    typedef boost::intrusive::multiset< Container,
+                                   boost::intrusive::compare< MemberHookLess< Container > >,
+                                   Hook > policy_container;
+
+    // could be just typedef
+    class type : public policy_container
+    {
+    public:
+      typedef policy policy_base; // to get access to get_order methods from outside
+      typedef Container parent_trie;
+
+      type (Base &base)
+        : base_ (base)
+        , max_size_ (100)
+      {
+      }
+
+      inline void
+      update (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+        get_order (item) += 1;
+        policy_container::insert (*item);
+      }
+
+      inline bool
+      insert (typename parent_trie::iterator item)
+      {
+        get_order (item) = 0;
+
+        if (max_size_ != 0 && policy_container::size () >= max_size_)
+          {
+            // this erases the "least frequently used item" from cache
+            base_.erase (&(*policy_container::begin ()));
+          }
+
+        policy_container::insert (*item);
+        return true;
+      }
+
+      inline void
+      lookup (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+        get_order (item) += 1;
+        policy_container::insert (*item);
+      }
+
+      inline void
+      erase (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+      }
+
+      inline void
+      clear ()
+      {
+        policy_container::clear ();
+      }
+
+      inline void
+      set_max_size (size_t max_size)
+      {
+        max_size_ = max_size;
+      }
+
+      inline size_t
+      get_max_size () const
+      {
+        return max_size_;
+      }
+
+    private:
+      type () : base_(*((Base*)0)) { };
+
+    private:
+      Base &base_;
+      size_t max_size_;
+    };
+  };
+};
+
+} // trie
+} // ndn
+
+#endif // LFU_POLICY_H
diff --git a/ndn-cpp/trie/policies/lru-policy.h b/ndn-cpp/trie/policies/lru-policy.h
new file mode 100644
index 0000000..ad3a382
--- /dev/null
+++ b/ndn-cpp/trie/policies/lru-policy.h
@@ -0,0 +1,124 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef LRU_POLICY_H_
+#define LRU_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for Least Recently Used replacement policy
+ */
+struct lru_policy_traits
+{
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName () { return "Lru"; }
+  
+  struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+  template<class Container>
+  struct container_hook
+  {
+    typedef boost::intrusive::member_hook< Container,
+                                           policy_hook_type,
+                                           &Container::policy_hook_ > type;
+  };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy 
+  {
+    typedef typename boost::intrusive::list< Container, Hook > policy_container;
+    
+    // could be just typedef
+    class type : public policy_container
+    {
+    public:
+      typedef Container parent_trie;
+    
+      type (Base &base)
+        : base_ (base)
+        , max_size_ (100)
+      {
+      }
+
+      inline void
+      update (typename parent_trie::iterator item)
+      {
+        // do relocation
+        policy_container::splice (policy_container::end (),
+                                  *this,
+                                  policy_container::s_iterator_to (*item));
+      }
+  
+      inline bool
+      insert (typename parent_trie::iterator item)
+      {
+        if (max_size_ != 0 && policy_container::size () >= max_size_)
+          {
+            base_.erase (&(*policy_container::begin ()));
+          }
+      
+        policy_container::push_back (*item);
+        return true;
+      }
+  
+      inline void
+      lookup (typename parent_trie::iterator item)
+      {
+        // do relocation
+        policy_container::splice (policy_container::end (),
+                                  *this,
+                                  policy_container::s_iterator_to (*item));
+      }
+  
+      inline void
+      erase (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+      }
+
+      inline void
+      clear ()
+      {
+        policy_container::clear ();
+      }
+
+      inline void
+      set_max_size (size_t max_size)
+      {
+        max_size_ = max_size;
+      }
+
+      inline size_t
+      get_max_size () const
+      {
+        return max_size_;
+      }
+
+    private:
+      type () : base_(*((Base*)0)) { };
+
+    private:
+      Base &base_;
+      size_t max_size_;
+    };
+  };
+};
+
+} // trie
+} // ndn
+
+#endif
diff --git a/ndn-cpp/trie/policies/multi-policy.h b/ndn-cpp/trie/policies/multi-policy.h
new file mode 100644
index 0000000..739de7b
--- /dev/null
+++ b/ndn-cpp/trie/policies/multi-policy.h
@@ -0,0 +1,177 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef MULTI_POLICY_H_
+#define MULTI_POLICY_H_
+
+#include "detail/multi-type-container.h"
+#include "detail/multi-policy-container.h"
+#include "detail/functor-hook.h"
+
+#include <boost/mpl/size.hpp>
+#include <boost/mpl/at.hpp>
+#include <boost/mpl/range_c.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/back_inserter.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/for_each.hpp>
+
+#include <boost/intrusive/options.hpp>
+
+namespace ndn {
+namespace trie {
+
+template<typename Policies> // e.g., mpl::vector1< lru_policy_traits >
+struct multi_policy_traits
+{
+  typedef Policies policy_traits;
+
+  struct getHook { template<class Item> struct apply { typedef typename Item::policy_hook_type type; }; };
+  typedef detail::multi_type_container< typename boost::mpl::transform1<policy_traits, getHook>::type > policy_hook_type;
+  
+  template<class Container>
+  struct container_hook
+  {
+    typedef policy_hook_type type;
+  };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy 
+  {
+    typedef boost::mpl::range_c<int, 0, boost::mpl::size<policy_traits>::type::value> policies_range;
+
+    struct getPolicy
+    {
+      template<class Number>
+      struct apply
+      {
+        typedef
+        typename boost::mpl::at_c<policy_traits, Number::value>::type::
+        template policy<Base,
+                        Container,
+                        boost::intrusive::function_hook< detail::FunctorHook <Hook,
+                                                                              Container,
+                                                                              Number::value> > >::type
+        type;
+      };
+    };
+    
+    typedef
+    typename boost::mpl::transform1<policies_range,
+                                    getPolicy,
+                                    boost::mpl::back_inserter< boost::mpl::vector0<> > >::type policies;
+                             
+    
+    typedef detail::multi_policy_container< Base, policies > policy_container;
+    
+    class type : public policy_container
+    {
+    public:
+      typedef policy policy_base; // to get access to get_time methods from outside
+      typedef Container parent_trie;
+
+      type (Base &base)
+        : policy_container (base)
+      {
+      }
+
+      inline void
+      update (typename parent_trie::iterator item)
+      {
+        policy_container::update (item);
+      }
+  
+      inline bool
+      insert (typename parent_trie::iterator item)
+      {
+        return policy_container::insert (item);
+      }
+  
+      inline void
+      lookup (typename parent_trie::iterator item)
+      {
+        policy_container::lookup (item);
+      }
+  
+      inline void
+      erase (typename parent_trie::iterator item)
+      {
+        policy_container::erase (item);
+      }
+      
+      inline void
+      clear ()
+      {
+        policy_container::clear ();
+      }
+
+      struct max_size_setter
+      {
+        max_size_setter (policy_container &container, size_t size) : m_container (container), m_size (size) { }
+        
+        template< typename U > void operator() (U index)
+        {
+          m_container.template get<U::value> ().set_max_size (m_size);
+        }
+
+      private:
+        policy_container &m_container;
+        size_t m_size;
+      };
+      
+      inline void
+      set_max_size (size_t max_size)
+      {
+        boost::mpl::for_each< boost::mpl::range_c<int, 0, boost::mpl::size<policy_traits>::type::value> >
+          (max_size_setter (*this, max_size));
+      }
+
+      inline size_t
+      get_max_size () const
+      {
+        // as max size should be the same everywhere, get the value from the first available policy
+        return policy_container::template get<0> ().get_max_size ();
+      }
+      
+    };
+  };
+
+
+  struct name_getter
+  {
+    name_getter (std::string &name) : m_name (name) { }
+    
+    template< typename U > void operator() (U index)
+    {
+      if (!m_name.empty ())
+        m_name += "::";
+      m_name += boost::mpl::at_c< policy_traits, U::value >::type::GetName ();
+    }
+
+    std::string &m_name;
+  };
+
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName ()
+  {
+    // combine names of all internal policies
+    std::string name;
+    boost::mpl::for_each< boost::mpl::range_c<int, 0, boost::mpl::size<policy_traits>::type::value> > (name_getter (name));
+    
+    return name;
+  }
+};
+
+} // trie
+} // ndn
+
+#endif // MULTI_POLICY_H_
diff --git a/ndn-cpp/trie/policies/persistent-policy.h b/ndn-cpp/trie/policies/persistent-policy.h
new file mode 100644
index 0000000..d34f373
--- /dev/null
+++ b/ndn-cpp/trie/policies/persistent-policy.h
@@ -0,0 +1,119 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef PERSISTENT_POLICY_H_
+#define PERSISTENT_POLICY_H_
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/list.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for persistent replacement policy
+ *
+ * In this policy entries are added until there is a space (controlled by set_max_size call).
+ * If maximum is reached, new entries will not be added and nothing will be removed from the container
+ */
+struct persistent_policy_traits
+{
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName () { return "Persistent"; }
+
+  struct policy_hook_type : public boost::intrusive::list_member_hook<> {};
+
+  template<class Container>
+  struct container_hook
+  {
+    typedef boost::intrusive::member_hook< Container,
+                                           policy_hook_type,
+                                           &Container::policy_hook_ > type;
+  };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy 
+  {
+    typedef typename boost::intrusive::list< Container, Hook > policy_container;
+    
+    // could be just typedef
+    class type : public policy_container
+    {
+    public:
+      typedef Container parent_trie;
+    
+      type (Base &base)
+        : base_ (base)
+        , max_size_ (100) // when 0, policy is not enforced
+      {
+      }
+
+      inline void
+      update (typename parent_trie::iterator item)
+      {
+        // do nothing
+      }
+  
+      inline bool
+      insert (typename parent_trie::iterator item)
+      {
+        if (max_size_ != 0 && policy_container::size () >= max_size_)
+          return false;
+      
+        policy_container::push_back (*item);
+        return true;
+      }
+  
+      inline void
+      lookup (typename parent_trie::iterator item)
+      {
+        // do nothing
+      }
+  
+      inline void
+      erase (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+      }
+
+      inline void
+      clear ()
+      {
+        policy_container::clear ();
+      }
+
+      inline void
+      set_max_size (size_t max_size)
+      {
+        max_size_ = max_size;
+      }
+
+      inline size_t
+      get_max_size () const
+      {
+        return max_size_;
+      }
+
+    private:
+      // type () : base_(*((Base*)0)) { };
+
+    private:
+      Base &base_;
+      size_t max_size_;
+    };
+  };
+};
+
+} // trie
+} // ndn
+
+#endif // PERSISTENT_POLICY_H_
diff --git a/ndn-cpp/trie/policies/random-policy.h b/ndn-cpp/trie/policies/random-policy.h
new file mode 100644
index 0000000..d896e89
--- /dev/null
+++ b/ndn-cpp/trie/policies/random-policy.h
@@ -0,0 +1,158 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef RANDOM_POLICY_H_
+#define RANDOM_POLICY_H_
+
+#include "ns3/random-variable.h"
+
+#include <boost/intrusive/options.hpp>
+#include <boost/intrusive/set.hpp>
+
+namespace ndn {
+namespace trie {
+
+/**
+ * @brief Traits for random replacement policy
+ */
+struct random_policy_traits
+{
+  /// @brief Name that can be used to identify the policy (e.g., for logging)
+  static std::string GetName () { return "Random"; }
+
+  struct policy_hook_type : public boost::intrusive::set_member_hook<> { uint32_t randomOrder; };
+
+  template<class Container>
+  struct container_hook
+  {
+    typedef boost::intrusive::member_hook< Container,
+                                           policy_hook_type,
+                                           &Container::policy_hook_ > type;
+  };
+
+  template<class Base,
+           class Container,
+           class Hook>
+  struct policy 
+  {
+    static uint32_t& get_order (typename Container::iterator item)
+    {
+      return static_cast<typename policy_container::value_traits::hook_type*>
+        (policy_container::value_traits::to_node_ptr(*item))->randomOrder;
+    }
+      
+    static const uint32_t& get_order (typename Container::const_iterator item)
+    {
+      return static_cast<const typename policy_container::value_traits::hook_type*>
+        (policy_container::value_traits::to_node_ptr(*item))->randomOrder;
+    }
+    
+    template<class Key>
+    struct MemberHookLess
+    {
+      bool operator () (const Key &a, const Key &b) const
+      {
+        return get_order (&a) < get_order (&b);
+      }
+    };
+
+    typedef boost::intrusive::multiset< Container,
+                                   boost::intrusive::compare< MemberHookLess< Container > >,
+                                   Hook > policy_container;
+    
+    // could be just typedef
+    class type : public policy_container
+    {
+    public:
+      typedef policy policy_base; // to get access to get_order methods from outside
+      typedef Container parent_trie;
+
+      type (Base &base)
+        : base_ (base)
+        , u_rand (0, std::numeric_limits<uint32_t>::max ())
+        , max_size_ (100)
+      {
+      }
+
+      inline void
+      update (typename parent_trie::iterator item)
+      {
+        // do nothing. it's random policy
+      }
+  
+      inline bool
+      insert (typename parent_trie::iterator item)
+      {
+        get_order (item) = u_rand.GetValue ();
+
+        if (max_size_ != 0 && policy_container::size () >= max_size_)
+          {
+            if (MemberHookLess<Container>() (*item, *policy_container::begin ()))
+              {
+                // std::cout << "Cannot add. Signaling fail\n";
+                // just return false. Indicating that insert "failed"
+                return false;
+              }
+            else
+              {
+                // removing some random element
+                base_.erase (&(*policy_container::begin ()));
+              }
+          }
+
+        policy_container::insert (*item);
+        return true;
+      }
+  
+      inline void
+      lookup (typename parent_trie::iterator item)
+      {
+        // do nothing. it's random policy
+      }
+  
+      inline void
+      erase (typename parent_trie::iterator item)
+      {
+        policy_container::erase (policy_container::s_iterator_to (*item));
+      }
+
+      inline void
+      clear ()
+      {
+        policy_container::clear ();
+      }
+
+      inline void
+      set_max_size (size_t max_size)
+      {
+        max_size_ = max_size;
+      }
+
+      inline size_t
+      get_max_size () const
+      {
+        return max_size_;
+      }
+
+    private:
+      type () : base_(*((Base*)0)) { };
+      
+    private:
+      Base &base_;
+      ns3::UniformVariable u_rand;
+      size_t max_size_;
+    };
+  };
+};
+
+} // trie
+} // ndn
+
+#endif // RANDOM_POLICY_H
diff --git a/ndn-cpp/trie/trie-with-policy.h b/ndn-cpp/trie/trie-with-policy.h
new file mode 100644
index 0000000..5a0d896
--- /dev/null
+++ b/ndn-cpp/trie/trie-with-policy.h
@@ -0,0 +1,263 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef TRIE_TRIE_WITH_POLICY_H_
+#define TRIE_TRIE_WITH_POLICY_H_
+
+#include "trie.h"
+
+namespace ndn {
+namespace trie {
+
+template<typename FullKey,
+         typename PayloadTraits,
+         typename PolicyTraits
+         >
+class trie_with_policy
+{
+public:
+  typedef trie< FullKey,
+                PayloadTraits,
+                typename PolicyTraits::policy_hook_type > parent_trie;
+
+  typedef typename parent_trie::iterator iterator;
+  typedef typename parent_trie::const_iterator const_iterator;
+  typedef typename parent_trie::payload_traits payload_traits;
+
+  typedef typename PolicyTraits::template policy<
+    trie_with_policy<FullKey, PayloadTraits, PolicyTraits>,
+    parent_trie,
+    typename PolicyTraits::template container_hook<parent_trie>::type >::type policy_container;
+
+  inline
+  trie_with_policy (size_t bucketSize = 10, size_t bucketIncrement = 10)
+    : trie_ ("", bucketSize, bucketIncrement)
+    , policy_ (*this)
+  {
+  }
+
+  inline std::pair< iterator, bool >
+  insert (const FullKey &key, typename PayloadTraits::insert_type payload)
+  {
+    std::pair<iterator, bool> item =
+      trie_.insert (key, payload);
+
+    if (item.second) // real insert
+      {
+        bool ok = policy_.insert (s_iterator_to (item.first));
+        if (!ok)
+          {
+            item.first->erase (); // cannot insert
+            return std::make_pair (end (), false);
+          }
+      }
+    else
+      {
+        return std::make_pair (s_iterator_to (item.first), false);
+      }
+
+    return item;
+  }
+
+  inline void
+  erase (const FullKey &key)
+  {
+    iterator foundItem, lastItem;
+    bool reachLast;
+    boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+    if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
+      return; // nothing to invalidate
+
+    erase (lastItem);
+  }
+
+  inline void
+  erase (iterator node)
+  {
+    if (node == end ()) return;
+
+    policy_.erase (s_iterator_to (node));
+    node->erase (); // will do cleanup here
+  }
+
+  inline void
+  clear ()
+  {
+    policy_.clear ();
+    trie_.clear ();
+  }
+
+  template<typename Modifier>
+  bool
+  modify (iterator position, Modifier mod)
+  {
+    if (position == end ()) return false;
+    if (position->payload () == PayloadTraits::empty_payload) return false;
+
+    mod (*position->payload ());
+    policy_.update (position);
+    return true;
+  }
+
+  /**
+   * @brief Find a node that has the exact match with the key
+   */
+  inline iterator
+  find_exact (const FullKey &key)
+  {
+    iterator foundItem, lastItem;
+    bool reachLast;
+    boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+    if (!reachLast || lastItem->payload () == PayloadTraits::empty_payload)
+      return end ();
+
+    return lastItem;
+  }
+
+  /**
+   * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
+   */
+  inline iterator
+  longest_prefix_match (const FullKey &key)
+  {
+    iterator foundItem, lastItem;
+    bool reachLast;
+    boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+    if (foundItem != trie_.end ())
+      {
+        policy_.lookup (s_iterator_to (foundItem));
+      }
+    return foundItem;
+  }
+
+  /**
+   * @brief Find a node that has the longest common prefix with key (FIB/PIT lookup)
+   */
+  template<class Predicate>
+  inline iterator
+  longest_prefix_match_if (const FullKey &key, Predicate pred)
+  {
+    iterator foundItem, lastItem;
+    bool reachLast;
+    boost::tie (foundItem, reachLast, lastItem) = trie_.find_if (key, pred);
+    if (foundItem != trie_.end ())
+      {
+        policy_.lookup (s_iterator_to (foundItem));
+      }
+    return foundItem;
+  }
+
+  // /**
+  //  * @brief Const version of the longest common prefix match
+  //  * (semi-const, because there could be update of the policy anyways)
+  //  */
+  // inline const_iterator
+  // longest_prefix_match (const FullKey &key) const
+  // {
+  //   return static_cast<trie_with_policy*> (this)->longest_prefix_match (key);
+  // }
+
+  /**
+   * @brief Find a node that has prefix at least as the key (cache lookup)
+   */
+  inline iterator
+  deepest_prefix_match (const FullKey &key)
+  {
+    iterator foundItem, lastItem;
+    bool reachLast;
+    boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+    // guard in case we don't have anything in the trie
+    if (lastItem == trie_.end ())
+      return trie_.end ();
+
+    if (reachLast)
+      {
+        if (foundItem == trie_.end ())
+          {
+            foundItem = lastItem->find (); // should be something
+          }
+        policy_.lookup (s_iterator_to (foundItem));
+        return foundItem;
+      }
+    else
+      { // couldn't find a node that has prefix at least as key
+        return trie_.end ();
+      }
+  }
+
+  /**
+   * @brief Find a node that has prefix at least as the key
+   */
+  template<class Predicate>
+  inline iterator
+  deepest_prefix_match (const FullKey &key, Predicate pred)
+  {
+    iterator foundItem, lastItem;
+    bool reachLast;
+    boost::tie (foundItem, reachLast, lastItem) = trie_.find (key);
+
+    // guard in case we don't have anything in the trie
+    if (lastItem == trie_.end ())
+      return trie_.end ();
+
+    if (reachLast)
+      {
+        foundItem = lastItem->find_if (pred); // may or may not find something
+        if (foundItem == trie_.end ())
+          {
+            return trie_.end ();
+          }
+        policy_.lookup (s_iterator_to (foundItem));
+        return foundItem;
+      }
+    else
+      { // couldn't find a node that has prefix at least as key
+        return trie_.end ();
+      }
+  }
+
+  iterator end () const
+  {
+    return 0;
+  }
+
+  const parent_trie &
+  getTrie () const { return trie_; }
+
+  parent_trie &
+  getTrie () { return trie_; }
+
+  const policy_container &
+  getPolicy () const { return policy_; }
+
+  policy_container &
+  getPolicy () { return policy_; }
+
+  static inline iterator
+  s_iterator_to (typename parent_trie::iterator item)
+  {
+    if (item == 0)
+      return 0;
+    else
+      return &(*item);
+  }
+
+private:
+  parent_trie      trie_;
+  mutable policy_container policy_;
+};
+
+} // trie
+} // ndn
+
+#endif // TRIE_TRIE_WITH_POLICY_H_
diff --git a/ndn-cpp/trie/trie.h b/ndn-cpp/trie/trie.h
new file mode 100644
index 0000000..edc8a1b
--- /dev/null
+++ b/ndn-cpp/trie/trie.h
@@ -0,0 +1,636 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2013, Regents of the University of California
+ *                     Alexander Afanasyev
+ *
+ * BSD license, See the LICENSE file for more information
+ *
+ * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef NDN_TRIE_TRIE_H_
+#define NDN_TRIE_TRIE_H_
+
+#include <boost/intrusive/unordered_set.hpp>
+#include <boost/intrusive/list.hpp>
+#include <boost/intrusive/set.hpp>
+#include <boost/functional/hash.hpp>
+#include <boost/interprocess/smart_ptr/unique_ptr.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/foreach.hpp>
+#include <boost/mpl/if.hpp>
+
+#include "payload-traits/pointer.h"
+#include "payload-traits/ptr.h"
+
+namespace ndn {
+namespace trie {
+
+////////////////////////////////////////////////////
+// forward declarations
+//
+template<typename FullKey,
+         typename PayloadTraits,
+         typename PolicyHook >
+class trie;
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline std::ostream&
+operator << (std::ostream &os,
+             const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+bool
+operator== (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+            const trie<FullKey, PayloadTraits, PolicyHook> &b);
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook >
+std::size_t
+hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
+
+///////////////////////////////////////////////////
+// actual definition
+//
+template<class T, class NonConstT>
+class trie_iterator;
+
+template<class T>
+class trie_point_iterator;
+
+template<typename FullKey,
+	 typename PayloadTraits,
+         typename PolicyHook >
+class trie
+{
+public:
+  typedef typename FullKey::partial_type Key;
+
+  typedef trie*       iterator;
+  typedef const trie* const_iterator;
+
+  typedef trie_iterator<trie, trie> recursive_iterator;
+  typedef trie_iterator<const trie, trie> const_recursive_iterator;
+
+  typedef trie_point_iterator<trie> point_iterator;
+  typedef trie_point_iterator<const trie> const_point_iterator;
+
+  typedef PayloadTraits payload_traits;
+
+  inline
+  trie (const Key &key, size_t bucketSize = 10, size_t bucketIncrement = 10)
+    : key_ (key)
+    , initialBucketSize_ (bucketSize)
+    , bucketIncrement_ (bucketIncrement)
+    , bucketSize_ (initialBucketSize_)
+    , buckets_ (new bucket_type [bucketSize_]) //cannot use normal pointer, because lifetime of buckets should be larger than lifetime of the container
+    , children_ (bucket_traits (buckets_.get (), bucketSize_))
+    , payload_ (PayloadTraits::empty_payload)
+    , parent_ (0)
+  {
+  }
+
+  inline
+  ~trie ()
+  {
+    payload_ = PayloadTraits::empty_payload; // necessary for smart pointers...
+    children_.clear_and_dispose (trie_delete_disposer ());
+  }
+
+  void
+  clear ()
+  {
+    children_.clear_and_dispose (trie_delete_disposer ());
+  }
+
+  template<class Predicate>
+  void
+  clear_if (Predicate cond)
+  {
+    recursive_iterator trieNode (this);
+    recursive_iterator end (0);
+
+    while (trieNode != end)
+      {
+        if (cond (*trieNode))
+          {
+            trieNode = recursive_iterator (trieNode->erase ());
+          }
+        trieNode ++;
+      }
+  }
+
+  // actual entry
+  friend bool
+  operator== <> (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+                 const trie<FullKey, PayloadTraits, PolicyHook> &b);
+
+  friend std::size_t
+  hash_value <> (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node);
+
+  inline std::pair<iterator, bool>
+  insert (const FullKey &key,
+          typename PayloadTraits::insert_type payload)
+  {
+    trie *trieNode = this;
+
+    BOOST_FOREACH (const Key &subkey, key)
+      {
+        typename unordered_set::iterator item = trieNode->children_.find (subkey);
+        if (item == trieNode->children_.end ())
+          {
+            trie *newNode = new trie (subkey, initialBucketSize_, bucketIncrement_);
+            // std::cout << "new " << newNode << "\n";
+            newNode->parent_ = trieNode;
+
+            if (trieNode->children_.size () >= trieNode->bucketSize_)
+              {
+                trieNode->bucketSize_ += trieNode->bucketIncrement_;
+                trieNode->bucketIncrement_ *= 2; // increase bucketIncrement exponentially
+
+                buckets_array newBuckets (new bucket_type [trieNode->bucketSize_]);
+                trieNode->children_.rehash (bucket_traits (newBuckets.get (), trieNode->bucketSize_));
+                trieNode->buckets_.swap (newBuckets);
+              }
+
+            std::pair< typename unordered_set::iterator, bool > ret =
+              trieNode->children_.insert (*newNode);
+
+            trieNode = &(*ret.first);
+          }
+        else
+          trieNode = &(*item);
+      }
+
+    if (trieNode->payload_ == PayloadTraits::empty_payload)
+      {
+        trieNode->payload_ = payload;
+        return std::make_pair (trieNode, true);
+      }
+    else
+      return std::make_pair (trieNode, false);
+  }
+
+  /**
+   * @brief Removes payload (if it exists) and if there are no children, prunes parents trie
+   */
+  inline iterator
+  erase ()
+  {
+    payload_ = PayloadTraits::empty_payload;
+    return prune ();
+  }
+
+  /**
+   * @brief Do exactly as erase, but without erasing the payload
+   */
+  inline iterator
+  prune ()
+  {
+    if (payload_ == PayloadTraits::empty_payload &&
+        children_.size () == 0)
+      {
+        if (parent_ == 0) return this;
+
+        trie *parent = parent_;
+        parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
+
+        return parent->prune ();
+      }
+    return this;
+  }
+
+  /**
+   * @brief Perform prune of the node, but without attempting to parent of the node
+   */
+  inline void
+  prune_node ()
+  {
+    if (payload_ == PayloadTraits::empty_payload &&
+        children_.size () == 0)
+      {
+        if (parent_ == 0) return;
+
+        trie *parent = parent_;
+        parent->children_.erase_and_dispose (*this, trie_delete_disposer ()); // delete this; basically, committing a suicide
+      }
+  }
+
+  // inline boost::tuple<const iterator, bool, const iterator>
+  // find (const FullKey &key) const
+  // {
+  //   return const_cast<trie*> (this)->find (key);
+  // }
+
+  /**
+   * @brief Perform the longest prefix match
+   * @param key the key for which to perform the longest prefix match
+   *
+   * @return ->second is true if prefix in ->first is longer than key
+   */
+  inline boost::tuple<iterator, bool, iterator>
+  find (const FullKey &key)
+  {
+    trie *trieNode = this;
+    iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
+    bool reachLast = true;
+
+    BOOST_FOREACH (const Key &subkey, key)
+      {
+        typename unordered_set::iterator item = trieNode->children_.find (subkey);
+        if (item == trieNode->children_.end ())
+          {
+            reachLast = false;
+            break;
+          }
+        else
+          {
+            trieNode = &(*item);
+
+            if (trieNode->payload_ != PayloadTraits::empty_payload)
+              foundNode = trieNode;
+          }
+      }
+
+    return boost::make_tuple (foundNode, reachLast, trieNode);
+  }
+
+  /**
+   * @brief Perform the longest prefix match satisfying preficate
+   * @param key the key for which to perform the longest prefix match
+   *
+   * @return ->second is true if prefix in ->first is longer than key
+   */
+  template<class Predicate>
+  inline boost::tuple<iterator, bool, iterator>
+  find_if (const FullKey &key, Predicate pred)
+  {
+    trie *trieNode = this;
+    iterator foundNode = (payload_ != PayloadTraits::empty_payload) ? this : 0;
+    bool reachLast = true;
+
+    BOOST_FOREACH (const Key &subkey, key)
+      {
+        typename unordered_set::iterator item = trieNode->children_.find (subkey);
+        if (item == trieNode->children_.end ())
+          {
+            reachLast = false;
+            break;
+          }
+        else
+          {
+            trieNode = &(*item);
+
+            if (trieNode->payload_ != PayloadTraits::empty_payload &&
+                pred (trieNode->payload_))
+              {
+                foundNode = trieNode;
+              }
+          }
+      }
+
+    return boost::make_tuple (foundNode, reachLast, trieNode);
+  }
+
+  /**
+   * @brief Find next payload of the sub-trie
+   * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
+   */
+  inline iterator
+  find ()
+  {
+    if (payload_ != PayloadTraits::empty_payload)
+      return this;
+
+    typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
+    for (typename trie::unordered_set::iterator subnode = children_.begin ();
+         subnode != children_.end ();
+         subnode++ )
+      // BOOST_FOREACH (trie &subnode, children_)
+      {
+        iterator value = subnode->find ();
+        if (value != 0)
+          return value;
+      }
+
+    return 0;
+  }
+
+  /**
+   * @brief Find next payload of the sub-trie satisfying the predicate
+   * @param pred predicate
+   * @returns end() or a valid iterator pointing to the trie leaf (order is not defined, enumeration )
+   */
+  template<class Predicate>
+  inline const iterator
+  find_if (Predicate pred)
+  {
+    if (payload_ != PayloadTraits::empty_payload && pred (payload_))
+      return this;
+
+    typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
+    for (typename trie::unordered_set::iterator subnode = children_.begin ();
+         subnode != children_.end ();
+         subnode++ )
+      // BOOST_FOREACH (const trie &subnode, children_)
+      {
+        iterator value = subnode->find_if (pred);
+        if (value != 0)
+          return value;
+      }
+
+    return 0;
+  }
+
+  iterator end ()
+  {
+    return 0;
+  }
+
+  const_iterator end () const
+  {
+    return 0;
+  }
+
+  typename PayloadTraits::const_return_type
+  payload () const
+  {
+    return payload_;
+  }
+
+  typename PayloadTraits::return_type
+  payload ()
+  {
+    return payload_;
+  }
+
+  void
+  set_payload (typename PayloadTraits::insert_type payload)
+  {
+    payload_ = payload;
+  }
+
+  Key key () const
+  {
+    return key_;
+  }
+
+  inline void
+  PrintStat (std::ostream &os) const;
+
+private:
+  //The disposer object function
+  struct trie_delete_disposer
+  {
+    void operator() (trie *delete_this)
+    {
+      delete delete_this;
+    }
+  };
+
+  template<class D>
+  struct array_disposer
+  {
+    void operator() (D *array)
+    {
+      delete [] array;
+    }
+  };
+
+  friend
+  std::ostream&
+  operator<< < > (std::ostream &os, const trie &trie_node);
+
+public:
+  PolicyHook policy_hook_;
+
+private:
+  boost::intrusive::unordered_set_member_hook<> unordered_set_member_hook_;
+
+  // necessary typedefs
+  typedef trie self_type;
+  typedef boost::intrusive::member_hook< trie,
+                                         boost::intrusive::unordered_set_member_hook< >,
+                                         &trie::unordered_set_member_hook_ > member_hook;
+
+  typedef boost::intrusive::unordered_set< trie, member_hook > unordered_set;
+  typedef typename unordered_set::bucket_type   bucket_type;
+  typedef typename unordered_set::bucket_traits bucket_traits;
+
+  template<class T, class NonConstT>
+  friend class trie_iterator;
+
+  template<class T>
+  friend class trie_point_iterator;
+
+  ////////////////////////////////////////////////
+  // Actual data
+  ////////////////////////////////////////////////
+
+  Key key_; ///< name component
+
+  size_t initialBucketSize_;
+  size_t bucketIncrement_;
+
+  size_t bucketSize_;
+  typedef boost::interprocess::unique_ptr< bucket_type, array_disposer<bucket_type> > buckets_array;
+  buckets_array buckets_;
+  unordered_set children_;
+
+  typename PayloadTraits::storage_type payload_;
+  trie *parent_; // to make cleaning effective
+};
+
+
+
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline std::ostream&
+operator << (std::ostream &os, const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
+{
+  os << "# " << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?"*":"") << std::endl;
+  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
+
+  for (typename trie::unordered_set::const_iterator subnode = trie_node.children_.begin ();
+       subnode != trie_node.children_.end ();
+       subnode++ )
+  // BOOST_FOREACH (const trie &subnode, trie_node.children_)
+    {
+      os << "\"" << &trie_node << "\"" << " [label=\"" << trie_node.key_ << ((trie_node.payload_ != PayloadTraits::empty_payload)?"*":"") << "\"]\n";
+      os << "\"" << &(*subnode) << "\"" << " [label=\"" << subnode->key_ << ((subnode->payload_ != PayloadTraits::empty_payload)?"*":"") << "\"]""\n";
+
+      os << "\"" << &trie_node << "\"" << " -> " << "\"" << &(*subnode) << "\"" << "\n";
+      os << *subnode;
+    }
+
+  return os;
+}
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline void
+trie<FullKey, PayloadTraits, PolicyHook>
+::PrintStat (std::ostream &os) const
+{
+  os << "# " << key_ << ((payload_ != PayloadTraits::empty_payload)?"*":"") << ": " << children_.size() << " children" << std::endl;
+  for (size_t bucket = 0, maxbucket = children_.bucket_count ();
+       bucket < maxbucket;
+       bucket++)
+    {
+      os << " " << children_.bucket_size (bucket);
+    }
+  os << "\n";
+
+  typedef trie<FullKey, PayloadTraits, PolicyHook> trie;
+  for (typename trie::unordered_set::const_iterator subnode = children_.begin ();
+       subnode != children_.end ();
+       subnode++ )
+  // BOOST_FOREACH (const trie &subnode, children_)
+    {
+      subnode->PrintStat (os);
+    }
+}
+
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline bool
+operator == (const trie<FullKey, PayloadTraits, PolicyHook> &a,
+             const trie<FullKey, PayloadTraits, PolicyHook> &b)
+{
+  return a.key_ == b.key_;
+}
+
+template<typename FullKey, typename PayloadTraits, typename PolicyHook>
+inline std::size_t
+hash_value (const trie<FullKey, PayloadTraits, PolicyHook> &trie_node)
+{
+  return boost::hash_value (trie_node.key_);
+}
+
+
+
+template<class Trie, class NonConstTrie> // hack for boost < 1.47
+class trie_iterator
+{
+public:
+  trie_iterator () : trie_ (0) {}
+  trie_iterator (typename Trie::iterator item) : trie_ (item) {}
+  trie_iterator (Trie &item) : trie_ (&item) {}
+
+  Trie & operator* () { return *trie_; }
+  const Trie & operator* () const { return *trie_; }
+  Trie * operator-> () { return trie_; }
+  const Trie * operator-> () const { return trie_; }
+  bool operator== (trie_iterator<const Trie, NonConstTrie> &other) const { return (trie_ == other.trie_); }
+  bool operator== (trie_iterator<Trie, NonConstTrie> &other) { return (trie_ == other.trie_); }
+  bool operator!= (trie_iterator<const Trie, NonConstTrie> &other) const { return !(*this == other); }
+  bool operator!= (trie_iterator<Trie, NonConstTrie> &other) { return !(*this == other); }
+
+  trie_iterator<Trie,NonConstTrie> &
+  operator++ (int)
+  {
+    if (trie_->children_.size () > 0)
+      trie_ = &(*trie_->children_.begin ());
+    else
+      trie_ = goUp ();
+    return *this;
+  }
+
+  trie_iterator<Trie,NonConstTrie> &
+  operator++ ()
+  {
+    (*this)++;
+    return *this;
+  }
+
+private:
+  typedef typename boost::mpl::if_< boost::is_same<Trie, NonConstTrie>,
+                                    typename Trie::unordered_set::iterator,
+                                    typename Trie::unordered_set::const_iterator>::type set_iterator;
+
+  Trie* goUp ()
+  {
+    if (trie_->parent_ != 0)
+      {
+        // typename Trie::unordered_set::iterator item =
+        set_iterator item = const_cast<NonConstTrie*>(trie_)->parent_->children_.iterator_to (const_cast<NonConstTrie&> (*trie_));
+        item++;
+        if (item != trie_->parent_->children_.end ())
+          {
+            return &(*item);
+          }
+        else
+          {
+            trie_ = trie_->parent_;
+            return goUp ();
+          }
+      }
+    else
+      return 0;
+  }
+private:
+  Trie *trie_;
+};
+
+
+template<class Trie>
+class trie_point_iterator
+{
+private:
+  typedef typename boost::mpl::if_< boost::is_same<Trie, const Trie>,
+                                    typename Trie::unordered_set::const_iterator,
+                                    typename Trie::unordered_set::iterator>::type set_iterator;
+
+public:
+  trie_point_iterator () : trie_ (0) {}
+  trie_point_iterator (typename Trie::iterator item) : trie_ (item) {}
+  trie_point_iterator (Trie &item)
+  {
+    if (item.children_.size () != 0)
+      trie_ = &*item.children_.begin ();
+    else
+      trie_ = 0;
+  }
+
+  Trie & operator* () { return *trie_; }
+  const Trie & operator* () const { return *trie_; }
+  Trie * operator-> () { return trie_; }
+  const Trie * operator-> () const { return trie_; }
+  bool operator== (trie_point_iterator<const Trie> &other) const { return (trie_ == other.trie_); }
+  bool operator== (trie_point_iterator<Trie> &other) { return (trie_ == other.trie_); }
+  bool operator!= (trie_point_iterator<const Trie> &other) const { return !(*this == other); }
+  bool operator!= (trie_point_iterator<Trie> &other) { return !(*this == other); }
+
+  trie_point_iterator<Trie> &
+  operator++ (int)
+  {
+    if (trie_->parent_ != 0)
+      {
+        set_iterator item = trie_->parent_->children_.iterator_to (*trie_);
+        item ++;
+        if (item == trie_->parent_->children_.end ())
+          trie_ = 0;
+        else
+          trie_ = &*item;
+      }
+    else
+      {
+        trie_ = 0;
+      }
+    return *this;
+  }
+
+  trie_point_iterator<Trie> &
+  operator++ ()
+  {
+    (*this)++;
+    return *this;
+  }
+
+private:
+  Trie *trie_;
+};
+
+
+} // trie
+} // ndn
+
+#endif // NDN_TRIE_TRIE_H_