diff options
author | Pacien TRAN-GIRARD | 2016-04-29 22:58:58 +0200 |
---|---|---|
committer | Pacien TRAN-GIRARD | 2016-04-29 22:58:58 +0200 |
commit | 1fe15b896ede0882a0970602fea9d2e823b51095 (patch) | |
tree | 9418bc835082a64128def4af2efb6e12c22a1123 | |
parent | ceb1ac5ca1e08095150c1dbb971540149a455673 (diff) | |
download | xblast-1fe15b896ede0882a0970602fea9d2e823b51095.tar.gz |
Implement RLE and its tests
-rw-r--r-- | src/ch/epfl/xblast/Lists.java | 39 | ||||
-rw-r--r-- | src/ch/epfl/xblast/RunLengthEncoder.java | 184 | ||||
-rw-r--r-- | test/ch/epfl/xblast/RunLengthEncoderTest.java | 100 |
3 files changed, 310 insertions, 13 deletions
diff --git a/src/ch/epfl/xblast/Lists.java b/src/ch/epfl/xblast/Lists.java index 22d9d06..4cff795 100644 --- a/src/ch/epfl/xblast/Lists.java +++ b/src/ch/epfl/xblast/Lists.java | |||
@@ -70,6 +70,30 @@ public final class Lists { | |||
70 | } | 70 | } |
71 | 71 | ||
72 | /** | 72 | /** |
73 | * Returns a copy of the given list with element e prepended. | ||
74 | * | ||
75 | * @param l the list | ||
76 | * @param e the element to prepend | ||
77 | * @param <T> the type of the list's elements | ||
78 | * @return a copy of the list with the element prepended | ||
79 | */ | ||
80 | public static <T> List<T> prepended(List<T> l, T e) { | ||
81 | return Lists.inserted(l, 0, e); | ||
82 | } | ||
83 | |||
84 | /** | ||
85 | * Returns a copy of the given list with element e appended. | ||
86 | * | ||
87 | * @param l the list | ||
88 | * @param e the element to append | ||
89 | * @param <T> the type of the list's elements | ||
90 | * @return a copy of the list with the element appended | ||
91 | */ | ||
92 | public static <T> List<T> appended(List<T> l, T e) { | ||
93 | return Lists.inserted(l, l.size(), e); | ||
94 | } | ||
95 | |||
96 | /** | ||
73 | * Returns all the permutations of the elements of the given list. | 97 | * Returns all the permutations of the elements of the given list. |
74 | * | 98 | * |
75 | * @param l given list | 99 | * @param l given list |
@@ -90,4 +114,19 @@ public final class Lists { | |||
90 | return p; | 114 | return p; |
91 | } | 115 | } |
92 | 116 | ||
117 | /** | ||
118 | * Returns a copy of the given list with the first n items dropped. | ||
119 | * | ||
120 | * @param l given list | ||
121 | * @param n number of items to drop | ||
122 | * @param <T> the type of the list's elements | ||
123 | * @return a copy of the list with the n first element dropped | ||
124 | */ | ||
125 | public static <T> List<T> firstDropped(List<T> l, int n) { | ||
126 | if (Objects.isNull(l)) | ||
127 | return Collections.emptyList(); | ||
128 | |||
129 | return new ArrayList<>(l.subList(n, l.size())); | ||
130 | } | ||
131 | |||
93 | } | 132 | } |
diff --git a/src/ch/epfl/xblast/RunLengthEncoder.java b/src/ch/epfl/xblast/RunLengthEncoder.java index a3c8a88..ecb9f4e 100644 --- a/src/ch/epfl/xblast/RunLengthEncoder.java +++ b/src/ch/epfl/xblast/RunLengthEncoder.java | |||
@@ -1,34 +1,192 @@ | |||
1 | package ch.epfl.xblast; | 1 | package ch.epfl.xblast; |
2 | 2 | ||
3 | import java.util.ArrayList; | 3 | import java.util.Arrays; |
4 | import java.util.Collections; | ||
4 | import java.util.List; | 5 | import java.util.List; |
6 | import java.util.Objects; | ||
7 | import java.util.stream.Collectors; | ||
5 | 8 | ||
6 | /** | 9 | /** |
7 | * @author Timothée FLOURE (257420) | 10 | * Run-length byte array encoder and decoder. |
11 | * | ||
12 | * @author Pacien TRAN-GIRARD (261948) | ||
8 | */ | 13 | */ |
9 | public final class RunLengthEncoder { | 14 | public final class RunLengthEncoder { |
10 | 15 | ||
16 | private static final int REPLACE_THRESHOLD = 2; | ||
17 | private static final int MAX_RUN_LENGTH = -Byte.MIN_VALUE + REPLACE_THRESHOLD; | ||
18 | |||
19 | /** | ||
20 | * A run-length representing a sequence of a byte repeated n times. | ||
21 | */ | ||
22 | static class RunLength { | ||
23 | |||
24 | final int len; | ||
25 | final byte val; | ||
26 | |||
27 | /** | ||
28 | * Instantiates a run-length of byte val and length len. | ||
29 | * | ||
30 | * @param len the length | ||
31 | * @param val the value | ||
32 | */ | ||
33 | RunLength(int len, byte val) { | ||
34 | this.len = ArgumentChecker.requireNonNegative(len); | ||
35 | this.val = val; | ||
36 | } | ||
37 | |||
38 | /** | ||
39 | * Instantiates a unit length RunLength of the given value. | ||
40 | * | ||
41 | * @param val the value | ||
42 | */ | ||
43 | RunLength(byte val) { | ||
44 | this(1, val); | ||
45 | } | ||
46 | |||
47 | /** | ||
48 | * Instantiates a run-length from its byte encoded representation. | ||
49 | * | ||
50 | * @param len the encoded byte length | ||
51 | * @param val the value | ||
52 | */ | ||
53 | RunLength(byte len, byte val) { | ||
54 | this(-len + REPLACE_THRESHOLD, val); | ||
55 | } | ||
56 | |||
57 | /** | ||
58 | * Merges tho current and the given same value RunLengths. | ||
59 | * | ||
60 | * @param rl the other RunLength to combine. | ||
61 | * @return the summed-length RunLength | ||
62 | */ | ||
63 | RunLength merge(RunLength rl) { | ||
64 | if (Objects.isNull(rl) || rl.val != this.val) | ||
65 | throw new IllegalArgumentException(); | ||
66 | |||
67 | return new RunLength(this.len + rl.len, this.val); | ||
68 | } | ||
69 | |||
70 | /** | ||
71 | * Splits the RunLength in one or more RunLengths, ensuring they do not exceed the maximum encode-able length. | ||
72 | * | ||
73 | * @return the split RunLength list | ||
74 | */ | ||
75 | List<RunLength> split() { | ||
76 | List<RunLength> fullRll = Collections.nCopies(this.len / MAX_RUN_LENGTH, new RunLength(MAX_RUN_LENGTH, this.val)); | ||
77 | int remainder = this.len % MAX_RUN_LENGTH; | ||
78 | |||
79 | if (remainder == 0) | ||
80 | return fullRll; | ||
81 | else | ||
82 | return Lists.appended(fullRll, new RunLength(remainder, this.val)); | ||
83 | } | ||
84 | |||
85 | /** | ||
86 | * Encodes a RunLength into its byte array representation. | ||
87 | * | ||
88 | * @return the byte array representation | ||
89 | */ | ||
90 | List<Byte> encode() { | ||
91 | if (this.len <= REPLACE_THRESHOLD) | ||
92 | return this.expand(); | ||
93 | else | ||
94 | return Arrays.asList((byte) (-this.len + REPLACE_THRESHOLD), this.val); | ||
95 | } | ||
96 | |||
97 | /** | ||
98 | * Returns the expanded byte array form of a RunLength. | ||
99 | * | ||
100 | * @return the expanded byte array form | ||
101 | */ | ||
102 | List<Byte> expand() { | ||
103 | return Collections.nCopies(this.len, this.val); | ||
104 | } | ||
105 | |||
106 | @Override | ||
107 | public String toString() { | ||
108 | return String.format("(%d,%d)", this.len, this.val); | ||
109 | } | ||
110 | |||
111 | @Override | ||
112 | public boolean equals(Object o) { | ||
113 | if (this == o) return true; | ||
114 | if (o == null || getClass() != o.getClass()) return false; | ||
115 | |||
116 | RunLength rl = (RunLength) o; | ||
117 | return len == rl.len && val == rl.val; | ||
118 | } | ||
119 | |||
120 | } | ||
121 | |||
122 | /** | ||
123 | * Collapses contiguous same-value RunLength in the given list. | ||
124 | * Optimal collapse is not guaranteed if zero-length elements are not filtered out first. | ||
125 | * | ||
126 | * @param rll the RunLength list | ||
127 | * @return a collapsed RunLength list | ||
128 | */ | ||
129 | static List<RunLength> collapseRunLengths(List<RunLength> rll) { | ||
130 | if (Objects.isNull(rll) || rll.isEmpty()) | ||
131 | return Collections.emptyList(); | ||
132 | |||
133 | if (rll.size() == 1) | ||
134 | return rll; | ||
135 | |||
136 | RunLength current = rll.get(0), next = rll.get(1); | ||
137 | if (current.val == next.val) | ||
138 | return collapseRunLengths(Lists.prepended(Lists.firstDropped(rll, 2), current.merge(next))); | ||
139 | else | ||
140 | return Lists.prepended(collapseRunLengths(Lists.firstDropped(rll, 1)), current); | ||
141 | } | ||
142 | |||
11 | /** | 143 | /** |
12 | * Encode the given Byte sequence using the run length encoding. | 144 | * Decodes a RunLengths byte array representation into a RunLength list. |
13 | * | 145 | * |
14 | * @param input the given byte sequence | 146 | * @param el the encoded byte array |
147 | * @return the decoded RunLength lest | ||
148 | */ | ||
149 | static List<RunLength> decodeRunLengths(List<Byte> el) { | ||
150 | if (Objects.isNull(el) || el.isEmpty()) | ||
151 | return Collections.emptyList(); | ||
152 | |||
153 | if (el.get(0) < 0 && el.size() >= 2) | ||
154 | return Lists.prepended( | ||
155 | decodeRunLengths(Lists.firstDropped(el, 2)), | ||
156 | new RunLength(el.get(0), el.get(1))); | ||
157 | else if (el.get(0) >= 0) | ||
158 | return Lists.prepended( | ||
159 | decodeRunLengths(Lists.firstDropped(el, 1)), | ||
160 | new RunLength(el.get(0))); | ||
161 | else | ||
162 | throw new IllegalArgumentException(); | ||
163 | } | ||
164 | |||