table.hpp

// table.hpp

// Copyright (C) 2004 Steven Weiß (steven11@gmx.de)
//
// Permission to copy, use, sell and distribute this software is granted
// provided this copyright notice appears in all copies.
// Permission to modify the code and to distribute modified code is granted
// provided this copyright notice appears in all copies, and a notice
// that the code was modified is included with the copyright notice.
//
// This software is provided "as is" without express or implied warranty,
// and with no claim as to its suitability for any purpose.


#pragma once
#include <background_wnd/detail/include.hpp>


namespace win32 { namespace gui {
namespace bg_wnd {

template <class CellData> class table;                      // forward declarations

namespace detail {
     template <class Table> class forward_proxy;
}

// ========================================================================================================= //

class COORDS
{    
     unsigned col_;
     unsigned row_;

public:
     COORDS(unsigned col, unsigned row) : col_(col), row_(row)
     {}

     void row(unsigned r)
     {
          row_ = r;
     }

     unsigned row() const
     {
          return row_;
     }    

     void col(unsigned c)
     {
          col_ = c;
     }

     unsigned col() const
     {
          return col_;
     }    

     void move(int horz, int vert)
     {
          col_ += horz;
          row_ += vert;       
     }

     bool operator== (COORDS coords) const
     {
          return row_ == coords.row() && col_ == coords.col();
     }

     bool operator!= (COORDS coords) const
     {
          return ! operator== (coords);
     }

     void swap(COORDS& coords)
     {
          std::swap(row_, coords.row_);
          std::swap(col_, coords.col_);
     }
};

// ========================================================================================================== //

class cell_range
{         
     COORDS top_left_;
     COORDS bottom_right_;

     inline static bool between(unsigned val, unsigned start, unsigned end)
     {
          return (start <= val && val <= end);
     }

public:        
     cell_range(COORDS topleft, COORDS bottomright) 
          : top_left_(topleft), bottom_right_(bottomright)
     {         
          _ASSERTE(top_left_.col() <= bottom_right_.col());      // coordinates must be correct     
          _ASSERTE(top_left_.row() <= bottom_right_.row());      
     }

     cell_range(COORDS topleft, unsigned horz_count, unsigned vert_count) 
          : top_left_( topleft ), 
            bottom_right_( topleft.col() + ((horz_count == 0) ? 0 : horz_count - 1), topleft.row() + ((vert_count == 0) ? 0 : vert_count - 1) )
     {}
     
     bool is_intersecting(const cell_range& range) const
     {              
          bool bHorz = between(range.top_left_.col(),      top_left_.col(),        bottom_right_.col()) ||
                          between(range.bottom_right_.col(), top_left_.col(),      bottom_right_.col()) ||
                          between(top_left_.col(),              range.top_left_.col(), range.bottom_right_.col()) ||
                          between(bottom_right_.col(),     range.top_left_.col(), range.bottom_right_.col()); 

          bool bVert = between(range.top_left_.row(),      top_left_.row(),        bottom_right_.row()) ||
                          between(range.bottom_right_.row(), top_left_.row(),      bottom_right_.row()) ||
                          between(top_left_.row(),              range.top_left_.row(), range.bottom_right_.row()) ||
                          between(bottom_right_.row(),     range.top_left_.row(), range.bottom_right_.row());           
          return bHorz && bVert;
     }
     
     cell_range operator+ (const cell_range& range) const
     {
          cell_range m_ret(*this);
          m_ret += range;
          return m_ret;
     }

     void operator+= (const cell_range& range)
     {
          top_left_.col( min(top_left_.col(), range.top_left_.col()) );
          top_left_.row( min(top_left_.row(), range.top_left_.row()) );
          bottom_right_.col( max(bottom_right_.col(), range.bottom_right_.col()) );
          bottom_right_.row( max(bottom_right_.row(), range.bottom_right_.row()) );       
     }         

     bool operator== (const cell_range& range) const
     {
          return top_left_     == range.top_left_ &&
                  bottom_right_ == range.bottom_right_;
     }

     bool operator!= (const cell_range& range) const
     {
          return ! operator==(range);
     }

     COORDS top_left() const
     {         
          return top_left_;
     }

     COORDS bottom_right() const
     {         
          return bottom_right_;
     }

     void move(int horz, int vert)
     {
          // ensure the coordinates won't be less than 0 (-> they are unsigned!)          
          int horz_amount = top_left_.col() + horz;
          int vert_amount = top_left_.row() + vert;
          if (horz_amount < 0)
               horz -= horz_amount;
          if (vert_amount < 0)
               vert -= vert_amount;

          top_left_.move(horz, vert);
          bottom_right_.move(horz, vert);         
     }    

     void horz_count(unsigned count)
     {
          _ASSERTE(count > 0);               // 0 is not possible
          bottom_right_.col( top_left_.col() + (count - 1) );
     }

     unsigned horz_count() const
     {
          return (bottom_right_.col() - top_left_.col()) + 1;
     }

     void vert_count(unsigned count)
     {
          _ASSERTE(count > 0);               // 0 is not possible          
          bottom_right_.row( top_left_.row() + (count - 1) );
     }

     unsigned vert_count() const
     {
          return (bottom_right_.row() - top_left_.row()) + 1;
     }
};


// ========================================================================================================== //

namespace detail {

     // Base class of cell_proxy. this class is the implementation shared by both cell_proxy-specializations
     template <class CellData>
     class cell_proxy_base
     {         
     protected:
          typedef CellData cell_data;   
          typedef table<CellData> Table;
          typedef typename Table::factor      factor;

          COORDS coords_;                    // coordinates of the cell

          cell_proxy_base(COORDS coords) : coords_(coords)
          {}

          inline factor log_left(const Table& table) const
          {
               factor x = 0;
               unsigned begin_col = range(table).top_left().col();    
               for (unsigned c = 0; c < begin_col; ++c)
                    x += table.col_width(c);
               return x;
          }

          inline factor log_top(const Table& table) const
          {
               factor y = 0;
               unsigned begin_row = range(table).top_left().row();    
               for (unsigned r = 0; r < begin_row; ++r)
                    y += table.row_height(r);
               return y;
          }

          inline factor log_width(const Table& table) const
          {
               factor width = 0;
               unsigned begin_col = range(table).top_left().col();
               unsigned end_col   = range(table).bottom_right().col();          
               for (unsigned c = begin_col; c <= end_col; ++c)
                    width += table.col_width(c);       
               return width;
          }

          inline factor log_height(const Table& table) const
          {
               factor height = 0;
               unsigned begin_row = range(table).top_left().row();
               unsigned end_row   = range(table).bottom_right().row();                    
               for (unsigned r = begin_row; r <= end_row; ++r)
                    height += table.row_height(r);          
               return height;      
          }

          const cell_range range(const Table& table) const
          {    
               typename Table::MergeColl::iterator it_range = table.find_cell_range(coords_);       
               if (it_range != table.pMerges_->end())
                    return *it_range;
               else
                    return cell_range(coords_, coords_);         // cell isn't in a range so create one exclusively for this cell ;-)
          }

          inline const cell_data get_cell_data(const Table& table) const
          {
               return (*table.pMatrix_) [ table.cell_idx(coords_) ];
          }
     };
}    // namespace detail

// ========================================================================================================== //

// there are two specializations:
//        one for a non-const table: the user is allowed to change the cell's data
//        one for a const table: the user has only read-access to the cell
template <class Table> class cell_proxy;

// specialization for a non-const table
template <class CellData>
class cell_proxy<table<CellData> > : private detail::cell_proxy_base<CellData>
{    
     typedef detail::cell_proxy_base<CellData> Base;

     Table&     table_;
          
     // a cell_proxy based on a const Table should be constructible by this non-const cell_proxy.
     // it needs access to table_ so it's our friend ;-)
     friend class cell_proxy<const Table>;

