Implement RLE and its tests

2 files changed, 210 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 {
     }
 
     /**
+     * Returns a copy of the given list with element e prepended.
+     *
+     * @param l   the list
+     * @param e   the element to prepend
+     * @param <T> the type of the list's elements
+     * @return a copy of the list with the element prepended
+     */
+    public static <T> List<T> prepended(List<T> l, T e) {
+        return Lists.inserted(l, 0, e);
+    }
+
+    /**
+     * Returns a copy of the given list with element e appended.
+     *
+     * @param l   the list
+     * @param e   the element to append
+     * @param <T> the type of the list's elements
+     * @return a copy of the list with the element appended
+     */
+    public static <T> List<T> appended(List<T> l, T e) {
+        return Lists.inserted(l, l.size(), e);
+    }
+
+    /**
      * Returns all the permutations of the elements of the given list.
      *
      * @param l   given list
@@ -90,4 +114,19 @@ public final class Lists {
         return p;
     }
 
+    /**
+     * Returns a copy of the given list with the first n items dropped.
+     *
+     * @param l   given list
+     * @param n   number of items to drop
+     * @param <T> the type of the list's elements
+     * @return a copy of the list with the n first element dropped
+     */
+    public static <T> List<T> firstDropped(List<T> l, int n) {
+        if (Objects.isNull(l))
+            return Collections.emptyList();
+
+        return new ArrayList<>(l.subList(n, l.size()));
+    }
+
 }
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 @@
 package ch.epfl.xblast;
 
-import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
 import java.util.List;
+import java.util.Objects;
+import java.util.stream.Collectors;
 
 /**
- * @author Timothée FLOURE (257420)
+ * 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);
+    }
+
     /**
-     * Encode the given Byte sequence using the run length encoding.
+     * Decodes a RunLengths byte array representation into a RunLength list.
      *
-     * @param input the given byte sequence
+     * @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();
+    }
+