Java – HuffmanBTree

An implementation of an Huffman Binary Tree in Java.

The project’s goal was to compress any text given in input to an output file and decompress it.

To compress the input text, our Compress program counts the number of occurences of each letter, put that information in a Priority Queue and then build the Huffman Binary Tree.

The output file is written bit by bit. It first contains the number of chars that will be present in the file. Then there is a representation of the HuffmanBTree so that the file can be decompressed. And finally comes the compressed version of the text.

Here is the HuffmanBTree class. The rest of the code can be found here.

package business;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;

import business.exception.EmptyQueueException;

/**
*
* @author Boris
*/
public class HuffmanBTree implements Comparable<HuffmanBTree>{

 private char character;
 private HuffmanBTree left;
 private HuffmanBTree right;
 private HuffmanBTree parent;
 private int freq;
 private boolean isLeaf;
 
 public HuffmanBTree(){
 
 }
 
 //Constructor. Utilis� lorsqu'on cr�e des noeuds externes
 public HuffmanBTree(char c, int f) {
 this.character = c;
 this.freq = f;
 this.isLeaf = true;
 }
 
 //Constructor. Utilis� lorsq'un cr�e des noeuds internes
 public HuffmanBTree(int f,HuffmanBTree left,HuffmanBTree right) {
 this.freq = f;
 this.isLeaf = false;
 this.setLeft(left);
 this.setRight(right);
 }

 public HuffmanBTree merge(HuffmanBTree other) {
 int f = this.getFreq() + other.getFreq();
 HuffmanBTree parent = new HuffmanBTree(f,this,other);
 this.setParent(parent);
 other.setParent(parent);
 return parent;
 }
 
 /**
 * @pre treeList est une priority queue contenant une liste de huffmanBTree orodnn� par fr�quence.
 * @post Tous les arbres pr�sents dans la queue ont �t� fusionn�s en un seul arbre de Huffman, retourn� comme r�sultat.
 * @throws EmptyQueueException si une priority queue est vide.
 */
 public static HuffmanBTree mergeAll(PriorityQueue<HuffmanBTree> treeList) throws EmptyQueueException {
 if (treeList.size()==1){
 return treeList.peek();
 } else if (treeList.size()<1){
 throw new EmptyQueueException();
 } else {
 HuffmanBTree t1 = treeList.poll();
 HuffmanBTree t2 = treeList.poll();
 HuffmanBTree parent = t1.merge(t2);
 treeList.add(parent);
 return mergeAll(treeList);
 }
 }
 
 /**
 * Converti l'arbre en format binaire
 * @return
 */
 public void toBitCode(ArrayList<Boolean> bitList, ArrayList<Character> charList){
 bitList.clear();
 charList.clear();
 
 Stack<HuffmanBTree> toCompress = new Stack<HuffmanBTree>();
 toCompress.push(this);
 
 HuffmanBTree current;
 while(!toCompress.isEmpty()){
 current = toCompress.pop();
 if(current.isLeaf()){
 bitList.add(new Boolean(true));
 charList.add(new Character(current.getChar()));
 } else {
 bitList.add(new Boolean(false));
 toCompress.push(current.getRight());
 toCompress.push(current.getLeft());
 }
 }
 }
 
 //Pour que la file de priorit� ordonne les arbres par ordre de fr�quence
 public int compareTo(HuffmanBTree other) {
 return this.getFreq() - other.getFreq();
 }
 
 //Pour trouver si un arbre a un certain caract�re
 public boolean characterIs(char c){
 return this.character == c;
 }
 
 //utility methods
 public HuffmanBTree getLeft() {return left;}
 public HuffmanBTree getRight() {return right;}
 public HuffmanBTree getParent() {return parent;}
 public void setLeft(HuffmanBTree t) {this.left = t; if(t!=null)t.setParent(this);}
 public void setRight(HuffmanBTree t) {this.right = t; if(t!=null)t.setParent(this);}
 public void setParent(HuffmanBTree t) {this.parent = t;}
 public int getFreq() {return freq;}
 public char getChar(){return character;}
 public boolean isLeaf() {return isLeaf;}
 public void incrementFreq() {this.freq+=1;}
 public boolean hasLeftChild() {return this.left != null;}

 public void setCharacter(char c) {
 this.character = c;
 this.isLeaf = true;
 this.setLeft(null);
 this.setRight(null);
 }
}
Advertisements

Java – BinaryTreeSearch

Implementation of a BinaryTreeSearch in Java

