aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPacien TRAN-GIRARD2016-04-29 22:58:58 +0200
committerPacien TRAN-GIRARD2016-04-29 22:58:58 +0200
commit1fe15b896ede0882a0970602fea9d2e823b51095 (patch)
tree9418bc835082a64128def4af2efb6e12c22a1123
parentceb1ac5ca1e08095150c1dbb971540149a455673 (diff)
downloadxblast-1fe15b896ede0882a0970602fea9d2e823b51095.tar.gz
Implement RLE and its tests
-rw-r--r--src/ch/epfl/xblast/Lists.java39
-rw-r--r--src/ch/epfl/xblast/RunLengthEncoder.java184
-rw-r--r--test/ch/epfl/xblast/RunLengthEncoderTest.java100
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 @@
1package ch.epfl.xblast; 1package ch.epfl.xblast;
2 2
3import java.util.ArrayList; 3import java.util.Arrays;
4import java.util.Collections;
4import java.util.List; 5import java.util.List;
6import java.util.Objects;
7import 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 */
9public final class RunLengthEncoder { 14public 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