JavaDataStructures/HuffmanFunctionalProgramming/Fork.java at master · upl-depot/JavaDataStructures · GitHub

History

104 lines (85 loc) · 2.94 KB

Raw

100

101

102

103

104

package HuffmanFunctionalProgramming;

import Heap.LeftistModule.Leftist;

import Heap.LeftistModule;

import List.ListModule;

import List.ListModule.List;

public class Fork implements CodeTree {

private Paire key;

private CodeTree left;

private CodeTree right;

public Fork(Paire key, CodeTree left, CodeTree right) {

this.key = Paire.merge(left.paire(), right.paire());

this.left = left;

this.right = right;

}

@Override

public boolean isLeaf() {

return false;

}

@Override

public Paire paire() {

return key;

}

public int compareTo(CodeTree n) {

return paire().compareTo(n.paire());

}

@Override

public CharBits getChar(List<Integer> bits) {

if (bits.head() == 0) {

return left.getChar(bits.tail());

}

return right.getChar(bits.tail());

}

@Override

public List<Integer> getCode(Character car, List<Integer> acc) {

if (left.paire().getChars().contains(car)) {

return ListModule.list(0, left.getCode(car, acc));

}

return ListModule.list(1, right.getCode(car, acc));

}

@Override

public List<Integer> encode(List<Character> chars, List<Integer> acc) {

if (chars.isEmpty()) {

return acc;

}

acc = ListModule.concat(getCode(chars.head(), ListModule.emptyList()), acc);

return encode(chars.tail(), acc);

}

public static CodeTree makeCodeTreeFromText(List<Character> text) {

return combineCodeTrees(makeLeftistFromFreqs(countFrequency(text, ListModule.emptyList()))).min();

}

public static List<Paire> countFrequency(List<Character> chars, List<Paire> acc) {

if (chars.isEmpty()) {

return acc;

}

if (!acc.reduce(false, (seed, head) -> head.getChars().head().equals(chars.head()))) {

return countFrequency(chars.tail(),

ListModule.list(new Paire(1, ListModule.list(chars.head())), acc));

}

return countFrequency(chars.tail(),

ListModule.list(new Paire(acc.head().getFr() + 1, acc.head().getChars()), acc.tail()));

}

public static Leftist<CodeTree> combineCodeTrees(Leftist<CodeTree> p) {

if (p.isEmpty()) {

return null;

}

if (p.size() == 1) {

return p;

}

CodeTree x = p.min();

p = p.delete();

CodeTree y = p.min();

p = p.delete();

return combineCodeTrees(p.insert(new Fork(new Paire(x.paire().getFr() + y.paire().getFr()), x, y)));

}

public static Leftist<CodeTree> makeLeftistFromFreqs(List<Paire> frequency) {

if (frequency.isEmpty()) {

return LeftistModule.emptyLeftist();

}

return LeftistModule.insert(makeLeftistFromFreqs(frequency.tail()), new Leaf(frequency.head()));

}

@Override

public String toString() {

return " (" + left + ", " + right + ")";

}

JavaDataStructures/HuffmanFunctionalProgramming/Fork.java at master · upl-depot/JavaDataStructures · GitHub

Uh oh!

Expand file tree

Breadcrumbs

Fork.java

Latest commit

History

Breadcrumbs

Fork.java

File metadata and controls