Hi On Tue, Nov 21, 2006 at 10:35:57PM +0100, Michael Niedermayer wrote: [...]
It is always possible via linear search. If the demuxer SHOULD NOT search for them then we should not go out of our way to make it easy to search... Just my 2ยข...
well there really are 2 cases IMHO A. midstream info packets are not allowed in normal nut files B. midstream info packets are allowed in normal nut files
for A i agree that the pointers and repeating shouldnt be required, there may be other reasons though why repeating the info makes sense ...
for B i dont agree, simply because if info is there, then there are cases where the user will want to have that info, think of some capture of odeds radio stream, its not unlikely to think that the user would want to seek to a specific song (she knows the song title but not the time to seek to)
Arrg, this is what I was saying way back about info streams and I got flamed to death. Anyway such file has no index already, so it's not meant to be searchable by index, and searching by chapter _name_ does not work with binary search so linear search is the natural requirement anyway.
it is possible to extend info packets so that O(log n) search for names can be done ill explain how (and no iam not saying i actually propose doing that, its just a random thought) 1. add a hash table to every info packet which contains pointers to info packets for all names in the X previous info packets 2. X is the largst power of 2 which divides n which is the number of the current info packet, (n=5 -> X=1, n=6 -> X=2, n=8 -> X=8) 3. add a pointer to the Xth previous info packet
another idea, if we choose Y=sqrt( number of info packets ) and then duplicate the last Y info packets in every Yth info packet and give the small info packets a pointer to the last and the large ones a pointer to the last large one, then it should look like: 1 2 3 1234 5 6 7 5678 9 A B 9ABC D E and needs O(n) space (actually exactly 2*n) and O(sqrt(n)) seeks for finding a info packet the same can be done with the xth root, O(n^(1/x)) time and x*n overhead [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB In the past you could go to a library and read, borrow or copy any book Today you'd get arrested for mere telling someone where the library is