git.sesse.net Git - vlc/blob - modules/gui/skins2/utils/var_tree.cpp

   1 /*****************************************************************************
   2  * var_tree.cpp
   3  *****************************************************************************
   4  * Copyright (C) 2005 the VideoLAN team
   5  * $Id$
   6  *
   7  * Authors: Antoine Cellerier <dionoea@videolan.org>
   8  *          Clément Stenac <zorglub@videolan.org>
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  23  *****************************************************************************/
  24
  25 #include "var_tree.hpp"
  26
  27
  28 const string VarTree::m_type = "tree";
  29
  30 VarTree::VarTree( intf_thread_t *pIntf )
  31     : Variable( pIntf ), m_id( 0 ), m_selected( false ), m_playing( false ),
  32     m_expanded( false ), m_deleted( false ),
  33     m_pData( NULL ), m_pParent( NULL ), m_readonly( false )
  34 {
  35     // Create the position variable
  36     m_cPosition = VariablePtr( new VarPercent( pIntf ) );
  37     getPositionVar().set( 1.0 );
  38 }
  39
  40 VarTree::VarTree( intf_thread_t *pIntf, VarTree *pParent, int id,
  41                   const UStringPtr &rcString, bool selected, bool playing,
  42                   bool expanded, bool readonly,
  43                   void *pData )
  44     : Variable( pIntf ), m_id( id ), m_cString( rcString ),
  45     m_selected( selected ), m_playing( playing ), m_expanded( expanded ),
  46     m_deleted( false ), m_pData( pData ), m_pParent( pParent ),
  47     m_readonly( readonly )
  48 {
  49     // Create the position variable
  50     m_cPosition = VariablePtr( new VarPercent( pIntf ) );
  51     getPositionVar().set( 1.0 );
  52 }
  53
  54 VarTree::~VarTree()
  55 {
  56 /// \todo check that children are deleted
  57 }
  58
  59 void VarTree::add( int id, const UStringPtr &rcString, bool selected,
  60                    bool playing, bool expanded, bool readonly,
  61                    void *pData )
  62 {
  63     m_children.push_back( VarTree( getIntf(), this, id, rcString, selected,
  64                                    playing, expanded, readonly,
  65                                    pData ) );
  66 }
  67
  68 void VarTree::delSelected()
  69 {
  70     Iterator it = begin();
  71     while( it != end() )
  72     {
  73         //dig down the tree
  74         if( size() ) it->delSelected();
  75         //stay on some level
  76         if( it->m_selected )
  77         {
  78             Iterator oldIt = it;
  79             it++;
  80             m_children.erase( oldIt );
  81         }
  82         else
  83         {
  84             it++;
  85         }
  86     }
  87 }
  88
  89 void VarTree::clear()
  90 {
  91     m_children.clear();
  92 }
  93
  94 VarTree::Iterator VarTree::operator[]( int n )
  95 {
  96     Iterator it;
  97     int i;
  98     for( it = begin(), i = 0;
  99          i < n && it != end();
 100          it++, i++ );
 101     return it;
 102 }
 103
 104 VarTree::ConstIterator VarTree::operator[]( int n ) const
 105 {
 106     ConstIterator it;
 107     int i;
 108     for( it = begin(), i = 0;
 109          i < n && it != end();
 110          it++, i++ );
 111     return it;
 112 }
 113
 114 VarTree::Iterator VarTree::getNextSibling( VarTree::Iterator current )
 115 {
 116     VarTree *p_parent = current->parent();
 117     if( p_parent  && current != p_parent->end() )
 118     {
 119         Iterator it = current->parent()->begin();
 120         while( it != p_parent->end() && it != current ) it++;
 121         if( it != p_parent->end() )
 122         {
 123             it++;
 124             return it;
 125         }
 126         return root()->end();
 127     }
 128     return root()->end();
 129 }
 130
 131 /* find iterator to next ancestor
 132  * ... which means parent++ or grandparent++ or grandgrandparent++ ... */
 133 VarTree::Iterator VarTree::next_uncle()
 134 {
 135     VarTree *p_parent = parent();
 136     if( p_parent != NULL )
 137     {
 138         VarTree *p_grandparent = p_parent->parent();
 139         while( p_grandparent != NULL )
 140         {
 141             Iterator it = p_grandparent->begin();
 142             while( it != p_grandparent->end() && &(*it) != p_parent ) it++;
 143             if( it != p_grandparent->end() )
 144             {
 145                 it++;
 146                 if( it != p_grandparent->end() )
 147                 {
 148                     return it;
 149                 }
 150             }
 151             if( p_grandparent->parent() )
 152             {
 153                 p_parent = p_grandparent;
 154                 p_grandparent = p_parent->parent();
 155             }
 156             else
 157                 p_grandparent = NULL;
 158         }
 159     }
 160
 161     /* if we didn't return before, it means that we've reached the end */
 162     return root()->end();
 163 }
 164
 165 VarTree::Iterator VarTree::prev_uncle()
 166 {
 167     VarTree *p_parent = parent();
 168     if( p_parent != NULL )
 169     {
 170         VarTree *p_grandparent = p_parent->parent();
 171         while( p_grandparent != NULL )
 172         {
 173             Iterator it = p_grandparent->end();
 174             while( it != p_grandparent->begin() && &(*it) != p_parent ) it--;
 175             if( it != p_grandparent->begin() )
 176             {
 177                 it--;
 178                 if( it != p_grandparent->begin() )
 179                 {
 180                     return it;
 181                 }
 182             }
 183             if( p_grandparent->parent() )
 184             {
 185                 p_parent = p_grandparent;
 186                 p_grandparent = p_parent->parent();
 187             }
 188             else
 189                 p_grandparent = NULL;
 190         }
 191     }
 192
 193     /* if we didn't return before, it means that we've reached the end */
 194     return root()->begin();
 195 }
 196
 197
 198 void VarTree::checkParents( VarTree *pParent )
 199 {
 200     m_pParent = pParent;
 201     Iterator it = begin();
 202     while( it != end() )
 203     {
 204         it->checkParents( this );
 205         it++;
 206     }
 207 }
 208
 209 int VarTree::visibleItems()
 210 {
 211     int i_count = size();
 212     Iterator it = begin();
 213     while( it != end() )
 214     {
 215         if( it->m_expanded )
 216         {
 217             i_count += it->visibleItems();
 218         }
 219         it++;
 220     }
 221     return i_count;
 222 }
 223
 224 VarTree::Iterator VarTree::getVisibleItem( int n )
 225 {
 226     Iterator it = begin();
 227     while( it != end() )
 228     {
 229         n--;
 230         if( n <= 0 )
 231             return it;
 232         if( it->m_expanded )
 233         {
 234             int i;
 235             i = n - it->visibleItems();
 236             if( i <= 0 ) return it->getVisibleItem( n );
 237             n = i;
 238         }
 239         it++;
 240     }
 241     return end();
 242 }
 243
 244 VarTree::Iterator VarTree::getLeaf( int n )
 245 {
 246     Iterator it = begin();
 247     while( it != end() )
 248     {
 249         if( it->size() )
 250         {
 251             int i;
 252             i = n - it->countLeafs();
 253             if( i <= 0 ) return it->getLeaf( n );
 254             n = i;
 255         }
 256         else
 257         {
 258             n--;
 259             if( n <= 0 )
 260                 return it;
 261         }
 262         it++;
 263     }
 264     return end();
 265 }
 266
 267 VarTree::Iterator VarTree::getNextVisibleItem( Iterator it )
 268 {
 269     if( it->m_expanded && it->size() )
 270     {
 271         it = it->begin();
 272     }
 273     else
 274     {
 275         VarTree::Iterator it_old = it;
 276         it++;
 277         // Was 'it' the last brother? If so, look for uncles
 278         if( it_old->parent() && it_old->parent()->end() == it )
 279         {
 280             it = it_old->next_uncle();
 281         }
 282     }
 283     return it;
 284 }
 285
 286 VarTree::Iterator VarTree::getPrevVisibleItem( Iterator it )
 287 {
 288     VarTree::Iterator it_old = it;
 289     if( it == root()->begin() || it == ++(root()->begin()) ) return it;
 290
 291     /* Was it the first child of its parent ? */
 292     if( it->parent() && it == it->parent()->begin() )
 293     {
 294         /* Yes, get previous uncle */
 295         it = it_old->prev_uncle();
 296     }
 297     else
 298         it--;
 299
 300     /* We have found an expanded uncle, take its last child */
 301     while( it != root()->begin() && it->size() && it->m_expanded )
 302     {
 303             it = it->end();
 304             it--;
 305     }
 306     return it;
 307 }
 308
 309 VarTree::Iterator VarTree::getNextItem( Iterator it )
 310 {
 311     if( it->size() )
 312     {
 313         it = it->begin();
 314     }
 315     else
 316     {
 317         VarTree::Iterator it_old = it;
 318         it++;
 319         // Was 'it' the last brother? If so, look for uncles
 320         if( it_old->parent() && it_old->parent()->end() == it )
 321         {
 322             it = it_old->next_uncle();
 323         }
 324     }
 325     return it;
 326 }
 327
 328 VarTree::Iterator VarTree::getPrevItem( Iterator it )
 329 {
 330     VarTree::Iterator it_old = it;
 331     if( it == root()->begin() || it == ++(root()->begin()) ) return it;
 332
 333     /* Was it the first child of its parent ? */
 334     if( it->parent() && it == it->parent()->begin() )
 335     {
 336         /* Yes, get previous uncle */
 337         it = it_old->prev_uncle();
 338     }
 339     else
 340         it--;
 341
 342     /* We have found an expanded uncle, take its last child */
 343     while( it != root()->begin() && it->size() )
 344     {
 345             it = it->end();
 346             it--;
 347     }
 348     return it;
 349 }
 350
 351 VarTree::Iterator VarTree::getNextLeaf( Iterator it )
 352 {
 353     do
 354     {
 355         it = getNextItem( it );
 356     }
 357     while( it != root()->end() && it->size() );
 358     return it;
 359 }
 360
 361 VarTree::Iterator VarTree::getPrevLeaf( Iterator it )
 362 {
 363     do
 364     {
 365         it = getPrevItem( it );
 366     }
 367     while( it != root()->begin() && it->size() ); /* FIXME ? */
 368     if( it == root()->begin() ) it = firstLeaf();
 369     return it;
 370 }
 371
 372 VarTree::Iterator VarTree::findById( int id )
 373 {
 374     for (Iterator it = begin(); it != end(); ++it )
 375     {
 376         if( it->m_id == id )
 377         {
 378             return it;
 379         }
 380         Iterator result = it->findById( id );
 381         if( result != it->end() ) return result;
 382     }
 383     return end();
 384 }
 385
 386
 387 void VarTree::ensureExpanded( VarTree::Iterator it )
 388 {
 389     /// Don't expand ourselves, only our parents
 390     VarTree *current = &(*it);
 391     current = current->parent();
 392     while( current->parent() != NULL )
 393     {
 394         current->m_expanded = true;
 395         current = current->parent();
 396     }
 397 }
 398
 399 int VarTree::countLeafs()
 400 {
 401     if( size() == 0 ) return 1;
 402
 403     int i_count = 0;
 404     Iterator it = begin();
 405     while( it != end() )
 406     {
 407         i_count += it->countLeafs();
 408         it++;
 409     }
 410     return i_count;
 411 }
 412
 413 VarTree::Iterator VarTree::firstLeaf()
 414 {
 415     Iterator b = root()->begin();
 416     if( b->size() ) return getNextLeaf( b );
 417     return b;
 418 }
 419