1169691Skan// -*- C++ -*-
2169691Skan
3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
4169691Skan//
5169691Skan// This file is part of the GNU ISO C++ Library.  This library is free
6169691Skan// software; you can redistribute it and/or modify it under the terms
7169691Skan// of the GNU General Public License as published by the Free Software
8169691Skan// Foundation; either version 2, or (at your option) any later
9169691Skan// version.
10169691Skan
11169691Skan// This library is distributed in the hope that it will be useful, but
12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of
13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14169691Skan// General Public License for more details.
15169691Skan
16169691Skan// You should have received a copy of the GNU General Public License
17169691Skan// along with this library; see the file COPYING.  If not, write to
18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19169691Skan// MA 02111-1307, USA.
20169691Skan
21169691Skan// As a special exception, you may use this file as part of a free
22169691Skan// software library without restriction.  Specifically, if other files
23169691Skan// instantiate templates or use macros or inline functions from this
24169691Skan// file, or you compile this file and link it with other files to
25169691Skan// produce an executable, this file does not by itself cause the
26169691Skan// resulting executable to be covered by the GNU General Public
27169691Skan// License.  This exception does not however invalidate any other
28169691Skan// reasons why the executable file might be covered by the GNU General
29169691Skan// Public License.
30169691Skan
31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32169691Skan
33169691Skan// Permission to use, copy, modify, sell, and distribute this software
34169691Skan// is hereby granted without fee, provided that the above copyright
35169691Skan// notice appears in all copies, and that both that copyright notice
36169691Skan// and this permission notice appear in supporting documentation. None
37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any
38169691Skan// representation about the suitability of this software for any
39169691Skan// purpose. It is provided "as is" without express or implied
40169691Skan// warranty.
41169691Skan
42169691Skan/**
43169691Skan * @file trie_policy_base.hpp
44169691Skan * Contains an implementation of trie_policy_base.
45169691Skan */
46169691Skan
47169691Skan#ifndef PB_DS_TRIE_POLICY_BASE_HPP
48169691Skan#define PB_DS_TRIE_POLICY_BASE_HPP
49169691Skan
50169691Skan#include <ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp>
51169691Skan
52169691Skannamespace pb_ds
53169691Skan{
54169691Skan  namespace detail
55169691Skan  {
56169691Skan
57169691Skan#define PB_DS_CLASS_T_DEC						\
58169691Skan    template<								\
59169691Skan						class Const_Node_Iterator, \
60169691Skan						class Node_Iterator,	\
61169691Skan						class E_Access_Traits,	\
62169691Skan						typename Allocator>
63169691Skan
64169691Skan#define PB_DS_CLASS_C_DEC						\
65169691Skan    trie_policy_base<							\
66169691Skan						Const_Node_Iterator,	\
67169691Skan						Node_Iterator,		\
68169691Skan						E_Access_Traits,	\
69169691Skan						Allocator>
70169691Skan
71169691Skan#define PB_DS_BASE_C_DEC						\
72169691Skan    basic_tree_policy_base<				\
73169691Skan								Const_Node_Iterator, \
74169691Skan								Node_Iterator, \
75169691Skan								Allocator>
76169691Skan
77169691Skan    template<typename Const_Node_Iterator,
78169691Skan	     class Node_Iterator,
79169691Skan	     class E_Access_Traits,
80169691Skan	     class Allocator>
81169691Skan    class trie_policy_base : public PB_DS_BASE_C_DEC
82169691Skan    {
83169691Skan
84169691Skan    public:
85169691Skan
86169691Skan      typedef E_Access_Traits e_access_traits;
87169691Skan
88169691Skan      typedef Allocator allocator;
89169691Skan
90169691Skan      typedef typename allocator::size_type size_type;
91169691Skan
92169691Skan      typedef null_node_metadata metadata_type;
93169691Skan
94169691Skan      typedef Const_Node_Iterator const_node_iterator;
95169691Skan
96169691Skan      typedef Node_Iterator node_iterator;
97169691Skan
98169691Skan      typedef typename const_node_iterator::value_type const_iterator;
99169691Skan
100169691Skan      typedef typename node_iterator::value_type iterator;
101169691Skan
102169691Skan    public:
103169691Skan
104169691Skan      typedef typename PB_DS_BASE_C_DEC::key_type key_type;
105169691Skan
106169691Skan      typedef
107169691Skan      typename PB_DS_BASE_C_DEC::const_key_reference
108169691Skan      const_key_reference;
109169691Skan
110169691Skan    protected:
111169691Skan
112169691Skan      virtual const_iterator
113169691Skan      end() const = 0;
114169691Skan
115169691Skan      virtual iterator
116169691Skan      end() = 0;
117169691Skan
118169691Skan      virtual const_node_iterator
119169691Skan      node_begin() const = 0;
120169691Skan
121169691Skan      virtual node_iterator
122169691Skan      node_begin() = 0;
123169691Skan
124169691Skan      virtual const_node_iterator
125169691Skan      node_end() const = 0;
126169691Skan
127169691Skan      virtual node_iterator
128169691Skan      node_end() = 0;
129169691Skan
130169691Skan      virtual const e_access_traits&
131169691Skan      get_e_access_traits() const = 0;
132169691Skan
133169691Skan    private:
134169691Skan      typedef
135169691Skan      std::pair<
136169691Skan      typename e_access_traits::const_iterator,
137169691Skan      typename e_access_traits::const_iterator>
138169691Skan      prefix_range_t;
139169691Skan
140169691Skan      typedef PB_DS_BASE_C_DEC base_type;
141169691Skan
142169691Skan    protected:
143169691Skan      static size_type
144169691Skan      common_prefix_len(node_iterator nd_it, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits);
145169691Skan
146169691Skan      static iterator
147169691Skan      leftmost_it(node_iterator nd_it);
148169691Skan
149169691Skan      static iterator
150169691Skan      rightmost_it(node_iterator nd_it);
151169691Skan
152169691Skan      static bool
153169691Skan      less(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits);
154169691Skan    };
155169691Skan
156169691Skan    PB_DS_CLASS_T_DEC
157169691Skan    typename PB_DS_CLASS_C_DEC::size_type
158169691Skan    PB_DS_CLASS_C_DEC::
159169691Skan    common_prefix_len(node_iterator nd_it, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits)
160169691Skan    {
161169691Skan      prefix_range_t pref_range = nd_it.valid_prefix();
162169691Skan
163169691Skan      typename e_access_traits::const_iterator b_l = pref_range.first;
164169691Skan      typename e_access_traits::const_iterator e_l = pref_range.second;
165169691Skan
166169691Skan      const size_type range_length_l =
167169691Skan	std::distance(b_l, e_l);
168169691Skan
169169691Skan      const size_type range_length_r =
170169691Skan	std::distance(b_r, e_r);
171169691Skan
172169691Skan      if (range_length_r < range_length_l)
173169691Skan	{
174169691Skan	  std::swap(b_l, b_r);
175169691Skan
176169691Skan	  std::swap(e_l, e_r);
177169691Skan	}
178169691Skan
179169691Skan      size_type ret = 0;
180169691Skan
181169691Skan      while (b_l != e_l)
182169691Skan	{
183169691Skan	  if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r))
184169691Skan	    return (ret);
185169691Skan
186169691Skan	  ++ret;
187169691Skan
188169691Skan	  ++b_l;
189169691Skan
190169691Skan	  ++b_r;
191169691Skan	}
192169691Skan
193169691Skan      return (ret);
194169691Skan    }
195169691Skan
196169691Skan    PB_DS_CLASS_T_DEC
197169691Skan    typename PB_DS_CLASS_C_DEC::iterator
198169691Skan    PB_DS_CLASS_C_DEC::
199169691Skan    leftmost_it(node_iterator nd_it)
200169691Skan    {
201169691Skan      if (nd_it.num_children() == 0)
202169691Skan	return (*nd_it);
203169691Skan
204169691Skan      return (leftmost_it(nd_it.get_child(0)));
205169691Skan    }
206169691Skan
207169691Skan    PB_DS_CLASS_T_DEC
208169691Skan    typename PB_DS_CLASS_C_DEC::iterator
209169691Skan    PB_DS_CLASS_C_DEC::
210169691Skan    rightmost_it(node_iterator nd_it)
211169691Skan    {
212169691Skan      const size_type num_children = nd_it.num_children();
213169691Skan
214169691Skan      if (num_children == 0)
215169691Skan	return (*nd_it);
216169691Skan
217169691Skan      return (rightmost_it(nd_it.get_child(num_children - 1)));
218169691Skan    }
219169691Skan
220169691Skan    PB_DS_CLASS_T_DEC
221169691Skan    bool
222169691Skan    PB_DS_CLASS_C_DEC::
223169691Skan    less(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r, const e_access_traits& r_traits)
224169691Skan    {
225169691Skan      while (b_l != e_l)
226169691Skan	{
227169691Skan	  if (b_r == e_r)
228169691Skan	    return (false);
229169691Skan
230169691Skan	  size_type l_pos =
231169691Skan	    r_traits.e_pos(*b_l);
232169691Skan	  size_type r_pos =
233169691Skan	    r_traits.e_pos(*b_r);
234169691Skan
235169691Skan	  if (l_pos != r_pos)
236169691Skan	    return (l_pos < r_pos);
237169691Skan
238169691Skan	  ++b_l;
239169691Skan	  ++b_r;
240169691Skan	}
241169691Skan
242169691Skan      return (b_r != e_r);
243169691Skan    }
244169691Skan
245169691Skan#undef PB_DS_CLASS_T_DEC
246169691Skan
247169691Skan#undef PB_DS_CLASS_C_DEC
248169691Skan
249169691Skan#undef PB_DS_BASE_C_DEC
250169691Skan
251169691Skan  } // namespace detail
252169691Skan} // namespace pb_ds
253169691Skan
254169691Skan#endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP
255169691Skan
256