I have been debating someone recently about whether physical keyboards are faster than touchscreen keyboards. I have a lot of CS knowledge, but not a lot of Android knowledge. Therefore, during this debate, I have been reading up on how the Android system processes touchscreen events into keyboard events. At this point, my understanding is this:
- With a physical keyboard, the keyboard hardware itself can send a scancode that can be translated to an actual keycode at the kernal level through a simple lookup.
- With a touchscreen, the hardware device is sending an X/Y position (along with some other data, but not a scancode), which then needs to usually be translated into a scancode by a previously exported virtual key map file. Then that scancode can be translated as expected.
This translation can happen either at the driver level or the software level. I cannot find any source code for driver level, but I found this Java file which seems to do the translation at the software level. However, its implementation is absolutely not what I would expect. It seems as though the virtual key map file is loaded into memory as an ArrayList, where the VirtualKey is a simple static class with some helper methods. Essentially, the VirtualKey class has the bounding box and can determine if a given X/Y point would fall into that bounding box. When the system is checking a virtual key (findVirtualKey, line 786), it simply iterates through the list and uses a helper method to linearly search for the relevant key (it doesn't even bother to precompute the math on the bounding box, allowing it to happen each time).
Am I looking at the wrong place to understand the algorithm used in my phone's virtual key translation? I genuinely expected some kind of spatial data structure like a QuadTree. Is the dumb linear search on an arraylist more effective in practice despite the presumably terrible Big Oh? Have people tested the runtimes? Does anyone know where I can read more about this?