The aim of this project is to develop generic packages on n-ary and quaternary trees.
These packages will be reused to implement another
package allowing to achieve image compression and decompression.

Operations that one has to operate on n-ary tree are grouped into 3 categories : creation,
consultation and modification. Here are the list of procedures to code.

A node is represented by a record type containing the value of the root,
a pointer on the first child, a pointer on the brother and another one on the father tree.
The tree_nr type is set to private for hiding from user
package the data structure chosen to represent the n-ary tree.

We chose to pass as generic parameters the type of value of the root, the procedure
which displays element and the function that will be applied to each element.

We use also here an auxiliary procedure that make browse the tree along two ways of recursivity, the children
one and the brothers one.

The auxiliary procedure is as follow : we use a boolean, passed as data/results parameters, to finish the
recursive calls if value is found. If it is found, tree_curr is set to a null pointer.

Quaternary tree being a subcategory of n-ary tree, we declare a type "quaternary tree", which is a
subtype of n-ary tree. The generic parameters are the same as parameters of n-ary tree package.

We use "renames" ADA directive in specification part. This will allow to reuse all procedures and functions
implemented into n-ary tree package. Example :

We do the same thing for exceptions :

We define a childq_empty exception for Qt_Build procedure.

The aim est to carry out compression and decompression on an image using
a quaternary tree. The images that we use are squares and their dimension
is a power of 2. A color is defined from the 3 primary colors (red, green, blue)
and is integer coded.

The recursive compression algorithm of a image with dimension n is as follows :
if image is homogeneous, then we create a leaf whose root value is the color of
image. If image is not homogeneous, we split it into 4 sub-images of dimension n/2, and
we create a quaternary tree whose the four children are the 4 encoded sub-images.

Browsing all the quaternary tree, we get a set of values representing the compressed image.

It is specified that pimage package allows to :

create a test image from a dimension and a matrix.

We explain here how is_homogeneous function deals with 3 possibles cases :
tolerance is minimal (0), maximal (100), or between these two values. If it
is maximal, then we return a boolean set to true and a leaf is created with
the average value of the image (see procedure im_to_tree). If it is
minimal, we check that all pixels have the same value. Finally, for the middle case,
we test the inequality abs(primary_color-average) <= tolerance on each pixel.

Firstly, we must build a tree from encoded sequence (procedure load_im_encod and
imc_to__tree) and then rebuild image from this tree (procedure tree_to_im).

Test program main_tree_nary.adb and main_tree_quater.adb use respectively
tree_nary.adb and tree_quater.adb package. It is possible to make a tree for
checking the good operating of all main above procedures and functions.

Tets program main_pimage.adb allows to create an image and validate compression and
decompression. An example of image is displayed as :

Its size equals to 260 bytes (64*4+4) because we save also the dimension.
We take into account a tolerance to see if image is homogeneous. The tree built with
a minimal tolerance (0) is represented on the following figure :

Image compressed size equals to 104 bytes (25*4+4) with 4 bytes for dimension, which was
expected. With a maximal tolerance (100), we get a leaf with the average color of image (161)
because this one is considered as homogeneous from criterion into is_homogeneous function.

with a tolerance equal to 80, we get this tree :

We can notice that there will be a loss of information regards to test image with compression.
Indeed, the north-west part of image is seen as homogeneous with this tolerance. This is illustrated
on this figure :

For each case, we save compressed image and check decompression.

This project has enabled us to create a package to make
compression and decompression of images. The operations implemented for
quaternary trees were reused and validated for encoding algorithm.