URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc4/] [libstdc++-v3/] [include/] [ext/] [pb_ds/] [detail/] [pat_trie_/] [point_iterators.hpp] - Blame information for rev 424

Go to most recent revision | Details | Compare with Previous | View Log


// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
 * @file point_iterators.hpp
 * Contains an implementation class for bin_search_tree_.
 */
 
#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
 
#include <debug/debug.h>
 
namespace __gnu_pbds
{
  namespace detail
  {
 
#define PB_DS_CONST_IT_C_DEC                                    \
    pat_trie_const_it_<                                         \
                                        Type_Traits,            \
                                        Node,                   \
                                        Leaf,                   \
                                        Head,                   \
                                        Internal_Node,          \
                                        Is_Forward_Iterator,    \
                                        Allocator>
 
#define PB_DS_CONST_ODIR_IT_C_DEC                               \
    pat_trie_const_it_<                                         \
                                        Type_Traits,            \
                                        Node,                   \
                                        Leaf,                   \
                                        Head,                   \
                                        Internal_Node,          \
                                        !Is_Forward_Iterator,   \
                                        Allocator>
 
#define PB_DS_IT_C_DEC                                                  \
    pat_trie_it_<                                                       \
                                                Type_Traits,            \
                                                Node,                   \
                                                Leaf,                   \
                                                Head,                   \
                                                Internal_Node,          \
                                                Is_Forward_Iterator,    \
                                                Allocator>
 
#define PB_DS_ODIR_IT_C_DEC                                             \
    pat_trie_it_<                                                       \
                                                Type_Traits,            \
                                                Node,                   \
                                                Leaf,                   \
                                                Head,                   \
                                                Internal_Node,          \
                                                !Is_Forward_Iterator,   \
                                                Allocator>
 
 
    // Const iterator.
    template<typename Type_Traits,
             class Node,
             class Leaf,
             class Head,
             class Internal_Node,
             bool Is_Forward_Iterator,
             class Allocator>
    class pat_trie_const_it_
    {
 
    private:
      typedef
      typename Allocator::template rebind<
      Node>::other::pointer
      node_pointer;
 
      typedef
      typename Allocator::template rebind<
        Leaf>::other::const_pointer
      const_leaf_pointer;
 
      typedef
      typename Allocator::template rebind<
        Leaf>::other::pointer
      leaf_pointer;
 
      typedef
      typename Allocator::template rebind<
        Head>::other::pointer
      head_pointer;
 
      typedef
      typename Allocator::template rebind<
        Internal_Node>::other::pointer
      internal_node_pointer;
 
    public:
 
      typedef std::bidirectional_iterator_tag iterator_category;
 
      typedef typename Allocator::difference_type difference_type;
 
      typedef typename Type_Traits::value_type value_type;
 
      typedef typename Type_Traits::pointer pointer;
 
      typedef typename Type_Traits::const_pointer const_pointer;
 
      typedef typename Type_Traits::reference reference;
 
      typedef typename Type_Traits::const_reference const_reference;
 
    public:
 
      inline
      pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
      { }
 
      inline
      pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)
      : m_p_nd(other.m_p_nd)
      { }
 
      inline
      PB_DS_CONST_IT_C_DEC&
      operator=(const PB_DS_CONST_IT_C_DEC& other)
      {
        m_p_nd = other.m_p_nd;
        return *this;
      }
 
      inline
      PB_DS_CONST_IT_C_DEC&
      operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
      {
        m_p_nd = other.m_p_nd;
        return *this;
      }
 
      inline const_pointer
      operator->() const
      {
        _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
        return &static_cast<leaf_pointer>(m_p_nd)->value();
      }
 
      inline const_reference
      operator*() const
      {
        _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
        return static_cast<leaf_pointer>(m_p_nd)->value();
      }
 
      inline bool
      operator==(const PB_DS_CONST_IT_C_DEC& other) const
      { return (m_p_nd == other.m_p_nd); }
 
      inline bool
      operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
      { return (m_p_nd == other.m_p_nd); }
 
