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