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::getNextSiblingOrUncle()
 115 {
 116     VarTree *p_parent = parent();
 117     if( p_parent )
 118     {
 119         Iterator it = p_parent->begin();
 120         while( it != p_parent->end() && &(*it) != this ) ++it;
 121         if( it != p_parent->end() )
 122         {
 123             Iterator current = it;
 124             ++it;
 125             if( it != p_parent->end() )
 126                 return it;
 127             else
 128                 return current->next_uncle();
 129         }
 130         else
 131         {
 132             msg_Err( getIntf(), "should never occur" );
 133             return end();
 134         }
 135     }
 136     return end();
 137 }
 138
 139 /* find iterator to next ancestor
 140  * ... which means parent++ or grandparent++ or grandgrandparent++ ... */
 141 VarTree::Iterator VarTree::next_uncle()
 142 {
 143     VarTree *p_parent = parent();
 144     if( p_parent != NULL )
 145     {
 146         VarTree *p_grandparent = p_parent->parent();
 147         while( p_grandparent != NULL )
 148         {
 149             Iterator it = p_grandparent->begin();
 150             while( it != p_grandparent->end() && &(*it) != p_parent ) it++;
 151             if( it != p_grandparent->end() )
 152             {
 153                 it++;
 154                 if( it != p_grandparent->end() )
 155                 {
 156                     return it;
 157                 }
 158             }
 159             if( p_grandparent->parent() )
 160             {
 161                 p_parent = p_grandparent;
 162                 p_grandparent = p_parent->parent();
 163             }
 164             else
 165                 p_grandparent = NULL;
 166         }
 167     }
 168
 169     /* if we didn't return before, it means that we've reached the end */
 170     return root()->end();
 171 }
 172
 173 VarTree::Iterator VarTree::prev_uncle()
 174 {
 175     VarTree *p_parent = parent();
 176     if( p_parent != NULL )
 177     {
 178         VarTree *p_grandparent = p_parent->parent();
 179         while( p_grandparent != NULL )
 180         {
 181             Iterator it = p_grandparent->end();
 182             while( it != p_grandparent->begin() && &(*it) != p_parent ) it--;
 183             if( it != p_grandparent->begin() )
 184             {
 185                 it--;
 186                 if( it != p_grandparent->begin() )
 187                 {
 188                     return it;
 189                 }
 190             }
 191             if( p_grandparent->parent() )
 192             {
 193                 p_parent = p_grandparent;
 194                 p_grandparent = p_parent->parent();
 195             }
 196             else
 197                 p_grandparent = NULL;
 198         }
 199     }
 200
 201     /* if we didn't return before, it means that we've reached the end */
 202     return root()->begin();
 203 }
 204
 205 int VarTree::visibleItems()
 206 {
 207     int i_count = size();
 208     Iterator it = begin();
 209     while( it != end() )
 210     {
 211         if( it->m_expanded )
 212         {
 213             i_count += it->visibleItems();
 214         }
 215         it++;
 216     }
 217     return i_count;
 218 }
 219
 220 VarTree::Iterator VarTree::getVisibleItem( int n )
 221 {
 222     Iterator it = begin();
 223     while( it != end() )
 224     {
 225         n--;
 226         if( n <= 0 )
 227             return it;
 228         if( it->m_expanded )
 229         {
 230             int i;
 231             i = n - it->visibleItems();
 232             if( i <= 0 ) return it->getVisibleItem( n );
 233             n = i;
 234         }
 235         it++;
 236     }
 237     return end();
 238 }
 239
 240 VarTree::Iterator VarTree::getLeaf( int n )
 241 {
 242     Iterator it = begin();
 243     while( it != end() )
 244     {
 245         if( it->size() )
 246         {
 247             int i;
 248             i = n - it->countLeafs();
 249             if( i <= 0 ) return it->getLeaf( n );
 250             n = i;
 251         }
 252         else
 253         {
 254             n--;
 255             if( n <= 0 )
 256                 return it;
 257         }
 258         it++;
 259     }
 260     return end();
 261 }
 262
 263 VarTree::Iterator VarTree::getNextVisibleItem( Iterator it )
 264 {
 265     if( it->m_expanded && it->size() )
 266     {
 267         it = it->begin();
 268     }
 269     else
 270     {
 271         VarTree::Iterator it_old = it;
 272         it++;
 273         // Was 'it' the last brother? If so, look for uncles
 274         if( it_old->parent() && it_old->parent()->end() == it )
 275         {
 276             it = it_old->next_uncle();
 277         }
 278     }
 279     return it;
 280 }
 281
 282 VarTree::Iterator VarTree::getPrevVisibleItem( Iterator it )
 283 {
 284     VarTree::Iterator it_old = it;
 285     if( it == root()->begin() || it == ++(root()->begin()) ) return it;
 286
 287     /* Was it the first child of its parent ? */
 288     if( it->parent() && it == it->parent()->begin() )
 289     {
 290         /* Yes, get previous uncle */
 291         it = it_old->prev_uncle();
 292     }
 293     else
 294         it--;
 295
 296     /* We have found an expanded uncle, take its last child */
 297     while( it != root()->begin() && it->size() && it->m_expanded )
 298     {
 299             it = it->end();
 300             it--;
 301     }
 302     return it;
 303 }
 304
 305 VarTree::Iterator VarTree::getNextItem( Iterator it )
 306 {
 307     if( it->size() )
 308     {
 309         it = it->begin();
 310     }
 311     else
 312     {
 313         VarTree::Iterator it_old = it;
 314         it++;
 315         // Was 'it' the last brother? If so, look for uncles
 316         if( it_old->parent() && it_old->parent()->end() == it )
 317         {
 318             it = it_old->next_uncle();
 319         }
 320     }
 321     return it;
 322 }
 323
 324 VarTree::Iterator VarTree::getPrevItem( Iterator it )
 325 {
 326     VarTree::Iterator it_old = it;
 327     if( it == root()->begin() || it == ++(root()->begin()) ) return it;
 328
 329     /* Was it the first child of its parent ? */
 330     if( it->parent() && it == it->parent()->begin() )
 331     {
 332         /* Yes, get previous uncle */
 333         it = it_old->prev_uncle();
 334     }
 335     else
 336         it--;
 337
 338     /* We have found an expanded uncle, take its last child */
 339     while( it != root()->begin() && it->size() )
 340     {
 341             it = it->end();
 342             it--;
 343     }
 344     return it;
 345 }
 346
 347 VarTree::Iterator VarTree::getNextLeaf( Iterator it )
 348 {
 349     do
 350     {
 351         it = getNextItem( it );
 352     }
 353     while( it != root()->end() && it->size() );
 354     return it;
 355 }
 356
 357 VarTree::Iterator VarTree::getPrevLeaf( Iterator it )
 358 {
 359     do
 360     {
 361         it = getPrevItem( it );
 362     }
 363     while( it != root()->begin() && it->size() ); /* FIXME ? */
 364     if( it == root()->begin() ) it = firstLeaf();
 365     return it;
 366 }
 367
 368 VarTree::Iterator VarTree::findById( int id )
 369 {
 370     for (Iterator it = begin(); it != end(); ++it )
 371     {
 372         if( it->m_id == id )
 373         {
 374             return it;
 375         }
 376         Iterator result = it->findById( id );
 377         if( result != it->end() ) return result;
 378     }
 379     return end();
 380 }
 381
 382
 383 void VarTree::ensureExpanded( VarTree::Iterator it )
 384 {
 385     /// Don't expand ourselves, only our parents
 386     VarTree *current = &(*it);
 387     current = current->parent();
 388     while( current->parent() != NULL )
 389     {
 390         current->m_expanded = true;
 391         current = current->parent();
 392     }
 393 }
 394
 395 int VarTree::countLeafs()
 396 {
 397     if( size() == 0 ) return 1;
 398
 399     int i_count = 0;
 400     Iterator it = begin();
 401     while( it != end() )
 402     {
 403         i_count += it->countLeafs();
 404         it++;
 405     }
 406     return i_count;
 407 }
 408
 409 VarTree::Iterator VarTree::firstLeaf()
 410 {
 411     Iterator b = root()->begin();
 412     if( b->size() ) return getNextLeaf( b );
 413     return b;
 414 }
 415
 416 void VarTree::cascadeDelete()
 417 {
 418     m_deleted = true;
 419     for( Iterator it = begin(); it != end(); ++it )
 420     {
 421         it->cascadeDelete();
 422     }
 423 }