0

I'm trying to understand one java code, here is the code

 package RestClient; import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.io.PrintStream; import java.io.BufferedWriter; import java.io.Writer; import java.io.OutputStreamWriter; import java.util.InputMismatchException; import java.io.IOException; import java.io.InputStream; public class Test { public static void main(String[] args) { InputStream inputStream = System.in; System.out.println("Its done"); OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); OutputWriter out = new OutputWriter(outputStream); TaskE solver = new TaskE(); solver.solve(1, in, out); out.close(); } static class TaskE { static long[] dp; static long[] sum; static int n; static SegmentTreeRMQ tree; public void solve(int testNumber, InputReader in, OutputWriter out) { System.out.println("2"); n = in.nextInt(); System.out.println("It always come Here"); int c = in.nextInt(); if (c == 1) { out.println(0); return; } int[] a = in.nextIntArray(n); dp = new long[n]; sum = new long[n + 1]; for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + a[i - 1]; } tree = new SegmentTreeRMQ(); tree.constructST(a, n); out.println(comp(a, 0, n - 1, c)); } private long comp(int[] a, int l, int r, int c) { //System.out.println(l+" "+r); if (r < l) return 0; if (r == l && c == 1) return 0; else if (r == l) return a[l]; if (dp[l] != 0) return dp[l]; int min = a[l]; long val = sum[r + 1] - sum[l]; val = Math.min(val, (a[l] + comp(a, l + 1, r, c))); if (l + c <= n) val = Math.min(val, sum[l + c] - sum[l] - tree.RMQ(n, l, l + c - 1) + comp(a, l + c, r, c)); //System.out.println("val:"+l+" "+val); dp[l] = val; return val; } } static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; private InputReader.SpaceCharFilter filter; public InputReader(InputStream stream) { System.out.println("1"); this.stream = stream; } public int read() { System.out.println("Its4"); System.out.println("numChars Near 4: " +numChars); System.out.println("curChar Near 4: " +curChar); if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { System.out.println("5"); numChars = stream.read(buf); System.out.println("numChars: "+numChars); System.out.println("Print: "+new String(new byte[]{ (buf[curChar]) }, "US-ASCII")); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) { return -1; } } System.out.println("curChar++: "+curChar); return buf[curChar++]; } public int nextInt() { System.out.println("3"); int c = read(); System.out.println("c: "+c); while (isSpaceChar(c)) { System.out.println("6"); c = read(); } int sgn = 1; System.out.println("7"); if (c == '-') { System.out.println("8"); sgn = -1; c = read(); } int res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } System.out.println("9"); res = res*10; res = res+c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { if (filter != null) { System.out.println("here"); return filter.isSpaceChar(c); } return isWhitespace(c); } public static boolean isWhitespace(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; ++i) array[i] = nextInt(); return array; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } static class SegmentTreeRMQ { int[] st; int minVal(int x, int y) { return (x < y) ? x : y; } int getMid(int s, int e) { return s + (e - s) / 2; } int RMQUtil(int ss, int se, int qs, int qe, int index) { // If segment of this node is a part of given range, then // return the min of the segment if (qs <= ss && qe >= se) return st[index]; // If segment of this node is outside the given range if (se < qs || ss > qe) return Integer.MAX_VALUE; // If a part of this segment overlaps with the given range int mid = getMid(ss, se); return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1), RMQUtil(mid + 1, se, qs, qe, 2 * index + 2)); } int RMQ(int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { System.out.println("Invalid Input"); return -1; } return RMQUtil(0, n - 1, qs, qe, 0); } int constructSTUtil(int arr[], int ss, int se, int si) { // If there is one element in array, store it in current // node of segment tree and return if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // If there are more than one elements, then recur for left and // right subtrees and store the minimum of two values in this node int mid = getMid(ss, se); st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1), constructSTUtil(arr, mid + 1, se, si * 2 + 2)); return st[si]; } void constructST(int arr[], int n) { // Allocate memory for segment tree //Height of segment tree int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); //Maximum size of segment tree int max_size = 2 * (int) Math.pow(2, x) - 1; st = new int[max_size]; // allocate memory // Fill the allocated memory st constructSTUtil(arr, 0, n - 1, 0); } } static class OutputWriter { private final PrintWriter writer; public OutputWriter(OutputStream outputStream) { writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); } public OutputWriter(Writer writer) { this.writer = new PrintWriter(writer); } public void close() { writer.close(); } public void println(long i) { writer.println(i); } public void println(int i) { writer.println(i); } } }

Doubts:

1) InputReader is inner class of Test class, where SpaceCharFilter interface is created with one method declared. I have seen only where interface can be used by using implementation on class eg class implements Interface { implements methods}, but in this case it is setup with class's variable filter. May I know please how this functionality works in Java ?

2) In isSpaceChar(int c) method what is the significance of filter variable ? What type of values can come in filter variable ?

3) I'm running code with this input "10 2" then enter. Ideally it should go to filter!=null condition in isSpaceChar method while reading second character from input "0" from "10 2", but its not going, may I know please why ?

Can anyone help me to clear these doubts ?

Improve this question
5
  • Does this code even work? I don't see any Implementation of of SpaceCharFilter, and the filter variable is never set. Commented Mar 7, 2018 at 9:10
  • @kutschkem, yes...! Commented Mar 7, 2018 at 9:10
  • Ah I see, it works because of point 3) - the filter variable is never set so is always == null. Commented Mar 7, 2018 at 9:12
  • @kutschkem, So what's the purpose of writing filter!=null ? Commented Mar 7, 2018 at 9:14
  • 1
    someone overengineering their code, to allow some other filter if InputReader is used somewhere else where only tabs need to be filtered for example. But there is no way to set the filter, so... don't worry too much about it, it's useless code. Commented Mar 7, 2018 at 9:17

1 Answer 1

Reset to default
2

  1. this is what polymorhism is about: we define an interface and call the method(s) defined in it not caring about what the actual implementation is (but expecting the implementation matching the interfaces contract which is defined by the name of the interface, the names of the methods defined in it and any comments it may have).

  2. it can hold an object that implements SpaceCharFilter.

  3. This is because the variable filter never gets an object assigned. Thus both, the interface and the variable are useless in this code.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

"it can hold an object that implements SpaceCharFilter" but no class implemented SpaceCharFilter interface but what about the filter variable in InputReader class ? How it is getting associated with interface SpaceCharFilter ?
@Squeez that variable can hold an object which implements SpaceCharFilter
@Squeez "How it is getting associated with interface SpaceCharFilter ?" The variable filter is defined to be of type SpaceCharFilter there is no association beyond that...
@kutschkem but who is implementing SpaceCharFilter interface ? I guess no one ..! Is that possible we could write write like this InputReader.SpaceCharFilter filer ?
@Squeez " who is implementing SpaceCharFilter interface ? I guess no one ..! Is that possible we could write write like this InputReader.SpaceCharFilter filer ?" obviously yes. The createor of an interface does not (want to) know how many implementations there will be (in future).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.