/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx

Bug Summary

File:	home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx
Warning:	line 1630, column 41 Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name navigatortree.cxx -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -mframe-pointer=all -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -isystem /usr/include/libxml2 -D BOOST_ERROR_CODE_HEADER_ONLY -D BOOST_SYSTEM_NO_DEPRECATED -D CPPU_ENV=gcc3 -D LINUX -D OSL_DEBUG_LEVEL=1 -D SAL_LOG_INFO -D SAL_LOG_WARN -D UNIX -D UNX -D X86_64 -D _PTHREADS -D _REENTRANT -D SVXCORE_DLLIMPLEMENTATION -D SYSTEM_LIBXML -D EXCEPTIONS_ON -D LIBO_INTERNAL_ONLY -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/epoxy/include -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/pdfium -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/pdfium/public -D COMPONENT_BUILD -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source/i18n -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source/common -I /home/maarten/src/libreoffice/core/external/boost/include -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/boost -I /home/maarten/src/libreoffice/core/svx/inc -I /home/maarten/src/libreoffice/core/svx/source/inc -I /home/maarten/src/libreoffice/core/include -I /usr/lib/jvm/java-11-openjdk-11.0.9.10-0.0.ea.fc33.x86_64/include -I /usr/lib/jvm/java-11-openjdk-11.0.9.10-0.0.ea.fc33.x86_64/include/linux -I /home/maarten/src/libreoffice/core/config_host -I /home/maarten/src/libreoffice/core/workdir/CustomTarget/officecfg/registry -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/udkapi/normal -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/offapi/normal -I /home/maarten/src/libreoffice/core/workdir/SdiTarget/svx/sdi -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/x86_64-redhat-linux -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O0 -Wno-missing-braces -std=c++17 -fdeprecated-macro -fdebug-compilation-dir /home/maarten/src/libreoffice/core -ferror-limit 19 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcxx-exceptions -fexceptions -debug-info-kind=constructor -analyzer-output=html -faddrsig -o /home/maarten/tmp/wis/scan-build-libreoffice/output/report/2020-10-07-141433-9725-1 -x c++ /home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx

/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx

→

1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*
* This file is part of the LibreOffice project.
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*
* This file incorporates work covered by the following license notice:
*
*   Licensed to the Apache Software Foundation (ASF) under one or more
*   contributor license agreements. See the NOTICE file distributed
*   with this work for additional information regarding copyright
*   ownership. The ASF licenses this file to you under the Apache
*   License, Version 2.0 (the "License"); you may not use this file
*   except in compliance with the License. You may obtain a copy of
*   the License at http://www.apache.org/licenses/LICENSE-2.0 .
*/

20#include <memory>
21#include <svx/dialmgr.hxx>
22#include <svx/fmshell.hxx>
23#include <svx/fmmodel.hxx>
24#include <svx/fmpage.hxx>
25#include <svx/svdpagv.hxx>
26#include <svx/svditer.hxx>

28#include <helpids.h>
29#include <fmexpl.hxx>
30#include <fmshimp.hxx>
31#include <fmservs.hxx>
32#include <fmundo.hxx>
33#include <fmpgeimp.hxx>
34#include <fmobj.hxx>
35#include <fmprop.hxx>
36#include <sal/log.hxx>
37#include <vcl/svapp.hxx>
38#include <sfx2/viewsh.hxx>
39#include <sfx2/dispatch.hxx>
40#include <sfx2/viewfrm.hxx>
41#include <comphelper/processfactory.hxx>
42#include <comphelper/property.hxx>
43#include <comphelper/types.hxx>
44#include <com/sun/star/form/FormComponentType.hpp>
45#include <com/sun/star/sdb/CommandType.hpp>
46#include <com/sun/star/beans/PropertyAttribute.hpp>
47#include <com/sun/star/script/XEventAttacherManager.hpp>
48#include <com/sun/star/datatransfer/clipboard/XClipboard.hpp>
49#include <com/sun/star/datatransfer/XTransferable.hpp>
50#include <com/sun/star/uno/XComponentContext.hpp>
51#include <svx/sdrpaintwindow.hxx>

53#include <svx/strings.hrc>
54#include <tools/diagnose_ex.h>
55#include <svx/svxids.hrc>
56#include <bitmaps.hlst>
57#include <vcl/commandevent.hxx>

59namespace svxform
60{
  #define EXPLORER_SYNC_DELAY200                 200
      // Time (in ms) until explorer synchronizes the view after select or deselect

  using namespace ::com::sun::star::uno;
  using namespace ::com::sun::star::lang;
  using namespace ::com::sun::star::beans;
  using namespace ::com::sun::star::form;
  using namespace ::com::sun::star::awt;
  using namespace ::com::sun::star::container;
  using namespace ::com::sun::star::script;
  using namespace ::com::sun::star::datatransfer;
  using namespace ::com::sun::star::datatransfer::clipboard;
  using namespace ::com::sun::star::sdb;


  // helper


  typedef ::std::map< Reference< XInterface >, SdrObject* > MapModelToShape;


  static void    collectShapeModelMapping( SdrPage const * _pPage, MapModelToShape& _rMapping )
  {
      OSL_ENSURE( _pPage, "collectShapeModelMapping: invalid arg!" )do { if (true && (!(_pPage))) { sal_detail_logFormat(
(SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "84" ": "), "%s", "collectShapeModelMapping: invalid arg!"
); } } while (false);

      _rMapping.clear();

      SdrObjListIter aIter( _pPage );
      while ( aIter.IsMore() )
      {
          SdrObject* pSdrObject = aIter.Next();
          FmFormObj* pFormObject = FmFormObj::GetFormObject( pSdrObject );
          if ( !pFormObject )
              continue;

          Reference< XInterface > xNormalizedModel( pFormObject->GetUnoControlModel(), UNO_QUERY );
              // note that this is normalized (i.e. queried for XInterface explicitly)

          ::std::pair< MapModelToShape::iterator, bool > aPos =
                _rMapping.emplace( xNormalizedModel, pSdrObject );
          DBG_ASSERT( aPos.second, "collectShapeModelMapping: model was already existent!" )do { if (true && (!(aPos.second))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "101" ": "), "%s", "collectShapeModelMapping: model was already existent!"
); } } while (false);
              // if this asserts, this would mean we have 2 shapes pointing to the same model
      }
  }

  NavigatorTreeDropTarget::NavigatorTreeDropTarget(NavigatorTree& rTreeView)
      : DropTargetHelper(rTreeView.get_widget().get_drop_target())
      , m_rTreeView(rTreeView)
  {
  }

  sal_Int8 NavigatorTreeDropTarget::AcceptDrop(const AcceptDropEvent& rEvt)
  {
      sal_Int8 nAccept = m_rTreeView.AcceptDrop(rEvt);

      if (nAccept != DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE)
      {
          // to enable the autoscroll when we're close to the edges
          weld::TreeView& rWidget = m_rTreeView.get_widget();
          rWidget.get_dest_row_at_pos(rEvt.maPosPixel, nullptr, true);
      }

      return nAccept;
  }

  sal_Int8 NavigatorTreeDropTarget::ExecuteDrop(const ExecuteDropEvent& rEvt)
  {
      return m_rTreeView.ExecuteDrop(rEvt);
  }

  NavigatorTree::NavigatorTree(std::unique_ptr<weld::TreeView> xTreeView)
      :m_xTreeView(std::move(xTreeView))
      ,m_aDropTargetHelper(*this)
      ,m_aControlExchange()
      ,nEditEvent(nullptr)
      ,m_sdiState(SDI_DIRTY)
      ,m_nSelectLock(0)
      ,m_nFormsSelected(0)
      ,m_nControlsSelected(0)
      ,m_nHiddenControls(0)
      ,m_bDragDataDirty(false)
      ,m_bPrevSelectionMixed(false)
      ,m_bRootSelected(false)
      ,m_bInitialUpdate(true)
      ,m_bKeyboardCut( false )
      ,m_bEditing( false )
  {
      m_xTreeView->set_help_id(HID_FORM_NAVIGATOR"SVX_HID_FORM_NAVIGATOR");

      m_xTreeView->set_selection_mode(SelectionMode::Multiple);

      m_pNavModel.reset(new NavigatorTreeModel());
      Clear();

      StartListening( *m_pNavModel );

      m_aSynchronizeTimer.SetInvokeHandler(LINK(this, NavigatorTree, OnSynchronizeTimer)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubOnSynchronizeTimer));
      m_xTreeView->connect_changed(LINK(this, NavigatorTree, OnEntrySelDesel)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubOnEntrySelDesel));
      m_xTreeView->connect_key_press(LINK(this, NavigatorTree, KeyInputHdl)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubKeyInputHdl));
      m_xTreeView->connect_popup_menu(LINK(this, NavigatorTree, PopupMenuHdl)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubPopupMenuHdl));
      m_xTreeView->connect_editing(LINK(this, NavigatorTree, EditingEntryHdl)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubEditingEntryHdl),
                                   LINK(this, NavigatorTree, EditedEntryHdl)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubEditedEntryHdl));
      m_xTreeView->connect_drag_begin(LINK(this, NavigatorTree, DragBeginHdl)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubDragBeginHdl));
  }

  NavigatorTree::~NavigatorTree()
  {
      if( nEditEvent )
          Application::RemoveUserEvent( nEditEvent );

      if (m_aSynchronizeTimer.IsActive())
          m_aSynchronizeTimer.Stop();

      DBG_ASSERT(GetNavModel() != nullptr, "NavigatorTree::~NavigatorTree : unexpected : no ExplorerModel")do { if (true && (!(GetNavModel() != nullptr))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "174" ": "), "%s", "NavigatorTree::~NavigatorTree : unexpected : no ExplorerModel"
); } } while (false);
      EndListening( *m_pNavModel );
      Clear();
      m_pNavModel.reset();
  }

  void NavigatorTree::Clear()
  {
      m_pNavModel->Clear();
  }

  void NavigatorTree::UpdateContent( FmFormShell* pFormShell )
  {
      if (m_bInitialUpdate)
      {
          GrabFocus();
          m_bInitialUpdate = false;
      }

      FmFormShell* pOldShell = GetNavModel()->GetFormShell();
      FmFormPage* pOldPage = GetNavModel()->GetFormPage();
      FmFormPage* pNewPage = pFormShell ? pFormShell->GetCurPage() : nullptr;

      if ((pOldShell != pFormShell) || (pOldPage != pNewPage))
      {
          // new shell during editing
          if (IsEditingActive())
          {
              m_xTreeView->end_editing();
              m_bEditing = false;
          }

          m_bDragDataDirty = true;    // as a precaution, although I don't drag
      }
      GetNavModel()->UpdateContent( pFormShell );

      // if there is a form, expand root
      if (m_xRootEntry && !m_xTreeView->get_row_expanded(*m_xRootEntry))
          m_xTreeView->expand_row(*m_xRootEntry);
      // if there is EXACTLY ONE form, expand it too
      if (m_xRootEntry)
      {
          std::unique_ptr<weld::TreeIter> xFirst(m_xTreeView->make_iterator(m_xRootEntry.get()));
          bool bFirst = m_xTreeView->iter_children(*xFirst);
          if (bFirst)
          {
              std::unique_ptr<weld::TreeIter> xSibling(m_xTreeView->make_iterator(xFirst.get()));
              if (!m_xTreeView->iter_next_sibling(*xSibling))
                  m_xTreeView->expand_row(*xFirst);
          }
      }
  }

  bool NavigatorTree::implAllowExchange( sal_Int8 _nAction, bool* _pHasNonHidden )
  {
      bool bCurEntry = m_xTreeView->get_cursor(nullptr);
      if (!bCurEntry)
          return false;

      // Information for AcceptDrop and Execute Drop
      CollectSelectionData(SDI_ALL);
      if (m_arrCurrentSelection.empty())
          // nothing to do
          return false;

      // check whether there are only hidden controls
      // I may add a format to pCtrlExch
      bool bHasNonHidden = std::any_of(m_arrCurrentSelection.begin(), m_arrCurrentSelection.end(),
          [this](const auto& rEntry) {
              FmEntryData* pCurrent = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*rEntry).toInt64());
              return !IsHiddenControl( pCurrent );
          });

      if ( bHasNonHidden && ( 0 == ( _nAction & DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE ) ) )
          // non-hidden controls need to be moved
          return false;

      if ( _pHasNonHidden )
          *_pHasNonHidden = bHasNonHidden;

      return true;
  }

  bool NavigatorTree::implPrepareExchange( sal_Int8 _nAction )
  {
      bool bHasNonHidden = false;
      if ( !implAllowExchange( _nAction, &bHasNonHidden ) )
          return false;

      m_aControlExchange.prepareDrag();
      m_aControlExchange->setFocusEntry(m_xTreeView->get_cursor(nullptr));

      for (const auto& rpEntry : m_arrCurrentSelection)
          m_aControlExchange->addSelectedEntry(m_xTreeView->make_iterator(rpEntry.get()));

      m_aControlExchange->setFormsRoot( GetNavModel()->GetFormPage()->GetForms() );
      m_aControlExchange->buildPathFormat(m_xTreeView.get(), m_xRootEntry.get());

      if (!bHasNonHidden)
      {
          // create a sequence
          Sequence< Reference< XInterface > > seqIFaces(m_arrCurrentSelection.size());
          Reference< XInterface >* pArray = seqIFaces.getArray();
          for (const auto& rpEntry : m_arrCurrentSelection)
          {
              *pArray = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*rpEntry).toInt64())->GetElement();
              ++pArray;
          }
          // and the new format
          m_aControlExchange->addHiddenControlsFormat(seqIFaces);
      }

      m_bDragDataDirty = false;
      return true;
  }

  IMPL_LINK(NavigatorTree, DragBeginHdl, bool&, rUnsetDragIcon, bool)bool NavigatorTree::LinkStubDragBeginHdl(void * instance, bool
& data) { return static_cast<NavigatorTree *>(instance
)->DragBeginHdl(data); } bool NavigatorTree::DragBeginHdl(
bool& rUnsetDragIcon)
  {
      rUnsetDragIcon = false;

      bool bSuccess = implPrepareExchange(DND_ACTION_COPYMOVEcss::datatransfer::dnd::DNDConstants::ACTION_COPY_OR_MOVE);
      if (bSuccess)
      {
          OControlExchange& rExchange = *m_aControlExchange;
          rtl::Reference<TransferDataContainer> xHelper(&rExchange);
          m_xTreeView->enable_drag_source(xHelper, DND_ACTION_COPYMOVEcss::datatransfer::dnd::DNDConstants::ACTION_COPY_OR_MOVE);
          rExchange.setDragging(true);
      }
      return !bSuccess;
  }

  IMPL_LINK(NavigatorTree, PopupMenuHdl, const CommandEvent&, rEvt, bool)bool NavigatorTree::LinkStubPopupMenuHdl(void * instance, const
 CommandEvent& data) { return static_cast<NavigatorTree
 *>(instance)->PopupMenuHdl(data); } bool NavigatorTree
