1// -*- 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 leaf.hpp
38 * Contains a pat_trie_leaf for a patricia tree.
39 */
40
41#ifndef PB_DS_PAT_TRIE_LEAF_HPP
42#define PB_DS_PAT_TRIE_LEAF_HPP
43
44#include <debug/debug.h>
45
46namespace __gnu_pbds
47{
48  namespace detail
49  {
50
51#define PB_DS_CLASS_T_DEC						\
52    template<								\
53						class Type_Traits,	\
54						class E_Access_Traits,	\
55						class Metadata,		\
56						class Allocator>
57
58#define PB_DS_CLASS_C_DEC						\
59    pat_trie_leaf<							\
60						Type_Traits,		\
61						E_Access_Traits,	\
62						Metadata,		\
63						Allocator>
64
65#define PB_DS_BASE_C_DEC					\
66    pat_trie_node_base<						\
67					Type_Traits,		\
68					E_Access_Traits,	\
69					Metadata,		\
70					Allocator>
71
72#define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC				\
73    pat_trie_subtree_debug_info<					\
74							Type_Traits,	\
75							E_Access_Traits, \
76							Allocator>
77
78    template<typename Type_Traits,
79	     class E_Access_Traits,
80	     class Metadata,
81	     class Allocator>
82    struct pat_trie_leaf : public PB_DS_BASE_C_DEC
83    {
84    private:
85      typedef typename Type_Traits::value_type value_type;
86
87      typedef typename Type_Traits::const_reference const_reference;
88
89      typedef typename Type_Traits::reference reference;
90
91      typedef
92      typename Allocator::template rebind<
93	E_Access_Traits>::other::const_pointer
94      const_e_access_traits_pointer;
95
96#ifdef _GLIBCXX_DEBUG
97      typedef
98      typename PB_DS_BASE_C_DEC::subtree_debug_info
99      subtree_debug_info;
100#endif
101
102      typedef PB_DS_BASE_C_DEC base_type;
103
104    public:
105      pat_trie_leaf(const_reference r_val);
106
107      inline reference
108      value();
109
110      inline const_reference
111      value() const;
112
113#ifdef _GLIBCXX_DEBUG
114      virtual subtree_debug_info
115      assert_valid_imp(const_e_access_traits_pointer p_traits) const;
116
117      virtual
118      ~pat_trie_leaf();
119#endif
120
121    private:
122      pat_trie_leaf(const PB_DS_CLASS_C_DEC& other);
123
124      value_type m_value;
125    };
126
127    PB_DS_CLASS_T_DEC
128    PB_DS_CLASS_C_DEC::
129    pat_trie_leaf(const_reference r_val) :
130    PB_DS_BASE_C_DEC(pat_trie_leaf_node_type), m_value(r_val)
131    { }
132
133    PB_DS_CLASS_T_DEC
134    inline typename PB_DS_CLASS_C_DEC::reference
135    PB_DS_CLASS_C_DEC::
136    value()
137    { return m_value; }
138
139    PB_DS_CLASS_T_DEC
140    inline typename PB_DS_CLASS_C_DEC::const_reference
141    PB_DS_CLASS_C_DEC::
142    value() const
143    { return m_value; }
144
145#ifdef _GLIBCXX_DEBUG
146    PB_DS_CLASS_T_DEC
147    typename PB_DS_CLASS_C_DEC::subtree_debug_info
148    PB_DS_CLASS_C_DEC::
149    assert_valid_imp(const_e_access_traits_pointer p_traits) const
150    {
151      _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_leaf_node_type);
152      subtree_debug_info ret;
153      const_reference r_val = value();
154      return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)),
155			     p_traits->end(p_traits->extract_key(r_val)));
156    }
157
158    PB_DS_CLASS_T_DEC
159    PB_DS_CLASS_C_DEC::
160    ~pat_trie_leaf() { }
161#endif
162
163#undef PB_DS_CLASS_T_DEC
164#undef PB_DS_CLASS_C_DEC
165#undef PB_DS_BASE_C_DEC
166#undef PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC
167
168  } // namespace detail
169} // namespace __gnu_pbds
170
171#endif
172