kspread Library API Documentation

stylecluster.cc

00001 /* This file is part of the KDE project
00002    Copyright (C) 2005 The KSpread Team
00003                               www.koffice.org/kspread
00004 
00005    This library is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Library General Public
00007    License as published by the Free Software Foundation; either
00008    version 2 of the License, or (at your option) any later version.
00009 
00010    This library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Library General Public License for more details.
00014 
00015    You should have received a copy of the GNU Library General Public License
00016    along with this library; see the file COPYING.LIB.  If not, write to
00017    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00018    Boston, MA 02111-1307, USA.
00019 */
00020 #include "stylecluster.h"
00021 
00022 #include "kspread_global.h"
00023 #include "kspread_doc.h"
00024 #include "kspread_style_manager.h"
00025 #include "kspread_style.h"
00026 #include "kspread_sheet.h"
00027 #include "kspread_util.h"
00028 
00029 #include <qvaluestack.h>
00030 
00031 namespace KSpread {
00032 
00059 class StyleClusterQuad
00060 {
00061   private:
00062     KSpreadStyle* m_style;
00063   public:
00064   
00068     inline StyleClusterQuad();
00069     
00073     inline ~StyleClusterQuad();
00074 
00080     inline int numNullChildren();
00081 
00086     bool m_isSimple;
00087 
00088     StyleClusterQuad* m_topLeft;
00089     StyleClusterQuad* m_topRight;
00090     StyleClusterQuad* m_bottomLeft;
00091     StyleClusterQuad* m_bottomRight;
00092 
00093     KSpreadStyle* getStyle() { return m_style; }
00094     inline void setStyle(KSpreadStyle * style);
00098     inline void makeChild(StyleClusterQuad **child);
00099 };
00100 
00101 void StyleClusterQuad::makeChild(StyleClusterQuad **child) {
00102   Q_ASSERT(!*child);
00103   Q_ASSERT(child == &m_topLeft || child == &m_topRight ||
00104       child == &m_bottomLeft || child == &m_bottomRight);
00105       
00106   *child = new StyleClusterQuad();
00107   (*child)->setStyle(getStyle());
00108   m_isSimple = false; //Make sure the parent knows it has a non-null child now.
00109 
00110   if(numNullChildren() == 0) {
00111     setStyle(0); //nothing is using this anymore
00112   }
00113 }
00114 void StyleClusterQuad::setStyle(KSpreadStyle * style) {
00115   if(m_style && m_style->release()) {
00116     delete m_style;
00117   }
00118   m_style = style;
00119   if(m_style)
00120     m_style->addRef();
00121 }
00122 
00123 StyleClusterQuad::StyleClusterQuad()
00124 : m_style(NULL),
00125   m_isSimple(true),
00126   m_topLeft(NULL),
00127   m_topRight(NULL),
00128   m_bottomLeft(NULL),
00129   m_bottomRight(NULL)
00130 {
00131 }
00132 
00133 StyleClusterQuad::~StyleClusterQuad()
00134 {
00135   if (m_style && m_style->release())
00136   {
00137     delete m_style;
00138     m_style = NULL;
00139   }
00140   
00141   if (!m_isSimple) //there are non-null pointers
00142   {
00143     if (m_topLeft)
00144       delete m_topLeft;
00145     if (m_topRight)
00146       delete m_topRight;
00147     if (m_bottomLeft)
00148       delete m_bottomLeft;
00149     if (m_bottomRight)
00150       delete m_bottomRight;
00151     m_topLeft = m_topRight = m_bottomLeft = m_bottomRight = 0;
00152   }
00153 }
00154 
00155 int StyleClusterQuad::numNullChildren() {
00156   int num_children = 0;
00157   if(!m_topLeft) num_children++;
00158   if(!m_topRight) num_children++;
00159   if(!m_bottomRight) num_children++;
00160   if(!m_bottomLeft ) num_children++;
00161   return num_children;
00162 }
00163 
00164 //end of StyleClusterQuad
00165 //start of StyleCluster
00166 
00167 StyleCluster::StyleCluster(KSpreadSheet* sheet)
00168 : m_sheet(sheet)
00169 {
00170   Q_ASSERT(sheet); if(!sheet) return;
00171   // create quad tree
00172   // don't use KSpreadFormat, it seems to be deprecated anyway...
00173   m_topQuad = new StyleClusterQuad();
00174   m_topQuad->setStyle(sheet->doc()->styleManager()->defaultStyle());
00175 }
00176 
00177 
00178 
00179 StyleCluster::~StyleCluster()
00180 {
00181   if (m_topQuad)
00182   {
00183     delete m_topQuad;
00184     m_topQuad=NULL;
00185   }
00186 }
00187 
00188 void StyleCluster::setStyle( const KSpreadRange & range, KSpreadStyle * style)
00189 {
00190   QValueStack< KSpreadRange > ranges;
00191   ranges.push(range);
00192   
00193   KSpreadRange current_range;
00194   
00195   while(!ranges.isEmpty()) {
00196     current_range = ranges.pop();
00197     
00198     
00199     StyleClusterQuad** current_node = &m_topQuad;
00200     StyleClusterQuad* last_node = NULL;
00201     int x_offset = 0;
00202     int y_offset = 0;
00203     int quad_size = KS_Max_Quad;
00204     
00205     int range_width = current_range.startCol()- current_range.endCol();
00206     int range_height = current_range.startRow()- current_range.endRow();
00207     int max_quad_size_wanted = (range_width > range_height)?range_width:range_height;
00208     
00209     while( x_offset != current_range.startCol() || 
00210            y_offset != current_range.startRow() ||
00211            quad_size > max_quad_size_wanted ) {
00212       //Note this function changes most of its parameters
00213       stepDownOne(current_node, current_range.startCol(), x_offset, current_range.startRow(), y_offset, quad_size);
00214       if(*current_node == NULL) {
00215         last_node->makeChild(current_node);
00216       }
00217     }
00218     (*current_node)->setStyle( style );
00219     
00220     //FIXME - finish this function
00221     if( quad_size < range_width ) {
00222       //ranges.push( new );
00223     }
00224   } 
00225 }
00226 
00227 // A Simple (m_isSimple) will never have the same style as the parent.  Instead, if the styles
00228 // are the same, the instance wouldn't exist and the parent would point to null.
00229 // If a Quad has a Simple, then it must also have a null.  If temporarily it doesn't, then the 
00230 // Simple must be deleted, and made a null and the Quad given that style.
00231 void StyleCluster::setStyle( int x, int y, KSpreadStyle * style)
00232 {
00233   Q_ASSERT(m_topQuad);
00234   
00235   StyleClusterQuad** current_node = &m_topQuad;
00236   StyleClusterQuad* last_node = NULL;
00237   int x_offset = 0;
00238   int y_offset = 0;
00239   int quad_size = KS_Max_Quad;
00240 
00241   if( m_topQuad->m_isSimple && style == m_topQuad->getStyle() )
00242       return;
00243 
00244   //let's keep track of the path we went down, so we can go up as well
00245   // note that we store pointers to pointers 
00246   QValueStack<StyleClusterQuad**> path;
00247   
00248   while (true)
00249   {
00250     Q_ASSERT (current_node);
00251     Q_ASSERT( *current_node);
00252     Q_ASSERT( quad_size > 0); // we can't have a quad of width 1!
00253     
00254     path.push(current_node);
00255     last_node = *current_node;
00256     
00257     //Note this function modifies its arguments
00258     stepDownOne(current_node, x, x_offset, y, y_offset, quad_size);
00259     
00260     //quad_size is now the size (size of width, and size of height) of current_node
00261     //Now we have gone down one step.  The current node may be null, in which case
00262     //our style is the style of the parent, or it's Simple,
00263     //in which case we need to check whether we to subdivide, or it's a quad, in which case
00264     //we don't do anything until we loop again around this while loop and go down into that quad.
00265     
00266     if( !*current_node ) { 
00267       //Okay, so we are using the style of the parent.
00268       //If we are not down to a single cell, then we will have to create a quad for current node,
00269       //and go down into it continously until there are no more quads to create.
00270       
00271       //The whole of this section is already this style.  No need to do anything.
00272       if( style == last_node->getStyle() ) return;
00273 
00274       if(quad_size == 1) {  //We are now on a single cell
00275     int num_null_children_in_parent = last_node->numNullChildren();
00276 
00277     Q_ASSERT(last_node->getStyle() != NULL);
00278     
00279         Q_ASSERT(num_null_children_in_parent > 0);
00280     if(num_null_children_in_parent == 1) {// We are the only one using the style info in parent, so just change the m_style in parent
00281 
00282       last_node->setStyle(style);
00283       simplify(path);
00284           Q_ASSERT( !last_node->m_isSimple);
00285     } else {  //someone else in the parent is using the style info in parent, so we have to create our own child
00286           last_node->makeChild(current_node);
00287     }
00288         return;
00289       }
00290       
00291       last_node->makeChild(current_node);
00292 
00293     }
00294   }
00295   
00296   return;
00297   
00298 }
00299 
00300 void StyleCluster::simplify(  QValueStack<StyleClusterQuad**> &path ) { 
00301   StyleClusterQuad** current_node;
00302   StyleClusterQuad* last_node = NULL;
00303 
00304   while (true) {
00305   
00306     if( path.isEmpty()) return;
00307     current_node = path.pop();
00308     if( !path.isEmpty() && path.top())
00309         last_node = *(path.top());
00310     
00311     Q_ASSERT( current_node && *current_node);
00312     
00313     if((*current_node)->m_bottomLeft && (*current_node)->m_bottomLeft->m_isSimple && (*current_node)->m_bottomLeft->getStyle() == (*current_node)->getStyle()) {
00314         delete (*current_node)->m_bottomLeft;
00315         (*current_node)->m_bottomLeft = 0;
00316     }
00317     if((*current_node)->m_bottomRight && (*current_node)->m_bottomRight->m_isSimple && (*current_node)->m_bottomRight->getStyle() == (*current_node)->getStyle()) {
00318         delete (*current_node)->m_bottomRight;
00319         (*current_node)->m_bottomRight = 0;
00320     }
00321     if((*current_node)->m_topLeft && (*current_node)->m_topLeft->m_isSimple && (*current_node)->m_topLeft->getStyle() == (*current_node)->getStyle()) {
00322         delete (*current_node)->m_topLeft;
00323         (*current_node)->m_topLeft = 0;
00324     }
00325     if((*current_node)->m_topRight && (*current_node)->m_topRight->m_isSimple && (*current_node)->m_topRight->getStyle() == (*current_node)->getStyle()) {
00326         delete (*current_node)->m_topRight;
00327         (*current_node)->m_topRight = 0;
00328     }
00329     
00330     
00331     if((*current_node)->numNullChildren() == 4) { //we can simplify - all children in the quad are pointing to use.
00332       (*current_node)->m_isSimple = true;
00333             
00334       if(!last_node) {
00335         
00336         Q_ASSERT( m_topQuad == *current_node );
00337     
00338         return;
00339       }
00340       if(last_node->getStyle() == (*current_node)->getStyle()) {
00341         //Parent has the same style, so delete us, then go back up recursively
00342         delete (*current_node);
00343         *current_node = 0;
00344       } else if(last_node->getStyle() == 0 ) {
00345         //the parent has only quads, and we are now the only simple one
00346         //so delete us, and set the style for the parent
00347         last_node->setStyle( (*current_node)->getStyle() );
00348         delete (*current_node);
00349         *current_node = 0; 
00350         return;
00351       } else if(last_node->numNullChildren() == 0) {
00352         //The style in the parent is different, but we are the only one using that style
00353         last_node->setStyle( (*current_node)->getStyle() );
00354         delete (*current_node);
00355         (*current_node) = 0;
00356       } else {
00357         //The style in the parent is different, and it has children using that style, so there is nothing we can do.
00358         return;
00359       }
00360     }
00361   }
00362 }
00363 
00364 const KSpreadStyle& StyleCluster::lookup(int x, int y) {
00365   return *(lookupNode(x,y)->getStyle());
00366 }
00367 
00368 void StyleCluster::stepDownOne(StyleClusterQuad **& current_node, int x, int & x_offset, int y, int & y_offset, int & quad_size) {
00369 
00370   quad_size /= 2;
00371   if( x - x_offset < quad_size ) {
00372     if( y - y_offset < quad_size ) {
00373         current_node = &((*current_node)->m_topLeft);
00374     }
00375     else {
00376         current_node = &((*current_node)->m_bottomLeft);
00377         y_offset += quad_size;
00378     }
00379   } else {
00380     if( y - y_offset < quad_size ) {
00381         current_node = &((*current_node)->m_topRight);
00382         x_offset += quad_size;
00383     }
00384     else {
00385         current_node = &((*current_node)->m_bottomRight);
00386         y_offset += quad_size;
00387         x_offset += quad_size;
00388     }
00389   }
00390 }
00391 
00392 StyleClusterQuad* StyleCluster::lookupNode(int x, int y) {
00393   //walk over quad-tree
00394   // see gnumeric sheet-style.c  cell_tile_apply_pos(...)
00395   //  these implementations rather differ though
00396   
00397   Q_ASSERT(m_topQuad);
00398   
00399   StyleClusterQuad** current_node = &m_topQuad;
00400   StyleClusterQuad* last_node = NULL;
00401   int x_offset = 0;
00402   int y_offset = 0;
00403   int quad_size = KS_Max_Quad;
00404   
00405   while ( *current_node && !(*current_node)->m_isSimple )
00406   {
00407     last_node = *current_node;
00408     //Below function modifies most of its parameters!
00409     stepDownOne(current_node, x, x_offset, y, y_offset, quad_size);
00410   }
00411   
00412   if( !(*current_node) ) return last_node;
00413   
00414   return *current_node;
00415 }
00416 
00417 }
00418 
00419 #include "stylecluster.moc"
KDE Logo
This file is part of the documentation for kspread Library Version 1.4.2.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Mon Feb 13 09:43:38 2006 by doxygen 1.4.2 written by Dimitri van Heesch, © 1997-2003