::PopupMenuHdl(const CommandEvent& rEvt)
  {
      bool bHandled = false;
      switch( rEvt.GetCommand() )
      {
          case CommandEventId::ContextMenu:
          {
              // Position of click
              ::Point ptWhere;
              if (rEvt.IsMouseEvent())
              {
                  ptWhere = rEvt.GetMousePosPixel();
                  std::unique_ptr<weld::TreeIter> xClickedOn(m_xTreeView->make_iterator());
                  if (!m_xTreeView->get_dest_row_at_pos(ptWhere, xClickedOn.get(), false))
                      break;
                  if (!m_xTreeView->is_selected(*xClickedOn))
                  {
                      m_xTreeView->unselect_all();
                      m_xTreeView->select(*xClickedOn);
                      m_xTreeView->set_cursor(*xClickedOn);
                  }
              }
              else
              {
                  if (m_arrCurrentSelection.empty()) // only happens with context menu via keyboard
                      break;

                  std::unique_ptr<weld::TreeIter> xCurrent(m_xTreeView->make_iterator());
                  if (!m_xTreeView->get_cursor(xCurrent.get()))
                      break;
                  ptWhere = m_xTreeView->get_row_area(*xCurrent).Center();
              }

              // update my selection data
              CollectSelectionData(SDI_ALL);

              // if there is at least one no-root-entry and the root selected, I deselect root
              if ( (m_arrCurrentSelection.size() > 1) && m_bRootSelected )
              {
                  const std::unique_ptr<weld::TreeIter>& rIter = *m_arrCurrentSelection.begin();
                  m_xTreeView->set_cursor(*rIter);
                  m_xTreeView->unselect(*m_xRootEntry);
              }
              bool bSingleSelection = (m_arrCurrentSelection.size() == 1);


              DBG_ASSERT( (!m_arrCurrentSelection.empty()) || m_bRootSelected, "no entries selected" )do { if (true && (!((!m_arrCurrentSelection.empty()) ||
 m_bRootSelected))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN
), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "351" ": "), "%s", "no entries selected"); } } while (false
);
                  // shouldn't happen, because I would have selected one during call to IsSelected,
                  // if there was none before


              // create menu
              FmFormShell* pFormShell = GetNavModel()->GetFormShell();
              FmFormModel* pFormModel = pFormShell ? pFormShell->GetFormModel() : nullptr;
              if( pFormShell && pFormModel )
              {
                  std::unique_ptr<weld::Builder> xBuilder(Application::CreateBuilder(m_xTreeView.get(), "svx/ui/formnavimenu.ui"));
                  std::unique_ptr<weld::Menu> xContextMenu(xBuilder->weld_menu("menu"));
                  std::unique_ptr<weld::Menu> xSubMenuNew(xBuilder->weld_menu("submenu"));

                  // menu 'New' only exists, if only the root or only one form is selected
                  bool bShowNew = bSingleSelection && (m_nFormsSelected || m_bRootSelected);
                  if (!bShowNew)
                      xContextMenu->remove("new");

                  // 'New'\'Form' under the same terms
                  bool bShowForm = bSingleSelection && (m_nFormsSelected || m_bRootSelected);
                  if (bShowForm)
                      xSubMenuNew->append("form", SvxResId(RID_STR_FORMreinterpret_cast<char const *>("RID_STR_FORM" "\004" u8"Form"
)), RID_SVXBMP_FORM"res/sx10593.png");

                  // 'New'\'hidden...', if exactly one form is selected
                  bool bShowHidden = bSingleSelection && m_nFormsSelected;
                  if (bShowHidden)
                      xSubMenuNew->append("hidden", SvxResId(RID_STR_HIDDENreinterpret_cast<char const *>("RID_STR_HIDDEN" "\004" u8"Hidden"
)), RID_SVXBMP_HIDDEN"res/sx18022.png");

                  // 'Delete': everything which is not root can be removed
                  if (m_bRootSelected)
                      xContextMenu->remove("delete");

                  // 'Cut', 'Copy' and 'Paste'
                  bool bShowCut = !m_bRootSelected && implAllowExchange(DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE);
                  if (!bShowCut)
                      xContextMenu->remove("cut");
                  bool bShowCopy = !m_bRootSelected && implAllowExchange(DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY);
                  if (!bShowCopy)
                      xContextMenu->remove("copy");
                  if (!implAcceptPaste())
                      xContextMenu->remove("paste");

                  // TabDialog, if exactly one form
                  bool bShowTabOrder = bSingleSelection && m_nFormsSelected;
                  if (!bShowTabOrder)
                      xContextMenu->remove("taborder");

                  bool bShowProps = true;
                  // in XML forms, we don't allow for the properties of a form
                  // #i36484#
                  if (pFormShell->GetImpl()->isEnhancedForm_Lock() && !m_nControlsSelected)
                      bShowProps = false;
                  // if the property browser is already open, we don't allow for the properties, too
                  if (pFormShell->GetImpl()->IsPropBrwOpen_Lock())
                      bShowProps = false;

                  // and finally, if there's a mixed selection of forms and controls, disable the entry, too
                  if (bShowProps && !pFormShell->GetImpl()->IsPropBrwOpen_Lock())
                      bShowProps =
                          (m_nControlsSelected && !m_nFormsSelected) || (!m_nControlsSelected && m_nFormsSelected);

                  if (!bShowProps)
                      xContextMenu->remove("props");

                  // rename, if one element and no root
                  bool bShowRename = bSingleSelection && !m_bRootSelected;
                  if (!bShowRename)
                      xContextMenu->remove("rename");

                  if (!m_bRootSelected)
                  {
                      // Readonly-entry is only for root
                      xContextMenu->remove("designmode");
                      // the same for automatic control focus
                      xContextMenu->remove("controlfocus");
                  }

                  std::unique_ptr<weld::Menu> xConversionMenu(xBuilder->weld_menu("changemenu"));
                  // ConvertTo-Slots are enabled, if one control is selected
                  // the corresponding slot is disabled
                  if (!m_bRootSelected && !m_nFormsSelected && (m_nControlsSelected == 1))
                  {
                      FmXFormShell::GetConversionMenu_Lock(*xConversionMenu);
435#if OSL_DEBUG_LEVEL1 > 0
                      const std::unique_ptr<weld::TreeIter>& rIter = *m_arrCurrentSelection.begin();
                      FmControlData* pCurrent = reinterpret_cast<FmControlData*>(m_xTreeView->get_id(*rIter).toInt64());
                      OSL_ENSURE( pFormShell->GetImpl()->isSolelySelected_Lock( pCurrent->GetFormComponent() ),do { if (true && (!(pFormShell->GetImpl()->isSolelySelected_Lock
( pCurrent->GetFormComponent() )))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "439" ": "), "%s", "NavigatorTree::Command: inconsistency between the navigator selection, and the selection as the shell knows it!"
); } } while (false)
                          "NavigatorTree::Command: inconsistency between the navigator selection, and the selection as the shell knows it!" )do { if (true && (!(pFormShell->GetImpl()->isSolelySelected_Lock
( pCurrent->GetFormComponent() )))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "439" ": "), "%s", "NavigatorTree::Command: inconsistency between the navigator selection, and the selection as the shell knows it!"
); } } while (false);
440#endif

                      pFormShell->GetImpl()->checkControlConversionSlotsForCurrentSelection_Lock(*xConversionMenu);
                  }
                  else
                      xContextMenu->remove("change");

                  if (m_bRootSelected)
                  {
                      // set OpenReadOnly
                      xContextMenu->set_active("designmode", pFormModel->GetOpenInDesignMode());
                      xContextMenu->set_active("controlfocus", pFormModel->GetAutoControlFocus());
                  }

                  OString sIdent = xContextMenu->popup_at_rect(m_xTreeView.get(), tools::Rectangle(ptWhere, ::Size(1, 1)));
                  if (sIdent == "form")
                  {
                      OUString aStr(SvxResId(RID_STR_FORMreinterpret_cast<char const *>("RID_STR_FORM" "\004" u8"Form"
)));
                      OUString aUndoStr = SvxResId(RID_STR_UNDO_CONTAINER_INSERTreinterpret_cast<char const *>("RID_STR_UNDO_CONTAINER_INSERT"
 "\004" u8"Insert in container")).replaceAll("#", aStr);

                      pFormModel->BegUndo(aUndoStr);
                      // slot was only available, if there is only one selected entry,
                      // which is a root or a form
                      const std::unique_ptr<weld::TreeIter>& rIter = *m_arrCurrentSelection.begin();
                      NewForm(*rIter);
                      pFormModel->EndUndo();
                  }
                  else if (sIdent == "hidden")
                  {
                      OUString aStr(SvxResId(RID_STR_CONTROLreinterpret_cast<char const *>("RID_STR_CONTROL" "\004"
 u8"Control")));
                      OUString aUndoStr = SvxResId(RID_STR_UNDO_CONTAINER_INSERTreinterpret_cast<char const *>("RID_STR_UNDO_CONTAINER_INSERT"
 "\004" u8"Insert in container")).replaceAll("#", aStr);

                      pFormModel->BegUndo(aUndoStr);
                      // slot was valid for (exactly) one selected form
                      const std::unique_ptr<weld::TreeIter>& rIter = *m_arrCurrentSelection.begin();
                      NewControl(FM_COMPONENT_HIDDEN"stardiv.one.form.component.Hidden", *rIter, true);
                      pFormModel->EndUndo();
                  }
                  else if (sIdent == "cut")
                      doCut();
                  else if (sIdent == "copy")
                      doCopy();
                  else if (sIdent == "paste")
                      doPaste();
                  else if (sIdent == "delete")
                      DeleteSelection();
                  else if (sIdent == "taborder")
                  {
                      // this slot was effective for exactly one selected form
                      const std::unique_ptr<weld::TreeIter>& rSelectedForm = *m_arrCurrentSelection.begin();
                      DBG_ASSERT( IsFormEntry(*rSelectedForm), "NavigatorTree::Command: This entry must be a FormEntry." )do { if (true && (!(IsFormEntry(*rSelectedForm)))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "490" ": "), "%s", "NavigatorTree::Command: This entry must be a FormEntry."
); } } while (false);

                      FmFormData* pFormData = reinterpret_cast<FmFormData*>(m_xTreeView->get_id(*rSelectedForm).toInt64());
                      const Reference< XForm >&  xForm(  pFormData->GetFormIface());

                      Reference< XTabControllerModel >  xTabController(xForm, UNO_QUERY);
                      if( !xTabController.is() )
                          break;
                      GetNavModel()->GetFormShell()->GetImpl()->ExecuteTabOrderDialog_Lock(xTabController);
                  }
                  else if (sIdent == "props")
                      ShowSelectionProperties(true);
                  else if (sIdent == "rename")
                  {
                      // only allowed for one no-root-entry
                      const std::unique_ptr<weld::TreeIter>& rIter = *m_arrCurrentSelection.begin();
                      m_xTreeView->start_editing(*rIter);
                      m_bEditing = true;
                  }
                  else if (sIdent == "designmode")
                  {
                      pFormModel->SetOpenInDesignMode( !pFormModel->GetOpenInDesignMode() );
                      pFormShell->GetViewShell()->GetViewFrame()->GetBindings().Invalidate(SID_FM_OPEN_READONLY( 10000 + 709 ));
                  }
                  else if (sIdent == "controlfocus")
                  {
                      pFormModel->SetAutoControlFocus( !pFormModel->GetAutoControlFocus() );
                      pFormShell->GetViewShell()->GetViewFrame()->GetBindings().Invalidate(SID_FM_AUTOCONTROLFOCUS( 10000 + 763 ));
                  }
                  else if (FmXFormShell::isControlConversionSlot(sIdent))
                  {
                      const std::unique_ptr<weld::TreeIter>& rIter = *m_arrCurrentSelection.begin();
                      FmControlData* pCurrent = reinterpret_cast<FmControlData*>(m_xTreeView->get_id(*rIter).toInt64());
                      if (pFormShell->GetImpl()->executeControlConversionSlot_Lock(pCurrent->GetFormComponent(), sIdent))
                          ShowSelectionProperties();
                  }
              }
              bHandled = true;
          }
          break;
          default: break;
      }

      return bHandled;
  }

  std::unique_ptr<weld::TreeIter> NavigatorTree::FindEntry(FmEntryData* pEntryData)
  {
      std::unique_ptr<weld::TreeIter> xRet;
      if(!pEntryData)
          return xRet;

      m_xTreeView->all_foreach([this, pEntryData, &xRet](weld::TreeIter& rEntry){
          FmEntryData* pCurEntryData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(rEntry).toInt64());
          if (pCurEntryData && pCurEntryData->IsEqualWithoutChildren(pEntryData))
          {
              xRet = m_xTreeView->make_iterator(&rEntry);
              return true;
          }
          return false;
      });

      return xRet;
  }

  void NavigatorTree::Notify( SfxBroadcaster& /*rBC*/, const SfxHint& rHint )
  {
      if( dynamic_cast<const FmNavRemovedHint*>(&rHint) )
      {
          const FmNavRemovedHint* pRemovedHint = static_cast<const FmNavRemovedHint*>(&rHint);
          FmEntryData* pEntryData = pRemovedHint->GetEntryData();
          Remove( pEntryData );
      }

      else if( dynamic_cast<const FmNavInsertedHint*>(&rHint) )
      {
          const FmNavInsertedHint* pInsertedHint = static_cast<const FmNavInsertedHint*>(&rHint);
          FmEntryData* pEntryData = pInsertedHint->GetEntryData();
          sal_uInt32 nRelPos = pInsertedHint->GetRelPos();
          Insert( pEntryData, nRelPos );
      }

      else if( dynamic_cast<const FmNavModelReplacedHint*>(&rHint) )
      {
          FmEntryData* pData = static_cast<const FmNavModelReplacedHint*>(&rHint)->GetEntryData();
          std::unique_ptr<weld::TreeIter> xEntry = FindEntry(pData);
          if (xEntry)
          {
              // reset image
              m_xTreeView->set_image(*xEntry, pData->GetNormalImage());
          }
      }

      else if( dynamic_cast<const FmNavNameChangedHint*>(&rHint) )
      {
          const FmNavNameChangedHint* pNameChangedHint = static_cast<const FmNavNameChangedHint*>(&rHint);
          std::unique_ptr<weld::TreeIter> xEntry = FindEntry(pNameChangedHint->GetEntryData());
          m_xTreeView->set_text(*xEntry, pNameChangedHint->GetNewName());
      }

      else if( dynamic_cast<const FmNavClearedHint*>(&rHint) )
      {
          m_aCutEntries.clear();
          if (m_aControlExchange.isDataExchangeActive())
              m_aControlExchange.clear();
          m_xTreeView->clear();

          // default-entry "Forms"
          OUString sText(SvxResId(RID_STR_FORMSreinterpret_cast<char const *>("RID_STR_FORMS" "\004" u8"Forms"
)));
          m_xRootEntry = m_xTreeView->make_iterator();
          m_xTreeView->insert(nullptr, -1, &sText, nullptr, nullptr, nullptr,
                              false, m_xRootEntry.get());
          m_xTreeView->set_image(*m_xRootEntry, RID_SVXBMP_FORMS"res/sx18013.png");
          m_xTreeView->set_sensitive(*m_xRootEntry, true);
      }
      else if (dynamic_cast<const FmNavRequestSelectHint*>(&rHint))
      {
          FmNavRequestSelectHint* pershHint = const_cast<FmNavRequestSelectHint*>(static_cast<const FmNavRequestSelectHint*>(&rHint));
          FmEntryDataArray& arredToSelect = pershHint->GetItems();
          SynchronizeSelection(arredToSelect);

          if (pershHint->IsMixedSelection())
              // in this case I deselect all, although the view had a mixed selection
              // during next selection, I must adapt the navigator to the view
              m_bPrevSelectionMixed = true;
      }
  }

  std::unique_ptr<weld::TreeIter> NavigatorTree::Insert(FmEntryData* pEntryData, int nRelPos)
  {
      // insert current entry
      std::unique_ptr<weld::TreeIter> xParentEntry = FindEntry( pEntryData->GetParent() );
      std::unique_ptr<weld::TreeIter> xNewEntry(m_xTreeView->make_iterator());
      OUString sId(OUString::number(reinterpret_cast<sal_Int64>(pEntryData)));

      if(!xParentEntry)
      {
          m_xTreeView->insert(m_xRootEntry.get(), nRelPos, &pEntryData->GetText(), &sId,
                              nullptr, nullptr, false, xNewEntry.get());
      }
      else
      {
          m_xTreeView->insert(xParentEntry.get(), nRelPos, &pEntryData->GetText(), &sId,
                              nullptr, nullptr, false, xNewEntry.get());
      }

      m_xTreeView->set_image(*xNewEntry, pEntryData->GetNormalImage());
      m_xTreeView->set_sensitive(*xNewEntry, true);

      // If root-entry, expand root
      if (!xParentEntry)
          m_xTreeView->expand_row(*m_xRootEntry);

      // insert children
      FmEntryDataList* pChildList = pEntryData->GetChildList();
      size_t nChildCount = pChildList->size();
      for( size_t i = 0; i < nChildCount; i++ )
      {
          FmEntryData* pChildData = pChildList->at( i );
          Insert(pChildData, -1);
      }

      return xNewEntry;
  }

  void NavigatorTree::Remove( FmEntryData* pEntryData )
  {
      if( !pEntryData )
          return;

      // entry for the data
      std::unique_ptr<weld::TreeIter> xEntry = FindEntry(pEntryData);
      if (!xEntry)
          return;

      // delete entry from TreeListBox
      // I'm not allowed, to treat the selection, which I trigger:
      // select changes the MarkList of the view, if somebody else does this at the same time
      // and removes a selection, we get a problem
      // e.g. Group controls with open navigator
      LockSelectionHandling();

      // little problem: I remember the selected data, but if somebody deletes one of these entries,
      // I get inconsistent... this would be bad
      m_xTreeView->unselect(*xEntry);

      // selection can be modified during deletion,
      // but because I disabled SelectionHandling, I have to do it later
      auto nExpectedSelectionCount = m_xTreeView->count_selected_rows();

      ModelHasRemoved(xEntry.get());
      m_xTreeView->remove(*xEntry);

      if (nExpectedSelectionCount != m_xTreeView->count_selected_rows())
          SynchronizeSelection();

      // by default I treat the selection of course
      UnlockSelectionHandling();
  }

  bool NavigatorTree::IsFormEntry(const weld::TreeIter& rEntry)
  {
      FmEntryData* pEntryData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(rEntry).toInt64());
      return !pEntryData || dynamic_cast<const FmFormData*>( pEntryData) !=  nullptr;
  }

  bool NavigatorTree::IsFormComponentEntry(const weld::TreeIter& rEntry)
  {
      FmEntryData* pEntryData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(rEntry).toInt64());
      return dynamic_cast<const FmControlData*>( pEntryData) != nullptr;
  }

  bool NavigatorTree::implAcceptPaste( )
  {
      auto nSelectedEntries = m_xTreeView->count_selected_rows();
      if (nSelectedEntries != 1)
          // no selected entry, or at least two selected entries
          return false;

      // get the clipboard
      TransferableDataHelper aClipboardContent(TransferableDataHelper::CreateFromClipboard(GetSystemClipboard()));

      sal_Int8 nAction = m_aControlExchange.isClipboardOwner() && doingKeyboardCut( ) ? DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE : DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY;
      std::unique_ptr<weld::TreeIter> xSelected(m_xTreeView->make_iterator());
      if (!m_xTreeView->get_selected(xSelected.get()))
          xSelected.reset();
      return nAction == implAcceptDataTransfer(aClipboardContent.GetDataFlavorExVector(), nAction, xSelected.get(), false);
  }

  sal_Int8 NavigatorTree::implAcceptDataTransfer( const DataFlavorExVector& _rFlavors, sal_Int8 _nAction, const weld::TreeIter* _pTargetEntry, bool _bDnD )
  {
      // no target -> no drop
      if (!_pTargetEntry)
          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

      // format check
      bool bHasDefControlFormat = OControlExchange::hasFieldExchangeFormat( _rFlavors );
      bool bHasControlPathFormat = OControlExchange::hasControlPathFormat( _rFlavors );
      bool bHasHiddenControlsFormat = OControlExchange::hasHiddenControlModelsFormat( _rFlavors );
      if (!bHasDefControlFormat && !bHasControlPathFormat && !bHasHiddenControlsFormat)
          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

      bool bSelfSource = _bDnD ? m_aControlExchange.isDragSource() : m_aControlExchange.isClipboardOwner();

      if ( bHasHiddenControlsFormat )
      {   // bHasHiddenControlsFormat means that only hidden controls are part of the data

          // hidden controls can be copied to a form only
          if (m_xTreeView->iter_compare(*_pTargetEntry, *m_xRootEntry) == 0 || !IsFormEntry(*_pTargetEntry))
              return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

          return bSelfSource ? ( DND_ACTION_COPYMOVEcss::datatransfer::dnd::DNDConstants::ACTION_COPY_OR_MOVE & _nAction ) : DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY;
      }

      if  ( !bSelfSource )
      {
          // DnD or CnP crossing navigator boundaries
          // The main problem here is that the current API does not allow us to sneak into the content which
          // is to be inserted. So we have to allow it for the moment, but maybe reject later on (in the real drop).

          // TODO: this smart behaviour later on ... at the moment, we disallow data transfer crossing navigator
          // boundaries.

          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;
      }

      DBG_ASSERT( _bDnD ? m_aControlExchange.isDragSource() : m_aControlExchange.isClipboardOwner(),do { if (true && (!(_bDnD ? m_aControlExchange.isDragSource
() : m_aControlExchange.isClipboardOwner()))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "757" ": "), "%s", "NavigatorTree::implAcceptDataTransfer: here only with source=dest!"
); } } while (false)
          "NavigatorTree::implAcceptDataTransfer: here only with source=dest!" )do { if (true && (!(_bDnD ? m_aControlExchange.isDragSource
() : m_aControlExchange.isClipboardOwner()))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "757" ": "), "%s", "NavigatorTree::implAcceptDataTransfer: here only with source=dest!"
); } } while (false);
          // somebody changed the logic of this method ...

      // from here on, I can work with m_aControlExchange instead of _rData!

      bool bForeignCollection = m_aControlExchange->getFormsRoot().get() != GetNavModel()->GetFormPage()->GetForms().get();
      if ( bForeignCollection )
      {
          // crossing shell/page boundaries, we can exchange hidden controls only
          // But if we survived the checks above, we do not have hidden controls.
          // -> no data transfer
          DBG_ASSERT( !bHasHiddenControlsFormat, "NavigatorTree::implAcceptDataTransfer: still hidden controls format!" )do { if (true && (!(!bHasHiddenControlsFormat))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "768" ": "), "%s", "NavigatorTree::implAcceptDataTransfer: still hidden controls format!"
); } } while (false);
              // somebody changed the logic of this method ...

          return DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY;
      }

      if (DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE != _nAction) // 'normal' controls within a shell are moved only (never copied)
          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

      if ( m_bDragDataDirty || !bHasDefControlFormat )
      {
          if (!bHasControlPathFormat)
              // I am in the shell/page, which has the controls, but I have no format,
              // which survived the shell change (SVX_FM_CONTROLS_AS_PATH)
              return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

          // I must recreate the list of the ExchangeObjects, because the shell was changed during dragging
          // (there are SvLBoxEntries in it, and we lost them during change)
          m_aControlExchange->buildListFromPath(m_xTreeView.get(), m_xRootEntry.get());
          m_bDragDataDirty = false;
      }

      // List of dropped entries from DragServer
      const ListBoxEntrySet& rDropped = m_aControlExchange->selected();
      DBG_ASSERT(!rDropped.empty(), "NavigatorTree::implAcceptDataTransfer: no entries !")do { if (true && (!(!rDropped.empty()))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "792" ": "), "%s", "NavigatorTree::implAcceptDataTransfer: no entries !"
); } } while (false);

      bool bDropTargetIsComponent = IsFormComponentEntry( *_pTargetEntry );

      // conditions to disallow the drop
      // 0) the root entry is part of the list (can't DnD the root!)
      // 1) one of the dragged entries is to be dropped onto its own parent
      // 2) -               "       - is to be dropped onto itself
      // 3) -               "       - is a Form and to be dropped onto one of its descendants
      // 4) one of the entries is a control and to be dropped onto the root
      // 5) a control or form will be dropped onto a control which is _not_ a sibling (dropping onto a sibling
      //      means moving the control)

      // collect the ancestors of the drop target (speeds up 3)
      SvLBoxEntrySortedArray arrDropAncestors;
      std::unique_ptr<weld::TreeIter> xLoop(m_xTreeView->make_iterator(_pTargetEntry));
      do
      {
          arrDropAncestors.emplace(m_xTreeView->make_iterator(xLoop.get()));
      }
      while (m_xTreeView->iter_parent(*xLoop));

      for (const auto& rCurrent : rDropped)
      {
          // test for 0)
          if (m_xTreeView->iter_compare(*rCurrent, *m_xRootEntry) == 0)
              return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

          std::unique_ptr<weld::TreeIter> xCurrentParent(m_xTreeView->make_iterator(rCurrent.get()));
          m_xTreeView->iter_parent(*xCurrentParent);

          // test for 1)
          if (m_xTreeView->iter_compare(*_pTargetEntry, *xCurrentParent) == 0)
              return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

          // test for 2)
          if (m_xTreeView->iter_compare(*rCurrent, *_pTargetEntry) == 0)
              return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

          // test for 5)
          if (bDropTargetIsComponent)
              return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

          // test for 3)
          if (IsFormEntry(*rCurrent))
          {
              auto aIter = std::find_if(arrDropAncestors.begin(), arrDropAncestors.end(),
                                        [this, &rCurrent](const auto& rElem) {
                                          return m_xTreeView->iter_compare(*rElem, *rCurrent) == 0;
                                        });

              if ( aIter != arrDropAncestors.end() )
                  return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;
          }
          else if (IsFormComponentEntry(*rCurrent))
          {
              // test for 4)
              if (m_xTreeView->iter_compare(*_pTargetEntry, *m_xRootEntry) == 0)
                  return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;
          }
      }
      return DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE;
  }

  sal_Int8 NavigatorTree::AcceptDrop( const AcceptDropEvent& rEvt )
  {
      ::Point aDropPos = rEvt.maPosPixel;
      std::unique_ptr<weld::TreeIter> xDropTarget(m_xTreeView->make_iterator());
      // get_dest_row_at_pos with false cause we must drop exactly "on" a form to paste a control into it
      if (!m_xTreeView->get_dest_row_at_pos(aDropPos, xDropTarget.get(), false))
          xDropTarget.reset();
      return implAcceptDataTransfer(m_aDropTargetHelper.GetDataFlavorExVector(), rEvt.mnAction, xDropTarget.get(), true);
  }

  sal_Int8 NavigatorTree::implExecuteDataTransfer( const OControlTransferData& _rData, sal_Int8 _nAction, const ::Point& _rDropPos, bool _bDnD )
  {
      std::unique_ptr<weld::TreeIter> xDrop(m_xTreeView->make_iterator());
      // get_dest_row_at_pos with false cause we must drop exactly "on" a form to paste a control into it
      if (!m_xTreeView->get_dest_row_at_pos(_rDropPos, xDrop.get(), false))
          xDrop.reset();
      return implExecuteDataTransfer( _rData, _nAction, xDrop.get(), _bDnD );
  }

  sal_Int8 NavigatorTree::implExecuteDataTransfer( const OControlTransferData& _rData, sal_Int8 _nAction, const weld::TreeIter* _pTargetEntry, bool _bDnD )
  {
      const DataFlavorExVector& rDataFlavors = _rData.GetDataFlavorExVector();

      if ( DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE == implAcceptDataTransfer( rDataFlavors, _nAction, _pTargetEntry, _bDnD ) )
          // under some platforms, it may happen that ExecuteDrop is called though AcceptDrop returned DND_ACTION_NONE
          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

      if (!_pTargetEntry)
          // no target -> no drop
          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

      // format checks
888#ifdef DBG_UTIL
      bool bHasHiddenControlsFormat = OControlExchange::hasHiddenControlModelsFormat( rDataFlavors );
      bool bForeignCollection = _rData.getFormsRoot().get() != GetNavModel()->GetFormPage()->GetForms().get();
      DBG_ASSERT(!bForeignCollection || bHasHiddenControlsFormat, "NavigatorTree::implExecuteDataTransfer: invalid format (AcceptDrop shouldn't have let this pass) !")do { if (true && (!(!bForeignCollection || bHasHiddenControlsFormat
))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "891" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: invalid format (AcceptDrop shouldn't have let this pass) !"
); } } while (false);
      DBG_ASSERT(bForeignCollection || !m_bDragDataDirty, "NavigatorTree::implExecuteDataTransfer: invalid state (shell changed since last exchange resync) !")do { if (true && (!(bForeignCollection || !m_bDragDataDirty
))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "892" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: invalid state (shell changed since last exchange resync) !"
); } } while (false);
          // this should be done in AcceptDrop: the list of controls is created in _rData
          // and m_bDragDataDirty is reset
895#endif

      if ( DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY == _nAction )
      {   // bHasHiddenControlsFormat means that only hidden controls are part of the data
899#ifdef DBG_UTIL
          DBG_ASSERT( bHasHiddenControlsFormat, "NavigatorTree::implExecuteDataTransfer: copy allowed for hidden controls only!" )do { if (true && (!(bHasHiddenControlsFormat))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "900" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: copy allowed for hidden controls only!"
); } } while (false);
901#endif
          DBG_ASSERT( _pTargetEntry && m_xTreeView->iter_compare(*_pTargetEntry, *m_xRootEntry) != 0 && IsFormEntry( *_pTargetEntry ),do { if (true && (!(_pTargetEntry && m_xTreeView
->iter_compare(*_pTargetEntry, *m_xRootEntry) != 0 &&
 IsFormEntry( *_pTargetEntry )))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN
), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "903" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: should not be here!"
); } } while (false)
              "NavigatorTree::implExecuteDataTransfer: should not be here!" )do { if (true && (!(_pTargetEntry && m_xTreeView
->iter_compare(*_pTargetEntry, *m_xRootEntry) != 0 &&
 IsFormEntry( *_pTargetEntry )))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN
), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "903" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: should not be here!"
); } } while (false);
              // implAcceptDataTransfer should have caught both cases

906#ifdef DBG_UTIL
          DBG_ASSERT(bHasHiddenControlsFormat, "NavigatorTree::implExecuteDataTransfer: only copying of hidden controls is supported !")do { if (true && (!(bHasHiddenControlsFormat))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "907" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: only copying of hidden controls is supported !"
); } } while (false);
              // should be caught by AcceptDrop
909#endif

          // because i want to select all targets (and only them)
          m_xTreeView->unselect_all();

          const Sequence< Reference< XInterface > >& aControls = _rData.hiddenControls();
          sal_Int32 nCount = aControls.getLength();
          const Reference< XInterface >* pControls = aControls.getConstArray();

          FmFormShell* pFormShell = GetNavModel()->GetFormShell();
          FmFormModel* pFormModel = pFormShell ? pFormShell->GetFormModel() : nullptr;

          // within undo
          if (pFormModel)
          {
              OUString aStr(SvxResId(RID_STR_CONTROLreinterpret_cast<char const *>("RID_STR_CONTROL" "\004"
 u8"Control")));
              OUString aUndoStr = SvxResId(RID_STR_UNDO_CONTAINER_INSERTreinterpret_cast<char const *>("RID_STR_UNDO_CONTAINER_INSERT"
 "\004" u8"Insert in container")).replaceAll("#", aStr);
              pFormModel->BegUndo(aUndoStr);
          }

          // copy controls
          for (sal_Int32 i=0; i<nCount; ++i)
          {
              // create new control
              FmControlData* pNewControlData = NewControl( FM_COMPONENT_HIDDEN"stardiv.one.form.component.Hidden", *_pTargetEntry, false);
              Reference< XPropertySet >  xNewPropSet( pNewControlData->GetPropertySet() );

              // copy properties form old control to new one
              Reference< XPropertySet >  xCurrent(pControls[i], UNO_QUERY);
938#if (OSL_DEBUG_LEVEL1 > 0)
              // check whether it is a hidden control
              sal_Int16 nClassId = ::comphelper::getINT16(xCurrent->getPropertyValue(FM_PROP_CLASSID"ClassId"));
              OSL_ENSURE(nClassId == FormComponentType::HIDDENCONTROL, "NavigatorTree::implExecuteDataTransfer: invalid control in drop list !")do { if (true && (!(nClassId == FormComponentType::HIDDENCONTROL
))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "941" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: invalid control in drop list !"
); } } while (false);
                  // if SVX_FM_HIDDEN_CONTROLS-format exists, the sequence
                  // should only contain hidden controls
