133965Sjdp// -*- C++ -*- 278828Sobrien 3218822Sdim// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 478828Sobrien// 533965Sjdp// This file is part of the GNU ISO C++ Library. This library is free 633965Sjdp// software; you can redistribute it and/or modify it under the terms 733965Sjdp// of the GNU General Public License as published by the Free Software 833965Sjdp// Foundation; either version 2, or (at your option) any later 933965Sjdp// version. 1033965Sjdp 1133965Sjdp// This library is distributed in the hope that it will be useful, but 1233965Sjdp// WITHOUT ANY WARRANTY; without even the implied warranty of 1333965Sjdp// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1477298Sobrien// General Public License for more details. 1533965Sjdp 1633965Sjdp// You should have received a copy of the GNU General Public License 1733965Sjdp// along with this library; see the file COPYING. If not, write to 1833965Sjdp// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1933965Sjdp// MA 02111-1307, USA. 2033965Sjdp 2133965Sjdp// As a special exception, you may use this file as part of a free 2233965Sjdp// software library without restriction. Specifically, if other files 2333965Sjdp// instantiate templates or use macros or inline functions from this 2433965Sjdp// file, or you compile this file and link it with other files to 2533965Sjdp// produce an executable, this file does not by itself cause the 2633965Sjdp// resulting executable to be covered by the GNU General Public 2733965Sjdp// License. This exception does not however invalidate any other 2833965Sjdp// reasons why the executable file might be covered by the GNU General 2933965Sjdp// Public License. 3033965Sjdp 3133965Sjdp// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3233965Sjdp 3333965Sjdp// Permission to use, copy, modify, sell, and distribute this software 3433965Sjdp// is hereby granted without fee, provided that the above copyright 3533965Sjdp// notice appears in all copies, and that both that copyright notice 3633965Sjdp// and this permission notice appear in supporting documentation. None 3733965Sjdp// of the above authors, nor IBM Haifa Research Laboratories, make any 3833965Sjdp// representation about the suitability of this software for any 3933965Sjdp// purpose. It is provided "as is" without express or implied 4033965Sjdp// warranty. 4133965Sjdp 4233965Sjdp/** 4333965Sjdp * @file traits.hpp 4433965Sjdp * Contains an implementation class for ov_tree_. 4560484Sobrien */ 4660484Sobrien 4733965Sjdp#ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP 4860484Sobrien#define PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP 4960484Sobrien 5060484Sobrien#include <ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp> 5160484Sobrien 5260484Sobriennamespace pb_ds 5360484Sobrien{ 5433965Sjdp namespace detail 5533965Sjdp { 5633965Sjdp 5733965Sjdp template<typename Key, 5889857Sobrien typename Mapped, 5989857Sobrien class Cmp_Fn, 6033965Sjdp template<typename Const_Node_Iterator, 6133965Sjdp class Node_Iterator, 6289857Sobrien class Cmp_Fn_, 6389857Sobrien class Allocator_> 6433965Sjdp class Node_Update, 6533965Sjdp class Allocator> 6633965Sjdp struct tree_traits< 6733965Sjdp Key, 6833965Sjdp Mapped, 6933965Sjdp Cmp_Fn, 7033965Sjdp Node_Update, 7133965Sjdp ov_tree_tag, 7233965Sjdp Allocator> 7333965Sjdp { 7433965Sjdp private: 7533965Sjdp typedef 7633965Sjdp typename types_traits< 7733965Sjdp Key, 7833965Sjdp Mapped, 7933965Sjdp Allocator, 80218822Sdim false>::value_type 81218822Sdim value_type; 8233965Sjdp 8333965Sjdp public: 8433965Sjdp typedef 8533965Sjdp typename tree_node_metadata_selector< 8633965Sjdp Key, 8733965Sjdp Mapped, 8833965Sjdp Cmp_Fn, 8933965Sjdp Node_Update, 9033965Sjdp Allocator>::type 9133965Sjdp metadata_type; 9233965Sjdp 9333965Sjdp typedef 9433965Sjdp ov_tree_node_const_it_< 9533965Sjdp value_type, 96218822Sdim metadata_type, 97218822Sdim Allocator> 9833965Sjdp const_node_iterator; 99218822Sdim 100218822Sdim typedef 10133965Sjdp ov_tree_node_it_< 102218822Sdim value_type, 103218822Sdim metadata_type, 10433965Sjdp Allocator> 105218822Sdim node_iterator; 106218822Sdim 107218822Sdim typedef 10833965Sjdp Node_Update< 109218822Sdim const_node_iterator, 110218822Sdim node_iterator, 111218822Sdim Cmp_Fn, 112218822Sdim Allocator> 11333965Sjdp node_update; 11433965Sjdp 11533965Sjdp typedef 11633965Sjdp pb_ds::null_tree_node_update< 11733965Sjdp const_node_iterator, 11833965Sjdp node_iterator, 11933965Sjdp Cmp_Fn, 12033965Sjdp Allocator>* 12133965Sjdp null_node_update_pointer; 12233965Sjdp }; 12360484Sobrien 12460484Sobrien template<typename Key, 12533965Sjdp class Cmp_Fn, 12633965Sjdp template<typename Const_Node_Iterator, 12733965Sjdp class Node_Iterator, 12833965Sjdp class Cmp_Fn_, 12933965Sjdp class Allocator_> 13033965Sjdp class Node_Update, 13133965Sjdp class Allocator> 13233965Sjdp struct tree_traits< 13333965Sjdp Key, 13489857Sobrien null_mapped_type, 13533965Sjdp Cmp_Fn, 13633965Sjdp Node_Update, 13733965Sjdp ov_tree_tag, 13833965Sjdp Allocator> 13933965Sjdp { 14033965Sjdp private: 14133965Sjdp typedef 14233965Sjdp typename types_traits< 14333965Sjdp Key, 14433965Sjdp null_mapped_type, 14533965Sjdp Allocator, 14633965Sjdp false>::value_type 14733965Sjdp value_type; 14833965Sjdp 14933965Sjdp public: 15033965Sjdp typedef 15133965Sjdp typename tree_node_metadata_selector< 15233965Sjdp Key, 15333965Sjdp null_mapped_type, 15433965Sjdp Cmp_Fn, 15533965Sjdp Node_Update, 15633965Sjdp Allocator>::type 15733965Sjdp metadata_type; 15833965Sjdp 15933965Sjdp typedef 16033965Sjdp ov_tree_node_const_it_< 16133965Sjdp value_type, 162218822Sdim metadata_type, 163218822Sdim Allocator> 16433965Sjdp const_node_iterator; 165218822Sdim 166218822Sdim typedef const_node_iterator node_iterator; 167218822Sdim 168218822Sdim typedef 169218822Sdim Node_Update< 170218822Sdim const_node_iterator, 171218822Sdim const_node_iterator, 172218822Sdim Cmp_Fn, 173218822Sdim Allocator> 174218822Sdim node_update; 175218822Sdim 176218822Sdim typedef 177218822Sdim pb_ds::null_tree_node_update< 178218822Sdim const_node_iterator, 179218822Sdim node_iterator, 180218822Sdim Cmp_Fn, 181218822Sdim Allocator>* 182218822Sdim null_node_update_pointer; 183218822Sdim }; 18433965Sjdp 18533965Sjdp } // namespace detail 18633965Sjdp} // namespace pb_ds 18733965Sjdp 18833965Sjdp#endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP 18933965Sjdp 19033965Sjdp