Subversion Repositories Kolibri OS

Rev

Go to most recent revision | 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 ov_tree_map_/node_iterators.hpp
  38.  * Contains an implementation class for ov_tree_.
  39.  */
  40.  
  41. #ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP
  42. #define PB_DS_OV_TREE_NODE_ITERATORS_HPP
  43.  
  44. #include <ext/pb_ds/tag_and_trait.hpp>
  45. #include <ext/pb_ds/detail/type_utils.hpp>
  46. #include <debug/debug.h>
  47.  
  48. namespace __gnu_pbds
  49. {
  50.   namespace detail
  51.   {
  52. #define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC \
  53.     ov_tree_node_const_it_<Value_Type, Metadata_Type, _Alloc>
  54.  
  55.     /// Const node reference.
  56.     template<typename Value_Type, typename Metadata_Type, typename _Alloc>
  57.     class ov_tree_node_const_it_
  58.     {
  59.  
  60.     protected:
  61.       typedef
  62.       typename _Alloc::template rebind<
  63.       Value_Type>::other::pointer
  64.       pointer;
  65.  
  66.       typedef
  67.       typename _Alloc::template rebind<
  68.         Value_Type>::other::const_pointer
  69.       const_pointer;
  70.  
  71.       typedef
  72.       typename _Alloc::template rebind<
  73.         Metadata_Type>::other::const_pointer
  74.       const_metadata_pointer;
  75.  
  76.       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type;
  77.  
  78.     protected:
  79.  
  80.       template<typename Ptr>
  81.       inline static Ptr
  82.       mid_pointer(Ptr p_begin, Ptr p_end)
  83.       {
  84.         _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
  85.         return (p_begin + (p_end - p_begin) / 2);
  86.       }
  87.  
  88.     public:
  89.  
  90.       typedef trivial_iterator_tag iterator_category;
  91.  
  92.       typedef trivial_iterator_difference_type difference_type;
  93.  
  94.       typedef
  95.       typename _Alloc::template rebind<
  96.         Value_Type>::other::const_pointer
  97.       value_type;
  98.  
  99.       typedef
  100.       typename _Alloc::template rebind<
  101.         typename remove_const<
  102.         Value_Type>::type>::other::const_pointer
  103.       reference;
  104.  
  105.       typedef
  106.       typename _Alloc::template rebind<
  107.         typename remove_const<
  108.         Value_Type>::type>::other::const_pointer
  109.       const_reference;
  110.  
  111.       typedef Metadata_Type metadata_type;
  112.  
  113.       typedef
  114.       typename _Alloc::template rebind<
  115.         metadata_type>::other::const_reference
  116.       metadata_const_reference;
  117.  
  118.     public:
  119.       inline
  120.       ov_tree_node_const_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata)
  121.       { }
  122.  
  123.       inline const_reference
  124.       operator*() const
  125.       { return m_p_value; }
  126.  
  127.       inline metadata_const_reference
  128.       get_metadata() const
  129.       {
  130.         enum
  131.           {
  132.             has_metadata = !is_same<Metadata_Type, null_type>::value
  133.           };
  134.  
  135.         PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata);
  136.         _GLIBCXX_DEBUG_ASSERT(m_p_metadata != 0);
  137.         return *m_p_metadata;
  138.       }
  139.  
  140.       /// Returns the node iterator associated with the left node.
  141.       inline this_type
  142.       get_l_child() const
  143.       {
  144.         if (m_p_begin_value == m_p_value)
  145.           return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value));
  146.  
  147.         const_metadata_pointer p_begin_metadata =
  148.           m_p_metadata - (m_p_value - m_p_begin_value);
  149.  
  150.         return (this_type(mid_pointer(m_p_begin_value, m_p_value),
  151.                           m_p_begin_value,
  152.                           m_p_value,
  153.                           mid_pointer(p_begin_metadata, m_p_metadata)));
  154.       }
  155.  
  156.       /// Returns the node iterator associated with the right node.
  157.       inline this_type
  158.       get_r_child() const
  159.       {
  160.         if (m_p_value == m_p_end_value)
  161.           return (this_type(m_p_end_value, m_p_end_value, m_p_end_value));
  162.  
  163.         const_metadata_pointer p_end_metadata =
  164.           m_p_metadata + (m_p_end_value - m_p_value);
  165.  
  166.         return (this_type(mid_pointer(m_p_value + 1, m_p_end_value),
  167.                           m_p_value + 1,
  168.                           m_p_end_value,(m_p_metadata == 0) ?
  169.                           0 : mid_pointer(m_p_metadata + 1, p_end_metadata)));
  170.       }
  171.  
  172.       inline bool
  173.       operator==(const this_type& other) const
  174.       {
  175.         const bool is_end = m_p_begin_value == m_p_end_value;
  176.         const bool is_other_end = other.m_p_begin_value == other.m_p_end_value;
  177.  
  178.         if (is_end)
  179.           return (is_other_end);
  180.  
  181.         if (is_other_end)
  182.           return (is_end);
  183.  
  184.         return m_p_value == other.m_p_value;
  185.       }
  186.  
  187.       inline bool
  188.       operator!=(const this_type& other) const
  189.       { return !operator==(other); }
  190.  
  191.     public:
  192.       pointer m_p_value;
  193.       pointer m_p_begin_value;
  194.       pointer m_p_end_value;
  195.  
  196.       const_metadata_pointer m_p_metadata;
  197.     };
  198.  
  199. #define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC \
  200.     ov_tree_node_it_<Value_Type, Metadata_Type, _Alloc>
  201.  
  202.     /// Node reference.
  203.     template<typename Value_Type, typename Metadata_Type, typename _Alloc>
  204.     class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
  205.     {
  206.     private:
  207.       typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type;
  208.  
  209.       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type;
  210.  
  211.       typedef typename base_type::pointer pointer;
  212.  
  213.       typedef typename base_type::const_pointer const_pointer;
  214.  
  215.       typedef
  216.       typename base_type::const_metadata_pointer
  217.       const_metadata_pointer;
  218.  
  219.     public:
  220.       typedef trivial_iterator_tag iterator_category;
  221.  
  222.       typedef trivial_iterator_difference_type difference_type;
  223.  
  224.       typedef
  225.       typename _Alloc::template rebind<
  226.         Value_Type>::other::pointer
  227.       value_type;
  228.  
  229.       typedef
  230.       typename _Alloc::template rebind<
  231.         typename remove_const<
  232.         Value_Type>::type>::other::pointer
  233.       reference;
  234.  
  235.       typedef
  236.       typename _Alloc::template rebind<
  237.         typename remove_const<
  238.         Value_Type>::type>::other::pointer
  239.       const_reference;
  240.  
  241.       inline
  242.       ov_tree_node_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : base_type(p_nd,  p_begin_nd,  p_end_nd,  p_metadata)
  243.       { }
  244.  
  245.       /// Access.
  246.       inline reference
  247.       operator*() const
  248.       { return reference(base_type::m_p_value); }
  249.  
  250.       /// Returns the node reference associated with the left node.
  251.       inline ov_tree_node_it_
  252.       get_l_child() const
  253.       {
  254.         if (base_type::m_p_begin_value == base_type::m_p_value)
  255.           return (this_type(base_type::m_p_begin_value,  base_type::m_p_begin_value,  base_type::m_p_begin_value));
  256.  
  257.         const_metadata_pointer p_begin_metadata =
  258.           base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value);
  259.  
  260.         return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value),
  261.                           base_type::m_p_begin_value,
  262.                           base_type::m_p_value,
  263.                           base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata)));
  264.       }
  265.  
  266.       /// Returns the node reference associated with the right node.
  267.       inline ov_tree_node_it_
  268.       get_r_child() const
  269.       {
  270.         if (base_type::m_p_value == base_type::m_p_end_value)
  271.           return this_type(base_type::m_p_end_value, base_type::m_p_end_value,  
  272.                            base_type::m_p_end_value);
  273.  
  274.         const_metadata_pointer p_end_metadata =
  275.           base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value);
  276.  
  277.         return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value),
  278.                           base_type::m_p_value + 1,
  279.                           base_type::m_p_end_value,(base_type::m_p_metadata == 0)?
  280.                           0 : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata)));
  281.       }
  282.  
  283.     };
  284.  
  285. #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC
  286. #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
  287.  
  288. } // namespace detail
  289. } // namespace __gnu_pbds
  290.  
  291. #endif
  292.