944#endif // (OSL_DEBUG_LEVEL > 0)
              Reference< XPropertySetInfo >  xPropInfo( xCurrent->getPropertySetInfo());
              const Sequence< Property> seqAllCurrentProps = xPropInfo->getProperties();
              for (Property const & currentProp : seqAllCurrentProps)
              {
                  if (((currentProp.Attributes & PropertyAttribute::READONLY) == 0) && (currentProp.Name != FM_PROP_NAME"Name"))
                  {   // (read-only attribs aren't set, ditto name,
                      // NewControl defined it uniquely
                      xNewPropSet->setPropertyValue(currentProp.Name, xCurrent->getPropertyValue(currentProp.Name));
                  }
              }

              std::unique_ptr<weld::TreeIter> xToSelect = FindEntry(pNewControlData);
              m_xTreeView->select(*xToSelect);
              if (i == 0)
                  m_xTreeView->set_cursor(*xToSelect);
          }

          if (pFormModel)
              pFormModel->EndUndo();

          return _nAction;
      }

      if ( !OControlExchange::hasFieldExchangeFormat( _rData.GetDataFlavorExVector() ) )
      {
          // can't do anything without the internal format here ... usually happens when doing DnD or CnP
          // over navigator boundaries
          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;
      }

      // some data for the target
      bool bDropTargetIsForm = IsFormEntry(*_pTargetEntry);
      FmFormData* pTargetData = bDropTargetIsForm ? reinterpret_cast<FmFormData*>(m_xTreeView->get_id(*_pTargetEntry).toInt64()) : nullptr;

      DBG_ASSERT( DND_ACTION_COPY != _nAction, "NavigatorTree::implExecuteDataTransfer: somebody changed the logics!" )do { if (true && (!(css::datatransfer::dnd::DNDConstants
::ACTION_COPY != _nAction))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN
), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "979" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: somebody changed the logics!"
); } } while (false);

      // list of dragged entries
      const ListBoxEntrySet& rDropped = _rData.selected();
      DBG_ASSERT(!rDropped.empty(), "NavigatorTree::implExecuteDataTransfer: no entries!")do { if (true && (!(!rDropped.empty()))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "983" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: no entries!"
); } } while (false);

      // make a copy because rDropped is updated on deleting an entry which we do in the processing loop
      ListBoxEntrySet aDropped;
      for (const auto& rEntry : rDropped)
          aDropped.emplace(m_xTreeView->make_iterator(rEntry.get()));

      // shell and model
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      FmFormModel* pFormModel = pFormShell ? pFormShell->GetFormModel() : nullptr;
      if (!pFormModel)
          return DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE;

      // for Undo
      const bool bUndo = pFormModel->IsUndoEnabled();

      if( bUndo )
      {
          OUString strUndoDescription(SvxResId(RID_STR_UNDO_CONTAINER_REPLACEreinterpret_cast<char const *>("RID_STR_UNDO_CONTAINER_REPLACE"
 "\004" u8"Replace a container element")));
          pFormModel->BegUndo(strUndoDescription);
      }

      // remove selection before adding an entry, so the mark doesn't flicker
      // -> lock action of selection
      LockSelectionHandling();

      // go through all dropped entries
      for (   ListBoxEntrySet::const_iterator dropped = aDropped.begin();
              dropped != aDropped.end();
              ++dropped
          )
      {
          bool bFirstEntry = aDropped.begin() == dropped;

          // some data of the current element
          const auto& rCurrent = *dropped;
          DBG_ASSERT(rCurrent, "NavigatorTree::implExecuteDataTransfer: invalid entry")do { if (true && (!(rCurrent))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1019" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: invalid entry"
); } } while (false);
          DBG_ASSERT(m_xTreeView->get_iter_depth(*rCurrent) != 0, "NavigatorTree::implExecuteDataTransfer: invalid entry")do { if (true && (!(m_xTreeView->get_iter_depth(*rCurrent
) != 0))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN),
 ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1020" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: invalid entry"
); } } while (false);
              // don't drag root

          FmEntryData* pCurrentUserData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*rCurrent).toInt64());

          Reference< XChild >  xCurrentChild = pCurrentUserData->GetChildIFace();
          Reference< XIndexContainer >  xContainer(xCurrentChild->getParent(), UNO_QUERY);

          FmFormData* pCurrentParentUserData = static_cast<FmFormData*>(pCurrentUserData->GetParent());
          DBG_ASSERT(pCurrentParentUserData == nullptr || dynamic_cast<const FmFormData*>(pCurrentUserData->GetParent()) !=  nullptr, "NavigatorTree::implExecuteDataTransfer: invalid parent")do { if (true && (!(pCurrentParentUserData == nullptr
 || dynamic_cast<const FmFormData*>(pCurrentUserData->
GetParent()) != nullptr))) { sal_detail_logFormat((SAL_DETAIL_LOG_LEVEL_WARN
), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1029" ": "), "%s", "NavigatorTree::implExecuteDataTransfer: invalid parent"
); } } while (false);

          // remove from parent
          if (pCurrentParentUserData)
              pCurrentParentUserData->GetChildList()->removeNoDelete( pCurrentUserData );
          else
              GetNavModel()->GetRootList()->removeNoDelete( pCurrentUserData );

          // remove from container
          sal_Int32 nIndex = getElementPos(xContainer, xCurrentChild);
          GetNavModel()->m_pPropChangeList->Lock();
          // UndoAction for removal
          if ( bUndo && GetNavModel()->m_pPropChangeList->CanUndo())
          {
              pFormModel->AddUndo(std::make_unique<FmUndoContainerAction>(*pFormModel, FmUndoContainerAction::Removed,
                                                          xContainer, xCurrentChild, nIndex));
          }
          else if( !GetNavModel()->m_pPropChangeList->CanUndo() )
          {
              FmUndoContainerAction::DisposeElement( xCurrentChild );
          }

          // copy events
          Reference< XEventAttacherManager >  xManager(xContainer, UNO_QUERY);
          Sequence< ScriptEventDescriptor > aEvts;

          if (xManager.is() && nIndex >= 0)
              aEvts = xManager->getScriptEvents(nIndex);
          xContainer->removeByIndex(nIndex);

          // remove selection
          m_xTreeView->unselect(*rCurrent);
          // and delete it
          Remove(pCurrentUserData);

          // position in DropParents, where to insert dropped entries
          if (pTargetData)
              xContainer.set(pTargetData->GetElement(), UNO_QUERY);
          else
              xContainer = GetNavModel()->GetForms();

          // always insert at the end
          nIndex = xContainer->getCount();

          // UndoAction for insertion
          if ( bUndo && GetNavModel()->m_pPropChangeList->CanUndo())
              pFormModel->AddUndo(std::make_unique<FmUndoContainerAction>(*pFormModel, FmUndoContainerAction::Inserted,
                                                       xContainer, xCurrentChild, nIndex));

          // insert in new container
          if (pTargetData)
          {
               // insert in a form needs a FormComponent
              xContainer->insertByIndex( nIndex,
                  makeAny( Reference< XFormComponent >( xCurrentChild, UNO_QUERY ) ) );
          }
          else
          {
              xContainer->insertByIndex( nIndex,
                  makeAny( Reference< XForm >( xCurrentChild, UNO_QUERY ) ) );
          }

          if (aEvts.hasElements())
          {
              xManager.set(xContainer, UNO_QUERY);
              if (xManager.is())
                  xManager->registerScriptEvents(nIndex, aEvts);
          }

          GetNavModel()->m_pPropChangeList->UnLock();

          // give an entry the new parent
          pCurrentUserData->SetParent(pTargetData);

          // give parent the new child
          if (pTargetData)
              pTargetData->GetChildList()->insert( std::unique_ptr<FmEntryData>(pCurrentUserData), nIndex );
          else
              GetNavModel()->GetRootList()->insert( std::unique_ptr<FmEntryData>(pCurrentUserData), nIndex );

          // announce to myself and reselect
          std::unique_ptr<weld::TreeIter> xNew = Insert( pCurrentUserData, nIndex );
          if (bFirstEntry && xNew)
          {
              if (m_xTreeView->iter_parent(*xNew))
                  m_xTreeView->expand_row(*xNew);
          }
      }

      UnlockSelectionHandling();

      if( bUndo )
          pFormModel->EndUndo();

      // During the move, the markings of the underlying view did not change (because the view is not affected by the logical
      // hierarchy of the form/control models. But my selection changed - which means I have to adjust it according to the
      // view marks, again.
      SynchronizeSelection();

      // in addition, with the move of controls such things as "the current form" may have changed - force the shell
      // to update itself accordingly
      if( pFormShell && pFormShell->GetImpl() && pFormShell->GetFormView() )
          pFormShell->GetImpl()->DetermineSelection_Lock( pFormShell->GetFormView()->GetMarkedObjectList() );

      if ( m_aControlExchange.isClipboardOwner() && ( DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE == _nAction ) )
          m_aControlExchange->clear();

      return _nAction;
  }

  sal_Int8 NavigatorTree::ExecuteDrop( const ExecuteDropEvent& rEvt )
  {
      sal_Int8 nResult( DND_ACTION_NONEcss::datatransfer::dnd::DNDConstants::ACTION_NONE );
      if ( m_aControlExchange.isDragSource() )
          nResult = implExecuteDataTransfer( *m_aControlExchange, rEvt.mnAction, rEvt.maPosPixel, true );
      else
      {
          OControlTransferData aDroppedData( rEvt.maDropEvent.Transferable );
          nResult = implExecuteDataTransfer( aDroppedData, rEvt.mnAction, rEvt.maPosPixel, true );
      }
      return nResult;
  }

  void NavigatorTree::doPaste()
  {
      std::unique_ptr<weld::TreeIter> xSelected(m_xTreeView->make_iterator());
      if (!m_xTreeView->get_selected(xSelected.get()))
          xSelected.reset();

      try
      {
          if ( m_aControlExchange.isClipboardOwner() )
          {
              implExecuteDataTransfer( *m_aControlExchange, doingKeyboardCut( ) ? DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE : DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY, xSelected.get(), false );
          }
          else
          {
              // the clipboard content
              Reference< XClipboard > xClipboard( GetSystemClipboard() );
              Reference< XTransferable > xTransferable;
              if ( xClipboard.is() )
                  xTransferable = xClipboard->getContents();

              OControlTransferData aClipboardContent( xTransferable );
              implExecuteDataTransfer( aClipboardContent, DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY, xSelected.get(), false );
          }
      }
      catch( const Exception& )
      {
          TOOLS_WARN_EXCEPTION( "svx", "NavigatorTree::doPaste" )do { css::uno::Any tools_warn_exception( DbgGetCaughtException
() ); do { if (true) { switch (sal_detail_log_report(::SAL_DETAIL_LOG_LEVEL_WARN
, "svx")) { case SAL_DETAIL_LOG_ACTION_IGNORE: break; case SAL_DETAIL_LOG_ACTION_LOG
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "NavigatorTree::doPaste" << " " << exceptionToString
(tools_warn_exception)) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN
), ("svx"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1178" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::doPaste" << " "
 << exceptionToString(tools_warn_exception)), 0); } else
 { ::std::ostringstream sal_detail_stream; sal_detail_stream <<
 "NavigatorTree::doPaste" << " " << exceptionToString
(tools_warn_exception); ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN
), ("svx"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1178" ": "), sal_detail_stream, 0); }; break; case SAL_DETAIL_LOG_ACTION_FATAL
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "NavigatorTree::doPaste" << " " << exceptionToString
(tools_warn_exception)) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN
), ("svx"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1178" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::doPaste" << " "
 << exceptionToString(tools_warn_exception)), 0); } else
 { ::std::ostringstream sal_detail_stream; sal_detail_stream <<
 "NavigatorTree::doPaste" << " " << exceptionToString
(tools_warn_exception); ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN
), ("svx"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1178" ": "), sal_detail_stream, 0); }; std::abort(); break
; } } } while (false); } while (false);
      }
  }

  void NavigatorTree::doCopy()
  {
      if ( implPrepareExchange( DND_ACTION_COPYcss::datatransfer::dnd::DNDConstants::ACTION_COPY ) )
      {
          m_aControlExchange.setClipboardListener( LINK( this, NavigatorTree, OnClipboardAction )::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubOnClipboardAction) );
          m_aControlExchange.copyToClipboard( );
      }
  }

  void NavigatorTree::ModelHasRemoved(const weld::TreeIter* pTypedEntry)
  {
      if (doingKeyboardCut())
      {
          auto aIter = std::find_if(m_aCutEntries.begin(), m_aCutEntries.end(),
                                    [this, pTypedEntry](const auto& rElem) {
                                      return m_xTreeView->iter_compare(*rElem, *pTypedEntry) == 0;
                                    });
          if (aIter != m_aCutEntries.end())
              m_aCutEntries.erase(aIter);
      }

      if (m_aControlExchange.isDataExchangeActive())
      {
          if (0 == m_aControlExchange->onEntryRemoved(m_xTreeView.get(), pTypedEntry))
          {
              // last of the entries which we put into the clipboard has been deleted from the tree.
              // Give up the clipboard ownership.
              m_aControlExchange.clear();
          }
      }
  }

  void NavigatorTree::doCut()
  {
      if ( !implPrepareExchange( DND_ACTION_MOVEcss::datatransfer::dnd::DNDConstants::ACTION_MOVE ) )
          return;

      m_aControlExchange.setClipboardListener( LINK( this, NavigatorTree, OnClipboardAction )::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubOnClipboardAction) );
      m_aControlExchange.copyToClipboard( );
      m_bKeyboardCut = true;

      // mark all the entries we just "cut" into the clipboard as "nearly moved"
      for (const auto& rEntry : m_arrCurrentSelection )
      {
          if (!rEntry)
              continue;
          m_aCutEntries.emplace(m_xTreeView->make_iterator(rEntry.get()));
          m_xTreeView->set_sensitive(*rEntry, false);
      }
  }

  IMPL_LINK(NavigatorTree, KeyInputHdl, const ::KeyEvent&, rKEvt, bool)bool NavigatorTree::LinkStubKeyInputHdl(void * instance, const
 ::KeyEvent& data) { return static_cast<NavigatorTree *
>(instance)->KeyInputHdl(data); } bool NavigatorTree::KeyInputHdl
(const ::KeyEvent& rKEvt)
1
Calling 'NavigatorTree::KeyInputHdl'→
  {
      const vcl::KeyCode& rCode = rKEvt.GetKeyCode();

      // delete?
      if (rCode.GetCode() == KEY_DELETE && !rCode.GetModifier())
2
←
Assuming the condition is true→
3
←
Assuming the condition is true→
4
←
Taking true branch→
      {
          DeleteSelection();
5
←
Calling 'NavigatorTree::DeleteSelection'→
          return true;
      }

      // copy'n'paste?
      switch ( rCode.GetFunction() )
      {
          case KeyFuncType::CUT:
              doCut();
              break;

          case KeyFuncType::PASTE:
              if ( implAcceptPaste() )
                  doPaste();
              break;

          case KeyFuncType::COPY:
              doCopy();
              break;

          default:
              break;
      }

      return false;
  }

  IMPL_LINK(NavigatorTree, EditingEntryHdl, const weld::TreeIter&, rIter, bool)bool NavigatorTree::LinkStubEditingEntryHdl(void * instance, const
 weld::TreeIter& data) { return static_cast<NavigatorTree
 *>(instance)->EditingEntryHdl(data); } bool NavigatorTree
::EditingEntryHdl(const weld::TreeIter& rIter)
  {
      // root, which isn't allowed to be renamed, has UserData=NULL
      m_bEditing = !m_xTreeView->get_id(rIter).isEmpty();
      return m_bEditing;
  }

  void NavigatorTree::NewForm(const weld::TreeIter& rParentEntry)
  {
      // get ParentFormData
      if (!IsFormEntry(rParentEntry))
          return;

      FmFormData* pParentFormData = reinterpret_cast<FmFormData*>(m_xTreeView->get_id(rParentEntry).toInt64());


      // create new form
      Reference<XComponentContext> xContext = comphelper::getProcessComponentContext();
      Reference< XForm >  xNewForm(xContext->getServiceManager()->createInstanceWithContext(FM_SUN_COMPONENT_FORM"com.sun.star.form.component.Form", xContext), UNO_QUERY);
      if (!xNewForm.is())
          return;

      Reference< XPropertySet >  xPropertySet(xNewForm, UNO_QUERY);
      if (!xPropertySet.is())
          return;

      FmFormData* pNewFormData = new FmFormData(xNewForm, pParentFormData);


      // set name
      OUString aName = GenerateName(pNewFormData);
      pNewFormData->SetText(aName);

      try
      {
          xPropertySet->setPropertyValue( FM_PROP_NAME"Name", makeAny(aName) );
          // a form should always have the command type table as default
          xPropertySet->setPropertyValue( FM_PROP_COMMANDTYPE"CommandType", makeAny(sal_Int32(CommandType::TABLE)));
      }
      catch ( const Exception& )
      {
          OSL_FAIL("NavigatorTree::NewForm : could not set essential properties!")do { if (true && (((sal_Bool)1))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1308" ": "), "%s", "NavigatorTree::NewForm : could not set essential properties!"
); } } while (false);
      }


      // insert form
      GetNavModel()->Insert(pNewFormData, SAL_MAX_UINT32((sal_uInt32) 0xFFFFFFFF), true);


      // set new form as active
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if( pFormShell )
      {
          InterfaceBag aSelection;
          aSelection.insert( Reference<XInterface>( xNewForm, UNO_QUERY ) );
          pFormShell->GetImpl()->setCurrentSelection_Lock(aSelection);

          pFormShell->GetViewShell()->GetViewFrame()->GetBindings().Invalidate(SID_FM_PROPERTIES( 10000 + 614 ), true, true);
      }
      GetNavModel()->SetModified();

      // switch to EditMode
      std::unique_ptr<weld::TreeIter> xNewEntry = FindEntry(pNewFormData);
      m_xTreeView->start_editing(*xNewEntry);
      m_bEditing = true;
  }

  FmControlData* NavigatorTree::NewControl(const OUString& rServiceName, const weld::TreeIter& rParentEntry, bool bEditName)
  {
      // get ParentForm
      if (!GetNavModel()->GetFormShell())
          return nullptr;
      if (!IsFormEntry(rParentEntry))
          return nullptr;

      FmFormData* pParentFormData = reinterpret_cast<FmFormData*>(m_xTreeView->get_id(rParentEntry).toInt64());
      Reference<XForm>  xParentForm(pParentFormData->GetFormIface());

      // create new component
      Reference<XComponentContext> xContext = comphelper::getProcessComponentContext();
      Reference<XFormComponent> xNewComponent( xContext->getServiceManager()->createInstanceWithContext(rServiceName, xContext), UNO_QUERY);
      if (!xNewComponent.is())
          return nullptr;

      FmControlData* pNewFormControlData = new FmControlData(xNewComponent, pParentFormData);

      // set name
      OUString sName = FmFormPageImpl::setUniqueName( xNewComponent, xParentForm );

      pNewFormControlData->SetText( sName );

      // insert FormComponent
      GetNavModel()->Insert(pNewFormControlData, SAL_MAX_UINT32((sal_uInt32) 0xFFFFFFFF), true);
      GetNavModel()->SetModified();

      if (bEditName)
      {
          // switch to EditMode
          std::unique_ptr<weld::TreeIter> xNewEntry = FindEntry( pNewFormControlData );
          m_xTreeView->select(*xNewEntry);

          m_xTreeView->start_editing(*xNewEntry);
          m_bEditing = true;
      }

      return pNewFormControlData;
  }

  OUString NavigatorTree::GenerateName( FmEntryData const * pEntryData )
  {
      const sal_uInt16 nMaxCount = 99;
      OUString aNewName;

      // create base name
      OUString aBaseName;
      if( dynamic_cast<const FmFormData*>( pEntryData) !=  nullptr )
          aBaseName = SvxResId( RID_STR_STDFORMNAMEreinterpret_cast<char const *>("RID_STR_STDFORMNAME" "\004"
 u8"Form") );
      else if( dynamic_cast<const FmControlData*>( pEntryData) !=  nullptr )
          aBaseName = SvxResId( RID_STR_CONTROLreinterpret_cast<char const *>("RID_STR_CONTROL" "\004"
 u8"Control") );


      // create new name
      FmFormData* pFormParentData = static_cast<FmFormData*>(pEntryData->GetParent());

      for( sal_Int32 i=0; i<nMaxCount; i++ )
      {
          aNewName = aBaseName;
          if( i>0 )
          {
              aNewName += " " + OUString::number(i);
          }

          if( GetNavModel()->FindData(aNewName, pFormParentData,false) == nullptr )
              break;
      }

      return aNewName;
  }

  IMPL_LINK(NavigatorTree, EditedEntryHdl, const IterString&, rIterString, bool)bool NavigatorTree::LinkStubEditedEntryHdl(void * instance, const
 IterString& data) { return static_cast<NavigatorTree *
>(instance)->EditedEntryHdl(data); } bool NavigatorTree
::EditedEntryHdl(const IterString& rIterString)
  {
      m_bEditing = false;

      const weld::TreeIter& rIter = rIterString.first;

      FmEntryData* pEntryData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(rIter).toInt64());
      bool bRes = NavigatorTreeModel::Rename(pEntryData, rIterString.second);
      if (!bRes)
      {
          m_xEditEntry = m_xTreeView->make_iterator(&rIter);
          nEditEvent = Application::PostUserEvent(LINK(this, NavigatorTree, OnEdit)::tools::detail::makeLink( ::tools::detail::castTo<NavigatorTree
 *>(this), &NavigatorTree::LinkStubOnEdit));
      }

      return bRes;
  }

  IMPL_LINK_NOARG(NavigatorTree, OnEdit, void*, void)void NavigatorTree::LinkStubOnEdit(void * instance, void* data
) { return static_cast<NavigatorTree *>(instance)->OnEdit
(data); } void NavigatorTree::OnEdit(__attribute__ ((unused))
 void*)
  {
      nEditEvent = nullptr;
      m_xTreeView->start_editing(*m_xEditEntry);
      m_bEditing = true;
      m_xEditEntry.reset();
  }

  IMPL_LINK_NOARG(NavigatorTree, OnEntrySelDesel, weld::TreeView&, void)void NavigatorTree::LinkStubOnEntrySelDesel(void * instance, weld
::TreeView& data) { return static_cast<NavigatorTree *
>(instance)->OnEntrySelDesel(data); } void NavigatorTree
::OnEntrySelDesel(__attribute__ ((unused)) weld::TreeView&
)
  {
      m_sdiState = SDI_DIRTY;

      if (IsSelectionHandlingLocked())
          return;

      if (m_aSynchronizeTimer.IsActive())
          m_aSynchronizeTimer.Stop();

      m_aSynchronizeTimer.SetTimeout(EXPLORER_SYNC_DELAY200);
      m_aSynchronizeTimer.Start();
  }

  IMPL_LINK_NOARG(NavigatorTree, OnSynchronizeTimer, Timer *, void)void NavigatorTree::LinkStubOnSynchronizeTimer(void * instance
, Timer * data) { return static_cast<NavigatorTree *>(instance
)->OnSynchronizeTimer(data); } void NavigatorTree::OnSynchronizeTimer
(__attribute__ ((unused)) Timer *)
  {
      SynchronizeMarkList();
  }

  IMPL_LINK_NOARG(NavigatorTree, OnClipboardAction, OLocalExchange&, void)void NavigatorTree::LinkStubOnClipboardAction(void * instance
, OLocalExchange& data) { return static_cast<NavigatorTree
 *>(instance)->OnClipboardAction(data); } void NavigatorTree
::OnClipboardAction(__attribute__ ((unused)) OLocalExchange&
)
  {
      if ( m_aControlExchange.isClipboardOwner() )
          return;

      if ( !doingKeyboardCut() )
          return;

      for (const auto& rEntry : m_aCutEntries)
      {
          if (!rEntry)
              continue;
          m_xTreeView->set_sensitive(*rEntry, true);
      }
      ListBoxEntrySet aEmpty;
      m_aCutEntries.swap( aEmpty );

      m_bKeyboardCut = false;
  }

  void NavigatorTree::ShowSelectionProperties(bool bForce)
  {
      // at first i need the FormShell
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if (!pFormShell)
          // no shell -> impossible to set curObject -> leave
          return;

      CollectSelectionData(SDI_ALL);
      SAL_WARN_IF(static_cast<size_t>(m_nFormsSelected + m_nControlsSelecteddo { if (true && (static_cast<size_t>(m_nFormsSelected
 + m_nControlsSelected + (m_bRootSelected ? 1 : 0)) != m_arrCurrentSelection
.size())) { switch (sal_detail_log_report(::SAL_DETAIL_LOG_LEVEL_WARN
, "svx.form")) { case SAL_DETAIL_LOG_ACTION_IGNORE: break; case
 SAL_DETAIL_LOG_ACTION_LOG: if (sizeof ::sal::detail::getResult
( ::sal::detail::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; break; case SAL_DETAIL_LOG_ACTION_FATAL
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; std::abort(); break
; } } } while (false)
              + (m_bRootSelected ? 1 : 0)) != m_arrCurrentSelection.size(),do { if (true && (static_cast<size_t>(m_nFormsSelected
 + m_nControlsSelected + (m_bRootSelected ? 1 : 0)) != m_arrCurrentSelection
.size())) { switch (sal_detail_log_report(::SAL_DETAIL_LOG_LEVEL_WARN
, "svx.form")) { case SAL_DETAIL_LOG_ACTION_IGNORE: break; case
 SAL_DETAIL_LOG_ACTION_LOG: if (sizeof ::sal::detail::getResult
( ::sal::detail::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; break; case SAL_DETAIL_LOG_ACTION_FATAL
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; std::abort(); break
; } } } while (false)
          "svx.form",do { if (true && (static_cast<size_t>(m_nFormsSelected
 + m_nControlsSelected + (m_bRootSelected ? 1 : 0)) != m_arrCurrentSelection
.size())) { switch (sal_detail_log_report(::SAL_DETAIL_LOG_LEVEL_WARN
, "svx.form")) { case SAL_DETAIL_LOG_ACTION_IGNORE: break; case
 SAL_DETAIL_LOG_ACTION_LOG: if (sizeof ::sal::detail::getResult
( ::sal::detail::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; break; case SAL_DETAIL_LOG_ACTION_FATAL
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; std::abort(); break
; } } } while (false)
          "NavigatorTree::ShowSelectionProperties : selection meta data invalid !")do { if (true && (static_cast<size_t>(m_nFormsSelected
 + m_nControlsSelected + (m_bRootSelected ? 1 : 0)) != m_arrCurrentSelection
.size())) { switch (sal_detail_log_report(::SAL_DETAIL_LOG_LEVEL_WARN
, "svx.form")) { case SAL_DETAIL_LOG_ACTION_IGNORE: break; case
 SAL_DETAIL_LOG_ACTION_LOG: if (sizeof ::sal::detail::getResult
( ::sal::detail::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; break; case SAL_DETAIL_LOG_ACTION_FATAL
: if (sizeof ::sal::detail::getResult( ::sal::detail::StreamStart
() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
) == 1) { ::sal_detail_log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), ::sal::detail::unwrapStream( ::sal::detail
::StreamStart() << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
), 0); } else { ::std::ostringstream sal_detail_stream; sal_detail_stream
 << "NavigatorTree::ShowSelectionProperties : selection meta data invalid !"
; ::sal::detail::log( (::SAL_DETAIL_LOG_LEVEL_WARN), ("svx.form"
), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1482" ": "), sal_detail_stream, 0); }; std::abort(); break
; } } } while (false);


      InterfaceBag aSelection;
      bool bSetSelectionAsMarkList = false;

      if (m_bRootSelected)
          ;                                   // no properties for the root, neither for single nor for multi selection
      else if ( m_nFormsSelected + m_nControlsSelected == 0 )   // none of the two should be less 0
          ;                                   // no selection -> no properties
      else if ( m_nFormsSelected * m_nControlsSelected != 0 )
          ;                                   // mixed selection -> no properties
      else
      {   // either only forms, or only controls are selected
          if (m_arrCurrentSelection.size() == 1)
          {
              const std::unique_ptr<weld::TreeIter>& rIter = *m_arrCurrentSelection.begin();
              if (m_nFormsSelected > 0)
              {   // exactly one form is selected
                  FmFormData* pFormData = reinterpret_cast<FmFormData*>(m_xTreeView->get_id(*rIter).toInt64());
                  aSelection.insert( Reference< XInterface >( pFormData->GetFormIface(), UNO_QUERY ) );
              }
              else
              {   // exactly one control is selected (whatever hidden or normal)
                  FmEntryData* pEntryData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*rIter).toInt64());

                  aSelection.insert( Reference< XInterface >( pEntryData->GetElement(), UNO_QUERY ) );
              }
          }
          else
          {   // it's a MultiSelection, so we must build a MultiSet
              if (m_nFormsSelected > 0)
              {   // ... only forms
                  // first of all collect PropertySet-Interfaces of the forms
                  SvLBoxEntrySortedArray::const_iterator it = m_arrCurrentSelection.begin();
                  for ( sal_Int32 i = 0; i < m_nFormsSelected; ++i )
                  {
                      const std::unique_ptr<weld::TreeIter>& rIter = *it;
                      FmFormData* pFormData = reinterpret_cast<FmFormData*>(m_xTreeView->get_id(*rIter).toInt64());
                      aSelection.insert( pFormData->GetPropertySet().get() );
                      ++it;
                  }
              }
              else
              {   // ... only controls
                  if (m_nHiddenControls == m_nControlsSelected)
                  {   // a MultiSet for properties of hidden controls
                      SvLBoxEntrySortedArray::const_iterator it = m_arrCurrentSelection.begin();
                      for ( sal_Int32 i = 0; i < m_nHiddenControls; ++i )
                      {
                          const std::unique_ptr<weld::TreeIter>& rIter = *it;
                          FmEntryData* pEntryData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*rIter).toInt64());
                          aSelection.insert( pEntryData->GetPropertySet().get() );
                          ++it;
                      }
                  }
                  else if (m_nHiddenControls == 0)
                  {   // only normal controls
                      bSetSelectionAsMarkList = true;
                  }
              }
          }

      }

      // and now my form and my SelObject
      if ( bSetSelectionAsMarkList )
          pFormShell->GetImpl()->setCurrentSelectionFromMark_Lock(pFormShell->GetFormView()->GetMarkedObjectList());
      else
          pFormShell->GetImpl()->setCurrentSelection_Lock(aSelection);

      if (pFormShell->GetImpl()->IsPropBrwOpen_Lock() || bForce)
      {
          // and now deliver all to the PropertyBrowser
          pFormShell->GetViewShell()->GetViewFrame()->GetDispatcher()->Execute( SID_FM_SHOW_PROPERTY_BROWSER( 10000 + 703 ), SfxCallMode::ASYNCHRON );
      }
  }


  void NavigatorTree::DeleteSelection()
  {
      // of course, i can't delete root
      bool bRootSelected = m_xTreeView->is_selected(*m_xRootEntry);
      auto nSelectedEntries = m_xTreeView->count_selected_rows();
      if (bRootSelected && (nSelectedEntries > 1))     // root and other elements ?
6
←
Assuming 'bRootSelected' is false→
          m_xTreeView->unselect(*m_xRootEntry);                // yes -> remove root from selection

      if ((nSelectedEntries == 0) || bRootSelected7.1
'bRootSelected' is false
1
'bRootSelected' is false
1
'bRootSelected' is false
)    // still root ?
7
←
Assuming 'nSelectedEntries' is not equal to 0→
8
←
Taking false branch→
          return;                                     // -> only selected element -> leave

      DBG_ASSERT(!m_bPrevSelectionMixed, "NavigatorTree::DeleteSelection() : delete permitted if mark and selection are inconsistent")do { if (true && (!(!m_bPrevSelectionMixed))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1572" ": "), "%s", "NavigatorTree::DeleteSelection() : delete permitted if mark and selection are inconsistent"
); } } while (false);
9
←
Assuming field 'm_bPrevSelectionMixed' is true→
10
←
Taking true branch→
11
←
Loop condition is false.  Exiting loop→

      // i need the FormModel later
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if (!pFormShell)
12
←
Assuming 'pFormShell' is non-null→
13
←
Taking false branch→
          return;
      FmFormModel* pFormModel = pFormShell->GetFormModel();
      if (!pFormModel)
14
←
Assuming 'pFormModel' is non-null→
15
←
Taking false branch→
          return;

      // now I have to safeguard the DeleteList: if you delete a form and a dependent element
      // - in this order - than the SvLBoxEntryPtr of the dependent element is already invalid,
      // when it should be deleted... you have to prohibit this GPF, that of course would happen,
      // so I take the 'normalized' list
      CollectSelectionData( SDI_NORMALIZED );

      // see below for why we need this mapping from models to shapes
      FmFormView*     pFormView       = pFormShell->GetFormView();
      SdrPageView*    pPageView       = pFormView ? pFormView->GetSdrPageView() : nullptr;
16
←
Assuming 'pFormView' is null→
17
←
'?' condition is false→
      SdrPage*        pPage           = pPageView17.1
'pPageView' is null
1
'pPageView' is null
1
'pPageView' is null
 ? pPageView->GetPage() : nullptr;
18
←
'?' condition is false→
      DBG_ASSERT( pPage, "NavigatorTree::DeleteSelection: invalid form page!" )do { if (true && (!(pPage))) { sal_detail_logFormat((
SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1592" ": "), "%s", "NavigatorTree::DeleteSelection: invalid form page!"
); } } while (false);
19
←
Taking true branch→
20
←
Loop condition is false.  Exiting loop→

      MapModelToShape aModelShapes;
      if ( pPage20.1
'pPage' is null
1
'pPage' is null
1
'pPage' is null
 )
21
←
Taking false branch→
          collectShapeModelMapping( pPage, aModelShapes );

      // problem: we have to use ExplorerModel::Remove, since only this one properly deletes Form objects.
      // But, the controls themself must be deleted via DeleteMarked (else, the Writer has some problems
      // somewhere). In case I'd first delete the structure, then the controls, the UNDO would not work
      // (since UNDO then would mean to first restore the controls, then the structure, means their parent
      // form). The other way round, the EntryDatas would be invalid, if I'd first delete the controls and
      // then go on to the structure. This means I have to delete the forms *after* the normal controls, so
      // that during UNDO, they're restored in the proper order.
      pFormShell->GetImpl()->EnableTrackProperties_Lock(false);
      for (SvLBoxEntrySortedArray::reverse_iterator it = m_arrCurrentSelection.rbegin();
32
←
Loop condition is true.  Entering loop body→
           it != m_arrCurrentSelection.rend(); )
22
←
Calling 'operator!=<std::_Rb_tree_const_iterator<std::unique_ptr<weld::TreeIter, std::default_delete<weld::TreeIter>>>>'→
31
←
Returning from 'operator!=<std::_Rb_tree_const_iterator<std::unique_ptr<weld::TreeIter, std::default_delete<weld::TreeIter>>>>'→
      {
          const std::unique_ptr<weld::TreeIter>& rIter = *it;
          FmEntryData* pCurrent = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*rIter).toInt64());
33
←
'pCurrent' initialized here→

          // a form ?
          bool bIsForm = dynamic_cast<const FmFormData*>( pCurrent) !=  nullptr;
34
←
Assuming the condition is false→
35
←
Assuming pointer value is null→

          // because deletion is done by the view, and i build on its MarkList,
          // but normally only direct controls, no indirect ones, are marked in a marked form,
          // I have to do it later
          if (bIsForm35.1
'bIsForm' is false
1
'bIsForm' is false
1
'bIsForm' is false
)
36
←
Taking false branch→
              MarkViewObj(static_cast<FmFormData*>(pCurrent), true/*deep*/);

          // a hidden control ?
          bool bIsHidden = IsHiddenControl(pCurrent);
37
←
Calling 'NavigatorTree::IsHiddenControl'→
40
←
Returning from 'NavigatorTree::IsHiddenControl'→

          // keep forms and hidden controls, the rest not
          if (!bIsForm40.1
'bIsForm' is false
1
'bIsForm' is false
1
'bIsForm' is false
 && !bIsHidden40.2
'bIsHidden' is false
2
'bIsHidden' is false
2
'bIsHidden' is false
)
41
←
Taking true branch→
          {
              // well, no form and no hidden control -> we can remove it from m_arrCurrentSelection, as it will
              // be deleted automatically. This is because for every model (except forms and hidden control models)
              // there exist a shape, which is marked _if_and_only_if_ the model is selected in our tree.
              if ( aModelShapes.find( pCurrent->GetElement() ) != aModelShapes.end() )
42
←
Called C++ object pointer is null
              {
                  // if there's a shape for the current entry, then either it is marked or it is in a
                  // hidden layer (#i28502#), or something like this.
                  // In the first case, it will be deleted below, in the second case, we currently don't
                  // delete it, as there's no real (working!) API for this, neither in UNO nor in non-UNO.
                  m_arrCurrentSelection.erase( --(it.base()) );
              }
              else
                 ++it;
              // In case there is no shape for the current entry, we keep the entry in m_arrCurrentSelection,
              // since then we can definitely remove it.
          }
          else
              ++it;
      }
      pFormShell->GetImpl()->EnableTrackProperties_Lock(true);

      // let the view delete the marked controls
      pFormShell->GetFormView()->DeleteMarked();

      // start UNDO at this point. Unfortunately, this results in 2 UNDO actions, since DeleteMarked is
      // creating an own one. However, if we'd move it before DeleteMarked, Writer does not really like
      // this ... :(
      // #i31038#
      {

          // initialize UNDO
          OUString aUndoStr;
          if ( m_arrCurrentSelection.size() == 1 )
          {
              aUndoStr = SvxResId(RID_STR_UNDO_CONTAINER_REMOVEreinterpret_cast<char const *>("RID_STR_UNDO_CONTAINER_REMOVE"
 "\004" u8"Delete #"));
              if (m_nFormsSelected)
                  aUndoStr = aUndoStr.replaceFirst( "#", SvxResId( RID_STR_FORMreinterpret_cast<char const *>("RID_STR_FORM" "\004" u8"Form"
) ) );
              else
                  // it must be a control (else the root would be selected, but it cannot be deleted)
                  aUndoStr = aUndoStr.replaceFirst( "#", SvxResId( RID_STR_CONTROLreinterpret_cast<char const *>("RID_STR_CONTROL" "\004"
 u8"Control") ) );
          }
          else
          {
              aUndoStr = SvxResId(RID_STR_UNDO_CONTAINER_REMOVE_MULTIPLEreinterpret_cast<char const *>("RID_STR_UNDO_CONTAINER_REMOVE_MULTIPLE"
 "\004" u8"Delete # objects"));
              aUndoStr = aUndoStr.replaceFirst( "#", OUString::number( m_arrCurrentSelection.size() ) );
          }
          pFormModel->BegUndo(aUndoStr);
      }

      // remove remaining structure
      for (const auto& rpSelection : m_arrCurrentSelection)
      {
          FmEntryData* pCurrent = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*rpSelection).toInt64());

          // if the entry still has children, we skipped deletion of one of those children.
          // This may for instance be because the shape is in a hidden layer, where we're unable
          // to remove it
          if ( pCurrent->GetChildList()->size() )
              continue;

          // one remaining subtile problem, before deleting it : if it's a form and the shell
          // knows it as CurrentObject, I have to tell it something else
          if (dynamic_cast<const FmFormData*>( pCurrent) !=  nullptr)
          {
              Reference< XForm >  xCurrentForm( static_cast< FmFormData* >( pCurrent )->GetFormIface() );
              if (pFormShell->GetImpl()->getCurrentForm_Lock() == xCurrentForm)  // shell knows form to be deleted ?
                  pFormShell->GetImpl()->forgetCurrentForm_Lock();                 // -> take away ...
          }
          GetNavModel()->Remove(pCurrent, true);
      }
      pFormModel->EndUndo();
  }


  void NavigatorTree::CollectSelectionData(SELDATA_ITEMS sdiHow)
  {
      DBG_ASSERT(sdiHow != SDI_DIRTY, "NavigatorTree::CollectSelectionData : ever thought about your parameter ? DIRTY ?")do { if (true && (!(sdiHow != SDI_DIRTY))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1703" ": "), "%s", "NavigatorTree::CollectSelectionData : ever thought about your parameter ? DIRTY ?"
); } } while (false);
      if (sdiHow == m_sdiState)
          return;

      m_arrCurrentSelection.clear();
      m_nFormsSelected = m_nControlsSelected = m_nHiddenControls = 0;
      m_bRootSelected = false;

      m_xTreeView->selected_foreach([this, sdiHow](weld::TreeIter& rSelectionLoop){
          // count different elements
          if (m_xTreeView->iter_compare(rSelectionLoop, *m_xRootEntry) == 0)
              m_bRootSelected = true;
          else
          {
              if (IsFormEntry(rSelectionLoop))
                  ++m_nFormsSelected;
              else
              {
                  ++m_nControlsSelected;
                  if (IsHiddenControl(reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(rSelectionLoop).toInt64())))
                      ++m_nHiddenControls;
              }
          }

          if (sdiHow == SDI_NORMALIZED)
          {
              // don't take something with a selected ancestor
              if (m_xTreeView->iter_compare(rSelectionLoop, *m_xRootEntry) == 0)
                  m_arrCurrentSelection.emplace(m_xTreeView->make_iterator(&rSelectionLoop));
              else
              {
                  std::unique_ptr<weld::TreeIter> xParentLoop(m_xTreeView->make_iterator(&rSelectionLoop));
                  bool bParentLoop = m_xTreeView->iter_parent(*xParentLoop);
                  while (bParentLoop)
                  {
                      // actually i would have to test, if parent is part of m_arr_CurrentSelection ...
                      // but if it's selected, then it's in m_arrCurrentSelection
                      // or one of its ancestors, which was selected earlier.
                      // In both cases IsSelected is enough
                      if (m_xTreeView->is_selected(*xParentLoop))
                          break;
                      else
                      {
                          if (m_xTreeView->iter_compare(*xParentLoop, *m_xRootEntry) == 0)
                          {
                              // until root (exclusive), there was no selected parent -> entry belongs to normalized list
                              m_arrCurrentSelection.emplace(m_xTreeView->make_iterator(&rSelectionLoop));
                              break;
                          }
                          else
                              bParentLoop = m_xTreeView->iter_parent(*xParentLoop);
                      }
                  }
              }
          }
          else if (sdiHow == SDI_NORMALIZED_FORMARK)
          {
              std::unique_ptr<weld::TreeIter> xParent(m_xTreeView->make_iterator(&rSelectionLoop));
              bool bParent = m_xTreeView->iter_parent(*xParent);
              if (!bParent || !m_xTreeView->is_selected(*xParent) || IsFormEntry(rSelectionLoop))
                  m_arrCurrentSelection.emplace(m_xTreeView->make_iterator(&rSelectionLoop));
          }
          else
              m_arrCurrentSelection.emplace(m_xTreeView->make_iterator(&rSelectionLoop));

          return false;
      });

      m_sdiState = sdiHow;
  }

  void NavigatorTree::SynchronizeSelection(FmEntryDataArray& arredToSelect)
  {
      LockSelectionHandling();
      if (arredToSelect.empty())
      {
          m_xTreeView->unselect_all();
      }
      else
      {
          // compare current selection with requested SelectList
          m_xTreeView->selected_foreach([this, &arredToSelect](weld::TreeIter& rSelection) {
              FmEntryData* pCurrent = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(rSelection).toInt64());
              if (pCurrent != nullptr)
              {
                  FmEntryDataArray::iterator it = arredToSelect.find(pCurrent);
                  if ( it != arredToSelect.end() )
                  {   // entry already selected, but also in SelectList
                      // remove it from there
                      arredToSelect.erase(it);
                  } else
                  {   // entry selected, but not in SelectList -> remove selection
                      m_xTreeView->unselect(rSelection);
                      // make it visible (maybe it's the only modification i do in this handler
                      // so you should see it
                      m_xTreeView->scroll_to_row(rSelection);
                  }
              }
              else
                  m_xTreeView->unselect(rSelection);

              return false;
          });

          // now SelectList contains only entries, which have to be selected
          // two possibilities : 1) run through SelectList, get SvTreeListEntry for every entry and select it (is more intuitive)
          // 2) run through my SvLBoxEntries and select those, i can find in the SelectList
          // 1) needs =(k*n) (k=length of SelectList, n=number of entries),
          // plus the fact, that FindEntry uses extensive IsEqualWithoutChilden instead of comparing pointer to UserData
          // 2) needs =(n*log k), duplicates some code from FindEntry
          // This may be a frequently used code ( at every change in mark of the view!),
          // so i use latter one
          m_xTreeView->all_foreach([this, &arredToSelect](weld::TreeIter& rLoop){
              FmEntryData* pCurEntryData = reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(rLoop).toInt64());
              FmEntryDataArray::iterator it = arredToSelect.find(pCurEntryData);
              if (it != arredToSelect.end())
              {
                  m_xTreeView->select(rLoop);
                  m_xTreeView->scroll_to_row(rLoop);
              }

              return false;
          });
      }
      UnlockSelectionHandling();
  }


  void NavigatorTree::SynchronizeSelection()
  {
      // shell and view
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if(!pFormShell) return;

      FmFormView* pFormView = pFormShell->GetFormView();
      if (!pFormView) return;

      GetNavModel()->BroadcastMarkedObjects(pFormView->GetMarkedObjectList());
  }


  void NavigatorTree::SynchronizeMarkList()
  {
      // i'll need this shell
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if (!pFormShell) return;

      CollectSelectionData(SDI_NORMALIZED_FORMARK);

      // the view shouldn't notify now if MarkList changed
      pFormShell->GetImpl()->EnableTrackProperties_Lock(false);

      UnmarkAllViewObj();

      for (auto& rSelectionLoop : m_arrCurrentSelection)
      {
          // When form selection, mark all controls of form
          if (IsFormEntry(*rSelectionLoop) && m_xTreeView->iter_compare(*rSelectionLoop, *m_xRootEntry) != 0)
              MarkViewObj(reinterpret_cast<FmFormData*>(m_xTreeView->get_id(*rSelectionLoop).toInt64()), false/*deep*/);

          // When control selection, mark Control-SdrObjects
          else if (IsFormComponentEntry(*rSelectionLoop))
          {
              FmControlData* pControlData = reinterpret_cast<FmControlData*>(m_xTreeView->get_id(*rSelectionLoop).toInt64());
              if (pControlData)
              {

                  // When HiddenControl no object can be selected
                  Reference< XFormComponent >  xFormComponent( pControlData->GetFormComponent());
                  if (!xFormComponent.is())
                      continue;
                  Reference< XPropertySet >  xSet(xFormComponent, UNO_QUERY);
                  if (!xSet.is())
                      continue;

                  sal_uInt16 nClassId = ::comphelper::getINT16(xSet->getPropertyValue(FM_PROP_CLASSID"ClassId"));
                  if (nClassId != FormComponentType::HIDDENCONTROL)
                      MarkViewObj(pControlData);
              }
          }
      }

      // if PropertyBrowser is open, I have to adopt it according to my selection
      // (Not as MarkList of view : if a form is selected, all belonging controls are selected in the view
      // but of course i want to see the form-properties
      ShowSelectionProperties();

      // reset flag at view
      pFormShell->GetImpl()->EnableTrackProperties_Lock(true);

      // if exactly one form is selected now, shell should notice it as CurrentForm
      // (if selection handling isn't locked, view cares about it in MarkListHasChanged
      // but mechanism doesn't work, if form is empty for example
      if ((m_arrCurrentSelection.size() != 1) || (m_nFormsSelected != 1))
          return;

      std::unique_ptr<weld::TreeIter> xSelected(m_xTreeView->make_iterator());
      if (!m_xTreeView->get_selected(xSelected.get()))
          xSelected.reset();
      FmFormData* pSingleSelectionData = xSelected ? dynamic_cast<FmFormData*>(reinterpret_cast<FmEntryData*>(m_xTreeView->get_id(*xSelected).toInt64()))
                                                   : nullptr;
      DBG_ASSERT( pSingleSelectionData, "NavigatorTree::SynchronizeMarkList: invalid selected form!" )do { if (true && (!(pSingleSelectionData))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.tools"), ("/home/maarten/src/libreoffice/core/svx/source/form/navigatortree.cxx"
 ":" "1904" ": "), "%s", "NavigatorTree::SynchronizeMarkList: invalid selected form!"
); } } while (false);
      if ( pSingleSelectionData )
      {
          InterfaceBag aSelection;
          aSelection.insert( Reference< XInterface >( pSingleSelectionData->GetFormIface(), UNO_QUERY ) );
          pFormShell->GetImpl()->setCurrentSelection_Lock(aSelection);
      }
  }

  bool NavigatorTree::IsHiddenControl(FmEntryData const * pEntryData)
  {
      if (pEntryData == nullptr) return false;
38
←
Taking true branch→
39
←
Returning zero, which participates in a condition later→

      Reference< XPropertySet > xProperties( pEntryData->GetPropertySet() );
      if (::comphelper::hasProperty(FM_PROP_CLASSID"ClassId", xProperties))
      {
          Any aClassID = xProperties->getPropertyValue( FM_PROP_CLASSID"ClassId" );
          return (::comphelper::getINT16(aClassID) == FormComponentType::HIDDENCONTROL);
      }
      return false;
  }

  void NavigatorTree::UnmarkAllViewObj()
  {
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if( !pFormShell )
          return;
      FmFormView* pFormView = pFormShell->GetFormView();
      pFormView->UnMarkAll();
  }

  void NavigatorTree::MarkViewObj(FmFormData const * pFormData, bool bDeep )
  {
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if( !pFormShell )
          return;

      // first collect all sdrobjects
      ::std::set< Reference< XFormComponent > > aObjects;
      CollectObjects(pFormData,bDeep,aObjects);


      // find and select appropriate SdrObj in page
      FmFormView*     pFormView       = pFormShell->GetFormView();
      SdrPageView*    pPageView       = pFormView->GetSdrPageView();
      SdrPage*        pPage           = pPageView->GetPage();
      //FmFormPage*     pFormPage       = dynamic_cast< FmFormPage* >( pPage );

      SdrObjListIter aIter( pPage );
      while ( aIter.IsMore() )
      {
          SdrObject* pSdrObject = aIter.Next();
          FmFormObj* pFormObject = FmFormObj::GetFormObject( pSdrObject );
          if ( !pFormObject )
              continue;

          Reference< XFormComponent > xControlModel( pFormObject->GetUnoControlModel(),UNO_QUERY );
          if ( xControlModel.is() && aObjects.find(xControlModel) != aObjects.end() && !pFormView->IsObjMarked( pSdrObject ) )
          {
              // unfortunately, the writer doesn't like marking an already-marked object, again, so reset the mark first
              pFormView->MarkObj( pSdrObject, pPageView );
          }
      } // while ( aIter.IsMore() )
      // make the mark visible
      ::tools::Rectangle aMarkRect( pFormView->GetAllMarkedRect());
      for ( sal_uInt32 i = 0; i < pFormView->PaintWindowCount(); ++i )
      {
          SdrPaintWindow* pPaintWindow = pFormView->GetPaintWindow( i );
          OutputDevice& rOutDev = pPaintWindow->GetOutputDevice();
          if ( ( OUTDEV_WINDOW == rOutDev.GetOutDevType() ) && !aMarkRect.IsEmpty() )
          {
              pFormView->MakeVisible( aMarkRect, static_cast<vcl::Window&>(rOutDev) );
          }
      } // for ( sal_uInt32 i = 0; i < pFormView->PaintWindowCount(); ++i )
  }

  void NavigatorTree::CollectObjects(FmFormData const * pFormData, bool bDeep, ::std::set< Reference< XFormComponent > >& _rObjects)
  {
      FmEntryDataList* pChildList = pFormData->GetChildList();
      FmControlData* pControlData;
      for( size_t i = 0; i < pChildList->size(); ++i )
      {
          FmEntryData* pEntryData = pChildList->at( i );
          if( dynamic_cast<const FmControlData*>( pEntryData) !=  nullptr )
          {
              pControlData = static_cast<FmControlData*>(pEntryData);
              _rObjects.insert(pControlData->GetFormComponent());
          } // if( dynamic_cast<const FmControlData*>( pEntryData) !=  nullptr )
          else if (bDeep && (dynamic_cast<const FmFormData*>( pEntryData) !=  nullptr))
              CollectObjects(static_cast<FmFormData*>(pEntryData), bDeep, _rObjects);
      } // for( sal_uInt32 i=0; i<pChildList->Count(); i++ )
  }

  void NavigatorTree::MarkViewObj( FmControlData const * pControlData)
  {
      if( !pControlData )
          return;
      FmFormShell* pFormShell = GetNavModel()->GetFormShell();
      if( !pFormShell )
          return;


      // find and select appropriate SdrObj
      FmFormView*     pFormView       = pFormShell->GetFormView();
      Reference< XFormComponent >  xFormComponent( pControlData->GetFormComponent());
      SdrPageView*    pPageView       = pFormView->GetSdrPageView();
      SdrPage*        pPage           = pPageView->GetPage();

      bool bPaint = false;
      SdrObjListIter aIter( pPage );
      while ( aIter.IsMore() )
      {
          SdrObject* pSdrObject = aIter.Next();
          FmFormObj* pFormObject = FmFormObj::GetFormObject( pSdrObject );
          if ( !pFormObject )
              continue;

          Reference< XInterface > xControlModel( pFormObject->GetUnoControlModel() );
          if ( xControlModel != xFormComponent )
              continue;

          // mark the object
          if ( !pFormView->IsObjMarked( pSdrObject ) )
              // unfortunately, the writer doesn't like marking an already-marked object, again, so reset the mark first
              pFormView->MarkObj( pSdrObject, pPageView );

          bPaint = true;

      } // while ( aIter.IsMore() )
      if ( !bPaint )
          return;

      // make the mark visible
      ::tools::Rectangle aMarkRect( pFormView->GetAllMarkedRect());
      for ( sal_uInt32 i = 0; i < pFormView->PaintWindowCount(); ++i )
      {
          SdrPaintWindow* pPaintWindow = pFormView->GetPaintWindow( i );
          OutputDevice& rOutDev = pPaintWindow->GetOutputDevice();
          if ( OUTDEV_WINDOW == rOutDev.GetOutDevType() )
          {
              pFormView->MakeVisible( aMarkRect, static_cast<vcl::Window&>(rOutDev) );
          }
      } // for ( sal_uInt32 i = 0; i < pFormView->PaintWindowCount(); ++i )
  }


2050}


2053/* vim:set shiftwidth=4 softtabstop=4 expandtab: */

←

/usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/bits/stl_iterator.h

→

1// Iterators -*- C++ -*-

3// Copyright (C) 2001-2020 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
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

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.

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/>.

25/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996-1998
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*/

51/** @file bits/stl_iterator.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{iterator}
*
*  This file implements reverse_iterator, back_insert_iterator,
*  front_insert_iterator, insert_iterator, __normal_iterator, and their
*  supporting functions and overloaded operators.
*/

60#ifndef _STL_ITERATOR_H1
61#define _STL_ITERATOR_H1 1

63#include <bits/cpp_type_traits.h>
64#include <ext/type_traits.h>
65#include <bits/move.h>
66#include <bits/ptr_traits.h>

68#if __cplusplus201703L >= 201103L
69# include <type_traits>
70#endif

72#if __cplusplus201703L > 201703L
73# define __cpp_lib_array_constexpr201803L 201811L
74# define __cpp_lib_constexpr_iterator 201811L
75#elif __cplusplus201703L == 201703L
76# define __cpp_lib_array_constexpr201803L 201803L
77#endif

79#if __cplusplus201703L > 201703L
80# include <compare>
81# include <new>
82# include <bits/iterator_concepts.h>
83#endif

85namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
86{
87_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
 * @addtogroup iterators
 * @{
 */

94#if __cplusplus201703L > 201703L && __cpp_lib_concepts
namespace __detail
{
  // Weaken iterator_category _Cat to _Limit if it is derived from that,
  // otherwise use _Otherwise.
  template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
    using __clamp_iter_cat
= conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
}
103#endif

// 24.4.1 Reverse iterators
/**
 *  Bidirectional and random access iterators have corresponding reverse
 *  %iterator adaptors that iterate through the data structure in the
 *  opposite direction.  They have the same signatures as the corresponding
 *  iterators.  The fundamental relation between a reverse %iterator and its
 *  corresponding %iterator @c i is established by the identity:
 *  @code
 *      &*(reverse_iterator(i)) == &*(i - 1)
 *  @endcode
 *
 *  <em>This mapping is dictated by the fact that while there is always a
 *  pointer past the end of an array, there might not be a valid pointer
 *  before the beginning of an array.</em> [24.4.1]/1,2
 *
 *  Reverse iterators can be tricky and surprising at first.  Their
 *  semantics make sense, however, and the trickiness is a side effect of
 *  the requirement that the iterators must be safe.
*/
template<typename _Iterator>
  class reverse_iterator
  : public iterator<typename iterator_traits<_Iterator>::iterator_category,
      typename iterator_traits<_Iterator>::value_type,
      typename iterator_traits<_Iterator>::difference_type,
      typename iterator_traits<_Iterator>::pointer,
                    typename iterator_traits<_Iterator>::reference>
  {
  protected:
    _Iterator current;

    typedef iterator_traits<_Iterator>		__traits_type;

  public:
    typedef _Iterator					iterator_type;
    typedef typename __traits_type::difference_type	difference_type;
    typedef typename __traits_type::pointer		pointer;
    typedef typename __traits_type::reference		reference;

143#if __cplusplus201703L > 201703L && __cpp_lib_concepts
    using iterator_concept
= conditional_t<random_access_iterator<_Iterator>,
	random_access_iterator_tag,
	bidirectional_iterator_tag>;
    using iterator_category
= __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
		     random_access_iterator_tag>;
151#endif

    /**
     *  The default constructor value-initializes member @p current.
     *  If it is a pointer, that means it is zero-initialized.
    */
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 235 No specification of default ctor for reverse_iterator
    // 1012. reverse_iterator default ctor should value initialize
    _GLIBCXX17_CONSTEXPRconstexpr
    reverse_iterator() : current() { }

    /**
     *  This %iterator will move in the opposite direction that @p x does.
    */
    explicit _GLIBCXX17_CONSTEXPRconstexpr
    reverse_iterator(iterator_type __x) : current(__x) { }

    /**
     *  The copy constructor is normal.
    */
    _GLIBCXX17_CONSTEXPRconstexpr
    reverse_iterator(const reverse_iterator& __x)
    : current(__x.current) { }

176#if __cplusplus201703L >= 201103L
    reverse_iterator& operator=(const reverse_iterator&) = default;
178#endif

    /**
     *  A %reverse_iterator across other types can be copied if the
     *  underlying %iterator can be converted to the type of @c current.
    */
    template<typename _Iter>
_GLIBCXX17_CONSTEXPRconstexpr
      reverse_iterator(const reverse_iterator<_Iter>& __x)
: current(__x.base()) { }

    /**
     *  @return  @c current, the %iterator used for underlying work.
    */
    _GLIBCXX17_CONSTEXPRconstexpr iterator_type
    base() const
    { return current; }

    /**
     *  @return  A reference to the value at @c --current
     *
     *  This requires that @c --current is dereferenceable.
     *
     *  @warning This implementation requires that for an iterator of the
     *           underlying iterator type, @c x, a reference obtained by
     *           @c *x remains valid after @c x has been modified or
     *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
    */
    _GLIBCXX17_CONSTEXPRconstexpr reference
    operator*() const
    {
_Iterator __tmp = current;
return *--__tmp;
    }

    /**
     *  @return  A pointer to the value at @c --current
     *
     *  This requires that @c --current is dereferenceable.
    */
    _GLIBCXX17_CONSTEXPRconstexpr pointer
    operator->() const
220#if __cplusplus201703L > 201703L && __cpp_concepts >= 201907L
    requires is_pointer_v<_Iterator>
|| requires(const _Iterator __i) { __i.operator->(); }
223#endif
    {
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 1052. operator-> should also support smart pointers
_Iterator __tmp = current;
--__tmp;
return _S_to_pointer(__tmp);
    }

    /**
     *  @return  @c *this
     *
     *  Decrements the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
    operator++()
    {
--current;
return *this;
    }

    /**
     *  @return  The original value of @c *this
     *
     *  Decrements the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
    operator++(int)
    {
reverse_iterator __tmp = *this;
--current;
return __tmp;
    }

    /**
     *  @return  @c *this
     *
     *  Increments the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
    operator--()
    {
++current;
return *this;
    }

    /**
     *  @return  A reverse_iterator with the previous value of @c *this
     *
     *  Increments the underlying iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
    operator--(int)
    {
reverse_iterator __tmp = *this;
++current;
return __tmp;
    }

    /**
     *  @return  A reverse_iterator that refers to @c current - @a __n
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
    operator+(difference_type __n) const
    { return reverse_iterator(current - __n); }

    /**
     *  @return  *this
     *
     *  Moves the underlying iterator backwards @a __n steps.
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
    operator+=(difference_type __n)
    {
current -= __n;
return *this;
    }

    /**
     *  @return  A reverse_iterator that refers to @c current - @a __n
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator
    operator-(difference_type __n) const
    { return reverse_iterator(current + __n); }

    /**
     *  @return  *this
     *
     *  Moves the underlying iterator forwards @a __n steps.
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator&
    operator-=(difference_type __n)
    {
current += __n;
return *this;
    }

    /**
     *  @return  The value at @c current - @a __n - 1
     *
     *  The underlying iterator must be a Random Access Iterator.
    */
    _GLIBCXX17_CONSTEXPRconstexpr reference
    operator[](difference_type __n) const
    { return *(*this + __n); }

  private:
    template<typename _Tp>
static _GLIBCXX17_CONSTEXPRconstexpr _Tp*
_S_to_pointer(_Tp* __p)
      { return __p; }

    template<typename _Tp>
static _GLIBCXX17_CONSTEXPRconstexpr pointer
_S_to_pointer(_Tp __t)
      { return __t.operator->(); }
  };

//@{
/**
 *  @param  __x  A %reverse_iterator.
 *  @param  __y  A %reverse_iterator.
 *  @return  A simple bool.
 *
 *  Reverse iterators forward comparisons to their underlying base()
 *  iterators.
 *
*/
357#if __cplusplus201703L <= 201703L || ! defined __cpp_lib_concepts
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator==(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return __x.base() == __y.base(); }
24
←
Calling 'operator=='→
27
←
Returning from 'operator=='→
28
←
Returning zero, which participates in a condition later→

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y.base() < __x.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator!=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__x == __y); }
23
←
Calling 'operator==<std::_Rb_tree_const_iterator<std::unique_ptr<weld::TreeIter, std::default_delete<weld::TreeIter>>>>'→
29
←
Returning from 'operator==<std::_Rb_tree_const_iterator<std::unique_ptr<weld::TreeIter, std::default_delete<weld::TreeIter>>>>'→
30
←
Returning the value 1, which participates in a condition later→

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y < __x; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__y < __x); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>=(const reverse_iterator<_Iterator>& __x,
      const reverse_iterator<_Iterator>& __y)
  { return !(__x < __y); }

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 280. Comparison of reverse_iterator to const reverse_iterator.
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator==(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return __x.base() == __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y.base() < __x.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator!=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__x == __y); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y < __x; }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__y < __x); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  { return !(__x < __y); }
431#else // C++20
template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator==(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
  { return __x.base() == __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator!=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
  { return __x.base() != __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator<(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
  { return __x.base() > __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator>(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
  { return __x.base() < __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator<=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
  { return __x.base() >= __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  constexpr bool
  operator>=(const reverse_iterator<_IteratorL>& __x,
      const reverse_iterator<_IteratorR>& __y)
  requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
  { return __x.base() <= __y.base(); }

template<typename _IteratorL,
  three_way_comparable_with<_IteratorL> _IteratorR>
  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
  operator<=>(const reverse_iterator<_IteratorL>& __x,
const reverse_iterator<_IteratorR>& __y)
  { return __y.base() <=> __x.base(); }
480#endif // C++20
//@}

483#if __cplusplus201703L < 201103L
template<typename _Iterator>
  inline typename reverse_iterator<_Iterator>::difference_type
  operator-(const reverse_iterator<_Iterator>& __x,
     const reverse_iterator<_Iterator>& __y)
  { return __y.base() - __x.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline typename reverse_iterator<_IteratorL>::difference_type
  operator-(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  { return __y.base() - __x.base(); }
495#else
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 685. reverse_iterator/move_iterator difference has invalid signatures
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr auto
  operator-(const reverse_iterator<_IteratorL>& __x,
     const reverse_iterator<_IteratorR>& __y)
  -> decltype(__y.base() - __x.base())
  { return __y.base() - __x.base(); }
504#endif

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator<_Iterator>
  operator+(typename reverse_iterator<_Iterator>::difference_type __n,
     const reverse_iterator<_Iterator>& __x)
  { return reverse_iterator<_Iterator>(__x.base() - __n); }

512#if __cplusplus201703L >= 201103L
// Same as C++14 make_reverse_iterator but used in C++11 mode too.
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator<_Iterator>
  __make_reverse_iterator(_Iterator __i)
  { return reverse_iterator<_Iterator>(__i); }

519# if __cplusplus201703L >= 201402L
520#  define __cpp_lib_make_reverse_iterator201402 201402

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 2285. make_reverse_iterator
/// Generator function for reverse_iterator.
template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr reverse_iterator<_Iterator>
  make_reverse_iterator(_Iterator __i)
  { return reverse_iterator<_Iterator>(__i); }

530#  if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
template<typename _Iterator1, typename _Iterator2>
  requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
  inline constexpr bool
  disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
	       reverse_iterator<_Iterator2>> = true;
536#  endif // C++20
537# endif // C++14

template<typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  auto
  __niter_base(reverse_iterator<_Iterator> __it)
  -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
  { return __make_reverse_iterator(__niter_base(__it.base())); }

template<typename _Iterator>
  struct __is_move_iterator<reverse_iterator<_Iterator> >
    : __is_move_iterator<_Iterator>
  { };

template<typename _Iterator>
  _GLIBCXX20_CONSTEXPR
  auto
  __miter_base(reverse_iterator<_Iterator> __it)
  -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
  { return __make_reverse_iterator(__miter_base(__it.base())); }
557#endif // C++11

// 24.4.2.2.1 back_insert_iterator
/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator appends it to the container using
 *  push_back.
 *
 *  Tip:  Using the back_inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class back_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
  protected:
    _Container* container;

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;
580#if __cplusplus201703L > 201703L
    using difference_type = ptrdiff_t;

    constexpr back_insert_iterator() noexcept : container(nullptr) { }
584#endif

    /// The only way to create this %iterator is with a container.
    explicit _GLIBCXX20_CONSTEXPR
    back_insert_iterator(_Container& __x)
    : container(std::__addressof(__x)) { }

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator doesn't really have a @a position in the
     *  container (you can think of the position as being permanently at
     *  the end, if you like).  Assigning a value to the %iterator will
     *  always append the value to the end of the container.
    */
602#if __cplusplus201703L < 201103L
    back_insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
container->push_back(__value);
return *this;
    }
609#else
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
container->push_back(__value);
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
container->push_back(std::move(__value));
return *this;
    }
625#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    back_insert_iterator
    operator++(int)
    { return *this; }
  };

/**
 *  @param  __x  A container of arbitrary type.
 *  @return  An instance of back_insert_iterator working on @p __x.
 *
 *  This wrapper function helps in creating back_insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
template<typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline back_insert_iterator<_Container>
  back_inserter(_Container& __x)
  { return back_insert_iterator<_Container>(__x); }

/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator prepends it to the container using
 *  push_front.
 *
 *  Tip:  Using the front_inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class front_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
  protected:
    _Container* container;

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;
683#if __cplusplus201703L > 201703L
    using difference_type = ptrdiff_t;

    constexpr front_insert_iterator() noexcept : container(nullptr) { }
687#endif

    /// The only way to create this %iterator is with a container.
    explicit _GLIBCXX20_CONSTEXPR
    front_insert_iterator(_Container& __x)
    : container(std::__addressof(__x)) { }

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator doesn't really have a @a position in the
     *  container (you can think of the position as being permanently at
     *  the front, if you like).  Assigning a value to the %iterator will
     *  always prepend the value to the front of the container.
    */
705#if __cplusplus201703L < 201103L
    front_insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
container->push_front(__value);
return *this;
    }
712#else
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
container->push_front(__value);
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
container->push_front(std::move(__value));
return *this;
    }
728#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    front_insert_iterator
    operator++(int)
    { return *this; }
  };

/**
 *  @param  __x  A container of arbitrary type.
 *  @return  An instance of front_insert_iterator working on @p x.
 *
 *  This wrapper function helps in creating front_insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
template<typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline front_insert_iterator<_Container>
  front_inserter(_Container& __x)
  { return front_insert_iterator<_Container>(__x); }

/**
 *  @brief  Turns assignment into insertion.
 *
 *  These are output iterators, constructed from a container-of-T.
 *  Assigning a T to the iterator inserts it in the container at the
 *  %iterator's position, rather than overwriting the value at that
 *  position.
 *
 *  (Sequences will actually insert a @e copy of the value before the
 *  %iterator's position.)
 *
 *  Tip:  Using the inserter function to create these iterators can
 *  save typing.
*/
template<typename _Container>
  class insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
  {
784#if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
    using _Iter = std::__detail::__range_iter_t<_Container>;

  protected:
    _Container* container = nullptr;
    _Iter iter = _Iter();
790#else
    typedef typename _Container::iterator		_Iter;

  protected:
    _Container* container;
    _Iter iter;
796#endif

  public:
    /// A nested typedef for the type of whatever container you used.
    typedef _Container          container_type;

802#if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
    using difference_type = ptrdiff_t;

    insert_iterator() = default;
806#endif

    /**
     *  The only way to create this %iterator is with a container and an
     *  initial position (a normal %iterator into the container).
    */
    _GLIBCXX20_CONSTEXPR
    insert_iterator(_Container& __x, _Iter __i)
    : container(std::__addressof(__x)), iter(__i) {}

    /**
     *  @param  __value  An instance of whatever type
     *                 container_type::const_reference is; presumably a
     *                 reference-to-const T for container<T>.
     *  @return  This %iterator, for chained operations.
     *
     *  This kind of %iterator maintains its own position in the
     *  container.  Assigning a value to the %iterator will insert the
     *  value into the container at the place before the %iterator.
     *
     *  The position is maintained such that subsequent assignments will
     *  insert values immediately after one another.  For example,
     *  @code
     *     // vector v contains A and Z
     *
     *     insert_iterator i (v, ++v.begin());
     *     i = 1;
     *     i = 2;
     *     i = 3;
     *
     *     // vector v contains A, 1, 2, 3, and Z
     *  @endcode
    */
839#if __cplusplus201703L < 201103L
    insert_iterator&
    operator=(typename _Container::const_reference __value)
    {
iter = container->insert(iter, __value);
++iter;
return *this;
    }
847#else
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator=(const typename _Container::value_type& __value)
    {
iter = container->insert(iter, __value);
++iter;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator=(typename _Container::value_type&& __value)
    {
iter = container->insert(iter, std::move(__value));
++iter;
return *this;
    }
865#endif

    /// Simply returns *this.
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator*()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator++()
    { return *this; }

    /// Simply returns *this.  (This %iterator does not @a move.)
    _GLIBCXX20_CONSTEXPR
    insert_iterator&
    operator++(int)
    { return *this; }
  };

/**
 *  @param __x  A container of arbitrary type.
 *  @param __i  An iterator into the container.
 *  @return  An instance of insert_iterator working on @p __x.
 *
 *  This wrapper function helps in creating insert_iterator instances.
 *  Typing the name of the %iterator requires knowing the precise full
 *  type of the container, which can be tedious and impedes generic
 *  programming.  Using this function lets you take advantage of automatic
 *  template parameter deduction, making the compiler match the correct
 *  types for you.
*/
898#if __cplusplus201703L > 201703L && defined __cpp_lib_concepts
template<typename _Container>
  constexpr insert_iterator<_Container>
  inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
  { return insert_iterator<_Container>(__x, __i); }
903#else
template<typename _Container, typename _Iterator>
  inline insert_iterator<_Container>
  inserter(_Container& __x, _Iterator __i)
  {
    return insert_iterator<_Container>(__x,
			 typename _Container::iterator(__i));
  }
911#endif

// @} group iterators

915_GLIBCXX_END_NAMESPACE_VERSION
916} // namespace

918namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
919{
920_GLIBCXX_BEGIN_NAMESPACE_VERSION

// This iterator adapter is @a normal in the sense that it does not
// change the semantics of any of the operators of its iterator
// parameter.  Its primary purpose is to convert an iterator that is
// not a class, e.g. a pointer, into an iterator that is a class.
// The _Container parameter exists solely so that different containers
// using this template can instantiate different types, even if the
// _Iterator parameter is the same.
template<typename _Iterator, typename _Container>
  class __normal_iterator
  {
  protected:
    _Iterator _M_current;

    typedef std::iterator_traits<_Iterator>		__traits_type;

  public:
    typedef _Iterator					iterator_type;
    typedef typename __traits_type::iterator_category iterator_category;
    typedef typename __traits_type::value_type  	value_type;
    typedef typename __traits_type::difference_type 	difference_type;
    typedef typename __traits_type::reference 	reference;
    typedef typename __traits_type::pointer   	pointer;

945#if __cplusplus201703L > 201703L && __cpp_lib_concepts
    using iterator_concept = std::__detail::__iter_concept<_Iterator>;
947#endif

    _GLIBCXX_CONSTEXPRconstexpr __normal_iterator() _GLIBCXX_NOEXCEPTnoexcept
    : _M_current(_Iterator()) { }

    explicit _GLIBCXX20_CONSTEXPR
    __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPTnoexcept
    : _M_current(__i) { }

    // Allow iterator to const_iterator conversion
    template<typename _Iter>
      _GLIBCXX20_CONSTEXPR
      __normal_iterator(const __normal_iterator<_Iter,
	  typename __enable_if<
    	       (std::__are_same<_Iter, typename _Container::pointer>::__value),
      _Container>::__type>& __i) _GLIBCXX_NOEXCEPTnoexcept
      : _M_current(__i.base()) { }

    // Forward iterator requirements
    _GLIBCXX20_CONSTEXPR
    reference
    operator*() const _GLIBCXX_NOEXCEPTnoexcept
    { return *_M_current; }

    _GLIBCXX20_CONSTEXPR
    pointer
    operator->() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator++() _GLIBCXX_NOEXCEPTnoexcept
    {
++_M_current;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator++(int) _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current++); }

    // Bidirectional iterator requirements
    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator--() _GLIBCXX_NOEXCEPTnoexcept
    {
--_M_current;
return *this;
    }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator--(int) _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current--); }

    // Random access iterator requirements
    _GLIBCXX20_CONSTEXPR
    reference
    operator[](difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current[__n]; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator+=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
    { _M_current += __n; return *this; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator+(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current + __n); }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator&
    operator-=(difference_type __n) _GLIBCXX_NOEXCEPTnoexcept
    { _M_current -= __n; return *this; }

    _GLIBCXX20_CONSTEXPR
    __normal_iterator
    operator-(difference_type __n) const _GLIBCXX_NOEXCEPTnoexcept
    { return __normal_iterator(_M_current - __n); }

    _GLIBCXX20_CONSTEXPR
    const _Iterator&
    base() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_current; }
  };

// Note: In what follows, the left- and right-hand-side iterators are
// allowed to vary in types (conceptually in cv-qualification) so that
// comparison between cv-qualified and non-cv-qualified iterators be
// valid.  However, the greedy and unfriendly operators in std::rel_ops
// will make overload resolution ambiguous (when in scope) if we don't
// provide overloads whose operands are of the same type.  Can someone
// remind me what generic programming is about? -- Gaby

1043#if __cpp_lib_three_way_comparison
template<typename _IteratorL, typename _IteratorR, typename _Container>
  requires requires (_IteratorL __lhs, _IteratorR __rhs)
  { { __lhs == __rhs } -> std::convertible_to<bool>; }
  constexpr bool
  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  noexcept(noexcept(__lhs.base() == __rhs.base()))
  { return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
  operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
const __normal_iterator<_IteratorR, _Container>& __rhs)
  noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
  { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1059#else
 // Forward iterator requirements
template<typename _IteratorL, typename _IteratorR, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() == __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() != __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() != __rhs.base(); }

// Random access iterator requirements
template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() < __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() < __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() > __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() > __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() <= __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() <= __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
  inline bool
  operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
      const __normal_iterator<_IteratorR, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() >= __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline bool
  operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
      const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() >= __rhs.base(); }
1153#endif // three-way comparison

// _GLIBCXX_RESOLVE_LIB_DEFECTS
// According to the resolution of DR179 not only the various comparison
// operators but also operator- must accept mixed iterator/const_iterator
// parameters.
template<typename _IteratorL, typename _IteratorR, typename _Container>
1160#if __cplusplus201703L >= 201103L
  // DR 685.
  _GLIBCXX20_CONSTEXPR
  inline auto
  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
  -> decltype(__lhs.base() - __rhs.base())
1167#else
  inline typename __normal_iterator<_IteratorL, _Container>::difference_type
  operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     const __normal_iterator<_IteratorR, _Container>& __rhs)
1171#endif
  { return __lhs.base() - __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline typename __normal_iterator<_Iterator, _Container>::difference_type
  operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
     const __normal_iterator<_Iterator, _Container>& __rhs)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __lhs.base() - __rhs.base(); }

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  inline __normal_iterator<_Iterator, _Container>
  operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
     __n, const __normal_iterator<_Iterator, _Container>& __i)
  _GLIBCXX_NOEXCEPTnoexcept
  { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }

1190_GLIBCXX_END_NAMESPACE_VERSION
1191} // namespace

1193namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
1194{
1195_GLIBCXX_BEGIN_NAMESPACE_VERSION

template<typename _Iterator, typename _Container>
  _GLIBCXX20_CONSTEXPR
  _Iterator
  __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
  _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)noexcept(std::is_nothrow_copy_constructible<_Iterator>::
value)
  { return __it.base(); }

1204#if __cplusplus201703L >= 201103L
/**
 * @addtogroup iterators
 * @{
 */

1210#if __cplusplus201703L > 201703L && __cpp_lib_concepts
template<semiregular _Sent>
  class move_sentinel
  {
  public:
    constexpr
    move_sentinel()
    noexcept(is_nothrow_default_constructible_v<_Sent>)
    : _M_last() { }

    constexpr explicit
    move_sentinel(_Sent __s)
    noexcept(is_nothrow_move_constructible_v<_Sent>)
    : _M_last(std::move(__s)) { }

    template<typename _S2> requires convertible_to<const _S2&, _Sent>
constexpr
move_sentinel(const move_sentinel<_S2>& __s)
noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
: _M_last(__s.base())
{ }

    template<typename _S2> requires assignable_from<_Sent&, const _S2&>
constexpr move_sentinel&
operator=(const move_sentinel<_S2>& __s)
noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
{
 _M_last = __s.base();
 return *this;
}

    constexpr _Sent
    base() const
    noexcept(is_nothrow_copy_constructible_v<_Sent>)
    { return _M_last; }

  private:
    _Sent _M_last;
  };
1249#endif // C++20

// 24.4.3  Move iterators
/**
 *  Class template move_iterator is an iterator adapter with the same
 *  behavior as the underlying iterator except that its dereference
 *  operator implicitly converts the value returned by the underlying
 *  iterator's dereference operator to an rvalue reference.  Some
 *  generic algorithms can be called with move iterators to replace
 *  copying with moving.
 */
template<typename _Iterator>
  class move_iterator
  {
    _Iterator _M_current;

    using __traits_type = iterator_traits<_Iterator>;
1266#if __cplusplus201703L > 201703L && __cpp_lib_concepts
    using __base_cat = typename __traits_type::iterator_category;
1268#else
    using __base_ref = typename __traits_type::reference;
1270#endif

  public:
    using iterator_type = _Iterator;

1275#if __cplusplus201703L > 201703L && __cpp_lib_concepts
    using iterator_concept = input_iterator_tag;
    using iterator_category
= __detail::__clamp_iter_cat<__base_cat, random_access_iterator_tag>;
    using value_type = iter_value_t<_Iterator>;
    using difference_type = iter_difference_t<_Iterator>;
    using pointer = _Iterator;
    using reference = iter_rvalue_reference_t<_Iterator>;
1283#else
    typedef typename __traits_type::iterator_category iterator_category;
    typedef typename __traits_type::value_type  	value_type;
    typedef typename __traits_type::difference_type	difference_type;
    // NB: DR 680.
    typedef _Iterator					pointer;
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2106. move_iterator wrapping iterators returning prvalues
    typedef typename conditional<is_reference<__base_ref>::value,
	 typename remove_reference<__base_ref>::type&&,
	 __base_ref>::type		reference;
1294#endif

    _GLIBCXX17_CONSTEXPRconstexpr
    move_iterator()
    : _M_current() { }

    explicit _GLIBCXX17_CONSTEXPRconstexpr
    move_iterator(iterator_type __i)
    : _M_current(std::move(__i)) { }

    template<typename _Iter>
_GLIBCXX17_CONSTEXPRconstexpr
move_iterator(const move_iterator<_Iter>& __i)
: _M_current(__i.base()) { }

1309#if __cplusplus201703L <= 201703L
    _GLIBCXX17_CONSTEXPRconstexpr iterator_type
    base() const
    { return _M_current; }
1313#else
    constexpr iterator_type
    base() const &
1316#if __cpp_lib_concepts
requires copy_constructible<iterator_type>
1318#endif
    { return _M_current; }

    constexpr iterator_type
    base() &&
    { return std::move(_M_current); }
1324#endif

    _GLIBCXX17_CONSTEXPRconstexpr reference
    operator*() const
    { return static_cast<reference>(*_M_current); }

    _GLIBCXX17_CONSTEXPRconstexpr pointer
    operator->() const
    { return _M_current; }

    _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
    operator++()
    {
++_M_current;
return *this;
    }

    _GLIBCXX17_CONSTEXPRconstexpr move_iterator
    operator++(int)
    {
move_iterator __tmp = *this;
++_M_current;
return __tmp;
    }

1349#if __cpp_lib_concepts
    constexpr void
    operator++(int) requires (!forward_iterator<_Iterator>)
    { ++_M_current; }
1353#endif

    _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
    operator--()
    {
--_M_current;
return *this;
    }

    _GLIBCXX17_CONSTEXPRconstexpr move_iterator
    operator--(int)
    {
move_iterator __tmp = *this;
--_M_current;
return __tmp;
    }

    _GLIBCXX17_CONSTEXPRconstexpr move_iterator
    operator+(difference_type __n) const
    { return move_iterator(_M_current + __n); }

    _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
    operator+=(difference_type __n)
    {
_M_current += __n;
return *this;
    }

    _GLIBCXX17_CONSTEXPRconstexpr move_iterator
    operator-(difference_type __n) const
    { return move_iterator(_M_current - __n); }
  
    _GLIBCXX17_CONSTEXPRconstexpr move_iterator&
    operator-=(difference_type __n)
    { 
_M_current -= __n;
return *this;
    }

    _GLIBCXX17_CONSTEXPRconstexpr reference
    operator[](difference_type __n) const
    { return std::move(_M_current[__n]); }

1396#if __cplusplus201703L > 201703L && __cpp_lib_concepts
    template<sentinel_for<_Iterator> _Sent>
friend constexpr bool
operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
{ return __x.base() == __y.base(); }

    template<sized_sentinel_for<_Iterator> _Sent>
friend constexpr iter_difference_t<_Iterator>
operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
{ return __x.base() - __y.base(); }

    template<sized_sentinel_for<_Iterator> _Sent>
friend constexpr iter_difference_t<_Iterator>
operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
{ return __x.base() - __y.base(); }

    friend constexpr iter_rvalue_reference_t<_Iterator>
    iter_move(const move_iterator& __i)
    noexcept(noexcept(ranges::iter_move(__i._M_current)))
    { return ranges::iter_move(__i._M_current); }

    template<indirectly_swappable<_Iterator> _Iter2>
friend constexpr void
iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
{ return ranges::iter_swap(__x._M_current, __y._M_current); }
1422#endif // C++20
  };

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator==(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1429#if __cplusplus201703L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1431#endif
  { return __x.base() == __y.base(); }

1434#if __cpp_lib_three_way_comparison
template<typename _IteratorL,
  three_way_comparable_with<_IteratorL> _IteratorR>
  constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
  operator<=>(const move_iterator<_IteratorL>& __x,
const move_iterator<_IteratorR>& __y)
  { return __x.base() <=> __y.base(); }
1441#else
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator!=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
  { return !(__x == __y); }
1447#endif

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
1453#if __cplusplus201703L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1455#endif
  { return __x.base() < __y.base(); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1462#if __cplusplus201703L > 201703L && __cpp_lib_concepts
  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1464#endif
  { return !(__y < __x); }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
1471#if __cplusplus201703L > 201703L && __cpp_lib_concepts
  requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1473#endif
  { return __y < __x; }

template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>=(const move_iterator<_IteratorL>& __x,
      const move_iterator<_IteratorR>& __y)
1480#if __cplusplus201703L > 201703L && __cpp_lib_concepts
  requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1482#endif
  { return !(__x < __y); }

1485#if ! (__cplusplus201703L > 201703L && __cpp_lib_concepts)
// Note: See __normal_iterator operators note from Gaby to understand
// why we have these extra overloads for some move_iterator operators.

// These extra overloads are not needed in C++20, because the ones above
// are constrained with a requires-clause and so overload resolution will
// prefer them to greedy unconstrained function templates.

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator==(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return __x.base() == __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator!=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__x == __y); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<(const move_iterator<_Iterator>& __x,
     const move_iterator<_Iterator>& __y)
  { return __x.base() < __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator<=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__y < __x); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>(const move_iterator<_Iterator>& __x,
     const move_iterator<_Iterator>& __y)
  { return __y < __x; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr bool
  operator>=(const move_iterator<_Iterator>& __x,
      const move_iterator<_Iterator>& __y)
  { return !(__x < __y); }
1528#endif // ! C++20

// DR 685.
template<typename _IteratorL, typename _IteratorR>
  inline _GLIBCXX17_CONSTEXPRconstexpr auto
  operator-(const move_iterator<_IteratorL>& __x,
     const move_iterator<_IteratorR>& __y)
  -> decltype(__x.base() - __y.base())
  { return __x.base() - __y.base(); }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr move_iterator<_Iterator>
  operator+(typename move_iterator<_Iterator>::difference_type __n,
     const move_iterator<_Iterator>& __x)
  { return __x + __n; }

template<typename _Iterator>
  inline _GLIBCXX17_CONSTEXPRconstexpr move_iterator<_Iterator>
  make_move_iterator(_Iterator __i)
  { return move_iterator<_Iterator>(std::move(__i)); }

template<typename _Iterator, typename _ReturnType
  = typename conditional<__move_if_noexcept_cond
    <typename iterator_traits<_Iterator>::value_type>::value,
              _Iterator, move_iterator<_Iterator>>::type>
  inline _GLIBCXX17_CONSTEXPRconstexpr _ReturnType
  __make_move_if_noexcept_iterator(_Iterator __i)
  { return _ReturnType(__i); }

// Overload for pointers that matches std::move_if_noexcept more closely,
// returning a constant iterator when we don't want to move.
template<typename _Tp, typename _ReturnType
  = typename conditional<__move_if_noexcept_cond<_Tp>::value,
	   const _Tp*, move_iterator<_Tp*>>::type>
  inline _GLIBCXX17_CONSTEXPRconstexpr _ReturnType
  __make_move_if_noexcept_iterator(_Tp* __i)
  { return _ReturnType(__i); }

1566#if __cplusplus201703L > 201703L && __cpp_lib_concepts
// [iterators.common] Common iterators

namespace __detail
{
  template<typename _It>
    concept __common_iter_has_arrow = indirectly_readable<const _It>
&& (requires(const _It& __it) { __it.operator->(); }
   || is_reference_v<iter_reference_t<_It>>
   || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);

} // namespace __detail

/// An iterator/sentinel adaptor for representing a non-common range.
template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
  requires (!same_as<_It, _Sent>) && copyable<_It>
class common_iterator
{
  template<typename _Tp, typename _Up>
    static constexpr bool
    _S_noexcept1()
    {
if constexpr (is_trivially_default_constructible_v<_Tp>)
 return is_nothrow_assignable_v<_Tp, _Up>;
else
 return is_nothrow_constructible_v<_Tp, _Up>;
    }

  template<typename _It2, typename _Sent2>
    static constexpr bool
    _S_noexcept()
    { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }

  class _Proxy
  {
    iter_value_t<_It> _M_keep;

    _Proxy(iter_reference_t<_It>&& __x)
    : _M_keep(std::move(__x)) { }

    friend class common_iterator;

  public:
    const iter_value_t<_It>*
    operator->() const
    { return std::__addressof(_M_keep); }
  };

public:
  constexpr
  common_iterator()
  noexcept(is_nothrow_default_constructible_v<_It>)
  : _M_it(), _M_index(0)
  { }

  constexpr
  common_iterator(_It __i)
  noexcept(is_nothrow_move_constructible_v<_It>)
  : _M_it(std::move(__i)), _M_index(0)
  { }

  constexpr
  common_iterator(_Sent __s)
  noexcept(is_nothrow_move_constructible_v<_Sent>)
  : _M_sent(std::move(__s)), _M_index(1)
  { }

  template<typename _It2, typename _Sent2>
    requires convertible_to<const _It2&, _It>
&& convertible_to<const _Sent2&, _Sent>
    constexpr
    common_iterator(const common_iterator<_It2, _Sent2>& __x)
    noexcept(_S_noexcept<const _It2&, const _Sent2&>())
    : _M_valueless(), _M_index(__x._M_index)
    {
if (_M_index == 0)
 {
   if constexpr (is_trivially_default_constructible_v<_It>)
     _M_it = std::move(__x._M_it);
   else
     ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
 }
else if (_M_index == 1)
 {
   if constexpr (is_trivially_default_constructible_v<_Sent>)
     _M_sent = std::move(__x._M_sent);
   else
     ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
 }
    }

  constexpr
  common_iterator(const common_iterator& __x)
  noexcept(_S_noexcept<const _It&, const _Sent&>())
  : _M_valueless(), _M_index(__x._M_index)
  {
    if (_M_index == 0)
{
 if constexpr (is_trivially_default_constructible_v<_It>)
   _M_it = std::move(__x._M_it);
 else
   ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
}
    else if (_M_index == 1)
{
 if constexpr (is_trivially_default_constructible_v<_Sent>)
   _M_sent = std::move(__x._M_sent);
 else
   ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
}
  }

  common_iterator&
  operator=(const common_iterator& __x)
  noexcept(is_nothrow_copy_assignable_v<_It>
    && is_nothrow_copy_assignable_v<_Sent>
    && is_nothrow_copy_constructible_v<_It>
    && is_nothrow_copy_constructible_v<_Sent>)
  {
    return this->operator=<_It, _Sent>(__x);
  }

  template<typename _It2, typename _Sent2>
    requires convertible_to<const _It2&, _It>
&& convertible_to<const _Sent2&, _Sent>
&& assignable_from<_It&, const _It2&>
&& assignable_from<_Sent&, const _Sent2&>
    common_iterator&
    operator=(const common_iterator<_It2, _Sent2>& __x)
    noexcept(is_nothrow_constructible_v<_It, const _It2&>
      && is_nothrow_constructible_v<_Sent, const _Sent2&>
      && is_nothrow_assignable_v<_It, const _It2&>
      && is_nothrow_assignable_v<_Sent, const _Sent2&>)
    {
switch(_M_index << 2 | __x._M_index)
 {
 case 0b0000:
   _M_it = __x._M_it;
   break;
 case 0b0101:
   _M_sent = __x._M_sent;
   break;
 case 0b0001:
   _M_it.~_It();
   _M_index = -1;
   [[fallthrough]];
 case 0b1001:
   ::new((void*)std::__addressof(_M_sent)) _Sent(__x._M_sent);
   _M_index = 1;
   break;
 case 0b0100:
   _M_sent.~_Sent();
   _M_index = -1;
   [[fallthrough]];
 case 0b1000:
   ::new((void*)std::__addressof(_M_it)) _It(__x._M_it);
   _M_index = 0;
   break;
 default:
   __glibcxx_assert(__x._M_has_value());
   __builtin_unreachable();
 }
return *this;
    }

  ~common_iterator()
  {
    switch (_M_index)
{
case 0:
 _M_it.~_It();
 break;
case 1:
 _M_sent.~_Sent();
 break;
}
  }

  decltype(auto)
  operator*()
  {
    __glibcxx_assert(_M_index == 0);
    return *_M_it;
  }

  decltype(auto)
  operator*() const requires __detail::__dereferenceable<const _It>
  {
    __glibcxx_assert(_M_index == 0);
    return *_M_it;
  }

  decltype(auto)
  operator->() const requires __detail::__common_iter_has_arrow<_It>
  {
    __glibcxx_assert(_M_index == 0);
    if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
return _M_it;
    else if constexpr (is_reference_v<iter_reference_t<_It>>)
{
 auto&& __tmp = *_M_it;
 return std::__addressof(__tmp);
}
    else
return _Proxy{*_M_it};
  }

  common_iterator&
  operator++()
  {
    __glibcxx_assert(_M_index == 0);
    ++_M_it;
    return *this;
  }

  decltype(auto)
  operator++(int)
  {
    __glibcxx_assert(_M_index == 0);
    if constexpr (forward_iterator<_It>)
{
 common_iterator __tmp = *this;
 ++*this;
 return __tmp;
}
    else
return _M_it++;
  }

  template<typename _It2, sentinel_for<_It> _Sent2>
    requires sentinel_for<_Sent, _It2>
    friend bool
    operator==(const common_iterator& __x,
 const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0000:
 case 0b0101:
   return true;
 case 0b0001:
   return __x._M_it == __y._M_sent;
 case 0b0100:
   return __x._M_sent == __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  template<typename _It2, sentinel_for<_It> _Sent2>
    requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
    friend bool
    operator==(const common_iterator& __x,
 const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0101:
   return true;
 case 0b0000:
   return __x._M_it == __y._M_it;
 case 0b0001:
   return __x._M_it == __y._M_sent;
 case 0b0100:
   return __x._M_sent == __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
    requires sized_sentinel_for<_Sent, _It2>
    friend iter_difference_t<_It2>
    operator-(const common_iterator& __x,
const common_iterator<_It2, _Sent2>& __y)
    {
switch(__x._M_index << 2 | __y._M_index)
 {
 case 0b0101:
   return 0;
 case 0b0000:
   return __x._M_it - __y._M_it;
 case 0b0001:
   return __x._M_it - __y._M_sent;
 case 0b0100:
   return __x._M_sent - __y._M_it;
 default:
   __glibcxx_assert(__x._M_has_value());
   __glibcxx_assert(__y._M_has_value());
   __builtin_unreachable();
 }
    }

  friend iter_rvalue_reference_t<_It>
  iter_move(const common_iterator& __i)
  noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
  requires input_iterator<_It>
  {
    __glibcxx_assert(__i._M_index == 0);
    return ranges::iter_move(__i._M_it);
  }

  template<indirectly_swappable<_It> _It2, typename _Sent2>
    friend void
    iter_swap(const common_iterator& __x,
const common_iterator<_It2, _Sent2>& __y)
    noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
			  std::declval<const _It2&>())))
    {
__glibcxx_assert(__x._M_index == 0);
__glibcxx_assert(__y._M_index == 0);
return ranges::iter_swap(__x._M_it, __y._M_it);
    }

private:
  template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
    friend class common_iterator;

  bool _M_has_value() const noexcept { return _M_index < 2; }

  union
  {
    _It _M_it;
    _Sent _M_sent;
    unsigned char _M_valueless;
  };
  unsigned char _M_index; // 0==_M_it, 1==_M_sent, 2==valueless
};

template<typename _It, typename _Sent>
  struct incrementable_traits<common_iterator<_It, _Sent>>
  {
    using difference_type = iter_difference_t<_It>;
  };

namespace __detail
{
  // FIXME: This has to be at namespace-scope because of PR 92103.
  template<typename _It, typename _Sent>
    struct __common_iter_ptr
    {
using type = void;
    };

  template<typename _It, typename _Sent>
    requires __detail::__common_iter_has_arrow<_It>
    struct __common_iter_ptr<_It, _Sent>
    {
using common_iterator = std::common_iterator<_It, _Sent>;

using type
 = decltype(std::declval<const common_iterator&>().operator->());
    };
} // namespace __detail

template<input_iterator _It, typename _Sent>
  struct iterator_traits<common_iterator<_It, _Sent>>
  {
    using iterator_concept = conditional_t<forward_iterator<_It>,
   forward_iterator_tag, input_iterator_tag>;
    using iterator_category = __detail::__clamp_iter_cat<
typename iterator_traits<_It>::iterator_category,
forward_iterator_tag, input_iterator_tag>;
    using value_type = iter_value_t<_It>;
    using difference_type = iter_difference_t<_It>;
    using pointer = typename __detail::__common_iter_ptr<_It, _Sent>::type;
    using reference = iter_reference_t<_It>;
  };

// [iterators.counted] Counted iterators

/// An iterator adaptor that keeps track of the distance to the end.
template<input_or_output_iterator _It>
  class counted_iterator
  {
  public:
    using iterator_type = _It;

    constexpr counted_iterator() = default;

    constexpr
    counted_iterator(_It __i, iter_difference_t<_It> __n)
    : _M_current(std::move(__i)), _M_length(__n)
    { __glibcxx_assert(__n >= 0); }

    template<typename _It2>
requires convertible_to<const _It2&, _It>
constexpr
counted_iterator(const counted_iterator<_It2>& __x)
: _M_current(__x._M_current), _M_length(__x._M_length)
{ }

    template<typename _It2>
requires assignable_from<_It&, const _It2&>
constexpr counted_iterator&
operator=(const counted_iterator<_It2>& __x)
{
 _M_current = __x._M_current;
 _M_length = __x._M_length;
 return *this;
}

    constexpr _It
    base() const &
    noexcept(is_nothrow_copy_constructible_v<_It>)
    requires copy_constructible<_It>
    { return _M_current; }

    constexpr _It
    base() &&
    noexcept(is_nothrow_move_constructible_v<_It>)
    { return std::move(_M_current); }

    constexpr iter_difference_t<_It>
    count() const noexcept { return _M_length; }

    constexpr decltype(auto)
    operator*()
    noexcept(noexcept(*_M_current))
    { return *_M_current; }

    constexpr decltype(auto)
    operator*() const
    noexcept(noexcept(*_M_current))
    requires __detail::__dereferenceable<const _It>
    { return *_M_current; }

    constexpr counted_iterator&
    operator++()
    {
__glibcxx_assert(_M_length > 0);
++_M_current;
--_M_length;
return *this;
    }

    decltype(auto)
    operator++(int)
    {
__glibcxx_assert(_M_length > 0);
--_M_length;
__trytry
 {
   return _M_current++;
 } __catch(...)catch(...) {
   ++_M_length;
   throw;
 }

    }

    constexpr counted_iterator
    operator++(int) requires forward_iterator<_It>
    {
auto __tmp = *this;
++*this;
return __tmp;
    }

    constexpr counted_iterator&
    operator--() requires bidirectional_iterator<_It>
    {
--_M_current;
++_M_length;
return *this;
    }

    constexpr counted_iterator
    operator--(int) requires bidirectional_iterator<_It>
    {
auto __tmp = *this;
--*this;
return __tmp;
    }

    constexpr counted_iterator
    operator+(iter_difference_t<_It> __n) const
requires random_access_iterator<_It>
    { return counted_iterator(_M_current + __n, _M_length - __n); }

    friend constexpr counted_iterator
    operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
    requires random_access_iterator<_It>
    { return __x + __n; }

    constexpr counted_iterator&
    operator+=(iter_difference_t<_It> __n)
    requires random_access_iterator<_It>
    {
__glibcxx_assert(__n <= _M_length);
_M_current += __n;
_M_length -= __n;
return *this;
    }

    constexpr counted_iterator
    operator-(iter_difference_t<_It> __n) const
    requires random_access_iterator<_It>
    { return counted_iterator(_M_current - __n, _M_length + __n); }

    template<common_with<_It> _It2>
friend constexpr iter_difference_t<_It2>
operator-(const counted_iterator& __x,
  const counted_iterator<_It2>& __y)
{ return __y._M_length - __x._M_length; }

    friend constexpr iter_difference_t<_It>
    operator-(const counted_iterator& __x, default_sentinel_t)
    { return -__x._M_length; }

    friend constexpr iter_difference_t<_It>
    operator-(default_sentinel_t, const counted_iterator& __y)
    { return __y._M_length; }

    constexpr counted_iterator&
    operator-=(iter_difference_t<_It> __n)
    requires random_access_iterator<_It>
    {
__glibcxx_assert(-__n <= _M_length);
_M_current -= __n;
_M_length += __n;
return *this;
    }

    constexpr decltype(auto)
    operator[](iter_difference_t<_It> __n) const
    noexcept(noexcept(_M_current[__n]))
    requires random_access_iterator<_It>
    {
__glibcxx_assert(__n < _M_length);
return _M_current[__n];
    }

    template<common_with<_It> _It2>
friend constexpr bool
operator==(const counted_iterator& __x,
   const counted_iterator<_It2>& __y)
{ return __x._M_length == __y._M_length; }

    friend constexpr bool
    operator==(const counted_iterator& __x, default_sentinel_t)
    { return __x._M_length == 0; }

    template<common_with<_It> _It2>
friend constexpr strong_ordering
operator<=>(const counted_iterator& __x,
    const counted_iterator<_It2>& __y)
{ return __y._M_length <=> __x._M_length; }

    friend constexpr iter_rvalue_reference_t<_It>
    iter_move(const counted_iterator& __i)
    noexcept(noexcept(ranges::iter_move(__i._M_current)))
    requires input_iterator<_It>
    { return ranges::iter_move(__i._M_current); }

    template<indirectly_swappable<_It> _It2>
friend constexpr void
iter_swap(const counted_iterator& __x,
  const counted_iterator<_It2>& __y)
noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
{ ranges::iter_swap(__x._M_current, __y._M_current); }

  private:
    template<input_or_output_iterator _It2> friend class counted_iterator;

    _It _M_current = _It();
    iter_difference_t<_It> _M_length = 0;
  };

template<typename _It>
  struct incrementable_traits<counted_iterator<_It>>
  {
    using difference_type = iter_difference_t<_It>;
  };

template<input_iterator _It>
  struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
  {
    using pointer = void;
  };
2150#endif // C++20

// @} group iterators

template<typename _Iterator>
  auto
  __niter_base(move_iterator<_Iterator> __it)
  -> decltype(make_move_iterator(__niter_base(__it.base())))
  { return make_move_iterator(__niter_base(__it.base())); }

template<typename _Iterator>
  struct __is_move_iterator<move_iterator<_Iterator> >
  {
    enum { __value = 1 };
    typedef __true_type __type;
  };

template<typename _Iterator>
  auto
  __miter_base(move_iterator<_Iterator> __it)
  -> decltype(__miter_base(__it.base()))
  { return __miter_base(__it.base()); }

2173#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) std::make_move_iterator(_Iter)
2174#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) \
std::__make_move_if_noexcept_iterator(_Iter)
2176#else
2177#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter)std::make_move_iterator(_Iter) (_Iter)
2178#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter)std::__make_move_if_noexcept_iterator(_Iter) (_Iter)
2179#endif // C++11

2181#if __cpp_deduction_guides201703L >= 201606
// These helper traits are used for deduction guides
// of associative containers.
template<typename _InputIterator>
  using __iter_key_t = remove_const_t<
  typename iterator_traits<_InputIterator>::value_type::first_type>;

template<typename _InputIterator>
  using __iter_val_t =
  typename iterator_traits<_InputIterator>::value_type::second_type;

template<typename _T1, typename _T2>
  struct pair;

template<typename _InputIterator>
  using __iter_to_alloc_t =
  pair<add_const_t<__iter_key_t<_InputIterator>>,
__iter_val_t<_InputIterator>>;
2199#endif // __cpp_deduction_guides

2201_GLIBCXX_END_NAMESPACE_VERSION
2202} // namespace

2204#ifdef _GLIBCXX_DEBUG
2205# include <debug/stl_iterator.h>
2206#endif

2208#endif

←

/usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/bits/stl_tree.h

1// RB tree implementation -*- C++ -*-

3// Copyright (C) 2001-2020 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
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.

11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.

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.

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/>.

25/*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation.  Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose.  It is provided "as is" without express or implied warranty.
*
*
*/

53/** @file bits/stl_tree.h
*  This is an internal header file, included by other library headers.
*  Do not attempt to use it directly. @headername{map,set}
*/

58#ifndef _STL_TREE_H1
59#define _STL_TREE_H1 1

61#pragma GCC system_header

63#include <bits/stl_algobase.h>
64#include <bits/allocator.h>
65#include <bits/stl_function.h>
66#include <bits/cpp_type_traits.h>
67#include <ext/alloc_traits.h>
68#if __cplusplus201703L >= 201103L
69# include <ext/aligned_buffer.h>
70#endif
71#if __cplusplus201703L > 201402L
72# include <bits/node_handle.h>
73#endif

75namespace std _GLIBCXX_VISIBILITY(default)__attribute__ ((__visibility__ ("default")))
76{
77_GLIBCXX_BEGIN_NAMESPACE_VERSION

79#if __cplusplus201703L > 201103L
80# define __cpp_lib_generic_associative_lookup201304 201304
81#endif

// Red-black tree class, designed for use in implementing STL
// associative containers (set, multiset, map, and multimap). The
// insertion and deletion algorithms are based on those in Cormen,
// Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
// 1990), except that
//
// (1) the header cell is maintained with links not only to the root
// but also to the leftmost node of the tree, to enable constant
// time begin(), and to the rightmost node of the tree, to enable
// linear time performance when used with the generic set algorithms
// (set_union, etc.)
//
// (2) when a node being deleted has two children its successor node
// is relinked into its place, rather than copied, so that the only
// iterators invalidated are those referring to the deleted node.

enum _Rb_tree_color { _S_red = false, _S_black = true };

struct _Rb_tree_node_base
{
  typedef _Rb_tree_node_base* _Base_ptr;
  typedef const _Rb_tree_node_base* _Const_Base_ptr;

  _Rb_tree_color	_M_color;
  _Base_ptr		_M_parent;
  _Base_ptr		_M_left;
  _Base_ptr		_M_right;

  static _Base_ptr
  _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
  {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }

  static _Const_Base_ptr
  _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
  {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }

  static _Base_ptr
  _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
  {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }

  static _Const_Base_ptr
  _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
  {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }
};

// Helper type offering value initialization guarantee on the compare functor.
template<typename _Key_compare>
  struct _Rb_tree_key_compare
  {
    _Key_compare		_M_key_compare;

    _Rb_tree_key_compare()
    _GLIBCXX_NOEXCEPT_IF(noexcept(is_nothrow_default_constructible<_Key_compare>
::value)
is_nothrow_default_constructible<_Key_compare>::value)noexcept(is_nothrow_default_constructible<_Key_compare>
::value)
    : _M_key_compare()
    { }

    _Rb_tree_key_compare(const _Key_compare& __comp)
    : _M_key_compare(__comp)
    { }

156#if __cplusplus201703L >= 201103L
    // Copy constructor added for consistency with C++98 mode.
    _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;

    _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
    : _M_key_compare(__x._M_key_compare)
    { }
164#endif
  };

// Helper type to manage default initialization of node count and header.
struct _Rb_tree_header
{
  _Rb_tree_node_base	_M_header;
  size_t		_M_node_count; // Keeps track of size of tree.

  _Rb_tree_header() _GLIBCXX_NOEXCEPTnoexcept
  {
    _M_header._M_color = _S_red;
    _M_reset();
  }

179#if __cplusplus201703L >= 201103L
  _Rb_tree_header(_Rb_tree_header&& __x) noexcept
  {
    if (__x._M_header._M_parent != nullptr)
_M_move_data(__x);
    else
{
 _M_header._M_color = _S_red;
 _M_reset();
}
  }
190#endif

  void
  _M_move_data(_Rb_tree_header& __from)
  {
    _M_header._M_color = __from._M_header._M_color;
    _M_header._M_parent = __from._M_header._M_parent;
    _M_header._M_left = __from._M_header._M_left;
    _M_header._M_right = __from._M_header._M_right;
    _M_header._M_parent->_M_parent = &_M_header;
    _M_node_count = __from._M_node_count;

    __from._M_reset();
  }

  void
  _M_reset()
  {
    _M_header._M_parent = 0;
    _M_header._M_left = &_M_header;
    _M_header._M_right = &_M_header;
    _M_node_count = 0;
  }
};

template<typename _Val>
  struct _Rb_tree_node : public _Rb_tree_node_base
  {
    typedef _Rb_tree_node<_Val>* _Link_type;

220#if __cplusplus201703L < 201103L
    _Val _M_value_field;

    _Val*
    _M_valptr()
    { return std::__addressof(_M_value_field); }

    const _Val*
    _M_valptr() const
    { return std::__addressof(_M_value_field); }
230#else
    __gnu_cxx::__aligned_membuf<_Val> _M_storage;

    _Val*
    _M_valptr()
    { return _M_storage._M_ptr(); }

    const _Val*
    _M_valptr() const
    { return _M_storage._M_ptr(); }
240#endif
  };

_GLIBCXX_PURE__attribute__ ((__pure__)) _Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ();

_GLIBCXX_PURE__attribute__ ((__pure__)) const _Rb_tree_node_base*
_Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();

_GLIBCXX_PURE__attribute__ ((__pure__)) _Rb_tree_node_base*
_Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();

_GLIBCXX_PURE__attribute__ ((__pure__)) const _Rb_tree_node_base*
_Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();

template<typename _Tp>
  struct _Rb_tree_iterator
  {
    typedef _Tp  value_type;
    typedef _Tp& reference;
    typedef _Tp* pointer;

    typedef bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t			 difference_type;

    typedef _Rb_tree_iterator<_Tp>		_Self;
    typedef _Rb_tree_node_base::_Base_ptr	_Base_ptr;
    typedef _Rb_tree_node<_Tp>*		_Link_type;

    _Rb_tree_iterator() _GLIBCXX_NOEXCEPTnoexcept
    : _M_node() { }

    explicit
    _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    : _M_node(__x) { }

    reference
    operator*() const _GLIBCXX_NOEXCEPTnoexcept
    { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }

    pointer
    operator->() const _GLIBCXX_NOEXCEPTnoexcept
    { return static_cast<_Link_type> (_M_node)->_M_valptr(); }

    _Self&
    operator++() _GLIBCXX_NOEXCEPTnoexcept
    {
_M_node = _Rb_tree_increment(_M_node);
return *this;
    }

    _Self
    operator++(int) _GLIBCXX_NOEXCEPTnoexcept
    {
_Self __tmp = *this;
_M_node = _Rb_tree_increment(_M_node);
return __tmp;
    }

    _Self&
    operator--() _GLIBCXX_NOEXCEPTnoexcept
    {
_M_node = _Rb_tree_decrement(_M_node);
return *this;
    }

    _Self
    operator--(int) _GLIBCXX_NOEXCEPTnoexcept
    {
_Self __tmp = *this;
_M_node = _Rb_tree_decrement(_M_node);
return __tmp;
    }

    friend bool
    operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
    { return __x._M_node == __y._M_node; }

318#if ! __cpp_lib_three_way_comparison
    friend bool
    operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
    { return __x._M_node != __y._M_node; }
322#endif

    _Base_ptr _M_node;
};

template<typename _Tp>
  struct _Rb_tree_const_iterator
  {
    typedef _Tp	 value_type;
    typedef const _Tp& reference;
    typedef const _Tp* pointer;

    typedef _Rb_tree_iterator<_Tp> iterator;

    typedef bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t			 difference_type;

    typedef _Rb_tree_const_iterator<_Tp>		_Self;
    typedef _Rb_tree_node_base::_Const_Base_ptr	_Base_ptr;
    typedef const _Rb_tree_node<_Tp>*			_Link_type;

    _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPTnoexcept
    : _M_node() { }

    explicit
    _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    : _M_node(__x) { }

    _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPTnoexcept
    : _M_node(__it._M_node) { }

    iterator
    _M_const_cast() const _GLIBCXX_NOEXCEPTnoexcept
    { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }

    reference
    operator*() const _GLIBCXX_NOEXCEPTnoexcept
    { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }

    pointer
    operator->() const _GLIBCXX_NOEXCEPTnoexcept
    { return static_cast<_Link_type>(_M_node)->_M_valptr(); }

    _Self&
    operator++() _GLIBCXX_NOEXCEPTnoexcept
    {
_M_node = _Rb_tree_increment(_M_node);
return *this;
    }

    _Self
    operator++(int) _GLIBCXX_NOEXCEPTnoexcept
    {
_Self __tmp = *this;
_M_node = _Rb_tree_increment(_M_node);
return __tmp;
    }

    _Self&
    operator--() _GLIBCXX_NOEXCEPTnoexcept
    {
_M_node = _Rb_tree_decrement(_M_node);
return *this;
    }

    _Self
    operator--(int) _GLIBCXX_NOEXCEPTnoexcept
    {
_Self __tmp = *this;
_M_node = _Rb_tree_decrement(_M_node);
return __tmp;
    }

    friend bool
    operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
    { return __x._M_node == __y._M_node; }
25
←
Assuming '__x._M_node' is not equal to '__y._M_node'→
26
←
Returning zero, which participates in a condition later→

399#if ! __cpp_lib_three_way_comparison
    friend bool
    operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPTnoexcept
    { return __x._M_node != __y._M_node; }
403#endif

    _Base_ptr _M_node;
  };

void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
		_Rb_tree_node_base* __x,
		_Rb_tree_node_base* __p,
		_Rb_tree_node_base& __header) throw ();

_Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
	       _Rb_tree_node_base& __header) throw ();

418#if __cplusplus201703L >= 201402L
template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
  struct __has_is_transparent
  { };

template<typename _Cmp, typename _SfinaeType>
  struct __has_is_transparent<_Cmp, _SfinaeType,
		__void_t<typename _Cmp::is_transparent>>
  { typedef void type; };

template<typename _Cmp, typename _SfinaeType>
  using __has_is_transparent_t
    = typename __has_is_transparent<_Cmp, _SfinaeType>::type;
431#endif

433#if __cplusplus201703L > 201402L
template<typename _Tree1, typename _Cmp2>
  struct _Rb_tree_merge_helper { };
436#endif

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc = allocator<_Val> >
  class _Rb_tree
  {
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Rb_tree_node<_Val> >::other _Node_allocator;

    typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;

  protected:
    typedef _Rb_tree_node_base* 		_Base_ptr;
    typedef const _Rb_tree_node_base* 	_Const_Base_ptr;
    typedef _Rb_tree_node<_Val>* 		_Link_type;
    typedef const _Rb_tree_node<_Val>*	_Const_Link_type;

  private:
    // Functor recycling a pool of nodes and using allocation once the pool
    // is empty.
    struct _Reuse_or_alloc_node
    {
_Reuse_or_alloc_node(_Rb_tree& __t)
: _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
{
 if (_M_root)
   {
     _M_root->_M_parent = 0;

     if (_M_nodes->_M_left)
_M_nodes = _M_nodes->_M_left;
   }
 else
   _M_nodes = 0;
}

472#if __cplusplus201703L >= 201103L
_Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
474#endif

~_Reuse_or_alloc_node()
{ _M_t._M_erase(static_cast<_Link_type>(_M_root)); }

template<typename _Arg>
 _Link_type
481#if __cplusplus201703L < 201103L
 operator()(const _Arg& __arg)
483#else
 operator()(_Arg&& __arg)
485#endif
 {
   _Link_type __node = static_cast<_Link_type>(_M_extract());
   if (__node)
     {
_M_t._M_destroy_node(__node);
_M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg)std::forward<_Arg>(__arg));
return __node;
     }

   return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)std::forward<_Arg>(__arg));
 }

    private:
_Base_ptr
_M_extract()
{
 if (!_M_nodes)
   return _M_nodes;

 _Base_ptr __node = _M_nodes;
 _M_nodes = _M_nodes->_M_parent;
 if (_M_nodes)
   {
     if (_M_nodes->_M_right == __node)
{
  _M_nodes->_M_right = 0;

  if (_M_nodes->_M_left)
    {
      _M_nodes = _M_nodes->_M_left;

      while (_M_nodes->_M_right)
	_M_nodes = _M_nodes->_M_right;

      if (_M_nodes->_M_left)
	_M_nodes = _M_nodes->_M_left;
    }
}
     else // __node is on the left.
_M_nodes->_M_left = 0;
   }
 else
   _M_root = 0;

 return __node;
}

_Base_ptr _M_root;
_Base_ptr _M_nodes;
_Rb_tree& _M_t;
    };

    // Functor similar to the previous one but without any pool of nodes to
    // recycle.
    struct _Alloc_node
    {
_Alloc_node(_Rb_tree& __t)
: _M_t(__t) { }

template<typename _Arg>
 _Link_type
547#if __cplusplus201703L < 201103L
 operator()(const _Arg& __arg) const
549#else
 operator()(_Arg&& __arg) const
551#endif
 { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)std::forward<_Arg>(__arg)); }

    private:
_Rb_tree& _M_t;
    };

  public:
    typedef _Key 				key_type;
    typedef _Val 				value_type;
    typedef value_type* 			pointer;
    typedef const value_type* 		const_pointer;
    typedef value_type& 			reference;
    typedef const value_type& 		const_reference;
    typedef size_t 				size_type;
    typedef ptrdiff_t 			difference_type;
    typedef _Alloc 				allocator_type;

    _Node_allocator&
    _M_get_Node_allocator() _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl; }

    const _Node_allocator&
    _M_get_Node_allocator() const _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl; }

    allocator_type
    get_allocator() const _GLIBCXX_NOEXCEPTnoexcept
    { return allocator_type(_M_get_Node_allocator()); }

  protected:
    _Link_type
    _M_get_node()
    { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }

    void
    _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPTnoexcept
    { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }

590#if __cplusplus201703L < 201103L
    void
    _M_construct_node(_Link_type __node, const value_type& __x)
    {
__trytry
 { get_allocator().construct(__node->_M_valptr(), __x); }
__catch(...)catch(...)
 {
   _M_put_node(__node);
   __throw_exception_againthrow;
 }
    }

    _Link_type
    _M_create_node(const value_type& __x)
    {
_Link_type __tmp = _M_get_node();
_M_construct_node(__tmp, __x);
return __tmp;
    }
610#else
    template<typename... _Args>
void
_M_construct_node(_Link_type __node, _Args&&... __args)
{
 __trytry
   {
     ::new(__node) _Rb_tree_node<_Val>;
     _Alloc_traits::construct(_M_get_Node_allocator(),
		       __node->_M_valptr(),
		       std::forward<_Args>(__args)...);
   }
 __catch(...)catch(...)
   {
     __node->~_Rb_tree_node<_Val>();
     _M_put_node(__node);
     __throw_exception_againthrow;
   }
}

    template<typename... _Args>
_Link_type
_M_create_node(_Args&&... __args)
{
 _Link_type __tmp = _M_get_node();
 _M_construct_node(__tmp, std::forward<_Args>(__args)...);
 return __tmp;
}
638#endif

    void
    _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPTnoexcept
    {
643#if __cplusplus201703L < 201103L
get_allocator().destroy(__p->_M_valptr());
645#else
_Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
__p->~_Rb_tree_node<_Val>();
648#endif
    }

    void
    _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPTnoexcept
    {
_M_destroy_node(__p);
_M_put_node(__p);
    }

    template<typename _NodeGen>
_Link_type
_M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
{
 _Link_type __tmp = __node_gen(*__x->_M_valptr());
 __tmp->_M_color = __x->_M_color;
 __tmp->_M_left = 0;
 __tmp->_M_right = 0;
 return __tmp;
}

  protected:
670#if _GLIBCXX_INLINE_VERSION0
    template<typename _Key_compare>
672#else
    // Unused _Is_pod_comparator is kept as it is part of mangled name.
    template<typename _Key_compare,
      bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
676#endif
struct _Rb_tree_impl
: public _Node_allocator
, public _Rb_tree_key_compare<_Key_compare>
, public _Rb_tree_header
{
 typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;

 _Rb_tree_impl()
   _GLIBCXX_NOEXCEPT_IF(noexcept(is_nothrow_default_constructible<_Node_allocator>
::value && is_nothrow_default_constructible<_Base_key_compare
>::value)
is_nothrow_default_constructible<_Node_allocator>::valuenoexcept(is_nothrow_default_constructible<_Node_allocator>
::value && is_nothrow_default_constructible<_Base_key_compare
>::value)
&& is_nothrow_default_constructible<_Base_key_compare>::value )noexcept(is_nothrow_default_constructible<_Node_allocator>
::value && is_nothrow_default_constructible<_Base_key_compare
>::value)
 : _Node_allocator()
 { }

 _Rb_tree_impl(const _Rb_tree_impl& __x)
 : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
 , _Base_key_compare(__x._M_key_compare)
 { }

696#if __cplusplus201703L < 201103L
 _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
 : _Node_allocator(__a), _Base_key_compare(__comp)
 { }
700#else
 _Rb_tree_impl(_Rb_tree_impl&&) = default;

 explicit
 _Rb_tree_impl(_Node_allocator&& __a)
 : _Node_allocator(std::move(__a))
 { }

 _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
 : _Node_allocator(std::move(__a)),
   _Base_key_compare(std::move(__x)),
   _Rb_tree_header(std::move(__x))
 { }

 _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 { }
717#endif
};

    _Rb_tree_impl<_Compare> _M_impl;

  protected:
    _Base_ptr&
    _M_root() _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl._M_header._M_parent; }

    _Const_Base_ptr
    _M_root() const _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl._M_header._M_parent; }

    _Base_ptr&
    _M_leftmost() _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl._M_header._M_left; }

    _Const_Base_ptr
    _M_leftmost() const _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl._M_header._M_left; }

    _Base_ptr&
    _M_rightmost() _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl._M_header._M_right; }

    _Const_Base_ptr
    _M_rightmost() const _GLIBCXX_NOEXCEPTnoexcept
    { return this->_M_impl._M_header._M_right; }

    _Link_type
    _M_begin() _GLIBCXX_NOEXCEPTnoexcept
    { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }

    _Const_Link_type
    _M_begin() const _GLIBCXX_NOEXCEPTnoexcept
    {
return static_cast<_Const_Link_type>
 (this->_M_impl._M_header._M_parent);
    }

    _Base_ptr
    _M_end() _GLIBCXX_NOEXCEPTnoexcept
    { return &this->_M_impl._M_header; }

    _Const_Base_ptr
    _M_end() const _GLIBCXX_NOEXCEPTnoexcept
    { return &this->_M_impl._M_header; }

    static const _Key&
    _S_key(_Const_Link_type __x)
    {
769#if __cplusplus201703L >= 201103L
// If we're asking for the key we're presumably using the comparison
// object, and so this is a good place to sanity check it.
static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
      "comparison object must be invocable "
      "with two arguments of key type");
775# if __cplusplus201703L >= 201703L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2542. Missing const requirements for associative containers
if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
 static_assert(
     is_invocable_v<const _Compare&, const _Key&, const _Key&>,
     "comparison object must be invocable as const");
782# endif // C++17
783#endif // C++11

return _KeyOfValue()(*__x->_M_valptr());
    }

    static _Link_type
    _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return static_cast<_Link_type>(__x->_M_left); }

    static _Const_Link_type
    _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return static_cast<_Const_Link_type>(__x->_M_left); }

    static _Link_type
    _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return static_cast<_Link_type>(__x->_M_right); }

    static _Const_Link_type
    _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return static_cast<_Const_Link_type>(__x->_M_right); }

    static const _Key&
    _S_key(_Const_Base_ptr __x)
    { return _S_key(static_cast<_Const_Link_type>(__x)); }

    static _Base_ptr
    _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return _Rb_tree_node_base::_S_minimum(__x); }

    static _Const_Base_ptr
    _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return _Rb_tree_node_base::_S_minimum(__x); }

    static _Base_ptr
    _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return _Rb_tree_node_base::_S_maximum(__x); }

    static _Const_Base_ptr
    _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPTnoexcept
    { return _Rb_tree_node_base::_S_maximum(__x); }

  public:
    typedef _Rb_tree_iterator<value_type>       iterator;
    typedef _Rb_tree_const_iterator<value_type> const_iterator;

    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

831#if __cplusplus201703L > 201402L
    using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
    using insert_return_type = _Node_insert_return<
conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
node_type>;
836#endif

    pair<_Base_ptr, _Base_ptr>
    _M_get_insert_unique_pos(const key_type& __k);

    pair<_Base_ptr, _Base_ptr>
    _M_get_insert_equal_pos(const key_type& __k);

    pair<_Base_ptr, _Base_ptr>
    _M_get_insert_hint_unique_pos(const_iterator __pos,
		    const key_type& __k);

    pair<_Base_ptr, _Base_ptr>
    _M_get_insert_hint_equal_pos(const_iterator __pos,
		   const key_type& __k);

  private:
853#if __cplusplus201703L >= 201103L
    template<typename _Arg, typename _NodeGen>
iterator
_M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);

    iterator
    _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);

    template<typename _Arg>
iterator
_M_insert_lower(_Base_ptr __y, _Arg&& __v);

    template<typename _Arg>
iterator
_M_insert_equal_lower(_Arg&& __x);

    iterator
    _M_insert_lower_node(_Base_ptr __p, _Link_type __z);

    iterator
    _M_insert_equal_lower_node(_Link_type __z);
874#else
    template<typename _NodeGen>
iterator
_M_insert_(_Base_ptr __x, _Base_ptr __y,
   const value_type& __v, _NodeGen&);

    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 233. Insertion hints in associative containers.
    iterator
    _M_insert_lower(_Base_ptr __y, const value_type& __v);

    iterator
    _M_insert_equal_lower(const value_type& __x);
887#endif

    template<typename _NodeGen>
_Link_type
_M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);

    template<typename _NodeGen>
_Link_type
_M_copy(const _Rb_tree& __x, _NodeGen& __gen)
{
 _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
 _M_leftmost() = _S_minimum(__root);
 _M_rightmost() = _S_maximum(__root);
 _M_impl._M_node_count = __x._M_impl._M_node_count;
 return __root;
}

    _Link_type
    _M_copy(const _Rb_tree& __x)
    {
_Alloc_node __an(*this);
return _M_copy(__x, __an);
    }

    void
    _M_erase(_Link_type __x);

    iterator
    _M_lower_bound(_Link_type __x, _Base_ptr __y,
     const _Key& __k);

    const_iterator
    _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
     const _Key& __k) const;

    iterator
    _M_upper_bound(_Link_type __x, _Base_ptr __y,
     const _Key& __k);

    const_iterator
    _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
     const _Key& __k) const;

  public:
    // allocation/deallocation
932#if __cplusplus201703L < 201103L
    _Rb_tree() { }
934#else
    _Rb_tree() = default;
936#endif

    _Rb_tree(const _Compare& __comp,
      const allocator_type& __a = allocator_type())
    : _M_impl(__comp, _Node_allocator(__a)) { }

    _Rb_tree(const _Rb_tree& __x)
    : _M_impl(__x._M_impl)
    {
if (__x._M_root() != 0)
 _M_root() = _M_copy(__x);
    }

949#if __cplusplus201703L >= 201103L
    _Rb_tree(const allocator_type& __a)
    : _M_impl(_Node_allocator(__a))
    { }

    _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
    : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
    {
if (__x._M_root() != nullptr)
 _M_root() = _M_copy(__x);
    }

    _Rb_tree(_Rb_tree&&) = default;

    _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
    : _Rb_tree(std::move(__x), _Node_allocator(__a))
    { }

  private:
    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
    noexcept(is_nothrow_default_constructible<_Compare>::value)
    : _M_impl(std::move(__x._M_impl), std::move(__a))
    { }

    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
    {
if (__x._M_root() != nullptr)
 _M_move_data(__x, false_type{});
    }

  public:
    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
    noexcept( noexcept(
_Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
 std::declval<typename _Alloc_traits::is_always_equal>())) )
    : _Rb_tree(std::move(__x), std::move(__a),
 typename _Alloc_traits::is_always_equal{})
    { }
988#endif

    ~_Rb_tree() _GLIBCXX_NOEXCEPTnoexcept
    { _M_erase(_M_begin()); }

    _Rb_tree&
    operator=(const _Rb_tree& __x);

    // Accessors.
    _Compare
    key_comp() const
    { return _M_impl._M_key_compare; }

    iterator
    begin() _GLIBCXX_NOEXCEPTnoexcept
    { return iterator(this->_M_impl._M_header._M_left); }

    const_iterator
    begin() const _GLIBCXX_NOEXCEPTnoexcept
    { return const_iterator(this->_M_impl._M_header._M_left); }

    iterator
    end() _GLIBCXX_NOEXCEPTnoexcept
    { return iterator(&this->_M_impl._M_header); }

    const_iterator
    end() const _GLIBCXX_NOEXCEPTnoexcept
    { return const_iterator(&this->_M_impl._M_header); }

    reverse_iterator
    rbegin() _GLIBCXX_NOEXCEPTnoexcept
    { return reverse_iterator(end()); }

    const_reverse_iterator
    rbegin() const _GLIBCXX_NOEXCEPTnoexcept
    { return const_reverse_iterator(end()); }

    reverse_iterator
    rend() _GLIBCXX_NOEXCEPTnoexcept
    { return reverse_iterator(begin()); }

    const_reverse_iterator
    rend() const _GLIBCXX_NOEXCEPTnoexcept
    { return const_reverse_iterator(begin()); }

    _GLIBCXX_NODISCARD[[__nodiscard__]] bool
    empty() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_impl._M_node_count == 0; }

    size_type
    size() const _GLIBCXX_NOEXCEPTnoexcept
    { return _M_impl._M_node_count; }

    size_type
    max_size() const _GLIBCXX_NOEXCEPTnoexcept
    { return _Alloc_traits::max_size(_M_get_Node_allocator()); }

    void
    swap(_Rb_tree& __t)
    _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)noexcept(__is_nothrow_swappable<_Compare>::value);

    // Insert/erase.
1050#if __cplusplus201703L >= 201103L
    template<typename _Arg>
pair<iterator, bool>
_M_insert_unique(_Arg&& __x);

    template<typename _Arg>
iterator
_M_insert_equal(_Arg&& __x);

    template<typename _Arg, typename _NodeGen>
iterator
_M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);

    template<typename _Arg>
iterator
_M_insert_unique_(const_iterator __pos, _Arg&& __x)
{
 _Alloc_node __an(*this);
 return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
}

    template<typename _Arg, typename _NodeGen>
iterator
_M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);

    template<typename _Arg>
iterator
_M_insert_equal_(const_iterator __pos, _Arg&& __x)
{
 _Alloc_node __an(*this);
 return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
}

    template<typename... _Args>
pair<iterator, bool>
_M_emplace_unique(_Args&&... __args);

    template<typename... _Args>
iterator
_M_emplace_equal(_Args&&... __args);

    template<typename... _Args>
iterator
_M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);

    template<typename... _Args>
iterator
_M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);

    template<typename _Iter>
using __same_value_type
 = is_same<value_type, typename iterator_traits<_Iter>::value_type>;

    template<typename _InputIterator>
__enable_if_t<__same_value_type<_InputIterator>::value>
_M_insert_range_unique(_InputIterator __first, _InputIterator __last)
{
 _Alloc_node __an(*this);
 for (; __first != __last; ++__first)
   _M_insert_unique_(end(), *__first, __an);
}

    template<typename _InputIterator>
__enable_if_t<!__same_value_type<_InputIterator>::value>
_M_insert_range_unique(_InputIterator __first, _InputIterator __last)
{
 for (; __first != __last; ++__first)
   _M_emplace_unique(*__first);
}

    template<typename _InputIterator>
__enable_if_t<__same_value_type<_InputIterator>::value>
_M_insert_range_equal(_InputIterator __first, _InputIterator __last)
{
 _Alloc_node __an(*this);
 for (; __first != __last; ++__first)
   _M_insert_equal_(end(), *__first, __an);
}

    template<typename _InputIterator>
__enable_if_t<!__same_value_type<_InputIterator>::value>
_M_insert_range_equal(_InputIterator __first, _InputIterator __last)
{
 _Alloc_node __an(*this);
 for (; __first != __last; ++__first)
   _M_emplace_equal(*__first);
}
1137#else
    pair<iterator, bool>
    _M_insert_unique(const value_type& __x);

    iterator
    _M_insert_equal(const value_type& __x);

    template<typename _NodeGen>
iterator
_M_insert_unique_(const_iterator __pos, const value_type& __x,
	  _NodeGen&);

    iterator
    _M_insert_unique_(const_iterator __pos, const value_type& __x)
    {
_Alloc_node __an(*this);
return _M_insert_unique_(__pos, __x, __an);
    }

    template<typename _NodeGen>
iterator
_M_insert_equal_(const_iterator __pos, const value_type& __x,
	 _NodeGen&);
    iterator
    _M_insert_equal_(const_iterator __pos, const value_type& __x)
    {
_Alloc_node __an(*this);
return _M_insert_equal_(__pos, __x, __an);
    }

    template<typename _InputIterator>
void
_M_insert_range_unique(_InputIterator __first, _InputIterator __last)
{
 _Alloc_node __an(*this);
 for (; __first != __last; ++__first)
   _M_insert_unique_(end(), *__first, __an);
}

    template<typename _InputIterator>
void
_M_insert_range_equal(_InputIterator __first, _InputIterator __last)
{
 _Alloc_node __an(*this);
 for (; __first != __last; ++__first)
   _M_insert_equal_(end(), *__first, __an);
}
1184#endif

  private:
    void
    _M_erase_aux(const_iterator __position);

    void
    _M_erase_aux(const_iterator __first, const_iterator __last);

  public:
1194#if __cplusplus201703L >= 201103L
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // DR 130. Associative erase should return an iterator.
    _GLIBCXX_ABI_TAG_CXX11__attribute ((__abi_tag__ ("cxx11")))
    iterator
    erase(const_iterator __position)
    {
__glibcxx_assert(__position != end());
const_iterator __result = __position;
++__result;
_M_erase_aux(__position);
return __result._M_const_cast();
    }

    // LWG 2059.
    _GLIBCXX_ABI_TAG_CXX11__attribute ((__abi_tag__ ("cxx11")))
    iterator
    erase(iterator __position)
    {
__glibcxx_assert(__position != end());
iterator __result = __position;
++__result;
_M_erase_aux(__position);
return __result;
    }
1219#else
    void
    erase(iterator __position)
    {
__glibcxx_assert(__position != end());
_M_erase_aux(__position);
    }

    void
    erase(const_iterator __position)
    {
__glibcxx_assert(__position != end());
_M_erase_aux(__position);
    }
1233#endif

    size_type
    erase(const key_type& __x);

1238#if __cplusplus201703L >= 201103L
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // DR 130. Associative erase should return an iterator.
    _GLIBCXX_ABI_TAG_CXX11__attribute ((__abi_tag__ ("cxx11")))
    iterator
    erase(const_iterator __first, const_iterator __last)
    {
_M_erase_aux(__first, __last);
return __last._M_const_cast();
    }
1248#else
    void
    erase(iterator __first, iterator __last)
    { _M_erase_aux(__first, __last); }

    void
    erase(const_iterator __first, const_iterator __last)
    { _M_erase_aux(__first, __last); }
1256#endif

    void
    clear() _GLIBCXX_NOEXCEPTnoexcept
    {
_M_erase(_M_begin());
_M_impl._M_reset();
    }

    // Set operations.
    iterator
    find(const key_type& __k);

    const_iterator
    find(const key_type& __k) const;

    size_type
    count(const key_type& __k) const;

    iterator
    lower_bound(const key_type& __k)
    { return _M_lower_bound(_M_begin(), _M_end(), __k); }

    const_iterator
    lower_bound(const key_type& __k) const
    { return _M_lower_bound(_M_begin(), _M_end(), __k); }

    iterator
    upper_bound(const key_type& __k)
    { return _M_upper_bound(_M_begin(), _M_end(), __k); }

    const_iterator
    upper_bound(const key_type& __k) const
    { return _M_upper_bound(_M_begin(), _M_end(), __k); }

    pair<iterator, iterator>
    equal_range(const key_type& __k);

    pair<const_iterator, const_iterator>
    equal_range(const key_type& __k) const;

1297#if __cplusplus201703L >= 201402L
    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
