M-ary trees

M-ary tree is a tree data structure in which each node has no more than m children. I have already mentioned M-ary trees in an earlier blog post. I’ve also written about the left child right sibling representation. In this blog post I want to write about M-ary trees in greater detail.

Refactoring

Refactoring is an important part of each project. It allows us to fix architectural mistakes, to better organize our code. Formal definition would say something like: Refactoring represents change in an internal structure of a software, in an attempt to make it more understandable and easier for modification, but without a visible shift in his behaviour. I have been applying refactoring techniques from the beginning of the project, to avoid having huge changes in the end.

Strategy Design Pattern

I have already written about the null object and the state design patterns and their use in designing and programming abstract data structures, with an emphasis on binary trees. In this post I decided to write about the strategy design pattern as it is a great way of extended existing trees by adding different balancing strategies. The strategy pattern is very similar to the state and null object patterns, but they solve different problems.

Trees

There have been some interesting changes in the last two weeks. The first of which is that I decided to change the name of my project ( repository ) to graPharo.
Next, I have been working on optimizing some layout algorithms. Equidistant circle and weighted circle have been implemented in many other projects, but the algorithms that were used, have not been working properly in every situation.
If we are talking about equidistant circle, the problem was found when we change the shape of vertices to rectangles or if vertices have different sizes. Than the positioning would not match the definition of equidistant ( to put all vertices on the circle in such a way, that they are equally distant from their neighbours). In the original algorithm to calculate angle of separation and the gap, we used only each vertices height, which worked well if the width is absolutly the same. But since that is not the case, we had to find the way to recognize which dimension is needed from which vertex and then use that one in the calculation.
Similar problem was with weighted circle, to calculate the weight factor of a vertex, we would only use height. Which would make a mistake if the width of the vertex is bigger than the height. For this reason, in the optimized version, we choose bigger of two dimensions and use it to make the calculation.

State Design Pattern

This week I continued with implementing different Tree data structures in Pharo, and have investigated the state design pattern as a good way of having a single class that can act as both an empty tree and a normal tree. In this blog post I will briefly describe the State Design Pattern and its applications. The state pattern is very closely related to the strategy and bridge design patterns. The Null object pattern that I described in a previous blog post can be regarded as a special case of the state pattern.

Meet The Authors

Nina Medić

Hi, my name is Nina and I am a master student of Computer Science in Novi Sad, Serbia. As a part in one of my classes I was introduced to Pharo world. The simplicity of the language and user friendly environment invited me to explore it more. Now I am a member of Pharo community and the team that is working on improving it.

Smiljana Knežev

Hi, my name is Smiljana Knežev and I am a final year undergraduate student at the Faculty of Sciences, University of Novi Sad. I am doing my studies in Informatics - Information Technologies, and I am very interested in Objected-Oriented design and functional and distributed programming. I am very passionate about Pharo and theoretical computer science and find it very interesting.