I wrote ..
>
> In a better world, isn't this exactly what Fl_Scroll would do?
>

I hacked together the following as a POC of what I had in mind.
Comments welcome of course, but I don't have the time to do
anything more with it.  Perhaps it will be useful to somebody.

Best,
Stan


#include <FL/Fl.H>
#include <FL/Fl_Double_Window.H>
#include <FL/Fl_Scrollbar.H>
#include <FL/Fl_Group.H>
#include <FL/fl_draw.H>
#include <vector>
#include <limits>
#include <functional>
#include <algorithm>

//////////////////
// for the demo
#include <FL/Fl_Input.H>
#include <stdio.h>
#include <cstdlib>
//////////////////

class Scroll : private Fl_Group {
public:
    class Cell {
        int x_; // x/y stored as ints, for extended geometry
        int y_;
        short w_; // w/h are only used to remember previous sizes
        short h_;
        Fl_Widget* widget_;
    public:
        Cell(int x, int y, Fl_Widget* wg)
            : x_(x), y_(y), w_(wg->w()), h_(wg->h()), widget_(wg)
        {;}
        int x() const { return x_; }
        int y() const { return y_; }
        int w() const { return w_; }
        int h() const { return h_; }
        Fl_Widget* widget() const { return widget_; }
    };
private:
    typedef std::vector<Cell> Vector;
    typedef Vector::const_iterator Iterator;

    struct LessX : public std::binary_function<Cell, Cell, bool> {
        bool operator()(Cell const& lhs, Cell const& rhs) const
        { return lhs.x() < rhs.x(); }
    };
    struct LessY : public std::binary_function<Cell, Cell, bool> {
        bool operator()(Cell const& lhs, Cell const& rhs) const
        { return lhs.y() < rhs.y(); }
    };
    struct LessYX : public std::binary_function<Cell, Cell, bool> {
        bool operator()(Cell const& lhs, Cell const& rhs) const
        { return lhs.y() ==  rhs.y() ? lhs.x() < rhs.x()
                 : lhs.y() < rhs.y(); }
    };
    struct LessWidget : public std::binary_function<Cell, Cell, bool> {
        bool operator()(Cell const& lhs, Cell const& rhs) const
        { return lhs.widget() < rhs.widget(); }
    };
    struct ByXW : public std::binary_function<Cell, int, bool> {
        bool operator()(Cell const& e, int i)
        { return e.x() + e.w() < i; }
    };
    struct ByYH : public std::binary_function<Cell, int, bool> {
        bool operator()(Cell const& e, int i)
        { return e.y() + e.h() < i; }
    };
public:
    Scroll(int x, int y, int w, int h, char const* label = 0)
        : Fl_Group(x, y, w, h, label)
        , vscroll_(new Fl_Scrollbar(0, 0, 0, 0))
        , hscroll_(new Fl_Scrollbar(0, 0, 0, 0))
        , minx_(std::numeric_limits<int>::max())
        , miny_(std::numeric_limits<int>::max())
        , maxx_(std::numeric_limits<int>::min())
        , maxy_(std::numeric_limits<int>::min())
        , sorted_(true)
    {
        end();
        hscroll_->type(FL_HORIZONTAL);
        vscroll_->type(FL_VERTICAL);
        hscroll_->callback(scr_cb, this);
        vscroll_->callback(scr_cb, this);
        hscroll_->value(0, w, 0, w);
        vscroll_->value(0, h, 0, h);
        place_scrollbars();
    }
    ~Scroll()
    {
        // Delete cells that fltk isn't going to delete
        for(Iterator i = byX_.begin(); i != byX_.end(); ++i) {
            if(i->widget() && !i->widget()->parent()) {
                delete i->widget();
            }
        }
    }
    Scroll& add(Fl_Widget* w, int x, int y)
    {
        minx_ = std::min(minx_, x);
        miny_ = std::min(miny_, y);
        maxx_ = std::max(maxx_, x + w->w());
        maxy_ = std::max(maxy_, y + w->h());
        Cell cell(x, y, w);
        byX_.push_back(cell);
        byY_.push_back(cell);
        sorted_ = false;
        return *this;
    }

    // A useful optimization when the number of
    // cells is known in advance.
    void reserve(Vector::size_type n)
    { byX_.reserve(n); byY_.reserve(n); }

private:
    Fl_Scrollbar* hscroll_;    // horizontal scrollbar
    Fl_Scrollbar* vscroll_;    // vertical scrollbar
    Vector byX_;               // cells sorted by x-coord
    Vector byY_;               // cells sorted by y-coord
    int minx_;                 // smallest x
    int maxx_;                 // largest x + w
    int miny_;                 // smallest y
    int maxy_;                 // largest y + h
    bool sorted_;

    static void scr_cb(Fl_Widget*, void* v)
    { static_cast<Scroll*>(v)->scroll(); }

    void scroll()
    { populate(hscroll_->value(), vscroll_->value()); redraw(); }

    void resize(int x, int y, int w, int h)
    {
        if(x != this->x() || y != this->y()
                    || w != this->w() || h != this->h()) {
            Fl_Widget::resize(x, y, w, h);
            place_scrollbars();
            // Not clear what to do here.
            populate(0, 0);
        }
    }