     // only a forward_proxy is allowed to create an object of this class ;-)
     friend class detail::forward_proxy<Table>;   
     cell_proxy(Table& table, COORDS coords) : Base(coords), table_(table)
     {}   
     
public:   
     typedef typename Base::cell_data cell_data;

     cell_proxy(const cell_proxy& cell) : Base(cell.coords_), table_(cell.table_)
     {}

     const cell_proxy& operator= (const cell_data& data)    
     { 
          (*table_.pMatrix_) [ table_.cell_idx(coords_) ] = data;                    
          return *this;
     }
     
     factor log_left() const       { return Base::log_left(table_); }

     factor log_top() const        { return Base::log_top(table_);    }

     factor log_width() const { return Base::log_width(table_); }

     factor log_height() const     { return Base::log_height(table_); }

     const cell_range range() const { return Base::range(table_); }

     // conversion to CellData
     operator const cell_data() const { return Base::get_cell_data(table_); }
};

// specialization for a const table
template <class CellData>
class cell_proxy<const table<CellData> > : private detail::cell_proxy_base<CellData>
{    
     typedef detail::cell_proxy_base<CellData> Base;   
               
     const Table& table_;
     
     // only a forward_proxy is allowed to create an object of this class ;-)
     friend class detail::forward_proxy<const Table>;  
     cell_proxy(const Table& t, COORDS coords) : Base(coords), table_(t)
     {}   
     
public:   
     typedef typename Base::cell_data cell_data;

     cell_proxy(const cell_proxy& cell) : Base(cell.coords_), table_(cell.table_)
     {}

     cell_proxy(const cell_proxy<Table>& cell) : Base(cell.coords_), table_(cell.table_)
     {}

     factor log_left() const       { return Base::log_left(table_); }

     factor log_top() const        { return Base::log_top(table_);    }

     factor log_width() const { return Base::log_width(table_); }

     factor log_height() const     { return Base::log_height(table_); }

     const cell_range range() const { return Base::range(table_); }

     // conversion to CellData
     operator const cell_data() const { return Base::get_cell_data(table_); }
};

// ========================================================================================================= //

namespace detail {
     // proxy class which returns a cell_proxy-object for the cell [col_idx][row_idx]. this indirection is necessary because
     // operator[] has only one dimension -> operator[] of table returns a forward_proxy so this creates two dimensions ;-)
     template <class Table>
     class forward_proxy
     {              
          Table& matrix_;
          unsigned col_;

          // only a table is allowed to construct an object of this class ;-)
          typedef typename Table::cell_data cell_data;
          friend class table<cell_data>;
          forward_proxy(Table& table, unsigned col) : matrix_(table), col_(col)
          {}

     public:
          // forward to cell_proxy
          inline cell_proxy<Table> operator[] (unsigned row)
          {                   
               return cell_proxy<Table> (matrix_, COORDS(col_, row));
          }

          inline const cell_proxy<Table> operator[] (unsigned row) const
          {    
               return cell_proxy<Table> (matrix_, COORDS(col_, row));                
          }
     };
}    // namespace detail

// ========================================================================================================= //

template <class CellData>
class table
{    
public:
     // typedef's
     typedef double factor;             // factor which indicates the height, width and position of cells. they are
                                             // only logical -> you have to define a default value which will be multiplied with the factor                               
     typedef CellData cell_data;
     typedef table<CellData> self;
     
     typedef cell_proxy<self>                cell_type;          
     typedef const cell_proxy<const self>    const_cell_type;

     // cell_proxy_base is a friend (needs access to our matrix). cell_type is also a friend (needs to change a cell)
     friend class detail::cell_proxy_base<CellData>;
     friend class cell_type;
     

     table(const cell_data& def_cell_data) : pMatrix_(new Matrix()), pRowHeights_(new RowHeightColl()), pColWidths_(new ColWidthColl()), pMerges_(new MergeColl()), def_cell_data_(def_cell_data)
     {}

