"Basic tests for new Pharo collections" by Alexander Brenchev on at brenchev/1xtwat4f10o3w8te0wacow2pg  0 thanks

Basic tests for new Pharo collections

1. Introduction

Greetings everyone. My name is Alexander, and I'm trying to make a new collections for Pharo. For now, I've prepared some basic tests to determine main functionality of these collections. There are three collections which i planned to implement:

  1. MultiValueDicionary
  2. CircularList
  3. Btree

Feel free to comment my code and make suggestions and express your thoughts about how these collections must work in Pharo.

2. Collections and tests overview

Now we are going to traverse this list of collections to overiew each class functionality and I'll try to explain you why the tests written in the way they are.

2.1. MultiValue Dictionary

2.1.1. What is that?

MultiValueDctionary - is dictionary which contains a pairs, which looks like Key -> {Val1. Val2. .. ValN}, thath means, that keys are mapped to the arrays of values.

2.1.2. How does it works?

In this section I want to introduce you to MultiValueDictionary tests. These tests will help you understand the principle of collection's functionality. Each tests will begin with an explanation sub-section which contains a motivation for the test.

2.1.2.1. Adding elements to the dictionary

    testAddAnother
	| multidict |
	multidict := MultiValueDictionary new.
	multidict add: #a -> 1.
	multidict add: #a -> 2.
	multidict add: #b -> 3.
	self assert: (multidict at: #a) = {1. 2}.
	self assert: (multidict at:#b) = {3}.

Explanation: The ordinary dictionary will override the value, mapped to the existing key in case of addition a new value to that key. MultiValueDictionary will add that new value to the array of values mapped to that key.

2.1.2.2. Accessing elements with at: put:

    testAtPut
	| multidict |
	multidict := MultiValueDictionary new.
	multidict at:#a put: 1.
	multidict at:#b put:2.
	multidict at: #a put:3.
	self assert: (multidict at:#a) = {1. 3}.
	self assert: (multidict at:#b) = {2}.

Explanation: The idea of this test is quite the same as the previous, but at: put: message is more user-friendly, because it doesn't uses the intermediate Association object.

2.1.2.3. Testing for association inclusion

testIncludeAssociation
	| multidict |
	multidict := MultiValueDictionary new.
	multidict at:#a put:1.
	multidict at:#a put:2.
	multidict at:#b put:3.
	self assert: (multidict includesAssociation: #a->1).
	self assert: (multidict includesAssociation: #a->2).
	self assert: (multidict includesAssociation: #b->3).
Explanation: This test shows that if MultiValueDictionary contains an association key -> { Val1,Val2 } it means that it holds associations key -> Val1 and key -> Val2 respectively.

2.1.2.4. Finding the value, associatied with a specified key

testKeyAtValueIfAbsent
	| multidict |
	multidict := MultiValueDictionary  new.
	multidict add: #a->1.
	multidict add: #a->2.
	multidict add: #b->3.
	self assert: (multidict keyAtValue: 1 ifAbsent:[] ) = #a.
	self assert: (multidict keyAtValue: 2 ifAbsent:[]) = #a.
	self assert: (multidict keyAtValue: 3 ifAbsent:[] ) = #b.
Explanation: This is a test for proper keyAtValue behaviour.

2.1.2.5. Traversing the dictionary with keysAndValuesDo:

testKeysAndValuesDo
	| collection anAssociations |
	collection := MultiValueDictionary new.
	anAssociations := OrderedCollection new.
	collection add: #a->1.
	collection add: #a->2.
	collection add: #a->3.
	collection add: #b->2.
	collection add: #b->4.
	collection add: #b->5.
	collection keysAndValuesDo: [ :key :value |
			anAssociations add: key->value.
			self assert: (collection includesAssociation: key -> value)
Explanation: This tests ensures that keysAndValuesDo will affect all of the associations of the MultiValueDictionary.

2.1.2.6. Counting the entries of specified value

testOccurencesOf
	| multidict |
	multidict := MultiValueDictionary new.
	multidict add:#a->1.
	multidict add:#b->2.
	multidict add:#a->3.
	multidict add:#c->4.
	multidict add:#c->2.
	self assert: ( multidict occurrencesOf: 1 ) equals: 1.
	self assert: (multidict occurrencesOf: 2) equals: 2.
	self assert: (multidict occurrencesOf: 3) equals: 1.
	self assert: (multidict occurrencesOf: 4) equals: 1.
Explanation: This is a test for proper counting of value entries.

2.1.2.7. Removing a key from the dictionary

testRemoveKey
	| multidict |
	multidict := MultiValueDictionary new.
	multidict at:#a put:1.
	multidict at:#b put:2.
	multidict at:#a put:3.
	multidict removeKey:#a.
	self assert: (multidict size = 1).
	self should:[ (multidict at:#a) ] raise: Error.
	self assert: (multidict includesAssociation: #b->2).
	self should: [ (multidict removeKey: #c) ] raise: Error.
	
Explanation: This tests ensures that you can't remove a key, which is not in the dictionary and that removing operation will not remove any keys, others from your desired ones.

2.2. Circular List

2.2.1. What is that?

CircularList - is a linked list, whose tail have an additional pointer to the head of the list.

Attention

What list we need to use as a base for this collection? Singly-linked or doubly-linked list? Please, share your opinion in the comments to this article or send it to the duscission to mailing list.

2.2.2. How does it work?

Let's review the tests for this collection in the same manner as we do with tests for MultiValueDictionary. Firstly, you will look at the code and after that i will describe the motivation of this test.

2.2.2.1. Adding elements after some link

testAddAfter
	| collection |
	collection := OrderedCollection new.
	list := LinkedList new.
	list add: link1.
	self assert: list size = 1.
	self assert: list first == link1.
	self assert: ((list tail) nextLink = list first).
	
	list add: link2 after: link1.
	self assert: list size = 2.
	self assert: list first == link1.
	self assert: list second == link2.
	self assert: ((list tail) nextLink = list first).
	
	
	list add: link3 after: link2.
	self assert: list size = 3.
	self assert: list first == link1.
	self assert: list second == link2.
	self assert: list third == link3.
	self assert: ((list tail) nextLink = list first).
	
	list add: link4 after: link3.
	self assert: list size = 4.
	self assert: list first == link1.
	self assert: list second == link2.
	self assert: list third == link3.
	self assert: list fourth == link4.
	self assert: ((list tail) nextLink = list first).
Explanation: The main idea of this test is to check that tail's pointer always properly points to the head of the list. In other ways this test looks just like the same test for LinkedList. Tests for other messages, that modifies the list (e.g AddLast,AddBefore) written in the same fashion, so I think it is not neccesary to list them here. All of the tests are avaliable on my project page which listed below.

2.2.2.2. Do something with a values of links

testDo
	| collection counter|
	list with: link1 with:link2 with:link3 with:link4.
	collection := OrderedCollection new.
	counter := 0.
	list do: [ :elem | collection add:elem.
			counter := counter + 1 ].
	self assert: ( counter = list size ).
	self assert: (collection first = link1 value).
	self assert: (collection second = link2 value).
	self assert: (collection third = link3 value).
	self assert: (collection fourth = link4 value).
Explanation: This tests ensures that aBlock argument of do: message runs with exactly values which the links of CircularList holds.

2.2.2.3. Checks the list integrity after adding node in the middle

testForListIntegrityAfterAdding
	| collection |
	collection := OrderedCollection new.
	list with: link1 with:link2.
	list add:link3 after: link1.
	list linksDo: [ :elem | collection add:elem ].
	self assert: (collection first = link1).
	self assert: (collection second  = link3).
	self assert: (collection third = link2).
	
Explanation: The heading tells everything. In this test we checked that structure of list is OK after addition of a new link in the middle.

2.2.2.4. Do something with a links of list

testLinksDo
	| collection counter |
	list with: link1 with:link2 with:link3 with:link4.
	collection := OrderedCollection new.
	counter := 0.
	list linksDo: [ :elem | collection add:elem.
			counter := counter + 1 ].
	self assert: ( counter = list size ).
	self assert: (collection first = link1).
	self assert: (collection second = link2).
	self assert: (collection third = link3).
	self assert: (collection fourth = link4).
Explanation: In this test we are checking that aBlock argument runs with every link from a CircularList.

2.3. B-tree

2.3.1. What is that?

B-tree is a complex tree data structure which keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.

I decided to make a front-end of this collection the same as of the Dictionary. Actually, it means that:

  1. The interface will be the same
  2. Btree will hold Association objects in their nodes

The main difference will be in the internal structure of this collection which will allow users to perform operations on the strored data very fast.

2.3.2. How does it works?

It works the same way as the ordinary dictionary works. The Btree will have the same protocol for adding elements with messages like at: put:. This collection will support searching elements with message at: or includes:. Also, you can remove data from it with removeKey:.

3. Conclusion

Thank you for your attention on new Pharo collections. Your feedback about this article will be really appreciated. The full code availiable at project page

blog comments powered by Disqus