redblacktree.h

Go to the documentation of this file.

 
#ifndef SEEN_LIB2GEOM_REDBLACKTREE_H
#define SEEN_LIB2GEOM_REDBLACKTREE_H
 
#include <vector>
//#include <cassert>
#include <limits>
#include <cfloat>
 
#include <2geom/d2.h>
#include <2geom/interval.h>
 
namespace Geom{
 
class RedBlack{    
public:
    Interval interval;    // Key of the redblack tree will be the min of the interval
    RedBlack *left, *right, *parent;
    bool isRed;
    Coord subtree_max;    // subtree_max = max( x->left->subtree_max, x->right->subtree_max, x->high )
    int data;
 
    RedBlack(): left(0), right(0), parent(0), isRed(false), subtree_max(0.0), data(0) {
        Interval interval(0.0, 0.0);
    }
    RedBlack(): left(0), right(0), parent(0), isRed(false), subtree_max(0.0), data(0) {…}
/*
    RedBlack(Coord min, Coord max): left(0), right(0), parent(0), isRed(false), subtree_max(0.0), data(0) {
        Interval interval( min, max );
    }
*/
    inline Coord key(){ return interval.min(); };
    inline Coord high(){ return interval.max(); };
};
class RedBlack {…};
 
 
class RedBlackTree{
public:
    RedBlack* root;
 
    RedBlackTree(): root(0) {}
 
    void insert(Rect const &r, int shape, int dimension);
    void insert(Coord dimension_min, Coord dimension_max, int shape);
 
    void erase(Rect const &r);
    void erase(int shape);
 
    RedBlack* search(Rect const &r, int dimension);
    RedBlack* search(Interval i);
    RedBlack* search(Coord a, Coord b);
 
    void print_tree();
private:
    void inorder_tree_walk(RedBlack* x);
    RedBlack* tree_minimum(RedBlack* x);
    RedBlack* tree_successor(RedBlack* x);
 
    void left_rotate(RedBlack* x);
    void right_rotate(RedBlack* x);
    void tree_insert(RedBlack* x);
 
    void update_max(RedBlack* x);
 
    RedBlack* erase(RedBlack* x); // TODO why rerutn pointer? to collect garbage ???
    void erase_fixup(RedBlack* x);
 
};
class RedBlackTree {…};
 
} // end namespace Geom
 
#endif // !SEEN_LIB2GEOM_REDBLACKTREE_H
 
/*
  Local Variables:
  mode:c++
  c-file-style:"stroustrup"
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  indent-tabs-mode:nil
  fill-column:99
  End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :