* 2nd review of /src/* \ libvlc.h (refs #438)
[vlc.git] / src / playlist / view.c
1 /*****************************************************************************
2  * view.c : Playlist views functions
3  *****************************************************************************
4  * Copyright (C) 1999-2004 the VideoLAN team
5  * $Id$
6  *
7  * Authors: ClĂ©ment Stenac <zorglub@videolan.org>
8  *
9  * This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation; either version 2 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
22  *****************************************************************************/
23 #include <stdlib.h>                                      /* free(), strtol() */
24 #include <stdio.h>                                              /* sprintf() */
25 #include <string.h>                                            /* strerror() */
26
27 #include <vlc/vlc.h>
28 #include <vlc/input.h>
29
30 #include "vlc_playlist.h"
31
32 #undef PLAYLIST_DEBUG
33
34 /************************************************************************
35  * Local prototypes
36  ************************************************************************/
37
38 /* TODO: inline */
39 playlist_item_t *playlist_FindDirectParent( playlist_t *p_playlist,
40                                         playlist_item_t *, int );
41
42 playlist_item_t *playlist_RecursiveFindNext( playlist_t *p_playlist,
43                 int i_view,
44                 playlist_item_t *p_root,
45                 playlist_item_t *p_item,
46                 playlist_item_t *p_parent );
47
48 playlist_item_t *playlist_RecursiveFindPrev( playlist_t *p_playlist,
49                 int i_view,
50                 playlist_item_t *p_root,
51                 playlist_item_t *p_item,
52                 playlist_item_t *p_parent );
53
54 void playlist_NodeDump( playlist_t *p_playlist, playlist_item_t *p_item,
55                         int i_level );
56
57 /**********************************************************************
58  * Exported View management functions
59  **********************************************************************/
60
61 /**
62  * Create a new view
63  *
64  * \param p_playlist a playlist object
65  * \param i_id the view identifier
66  * \return the new view or NULL on failure
67  */
68 playlist_view_t * playlist_ViewCreate( playlist_t *p_playlist, int i_id,
69                                        char *psz_name )
70 {
71     playlist_view_t * p_view;
72
73     p_view = malloc( sizeof( playlist_view_t ) );
74
75     memset( p_view, 0, sizeof( playlist_view_t ) );
76
77     p_view->p_root = playlist_NodeCreate( p_playlist, i_id, NULL, NULL );
78     p_view->i_id = i_id;
79     p_view->psz_name = psz_name ? strdup( psz_name ) : strdup(_("Undefined") );
80
81     return p_view;
82 }
83
84 /**
85  * Creates a new view and add it to the list
86  *
87  * This function must be entered without the playlist lock
88  *
89  * \param p_playlist a playlist object
90  * \param i_id the view identifier
91  * \return VLC_SUCCESS or an error
92  */
93 int playlist_ViewInsert( playlist_t *p_playlist, int i_id, char *psz_name )
94 {
95     playlist_view_t *p_view =
96         playlist_ViewCreate( p_playlist, i_id , psz_name );
97     if( !p_view )
98     {
99         msg_Err( p_playlist, "Creation failed" );
100         return VLC_EGENERIC;
101     }
102
103     vlc_mutex_lock( &p_playlist->object_lock );
104
105     INSERT_ELEM( p_playlist->pp_views, p_playlist->i_views,
106                  p_playlist->i_views, p_view );
107
108     vlc_mutex_unlock( &p_playlist->object_lock );
109     return VLC_SUCCESS;
110 }
111
112
113 /**
114  * Deletes a view
115  *
116  * This function must be entered wit the playlist lock
117  *
118  * \param p_view the view to delete
119  * \return nothing
120  */
121 int playlist_ViewDelete( playlist_t *p_playlist,playlist_view_t *p_view )
122 {
123     playlist_NodeDelete( p_playlist, p_view->p_root, VLC_TRUE, VLC_TRUE );
124     REMOVE_ELEM( p_playlist->pp_views, p_playlist->i_views, 0 );
125     return VLC_SUCCESS;
126 }
127
128
129 /**
130  * Dumps the content of a view
131  *
132  * \param p_playlist the playlist
133  * \param p_view the view to dump
134  * \return nothing
135  */
136 int playlist_ViewDump( playlist_t *p_playlist, playlist_view_t *p_view )
137 {
138 #ifdef PLAYLIST_DEBUG
139     msg_Dbg( p_playlist, "dumping view %i",p_view->i_id );
140     playlist_NodeDump( p_playlist,p_view->p_root, 1 );
141 #endif
142     return VLC_SUCCESS;
143 }
144
145 /**
146  * Counts the items of a view
147  *
148  * \param p_playlist the playlist
149  * \param p_view the view to count
150  * \return the number of items
151  */
152 int playlist_ViewItemCount( playlist_t *p_playlist,
153                             playlist_view_t *p_view )
154 {
155     return playlist_NodeChildrenCount( p_playlist, p_view->p_root );
156 }
157
158
159 /**
160  * Updates a view. Only make sense for "sorted" and "ALL" views
161  *
162  * \param p_playlist the playlist
163  * \param i_view the view to update
164  * \return nothing
165  */
166 int playlist_ViewUpdate( playlist_t *p_playlist, int i_view)
167 {
168     playlist_view_t *p_view = playlist_ViewFind( p_playlist, i_view );
169
170     if( p_view == NULL )
171     {
172         return VLC_EGENERIC;
173     }
174
175     if( i_view == VIEW_ALL )
176     {
177         p_view->p_root->i_children = p_playlist->i_size;
178         p_view->p_root->pp_children = p_playlist->pp_items;
179     }
180
181     /* Handle update of sorted views here */
182     if( i_view >= VIEW_FIRST_SORTED )
183     {
184         int i_sort_type;
185         playlist_ViewEmpty( p_playlist, i_view, VLC_FALSE );
186
187         switch( i_view )
188         {
189             case VIEW_S_AUTHOR: i_sort_type = SORT_AUTHOR;break;
190             case VIEW_S_ALBUM: i_sort_type = SORT_ALBUM;break;
191             case VIEW_S_GENRE: i_sort_type = SORT_GENRE;break;
192             default: i_sort_type = SORT_AUTHOR;
193         }
194         playlist_NodeGroup( p_playlist, i_view, p_view->p_root,
195                             p_playlist->pp_items,p_playlist->i_size,
196                             i_sort_type, ORDER_NORMAL );
197     }
198
199
200     return VLC_SUCCESS;
201 }
202
203
204 /**
205  * Find a view
206  *
207  * \param p_playlist the playlist
208  * \param i_id the id to find
209  * \return the found view or NULL if not found
210  */
211 playlist_view_t *playlist_ViewFind( playlist_t *p_playlist, int i_id )
212 {
213     int i;
214     for( i=0 ; i< p_playlist->i_views ; i++ )
215     {
216         if( p_playlist->pp_views[i]->i_id == i_id )
217         {
218             return p_playlist->pp_views[i];
219         }
220     }
221     return NULL;
222 }
223
224
225 int playlist_ViewEmpty( playlist_t *p_playlist, int i_view,
226                         vlc_bool_t b_delete_items )
227 {
228     playlist_view_t *p_view = playlist_ViewFind( p_playlist, i_view );
229
230     if( p_view == NULL )
231     {
232         return VLC_EGENERIC;
233     }
234
235     return playlist_NodeEmpty( p_playlist, p_view->p_root, b_delete_items );
236 }
237
238 /**********************************************************************
239  * Exported Nodes management functions
240  **********************************************************************/
241
242
243
244 /**
245  * Create a playlist node
246  *
247  * \param p_playlist the playlist
248  * \paam psz_name the name of the node
249  * \param p_parent the parent node to attach to or NULL if no attach
250  * \return the new node
251  */
252 playlist_item_t * playlist_NodeCreate( playlist_t *p_playlist, int i_view,
253                                        char *psz_name,
254                                        playlist_item_t *p_parent )
255 {
256     /* Create the item */
257     playlist_item_t *p_item = (playlist_item_t *)malloc(
258                                         sizeof( playlist_item_t ) );
259     vlc_value_t val;
260     playlist_add_t *p_add;
261
262     if( p_item == NULL )
263     {
264         return NULL;
265     }
266     p_add = (playlist_add_t*)malloc( sizeof(playlist_add_t) );
267     if( p_add == NULL )
268     {
269         free( p_item );
270         return NULL;
271     }
272     vlc_input_item_Init( VLC_OBJECT(p_playlist), &p_item->input );
273
274     if( psz_name != NULL )
275     {
276         p_item->input.psz_name = strdup( psz_name );
277     }
278     else
279     {
280         p_item->input.psz_name = strdup( _("Undefined") );
281     }
282
283     p_item->input.psz_uri = NULL;
284
285     p_item->b_enabled = VLC_TRUE;
286     p_item->i_nb_played = 0;
287
288     p_item->i_flags = 0;
289
290     p_item->i_children = 0;
291     p_item->pp_children = NULL;
292
293     p_item->input.i_duration = -1;
294     p_item->input.ppsz_options = NULL;
295     p_item->input.i_options = 0;
296     p_item->input.i_categories = 0;
297     p_item->input.pp_categories = NULL;
298     p_item->input.i_id = ++p_playlist->i_last_id;
299
300     p_item->input.i_type = ITEM_TYPE_NODE;
301
302     p_item->pp_parents = NULL;
303     p_item->i_parents = 0;
304     p_item->i_serial = 0;
305
306     p_item->i_flags |= PLAYLIST_SKIP_FLAG; /* Default behaviour */
307
308     vlc_mutex_init( p_playlist, &p_item->input.lock );
309
310     INSERT_ELEM( p_playlist->pp_all_items,
311                  p_playlist->i_all_size,
312                  p_playlist->i_all_size,
313                  p_item );
314
315     if( p_parent != NULL )
316     {
317         playlist_NodeAppend( p_playlist, i_view, p_item, p_parent );
318     }
319
320     p_add->i_node = p_parent ? p_parent->input.i_id : -1;
321     p_add->i_item = p_item->input.i_id;
322     p_add->i_view = i_view;
323     val.p_address = p_add;
324     var_Set( p_playlist, "item-append", val);
325
326     free( p_add );
327
328     return p_item;
329 }
330
331 /**
332  * Remove all the children of a node
333  *
334  * This function must be entered with the playlist lock
335  *
336  * \param p_playlist the playlist
337  * \param p_root the node
338  * \param b_delete_items do we have to delete the children items ?
339  * \return VLC_SUCCESS or an error
340  */
341 int playlist_NodeEmpty( playlist_t *p_playlist, playlist_item_t *p_root,
342                         vlc_bool_t b_delete_items )
343 {
344     int i;
345     if( p_root->i_children == -1 )
346     {
347         return VLC_EGENERIC;
348     }
349
350     /* Delete the children */
351     for( i =  p_root->i_children-1 ; i >= 0 ;i-- )
352     {
353         if( p_root->pp_children[i]->i_children > -1 )
354         {
355             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
356                                  b_delete_items , VLC_FALSE );
357         }
358         else if( b_delete_items )
359         {
360             /* Delete the item here */
361             playlist_Delete( p_playlist, p_root->pp_children[i]->input.i_id );
362         }
363     }
364     return VLC_SUCCESS;
365 }
366
367 /**
368  * Remove all the children of a node and removes the node
369  *
370  * \param p_playlist the playlist
371  * \param p_root the node
372  * \param b_delete_items do we have to delete the children items ?
373  * \return VLC_SUCCESS or an error
374  */
375 int playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root,
376                          vlc_bool_t b_delete_items, vlc_bool_t b_force )
377 {
378     int i, i_top, i_bottom;
379     if( p_root->i_children == -1 )
380     {
381         return VLC_EGENERIC;
382     }
383
384     /* Delete the children */
385     for( i =  p_root->i_children - 1 ; i >= 0; i-- )
386     {
387         if( p_root->pp_children[i]->i_children > -1 )
388         {
389             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
390                                 b_delete_items , b_force );
391         }
392         else if( b_delete_items )
393         {
394             /* Delete the item here */
395             playlist_Delete( p_playlist, p_root->pp_children[i]->input.i_id );
396         }
397     }
398     /* Delete the node */
399     if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
400     {
401     }
402     else
403     {
404         for( i = 0 ; i< p_root->i_parents; i++ )
405         {
406             playlist_NodeRemoveItem( p_playlist, p_root,
407                                      p_root->pp_parents[i]->p_parent );
408         }
409         var_SetInteger( p_playlist, "item-deleted", p_root->input.i_id );
410
411         i_bottom = 0; i_top = p_playlist->i_all_size - 1;
412         i = i_top / 2;
413         while( p_playlist->pp_all_items[i]->input.i_id != p_root->input.i_id &&
414                i_top > i_bottom )
415         {
416             if( p_playlist->pp_all_items[i]->input.i_id < p_root->input.i_id )
417             {
418                 i_bottom = i + 1;
419             }
420             else
421             {
422                 i_top = i - 1;
423             }
424             i = i_bottom + ( i_top - i_bottom ) / 2;
425         }
426         if( p_playlist->pp_all_items[i]->input.i_id == p_root->input.i_id )
427         {
428             REMOVE_ELEM( p_playlist->pp_all_items, p_playlist->i_all_size, i );
429         }
430         playlist_ItemDelete( p_root );
431     }
432     return VLC_SUCCESS;
433 }
434
435
436 /**
437  * Adds an item to the childs of a node
438  *
439  * \param p_playlist the playlist
440  * \param i_view the view of the node ( needed for parent search )
441  * \param p_item the item to append
442  * \param p_parent the parent node
443  * \return VLC_SUCCESS or an error
444  */
445 int playlist_NodeAppend( playlist_t *p_playlist,
446                          int i_view,
447                          playlist_item_t *p_item,
448                          playlist_item_t *p_parent )
449 {
450     return playlist_NodeInsert( p_playlist, i_view, p_item, p_parent, -1 );
451 }
452
453 int playlist_NodeInsert( playlist_t *p_playlist,
454                          int i_view,
455                          playlist_item_t *p_item,
456                          playlist_item_t *p_parent,
457                          int i_position )
458 {
459    int i;
460    vlc_bool_t b_found = VLC_FALSE;
461    if( !p_parent || p_parent->i_children == -1 )
462    {
463         msg_Err( p_playlist, "invalid node" );
464         return VLC_EGENERIC;
465    }
466
467    if( i_position == -1 ) i_position = p_parent->i_children ;
468
469    INSERT_ELEM( p_parent->pp_children,
470                 p_parent->i_children,
471                 i_position,
472                 p_item );
473
474    /* Add the parent to the array */
475    for( i= 0; i< p_item->i_parents ; i++ )
476    {
477        if( p_item->pp_parents[i]->i_view == i_view )
478        {
479            b_found = VLC_TRUE;
480            break;
481        }
482    }
483    if( b_found == VLC_FALSE )
484    {
485         struct item_parent_t *p_ip = (struct item_parent_t *)
486                                      malloc(sizeof(struct item_parent_t) );
487         p_ip->i_view = i_view;
488         p_ip->p_parent = p_parent;
489
490         INSERT_ELEM( p_item->pp_parents,
491                      p_item->i_parents, p_item->i_parents,
492                      p_ip );
493    }
494
495    /* Let the interface know this has been updated */
496    p_parent->i_serial++;
497    return VLC_SUCCESS;
498 }
499
500 /**
501  * Deletes a parent from the parent list of a node
502  *
503  * \param p_playlist the playlist
504  * \param p_item the item to remove
505  * \param p_parent the parent node
506  * \return VLC_SUCCESS or an error
507  */
508 int playlist_NodeRemoveParent( playlist_t *p_playlist,
509                         playlist_item_t *p_item,
510                         playlist_item_t *p_parent )
511 {
512    int i;
513    if( !p_parent || p_parent->i_children == -1 )
514    {
515         msg_Err( p_playlist, "invalid node" );
516    }
517
518    for( i = 0; i < p_item->i_parents; i++ )
519    {
520        if( p_item->pp_parents[i]->p_parent == p_parent )
521        {
522            if( p_item->pp_parents[i] )
523            {
524                free( p_item->pp_parents[i] );
525            }
526            REMOVE_ELEM( p_item->pp_parents, p_item->i_parents, i );
527        }
528    }
529    p_item->i_serial++;
530    return VLC_SUCCESS;
531 }
532
533 /**
534  * Deletes an item from the children of a node
535  *
536  * \param p_playlist the playlist
537  * \param p_item the item to remove
538  * \param p_parent the parent node
539  * \return VLC_SUCCESS or an error
540  */
541 int playlist_NodeRemoveItem( playlist_t *p_playlist,
542                         playlist_item_t *p_item,
543                         playlist_item_t *p_parent )
544 {
545    int i;
546    for( i= 0; i< p_parent->i_children ; i++ )
547    {
548        if( p_parent->pp_children[i] == p_item )
549        {
550            REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
551        }
552    }
553
554    /* Let the interface know this has been updated */
555    p_parent->i_serial++;
556
557    return VLC_SUCCESS;
558 }
559
560
561 /**
562  * Count the children of a node
563  *
564  * \param p_playlist the playlist
565  * \param p_node the node
566  * \return the number of children
567  */
568 int playlist_NodeChildrenCount( playlist_t *p_playlist, playlist_item_t*p_node)
569 {
570     int i;
571     int i_nb = 0;
572     if( p_node->i_children == -1 )
573     {
574         return 0;
575     }
576
577     for( i=0 ; i< p_node->i_children;i++ )
578     {
579         if( p_node->pp_children[i]->i_children == -1 )
580         {
581             i_nb++;
582         }
583         else
584         {
585             i_nb += playlist_NodeChildrenCount( p_playlist, 
586                                                 p_node->pp_children[i] );
587         }
588     }
589     return i_nb;
590 }
591
592 /**
593  * Search a child of a node by its name
594  *
595  * \param p_node the node
596  * \param psz_search the name of the child to search
597  * \return the child item or NULL if not found or error
598  */
599 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
600                                            const char *psz_search )
601 {
602     int i;
603
604     if( p_node->i_children < 0 )
605     {
606          return NULL;
607     }
608     for( i = 0 ; i< p_node->i_children; i++ )
609     {
610         if( !strcmp( p_node->pp_children[i]->input.psz_name, psz_search ) )
611         {
612             return p_node->pp_children[i];
613         }
614     }
615     return NULL;
616 }
617
618
619 /**********************************************************************
620  * Tree functions
621  **********************************************************************/
622
623 /**
624  * Finds the next item to play
625  *
626  * \param p_playlist the playlist
627  * \param i_view the view
628  * \param p_root the root node
629  * \param p_node the node we are playing from
630  * \param p_item the item we were playing (NULL if none )
631  * \return the next item to play, or NULL if none found
632  */
633 playlist_item_t *playlist_FindNextFromParent( playlist_t *p_playlist,
634                                         int i_view, /* FIXME: useless */
635                                         playlist_item_t *p_root,
636                                         playlist_item_t *p_node,
637                                         playlist_item_t *p_item )
638 {
639     playlist_item_t *p_search, *p_next;
640
641 #ifdef PLAYLIST_DEBUG
642     if( p_item != NULL )
643     {
644         msg_Dbg( p_playlist, "finding next of %s within %s - root %s",
645                         p_item->input.psz_name, p_node->input.psz_name,
646                         p_root->input.psz_name );
647     }
648     else
649     {
650         msg_Dbg( p_playlist, "finding something to play within %s -root %s",
651                             p_node->input.psz_name, p_root->input.psz_name );
652
653     }
654 #endif
655
656     if( !p_node  || p_node->i_children == -1 )
657     {
658         msg_Err( p_playlist,"invalid arguments for FindNextFromParent" );
659         return NULL;
660     }
661
662     /* Find the parent node of the item */
663     if( p_item != NULL )
664     {
665         p_search = playlist_FindDirectParent( p_playlist, p_item, i_view );
666         if( p_search == NULL )
667         {
668             msg_Err( p_playlist, "parent node not found" );
669             return NULL;
670         }
671     }
672     else
673     {
674         p_search = p_node;
675     }
676
677     /* Now, go up the tree until we find a suitable next item */
678     p_next = playlist_RecursiveFindNext( p_playlist,i_view,
679                                          p_node, p_item, p_search );
680
681     /* Not found, do we go past p_node ? */
682     if( p_next == NULL )
683     {
684         if( p_playlist->b_go_next )
685         {
686 #ifdef PLAYLIST_DEBUG
687             msg_Dbg( p_playlist, "moving on to next node: search from %s",
688                             p_root->input.psz_name );
689 #endif
690             p_next = playlist_RecursiveFindNext( p_playlist, i_view,
691                                 p_root, p_item, p_search );
692             if( p_next == NULL )
693             {
694                 return NULL;
695             }
696             /* OK, we could continue, so set our current node to the root */
697             p_playlist->status.p_node = p_root;
698         }
699         else
700         {
701 #ifdef PLAYLIST_DEBUG
702             msg_Dbg( p_playlist, "not moving on to next node: you loose" );
703 #endif
704             return NULL;
705         }
706     }
707     return p_next;
708 }
709
710 /**
711  * Finds the previous item to play
712  *
713  * \param p_playlist the playlist
714  * \param i_view the view
715  * \param p_root the root node
716  * \param p_node the node we are playing from
717  * \param p_item the item we were playing (NULL if none )
718  * \return the next item to play, or NULL if none found
719  */
720 playlist_item_t *playlist_FindPrevFromParent( playlist_t *p_playlist,
721                                         int i_view,
722                                         playlist_item_t *p_root,
723                                         playlist_item_t *p_node,
724                                         playlist_item_t *p_item )
725 {
726     playlist_item_t *p_search, *p_next;
727
728 #ifdef PLAYLIST_DEBUG
729     if( p_item != NULL )
730     {
731         msg_Dbg( p_playlist, "finding prev of %s within %s",
732                         p_item->input.psz_name, p_node->input.psz_name );
733     }
734     else
735     {
736         msg_Dbg( p_playlist, "finding prev from %s",p_node->input.psz_name );
737     }
738 #endif
739
740     if( !p_node  || p_node->i_children == -1 )
741     {
742         msg_Err( p_playlist,"Invalid arguments for FindPrevFromParent" );
743         return NULL;
744     }
745
746     /* Find the parent node of the item */
747     if( p_item != NULL )
748     {
749         p_search = playlist_FindDirectParent( p_playlist, p_item, i_view );
750         if( p_search == NULL )
751         {
752             msg_Err( p_playlist, "parent node not found" );
753             return NULL;
754         }
755     }
756     else
757     {
758         p_search = p_node;
759     }
760
761     /* Now, go up the tree until we find a suitable next item */
762     p_next = playlist_RecursiveFindPrev( p_playlist,i_view,
763                                          p_node, p_item, p_search );
764
765     if( p_next == NULL )
766     {
767         if( p_playlist->b_go_next )
768         {
769             p_next = playlist_RecursiveFindPrev( p_playlist, i_view,
770                                 p_root, p_item, p_search );
771             if( p_next == NULL )
772             {
773                 return NULL;
774             }
775             /* OK, we could continue, so set our current node to the root */
776             p_playlist->status.p_node = p_root;
777         }
778         else
779         {
780             return NULL;
781         }
782     }
783     return p_next;
784 }
785
786 /************************************************************************
787  * Following functions are local
788  ***********************************************************************/
789
790
791 /* Recursively search the tree for next item */
792 playlist_item_t *playlist_RecursiveFindNext( playlist_t *p_playlist,
793                 int i_view,
794                 playlist_item_t *p_root,
795                 playlist_item_t *p_item,
796                 playlist_item_t *p_parent )
797 {
798     int i;
799     playlist_item_t *p_parent_parent;
800
801     for( i= 0 ; i < p_parent->i_children ; i++ )
802     {
803         if( p_parent->pp_children[i] == p_item || p_item == NULL )
804         {
805             if( p_item == NULL )
806             {
807                 i = -1;
808             }
809 #ifdef PLAYLIST_DEBUG
810             msg_Dbg( p_playlist,"current item found, child %i of %s",
811                                 i , p_parent->input.psz_name );
812 #endif
813             /* We found our item */
814             if( i+1 >= p_parent->i_children )
815             {
816                 /* Too far... */
817 #ifdef PLAYLIST_DEBUG
818                 msg_Dbg( p_playlist, "going up the tree, at parent of %s",
819                                 p_parent->input.psz_name );
820 #endif
821                 if( p_parent == p_root )
822                 {
823 #ifdef PLAYLIST_DEBUG
824                     msg_Dbg( p_playlist, "at root item (%s)",
825                                          p_root->input.psz_name );
826 #endif
827                     /* Hmm, seems it's the end for you, guy ! */
828                     return NULL;
829                 }
830
831                 /* Go up one level */
832                 p_parent_parent = playlist_FindDirectParent( p_playlist,
833                                                              p_parent, i_view );
834                 if( p_parent_parent == NULL )
835                 {
836                     msg_Warn( p_playlist, "unable to find parent!");
837                     return NULL;
838                 }
839                 return playlist_RecursiveFindNext( p_playlist, i_view,p_root,
840                                                    p_parent, p_parent_parent );
841             }
842             else
843             {
844                 if( p_parent->pp_children[i+1]->i_children == -1 )
845                 {
846                     /* Cool, we have found a real item to play */
847 #ifdef PLAYLIST_DEBUG
848                     msg_Dbg( p_playlist, "playing child %i of %s",
849                                      i+1 , p_parent->input.psz_name );
850 #endif
851                     return p_parent->pp_children[i+1];
852                 }
853                 else if( p_parent->pp_children[i+1]->i_children > 0 )
854                 {
855                     /* Select the first child of this node */
856 #ifdef PLAYLIST_DEBUG
857                     msg_Dbg( p_playlist, "%s is a node with children, "
858                                  "playing the first",
859                                   p_parent->pp_children[i+1]->input.psz_name);
860 #endif
861                     if( p_parent->pp_children[i+1]->pp_children[0]
862                                     ->i_children >= 0 )
863                     {
864                         /* first child is a node ! */
865                         return playlist_RecursiveFindNext( p_playlist, i_view,
866                                    p_root, NULL ,
867                                    p_parent->pp_children[i+1]->pp_children[0]);
868                     }
869                     return p_parent->pp_children[i+1]->pp_children[0];
870                 }
871                 else
872                 {
873                     /* This node has no child... We must continue */
874 #ifdef PLAYLIST_DEBUG
875                     msg_Dbg( p_playlist, "%s is a node with no children",
876                                  p_parent->pp_children[i+1]->input.psz_name);
877 #endif
878                     p_item = p_parent->pp_children[i+1];
879                 }
880             }
881         }
882     }
883     /* Just in case :) */
884     return NULL;
885 }
886
887 /* Recursively search the tree for previous item */
888 playlist_item_t *playlist_RecursiveFindPrev( playlist_t *p_playlist,
889                 int i_view,
890                 playlist_item_t *p_root,
891                 playlist_item_t *p_item,
892                 playlist_item_t *p_parent )
893 {
894     int i;
895     playlist_item_t *p_parent_parent;
896
897     for( i= p_parent->i_children - 1 ; i >= 0 ; i-- )
898     {
899         if( p_parent->pp_children[i] == p_item || p_item == NULL )
900         {
901             if( p_item == NULL )
902             {
903                 i = -1;
904             }
905 #ifdef PLAYLIST_DEBUG
906             msg_Dbg( p_playlist,"current item found, child %i of %s",
907                              i , p_parent->input.psz_name );
908 #endif
909             /* We found our item */
910             if( i < 1 )
911             {
912                 /* Too far... */
913 #ifdef PLAYLIST_DEBUG
914                 msg_Dbg( p_playlist, "going up the tree, at parent of %s",
915                                      p_parent->input.psz_name );
916 #endif
917                 if( p_parent == p_root )
918                 {
919 #ifdef PLAYLIST_DEBUG
920                     msg_Dbg( p_playlist, "at root item (%s)",
921                                          p_root->input.psz_name );
922 #endif
923                     /* Hmm, seems it's the end for you, guy ! */
924                     return NULL;
925                 }
926                 /* Go up one level */
927                 p_parent_parent = playlist_FindDirectParent( p_playlist,
928                                             p_parent, i_view );
929                 if( p_parent_parent == NULL )
930                 {
931 #ifdef PLAYLIST_DEBUG
932                     msg_Dbg( p_playlist, "mmmh, couldn't find parent" );
933 #endif
934                     return NULL;
935                 }
936                 return playlist_RecursiveFindPrev( p_playlist, i_view,p_root,
937                                             p_parent, p_parent_parent );
938             }
939             else
940             {
941                 if( p_parent->pp_children[i-1]->i_children == -1 )
942                 {
943                     /* Cool, we have found a real item to play */
944 #ifdef PLAYLIST_DEBUG
945                     msg_Dbg( p_playlist, "playing child %i of %s",
946                                      i-1, p_parent->input.psz_name );
947 #endif
948                     return p_parent->pp_children[i-1];
949                 }
950                 else if( p_parent->pp_children[i-1]->i_children > 0 )
951                 {
952                     /* Select the last child of this node */
953 #ifdef PLAYLIST_DEBUG
954                     msg_Dbg( p_playlist, "%s is a node with children,"
955                                    " playing the last",
956                                    p_parent->pp_children[i-1]->input.psz_name);
957 #endif
958                     if( p_parent->pp_children[i-1]->pp_children[p_parent->
959                             pp_children[i-1]->i_children-1]->i_children >= 0 )
960                     {
961                         /* Last child is a node */
962                         return playlist_RecursiveFindPrev( p_playlist, i_view,
963                                     p_root,NULL,
964                                     p_parent->pp_children[i-1]->pp_children[
965                                     p_parent->pp_children[i-1]->i_children-1]);
966                     }
967                     return p_parent->pp_children[i-1]->pp_children[
968                                  p_parent->pp_children[i-1]->i_children-1];
969                 }
970                 else
971                 {
972                     /* This node has no child... We must continue */
973 #ifdef PLAYLIST_DEBUG
974                     msg_Dbg( p_playlist, "%s is a node with no children",
975                                 p_parent->pp_children[i-1]->input.psz_name);
976 #endif
977                     p_item = p_parent->pp_children[i-1];
978                 }
979             }
980         }
981     }
982     return NULL;
983 }
984
985 /* This function returns the parent of an item in a view */
986 playlist_item_t *playlist_FindDirectParent( playlist_t *p_playlist,
987                                          playlist_item_t *p_item,
988                                          int i_view )
989 {
990         int i = 0;
991         for( i= 0; i< p_item->i_parents ; i++ )
992         {
993             if( p_item->pp_parents[i]->i_view == i_view )
994             {
995                 return p_item->pp_parents[i]->p_parent;
996             }
997         }
998         return NULL;
999 }
1000
1001
1002 #ifdef PLAYLIST_DEBUG
1003 /* This function dumps a node : to be used only for debug*/
1004 void playlist_NodeDump( playlist_t *p_playlist, playlist_item_t *p_item,
1005                         int i_level )
1006 {
1007     char str[512];
1008     int i;
1009
1010     if( i_level == 1 )
1011     {
1012         msg_Dbg( p_playlist, "%s (%i)",
1013                         p_item->input.psz_name, p_item->i_children );
1014     }
1015
1016     if( p_item->i_children == -1 )
1017     {
1018         return;
1019     }
1020
1021     for( i = 0; i< p_item->i_children; i++ )
1022     {
1023         memset( str, 32, 512 );
1024         sprintf( str + 2 * i_level , "%s (%i)",
1025                                 p_item->pp_children[i]->input.psz_name,
1026                                 p_item->pp_children[i]->i_children );
1027         msg_Dbg( p_playlist, "%s",str );
1028         if( p_item->pp_children[i]->i_children >= 0 )
1029         {
1030             playlist_NodeDump( p_playlist, p_item->pp_children[i],
1031                               i_level + 1 );
1032         }
1033     }
1034     return;
1035 }
1036 #endif