Implementing a sliding window (java)

Question

I am fairly new to java (and programming overall) and have received the task to implement a Sliding Window object from start to finish. The skeleton code is as follows:

import java.util.Scanner;

//implement class SlidingWindow

class Main {

// this is the test code for the judge, do not modify
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int windowSize = scanner.nextInt();
    SlidingWindow window = new SlidingWindow(windowSize);
    while (scanner.hasNextInt())
    {
        int value = scanner.nextInt();
        window.Put(value);
        System.out.println("[" + window.Min() + " " + window.Max() + "]");
    }
    scanner.close();
}

What needs to be done (and the ideas I have had so far towards solving it)

Create a sliding window w that can be instantiated with a window size n:

SlidingWindow w = New SlidingWindow(n) //This is what stumps me the most - is it a self-growing array? A linked list?
An input method Put that accepts integer numbers and has no return value:

public static void Put(int value){ // implementation will depend on SlidingWindow
A Max and Min method to return the min and max of the most recent inputs. This I will just do by looking for the min and max.
If the number of inputs exceeds the size of the window, the oldest element should be discarded.

Sorry for the vagueness of the question - we never dealt with windows in class (I am a few weeks in to learning anything about coding) so I am truly stumped. I have looked around online for some resources but have not yet found anything suitable to help me.

If you have any ideas or advice to offer on how to create SlidingWindow w, I think that will get me on the right track!

Thanks in advance!

A starting point for this problem is the good old "pen & paper" method: visualize the stream of inputs (integers) and draw a fixed window around them. Then think about how the window starts sliding when you accumulate enough inputs. — Mick Mnemonic, Apr 10 '15 at 14:57
Done that, but am I right in thinking a window is implemented as a FIFO list? I feel utterly clueless! — Nina Hain, Apr 10 '15 at 14:58
Yes, a fixed-size FIFO queue could be used as the window. However, there [is no implementation for this in the Java API](http://stackoverflow.com/questions/5498865/size-limited-queue-that-holds-last-n-elements-in-java), so you would need to either write the FIFO yourself or use an utility library such as Apache Commons or Guava. — Mick Mnemonic, Apr 10 '15 at 15:27

score 9 · Answer 1 · 2015-04-10T16:05:33.487

9

For the sliding window, the simplest would possibly be a counter for the number of the insertion. Like this:

class Window{
    int ct = 0;
    int[] storage; 

    public Window(int size){
         storage = new int[size];
    }

    public void put(int i){
         storage[ct % storage.length] = i;
         ct++;
    }
}

This way, you can use a fixed size array and replace the oldest value by newer ones as soon as the array is filled, without shifting content.

edited Apr 10 '15 at 16:05

answered Apr 10 '15 at 14:57

Thanks for the response. A few questions about whether or not I am understanding this correctly: You create in int "ct" to count the number of insertions you make. Then create an array "storage" of a certain size. Could you explain your method put? I'm not sure I grasp the concept. – Nina Hain Apr 10 '15 at 15:10
1

the counter counts how many insertions you have made. storage holds all values that are currently in the window. the insertions would work this way: `counter % storage.length` counts from 0 to `storage.length` and starts again from 0. – Apr 10 '15 at 15:18
1

basically this is equivalent to using `storage[ct] = i;` and adding `if(ct == storage.length)ct = 0;` at the end – Apr 10 '15 at 15:29
Thanks for the clarification. I'm still stuck on the first part of the implementation of w though - I need to declare an array window of size windowSize. Any tips on how to go about this? I'm brutally new to java so thanks for putting up with stupid questions! – Nina Hain Apr 10 '15 at 16:02
the array creation is pretty simple, i'll edit the post to show it – Apr 10 '15 at 16:04
That helped a ton! Great explanation, I will get on the Max and Min implementation but that should work just fine. Thanks again! – Nina Hain Apr 10 '15 at 16:12
I just realized I have one more question concerning inserting values into the array via put - I need a for loop to read in the values and insert them in the array, right? – Nina Hain Apr 10 '15 at 16:24
nope, the codesnippets i wrote should work with your mainmethod (apart from some naming issues - like your `Put` is uppercase - and the missing `min()` and `max()` methods. And you might think about how you want to quit the whole thing at some point. – Apr 10 '15 at 16:29

score 0 · Answer 2 · edited Feb 17 '16 at 16:18

I am hereby providing an easy and relatively simple solution. I am giving code of two java files.

The Class:

    public class Window {           
        public void getValue(int[] a, int w){   
            int t = 0;      
            for(int i=0;i<a.length;i++){
                if(i==a.length-w+1){
                    break;
                }else{
                    for(int j=i;j<i+w;j++){
                        if(t<a[j]){
                            t = a[j];
                        }
                    }
                }           
                System.out.println(t);
                t = 0;
            }
        }   
    }

The Main method:

    public class MainMethod {       
        public static void main(String[] args) {
            int[] a = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
            int w = 3;
            Window ob = new Window();
            ob.getValue(a, w);
        }
    }


    Answer: 3 3 5 5 6 7

I only left checking of the length of the window should not be greater than the array.

Implementing a sliding window (java)

2 Answers2