Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2013 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 bin_search_tree_traits<
  170.       Key,
  171.       null_type,
  172.       Cmp_Fn,
  173.       Node_Update,
  174.       Node,
  175.       _Alloc>
  176.     {
  177.     private:
  178.       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
  179.  
  180.     public:
  181.       typedef Node node;
  182.  
  183.       typedef
  184.       bin_search_tree_const_it_<
  185.         typename _Alloc::template rebind<
  186.         node>::other::pointer,
  187.         typename type_traits::value_type,
  188.         typename type_traits::pointer,
  189.         typename type_traits::const_pointer,
  190.         typename type_traits::reference,
  191.         typename type_traits::const_reference,
  192.         true,
  193.         _Alloc>
  194.       point_const_iterator;
  195.  
  196.       typedef point_const_iterator point_iterator;
  197.  
  198.       typedef
  199.       bin_search_tree_const_it_<
  200.         typename _Alloc::template rebind<
  201.         node>::other::pointer,
  202.         typename type_traits::value_type,
  203.         typename type_traits::pointer,
  204.         typename type_traits::const_pointer,
  205.         typename type_traits::reference,
  206.         typename type_traits::const_reference,
  207.         false,
  208.         _Alloc>
  209.       const_reverse_iterator;
  210.  
  211.       typedef const_reverse_iterator reverse_iterator;
  212.  
  213.       /// This is an iterator to an iterator: it iterates over nodes,
  214.       /// and de-referencing it returns one of the tree's iterators.
  215.       typedef
  216.       bin_search_tree_const_node_it_<
  217.         Node,
  218.         point_const_iterator,
  219.         point_iterator,
  220.         _Alloc>
  221.       node_const_iterator;
  222.  
  223.       typedef node_const_iterator node_iterator;
  224.  
  225.       typedef
  226.       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
  227.       node_update;
  228.  
  229.       typedef
  230.       __gnu_pbds::null_node_update<
  231.         node_const_iterator,
  232.         node_iterator,
  233.         Cmp_Fn,
  234.         _Alloc>*
  235.       null_node_update_pointer;
  236.     };
  237.  
  238.   } // namespace detail
  239. } // namespace __gnu_pbds
  240.  
  241. #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  242.