Line data    Source code

       1              : /*
       2              :  * SPDX-License-Identifier: GPL-3.0-only
       3              :  * MuseScore-Studio-CLA-applies
       4              :  *
       5              :  * MuseScore Studio
       6              :  * Music Composition & Notation
       7              :  *
       8              :  * Copyright (C) 2021 MuseScore Limited and others
       9              :  *
      10              :  * This program is free software: you can redistribute it and/or modify
      11              :  * it under the terms of the GNU General Public License version 3 as
      12              :  * published by the Free Software Foundation.
      13              :  *
      14              :  * This program is distributed in the hope that it will be useful,
      15              :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      16              :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      17              :  * GNU General Public License for more details.
      18              :  *
      19              :  * You should have received a copy of the GNU General Public License
      20              :  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
      21              :  */
      22              : 
      23              : #pragma once
      24              : 
      25              : #include <vector>
      26              : 
      27              : #include "global/allocator.h"
      28              : #include "types/string.h"
      29              : #include "../types/types.h"
      30              : 
      31              : namespace mu::engraving {
      32              : class BspTreeVisitor;
      33              : class InsertItemBspTreeVisitor;
      34              : class RemoveItemBspTreeVisitor;
      35              : class FindItemBspTreeVisitor;
      36              : 
      37              : class EngravingItem;
      38              : 
      39              : //---------------------------------------------------------
      40              : //   BspTree
      41              : //    binary space partitioning
      42              : //---------------------------------------------------------
      43              : 
      44              : class BspTree
      45              : {
      46              : public:
      47              :     struct Node {
      48              :         enum class Type : char {
      49              :             HORIZONTAL, VERTICAL, LEAF
      50              :         };
      51              :         union {
      52              :             double offset;
      53              :             int leafIndex;
      54              :         };
      55              :         Type type;
      56              :     };
      57              : private:
      58              : 
      59              :     void initialize(const RectF& rect, int depth, int index);
      60              :     void climbTree(BspTreeVisitor* visitor, const PointF& pos, int index = 0);
      61              :     void climbTree(BspTreeVisitor* visitor, const RectF& rect, int index = 0);
      62              : 
      63              :     void nearestNeighbor(const PointF& pos, EngravingItem** bestItem, double& bestDistance, int nodeIndex = 0);
      64              : 
      65              :     RectF rectForIndex(int index) const;
      66              : 
      67              :     unsigned int m_depth = 0;
      68              :     std::vector<Node> m_nodes;
      69              :     std::vector<std::vector<EngravingItem*> > m_leaves;
      70              :     int m_leafCnt = 0;
      71              :     RectF m_rect;
      72              : 
      73              : public:
      74              :     BspTree();
      75              : 
      76              :     void initialize(const RectF& rect, int depth);
      77              :     void clear();
      78              : 
      79              :     void insert(EngravingItem* item);
      80              :     void remove(EngravingItem* item);
      81              : 
      82              :     std::vector<EngravingItem*> items(const RectF& rect);
      83              :     std::vector<EngravingItem*> items(const PointF& pos);
      84              : 
      85              :     EngravingItem* nearestNeighbor(const PointF& pos);
      86              : 
      87              :     int leafCount() const { return m_leafCnt; }
      88        11204 :     inline int firstChildIndex(int index) const { return index * 2 + 1; }
      89              : 
      90            0 :     inline int parentIndex(int index) const
      91              :     {
      92            0 :         return index > 0 ? ((index & 1) ? ((index - 1) / 2) : ((index - 2) / 2)) : -1;
      93              :     }
      94              : 
      95              : #ifndef NDEBUG
      96              :     String debug(int index) const;
      97              : #endif
      98              : };
      99              : 
     100              : //---------------------------------------------------------
     101              : //   BspTreeVisitor
     102              : //---------------------------------------------------------
     103              : 
     104              : class BspTreeVisitor
     105              : {
     106            0 :     OBJECT_ALLOCATOR(engraving, BspTreeVisitor)
     107              : public:
     108          418 :     virtual ~BspTreeVisitor() {}
     109              :     virtual void visit(std::vector<EngravingItem*>& items) = 0;
     110              : };
     111              : }