libs/canvas/lookup_table.cc

   1 /*
   2     Copyright (C) 2011-2013 Paul Davis
   3     Author: Carl Hetherington <cth@carlh.net>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18 */
  19
  20 #include "canvas/lookup_table.h"
  21 #include "canvas/group.h"
  22
  23 using namespace std;
  24 using namespace ArdourCanvas;
  25
  26 LookupTable::LookupTable (Group const & group)
  27         : _group (group)
  28 {
  29
  30 }
  31
  32 LookupTable::~LookupTable ()
  33 {
  34
  35 }
  36
  37 DumbLookupTable::DumbLookupTable (Group const & group)
  38         : LookupTable (group)
  39 {
  40
  41 }
  42
  43 vector<Item *>
  44 DumbLookupTable::get (Rect const &)
  45 {
  46         list<Item *> const & items = _group.items ();
  47         vector<Item *> vitems;
  48         copy (items.begin(), items.end(), back_inserter (vitems));
  49         return vitems;
  50 }
  51
  52 /* XXX: what coordinate system is the point in? parent of our group I think */
  53 vector<Item *>
  54 DumbLookupTable::items_at_point (Duple point) const
  55 {
  56         list<Item *> items = _group.items ();
  57         vector<Item *> vitems;
  58
  59         for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
  60                 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
  61                 if (item_bbox) {
  62                         Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
  63                         if (parent_bbox.contains (point)) {
  64                                 vitems.push_back (*i);
  65                         }
  66                 }
  67         }
  68
  69         return vitems;
  70 }
  71
  72 OptimizingLookupTable::OptimizingLookupTable (Group const & group, int items_per_cell)
  73         : LookupTable (group)
  74         , _items_per_cell (items_per_cell)
  75         , _added (false)
  76 {
  77         list<Item*> const & items = _group.items ();
  78
  79         /* number of cells */
  80         int const cells = items.size() / _items_per_cell;
  81         /* hence number down each side of the table's square */
  82         _dimension = max (1, int (rint (sqrt ((double)cells))));
  83
  84         _cells = new Cell*[_dimension];
  85         for (int i = 0; i < _dimension; ++i) {
  86                 _cells[i] = new Cell[_dimension];
  87         }
  88
  89         /* our group's bounding box in its coordinates */
  90         boost::optional<Rect> bbox = _group.bounding_box ();
  91         if (!bbox) {
  92                 return;
  93         }
  94
  95         _cell_size.x = bbox.get().width() / _dimension;
  96         _cell_size.y = bbox.get().height() / _dimension;
  97         _offset.x = bbox.get().x0;
  98         _offset.y = bbox.get().y0;
  99
 100 //      cout << "BUILD bbox=" << bbox.get() << ", cellsize=" << _cell_size << ", offset=" << _offset << ", dimension=" << _dimension << "\n";
 101
 102         for (list<Item*>::const_iterator i = items.begin(); i != items.end(); ++i) {
 103
 104                 /* item bbox in its own coordinates */
 105                 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
 106                 if (!item_bbox) {
 107                         continue;
 108                 }
 109
 110                 /* and in the group's coordinates */
 111                 Rect const item_bbox_in_group = (*i)->item_to_parent (item_bbox.get ());
 112
 113                 int x0, y0, x1, y1;
 114                 area_to_indices (item_bbox_in_group, x0, y0, x1, y1);
 115
 116                 /* XXX */
 117                 assert (x0 >= 0);
 118                 assert (y0 >= 0);
 119                 assert (x1 >= 0);
 120                 assert (y1 >= 0);
 121                 //assert (x0 <= _dimension);
 122                 //assert (y0 <= _dimension);
 123                 //assert (x1 <= _dimension);
 124                 //assert (y1 <= _dimension);
 125
 126                 if (x0 > _dimension) {
 127                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x0 - bbox.get().x0) << "\n";
 128                         x0 = _dimension;
 129                 }
 130                 if (x1 > _dimension) {
 131                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x1 - bbox.get().x1) << "\n";
 132                         x1 = _dimension;
 133                 }
 134                 if (y0 > _dimension) {
 135                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y0 - bbox.get().y0) << "\n";
 136                         y0 = _dimension;
 137                 }
 138                 if (y1 > _dimension) {
 139                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y1 - bbox.get().y1) << "\n";
 140                         y1 = _dimension;
 141                 }
 142
 143                 for (int x = x0; x < x1; ++x) {
 144                         for (int y = y0; y < y1; ++y) {
 145                                 _cells[x][y].push_back (*i);
 146                         }
 147                 }
 148         }
 149 }
 150
 151 void
 152 OptimizingLookupTable::area_to_indices (Rect const & area, int& x0, int& y0, int& x1, int& y1) const
 153 {
 154         if (_cell_size.x == 0 || _cell_size.y == 0) {
 155                 x0 = y0 = x1 = y1 = 0;
 156                 return;
 157         }
 158
 159         Rect const offset_area = area.translate (-_offset);
 160
 161         x0 = floor (offset_area.x0 / _cell_size.x);
 162         y0 = floor (offset_area.y0 / _cell_size.y);
 163         x1 = ceil  (offset_area.x1 / _cell_size.x);
 164         y1 = ceil  (offset_area.y1 / _cell_size.y);
 165 }
 166
 167 OptimizingLookupTable::~OptimizingLookupTable ()
 168 {
 169         for (int i = 0; i < _dimension; ++i) {
 170                 delete[] _cells[i];
 171         }
 172
 173         delete[] _cells;
 174 }
 175
 176 void
 177 OptimizingLookupTable::point_to_indices (Duple point, int& x, int& y) const
 178 {
 179         if (_cell_size.x == 0 || _cell_size.y == 0) {
 180                 x = y = 0;
 181                 return;
 182         }
 183
 184         Duple const offset_point = point - _offset;
 185
 186         x = floor (offset_point.x / _cell_size.x);
 187         y = floor (offset_point.y / _cell_size.y);
 188 }
 189
 190 vector<Item*>
 191 OptimizingLookupTable::items_at_point (Duple point) const
 192 {
 193         int x;
 194         int y;
 195         point_to_indices (point, x, y);
 196
 197         if (x >= _dimension) {
 198                 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
 199         }
 200
 201         if (y >= _dimension) {
 202                 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
 203         }
 204
 205         /* XXX: hmm */
 206         x = min (_dimension - 1, x);
 207         y = min (_dimension - 1, y);
 208
 209         assert (x >= 0);
 210         assert (y >= 0);
 211
 212         Cell const & cell = _cells[x][y];
 213         vector<Item*> items;
 214         for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
 215                 boost::optional<Rect> const item_bbox = (*i)->bounding_box ();
 216                 if (item_bbox) {
 217                         Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
 218                         if (parent_bbox.contains (point)) {
 219                                 items.push_back (*i);
 220                         }
 221                 }
 222         }
 223
 224         return items;
 225 }
 226
 227 /** @param area Area in our owning group's coordinates */
 228 vector<Item*>
 229 OptimizingLookupTable::get (Rect const & area)
 230 {
 231         list<Item*> items;
 232         int x0, y0, x1, y1;
 233         area_to_indices (area, x0, y0, x1, y1);
 234
 235         /* XXX: hmm... */
 236         x0 = min (_dimension - 1, x0);
 237         y0 = min (_dimension - 1, y0);
 238         x1 = min (_dimension, x1);
 239         y1 = min (_dimension, y1);
 240
 241         for (int x = x0; x < x1; ++x) {
 242                 for (int y = y0; y < y1; ++y) {
 243                         for (Cell::const_iterator i = _cells[x][y].begin(); i != _cells[x][y].end(); ++i) {
 244                                 if (find (items.begin(), items.end(), *i) == items.end ()) {
 245                                         items.push_back (*i);
 246                                 }
 247                         }
 248                 }
 249         }
 250
 251         vector<Item*> vitems;
 252         copy (items.begin (), items.end (), back_inserter (vitems));
 253
 254         return vitems;
 255 }
 256