SweepStructure.h

Go to the documentation of this file.

// -*- lsst-c++ -*-

/* 
 * LSST Data Management System
 * Copyright 2008, 2009, 2010 LSST Corporation.
 * 
 * This product includes software developed by the
 * LSST Project (http://www.lsst.org/).
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the LSST License Statement and 
 * the GNU General Public License along with this program.  If not, 
 * see <http://www.lsstcorp.org/LegalNotices/>.
 */

#ifndef LSST_AP_MATCH_DETAIL_SWEEPSTRUCTURE_H
#define LSST_AP_MATCH_DETAIL_SWEEPSTRUCTURE_H

#include <vector>

#include "../BBox.h"
#include "../../utils/Arena.h"


namespace lsst { namespace ap { namespace match { namespace detail {

// -- Interval tree nodes ----

enum Color {
    BLACK = 0, RED
};

struct CartesianNode {
    CartesianNode *link[2];
    Color color;
    double reach;
    double minCoord0;
    double maxCoord0;
    BBox *bbox;

    inline CartesianNode();
    inline CartesianNode(BBox *b);
    inline ~CartesianNode();
};

inline bool lessThan(CartesianNode const *left, CartesianNode const *right);

inline bool operator<(std::pair<double, CartesianNode *> const &left,
                      std::pair<double, CartesianNode *> const &right);


struct SphericalNode {
    SphericalNode *link[2];
    Color color;
    unsigned int foundBy;
    double reach;
    double minCoord0;
    double maxCoord0;
    BBox *bbox;
    SphericalNode *twin;

    inline SphericalNode();
    inline SphericalNode(BBox *b, double minC0, double maxC0);
    inline ~SphericalNode();

    inline bool markFound(unsigned int searchId);
};

inline bool lessThan(SphericalNode const *left, SphericalNode const *right);

inline bool operator<(std::pair<double, SphericalNode *> const &left,
                      std::pair<double, SphericalNode *> const &right);


// -- Sweep structures ----

template <typename Node>
class SweepStructure {
public:
    SweepStructure() : _arena(), _root(0), _heap() { }
    virtual ~SweepStructure();

    inline size_t size() const;
    inline bool empty() const;
    inline size_t getNumBytes() const;

    virtual bool isValid() const;

protected:
    typedef std::pair<double, Node *> HeapEntry;

    void _insert(Node *i);
    void _insert(BBox *b);
    void _remove(Node *n);
    void _grow(typename std::vector<HeapEntry>::size_type n);

    lsst::ap::utils::Arena<Node> _arena;
    Node *_root; 
    std::vector<HeapEntry> _heap; 

private:
    // Disable copy construction and assignment
    SweepStructure(SweepStructure const &);
    SweepStructure & operator = (SweepStructure const &);

    // Low-level implementation
    static inline double _reach(Node const *n);
    inline Node * _rotate(Node *n, int dir);
    inline Node * _doubleRotate(Node *n, int dir);

    // Invariant checks
    static bool _isBinarySearchTree(Node const *n);
    static bool _isRedChildBlack(Node const *n);
    static bool _isBalanced(Node const *n, int numBlack);
    static double _checkReach(Node const *n);
    bool _isBalanced() const;
    bool _isIntervalTree() const;
};


template <typename Region>
class CartesianSweep : public SweepStructure<CartesianNode> {
public:
    CartesianSweep() : SweepStructure<CartesianNode>() { }
    virtual ~CartesianSweep() { }

    inline void insert(Region *region);

    template <typename RegionProcessor>
    void advance(double to, RegionProcessor &f);

    template <typename RegionProcessor>
    void clear(RegionProcessor &f);

    template <typename OtherRegion, typename MatchProcessor>
    void search(OtherRegion *r, MatchProcessor &f);
};


template <typename Region>
class SphericalSweep : public SweepStructure<SphericalNode> {
public:
    SphericalSweep() : SweepStructure<SphericalNode>(), _searchId(1u) { }
    virtual ~SphericalSweep() { }

    inline void insert(Region *region);

    template <typename RegionProcessor>
    void advance(double to, RegionProcessor &f);

    template <typename RegionProcessor>
    void clear(RegionProcessor &f);

    template <typename OtherRegion, typename MatchProcessor>
    void search(OtherRegion *r, MatchProcessor &f);

    virtual bool isValid() const;

    void setSearchId(unsigned int searchId);

private:
    template <typename OtherRegion, typename MatchProcessor>
    void _search(OtherRegion *r, MatchProcessor &f, double min, double max);

    unsigned int _searchId; 
};

}}}} // namespace lsst::ap::match::detail


#include "SweepStructure.cc"

#endif // LSST_AP_MATCH_DETAIL_SWEEPSTRUCTURE_H