OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [ext/] [pb_ds/] [detail/] [trie_policy/] [trie_policy_base.hpp] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe
// -*- 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 trie_policy/trie_policy_base.hpp
38
 * Contains an implementation of trie_policy_base.
39
 */
40
 
41
#ifndef PB_DS_TRIE_POLICY_BASE_HPP
42
#define PB_DS_TRIE_POLICY_BASE_HPP
43
 
44
#include <ext/pb_ds/detail/branch_policy/branch_policy.hpp>
45
 
46
namespace __gnu_pbds
47
{
48
  namespace detail
49
  {
50
    /// Base class for trie policies.
51
    template<typename Node_CItr, typename Node_Itr,
52
             typename _ATraits, typename _Alloc>
53
    class trie_policy_base
54
    : public branch_policy<Node_CItr, Node_Itr, _Alloc>
55
    {
56
      typedef branch_policy<Node_CItr, Node_Itr, _Alloc> base_type;
57
 
58
    public:
59
      typedef _ATraits                          access_traits;
60
      typedef _Alloc                                    allocator_type;
61
      typedef typename allocator_type::size_type        size_type;
62
      typedef null_type                                 metadata_type;
63
      typedef Node_CItr                                 node_const_iterator;
64
      typedef Node_Itr                                  node_iterator;
65
      typedef typename node_const_iterator::value_type  const_iterator;
66
      typedef typename node_iterator::value_type        iterator;
67
      typedef typename base_type::key_type              key_type;
68
      typedef typename base_type::key_const_reference   key_const_reference;
69
 
70
    protected:
71
      virtual const_iterator
72
      end() const = 0;
73
 
74
      virtual iterator
75
      end() = 0;
76
 
77
      virtual node_const_iterator
78
      node_begin() const = 0;
79
 
80
      virtual node_iterator
81
      node_begin() = 0;
82
 
83
      virtual node_const_iterator
84
      node_end() const = 0;
85
 
86
      virtual node_iterator
87
      node_end() = 0;
88
 
89
      virtual const access_traits&
90
      get_access_traits() const = 0;
91
 
92
    private:
93
      typedef typename access_traits::const_iterator    e_const_iterator;
94
      typedef std::pair<e_const_iterator, e_const_iterator> prefix_range_t;
95
 
96
    protected:
97
      static size_type
98
      common_prefix_len(node_iterator, e_const_iterator,
99
                        e_const_iterator, const access_traits&);
100
 
101
      static iterator
102
      leftmost_it(node_iterator);
103
 
104
      static iterator
105
      rightmost_it(node_iterator);
106
 
107
      static bool
108
      less(e_const_iterator, e_const_iterator, e_const_iterator,
109
           e_const_iterator, const access_traits&);
110
    };
111
 
112
 
113
#define PB_DS_CLASS_T_DEC \
114
    template<typename Node_CItr, typename Node_Itr, \
115
             typename _ATraits, typename _Alloc>
116
 
117
#define PB_DS_CLASS_C_DEC \
118
    trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc>
119
 
120
    PB_DS_CLASS_T_DEC
121
    typename PB_DS_CLASS_C_DEC::size_type
122
    PB_DS_CLASS_C_DEC::
123
    common_prefix_len(node_iterator nd_it, e_const_iterator b_r,
124
                      e_const_iterator e_r, const access_traits& r_traits)
125
    {
126
      prefix_range_t pref_range = nd_it.valid_prefix();
127
 
128
      e_const_iterator b_l = pref_range.first;
129
      e_const_iterator e_l = pref_range.second;
130
 
131
      const size_type range_length_l = std::distance(b_l, e_l);
132
      const size_type range_length_r = std::distance(b_r, e_r);
133
 
134
      if (range_length_r < range_length_l)
135
        {
136
          std::swap(b_l, b_r);
137
          std::swap(e_l, e_r);
138
        }
139
 
140
      size_type ret = 0;
141
      while (b_l != e_l)
142
        {
143
          if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r))
144
            return ret;
145
 
146
          ++ret;
147
          ++b_l;
148
          ++b_r;
149
        }
150
 
151
      return ret;
152
    }
153
 
154
    PB_DS_CLASS_T_DEC
155
    typename PB_DS_CLASS_C_DEC::iterator
156
    PB_DS_CLASS_C_DEC::
157
    leftmost_it(node_iterator nd_it)
158
    {
159
      if (nd_it.num_children() == 0)
160
        return *nd_it;
161
 
162
      return leftmost_it(nd_it.get_child(0));
163
    }
164
 
165
    PB_DS_CLASS_T_DEC
166
    typename PB_DS_CLASS_C_DEC::iterator
167
    PB_DS_CLASS_C_DEC::
168
    rightmost_it(node_iterator nd_it)
169
    {
170
      const size_type num_children = nd_it.num_children();
171
 
172
      if (num_children == 0)
173
        return *nd_it;
174
 
175
      return rightmost_it(nd_it.get_child(num_children - 1));
176
    }
177
 
178
    PB_DS_CLASS_T_DEC
179
    bool
180
    PB_DS_CLASS_C_DEC::
181
    less(e_const_iterator b_l, e_const_iterator e_l,
182
         e_const_iterator b_r, e_const_iterator e_r,
183
         const access_traits& r_traits)
184
    {
185
      while (b_l != e_l)
186
        {
187
          if (b_r == e_r)
188
            return false;
189
 
190
          size_type l_pos = r_traits.e_pos(*b_l);
191
          size_type r_pos = r_traits.e_pos(*b_r);
192
          if (l_pos != r_pos)
193
            return (l_pos < r_pos);
194
 
195
          ++b_l;
196
          ++b_r;
197
        }
198
      return b_r != e_r;
199
    }
200
 
201
#undef PB_DS_CLASS_T_DEC
202
#undef PB_DS_CLASS_C_DEC
203
 
204
  } // namespace detail
205
} // namespace __gnu_pbds
206
 
207
#endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.