(The project‘s goal was to parse some entries and be able to sort them via filters)

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

/**
 *
 * Implémentation de BinaryTreeSearch
 * 
 */
public class BinaryTreeSearch<K, V> {
 private Node root;
 
 private Comparator<K> comparator;
 
 /**
 * Constructeur
 */
 public BinaryTreeSearch(Comparator<K> comparator) {
 this.comparator = comparator;
 }
 
 /**
 * Implémentation de Node
 */
 private class Node {
 private K key;
 private TreeSet<V> values = new TreeSet<V>();
 private Node left;
 private Node right;
 
 /**
 * Constructeur
 */
 public Node(K key, V value) {
 this.key = key;
 this.values.add(value);
 this.left = null;
 this.right = null;
 }
 }
 
 
 /**
 * @pre --
 * @post - retourne null si la clé recherchée k n'est pas dans 
 * l'arbre
 * - retourne un itérateur contenant les valeurs du noeud
 * correspondant à la clé k 
 */
 public Iterator<V> get(K key) {
 return get(root, key);
 }
 /**
 * @pre --
 * @post - retourne null si le noeud est vide
 * - lance une recherche dans l'arbre de gauche si la clé
 * recherchée k est inférieure à la clé de node
 * - lance une recherche dans l'arbre de droite si la clé
 * recherchée k est supérieur à la clé de node
 * - retourne un itérateur contenant les valeurs du noeud
 * si la clé recherchée k est égale à la clé de node
 */
 private Iterator<V> get(Node node, K key) {
 if(node == null) return null;
 int comp = comparator.compare(key, node.key);
 if(comp < 0)
 return get(node.left, key);
 else if(comp > 0)
 return get(node.right, key);
 return node.values.iterator();
 }
 
 /**
 * @pre --
 * @post value est ajouté à l'arbre root
 */
 public void put(K key, V value) {
 root = put(root, key, value);
 }
 
 /**
 * @pre --
 * @post - crée un nouvelle arbre si root est vide
 * - ajoute value à l'arbre root
 */
 private Node put(Node node, K key, V value) {
 if(node == null) return new Node(key, value);
 int comp = comparator.compare(key, node.key);
 if(comp < 0) node.left = put(node.left, key, value);
 else if(comp > 0) node.right = put(node.right, key, value);
 else node.values.add(value);
 return node;
 }
}

Java – Parse and derivate an analytic expression using a Recursive Binary Tree

The program at this repository parse a file containing analytics expressions and write the derivates expression in the output file.

The supporting operations are sin, cos, +, -, *, /, ^ (exp)

But the interesting part is the Recursive binary tree implementation.
First we use an interface for generic purpose then we implement it.

To be complete, we need the classes Position and Node 

RBinaryTree.java

package linkedRBinaryTree;

/**
 * Interface for a Binary Tree defined recursively.
 *
 * This interface uses the Position interface described in DSAJ-4.
 *
 * @author Tanguy
 */
public interface RBinaryTree<E> extends Cloneable {
	/**
	 * @pre -
	 * @post return true if this is empty, false otherwise.
	 */
	public boolean isEmpty();

	/**
	 * @pre -
	 * @post return the number of nodes of this. Note: the number of nodes of an
	 *       empty tree is 0.
	 */
	public int size();

	/**
	 * @pre this is not empty.
	 * @post return a reference to the tree root.
	 */
	public Position<E> root();

	/**
	 * @pre this is not empty
	 * @post return true if this is reduced to a leaf (External Node), false
	 *       otherwise
	 */
	public boolean isLeaf();

	/**
	 * @pre this is not empty.
	 * @post return a reference to the left subtree.
	 */
	public RBinaryTree<E> leftTree();

	/**
	 * @pre this is not empty.
	 * @post return a reference to the right subtree.
	 */
	public RBinaryTree<E> rightTree();

	/**
	 * @pre this is not empty.
	 * @post o is the element stored at the root of this.
	 */
	public void setElement(E o);

	/**
	 * @pre this is not empty.
	 * @post tree is the left subtree of this. Parent of tree is this.
	 */
	public void setLeft(RBinaryTree<E> tree);

	/**
	 * @pre this is not empty.
	 * @post tree is the right subtree of this. Parent of tree is this.
	 */
	public void setRight(RBinaryTree<E> tree);

	/**
	 * @pre -
	 * @post an iterable collection of the positions of this, following an
	 *       inorder traversal, is returned.
	 */
	public Iterable<Position<E>> positions();

