Sliding window (shift) for an array

Question

I've got a low-level keyboard hook which currently allows me to control a media player from inside any application, including games.

It works by looking at the specific keystroke captured.

I'd like to extend it to look for combinations of keys. I can hardcode some logic but I feel there must be a more logical way.

Really, I'm looking for something like a shift register...

eg as I type "BlahPlay", I'd like a structure which can be used like this...

[_,_,_,_]
[_,_,_,B]
[_,_,B,l]
[_,B,l,a]
[B,l,a,h]
[l,a,h,P]
[a,h,P,l]
[h,P,l,a]
[P,l,a,y] <-- detect "Play"

Short of looping and shifting the items in an array, what's the correct way to do this?

The best I can think of right now is ...

Private Register(4) As Char
Private Position = 0 

Sub Add(Character as Char)
    Register(Position) = Character
    Position = (Position + 1) Mod Register.Length
End Sub

Function Get() as String
    Dim Ret As New StringBuilder
    For i = Position To Position + Register.Length
        Ret.Append(Register(i Mod Register.Length)
    Next
    Return Ret.ToString
End Function

Sounds like a [Queue](http://msdn.microsoft.com/en-us/library/7977ey2c.aspx) might work here. — keyboardP, Aug 04 '13 at 17:22
@keyboardP Maybe if there's an unconventional way to use it? But I need to be able to query the state of the register as a whole, ideally without dequeueing/requeueing every time. I also want a maximum size so that new values force out old ones. I'll improve my example — Basic, Aug 04 '13 at 17:24
Maybe this [circular buffer](http://stackoverflow.com/questions/1213317/maximum-capacity-collection-in-c-sharp) might be helpful. — keyboardP, Aug 04 '13 at 17:41
How about an integer. No really: you could let every byte in the integer be an ascii character / keycode. Shifting/adding in a new char is trivial, just `state * 256 + Character` (that's equivalent to shifting left by 8 and orring the new char in). Comparing all four characters with, say, `{P, l, a, y}` is trivial, just compare the integer with a known integer constant (0x506C6179 in the case of Play). — harold, Aug 04 '13 at 17:54
@harold That's an interesting approach but it shows some promise... I took a 4-char command as an example but off the top of my head, I can't imagine a scenario requiring more than 8 so it may well be a viable option. I'll leave this open in case of a better solution but thanks for the idea, I wouldn't have considerd it myself — Basic, Aug 04 '13 at 18:13

p.s.w.g · Answer 1 · 2013-08-04T17:43:16.243

Instead of shifting the items in the buffer, you could create standard array and just inserting each item in the next position, looping around as necessary. Consider the following code:

var buffSize = 4;
var position = 0;
var buffer = new char[buffSize];

Now you simply insert every new character at position and set position = (position + 1) % buffSize every time a new key is entered. Suppose you typed abcPlay, the buffer would be:

[_,_,_,_] position = 0
[a,_,_,_] position = 1
[a,b,_,_] position = 2
[a,b,c,_] position = 3
[a,b,c,P] position = 0
[l,b,c,P] position = 1
[l,a,c,P] position = 2
[l,a,y,P] position = 3

This means that instead of simply reading each char out from the begin reading at position. For example, if you're testing to see if the buffer contains Play, you'd have to do something like this:

var test = new char[] { 'P', 'l', 'a', 'y' };
int p = (position + buffSize - test.Length) % buffSize;
bool success = true;
for(int i = 0; i < test.Length; i++)
{
    if (buffer[p] != test[i])
    {
        success = false;
        break;
    }

    p = (p + 1) % buffSize;
}

Edit You edited your question since I began writing this answer. It appears that you've already developed a solution pretty close to this. I'd still recommend going with something like this. It will be more efficient than shifting each item in the array on every insert.

Yeah, sorry for that - I thought I should add more detail after the first comment - but it's gratifying to see that I'm not the only one thinking of that approach. I have to admit I'm surprised that there isn't a more "standard" way to do this - after all, shift registers are pretty fundamental to µProcessors... If I don't find a better solution, I'll accept. Thanks for taking the time to respond — Basic, Aug 04 '13 at 18:08

Sliding window (shift) for an array

1 Answers1