From 1fe15b896ede0882a0970602fea9d2e823b51095 Mon Sep 17 00:00:00 2001 From: Pacien TRAN-GIRARD Date: Fri, 29 Apr 2016 22:58:58 +0200 Subject: Implement RLE and its tests --- src/ch/epfl/xblast/Lists.java | 39 +++++++ src/ch/epfl/xblast/RunLengthEncoder.java | 184 ++++++++++++++++++++++++++++--- 2 files changed, 210 insertions(+), 13 deletions(-) (limited to 'src/ch/epfl') 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 @@ -69,6 +69,30 @@ public final class Lists { return r; } + /** + * Returns a copy of the given list with element e prepended. + * + * @param l the list + * @param e the element to prepend + * @param the type of the list's elements + * @return a copy of the list with the element prepended + */ + public static List prepended(List 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 the type of the list's elements + * @return a copy of the list with the element appended + */ + public static List appended(List l, T e) { + return Lists.inserted(l, l.size(), e); + } + /** * Returns all the permutations of the elements of the 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 the type of the list's elements + * @return a copy of the list with the n first element dropped + */ + public static List firstDropped(List 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 split() { + List 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 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 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 collapseRunLengths(List 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 decodeRunLengths(List 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 encode(List input) { - List output = new ArrayList<>(); + public static List encode(List bl) { + List rll = bl.stream().map(RunLength::new).collect(Collectors.toList()); - return output; + return collapseRunLengths(rll).stream() + .flatMap(rl -> rl.split().stream()) + .flatMap(rl -> rl.encode().stream()) + .collect(Collectors.toList()); } /** - * Decode the given Byte sequence using the run length encoding. + * Decodes the given Byte sequence using the run length encoding. * - * @param input the given encoded byte sequence + * @param el the given encoded byte sequence * @return the decoded byte sequence */ - public static List decode(List input) { - List output = new ArrayList<>(); - - return output; + public static List decode(List el) { + return decodeRunLengths(el).stream() + .flatMap(rl -> rl.expand().stream()) + .collect(Collectors.toList()); } + } -- cgit v1.2.3