    void draw()
    {
        static bool firsttime = true;
        if(firsttime) {
            populate(hscroll_->value(), vscroll_->value());
            firsttime = false;
        }
        Fl_Group::draw();
    }

    void place_scrollbars()
    {
        vscroll_->resize(x() + w() - Fl::scrollbar_size(), y(),
              Fl::scrollbar_size(), h());
        hscroll_->resize(x(), y() + h() - Fl::scrollbar_size(),
              w() - Fl::scrollbar_size(), Fl::scrollbar_size());
    }

    void clip(int& x, int& y, int& w, int& h,
              int left, int right, int top, int bottom);
    void populate(int xoffs, int yoffs);
};
void Scroll::clip(int& x, int& y, int& w, int& h,
           int left, int right, int top, int bottom)
{
    // Keep cells from slopping over the edges
    if(x < left) {
        w -= left - x;
        x = left;
    }
    if(x + w > right) {
        w -= x + w - right;
    }
    if(y < top) {
        h -= top - y;
        y = top;
    }
    if(y + h > bottom) {
        h -= y + h - bottom;
    }
}
void
Scroll::populate(int xoffs, int yoffs)
{
    if(!sorted_) {
        std::sort(byX_.begin(), byX_.end(), LessX());
        std::sort(byY_.begin(), byY_.end(), LessY());
        sorted_ = true;
    }

    // Bounding box of the cells
    int const X = x();
    int const Y = y();
    int const W = w() - vscroll_->w();
    int const H = h() - hscroll_->h();

    for(int i = children() - 1; i >= 0; --i) {
        remove(child(i));
    }

    // Find cells fully or partially in visible x and y range,
    // in O(log(n))
    Iterator xlb = std::lower_bound(byX_.begin(), byX_.end(),
              xoffs, ByXW());
    Iterator xub = xlb;
    while(xub != byX_.end() && xub->x() < W + xoffs) {
        ++xub;
    }
    Iterator ylb = std::lower_bound(byY_.begin(), byY_.end(),
              yoffs, ByYH());
    Iterator yub = ylb;
    while(yub != byY_.end() && yub->y() < H + yoffs) {
        ++yub;
    }

    // Hopeully there are ~sqrt(n) in each range
    // Sort these by identity in (hopefully) O(sqrt(n)log(sqrt(n)))
    Vector xrange(xlb, xub);
    std::sort(xrange.begin(), xrange.end(), LessWidget());
    Vector yrange(ylb, yub);
    std::sort(yrange.begin(), yrange.end(), LessWidget());

    // The intersection of the 2 collections is what is to be displayed.
    // Find this in log(sqrt(n))
    Vector range;
    std::insert_iterator<Vector> range_inserter(range, range.begin());
    std::set_intersection(
        xrange.begin(), xrange.end(),
        yrange.begin(), yrange.end(),
        range_inserter,
        LessWidget()
    );

    // Sort again to establish a reasonable tab order
    std::sort(range.begin(), range.end(), LessYX());


    // Map virtual space to real space and add the cells.
    // The cells have to be clipped individually, or else they'll
    // slop over the edges when redrawn independently of the container.
    // The use of max(i->w(), i->widget()->w()) (res h) is to restore
    // the original size of previously clipped cells.
    for(Iterator i = range.begin(); i != range.end(); ++i) {
        int cell_x = X + i->x() - xoffs;
        int cell_y = Y + i->y() - yoffs;
        int cell_w = std::max(i->widget()->w(), i->w());
        int cell_h = std::max(i->widget()->h(), i->h());
        clip(cell_x, cell_y, cell_w, cell_h, X, X + W, Y, Y + H);
        i->widget()->resize(cell_x, cell_y, cell_w, cell_h);
        Fl_Group::add(i->widget());
    }

    Fl_Group::add(vscroll_);
    Fl_Group::add(hscroll_);
    hscroll_->value(xoffs, W, 0, maxx_ - minx_);
    vscroll_->value(yoffs, H, 0, maxy_ - miny_);
}

////////////////////////////////////////////////////////////////////////////////////////////////
//  Demo

class Box : public Fl_Input {
public:
    Box(int x, int y, int w, int h, int i, int j)
        : Fl_Input(x, y, w, h)
    {
        char buff[100];
        sprintf(buff, "%d, %d", i, j);
        value(buff);
    }
};

int main(int argc, char* argv[])
{
    int N = 1000;
    if(argc > 1) {
        N = std::atoi(argv[1]);
    }
    char title[100];
    sprintf(title, "%d Widgets", N * N);
    Fl_Double_Window win(450, 400, title);
    Scroll scroll(50, 50, 300, 300);
    win.end();
    win.resizable(&win);

    int const cell_w = 100;
    int const cell_h = 20;
    scroll.reserve(N * N);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            int X = i * cell_w;
            int Y = j * cell_h;
            scroll.add(new Box(X, Y, cell_w, cell_h, i, j), X, Y);
        }
    }
    win.show();
    return Fl::run();
}
_______________________________________________
fltk mailing list
[email protected]
http://lists.easysw.com/mailman/listinfo/fltk

Reply via email to