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 splay_tree_.hpp 44169691Skan * Contains an implementation class for splay_tree_. 45169691Skan */ 46169691Skan/* 47169691Skan * This implementation uses an idea from the SGI STL (using a "header" node 48169691Skan * which is needed for efficient iteration). Following is the SGI STL 49169691Skan * copyright. 50169691Skan * 51169691Skan * Copyright (c) 1996,1997 52169691Skan * Silicon Graphics Computer Systems, Inc. 53169691Skan * 54169691Skan * Permission to use, copy, modify, distribute and sell this software 55169691Skan * and its documentation for any purpose is hereby granted without fee, 56169691Skan * provided that the above copyright notice appear in all copies and 57169691Skan * that both that copyright notice and this permission notice appear 58169691Skan * in supporting documentation. Silicon Graphics makes no 59169691Skan * representations about the suitability of this software for any 60169691Skan * purpose. It is provided "as is" without express or implied warranty. 61169691Skan * 62169691Skan * 63169691Skan * Copyright (c) 1994 64169691Skan * Hewlett-Packard Company 65169691Skan * 66169691Skan * Permission to use, copy, modify, distribute and sell this software 67169691Skan * and its documentation for any purpose is hereby granted without fee, 68169691Skan * provided that the above copyright notice appear in all copies and 69169691Skan * that both that copyright notice and this permission notice appear 70169691Skan * in supporting documentation. Hewlett-Packard Company makes no 71169691Skan * representations about the suitability of this software for any 72169691Skan * purpose. It is provided "as is" without express or implied warranty. 73169691Skan * 74169691Skan * 75169691Skan */ 76169691Skan 77169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 78169691Skan#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR 79169691Skan#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR 80169691Skan#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 81169691Skan#endif 82169691Skan#endif 83169691Skan 84169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 85169691Skan#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR 86169691Skan#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR 87169691Skan#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 88169691Skan#endif 89169691Skan#endif 90169691Skan 91169691Skan#include <utility> 92169691Skan#include <vector> 93169691Skan#include <assert.h> 94169691Skan#include <debug/debug.h> 95169691Skan 96169691Skannamespace pb_ds 97169691Skan{ 98169691Skan namespace detail 99169691Skan { 100169691Skan#define PB_DS_CLASS_T_DEC \ 101169691Skan template<typename Key, typename Mapped, typename Cmp_Fn, \ 102169691Skan typename Node_And_It_Traits, typename Allocator> 103169691Skan 104169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 105169691Skan#define PB_DS_CLASS_NAME splay_tree_data_ 106169691Skan#endif 107169691Skan 108169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 109169691Skan#define PB_DS_CLASS_NAME splay_tree_no_data_ 110169691Skan#endif 111169691Skan 112169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 113169691Skan#define PB_DS_BASE_CLASS_NAME bin_search_tree_data_ 114169691Skan#endif 115169691Skan 116169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 117169691Skan#define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_ 118169691Skan#endif 119169691Skan 120169691Skan#define PB_DS_CLASS_C_DEC \ 121169691Skan PB_DS_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator> 122169691Skan 123169691Skan#define PB_DS_BASE_C_DEC \ 124169691Skan PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator> 125169691Skan 126169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 127169691Skan#define PB_DS_V2F(X) (X).first 128169691Skan#define PB_DS_V2S(X) (X).second 129169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value) 130169691Skan#endif 131169691Skan 132169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 133169691Skan#define PB_DS_V2F(X) (X) 134169691Skan#define PB_DS_V2S(X) Mapped_Data() 135169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value.first) 136169691Skan#endif 137169691Skan 138169691Skan // $p14y 7r33 7481. 139169691Skan template<typename Key, typename Mapped, typename Cmp_Fn, 140169691Skan typename Node_And_It_Traits, typename Allocator> 141169691Skan class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC 142169691Skan { 143169691Skan private: 144169691Skan typedef PB_DS_BASE_C_DEC base_type; 145169691Skan typedef typename base_type::node_pointer node_pointer; 146169691Skan 147169691Skan public: 148169691Skan typedef Allocator allocator; 149169691Skan typedef typename Allocator::size_type size_type; 150169691Skan typedef typename Allocator::difference_type difference_type; 151169691Skan typedef Cmp_Fn cmp_fn; 152169691Skan typedef typename base_type::key_type key_type; 153169691Skan typedef typename base_type::key_pointer key_pointer; 154169691Skan typedef typename base_type::const_key_pointer const_key_pointer; 155169691Skan typedef typename base_type::key_reference key_reference; 156169691Skan typedef typename base_type::const_key_reference const_key_reference; 157169691Skan typedef typename base_type::mapped_type mapped_type; 158169691Skan typedef typename base_type::mapped_pointer mapped_pointer; 159169691Skan typedef typename base_type::const_mapped_pointer const_mapped_pointer; 160169691Skan typedef typename base_type::mapped_reference mapped_reference; 161169691Skan typedef typename base_type::const_mapped_reference const_mapped_reference; 162169691Skan typedef typename base_type::value_type value_type; 163169691Skan typedef typename base_type::pointer pointer; 164169691Skan typedef typename base_type::const_pointer const_pointer; 165169691Skan typedef typename base_type::reference reference; 166169691Skan typedef typename base_type::const_reference const_reference; 167169691Skan typedef typename base_type::point_iterator point_iterator; 168169691Skan typedef typename base_type::const_iterator const_point_iterator; 169169691Skan typedef typename base_type::iterator iterator; 170169691Skan typedef typename base_type::const_iterator const_iterator; 171169691Skan typedef typename base_type::reverse_iterator reverse_iterator; 172169691Skan typedef typename base_type::const_reverse_iterator const_reverse_iterator; 173169691Skan typedef typename base_type::node_update node_update; 174169691Skan 175169691Skan PB_DS_CLASS_NAME(); 176169691Skan 177169691Skan PB_DS_CLASS_NAME(const Cmp_Fn&); 178169691Skan 179169691Skan PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&); 180169691Skan 181169691Skan PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 182169691Skan 183169691Skan void 184169691Skan swap(PB_DS_CLASS_C_DEC&); 185169691Skan 186169691Skan template<typename It> 187169691Skan void 188169691Skan copy_from_range(It, It); 189169691Skan 190169691Skan void 191169691Skan initialize(); 192169691Skan 193169691Skan inline std::pair<point_iterator, bool> 194169691Skan insert(const_reference r_value); 195169691Skan 196169691Skan inline mapped_reference 197169691Skan operator[](const_key_reference r_key) 198169691Skan { 199169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 200169691Skan _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) 201169691Skan std::pair<point_iterator, bool> ins_pair = 202169691Skan insert_leaf_imp(value_type(r_key, mapped_type())); 203169691Skan 204169691Skan ins_pair.first.m_p_nd->m_special = false; 205169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_valid()); 206169691Skan splay(ins_pair.first.m_p_nd); 207169691Skan _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) 208169691Skan return ins_pair.first.m_p_nd->m_value.second; 209169691Skan#else 210169691Skan insert(r_key); 211169691Skan return base_type::s_null_mapped; 212169691Skan#endif 213169691Skan } 214169691Skan 215169691Skan inline point_iterator 216169691Skan find(const_key_reference); 217169691Skan 218169691Skan inline const_point_iterator 219169691Skan find(const_key_reference) const; 220169691Skan 221169691Skan inline bool 222169691Skan erase(const_key_reference); 223169691Skan 224169691Skan inline iterator 225169691Skan erase(iterator it); 226169691Skan 227169691Skan inline reverse_iterator 228169691Skan erase(reverse_iterator); 229169691Skan 230169691Skan template<typename Pred> 231169691Skan inline size_type 232169691Skan erase_if(Pred); 233169691Skan 234169691Skan void 235169691Skan join(PB_DS_CLASS_C_DEC&); 236169691Skan 237169691Skan void 238169691Skan split(const_key_reference, PB_DS_CLASS_C_DEC&); 239169691Skan 240169691Skan private: 241169691Skan inline std::pair<point_iterator, bool> 242169691Skan insert_leaf_imp(const_reference); 243169691Skan 244169691Skan inline node_pointer 245169691Skan find_imp(const_key_reference); 246169691Skan 247169691Skan inline const node_pointer 248169691Skan find_imp(const_key_reference) const; 249169691Skan 250169691Skan#ifdef _GLIBCXX_DEBUG 251169691Skan void 252169691Skan assert_valid() const; 253169691Skan 254169691Skan void 255169691Skan assert_special_imp(const node_pointer) const; 256169691Skan#endif 257169691Skan 258169691Skan void 259169691Skan splay(node_pointer); 260169691Skan 261169691Skan inline void 262169691Skan splay_zig_zag_left(node_pointer, node_pointer, node_pointer); 263169691Skan 264169691Skan inline void 265169691Skan splay_zig_zag_right(node_pointer, node_pointer, node_pointer); 266169691Skan 267169691Skan inline void 268169691Skan splay_zig_zig_left(node_pointer, node_pointer, node_pointer); 269169691Skan 270169691Skan inline void 271169691Skan splay_zig_zig_right(node_pointer, node_pointer, node_pointer); 272169691Skan 273169691Skan inline void 274169691Skan splay_zz_start(node_pointer, node_pointer, node_pointer); 275169691Skan 276169691Skan inline void 277169691Skan splay_zz_end(node_pointer, node_pointer, node_pointer); 278169691Skan 279169691Skan inline node_pointer 280169691Skan leftmost(node_pointer); 281169691Skan 282169691Skan void 283169691Skan erase_node(node_pointer); 284169691Skan }; 285169691Skan 286169691Skan#include <ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp> 287169691Skan#include <ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp> 288169691Skan#include <ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp> 289169691Skan#include <ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp> 290169691Skan#include <ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp> 291169691Skan#include <ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp> 292169691Skan#include <ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp> 293169691Skan 294169691Skan#undef PB_DS_CLASS_T_DEC 295169691Skan#undef PB_DS_CLASS_C_DEC 296169691Skan#undef PB_DS_CLASS_NAME 297169691Skan#undef PB_DS_BASE_CLASS_NAME 298169691Skan#undef PB_DS_BASE_C_DEC 299169691Skan#undef PB_DS_V2F 300169691Skan#undef PB_DS_EP2VP 301169691Skan#undef PB_DS_V2S 302169691Skan } // namespace detail 303169691Skan} // namespace pb_ds 304169691Skan 305