	/**
	 * @pre this is not empty.
	 * @post return a reference to the parent tree.
	 */
	public RBinaryTree<E> parent();

	/**
	 * @pre this is not empty.
	 * @post parent is the parent of this. this is not defined as parent's child
	 *       /!\
	 */
	public void setParent(RBinaryTree<E> parent);

	/**
	 * @pre this is not empty.
	 * @post return a reference to the first subtree which element's matching
	 *       element.
	 */
	public RBinaryTree<E> search(E element);

	/**
	 * @pre this is not empty.
	 * @post return a full clone of this.
	 */
	public LinkedRBinaryTree<E> clone();

	/**
	 * @pre this is not empty.
	 * @post return a string representation of this.
	 */
	public String toString();
}

LinkedRBinaryTree.java

package linkedRBinaryTree;

import java.util.ArrayList;

/**
 * @author Tanguy
 */
public class LinkedRBinaryTree<E> implements RBinaryTree<E>, Cloneable {
	private Position<E> root;
	private RBinaryTree<E> leftChild;
	private RBinaryTree<E> rightChild;
	private RBinaryTree<E> parent;

	public LinkedRBinaryTree() {
		this.root = null;
		this.leftChild = null;
		this.rightChild = null;
		this.parent = null;
	}

	@Override
	public boolean isEmpty() {
		return this.root == null;
	}

	@Override
	public int size() {
		int size = 0;
		if (!this.isEmpty()) {
			size += 1;
			if (this.leftTree() != null) {
				size += this.leftTree().size();
			}
			if (this.rightTree() != null) {
				size += this.rightTree().size();
			}
		}
		return size;
	}

	@Override
	public Position<E> root() {
		return this.root;
	}

	@Override
	public boolean isLeaf() {
		return this.leftChild == null && this.rightChild == null;
	}

	@Override
	public RBinaryTree<E> leftTree() {
		return this.leftChild;
	}

	@Override
	public RBinaryTree<E> rightTree() {
		return this.rightChild;
	}

	@Override
	public void setElement(E o) {
		this.root = new Node(o);
	}

	@Override
	public void setLeft(RBinaryTree<E> tree) {
		this.leftChild = tree;
		if (tree != null)
			tree.setParent(this);
	}

	@Override
	public void setRight(RBinaryTree<E> tree) {
		this.rightChild = tree;
		if (tree != null)
			tree.setParent(this);
	}

	@Override
	public Iterable<Position<E>> positions() {
		ArrayList<Position<E>> positions = new ArrayList();
		if (!this.isEmpty()) {
			positions.add(this.root);
			if (this.leftChild != null) {
				positions.addAll((ArrayList<Position<E>>) this.leftChild
						.positions());
			}
			if (this.rightChild != null) {
				positions.addAll((ArrayList<Position<E>>) this.rightChild
						.positions());
			}
		}
		return positions;
	}

	@Override
	public RBinaryTree<E> parent() {
		return parent;
	}

	@Override
	public void setParent(RBinaryTree<E> parent) {
		this.parent = parent;
	}

	public RBinaryTree<E> search(E element) {
		RBinaryTree<E> result = null;
		if (this.root.element().equals(element))
			result = this;
		else if (this.leftChild != null) {
			result = leftChild.search(element);
			if (result == null && this.rightChild != null) {
				result = rightChild.search(element);
			}
		}
		return result;
	}

	public LinkedRBinaryTree<E> clone() {
		LinkedRBinaryTree<E> linkedRBinaryTree = null;
		try {
			linkedRBinaryTree = (LinkedRBinaryTree<E>) super.clone();
		} catch (CloneNotSupportedException e) {
			e.printStackTrace(System.err);
		}

		linkedRBinaryTree.root = (Position<E>) root.clone();
		if (leftChild != null)
			linkedRBinaryTree.leftChild = (RBinaryTree<E>) leftChild.clone();
		if (rightChild != null)
			linkedRBinaryTree.rightChild = (RBinaryTree<E>) rightChild.clone();
		// linkedRBinaryTree.parent = (RBinaryTree<E>) parent.clone();

		// on renvoie le clone
		return linkedRBinaryTree;
	}

	public String toString() {
		if (this.leftChild != null && this.rightChild != null) {
			return "(" + this.leftChild.toString()
					+ this.root.element().toString()
					+ this.rightChild.toString() + ")";
		} else if (this.leftChild != null) {
			return this.root.element().toString() + "("
					+ this.leftChild.toString() + ")";
		} else {
			return this.root.element().toString();
		}
	}

}

