modules/quadTree.h

#ifndef QUADTREE_HEADER_
#define QUADTREE_HEADER_

#include "../headers.h"

//  forwards from "fileUtils.h"
class BitWriter;
class BitReader;


class MQuadTree: public ISquareRanges {
    DECLARE_debugModule;

    DECLARE_TypeInfo( MQuadTree, "Quad-tree"
    , "Splits the range blocks according to the <b>quad-tree</b> algorithm"
    , {
        label:  "Min. range-block size",
        desc:   "Blocks with this size won't be divided",
        type:   settingInt(2,2,8,IntLog2)
    }, {
        label:  "Max. range-block size",
        desc:   "Blocks with bigger size will be always divided",
        type:   settingInt(2,12,12,IntLog2)
    }, {
        label:  "Heuristic dividing",
        desc:   "Pre-divide the ranges heuristically and later divide ranges\n"
                "with bad quality and try to merge ranges with good quality",
        type:   settingCombo("no\nyes",1)
    } )
    // \todo better heuristics via changes in ISquareEncoder interface
    
protected:
    class Node; // forward declaration, derived from RangeNode
    friend class Node;

protected:
    enum Settings { MinLevel, MaxLevel, HeuristicAllowed };
//  Settings-retrieval methods
    int minLevel()          { return settingsInt(MinLevel); }
    int maxLevel()          { return settingsInt(MaxLevel); }
    bool heuristicAllowed() { return settingsInt(HeuristicAllowed); }

protected:
//  Module's data
    Node *root;                     
    std::vector<RangeNode*> fringe; 
    int zoom;                       
#ifndef NDEBUG /* things needed for showing debugging info */
    int badDivides, triedMerges, badTries;
    const PlaneBlock *planeBlock;
#endif

protected:
//  Construction and destruction
    MQuadTree()
    : root(0), zoom(-1)
    #ifndef NDEBUG
    , badDivides(0), triedMerges(0), badTries(0), planeBlock(0)
    #endif
        {}
    ~MQuadTree() { delete root; }
public:
    void encode(const PlaneBlock &toEncode);
    const RangeList& getRangeList() const
        { return fringe; }

    /* The module doesn't need to preserve any settings */
    void writeSettings(std::ostream&) {}
    void readSettings(std::istream&) {}

    void writeData(std::ostream &file);
    void readData_buildRanges(std::istream &file,const PlaneBlock &block);
protected:
    static float estimateSE(Real rSum,Real r2Sum,int pixCount,int level)
        { return ldexp( r2Sum-sqr(rSum)/pixCount, -4 ) * level; }
protected:
    struct NodeExtremes;
    class Node: public RangeNode {
        Node *father    
        , *brother      
        , *son;         

        Node( const Block &block, Node *father_, Node* brother_ )
        : RangeNode( block, father_->level-1 )
        , father(father_), brother(brother_), son(0) {}
        void disconnect();
    public:
        Node(const Block &block)
        : RangeNode( block, log2ceil(std::max(block.width(),block.height())) )
        , father(0), brother(this), son(0) {}
        ~Node() { deleteSons(); }
        void deleteSons();

        void divide();
        void getHilbertList(RangeList &list,char start=0,char clockwise=1);
        int getSonCount() const;

        bool encode(const PlaneBlock &toEncode);

        void toFile(BitWriter &file,NodeExtremes extremes);
        void fromFile(BitReader &file,NodeExtremes extremes);
    }; // MQuadTree::Node class
};

#endif // QUADTREE_HEADER_

---