"Worklow of developing new collections for Pharo" by Alexander Brenchev on at brenchev/6jxn656dns6gzhrno97bw5ktj  0 thanks

Worklow of developing new collections for Pharo

1. Introduction

Greetings everyone. In my previous article I introduced the idea of my project which called "New Collections for Pharo". So far I've done a review of current fundamental collections of Pharo language, and determined the places for the new ones.

Fore best development practice and good communication with Pharo community, I decided to make a workflow like this:

  1. Implementing the collection
  2. Writing unit-tests
  3. Creating an article with a brief review of implemented colllection

As a student, I had no such experience before. So, I decided to test this workflow on a simple example. Actually, it is "reinventing the wheel" as you can understand from the header of this post. I tried to implement simple linked list, which is already implemented in Pharo. Just now, he is ready and fully documented. You can download and use it freely from smalltalkhub using this tutorial.

I think, we are ready to move on. Also I want to metion, that with help of this post i'll later build a some kind of a template for articles, which I will use for describing implemented collections. So, feel free to share your opinions, comments and suggestions.

2. Implementation

2.1. Description

VerySimpleLinkedList - it is a sequntial collection of any objects, which connected to each other by wrapping into the Link object. This kind of wrapping ensures the main difference from the other collections - the search in VerySimpleLinkedList will be linear instead of constant. But this collections is well designed for easily modifing the content of the list. In case of insertion some element somewhere inside the list, we can simple change 2 pointers in the appropriate links.

2.2. Class definition

VerySimpleLinkedList is derived from SequntialCollection. Moreover, this collection is Unarrayed that means that VerySimpleLinkedList have a dynamic sizing. There are only two instance veriables - begin and end which means a first link and the last link of list, respectively.

2.3. Interface

2.3.1. Accsessing

As a name of the protocol said, here I placed methods for accessing elements of list.

  1. Getters for instance variables - firstLink and lastLink. Also, we can get their concrete values with methods first and last.
  2. Method for swapping elements of the list - swap: with:
  3. Method for accessing the value of link through index - at:
  4. Some methods for putting the links anywhere in the list - at: put:,at: putLink:

2.3.2. Adding

There are different methods for adding new links to the list. Every case have a special method.

  1. Simply add new element to the back - add:
  2. Add after something - add: after:,add: afterLink:
  3. Add before something - add: before:, add: beforeLink:
  4. Add on the edge of the list - addLast:,addFirst:

2.3.3. Copiyng

There are useful methods for copying and cloning the list in thew wat you desire. Their names describe themselves very well : copyWith: will clone the list with addition of new elements and copyWithout: will erase some elements.

2.3.4. Enumarating

In this protocol we just have some standard methods for almost every collection like select:, do:, collect: but reimplemented for the structure of VerySimpleLinkedList.

2.3.5. Removing

Here I implemented some methods for removing an elements from the list.

  1. For clearing the entire list just use removeAll
  2. With methods like removeFirst and removeLast you can easily build some interesting data structures like stack or deque on top of this linked list.
  3. If you want to remove some elements from list, which meets some condition you can use this condition with method removeAllSuchThat:
  4. Other methods like remove: or removeLink: gives your oportunity to remove single elemements. Also you can use their modifications with a keyword for exception blocks.

2.3.6. Testing

This kind of methods is using for checking the state of objects. For the needs of our collection we have only one method - isEmpty - which simply checks the list for holding something.

3. Collection tests

Testing is a very important part of any software development process. There are two main sources of information about testing related to Pharo:

  1. SUnit - the 7th chapter from Pharo by Example - the best place to introduce yourself to testing techniques.
  2. SmallLint: static analysis in Pharo - the 16th chapter from Pharo for Enterprise which can teach you how to use the Code Critic browser - great tool to use best Pharo code practise in your projects.

As it was my first writing tests experience, it was not so easy for me to decide, what kind of test should I choose to prove my collection? For now, I choose to start with a simple concept: let's try to think about the difference between the linked list and other sequeanceable collections?

  1. Elements can be inserted into list anywhere and with minimal cost of operations.
  2. Removing elements from the edge of the list (begin or end) is quite simillar but if we want to remove something from the inside we need to rearrange some pointers. Thats quire unusual.
  3. Swapping elements will also feature another style of implementation because of link-ing relations between elements.

So let's try to write our test according to this list of special functionality of linked lists.

3.1. The definition of VerySimpleLinkedListTest class

On this stage we need to choose wisely, what instance variables we need for out tests. Let's try to pefrorm this step-by-step:

  1. Fristly, we need some variable called list. It wiil be our main testing playground.
  2. Also, we need something, tht we can insert into our list. So, let's add some links: call them in a fashion like links1,links2 etc.

This little set of variables is great enough to write the tests for out desired functionality.

3.2. Setting up the tests

If you are done with the books from the header of this part, you must know about setUp method. This method is called every time, when testing occures. It's just like a constructor for out object and here we need to perform initialization of our instance variables. Links can get some random values and "list" must be an object of class VerySimpleLinkedList.

3.3. Genreal ideas of tests

Here i want to discuss some general ideas about testing the methods that we've choosen so far. If you will have any problems with implementation of tests, implementation is avaliable on my Smalltalkhub project page, but ideas are pretty easy so i suggetst you to try to write your tests by your own first.

  1. Tests for methods, which adds something - this kind of tests must be applied in iterative way. On each iteration we add something to the list, then we checks the size of our structure. If we are testing methods which inserts content in seom special place like begin of the list or somewhere in the middle, we also need to check correctnesses of placement of all elelements in list.
  2. Tests for methods, which removes something - here we have a quite the same idea, but we just need to remember, that removing will decrease the size of list instead of increase.
  3. Tests for swapping methods - with these methods we need to pay attenntion to different cases, in which can occures swapping procces. We can swap adajacent elements, or can swap the elements right on the edges of the list. Tests must handle all of this cases and after their passing you can be sure that you implementation of swap: with: is correct.

4. Conclusion

I hope that you will find this guide useful for your good start in the world of Pharo language programming. Thank you for your attention. More articles to come.

blog comments powered by Disqus