dpdk Open Source

The collections package has some classes in it that provide a very powerful way of storing, retrieving, selecting, sorting and manipulating data. It features well known datastructures like lists (both the double linked list version and the array list version, very useful for storing lists of like object instances, which is useful in almost every application you encounter), queues (very useful for getting things done in a specified order, first in first out or FIFO), stacks , deques ( double ended queue, can function as a stack and a queue), heaps, priorityqueue, set, resultset (very useful when using flash remoting and a database) and trees (for menus, games, searching etc., both binary and n-ary trees). It is a very comprehensive library, influenced by the Java collections package, with a clear interface, easy to use and very consistent throughout the different classes. Know one of them, know ‘em all.

In our projects, whereever we needed datastructures, we’ve been using the great opensource package from Michael Baczynksy at polygonal.de for the use of lists, queues, stacks and trees
.
While it works great, it has some explicit design decisions that we do not want to follow, mainly the direct property access throughout the classes and the lack of reuse throughout the code. This works for him as it is fantastic for pure speed, but in our case we needed some other design decisions, as we wanted to make a better integration in our own package and also needed the flexibility to change the interface and have some stuff in there that better suited our way of programming. Plus the added benefit of throwing in some other powerful stuff, like selection, an easy setup of sorting on the lists, foolproof iterators (no unintended infinite loops) and some robust, high level code.

One of the first design decisions was to use the interface of the Java Collections as a basis for our collections package. This is a very well known interface which is perfectly suited for our goals.

The basics were lists: LinkedList and ArrayList. There were many requirements for the lists, but we were not afraid of making them power packed lists. Therefore the lists themselves were given the capabilities to be functionally very flexible and powerful. We decided to have them implement interfaces for queues, stacks, lists and Deque (double ended queue) as this would cover a lot of our uses cases of lists.

Furthermore we needed the lists to be sortable with quick (custom writable) sorting algorithms and to make them selectable by using a selection criterium that was outside of the list itself (get me all the listitems that satisfy a certain criterium), so we would not have to write code like users.getByFirstName(”henk”) but instead make this more generic (see the specifications post on this blog).

By implementing these interfaces, we were able to design the lists to be used in a multitude of situations just by casting them to a certain interface, for example:

//make it a queue
var queue: IQueue = new LinkedList();
queue.enqueue('a');
queue.enqueue('b');
trace(queue.dequeue());//'a'
 
//or make it a stack
var stack: IStack = new LinkedList();
stack.push('a');
stack.push('b');
trace(stack.pop());//'b'
 
 
//or make it have all the power you want from a list
var list: LinkedList = new LinkedList();
list.add('c');
list.add('a');
list.add('b');
//sort it, using quicksort, using one of the provided sort methods.
list.sort(Comparators.compareStringDescending, SortTypes.QUICK);
//now iterate
var iterator: IIterator = list.iterator();
while(iterator.hasNext()){
    //only one call to access data and go to the next item
    trace(iterator.next());
}
//trace output after sorting: c, b, a
//now select some stuff from the list with a one liner, getting a range from our list by using a specification
var subsetOfAlphabet: IList = list.selectBy(new getRangeFromAlphabetSpecification('a', 'b'));
trace(subsetOfAlphabet.toArray().toString());//b,a

As is obvious from the example above, the lists are usable in a multitude of programming problems where they can fullfill various roles and get to the solution fast. They can be manipulated in very powerful ways, provide good encapsulation and are very heavily unittested, therefore we know they work very well :). Did I also mention that they are fast? The different sorting methods (mergesort, quicksort etc) are very fast, very customizable and very convenient. Adding, removing, iterating, enqueing, dequeing, pushing and popping are also very fast. For concrete examples of using the lists, check out the test code to see what kind of powerful manipulations you can do.

We will delve deeper in the collections package in the near future on the blog. Our nice-to-have /todo list features articles on iterators, trees and how to manipulate / traverse them, sorting and an overview of the api.