     table(const cell_data& def_cell_data, unsigned cols, unsigned rows) 
          : pMatrix_( new Matrix(cols * rows, def_cell_data) ),                 // init with default cell_data
            pColWidths_(new ColWidthColl(cols, 1)),
            pRowHeights_(new RowHeightColl(rows, 1)),
            pMerges_(new MergeColl()), def_cell_data_(def_cell_data)
     {}

     // copy c'tor
     table(const table& t) 
          : pMatrix_( new Matrix(*t.pMatrix_.get()) ),
            pColWidths_( new ColWidthColl(*t.pColWidths_.get()) ),
            pRowHeights_( new RowHeightColl(*t.pRowHeights_.get()) ),
            pMerges_( new MergeColl(*t.pMerges_.get()) ),
            def_cell_data_(t.def_cell_data_)
     {}

     virtual ~table()
     {}

     const table& operator= (const table& t)
     {
          if (this != &t) {
               table temp(t);
               swap(temp);              
          }
          return *this;
     }

     const cell_data default_cell_data() const
     {
          return def_cell_data_;
     }

     void dimensions(unsigned cols, unsigned rows)
     {
          if (rows == 0 || cols == 0) {
               pMatrix_->clear();       
               pRowHeights_->clear();
               pColWidths_->clear();    
               pMerges_->clear();            
          }
          // copy cells (exception safe)
          else if (rows != row_count() || cols != col_count()) {
               self temp(def_cell_data_, cols, rows);

               // set row heights and copy cell data
               for (unsigned row = 0; row < rows && row < row_count(); ++row) {
                    temp.row_height(row, row_height(row));
                    for (unsigned col = 0; col < cols && col < col_count(); ++col)                            
                         temp[col][row] = (*this) [col][row];                                            
               }
               // set column widths
               for (unsigned col = 0; col < cols && col < col_count(); ++col)
                    temp.col_width(col, col_width(col));
               
               // copy ranges           
               temp.pMerges_->reserve(pMerges_->size());
               for (MergeColl::iterator it = pMerges_->begin(); it != pMerges_->end(); ++it)
               {              
                    // if table shrinks some ranges can be deleted
                    cell_range range = *it;       
                    unsigned left   = range.top_left().col();
                    unsigned top    = range.top_left().row();
                    
                    if (cols <= left || rows <= top)
                         continue;                     
                    
                    range.horz_count( min(cols - left, range.horz_count()) );        // shrink if necessary
                    range.vert_count( min(rows - top, range.vert_count()) );
                         
                    temp.pMerges_->push_back( range );
               }              

               swap(temp);
          }
     }

     inline unsigned row_count() const
     {
          return static_cast<unsigned> (pRowHeights_->size());
     }

     inline unsigned col_count() const
     {
          return static_cast<unsigned> (pColWidths_->size());
     }

     inline detail::forward_proxy<self> operator[] (unsigned col)
     {
          return detail::forward_proxy<self> (*this, col);
     }

     inline const detail::forward_proxy<const self> operator[] (unsigned col) const
     {
          return detail::forward_proxy<const self> (*this, col);
     }

     void row_height(unsigned row, factor height_factor)
     {
          _ASSERTE(row < pRowHeights_->size());                  // must be in bounds
          (*pRowHeights_) [row] = height_factor;  
     }

     factor row_height(unsigned row) const
     {
          _ASSERTE(row < pRowHeights_->size());                  // must be in bounds
          return (*pRowHeights_) [row];           
     }

     void col_width(unsigned col, factor width_factor)
     {
          _ASSERTE(col < pColWidths_->size());                   // must be in bounds
          (*pColWidths_) [col] = width_factor;
     }

     factor col_width(unsigned col) const
     {
          _ASSERTE(col < pColWidths_->size());                   // must be in bounds
          return (*pColWidths_) [col];            
     }                   

