RollingMaximum - using "descending maxima" algorithm [OK] [1025078]

< > BotCompany Repo | #1025078 // RollingMaximum - using "descending maxima" algorithm [OK]

JavaX fragment (include) [tags: use-pretranspiled]

sclass RollingMaximum {
  int windowSize = 100, i;
  L<Entry> queue = new CircularArrayList; //linkedList();

  sclass Entry {
    int removeIndex;
    double value;
  
    *() {}
    *(int *removeIndex, double *value) {}
  }
  
  *() {}
  *(int *windowSize) {}
    
  double addAndGet(double val) {
    while (nempty(queue) && i >= first(queue).removeIndex)
      popFirst(queue);

    while (nempty(queue) && last(queue).value <= val)
      popLast(queue);

    queue.add(new Entry(i + windowSize, val));
    i++;
    ret first(queue).value;
  }
}

Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt

Snippet ID:

#1025078

Snippet name:

RollingMaximum - using "descending maxima" algorithm [OK]

Eternal ID of this version:

#1025078/9

Text MD5:

b3bea9e67bd5c18f267de7afab46db39

Transpilation MD5:

85be16b767ddb878118b4cd99b539f75

Author:

stefan

Category:

javax / maths

Type:

JavaX fragment (include)

Public (visible to everyone):

Yes

Archived (hidden from active list):

Created/modified:

2019-09-05 13:24:27

Source code size:

575 bytes / 27 lines

Pitched / IR pitched:

No / No

Views / Downloads:

274 / 738

Version history:

8 change(s)

Referenced in:

[show references]

1	sclass RollingMaximum {
2	int windowSize = 100, i;
3	L<Entry> queue = new CircularArrayList; //linkedList();
4
5	sclass Entry {
6	int removeIndex;
7	double value;
8
9	*() {}
10	(int removeIndex, double *value) {}
11	}
12
13	*() {}
14	(int windowSize) {}
15
16	double addAndGet(double val) {
17	while (nempty(queue) && i >= first(queue).removeIndex)
18	popFirst(queue);
19
20	while (nempty(queue) && last(queue).value <= val)
21	popLast(queue);
22
23	queue.add(new Entry(i + windowSize, val));
24	i++;
25	ret first(queue).value;
26	}
27	}