      inline bool
      operator!=(const PB_DS_CONST_IT_C_DEC& other) const
      { return (m_p_nd != other.m_p_nd); }
 
      inline bool
      operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
      { return (m_p_nd != other.m_p_nd); }
 
      inline PB_DS_CONST_IT_C_DEC&
      operator++()
      {
        inc(integral_constant<int,Is_Forward_Iterator>());
        return *this;
      }
 
      inline PB_DS_CONST_IT_C_DEC
      operator++(int)
      {
        PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
        operator++();
        return ret_it;
      }
 
      inline PB_DS_CONST_IT_C_DEC&
      operator--()
      {
        dec(integral_constant<int,Is_Forward_Iterator>());
        return *this;
      }
 
      inline PB_DS_CONST_IT_C_DEC
      operator--(int)
      {
        PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
        operator--();
        return ret_it;
      }
 
    protected:
      inline void
      inc(false_type)
      { dec(true_type()); }
 
      void
      inc(true_type)
      {
        if (m_p_nd->m_type == pat_trie_head_node_type)
          {
            m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
            return;
          }
 
        node_pointer p_y = m_p_nd->m_p_parent;
        while (p_y->m_type != pat_trie_head_node_type &&
               get_larger_sibling(m_p_nd) == NULL)
          {
            m_p_nd = p_y;
            p_y = p_y->m_p_parent;
          }
 
        if (p_y->m_type == pat_trie_head_node_type)
          {
            m_p_nd = p_y;
            return;
          }
        m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
      }
 
      inline void
      dec(false_type)
      { inc(true_type()); }
 
      void
      dec(true_type)
      {
        if (m_p_nd->m_type == pat_trie_head_node_type)
          {
            m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
            return;
          }
 
        node_pointer p_y = m_p_nd->m_p_parent;
        while (p_y->m_type != pat_trie_head_node_type &&
               get_smaller_sibling(m_p_nd) == NULL)
          {
            m_p_nd = p_y;
            p_y = p_y->m_p_parent;
          }
 
        if (p_y->m_type == pat_trie_head_node_type)
          {
            m_p_nd = p_y;
            return;
          }
        m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
      }
 
      inline static node_pointer
      get_larger_sibling(node_pointer p_nd)
      {
        internal_node_pointer p_parent =
          static_cast<internal_node_pointer>(p_nd->m_p_parent);
 
        typename Internal_Node::iterator it = p_parent->begin();
        while (*it != p_nd)
          ++it;
 
        typename Internal_Node::iterator next_it = it;
        ++next_it;
        return ((next_it == p_parent->end())? NULL :* next_it);
      }
 
      inline static node_pointer
      get_smaller_sibling(node_pointer p_nd)
      {
        internal_node_pointer p_parent =
          static_cast<internal_node_pointer>(p_nd->m_p_parent);
 
        typename Internal_Node::iterator it = p_parent->begin();
 
        if (*it == p_nd)
          return (NULL);
        typename Internal_Node::iterator prev_it;
        do
          {
            prev_it = it;
            ++it;
            if (*it == p_nd)
              return (*prev_it);
          }
        while (true);
 
        _GLIBCXX_DEBUG_ASSERT(false);
        return (NULL);
      }
 
      inline static leaf_pointer
      leftmost_descendant(node_pointer p_nd)
      {
        if (p_nd->m_type == pat_trie_leaf_node_type)
          return static_cast<leaf_pointer>(p_nd);
        return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
      }
 
      inline static leaf_pointer
      rightmost_descendant(node_pointer p_nd)
      {
        if (p_nd->m_type == pat_trie_leaf_node_type)
          return static_cast<leaf_pointer>(p_nd);
        return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
      }
 
    public:
      node_pointer m_p_nd;
    };
 
    // Iterator.
    template<typename Type_Traits,
             class Node,
             class Leaf,
             class Head,
             class Internal_Node,
             bool Is_Forward_Iterator,
             class Allocator>
    class pat_trie_it_ :
      public PB_DS_CONST_IT_C_DEC
 
