Netflix on Android

Like many Android users I’m dismayed at the lack of a Netflix application. I loathe that I have to go grab my iPod when I want Netflix on the go. Apparently there’s a good reason for this, however, as a naive mid-level Android developer I’m at a loss trying to understand what that reason is. In a recent blog entry, Greg Peters from Netflix said,

“The hurdle has been the lack of a generic and complete platform security and content protection mechanism available for Android. The same security issues that have led to piracy concerns on the Android platform have made it difficult for us to secure a common Digital Rights Management (DRM) system on these devices.”

What does copy protection have to do with a streaming app? You authenticate the user and then stream. Nothing is every written to disk (except maybe a buffer) so there’s nothing to copy. The stream itself must be protected, so the point of comprise would need to be the memory space in the app itself, where the unencrypted stream is present. In Android, you’d need to have a rooted phone and a native library or app to access this. Sure, it’s relatively easy to root Android phones, but it’s easy to root an iPhone as well.

Also, what piracy concerns? It used to be the case that apps were pirated left and right, but that’s not true anymore. Android did away with its copy protection scheme and now uses a license management service which is built right into the Android SDK. Regardless, what do pirated apps have to do with digital content protection?

Content holders in general would do well to understand the purpose of DRM in 2010. It’s purpose should NOT be to prevent people from copying copy protected digital media. Why not? Because that’s impossible. The world contains an infinite supply of bored 15 year olds with nothing but time on their hands. They will beat whatever scheme you put in place. You can waste innumerable costly hours of  highly paid staff software developers coming up with a new methodology to have it broken in hours.

So what should be the purpose of DRM? To make stealing content annoying. To make it, for 99.9% of the schlubs out there, easier and more cost effective to pay for the content than it is to steal it … and write off your losses for that 0.1% of people that have way more time than money and will find a way to beat the DRM regardless.

Content holders should understand that any content (music, movies, bookes) is a bitorrent download away, and one need not be highly technical to grab it. Go to a site. Search. Click. Wait 10 minutes. That’s it. Make it easier and more cost effective than that to purchase content. If you don’t, people will steal it.

Coming back to Netflix and Android … a Netflix app doesn’t need to provide uber-safe device dependent hardware-level DRM. If it simply avoids writing the video file to a persistent store that would be enough.

Netflix tells us we can expect an app in 2011,

But I’m happy to announce we’ll launch select Android devices that will instantly stream from Netflix early next year.

That means we’ll see a Netflix app for the premiere devices / carriers – like whatever the latest Motorla Droid will be at the time. I don’t hold much hope for my poor Nexus One, relegated to a second class carrier like T-Mobile.

Iterative Tree Traversal

While studying for an interview, I some how got it into my head that I should understand the iterative algorithms for the three standard tree traversal methods (pre-, post-, in-). While the recursive algorithms for these are straightforward and intuitive, the iterative ones are most certainly not. Worse, googling on this topic turned up a lot of incomplete or just plain wrong solutions.

With some painstaking work I believe I came up with some nearly as simple as possible solutions. Some solutions I found required parent pointers, some required visit markers. These require neither of these.

After each algorithm, I include a walkthrough of the algorithm based on this sample tree from the Wikipedia tree traversal page.

Pre-order,

void preOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		n = s.pop();
		n.visit();

		if (n.right != null) {
			s.push(n.right);
		}
		if (n.left != null) {
			s.push(n.left);
		}
	}
}

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={}, visited={F}, s={B,G}
2: s={G}, visited={F,B}, s={A,D,G}
3: s={D,G}, visited={F,B,A}, s={D,G}
4: s={G}, visited={F,B,A,D}, s={C,E,G}
5: s={E,G}, visited={F,B,A,D,C}, s={E,G}
6: s={G}, visited={F,B,A,D,C,E}, s={G}
7: s={}, visited={F,B,A,D,C,E,G}, s={I}
8: s={}, visited={F,B,A,D,C,E,G,I}, s={H}
9: s={}, visited={F,B,A,D,C,E,G,I,H}, s={}

Post-order,

This one uses two stacks. It consumes the input stack and builds the output stack. At the end of the method, it pops each node from the output stack and visits it.

void postOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	Stack<Node> o = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		n = s.pop();
		o.push(n);

		if (n.left != null) {
			s.push(n.left);
		if (n.right != null) {
			s.push(n.right);
		}
	}
	while (!o.empty()) {
		o.pop().visit();
	}
}

Each line of the example below shows state of the input stack and output stack after the iteration.

1: out={F}, in={G,B}
2: out={G,F}, in={I,B}
3: out={I,G,F}, in={H,B}
4: out={H,I,G,F}, in={B}
5: out={B,H,I,G,F}, in={D,A}
6: out={D,B,H,I,G,F}, in={E,C,A}
7: out={E,D,B,H,I,G,F}, in={C,A}
8: out={C,E,D,B,H,I,G,F}, in={A}
9: out={A,C,E,D,B,H,I,G,F}, in={}

In-order,

void inOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		while (n.left != null) {
			n = n.left;
			s.push(n);
		}
		n = s.pop();
		n.visit();
		if (n.right != null) {
			s.push(n.right);
		}
	}
}

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={A,B,F}, v={A}, s={B,F}
2: s={B,F}, v={A,B}, s={D,F}
3: s={C,D,F}, v={A,B,C}, s={D,F}
4: s={D,F}, v={A,B,C,D}, s={E,F}
5: s={E,F}, v={A,B,C,D,E}, s={F}
6: s={F}, v={A,B,C,D,E,F}, s={G}
7: s={G}, v={A,B,C,D,E,F,G}, s={I}
8: s={H,I}, v={A,B,C,D,E,F,G,H}, s={I}
9: s={I}, v={A,B,C,D,E,F,G,H,I}, s={}