1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.imaging.formats.tiff.itu_t4;
18
19 import java.io.IOException;
20 import java.util.ArrayList;
21 import java.util.List;
22
23 import org.apache.commons.imaging.ImagingException;
24
25
26
27
28 final class HuffmanTree<T> {
29 private static final class Node<T> {
30 boolean empty = true;
31 T value;
32 }
33
34 private final List<Node<T>> nodes = new ArrayList<>();
35
36 public T decode(final BitInputStreamFlexible bitStream) throws ImagingException {
37 int position = 0;
38 Node<T> node = nodes.get(0);
39 while (node.value == null) {
40 int nextBit;
41 try {
42 nextBit = bitStream.readBits(1);
43 } catch (final IOException ioEx) {
44 throw new ImagingException("Error reading stream for huffman tree", ioEx);
45 }
46 if (nextBit == 0) {
47 position = (position << 1) + 1;
48 } else {
49 position = position + 1 << 1;
50 }
51 if (position >= nodes.size()) {
52 throw new ImagingException("Invalid bit pattern");
53 }
54 node = nodes.get(position);
55 if (node.empty) {
56 throw new ImagingException("Invalid bit pattern");
57 }
58 }
59 return node.value;
60 }
61
62 private Node<T> growAndGetNode(final int position) {
63 while (position >= nodes.size()) {
64 nodes.add(new Node<>());
65 }
66 final Node<T> node = nodes.get(position);
67 node.empty = false;
68 return node;
69 }
70
71 public void insert(final String pattern, final T value) throws ImagingException {
72 int position = 0;
73 Node<T> node = growAndGetNode(position);
74 if (node.value != null) {
75 throw new ImagingException("Can't add child to a leaf");
76 }
77 for (int patternPosition = 0; patternPosition < pattern.length(); patternPosition++) {
78 final char nextChar = pattern.charAt(patternPosition);
79 if (nextChar == '0') {
80 position = (position << 1) + 1;
81 } else {
82 position = position + 1 << 1;
83 }
84 node = growAndGetNode(position);
85 if (node.value != null) {
86 throw new ImagingException("Can't add child to a leaf");
87 }
88 }
89 node.value = value;
90 }
91 }