     void insert_row(unsigned row)
     {
          row = min(row, row_count());

          // copy cells (exception safe)
          self temp(def_cell_data_, col_count(), row_count() + 1);
          for (unsigned c = 0; c < col_count(); ++c) {
               for (unsigned r = 0; r < row_count() + 1; ++r) {
                    if (r < row)
                         temp[c][r] = (*this) [c][r];
                    else if (r > row)
                         temp[c][r] = (*this) [c][r - 1];
               }
          }    

          // copy merges
          temp.pMerges_->reserve(pMerges_->size());
          for (MergeColl::iterator it = pMerges_->begin(); it != pMerges_->end(); ++it) {           
               // if a row is inserted the ranges are likely to be changed
               cell_range range = *it;  
               unsigned top    = range.top_left().row();
               unsigned bottom = range.bottom_right().row();
               if (row <= top)
                    range.move(0, 1);                  
               else if (top < row && row <= bottom)
                    range.vert_count(range.vert_count() + 1);

               temp.pMerges_->push_back( range );
          }

          // ensure exception safety ;-)
          swap(temp);
     }         

     void insert_col(unsigned col)
     {
          col = min(col, col_count());

          // copy cells
          self temp(def_cell_data_, col_count() + 1, row_count());
          for (unsigned r = 0; r < row_count(); ++r) {
               for (unsigned c = 0; c < col_count() + 1; ++c) {
                    if (c < col)
                         temp[c][r] = (*this) [c][r];
                    else if (c > col)
                         temp[c][r] = (*this) [c - 1][r];
               }                   
          }         

          // copy merges
          temp.pMerges_->reserve(pMerges_->size());
          for (MergeColl::iterator it = pMerges_->begin(); it != pMerges_->end(); ++it) {           
               // if a column is inserted the ranges are likely to be changed
               cell_range range = *it;       
               unsigned left  = range.top_left().col();
               unsigned right = range.bottom_right().col();
               if (col <= left)
                    range.move(1, 0);                  
               else if (left < col && col <= right)
                    range.horz_count(range.horz_count() + 1);

               temp.pMerges_->push_back( range );
          }

          // ensure exception safety ;-)
          swap(temp);
     }    

     void remove_col(unsigned col)
     {
          _ASSERTE(col < col_count());  

          // take care of the merged cells
          for (unsigned row = 0; row < row_count(); ++row) {
               MergeColl::iterator it_range = find_cell_range(COORDS(col, row));
               if (it_range != pMerges_->end()) {
                    cell_range& range = *it_range;
                    
                    if (range.horz_count() == 1)                 // if range is only in this column remove it
                         pMerges_->erase(it_range);                        
                    else {
                         unsigned left  = range.top_left().col();
                         unsigned right = range.bottom_right().col();
                                             
                         if (left <= col && col <= right) {                     
                              range.horz_count(range.horz_count() - 1);
                              row += range.vert_count() - 1;          // go to next row which isn't in this range
                         }
                         if (left == col)                             // if first column of range is removed move the range
                              range.move(-1, 0);
                    }
               }              
          }    

          // erase cells - but from last to first so that the index is always correct. 
          // note: because row is unsigned we have to be aware of the underflow when decreasing 0!!!
          for (unsigned row = row_count(); row > 0; --row)
               pMatrix_->erase( pMatrix_->begin() + cell_idx(COORDS(col, row - 1)) );

          // erase column          
          pColWidths_->erase(pColWidths_->begin() + col);        
     }
     