iterator
_M_find_tr(const _Kt& __k)
{
 const _Rb_tree* __const_this = this;
 return __const_this->_M_find_tr(__k)._M_const_cast();
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
const_iterator
_M_find_tr(const _Kt& __k) const
{
 auto __j = _M_lower_bound_tr(__k);
 if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
   __j = end();
 return __j;
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
size_type
_M_count_tr(const _Kt& __k) const
{
 auto __p = _M_equal_range_tr(__k);
 return std::distance(__p.first, __p.second);
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
iterator
_M_lower_bound_tr(const _Kt& __k)
{
 const _Rb_tree* __const_this = this;
 return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
const_iterator
_M_lower_bound_tr(const _Kt& __k) const
{
 auto __x = _M_begin();
 auto __y = _M_end();
 while (__x != 0)
   if (!_M_impl._M_key_compare(_S_key(__x), __k))
     {
__y = __x;
__x = _S_left(__x);
     }
   else
     __x = _S_right(__x);
 return const_iterator(__y);
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
iterator
_M_upper_bound_tr(const _Kt& __k)
{
 const _Rb_tree* __const_this = this;
 return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
const_iterator
_M_upper_bound_tr(const _Kt& __k) const
{
 auto __x = _M_begin();
 auto __y = _M_end();
 while (__x != 0)
   if (_M_impl._M_key_compare(__k, _S_key(__x)))
     {
__y = __x;
__x = _S_left(__x);
     }
   else
     __x = _S_right(__x);
 return const_iterator(__y);
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
pair<iterator, iterator>
_M_equal_range_tr(const _Kt& __k)
{
 const _Rb_tree* __const_this = this;
 auto __ret = __const_this->_M_equal_range_tr(__k);
 return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
}

    template<typename _Kt,
      typename _Req = __has_is_transparent_t<_Compare, _Kt>>
pair<const_iterator, const_iterator>
_M_equal_range_tr(const _Kt& __k) const
{
 auto __low = _M_lower_bound_tr(__k);
 auto __high = __low;
 auto& __cmp = _M_impl._M_key_compare;
 while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
   ++__high;
 return { __low, __high };
}
1403#endif

    // Debugging.
    bool
    __rb_verify() const;

1409#if __cplusplus201703L >= 201103L
    _Rb_tree&
    operator=(_Rb_tree&&)
    noexcept(_Alloc_traits::_S_nothrow_move()
      && is_nothrow_move_assignable<_Compare>::value);

    template<typename _Iterator>
void
_M_assign_unique(_Iterator, _Iterator);

    template<typename _Iterator>
void
_M_assign_equal(_Iterator, _Iterator);

  private:
    // Move elements from container with equal allocator.
    void
    _M_move_data(_Rb_tree& __x, true_type)
    { _M_impl._M_move_data(__x._M_impl); }

    // Move elements from container with possibly non-equal allocator,
    // which might result in a copy not a move.
    void
    _M_move_data(_Rb_tree&, false_type);

    // Move assignment from container with equal allocator.
    void
    _M_move_assign(_Rb_tree&, true_type);

    // Move assignment from container with possibly non-equal allocator,
    // which might result in a copy not a move.
    void
    _M_move_assign(_Rb_tree&, false_type);
1442#endif

1444#if __cplusplus201703L > 201402L
  public:
    /// Re-insert an extracted node.
    insert_return_type
    _M_reinsert_node_unique(node_type&& __nh)
    {
insert_return_type __ret;
if (__nh.empty())
 __ret.position = end();
else
 {
   __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);

   auto __res = _M_get_insert_unique_pos(__nh._M_key());
   if (__res.second)
     {
__ret.position
  = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
__nh._M_ptr = nullptr;
__ret.inserted = true;
     }
   else
     {
__ret.node = std::move(__nh);
__ret.position = iterator(__res.first);
__ret.inserted = false;
     }
 }
return __ret;
    }

    /// Re-insert an extracted node.
    iterator
    _M_reinsert_node_equal(node_type&& __nh)
    {
iterator __ret;
if (__nh.empty())
 __ret = end();
else
 {
   __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
   auto __res = _M_get_insert_equal_pos(__nh._M_key());
   if (__res.second)
     __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
   else
     __ret = _M_insert_equal_lower_node(__nh._M_ptr);
   __nh._M_ptr = nullptr;
 }
return __ret;
    }

    /// Re-insert an extracted node.
    iterator
    _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
    {
iterator __ret;
if (__nh.empty())
 __ret = end();
else
 {
   __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
   auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
   if (__res.second)
     {
__ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
__nh._M_ptr = nullptr;
     }
   else
     __ret = iterator(__res.first);
 }
return __ret;
    }

    /// Re-insert an extracted node.
    iterator
    _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
    {
iterator __ret;
if (__nh.empty())
 __ret = end();
else
 {
   __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
   auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
   if (__res.second)
     __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
   else
     __ret = _M_insert_equal_lower_node(__nh._M_ptr);
   __nh._M_ptr = nullptr;
 }
return __ret;
    }

    /// Extract a node.
    node_type
    extract(const_iterator __pos)
    {
auto __ptr = _Rb_tree_rebalance_for_erase(
   __pos._M_const_cast()._M_node, _M_impl._M_header);
--_M_impl._M_node_count;
return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
    }

    /// Extract a node.
    node_type
    extract(const key_type& __k)
    {
node_type __nh;
auto __pos = find(__k);
if (__pos != end())
 __nh = extract(const_iterator(__pos));
return __nh;
    }

    template<typename _Compare2>
using _Compatible_tree
 = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;

    template<typename, typename>
friend class _Rb_tree_merge_helper;

    /// Merge from a compatible container into one with unique keys.
    template<typename _Compare2>
void
_M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
{
 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
   {
     auto __pos = __i++;
     auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
     if (__res.second)
{
  auto& __src_impl = _Merge_helper::_S_get_impl(__src);
  auto __ptr = _Rb_tree_rebalance_for_erase(
      __pos._M_node, __src_impl._M_header);
  --__src_impl._M_node_count;
  _M_insert_node(__res.first, __res.second,
		 static_cast<_Link_type>(__ptr));
}
   }
}

    /// Merge from a compatible container into one with equivalent keys.
    template<typename _Compare2>
void
_M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
{
 using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
   {
     auto __pos = __i++;
     auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
     if (__res.second)
{
  auto& __src_impl = _Merge_helper::_S_get_impl(__src);
  auto __ptr = _Rb_tree_rebalance_for_erase(
      __pos._M_node, __src_impl._M_header);
  --__src_impl._M_node_count;
  _M_insert_node(__res.first, __res.second,
		 static_cast<_Link_type>(__ptr));
}
   }
}
1608#endif // C++17

    friend bool
    operator==(const _Rb_tree& __x, const _Rb_tree& __y)
    {
return __x.size() == __y.size()
 && std::equal(__x.begin(), __x.end(), __y.begin());
    }

1617#if __cpp_lib_three_way_comparison
    friend auto
    operator<=>(const _Rb_tree& __x, const _Rb_tree& __y)
    {
if constexpr (requires { typename __detail::__synth3way_t<_Val>; })
 return std::lexicographical_compare_three_way(__x.begin(), __x.end(),
					__y.begin(), __y.end(),
					__detail::__synth3way);
    }
1626#else
    friend bool
    operator<(const _Rb_tree& __x, const _Rb_tree& __y)
    {
return std::lexicographical_compare(__x.begin(), __x.end(),
			    __y.begin(), __y.end());
    }

    friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
    operator!=(const _Rb_tree& __x, const _Rb_tree& __y)
    { return !(__x == __y); }

    friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
    operator>(const _Rb_tree& __x, const _Rb_tree& __y)
    { return __y < __x; }

    friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
    operator<=(const _Rb_tree& __x, const _Rb_tree& __y)
    { return !(__y < __x); }

    friend bool _GLIBCXX_DEPRECATED__attribute__ ((__deprecated__))
    operator>=(const _Rb_tree& __x, const _Rb_tree& __y)
    { return !(__x < __y); }
1649#endif
  };

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  inline void
  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
  { __x.swap(__y); }

1659#if __cplusplus201703L >= 201103L
template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  void
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_move_data(_Rb_tree& __x, false_type)
  {
    if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
_M_move_data(__x, true_type());
    else
{
 _Alloc_node __an(*this);
 auto __lbd =
   [&__an](const value_type& __cval)
   {
     auto& __val = const_cast<value_type&>(__cval);
     return __an(std::move_if_noexcept(__val));
   };
 _M_root() = _M_copy(__x, __lbd);
}
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  inline void
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_move_assign(_Rb_tree& __x, true_type)
  {
    clear();
    if (__x._M_root() != nullptr)
_M_move_data(__x, true_type());
    std::__alloc_on_move(_M_get_Node_allocator(),
	   __x._M_get_Node_allocator());
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  void
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_move_assign(_Rb_tree& __x, false_type)
  {
    if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
return _M_move_assign(__x, true_type{});

    // Try to move each node reusing existing nodes and copying __x nodes
    // structure.
    _Reuse_or_alloc_node __roan(*this);
    _M_impl._M_reset();
    if (__x._M_root() != nullptr)
{
 auto __lbd =
   [&__roan](const value_type& __cval)
   {
     auto& __val = const_cast<value_type&>(__cval);
     return __roan(std::move(__val));
   };
 _M_root() = _M_copy(__x, __lbd);
 __x.clear();
}
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  operator=(_Rb_tree&& __x)
  noexcept(_Alloc_traits::_S_nothrow_move()
    && is_nothrow_move_assignable<_Compare>::value)
  {
    _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
    _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
    return *this;
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  template<typename _Iterator>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_assign_unique(_Iterator __first, _Iterator __last)
    {
_Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
for (; __first != __last; ++__first)
 _M_insert_unique_(end(), *__first, __roan);
    }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  template<typename _Iterator>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_assign_equal(_Iterator __first, _Iterator __last)
    {
_Reuse_or_alloc_node __roan(*this);
_M_impl._M_reset();
for (; __first != __last; ++__first)
 _M_insert_equal_(end(), *__first, __roan);
    }
1758#endif

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  operator=(const _Rb_tree& __x)
  {
    if (this != &__x)
{
 // Note that _Key may be a constant type.
1769#if __cplusplus201703L >= 201103L
 if (_Alloc_traits::_S_propagate_on_copy_assign())
   {
     auto& __this_alloc = this->_M_get_Node_allocator();
     auto& __that_alloc = __x._M_get_Node_allocator();
     if (!_Alloc_traits::_S_always_equal()
  && __this_alloc != __that_alloc)
{
  // Replacement allocator cannot free existing storage, we need
  // to erase nodes first.
  clear();
  std::__alloc_on_copy(__this_alloc, __that_alloc);
}
   }
1783#endif

 _Reuse_or_alloc_node __roan(*this);
 _M_impl._M_reset();
 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 if (__x._M_root() != 0)
   _M_root() = _M_copy(__x, __roan);
}

    return *this;
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
1797#if __cplusplus201703L >= 201103L
  template<typename _Arg, typename _NodeGen>
1799#else
  template<typename _NodeGen>
1801#endif
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_insert_(_Base_ptr __x, _Base_ptr __p,
1805#if __cplusplus201703L >= 201103L
 _Arg&& __v,
1807#else
 const _Val& __v,
1809#endif
 _NodeGen& __node_gen)
    {
bool __insert_left = (__x != 0 || __p == _M_end()
	      || _M_impl._M_key_compare(_KeyOfValue()(__v),
					_S_key(__p)));

_Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));

_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
		      this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
    }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
1826#if __cplusplus201703L >= 201103L
  template<typename _Arg>
1828#endif
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1831#if __cplusplus201703L >= 201103L
  _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1833#else
  _M_insert_lower(_Base_ptr __p, const _Val& __v)
1835#endif
  {
    bool __insert_left = (__p == _M_end()
	    || !_M_impl._M_key_compare(_S_key(__p),
				       _KeyOfValue()(__v)));

    _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));

    _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
		    this->_M_impl._M_header);
    ++_M_impl._M_node_count;
    return iterator(__z);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
1851#if __cplusplus201703L >= 201103L
  template<typename _Arg>
1853#endif
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1856#if __cplusplus201703L >= 201103L
  _M_insert_equal_lower(_Arg&& __v)
1858#else
  _M_insert_equal_lower(const _Val& __v)
1860#endif
  {
    _Link_type __x = _M_begin();
    _Base_ptr __y = _M_end();
    while (__x != 0)
{
 __y = __x;
 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
_S_left(__x) : _S_right(__x);
}
    return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));
  }

template<typename _Key, typename _Val, typename _KoV,
  typename _Compare, typename _Alloc>
  template<typename _NodeGen>
    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
    _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
    {
// Structural copy. __x and __p must be non-null.
_Link_type __top = _M_clone_node(__x, __node_gen);
__top->_M_parent = __p;

__trytry
 {
   if (__x->_M_right)
     __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
   __p = __top;
   __x = _S_left(__x);

   while (__x != 0)
     {
_Link_type __y = _M_clone_node(__x, __node_gen);
__p->_M_left = __y;
__y->_M_parent = __p;
if (__x->_M_right)
  __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
__p = __y;
__x = _S_left(__x);
     }
 }
__catch(...)catch(...)
 {
   _M_erase(__top);
   __throw_exception_againthrow;
 }
return __top;
    }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  void
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_erase(_Link_type __x)
  {
    // Erase without rebalancing.
    while (__x != 0)
{
 _M_erase(_S_right(__x));
 _Link_type __y = _S_left(__x);
 _M_drop_node(__x);
 __x = __y;
}
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
      _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_lower_bound(_Link_type __x, _Base_ptr __y,
   const _Key& __k)
  {
    while (__x != 0)
if (!_M_impl._M_key_compare(_S_key(__x), __k))
 __y = __x, __x = _S_left(__x);
else
 __x = _S_right(__x);
    return iterator(__y);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
      _Compare, _Alloc>::const_iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
   const _Key& __k) const
  {
    while (__x != 0)
if (!_M_impl._M_key_compare(_S_key(__x), __k))
 __y = __x, __x = _S_left(__x);
else
 __x = _S_right(__x);
    return const_iterator(__y);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
      _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_upper_bound(_Link_type __x, _Base_ptr __y,
   const _Key& __k)
  {
    while (__x != 0)
if (_M_impl._M_key_compare(__k, _S_key(__x)))
 __y = __x, __x = _S_left(__x);
else
 __x = _S_right(__x);
    return iterator(__y);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
      _Compare, _Alloc>::const_iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
   const _Key& __k) const
  {
    while (__x != 0)
if (_M_impl._M_key_compare(__k, _S_key(__x)))
 __y = __x, __x = _S_left(__x);
else
 __x = _S_right(__x);
    return const_iterator(__y);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::iterator,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::iterator>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  equal_range(const _Key& __k)
  {
    _Link_type __x = _M_begin();
    _Base_ptr __y = _M_end();
    while (__x != 0)
{
 if (_M_impl._M_key_compare(_S_key(__x), __k))
   __x = _S_right(__x);
 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
   __y = __x, __x = _S_left(__x);
 else
   {
     _Link_type __xu(__x);
     _Base_ptr __yu(__y);
     __y = __x, __x = _S_left(__x);
     __xu = _S_right(__xu);
     return pair<iterator,
	  iterator>(_M_lower_bound(__x, __y, __k),
		    _M_upper_bound(__xu, __yu, __k));
   }
}
    return pair<iterator, iterator>(iterator(__y),
		      iterator(__y));
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::const_iterator,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::const_iterator>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  equal_range(const _Key& __k) const
  {
    _Const_Link_type __x = _M_begin();
    _Const_Base_ptr __y = _M_end();
    while (__x != 0)
{
 if (_M_impl._M_key_compare(_S_key(__x), __k))
   __x = _S_right(__x);
 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
   __y = __x, __x = _S_left(__x);
 else
   {
     _Const_Link_type __xu(__x);
     _Const_Base_ptr __yu(__y);
     __y = __x, __x = _S_left(__x);
     __xu = _S_right(__xu);
     return pair<const_iterator,
	  const_iterator>(_M_lower_bound(__x, __y, __k),
			  _M_upper_bound(__xu, __yu, __k));
   }
}
    return pair<const_iterator, const_iterator>(const_iterator(__y),
				  const_iterator(__y));
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  void
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  swap(_Rb_tree& __t)
  _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)noexcept(__is_nothrow_swappable<_Compare>::value)
  {
    if (_M_root() == 0)
{
 if (__t._M_root() != 0)
   _M_impl._M_move_data(__t._M_impl);
}
    else if (__t._M_root() == 0)
__t._M_impl._M_move_data(_M_impl);
    else
{
 std::swap(_M_root(),__t._M_root());
 std::swap(_M_leftmost(),__t._M_leftmost());
 std::swap(_M_rightmost(),__t._M_rightmost());

 _M_root()->_M_parent = _M_end();
 __t._M_root()->_M_parent = __t._M_end();
 std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
}
    // No need to swap header's color as it does not change.
    std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);

    _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
		__t._M_get_Node_allocator());
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_get_insert_unique_pos(const key_type& __k)
  {
    typedef pair<_Base_ptr, _Base_ptr> _Res;
    _Link_type __x = _M_begin();
    _Base_ptr __y = _M_end();
    bool __comp = true;
    while (__x != 0)
{
 __y = __x;
 __comp = _M_impl._M_key_compare(__k, _S_key(__x));
 __x = __comp ? _S_left(__x) : _S_right(__x);
}
    iterator __j = iterator(__y);
    if (__comp)
{
 if (__j == begin())
   return _Res(__x, __y);
 else
   --__j;
}
    if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
return _Res(__x, __y);
    return _Res(__j._M_node, 0);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_get_insert_equal_pos(const key_type& __k)
  {
    typedef pair<_Base_ptr, _Base_ptr> _Res;
    _Link_type __x = _M_begin();
    _Base_ptr __y = _M_end();
    while (__x != 0)
{
 __y = __x;
 __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
_S_left(__x) : _S_right(__x);
}
    return _Res(__x, __y);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
2140#if __cplusplus201703L >= 201103L
  template<typename _Arg>
2142#endif
  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::iterator, bool>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2146#if __cplusplus201703L >= 201103L
  _M_insert_unique(_Arg&& __v)
2148#else
  _M_insert_unique(const _Val& __v)
2150#endif
  {
    typedef pair<iterator, bool> _Res;
    pair<_Base_ptr, _Base_ptr> __res
= _M_get_insert_unique_pos(_KeyOfValue()(__v));

    if (__res.second)
{
 _Alloc_node __an(*this);
 return _Res(_M_insert_(__res.first, __res.second,
		 _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v), __an),
      true);
}

    return _Res(iterator(__res.first), false);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
2169#if __cplusplus201703L >= 201103L
  template<typename _Arg>
2171#endif
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2174#if __cplusplus201703L >= 201103L
  _M_insert_equal(_Arg&& __v)
2176#else
  _M_insert_equal(const _Val& __v)
2178#endif
  {
    pair<_Base_ptr, _Base_ptr> __res
= _M_get_insert_equal_pos(_KeyOfValue()(__v));
    _Alloc_node __an(*this);
    return _M_insert_(__res.first, __res.second,
	_GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v), __an);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_get_insert_hint_unique_pos(const_iterator __position,
		  const key_type& __k)
  {
    iterator __pos = __position._M_const_cast();
    typedef pair<_Base_ptr, _Base_ptr> _Res;

    // end()
    if (__pos._M_node == _M_end())
{
 if (size() > 0
     && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
   return _Res(0, _M_rightmost());
 else
   return _M_get_insert_unique_pos(__k);
}
    else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
{
 // First, try before...
 iterator __before = __pos;
 if (__pos._M_node == _M_leftmost()) // begin()
   return _Res(_M_leftmost(), _M_leftmost());
 else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
   {
     if (_S_right(__before._M_node) == 0)
return _Res(0, __before._M_node);
     else
return _Res(__pos._M_node, __pos._M_node);
   }
 else
   return _M_get_insert_unique_pos(__k);
}
    else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
{
 // ... then try after.
 iterator __after = __pos;
 if (__pos._M_node == _M_rightmost())
   return _Res(0, _M_rightmost());
 else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
   {
     if (_S_right(__pos._M_node) == 0)
return _Res(0, __pos._M_node);
     else
return _Res(__after._M_node, __after._M_node);
   }
 else
   return _M_get_insert_unique_pos(__k);
}
    else
// Equivalent keys.
return _Res(__pos._M_node, 0);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
2248#if __cplusplus201703L >= 201103L
  template<typename _Arg, typename _NodeGen>
2250#else
  template<typename _NodeGen>
2252#endif
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_insert_unique_(const_iterator __position,
2256#if __cplusplus201703L >= 201103L
	_Arg&& __v,
2258#else
	const _Val& __v,
2260#endif
	_NodeGen& __node_gen)
  {
    pair<_Base_ptr, _Base_ptr> __res
= _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));

    if (__res.second)
return _M_insert_(__res.first, __res.second,
	  _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v),
	  __node_gen);
    return iterator(__res.first);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
	   _Compare, _Alloc>::_Base_ptr>
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
  {
    iterator __pos = __position._M_const_cast();
    typedef pair<_Base_ptr, _Base_ptr> _Res;

    // end()
    if (__pos._M_node == _M_end())
{
 if (size() > 0
     && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
   return _Res(0, _M_rightmost());
 else
   return _M_get_insert_equal_pos(__k);
}
    else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
{
 // First, try before...
 iterator __before = __pos;
 if (__pos._M_node == _M_leftmost()) // begin()
   return _Res(_M_leftmost(), _M_leftmost());
 else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
   {
     if (_S_right(__before._M_node) == 0)
return _Res(0, __before._M_node);
     else
return _Res(__pos._M_node, __pos._M_node);
   }
 else
   return _M_get_insert_equal_pos(__k);
}
    else
{
 // ... then try after.
 iterator __after = __pos;
 if (__pos._M_node == _M_rightmost())
   return _Res(0, _M_rightmost());
 else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
   {
     if (_S_right(__pos._M_node) == 0)
return _Res(0, __pos._M_node);
     else
return _Res(__after._M_node, __after._M_node);
   }
 else
   return _Res(0, 0);
}
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
2330#if __cplusplus201703L >= 201103L
  template<typename _Arg, typename _NodeGen>
2332#else
  template<typename _NodeGen>
2334#endif
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_insert_equal_(const_iterator __position,
2338#if __cplusplus201703L >= 201103L
       _Arg&& __v,
2340#else
       const _Val& __v,
2342#endif
       _NodeGen& __node_gen)
    {
pair<_Base_ptr, _Base_ptr> __res
 = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));

if (__res.second)
 return _M_insert_(__res.first, __res.second,
	    _GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v),
	    __node_gen);

return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)std::forward<_Arg>(__v));
    }

2356#if __cplusplus201703L >= 201103L
template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
  {
    bool __insert_left = (__x != 0 || __p == _M_end()
	    || _M_impl._M_key_compare(_S_key(__z),
				      _S_key(__p)));

    _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
		    this->_M_impl._M_header);
    ++_M_impl._M_node_count;
    return iterator(__z);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
  {
    bool __insert_left = (__p == _M_end()
	    || !_M_impl._M_key_compare(_S_key(__p),
				       _S_key(__z)));

    _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
		    this->_M_impl._M_header);
    ++_M_impl._M_node_count;
    return iterator(__z);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_insert_equal_lower_node(_Link_type __z)
  {
    _Link_type __x = _M_begin();
    _Base_ptr __y = _M_end();
    while (__x != 0)
{
 __y = __x;
 __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
_S_left(__x) : _S_right(__x);
}
    return _M_insert_lower_node(__y, __z);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  template<typename... _Args>
    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
	     _Compare, _Alloc>::iterator, bool>
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_emplace_unique(_Args&&... __args)
    {
_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);

__trytry
 {
   typedef pair<iterator, bool> _Res;
   auto __res = _M_get_insert_unique_pos(_S_key(__z));
   if (__res.second)
     return _Res(_M_insert_node(__res.first, __res.second, __z), true);

   _M_drop_node(__z);
   return _Res(iterator(__res.first), false);
 }
__catch(...)catch(...)
 {
   _M_drop_node(__z);
   __throw_exception_againthrow;
 }
    }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  template<typename... _Args>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_emplace_equal(_Args&&... __args)
    {
_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);

__trytry
 {
   auto __res = _M_get_insert_equal_pos(_S_key(__z));
   return _M_insert_node(__res.first, __res.second, __z);
 }
__catch(...)catch(...)
 {
   _M_drop_node(__z);
   __throw_exception_againthrow;
 }
    }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  template<typename... _Args>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
    {
_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);

__trytry
 {
   auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));

   if (__res.second)
     return _M_insert_node(__res.first, __res.second, __z);

   _M_drop_node(__z);
   return iterator(__res.first);
 }
__catch(...)catch(...)
 {
   _M_drop_node(__z);
   __throw_exception_againthrow;
 }
    }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  template<typename... _Args>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
    {
_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);

__trytry
 {
   auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));

   if (__res.second)
     return _M_insert_node(__res.first, __res.second, __z);

   return _M_insert_equal_lower_node(__z);
 }
__catch(...)catch(...)
 {
   _M_drop_node(__z);
   __throw_exception_againthrow;
 }
    }
2504#endif


template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  void
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_erase_aux(const_iterator __position)
  {
    _Link_type __y =
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
		(const_cast<_Base_ptr>(__position._M_node),
		 this->_M_impl._M_header));
    _M_drop_node(__y);
    --_M_impl._M_node_count;
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  void
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  _M_erase_aux(const_iterator __first, const_iterator __last)
  {
    if (__first == begin() && __last == end())
clear();
    else
while (__first != __last)
 _M_erase_aux(__first++);
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  erase(const _Key& __x)
  {
    pair<iterator, iterator> __p = equal_range(__x);
    const size_type __old_size = size();
    _M_erase_aux(__p.first, __p.second);
    return __old_size - size();
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
      _Compare, _Alloc>::iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  find(const _Key& __k)
  {
    iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
    return (__j == end()
     || _M_impl._M_key_compare(__k,
			_S_key(__j._M_node))) ? end() : __j;
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue,
      _Compare, _Alloc>::const_iterator
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  find(const _Key& __k) const
  {
    const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
    return (__j == end()
     || _M_impl._M_key_compare(__k,
			_S_key(__j._M_node))) ? end() : __j;
  }

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  count(const _Key& __k) const
  {
    pair<const_iterator, const_iterator> __p = equal_range(__k);
    const size_type __n = std::distance(__p.first, __p.second);
    return __n;
  }

_GLIBCXX_PURE__attribute__ ((__pure__)) unsigned int
_Rb_tree_black_count(const _Rb_tree_node_base* __node,
       const _Rb_tree_node_base* __root) throw ();

template<typename _Key, typename _Val, typename _KeyOfValue,
  typename _Compare, typename _Alloc>
  bool
  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
  {
    if (_M_impl._M_node_count == 0 || begin() == end())
return _M_impl._M_node_count == 0 && begin() == end()
      && this->_M_impl._M_header._M_left == _M_end()
      && this->_M_impl._M_header._M_right == _M_end();

    unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
    for (const_iterator __it = begin(); __it != end(); ++__it)
{
 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
 _Const_Link_type __L = _S_left(__x);
 _Const_Link_type __R = _S_right(__x);

 if (__x->_M_color == _S_red)
   if ((__L && __L->_M_color == _S_red)
|| (__R && __R->_M_color == _S_red))
     return false;

 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
   return false;
 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
   return false;

 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
   return false;
}

    if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
return false;
    if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
return false;
    return true;
  }

2625#if __cplusplus201703L > 201402L
// Allow access to internals of compatible _Rb_tree specializations.
template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
  typename _Alloc, typename _Cmp2>
  struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
		 _Cmp2>
  {
  private:
    friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;

    static auto&
    _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
    { return __tree._M_impl; }
  };
2639#endif // C++17

2641_GLIBCXX_END_NAMESPACE_VERSION
2642} // namespace

2644#endif