111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2005-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Permission to use, copy, modify, sell, and distribute this software 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// is hereby granted without fee, provided that the above copyright 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// notice appears in all copies, and that both that copyright notice 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// and this permission notice appear in supporting documentation. None 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the above authors, nor IBM Haifa Research Laboratories, make any 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// representation about the suitability of this software for any 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// purpose. It is provided "as is" without express or implied 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// warranty. 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @file splay_tree_/splay_tree_.hpp 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Contains an implementation class for splay trees. 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/* 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This implementation uses an idea from the SGI STL (using a @a header node 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * which is needed for efficient iteration). Following is the SGI STL 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * copyright. 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1996,1997 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Silicon Graphics Computer Systems, Inc. 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Permission to use, copy, modify, distribute and sell this software 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * and its documentation for any purpose is hereby granted without fee, 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * provided that the above copyright notice appear in all copies and 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * that both that copyright notice and this permission notice appear 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * in supporting documentation. Silicon Graphics makes no 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * representations about the suitability of this software for any 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * purpose. It is provided "as is" without express or implied warranty. 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1994 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Hewlett-Packard Company 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Permission to use, copy, modify, distribute and sell this software 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * and its documentation for any purpose is hereby granted without fee, 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * provided that the above copyright notice appear in all copies and 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * that both that copyright notice and this permission notice appear 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * in supporting documentation. Hewlett-Packard Company makes no 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * representations about the suitability of this software for any 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * purpose. It is provided "as is" without express or implied warranty. 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <utility> 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <vector> 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <assert.h> 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <debug/debug.h> 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_pbds 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert namespace detail 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# define PB_DS_S_TREE_NAME splay_tree_map 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# define PB_DS_S_TREE_BASE_NAME bin_search_tree_map 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_FALSE_INDICATOR 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# define PB_DS_S_TREE_NAME splay_tree_set 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# define PB_DS_S_TREE_BASE_NAME bin_search_tree_set 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_T_DEC \ 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Cmp_Fn, \ 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits, typename _Alloc> 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_C_DEC \ 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_S_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_S_TREE_BASE \ 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_S_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Splay tree. 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @ingroup branch-detail 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Cmp_Fn, 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits, typename _Alloc> 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class PB_DS_S_TREE_NAME : public PB_DS_S_TREE_BASE 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_S_TREE_BASE base_type; 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef base_type debug_base; 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::node_pointer node_pointer; 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef splay_tree_tag container_category; 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Alloc allocator_type; 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::size_type size_type; 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::difference_type difference_type; 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef Cmp_Fn cmp_fn; 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::key_type key_type; 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::key_pointer key_pointer; 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::key_const_pointer key_const_pointer; 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::key_reference key_reference; 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::key_const_reference key_const_reference; 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::mapped_type mapped_type; 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::mapped_pointer mapped_pointer; 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::mapped_const_pointer mapped_const_pointer; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::mapped_reference mapped_reference; 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::mapped_const_reference mapped_const_reference; 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::value_type value_type; 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::pointer pointer; 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::const_pointer const_pointer; 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::reference reference; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::const_reference const_reference; 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::point_iterator point_iterator; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::const_iterator point_const_iterator; 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::iterator iterator; 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::const_iterator const_iterator; 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::reverse_iterator reverse_iterator; 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::const_reverse_iterator const_reverse_iterator; 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename base_type::node_update node_update; 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_S_TREE_NAME(); 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_S_TREE_NAME(const Cmp_Fn&); 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_S_TREE_NAME(const Cmp_Fn&, const node_update&); 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_S_TREE_NAME(const PB_DS_CLASS_C_DEC&); 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert swap(PB_DS_CLASS_C_DEC&); 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename It> 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert copy_from_range(It, It); 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert initialize(); 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline std::pair<point_iterator, bool> 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(const_reference r_value); 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline mapped_reference 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator[](key_const_reference r_key) 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<point_iterator, bool> ins_pair = 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert_leaf_imp(value_type(r_key, mapped_type())); 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ins_pair.first.m_p_nd->m_special = false; 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(base_type::assert_valid(__FILE__, __LINE__)); 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay(ins_pair.first.m_p_nd); 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return ins_pair.first.m_p_nd->m_value.second; 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(r_key); 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return base_type::s_null_type; 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference); 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference) const; 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(key_const_reference); 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(iterator it); 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline reverse_iterator 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(reverse_iterator); 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Pred> 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase_if(Pred); 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert join(PB_DS_CLASS_C_DEC&); 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert split(key_const_reference, PB_DS_CLASS_C_DEC&); 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline std::pair<point_iterator, bool> 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert_leaf_imp(const_reference); 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_pointer 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find_imp(key_const_reference); 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const node_pointer 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find_imp(key_const_reference) const; 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_valid(const char* file, int line) const; 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_special_imp(const node_pointer, const char* file, int line) const; 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay(node_pointer); 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay_zig_zag_left(node_pointer, node_pointer, node_pointer); 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay_zig_zag_right(node_pointer, node_pointer, node_pointer); 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay_zig_zig_left(node_pointer, node_pointer, node_pointer); 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay_zig_zig_right(node_pointer, node_pointer, node_pointer); 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay_zz_start(node_pointer, node_pointer, node_pointer); 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert splay_zz_end(node_pointer, node_pointer, node_pointer); 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_pointer 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert leftmost(node_pointer); 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase_node(node_pointer); 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_ASSERT_BASE_NODE_CONSISTENT(_Node) \ 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node, \ 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __FILE__, __LINE__);) 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp> 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp> 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp> 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp> 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp> 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp> 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp> 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_ASSERT_BASE_NODE_CONSISTENT 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_T_DEC 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_C_DEC 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_S_TREE_NAME 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_S_TREE_BASE_NAME 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_S_TREE_BASE 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } // namespace detail 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __gnu_pbds 276