Java – PostScript mini interpreter – Stack – IStack

Use a Stack to implement a mini PostScript interpreter.

https://github.com/lsinf1121-groupe3-2/mission1

IStack interface – for generic usage

package postScriptInterpreter;

import postScriptInterpreter.exception.EmptyStackException;

/**
 * Define the methods that a Stack class must implements to be manipulated by an Interpreter.
 * @param <E> the type of elements that the Stack will contains.
 */
public interface IStack<E> {
    /**
     * Return the number of elements in the stack.
     * @pre --
     * @post return number of elements in the stack.
     * @return number of elements in the stack.
     */
    public int size();
    
    /**
     * Return wheter the stack is empty.
     * @pre --
     * @post return true if the stack is empty, false otherwise.
     * @return true if the stack is empty, false otherwise.
     */
    public boolean isEmpty();
    
    /**
     * Inspect the element at the top of the stack.
     * @pre --
     * @post return top element of the stack, run a exception if the stack is empty.
     * @return top element of the stack, run a exception if the stack is empty.
     * @throws EmptyStackException if the stack is empty.
     */
    public E top() throws EmptyStackException;
    
    /**
     * Insert an element at the top of the stack.
     * @param element to be inserted.
     * @pre --
     * @post the stack has a new element in the front.
     */
    public void push(E element);
    
    /**
     * Remove the top lement from the stack.
     * @pre --
     * @post Element at the front of the queue is removed, return element remover and run an excpetion if the stak is empty.
     * @return element removed.
     * @throws EmptyStackException if the stack is empty.
     */
    public E pop() throws EmptyStackException;
    
    /**
     * Create a string that represent the stack.
     * @pre --
     * @post --
     * @return string representing the stack.
     */
    @Override
    public String toString();
}

Implementation of the IStack interface

package postScriptInterpreter;

import postScriptInterpreter.exception.EmptyStackException;

/**
 * Implementation of the interface : IStack
 *
 */
public class Stack implements IStack<String> {

	private int size;
	private Node first;
	
	private class Node {
		private String element;
		private Node next;
	}
	
	public Stack() {
		this.size = 0;
		this.first = null;
	}
	
	@Override
	public int size() {
		return this.size;
	}

	@Override
	public boolean isEmpty() {
		return this.size == 0;
	}

	@Override
	public String top() throws EmptyStackException {
		return this.first.element;
	}

	@Override
	public void push(String element) {
		Node current = first;
		first = new Node();
		first.element = element;
		first.next= current;
		size++;
		
	}

	@Override
	public String pop() throws EmptyStackException {
		if(this.isEmpty()) throw new EmptyStackException();
		String element = first.element;
		first = first.next;
		size--;
		return element;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Node tmp = first;
		while(tmp != null) {
			sb.append(tmp.element).append(" ");
			tmp = tmp.next;
		}
		return sb.toString()+"\n";
	}

}

Java – Unmarshaller using JAXB binding

The generated package has been generated by JAXB and the classes where generated too.

/**
* This method open, read and unmarshall a file
* @param URLFichier url of the file to open
* @return an entity object
*/
public MyEntity readFile (String URLfile){

 try {
   JAXBContext jc = JAXBContext.newInstance("generated"); //this is the name of the generated package
   Unmarshaller unmarshaller = jc.createUnmarshaller();
 
   File fileXML = new File(URLfile);
   JAXBElement parseResult = (JAXBElement) unmarshaller.unmarshal(fileXML);
   MyEntity myEntity = (MyEntity) parseResult.getValue();
 } 
 catch (JAXBException ex) {
   System.out.println("Erreur JAXB : " + ex.getMessage());
 } 
 catch (ClassCastException ex) {
   System.out.println("Erreur lors du cast : " + ex.getMessage());
 }
}

Java – DataBase access – basic class

This is a basic class to access a database using a persistence.xml file. This class has already 3 methods to handle the transactions.

public class DBaccess {

    private final EntityManagerFactory factory;
    private final EntityManager manager;
    private EntityTransaction transaction;

    public DBaccess() {
        factory = Persistence.createEntityManagerFactory("myPersistenceUnit");
        manager = factory.createEntityManager();
    }

    private void startTransaction() {
        transaction = manager.getTransaction();
        transaction.begin();
    }

    private void commit() {
        if (transaction != null) {
            transaction.commit();
        }
        transaction = null;
    }

    private void rollback() {
        if (transaction != null) {
            transaction.rollback();
        }
        transaction = null;
    }
}