bsp.hpp

Go to the documentation of this file.

/* BSD 3-Clause License
 *
 * Copyright © 2008-2025, Jice and the libtcod contributors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * 3. Neither the name of the copyright holder nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
// clang-format off
#pragma once
#ifndef TCOD_BSP_HPP_
#define TCOD_BSP_HPP_
 
#include <utility>
 
#include "bsp.h"
#include "list.hpp"
#include "mersenne.hpp"
#include "tree.hpp"

 
class TCODBsp;
 
class TCODLIB_API ITCODBspCallback {
public :
  virtual ~ITCODBspCallback() {}
  virtual bool visitNode(TCODBsp *node, void *userData) = 0;
};

 
// clang-format on
class TCODLIB_API TCODBsp : public TCODTree {
 public:
  int x{}, y{}, w{}, h{};  //
  int position{};  // position of splitting
  bool horizontal{};  // horizontal splitting ?
  uint8_t level{};  // level in the tree

  TCODBsp() : level{0} {}
  TCODBsp(int x, int y, int w, int h) : x{x}, y{y}, w{w}, h{h}, level{0} {}
 
  TCODBsp(const TCODBsp&) = delete;
  TCODBsp& operator=(const TCODBsp&) = delete;
  TCODBsp(TCODBsp&& rhs) noexcept { (*this) = std::move(rhs); };
  TCODBsp& operator=(TCODBsp&& rhs) noexcept {
    swap(*this, rhs);
    return *this;
  };
 
  friend void swap(TCODBsp& lhs, TCODBsp& rhs) noexcept {
    std::swap(lhs.x, rhs.x);
    std::swap(lhs.y, rhs.y);
    std::swap(lhs.w, rhs.w);
    std::swap(lhs.h, rhs.h);
    std::swap(lhs.position, rhs.position);
    std::swap(lhs.horizontal, rhs.horizontal);
    std::swap(lhs.level, rhs.level);
    std::swap(lhs.next, rhs.next);
    std::swap(lhs.father, rhs.father);
    std::swap(lhs.sons, rhs.sons);
  };
 

  virtual ~TCODBsp();
 
  // clang-format off
  void removeSons();

  void splitOnce(bool horizontal, int position);

  void splitRecursive(TCODRandom *randomizer, int nb, int minHSize, int minVSize, float maxHRatio, float maxVRatio);

  void resize(int x,int y, int w, int h);


  TCODBsp *getLeft() const {
    return static_cast<TCODBsp*>(sons);
  }
  TCODBsp *getRight() const {
    return sons ? static_cast<TCODBsp*>(sons->next) : NULL;
  }
  TCODBsp *getFather() const {
    return static_cast<TCODBsp*>(father);
  }

  bool isLeaf() const { return sons == NULL ; }

  bool contains(int x, int y) const;

  TCODBsp *findNode(int x, int y);

  bool traversePreOrder(ITCODBspCallback* listener, void* userData);
  bool traverseInOrder(ITCODBspCallback* listener, void* userData);
  bool traversePostOrder(ITCODBspCallback* listener, void* userData);
  bool traverseLevelOrder(ITCODBspCallback* listener, void* userData);
  bool traverseInvertedLevelOrder(ITCODBspCallback* listener, void* userData);
  // clang-format on

  template <typename VisitorFunc>
  bool traversePreOrder(VisitorFunc&& visitor) {
    auto visitor_instance = LambdaVisitor<VisitorFunc>{};
    return traversePreOrder(&visitor_instance, static_cast<void*>(&visitor));
  }

  template <typename VisitorFunc>
  bool traverseInOrder(VisitorFunc&& visitor) {
    auto visitor_instance = LambdaVisitor<VisitorFunc>{};
    return traverseInOrder(&visitor_instance, static_cast<void*>(&visitor));
  }

  template <typename VisitorFunc>
  bool traversePostOrder(VisitorFunc&& visitor) {
    auto visitor_instance = LambdaVisitor<VisitorFunc>{};
    return traversePostOrder(&visitor_instance, static_cast<void*>(&visitor));
  }

  template <typename VisitorFunc>
  bool traverseLevelOrder(VisitorFunc&& visitor) {
    auto visitor_instance = LambdaVisitor<VisitorFunc>{};
    return traverseLevelOrder(&visitor_instance, static_cast<void*>(&visitor));
  }

  template <typename VisitorFunc>
  bool traverseInvertedLevelOrder(VisitorFunc&& visitor) {
    auto visitor_instance = LambdaVisitor<VisitorFunc>{};
    return traverseInvertedLevelOrder(&visitor_instance, static_cast<void*>(&visitor));
  }
 
 protected:
  TCODBsp(TCODBsp* father, bool left);
 
 private:

  template <typename VisitorFunc>
  class LambdaVisitor final : public ITCODBspCallback {

    bool visitNode(TCODBsp* node, void* callback) override {
      if constexpr (std::is_same_v<typename std::invoke_result<VisitorFunc, TCODBsp&>::type, void>) {
        (*static_cast<VisitorFunc*>(callback))(*node);
        return true;
      } else {
        return ((*static_cast<VisitorFunc*>(callback))(*node));
      }
    }
  };
};
#endif  // TCOD_BSP_HPP_