It also has at least the initial version of the scheduling. I've decided to rename this to "Best-Effort" scheduling.
Best-Effort Channel Scheduling
Using this rule you do not schedule a movie or show, you schedule one channel to be played at a certain time during another channel. This gives all sorts of flexibility since the scheduled channel can use rules of its own.
Why is it best-effort instead of just real "play this show exactly at this time" scheduling? Because that way would be really damn hard, if not impossible.
When you watch a normal broadcast channel, the length of everything from the shows to commercials to the black spots in between are all timed so that the final length of an episode of the Simpsons will be 30 minutes. I don't have that control. In PseudoTV I give most of the control to XBMC itself to play a playlist that is created. The best that I can do is insert an item into that playlist that should play (based on the length of each show before it) at about the time you want.
Of course just inserting a show blindly at about that time would result in really shitty timing. If a movie is normally playing between 6 and 8 and you've scheduled something for 7, what would I do? Either way the show will be an hour off. Ideally what I would do is to rearrange the shows so that something ends at exactly 7 so that the new show can be inserted. As I discovered, this is classic computer science problem called the subset sum problem. Can any of the values in this subset be added together to get to zero. This is effectively the problem that I faced.
First attempt
My first goal was to solve this problem. In this case, I could setup a range that was valid: anywhere between 120 seconds before or after the time slot was good enough. I hoped that this would make it easier. I also decided to confine my search to only combinations of up to 4 values. So I created an array that had the sum of all values added together:
{ [ index 1: 1021, index 2: 1426, total: 2447 ], [ index 1: 1021, index 3: 709, total: 1730 ], ... , [ index 499: 639, index 500: 3285, total: 3924 ] }
On top of that, I appended all combinations of 3 values, and then all combinations of 4 values. It would be only a matter of taking the time that I wanted and seeing if swapping the shows from before the time to after would get me to the value that I wanted.
This took quite a bit of memory. For only 10 shows I would have a total of 45 combinations of two, 120 combinations of three, and 330 combinations of four. This means that for only 10 shows I would have 495 array entries. Now, computers have a lot of memory. In reality, these 495 entries would probably take up about 6KB worth of memory, not a significant amount by any means. As the total number of entries increases, though, the total amount of memory grows extremely quickly. Going from 10 to 20 entries raises the memory requirements to 88KB, 30 entries takes up 431KB.
Even this isn't a huge amount. The problem is that, on occasion, the size of a playlist will get into the thousands. How much memory? I honestly have no idea. I pushed my test program up to 300 entries and before it crashes it was taking up over 1GB worth of memory. Obviously, this approach isn't feasible.
It's worth mentioning that, yes, it could be optimized. I could sort the entries by time and remove duplicates. Since I can't swap the same show more than once I could eliminate duplicate indexes. Even so, this trades memory usage for processor usage. While I don't mind taking up some time, a script inside of XBMC should not be killing your computer...other things need to take precedence, like playing video (for instance).
Second attempt (the best-effort method)
So I still need to schedule shows, but having a script solve the subset sum problem for thousands of elements probably won't work. What I really need is some crappy method that will work, even if it isn't ideal.
I went back to the ridiculous array I created. With some experimentation, I realized that since the number of elements in the subset (playlist) actually allowed for a reasonable switch of two items to get my time correct. Essentially, I found that a combination of 2 items worked great in most situations. Excellent, I can create the combinations of 2 array and just look for the closest match out of that.
This simple solution solved most of the problems. There were situations that still didn't work properly, though. To resolve this, I just put my function inside of a nice little loop:
for loops in range(5):
newtime = self.rearrangeShows(showindex, lasttime, channeldata, channelList)
if newtime == lasttime or newtime < 120:
break
lasttime = newtime
This gives the system 5 chances at fixing the time, by switching up to 5 pairs of shows. If the difference in the time between when I scheduled the show and when it will actually play is ever less than 120 seconds (plus or minus) then it will just say "good enough".
This method works pretty damn well, surprisingly. It isn't optimal. It does, though, minimize memory usage and attempts to get the optimal show placement out of as few processor cycles as possible.
Results
The outcome of this algorithm, though, is heavily dependent upon the channel contents itself. If you're scheduling a TV show on a channel that plays only movies, then it may be difficult for it to place the show very well. There would be fewer playlist entries and since the times for each entry is so high (2 hours or so, compared to 25 minutes of a TV show) then it may be difficult to place a show when you want it. Can I improve this algorithm? I'm sure it could be better. Will I? I'm not sure it's worth while, honestly. I think any results I get would only be incrementally better, and since the function is only a minor part of the PseudoTV package (and will probably rarely get used as it is) I don't think it's worth my time. Hopefully everyone will be happy with the current results, though.
If you do end up with large discrepancies between when you schedule a show and when it plays, please report it! While I probably won't change the algorithm much, I certainly will fix any bugs that show up.
