Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2015 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the terms
  7. // of the GNU General Public License as published by the Free Software
  8. // Foundation; either version 3, or (at your option) any later
  9. // version.
  10.  
  11. // This library is distributed in the hope that it will be useful, but
  12. // WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. // General Public License for more details.
  15.  
  16. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26.  
  27. // Permission to use, copy, modify, sell, and distribute this software
  28. // is hereby granted without fee, provided that the above copyright
  29. // notice appears in all copies, and that both that copyright notice
  30. // and this permission notice appear in supporting documentation. None
  31. // of the above authors, nor IBM Haifa Research Laboratories, make any
  32. // representation about the suitability of this software for any
  33. // purpose. It is provided "as is" without express or implied
  34. // warranty.
  35.  
  36. /**
  37.  * @file bin_search_tree_/traits.hpp
  38.  * Contains an implementation for bin_search_tree_.
  39.  */
  40.  
  41. #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  42. #define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  43.  
  44. #include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
  45. #include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
  46.  
  47. namespace __gnu_pbds
  48. {
  49.   namespace detail
  50.   {
  51.     /// Binary search tree traits, primary template
  52.     /// @ingroup traits
  53.     template<typename Key,
  54.              typename Mapped,
  55.              class Cmp_Fn,
  56.              template<typename Node_CItr,
  57.                       class Node_Itr,
  58.                       class _Cmp_Fn,
  59.                       typename _Alloc>
  60.              class Node_Update,
  61.              class Node,
  62.              typename _Alloc>
  63.     struct bin_search_tree_traits
  64.     {
  65.     private:
  66.       typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
  67.  
  68.     public:
  69.       typedef Node node;
  70.  
  71.       typedef
  72.       bin_search_tree_const_it_<
  73.         typename _Alloc::template rebind<
  74.         node>::other::pointer,
  75.         typename type_traits::value_type,
  76.         typename type_traits::pointer,
  77.         typename type_traits::const_pointer,
  78.         typename type_traits::reference,
  79.         typename type_traits::const_reference,
  80.         true,
  81.         _Alloc>
  82.       point_const_iterator;
  83.  
  84.       typedef
  85.       bin_search_tree_it_<
  86.         typename _Alloc::template rebind<
  87.         node>::other::pointer,
  88.         typename type_traits::value_type,
  89.         typename type_traits::pointer,
  90.         typename type_traits::const_pointer,
  91.         typename type_traits::reference,
  92.         typename type_traits::const_reference,
  93.         true,
  94.         _Alloc>
  95.       point_iterator;
  96.  
  97.       typedef
  98.       bin_search_tree_const_it_<
  99.         typename _Alloc::template rebind<
  100.         node>::other::pointer,
  101.         typename type_traits::value_type,
  102.         typename type_traits::pointer,
  103.         typename type_traits::const_pointer,
  104.         typename type_traits::reference,
  105.         typename type_traits::const_reference,
  106.         false,
  107.         _Alloc>
  108.       const_reverse_iterator;
  109.  
  110.       typedef
  111.       bin_search_tree_it_<
  112.         typename _Alloc::template rebind<
  113.         node>::other::pointer,
  114.         typename type_traits::value_type,
  115.         typename type_traits::pointer,
  116.         typename type_traits::const_pointer,
  117.         typename type_traits::reference,
  118.         typename type_traits::const_reference,
  119.         false,
  120.         _Alloc>
  121.       reverse_iterator;
  122.  
  123.       /// This is an iterator to an iterator: it iterates over nodes,
  124.       /// and de-referencing it returns one of the tree's iterators.
  125.       typedef
  126.       bin_search_tree_const_node_it_<
  127.         Node,
  128.         point_const_iterator,
  129.         point_iterator,
  130.         _Alloc>
  131.       node_const_iterator;
  132.  
  133.       typedef
  134.       bin_search_tree_node_it_<
  135.         Node,
  136.         point_const_iterator,
  137.         point_iterator,
  138.         _Alloc>
  139.       node_iterator;
  140.  
  141.       typedef
  142.       Node_Update<
  143.         node_const_iterator,
  144.         node_iterator,
  145.         Cmp_Fn,
  146.         _Alloc>
  147.       node_update;
  148.  
  149.       typedef
  150.       __gnu_pbds::null_node_update<
  151.         node_const_iterator,
  152.         node_iterator,
  153.         Cmp_Fn,
  154.         _Alloc>*
  155.       null_node_update_pointer;
  156.     };
  157.  
  158.     /// Specialization.
  159.     /// @ingroup traits
  160.     template<typename Key,
  161.              class Cmp_Fn,
  162.              template<typename Node_CItr,
  163.                       class Node_Itr,
  164.                       class _Cmp_Fn,
  165.                       typename _Alloc>
  166.              class Node_Update,
  167.              class Node,
  168.              typename _Alloc>
  169.     struct
  170.     bin_search_tree_traits<Key, null_type, Cmp_Fn, Node_Update, Node, _Alloc>
  171.     {
  172.     private:
  173.       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
  174.  
  175.     public:
  176.       typedef Node node;
  177.  
  178.       typedef
  179.       bin_search_tree_const_it_<
  180.         typename _Alloc::template rebind<
  181.         node>::other::pointer,
  182.         typename type_traits::value_type,
  183.         typename type_traits::pointer,
  184.         typename type_traits::const_pointer,
  185.         typename type_traits::reference,
  186.         typename type_traits::const_reference,
  187.         true,
  188.         _Alloc>
  189.       point_const_iterator;
  190.  
  191.       typedef point_const_iterator point_iterator;
  192.  
  193.       typedef
  194.       bin_search_tree_const_it_<
  195.         typename _Alloc::template rebind<
  196.         node>::other::pointer,
  197.         typename type_traits::value_type,
  198.         typename type_traits::pointer,
  199.         typename type_traits::const_pointer,
  200.         typename type_traits::reference,
  201.         typename type_traits::const_reference,
  202.         false,
  203.         _Alloc>
  204.       const_reverse_iterator;
  205.  
  206.       typedef const_reverse_iterator reverse_iterator;
  207.  
  208.       /// This is an iterator to an iterator: it iterates over nodes,
  209.       /// and de-referencing it returns one of the tree's iterators.
  210.       typedef
  211.       bin_search_tree_const_node_it_<
  212.         Node,
  213.         point_const_iterator,
  214.         point_iterator,
  215.         _Alloc>
  216.       node_const_iterator;
  217.  
  218.       typedef node_const_iterator node_iterator;
  219.  
  220.       typedef
  221.       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
  222.       node_update;
  223.  
  224.       typedef
  225.       __gnu_pbds::null_node_update<
  226.         node_const_iterator,
  227.         node_iterator,
  228.         Cmp_Fn,
  229.         _Alloc>*
  230.       null_node_update_pointer;
  231.     };
  232.  
  233.   } // namespace detail
  234. } // namespace __gnu_pbds
  235.  
  236. #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  237.