    {
    private:
      typedef
      typename Allocator::template rebind<
      Node>::other::pointer
      node_pointer;
 
      typedef
      typename Allocator::template rebind<
        Leaf>::other::const_pointer
      const_leaf_pointer;
 
      typedef
      typename Allocator::template rebind<
        Leaf>::other::pointer
      leaf_pointer;
 
      typedef
      typename Allocator::template rebind<
        Head>::other::pointer
      head_pointer;
 
      typedef
      typename Allocator::template rebind<
        Internal_Node>::other::pointer
      internal_node_pointer;
 
    public:
      typedef typename Type_Traits::value_type value_type;
 
      typedef typename Type_Traits::const_pointer const_pointer;
 
      typedef typename Type_Traits::pointer pointer;
 
      typedef typename Type_Traits::const_reference const_reference;
 
      typedef typename Type_Traits::reference reference;
 
      inline
      pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
      { }
 
      inline
      pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
      { }
 
      inline
      PB_DS_IT_C_DEC&
      operator=(const PB_DS_IT_C_DEC& other)
      {
        base_it_type::m_p_nd = other.m_p_nd;
        return *this;
      }
 
      inline
      PB_DS_IT_C_DEC&
      operator=(const PB_DS_ODIR_IT_C_DEC& other)
      {
        base_it_type::m_p_nd = other.m_p_nd;
        return *this;
      }
 
      inline pointer
      operator->() const
      {
        _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
 
        return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
      }
 
      inline reference
      operator*() const
      {
        _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
        return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
      }
 
      inline PB_DS_IT_C_DEC&
      operator++()
      {
        PB_DS_CONST_IT_C_DEC::
          operator++();
        return *this;
      }
 
      inline PB_DS_IT_C_DEC
      operator++(int)
      {
        PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
        operator++();
        return ret_it;
      }
 
      inline PB_DS_IT_C_DEC&
      operator--()
      {
        PB_DS_CONST_IT_C_DEC::operator--();
        return *this;
      }
 
      inline PB_DS_IT_C_DEC
      operator--(int)
      {
        PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
        operator--();
        return ret_it;
      }
 
    protected:
      typedef PB_DS_CONST_IT_C_DEC base_it_type;
 
      friend class PB_DS_CLASS_C_DEC;
    };
 
#undef PB_DS_CONST_IT_C_DEC
#undef PB_DS_CONST_ODIR_IT_C_DEC
#undef PB_DS_IT_C_DEC
#undef PB_DS_ODIR_IT_C_DEC
 
  } // namespace detail
} // namespace __gnu_pbds
 
#endif 
 

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc4/] [libstdc++-v3/] [include/] [ext/] [pb_ds/] [detail/] [pat_trie_/] [point_iterators.hpp] - Blame information for rev 424

