Skip to content

Instantly share code, notes, and snippets.

@elifarley

elifarley/MaxConsecutiveRepeatingRLE.java

Created April 22, 2015 14:57
Show Gist options
  • Save elifarley/73c861a5eee0bc438608 to your computer and use it in GitHub Desktop.
Save elifarley/73c861a5eee0bc438608 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
MaxConsecutiveRepeatingRLE.java
package org.ecc.numericnotation;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.nio.charset.Charset;
import java.util.Arrays;
/**
*
* @see http://math.stackexchange.com/a/1219777/228023
* @author Elifarley
*
*/
public class MaxConsecutiveRepeatingRLE {
private static final Charset UTF8 = Charset.forName( "UTF-8" );
public static String encode( final String in, final int minRepetitions, final int maxCount ) {
final byte[] c = in.getBytes( UTF8 );
return encodeToString( c, minRepetitions, maxCount );
}
public static String encodeToString( final byte[] in, final int minRepetitions,
final int maxCount ) {
return new String( encode( in, minRepetitions, maxCount ), UTF8 );
}
public static byte[] encode( final byte[] in, final int minRepetitions, final int maxCount ) {
System.out.print( String.format( "in %s: ", minRepetitions ) );
for ( final byte b: in ) {
System.out.print( ( b & 0xFF ) + " " );
}
System.out.println();
final ByteArrayOutputStream out = new ByteArrayOutputStream( (int) ( in.length * 1.5 ) );
try {
encode( in, minRepetitions, maxCount, out );
} catch ( final IOException e ) {
throw new RuntimeException( e );
}
System.out.print( "out: " );
for ( final byte b: out.toByteArray() ) {
System.out.print( ( b & 0xFF ) + " " );
}
System.out.println();
return out.toByteArray();
}
public static void encode( final byte[] in, final int minRepetitions, final int maxCount,
final OutputStream out ) throws IOException {
int lastC = Integer.MAX_VALUE;
int repeatedCount = 0;
final byte[] repeated = new byte[ minRepetitions - 1 ];
for ( final byte element: in ) {
final int c = element & 0xFF;
if ( c == lastC ) {
repeatedCount++;
if ( repeatedCount < maxCount ) {
continue;
}
repeatedCount--;
}
if ( repeatedCount > 0 ) {
if ( repeatedCount + 1 < minRepetitions ) {
Arrays.fill( repeated, 0, repeatedCount, (byte) lastC );
out.write( repeated, 0, repeatedCount );
} else {
Arrays.fill( repeated, (byte) lastC );
out.write( repeated, 0, repeated.length );
out.write( repeatedCount + 1 - minRepetitions );
}
repeatedCount = 0;
}
out.write( c );
lastC = c;
}
if ( repeatedCount > 0 ) {
if ( repeatedCount + 1 < minRepetitions ) {
Arrays.fill( repeated, 0, repeatedCount, (byte) lastC );
out.write( repeated, 0, repeatedCount );
} else {
Arrays.fill( repeated, (byte) lastC );
out.write( repeated, 0, repeated.length );
out.write( repeatedCount + 1 - minRepetitions );
}
}
}
public static byte[] decode( final byte[] in, final int minRepetitions ) {
final ByteArrayOutputStream out = new ByteArrayOutputStream( (int) ( in.length * 1.5 ) );
try {
decode( in, minRepetitions, out );
} catch ( final IOException e ) {
throw new RuntimeException( e );
}
System.out.print( "out: " );
for ( final byte b: out.toByteArray() ) {
System.out.print( ( b & 0xFF ) + " " );
}
System.out.println();
return out.toByteArray();
}
public static void decode( final byte[] in, final int minRepetitions, final OutputStream out )
throws IOException {
final byte[] repeated = new byte[ minRepetitions - 1 ];
int lastC = Integer.MAX_VALUE;
int repeatedCount = 0;
for ( final byte element: in ) {
int c = element & 0xFF;
if ( repeatedCount + 1 < minRepetitions ) {
if ( c == lastC ) {
repeatedCount++;
continue;
}
}
if ( repeatedCount > 0 ) {
if ( repeatedCount + 1 == minRepetitions ) {
repeatedCount = c;
final byte[] dec = new byte[ repeatedCount + minRepetitions - 1 ];
Arrays.fill( dec, (byte) lastC );
out.write( dec, 0, dec.length );
c = Integer.MAX_VALUE;
} else {
Arrays.fill( repeated, 0, repeatedCount, (byte) lastC );
out.write( repeated, 0, repeatedCount );
out.write( c );
}
repeatedCount = 0;
} else {
out.write( c );
}
lastC = c;
}
if ( repeatedCount > 0 ) {
if ( repeatedCount + 1 == minRepetitions ) {
repeatedCount = lastC;
final byte[] dec = new byte[ repeatedCount + minRepetitions + 1 ];
Arrays.fill( dec, (byte) lastC );
out.write( dec, 0, dec.length );
} else {
Arrays.fill( repeated, 0, repeatedCount, (byte) lastC );
out.write( repeated, 0, repeatedCount );
}
}
}
}
Raw
MaxConsecutiveRepeatingRLETest.java
package org.ecc.numericnotation;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.fail;
import org.junit.Test;
public class MaxConsecutiveRepeatingRLETest {
@Test
public final void testEncodeStringIntInt() {
fail( "Not yet implemented" );
}
@Test
public final void testEncodeToString() {
fail( "Not yet implemented" );
}
@Test
public final void encodeNonRepeatingSymbols() {
assertArrayEquals( new byte[] {
'a', 'b'
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'a', 'b'
}, 2, 4 ) );
}
@Test
public final void encodeSpecialCase() {
assertArrayEquals( new byte[] {
2, 2, 2
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
2, 2, 2, 2
}, 2, 4 ) );
assertArrayEquals( new byte[] {
2, 2, 2, 2
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
2, 2, 2, 2, 2
}, 2, 4 ) );
}
@Test
public final void decodeNonRepeatingSymbols() {
assertDecode( new byte[] {
'a', 'b'
}, 2, 4 );
}
@Test
public final void decodeSpecialCase1() {
assertDecode( new byte[] {
2, 2, 2, 2
}, 2, 4 );
}
@Test
public final void decodeSpecialCase2() {
assertDecode( new byte[] {
2, 2, 2, 2, 2
}, 2, 4 );
}
@Test
public final void decodeSpecialCase3() {
assertDecode( new byte[] {
3, 3, 3, 3, 3, 3
}, 3, 6 );
assertDecode( new byte[] {
3, 3, 3, 3, 3, 3, 3
}, 3, 6 );
}
@Test
public final void decodeAAB() {
assertDecode( new byte[] {
'a', 'a', 'b'
}, 2, 4 );
}
@Test
public final void decodeABB() {
assertDecode( new byte[] {
'a', 'b', 'b'
}, 2, 4 );
}
@Test
public final void decode3ABBCCC() {
assertDecode( new byte[] {
'a', 'b', 'b', 'c', 'c', 'c'
}, 3, 4 );
}
@Test
public final void decode1to5() {
assertDecode( new byte[] {
'1', '2', '2', '3', '3', '3', '4', '4', '4', '4', '5', '5', '5', '5', '5'
}, 3, 4 );
}
private static void assertDecode( final byte[] b, final int minRepetitions, final int maxCount ) {
assertArrayEquals( b, MaxConsecutiveRepeatingRLENotation.decode(
MaxConsecutiveRepeatingRLENotation.encode( b, minRepetitions, maxCount ),
minRepetitions ) );
}
@Test
public final void encode2AAB() {
assertArrayEquals( new byte[] {
'a', 'a', 0, 'b'
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'a', 'a', 'b'
}, 2, 4 ) );
}
@Test
public final void encode2ABB() {
assertArrayEquals( new byte[] {
'a', 'b', 'b', 0
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'a', 'b', 'b'
}, 2, 4 ) );
assertArrayEquals( new byte[] {
'a', 'b', 'c', 'c', 0
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'a', 'b', 'c', 'c'
}, 2, 4 ) );
}
@Test
public final void encode2ABBCCC() {
assertArrayEquals( new byte[] {
'1', '2', '2', 0, '3', '3', 1
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'1', '2', '2', '3', '3', '3'
}, 2, 4 ) );
assertArrayEquals( new byte[] {
'1', '2', '2', 0, '3', '3', 1, 'x'
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'1', '2', '2', '3', '3', '3', 'x'
}, 2, 4 ) );
}
@Test
public final void encode3ABBB() {
assertArrayEquals( new byte[] {
'a', 'a', 'b', 'b', 'b', 0
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'a', 'a', 'b', 'b', 'b'
}, 3, 4 ) );
}
@Test
public final void encode3ABBCCC() {
assertArrayEquals( new byte[] {
'1', '2', '2', '3', '3', '3', 0
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'1', '2', '2', '3', '3', '3'
}, 3, 4 ) );
}
@Test
public final void encode34AAAAAC() {
assertArrayEquals( new byte[] {
'5', '5', '5', 1, '5', 'A'
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'5', '5', '5', '5', '5', 'A'
}, 3, 4 ) );
}
@Test
public final void encode34AAAAA() {
assertArrayEquals( new byte[] {
'5', '5', '5', 1, '5'
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'5', '5', '5', '5', '5'
}, 3, 4 ) );
}
@Test
public final void encode3ABBCCCDDDDEEEEE() {
assertArrayEquals( new byte[] {
'1', '2', '2', '3', '3', '3', 0, '4', '4', '4', 1, '5', '5', '5', 1, '5'
}, MaxConsecutiveRepeatingRLENotation.encode( new byte[] {
'1', '2', '2', '3', '3', '3', '4', '4', '4', '4', '5', '5', '5', '5', '5'
}, 3, 4 ) );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment