Places of the new Pharo collections in the current hierarchy
Greetings everyone. My name is Alexander, I'm from computer science department of Tomsk State University, Russia. Currently, I'm on the 3rd course of my bachelor's degree, and I'm going to make a project related with Smalltalk and Pharo world.
The goal of my project is to power up the impressive collection set of Pharo with more interesting and complex collections, like CircularList, B-trees etc. The full list of collections which are planned to implement is avaliable at this site
Before we can start making new collections for Pharo, we need to uderstand, what place they will hold in this big world of Pharo collections? To reach this understanding, we need to review the core collections from the current language arsenal. When we will know about their placement, we will have enough information to place the new ones.
As I mentioned earlier, the collections library of Smalltalk programming language is great enough to solve almost every problem from computer science world. The hierarchy of collections classes is complex, but we try to depict them like on the picture below:
The following diagramm illustrates the simplified structure of collections hierarchy. So, all collections are splitted in a 3 big groups: sequanceable, hashed and other. Third group is a special group for collections, which we can't put neither in sequnceable nor in hashed.
With this diagramm we are really well armed to perfom a review of current core collections. During the review, I will try to give a some breif description of each collection and I will try to explain the difference between collections. Actually, the goal of this review, is just to understand "why" this collections are placed in the one category, and another collection are not.
So, let's start reviewing each node of this diagramm.
1. Sequanceable collections
Collections of this kind are organized in the way we can get to the every element consecutive by moving from one to another. From there, I will call this kind of collections with one word — containers.
Containers category is also divided in two categories: arrayed collections and unarrayed collections. So, let's find out:
1.1. Arrayed collections
Arrayed collections always have a fixed size and they can't change him during the execution. The most important collections from this subcategory are:
Array— This collection holds fixed amount of elements, which can be accessed through indexes. The most simple and pretty straightforward class. Have a widely usage in a design of more complex collections.
String— simply, container of characters. There are many different versions of this collection because of a great range of different encoding tables, charsets etc.
1.2. Unarrayed collections
Unarrayed collections have a dynamic size. They can help you to save memory by resizing themselves during the execution of programm. Their size always shrinks to the amount of data they store. Here, we need to pay attention to:
LinkedList- container with a very unusual way of connecting elements. Elemnts-neighbours connected with each-other by object of class Link. This kind of «linking» gives you some advantages in changing this data structure.
Interval— container wich holds a numeric sequance with a user-determinated difference. Almost every loop construction in Pharo uses this collection.
UnorderedCollection— basicaly, this collections is quite the same as array from arrayed category, but this one have a dynamic size.
Here comes the second big sub-tree of out hierarchy: hashed collections.
2. Hashed collections
Collections, which doesn't allow you to access their element directly, because their data stored by keys, which can be accessed by hashing them. This approach gives us ability to test this kind of collections for appearring some element incredibly fast.
Let's focus on these collections:
Set— a set, just as set from mathematics. Doesn't hold the same elements and supports all the main set operations: union, intersetioc etc.
Dictionary— a storage of «key-value» pairs.
We can conclude, that collections from this category are used to store some complex objects and relations between them.
However, we have two more interesting collections from another category:
As you remember, here we will place collections, which doesn't fit in terms of hashed or sequenceable. I want to tell you about two interesting classes:
Bag— idea of this collections is simillar to Dictionary, but instead of keys, this one holding a number of entries of each element.
Heap— implementation of binary heap, using the array.
4. And what's next?
So far we've done this review and now we are ready to make some thoughts about placement of new collections.
- First of all, we can easily place all kinds of planned lists(circular,doubly linked) to the sub-tree of Sequanceable collections. Actually, their place is in the subcategory of "Unnarrayed" collections. Why? Because they are just the modified versions of basic linked list! All of these collections share the same idea of "linking" the elements through special objects, as we get from the review. They even might be a childs of Linked List, but now i'm not really sure about it. During the implementation, this question will be answered and i will share my solution with you.
- Now, let's try to think about the different kinds of trees( cerrtainly, B-trees, Q-trees,Tries ). We can't bring them to the Sequanceable category because their way of organasing data theey store is far more complex than in arrays and lists. So, is there any reason to call these collections hashed? Nope. They have no usage of hash functions in their implementation. Thus, we need to admit, that these data structures a quite uniqie for Pharo and we have no more variants of placement. These collections a going to the category "Other".
Now, let's modify our previous diagramm by adding all the new collections:
And this is it! We've done a nice review of basic collections and then make a proper decision about places of new collections in Pharo collections hierarchy. So, I think this analysis is full enough to help us to start making new collections for Pharo Smalltalk. Feel free to ask questions and make suggestions. Thank you for you attention.