     void remove_row(unsigned row)
     {
          _ASSERTE(row < row_count());  

          // take care of the merged cells
          for (unsigned col = 0; col < col_count(); ++col) {
               MergeColl::iterator it_range = find_cell_range(COORDS(col, row));
               if (it_range != pMerges_->end()) {
                    cell_range& range = *it_range;
                    
                    if (range.vert_count() == 1)                 // if range is only in this row remove it
                         pMerges_->erase(it_range);                        
                    else {
                         unsigned top    = range.top_left().row();
                         unsigned bottom = range.bottom_right().row();
                                             
                         if (top <= row && row <= bottom) {                     
                              range.vert_count(range.vert_count() - 1);
                              col += range.horz_count() - 1;          // go to next column which isn't in this range
                         }
                         if (top == row)                                   // if first row of range is removed move the range
                              range.move(0, -1);
                    }
               }              
          }    

          // erase cells - but from last to first so that the index is always correct. 
          // note: because col is unsigned we have to be aware of the underflow when decreasing 0!!!
          for (unsigned col = col_count(); col > 0; --col)
               pMatrix_->erase( pMatrix_->begin() + cell_idx(COORDS(col - 1, row)) );

          // erase row
          pRowHeights_->erase(pRowHeights_->begin() + row);
     }

     void merge_cells(const cell_range& range)
     {
          cell_range r = apply_merge_recursive(range);
          pMerges_->push_back(r);
     }

     void unmerge_cells(const cell_range& range)
     {
          MergeColl::iterator it_range = std::find(pMerges_->begin(), pMerges_->end(), range);
          if (it_range != pMerges_->end())
               pMerges_->erase(it_range);         
     }

     void unmerge_cells(COORDS coords)
     {
          MergeColl::iterator it_range = find_cell_range(coords);
          if (it_range != pMerges_->end())
               pMerges_->erase(it_range);
     }

     void swap(self& t)
     {
          std::swap(pMatrix_, t.pMatrix_);
          std::swap(pRowHeights_,   t.pRowHeights_);
          std::swap(pColWidths_,    t.pColWidths_);
          std::swap(def_cell_data_, t.def_cell_data_);
          std::swap(pMerges_, t.pMerges_);
     }

private:  
     // applies a merge-operation recursively
     cell_range apply_merge_recursive(const cell_range& range)
     {              
          for (unsigned i = 0; i < pMerges_->size(); ++i) {           
               cell_range& r2 = (*pMerges_) [i];
               if (range == r2)
                    continue;

               // if merges intersect add them and call this function recursive                          
               if (range.is_intersecting(r2)) {
                    cell_range temp = range + r2;      
                    if (temp != range) {                         
                         pMerges_->erase(pMerges_->begin() + i);      // erase from collection
                         --i;                
                         return apply_merge_recursive(temp);
                    }
               }
          }

          return range;
     }

     // returns the index of cell with the passed coordinates in the vector matrix_
     inline unsigned cell_idx(COORDS coords) const
     {              
          unsigned ret = coords.col() + coords.row() * col_count();
          _ASSERTE(ret < (row_count() * col_count())); // index must be in bounds
          return ret;
     }


private:
     // members
     typedef std::vector<cell_data> Matrix;
     typedef std::auto_ptr<Matrix> MatrixPtr;
     MatrixPtr pMatrix_;                                    // the Matrix: saves the data
     cell_data def_cell_data_;                              // default data

     typedef std::vector<factor> RowHeightColl;
     typedef RowHeightColl         ColWidthColl;
     typedef std::auto_ptr<RowHeightColl> RowHeightCollPtr;
     typedef std::auto_ptr<ColWidthColl>  ColWidthCollPtr;
     RowHeightCollPtr pRowHeights_;                         // saves the height and width of the rows/columns
     ColWidthCollPtr  pColWidths_;                

     typedef std::vector<cell_range>   MergeColl;      
     typedef std::auto_ptr<MergeColl>  MergeCollPtr;
     MergeCollPtr pMerges_;                                 // collection of the merged cells


private:
     // returns the cell range of the cell with the passed coordinates
     MergeColl::iterator find_cell_range(COORDS coords) const
     {
          cell_range this_cell(coords, coords);
          for (MergeColl::iterator it = pMerges_->begin(); it != pMerges_->end(); ++it) {
               if (this_cell.is_intersecting(*it))
                    return it;               
          }

          return pMerges_->end();
     }
};


}    // namespace bg_wnd
} }  // namespace win32::gui