Line No.	Rev	Author	Line
1	424	jeremybenn	`// -- C++ --`
2
3			`// Copyright (C) 2005, 2006, 2009 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 point_iterators.hpp`
38			`* Contains an implementation class for bin_search_tree_.`
39			`*/`
40
41			`#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP`
42			`#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP`
43
44			`#include <debug/debug.h>`
45
46			`namespace __gnu_pbds`
47			`{`
48			`namespace detail`
49			`{`
50
51			`#define PB_DS_CONST_IT_C_DEC \`
52			`pat_trie_const_it_< \`
53			`Type_Traits, \`
54			`Node, \`
55			`Leaf, \`
56			`Head, \`
57			`Internal_Node, \`
58			`Is_Forward_Iterator, \`
59			`Allocator>`
60
61			`#define PB_DS_CONST_ODIR_IT_C_DEC \`
62			`pat_trie_const_it_< \`
63			`Type_Traits, \`
64			`Node, \`
65			`Leaf, \`
66			`Head, \`
67			`Internal_Node, \`
68			`!Is_Forward_Iterator, \`
69			`Allocator>`
70
71			`#define PB_DS_IT_C_DEC \`
72			`pat_trie_it_< \`
73			`Type_Traits, \`
74			`Node, \`
75			`Leaf, \`
76			`Head, \`
77			`Internal_Node, \`
78			`Is_Forward_Iterator, \`
79			`Allocator>`
80
81			`#define PB_DS_ODIR_IT_C_DEC \`
82			`pat_trie_it_< \`
83			`Type_Traits, \`
84			`Node, \`
85			`Leaf, \`
86			`Head, \`
87			`Internal_Node, \`
88			`!Is_Forward_Iterator, \`
89			`Allocator>`
90
91
92			`// Const iterator.`
93			`template<typename Type_Traits,`
94			`class Node,`
95			`class Leaf,`
96			`class Head,`
97			`class Internal_Node,`
98			`bool Is_Forward_Iterator,`
99			`class Allocator>`
100			`class pat_trie_const_it_`
101			`{`
102
103			`private:`
104			`typedef`
105			`typename Allocator::template rebind<`
106			`Node>::other::pointer`
107			`node_pointer;`
108
109			`typedef`
110			`typename Allocator::template rebind<`
111			`Leaf>::other::const_pointer`
112			`const_leaf_pointer;`
113
114			`typedef`
115			`typename Allocator::template rebind<`
116			`Leaf>::other::pointer`
117			`leaf_pointer;`
118
119			`typedef`
120			`typename Allocator::template rebind<`
121			`Head>::other::pointer`
122			`head_pointer;`
123
124			`typedef`
125			`typename Allocator::template rebind<`
126			`Internal_Node>::other::pointer`
127			`internal_node_pointer;`
128
129			`public:`
130
131			`typedef std::bidirectional_iterator_tag iterator_category;`
132
133			`typedef typename Allocator::difference_type difference_type;`
134
135			`typedef typename Type_Traits::value_type value_type;`
136
137			`typedef typename Type_Traits::pointer pointer;`
138
139			`typedef typename Type_Traits::const_pointer const_pointer;`
140
141			`typedef typename Type_Traits::reference reference;`
142
143			`typedef typename Type_Traits::const_reference const_reference;`
144
145			`public:`
146
147			`inline`
148			`pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)`
149			`{ }`
150
151			`inline`
152			`pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)`
153			`: m_p_nd(other.m_p_nd)`
154			`{ }`
155
156			`inline`
157			`PB_DS_CONST_IT_C_DEC&`
158			`operator=(const PB_DS_CONST_IT_C_DEC& other)`
159			`{`
160			`m_p_nd = other.m_p_nd;`
161			`return *this;`
162			`}`
163
164			`inline`
165			`PB_DS_CONST_IT_C_DEC&`
166			`operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)`
167			`{`
168			`m_p_nd = other.m_p_nd;`
169			`return *this;`
170			`}`
171
172			`inline const_pointer`
173			`operator->() const`
174			`{`
175			`_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);`
176			`return &static_cast<leaf_pointer>(m_p_nd)->value();`
177			`}`
178
179			`inline const_reference`
180			`operator*() const`
181			`{`
182			`_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);`
183			`return static_cast<leaf_pointer>(m_p_nd)->value();`
184			`}`
185
186			`inline bool`
187			`operator==(const PB_DS_CONST_IT_C_DEC& other) const`
188			`{ return (m_p_nd == other.m_p_nd); }`
189
190			`inline bool`
191			`operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const`
192			`{ return (m_p_nd == other.m_p_nd); }`
193
194			`inline bool`
195			`operator!=(const PB_DS_CONST_IT_C_DEC& other) const`
196			`{ return (m_p_nd != other.m_p_nd); }`
197
198			`inline bool`
199			`operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const`
200			`{ return (m_p_nd != other.m_p_nd); }`
201
202			`inline PB_DS_CONST_IT_C_DEC&`
203			`operator++()`
204			`{`
205			`inc(integral_constant<int,Is_Forward_Iterator>());`
206			`return *this;`
207			`}`
208
209			`inline PB_DS_CONST_IT_C_DEC`
210			`operator++(int)`
211			`{`
212			`PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);`
213			`operator++();`
214			`return ret_it;`
215			`}`
216
217			`inline PB_DS_CONST_IT_C_DEC&`
218			`operator--()`
219			`{`
220			`dec(integral_constant<int,Is_Forward_Iterator>());`
221			`return *this;`
222			`}`
223
224			`inline PB_DS_CONST_IT_C_DEC`
225			`operator--(int)`
226			`{`
227			`PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);`
228			`operator--();`
229			`return ret_it;`
230			`}`
231
232			`protected:`
233			`inline void`
234			`inc(false_type)`
235			`{ dec(true_type()); }`
236
237			`void`
238			`inc(true_type)`
239			`{`
240			`if (m_p_nd->m_type == pat_trie_head_node_type)`
241			`{`
242			`m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;`
243			`return;`
244			`}`
245
246			`node_pointer p_y = m_p_nd->m_p_parent;`
247			`while (p_y->m_type != pat_trie_head_node_type &&`
248			`get_larger_sibling(m_p_nd) == NULL)`
249			`{`
250			`m_p_nd = p_y;`
251			`p_y = p_y->m_p_parent;`
252			`}`
253
254			`if (p_y->m_type == pat_trie_head_node_type)`
255			`{`
256			`m_p_nd = p_y;`
257			`return;`
258			`}`
259			`m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));`
260			`}`
261
262			`inline void`
263			`dec(false_type)`
264			`{ inc(true_type()); }`
265
266			`void`
267			`dec(true_type)`
268			`{`
269			`if (m_p_nd->m_type == pat_trie_head_node_type)`
270			`{`
271			`m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;`
272			`return;`
273			`}`
274
275			`node_pointer p_y = m_p_nd->m_p_parent;`
276			`while (p_y->m_type != pat_trie_head_node_type &&`
277			`get_smaller_sibling(m_p_nd) == NULL)`
278			`{`
279			`m_p_nd = p_y;`
280			`p_y = p_y->m_p_parent;`
281			`}`
282
283			`if (p_y->m_type == pat_trie_head_node_type)`
284			`{`
285			`m_p_nd = p_y;`
286			`return;`
287			`}`
288			`m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));`
289			`}`
290
291			`inline static node_pointer`
292			`get_larger_sibling(node_pointer p_nd)`
293			`{`
294			`internal_node_pointer p_parent =`
295			`static_cast<internal_node_pointer>(p_nd->m_p_parent);`
296
297			`typename Internal_Node::iterator it = p_parent->begin();`
298			`while (*it != p_nd)`
299			`++it;`
300
301			`typename Internal_Node::iterator next_it = it;`
302			`++next_it;`
303			`return ((next_it == p_parent->end())? NULL :* next_it);`
304			`}`
305
306			`inline static node_pointer`
307			`get_smaller_sibling(node_pointer p_nd)`
308			`{`
309			`internal_node_pointer p_parent =`
310			`static_cast<internal_node_pointer>(p_nd->m_p_parent);`
311
312			`typename Internal_Node::iterator it = p_parent->begin();`
313
314			`if (*it == p_nd)`
315			`return (NULL);`
316			`typename Internal_Node::iterator prev_it;`
317			`do`
318			`{`
319			`prev_it = it;`
320			`++it;`
321			`if (*it == p_nd)`
322			`return (*prev_it);`
323			`}`
324			`while (true);`
325
326			`_GLIBCXX_DEBUG_ASSERT(false);`
327			`return (NULL);`
328			`}`
329
330			`inline static leaf_pointer`
331			`leftmost_descendant(node_pointer p_nd)`
332			`{`
333			`if (p_nd->m_type == pat_trie_leaf_node_type)`
334			`return static_cast<leaf_pointer>(p_nd);`
335			`return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();`
336			`}`
337
338			`inline static leaf_pointer`
339			`rightmost_descendant(node_pointer p_nd)`
340			`{`
341			`if (p_nd->m_type == pat_trie_leaf_node_type)`
342			`return static_cast<leaf_pointer>(p_nd);`
343			`return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();`
344			`}`
345
346			`public:`
347			`node_pointer m_p_nd;`
348			`};`
349
350			`// Iterator.`
351			`template<typename Type_Traits,`
352			`class Node,`
353			`class Leaf,`
354			`class Head,`
355			`class Internal_Node,`
356			`bool Is_Forward_Iterator,`
357			`class Allocator>`
358			`class pat_trie_it_ :`
359			`public PB_DS_CONST_IT_C_DEC`
360
361			`{`
362			`private:`
363			`typedef`
364			`typename Allocator::template rebind<`
365			`Node>::other::pointer`
366			`node_pointer;`
367
368			`typedef`
369			`typename Allocator::template rebind<`
370			`Leaf>::other::const_pointer`
371			`const_leaf_pointer;`
372
373			`typedef`
374			`typename Allocator::template rebind<`
375			`Leaf>::other::pointer`
376			`leaf_pointer;`
377
378			`typedef`
379			`typename Allocator::template rebind<`
380			`Head>::other::pointer`
381			`head_pointer;`
382
383			`typedef`
384			`typename Allocator::template rebind<`
385			`Internal_Node>::other::pointer`
386			`internal_node_pointer;`
387
388			`public:`
389			`typedef typename Type_Traits::value_type value_type;`
390
391			`typedef typename Type_Traits::const_pointer const_pointer;`
392
393			`typedef typename Type_Traits::pointer pointer;`
394
395			`typedef typename Type_Traits::const_reference const_reference;`
396
397			`typedef typename Type_Traits::reference reference;`
398
399			`inline`
400			`pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)`
401			`{ }`
402
403			`inline`
404			`pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)`
405			`{ }`
406
407			`inline`
408			`PB_DS_IT_C_DEC&`
409			`operator=(const PB_DS_IT_C_DEC& other)`
410			`{`
411			`base_it_type::m_p_nd = other.m_p_nd;`
412			`return *this;`
413			`}`
414
415			`inline`
416			`PB_DS_IT_C_DEC&`
417			`operator=(const PB_DS_ODIR_IT_C_DEC& other)`
418			`{`
419			`base_it_type::m_p_nd = other.m_p_nd;`
420			`return *this;`
421			`}`
422
423			`inline pointer`
424			`operator->() const`
425			`{`
426			`_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);`
427
428			`return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();`
429			`}`
430
431			`inline reference`
432			`operator*() const`
433			`{`
434			`_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);`
435			`return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();`
436			`}`
437
438			`inline PB_DS_IT_C_DEC&`
439			`operator++()`
440			`{`
441			`PB_DS_CONST_IT_C_DEC::`
442			`operator++();`
443			`return *this;`
444			`}`
445
446			`inline PB_DS_IT_C_DEC`
447			`operator++(int)`
448			`{`
449			`PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);`
450			`operator++();`
451			`return ret_it;`
452			`}`
453
454			`inline PB_DS_IT_C_DEC&`
455			`operator--()`
456			`{`
457			`PB_DS_CONST_IT_C_DEC::operator--();`
458			`return *this;`
459			`}`
460
461			`inline PB_DS_IT_C_DEC`
462			`operator--(int)`
463			`{`
464			`PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);`
465			`operator--();`
466			`return ret_it;`
467			`}`
468
469			`protected:`
470			`typedef PB_DS_CONST_IT_C_DEC base_it_type;`
471
472			`friend class PB_DS_CLASS_C_DEC;`
473			`};`
474
475			`#undef PB_DS_CONST_IT_C_DEC`
476			`#undef PB_DS_CONST_ODIR_IT_C_DEC`
477			`#undef PB_DS_IT_C_DEC`
478			`#undef PB_DS_ODIR_IT_C_DEC`
479
480			`} // namespace detail`
481			`} // namespace __gnu_pbds`
482
483			`#endif`
484