1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
package ch.epfl.xblast;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;
/**
* Run-length byte array encoder and decoder.
*
* @author Pacien TRAN-GIRARD (261948)
*/
public final class RunLengthEncoder {
private static final int REPLACE_THRESHOLD = 2;
private static final int MAX_RUN_LENGTH = -Byte.MIN_VALUE + REPLACE_THRESHOLD;
/**
* A run-length representing a sequence of a byte repeated n times.
*/
static class RunLength {
final int len;
final byte val;
/**
* Instantiates a run-length of byte val and length len.
*
* @param len the length
* @param val the value
*/
RunLength(int len, byte val) {
this.len = ArgumentChecker.requireNonNegative(len);
this.val = val;
}
/**
* Instantiates a unit length RunLength of the given value.
*
* @param val the value
*/
RunLength(byte val) {
this(1, val);
}
/**
* Instantiates a run-length from its byte encoded representation.
*
* @param len the encoded byte length
* @param val the value
*/
RunLength(byte len, byte val) {
this(-len + REPLACE_THRESHOLD, val);
}
/**
* Merges tho current and the given same value RunLengths.
*
* @param rl the other RunLength to combine.
* @return the summed-length RunLength
*/
RunLength merge(RunLength rl) {
if (Objects.isNull(rl) || rl.val != this.val)
throw new IllegalArgumentException();
return new RunLength(this.len + rl.len, this.val);
}
/**
* Splits the RunLength in one or more RunLengths, ensuring they do not exceed the maximum encode-able length.
*
* @return the split RunLength list
*/
List<RunLength> split() {
List<RunLength> fullRll = Collections.nCopies(this.len / MAX_RUN_LENGTH, new RunLength(MAX_RUN_LENGTH, this.val));
int remainder = this.len % MAX_RUN_LENGTH;
if (remainder == 0)
return fullRll;
else
return Lists.appended(fullRll, new RunLength(remainder, this.val));
}
/**
* Encodes a RunLength into its byte array representation.
*
* @return the byte array representation
*/
List<Byte> encode() {
if (this.len <= REPLACE_THRESHOLD)
return this.expand();
else
return Arrays.asList((byte) (-this.len + REPLACE_THRESHOLD), this.val);
}
/**
* Returns the expanded byte array form of a RunLength.
*
* @return the expanded byte array form
*/
List<Byte> expand() {
return Collections.nCopies(this.len, this.val);
}
@Override
public String toString() {
return String.format("(%d,%d)", this.len, this.val);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
RunLength rl = (RunLength) o;
return len == rl.len && val == rl.val;
}
}
/**
* Collapses contiguous same-value RunLength in the given list.
* Optimal collapse is not guaranteed if zero-length elements are not filtered out first.
*
* @param rll the RunLength list
* @return a collapsed RunLength list
*/
static List<RunLength> collapseRunLengths(List<RunLength> rll) {
if (Objects.isNull(rll) || rll.isEmpty())
return Collections.emptyList();
if (rll.size() == 1)
return rll;
RunLength current = rll.get(0), next = rll.get(1);
if (current.val == next.val)
return collapseRunLengths(Lists.prepended(Lists.firstDropped(rll, 2), current.merge(next)));
else
return Lists.prepended(collapseRunLengths(Lists.firstDropped(rll, 1)), current);
}
/**
* Decodes a RunLengths byte array representation into a RunLength list.
*
* @param el the encoded byte array
* @return the decoded RunLength lest
*/
static List<RunLength> decodeRunLengths(List<Byte> el) {
if (Objects.isNull(el) || el.isEmpty())
return Collections.emptyList();
if (el.get(0) < 0 && el.size() >= 2)
return Lists.prepended(
decodeRunLengths(Lists.firstDropped(el, 2)),
new RunLength(el.get(0), el.get(1)));
else if (el.get(0) >= 0)
return Lists.prepended(
decodeRunLengths(Lists.firstDropped(el, 1)),
new RunLength(el.get(0)));
else
throw new IllegalArgumentException();
}
/**
* Encodes the given Byte sequence using the run length encoding.
*
* @param bl the given byte sequence
* @return the encoded byte sequence
*/
public static List<Byte> encode(List<Byte> bl) {
List<RunLength> rll = bl.stream().map(RunLength::new).collect(Collectors.toList());
return Collections.unmodifiableList(collapseRunLengths(rll).stream()
.flatMap(rl -> rl.split().stream())
.flatMap(rl -> rl.encode().stream())
.collect(Collectors.toList()));
}
/**
* Decodes the given Byte sequence using the run length encoding.
*
* @param el the given encoded byte sequence
* @return the decoded byte sequence
*/
public static List<Byte> decode(List<Byte> el) {
return Collections.unmodifiableList(decodeRunLengths(el).stream()
.flatMap(rl -> rl.expand().stream())
.collect(Collectors.toList()));
}
}
|