Warning: session_start(): open(/var/lib/php/sessions/sess_rg03mmf7a6ejnfr22slkl3lrl8, O_RDWR) failed: No space left on device (28) in /var/www/tb-usercake/models/config.php on line 51
Warning: session_start(): Failed to read session data: files (path: /var/lib/php/sessions) in /var/www/tb-usercake/models/config.php on line 51
// This is using the implementation that seems to work fastest
// in reality, although it probably is O(n log n) due to the use
// of TreeMaps.
//
// The theoretically best implementation is O(n) due to replacing the
// TreeMaps with a linked list.
// I think it works, see LineComp_PairIndex_v2, but #1028231 is fuxx0red.
!include once #1027304 // Eclipse Collections
import org.eclipse.collections.impl.map.mutable.primitive.*;
final sclass LineCompCompressor {
int safety = 0;
replace Encodings with Map>.
abstract sclass Chunk {
abstract S text(L chunks);
}
srecord CPair(int i1, int i2) > Chunk {
CPair(IntPair p) { i1 = p.a; i2 = p.b; }
S text(L chunks) {
ret linesLL_rtrim(chunks.get(i1).text(chunks), chunks.get(i2).text(chunks));
}
}
srecord CPrim(S s) > Chunk {
S text(L chunks) { ret s; }
}
bool verbose = false, verboseCompressionSteps = false;
bool verboseStats;
bool sortLines = true;
bool verify = true;
new LineComp_PairIndex pairIndex;
Map textIDToLines;
LS allUniqueLines;
new L chunks;
int primChunks;
Map lineIndex;
Encodings simpleEncodings; // temporary
Encodings finalEncodings;
new LongIntHashMap existingPairsIndex; // formerly Map
int round, printStatsEvery = /*10000*/0, printStatsInFirstRounds = 10;
int printStatsEveryNSeconds = 10;
*() {}
*(SS texts) { loadTexts(texts); }
// key = version ID, values = text
void loadTexts(SS texts) {
textIDToLines = mapValuesToLinkedHashMap myToLines(texts);
}
LS myToLines(S s) { ret toLines_nOnly_reversible(s); }
S myFromLines(LS l) { ret fromLines_rtrim(l); }
run {
LS allLines = concatLists(values(textIDToLines));
if (verboseCompressionSteps) print("Uniquifying " + nLines(allLines));
allUniqueLines = uniquify(allLines);
if (verboseCompressionSteps) print("Have " + n2(allUniqueLines, "unique line"));
allLines = null; // allow me to forget
if (sortLines) sortInPlace(allUniqueLines);
if (verboseCompressionSteps) print("Sorted " + nLines(allUniqueLines));
for (S line : allUniqueLines)
chunks.add(new CPrim(line));
primChunks = l(chunks);
lineIndex = listIndex(collect s(chunks));
// simple encoding (only direct line references)
simpleEncodings = mapValues(textIDToLines,
(IF1>) (lines -> wrapIntArrayAsImmutableList(mapToIntArray(lines, line -> lineIndex.get(line)))));
//printAndCheckEncodings(simpleEncodings);
if (verboseCompressionSteps) print("Have simple encodings");
finalEncodings = compressPairs_v3();
if (verbose || verify) printAndCheckEncodings(finalEncodings);
}
void saveAsTextFile(File f) {
S out = exportEncoding(finalEncodings);
saveTextFile(f, out);
if (verify) checkDecompression(f, textIDToLines);
}
void checkDecompression(File file, Map textIDToLines) {
temp BufferedReader reader = bufferedUtf8Reader(file);
LineCompReader lcr = new(reader);
assertEquals(keysList(textIDToLines), asList(lcr.versions()));
for (S version : keys(textIDToLines))
assertEquals(lcr.textForVersion(version), lines_rtrim(textIDToLines.get(version)));
if (verbose) print("Decompression OK for " + nVersions(textIDToLines));
}
S asText() { ret exportEncoding(finalEncodings); }
S exportEncoding(Encodings encodings) {
new LS buf;
buf.add("LINECOMP " + primChunks); // magic signature
for (Chunk c : chunks) {
if (c cast CPair)
buf.add(c.i1 + " " + c.i2);
else
buf.add(((CPrim) c).s);
}
for (S id, L l : encodings)
buf.add(id + "=" + joinWithSpace(l));
ret lines_rtrim(buf);
}
Encodings compressPairs_v3() {
pairIndex.verbose = verboseCompressionSteps;
pairIndex.init();
for (S version, L l : simpleEncodings)
pairIndex.newChain(version, l);
pairIndex.haveChains();
simpleEncodings = null; // forget
NotTooOften nto = new(printStatsEveryNSeconds*1000);
IntPair toCompress;
// Compress only most popular pair in one step
while ping ((toCompress = pairIndex.mostPopularDuplicate()) != null) {
if (safety > 0 && --safety <= 0) fail("safety");
++round;
if (verboseStats)
if (printStatsEvery > 0 && (round % printStatsEvery) == 0
|| round <= printStatsInFirstRounds
|| nto!)
printStats();
int count = pairIndex.getCount(toCompress);
Int idx = makeCPair(toCompress);
int dups = pairIndex.numberOfDuplicates();
if (verboseCompressionSteps) print("Compressing pair " + toCompress + " (count=" + count + ") -> " + idx + ", " + (dups-1) + " remaining");
pairIndex.replacePair(toCompress.a, toCompress.b, idx);
}
if (verboseStats) printStats();
// reconvert to normal list
ret mapValues(ch -> ch.toList(), pairIndex.chains);
}
// TODO: check if pair is already there
Int makeCPair(IntPair p) {
long l = intPairToLong(p);
int idx = existingPairsIndex.getIfAbsent(l, -1);
if (idx < 0) {
idx = addAndReturnIndex(chunks, new CPair(p));
existingPairsIndex.put(l, idx);
}
ret idx;
}
void printAndCheckEncodings(Encodings encodings) {
for (S id, L encoded : encodings) {
if (verbose) print(id + ": " + joinWithSpace(encoded));
assertEquals(myFromLines(textIDToLines.get(id)), decode(encoded));
}
}
S decode(L encoded) {
ret myFromLines(lambdaMap chunkText(encoded));
}
S chunkText(int idx) {
ret chunks.get(idx).text(chunks);
}
void printStats() {
print("Round: " + round);
pairIndex.printStats();
}
}