Standardized Data Structure Interface

Question

I want to work with a variety of data structures (arrays, singly/doubly linked lists, sorted structures, etc.) on a plug-and-play basis. For example, I want to be able to easily swap in and out the sorted list and the array (which is re-sorted after every insertion/deletion), to test which one has better performance.

In every language I know of, the public interface to such data structures is very inconsistent. So changing the implementation requires a lot of work.

Is there a language, or a language-agnostic design pattern, that makes it easy to define a generic public interface that works with any data structure?

Of course, I understand how different performance would be (e.g., binary search in a sorted array vs linear search in a regular array). All I ask is that the performance of the data structure doesn't degrade asymptotically or by a large constant factor due to the use of the standard interface.

Example problem: iterate through the container of numbers, find the two numbers that are nearest each other, and remove the pair of them. (If several pairs are equal distance, pick an arbitrary pair).

I'd like the code to solve the problem to be unchanged as I switch in and out different containers.

Answer 1

The best designed collection framework I have personally worked with, is Scala's, especially combined with the extensions from the Scalaz library.

The Haskell community currently seems to be the frontrunner when it comes to figuring out very general collection interfaces, see e.g. the Data.Traversable or Data.Foldable type classes, zippers, iteratees, enumeratees etc. (A lot of this is also implemented in Scalaz.)

Here's an example how to solve your problem in Scala. Note, I haven't done anything to make this efficient or beautiful, nor have I given any thought to whether this algorithm is sensible or not.

The important feature is that this code is only dependent on operations provided by the Seq trait (zipWithIndex, sorted, foldRight, filterNot), which is very general: it only assumes that the collection has a definite size and that elements may appear multiple times. That's it.

val s = Seq(5, 1, 9, 2, 6) // our test sequence

val sWithIndex = s zipWithIndex

val rejects = sWithIndex.sorted.foldRight(
  (Int.MaxValue, (
    (Int.MinValue, Int.MinValue), (Int.MinValue, Int.MinValue)))) {
  case ((el, i), (minDist, ((n1, i1), (n2, i2)))) => 
    if(math.abs(n2 - el) <= minDist)
      (math.abs(n2 - el), ((n2, i2), (el, i)))
    else
      (minDist, ((n1, i1), (n2, i2)))
  }._2

val rejectIndices = (rejects._1._2, rejects._2._2)

val result = sWithIndex filterNot { case (_, i) =>
  i == rejectIndices._1 || i == rejectIndices._2 } map (_._1)
// result = List(1, 9, 2)

This algorithm is O(n*log n), because sorted is a generic stable sort. You could make it O(n) by using a radix sort, since the elements are known to be integers.

Answer 2

The problem with the data structures you mentioned is, that they have a different semantic. I.e. they work in a different way and cannot have a common interface. E.g. a list could have an Add method that would add an element to the list. An array, however, cannot have such a method, since the length of the array fixed. An array allows you access elements randomly through an indexer (a[i] = x; print(a[k]);), but you cannot do that with a linked list. In a linked list you can only access the next or previous element starting at the list header or tail. An unsorted collection would probably have a Sort method, a inherently sorted collection (e.g. a binary tree sorted by a given key) of course not, as the elements get sorted at insertion.

One single interface won't work. You need a set of interfaces, each of them exposing specific aspects of collections.

---

If you want to compare different collection types, I suggest you to create wrappers using a common interface. You would then perform the tests on the wrappers.

Such a wrapper interface could look like this

public interface ICollectionTestWrapper<T>
{
    void FillWithTestData(IEnumerable<T> data);

    bool IsSortable { get; }
    void Sort();

    void FindElement(T element); // No return value needed for speed tests.

    // TODO: Add functionality for the tests you have in mind
    ...
}

Answer 3

Java does this somewhat.

See the List, Set, or Map interfaces. Each interface has a number of implementations, implementing the various operations in different ways.

Python also does this somewhat by virtue of its duck typing. The interface of different objects is similar, so you use the same code on different data structures.

Answer 4

Also there is a generic programming style, which allows to split data and algorithms. For more details see also C++ Standard Template Library

Answer 5

Its called Table in most systems:

OO systems that provide the concept of an Interface support swapping out implementations transparently. Java specifically does this Collection <- List <- ArrayList, LinkedList, etc.

C++ supports this as well. Python supports this. C would not support this directly.

Dependency Injection in the languages that support this would making plugging concrete implementations in and out configurable as well.

• Java: For a extremely generalized interface Guava has the Table interface and enough specific implementations to cover almost all cases.

• Lua really on has one collection type and that is Table.

A Table interface can serve all the general purposes of an Associative Array as well as a random access normal Array if you just use numbers for the keys.

Answer 6

Example problem: iterate through the container of numbers, find the two numbers that are nearest each other, and remove the pair of them. (If several pairs are equal distance, pick an arbitrary pair).

Data structures have different interfaces because they do different things. Arrays and linked lists are somewhat comparable in that they both store an ordered collection, but there are important differences even here: you generally don't refer to items in a linked list by index, memory is managed very differently, etc. When you start looking at other structures (heaps, sets, maps, binary trees, etc.) the differences increase and the similarities decrease.

If you're willing to give up some of the advantages of each of the structures you test for the sake of providing a uniform interface, there's nothing to stop you from defining a "List" interface and implementing it using each of the structures you want to test. Any language that supports polymorphism will do the job, and you can easily imagine a set of operations that are common to all the structures (insert, remove, sort, search). Just don't forget that your test conditions will be somewhat contrived -- by forcing the structures you test to conform to a common interface, you'll be ignoring the aspects that differentiate each structure from the group.

Answer 7

It sounds like you're looking for the strategy pattern. What you'll do is define your own interface (like find-nearest-neighbors(NumericCollection) or find-closest-value(NumericCollection, Integer)) and provide several implementations of it. Details of calling the various implementations are necessarily language-specific, but as long as each supports the defined interface, you should have a good basis for comparison.

Answer 8

C++'s STL has something along these lines - all collections support iterators which you can use to access the members, and the iterator is a standard class itself, so has the operations you want.

So you can walk an array using begin() to end(), and you can swap the array for a list without any issues.

However, some collections support different operations - although you can sort both array, list and queue, you can't sort a map or set (they're already sorted). This just means some operations don't make sense for some collections.

Look at the algorithms section of the STL for a set of operations that apply to every different type of STL collection.

Answer 9

You should research the Adapter Pattern. Using the Adapter Pattern, you'd define an interface, IContainer, that provides all the required operations, such as indexing, sorting, etc. You would then create different implementations of your IContainer interface, such as ArrayContainer, LinkedListContainer, and so on. Next, using a technique such as Dependency Injection, you could write your algorithms around your IContainer interface, thereby decoupling your code from any one particular container type. This would allow you to substitute and measure the performance of different kinds of containers.

Answer 10

Is there a language, or a language-agnostic design pattern, that makes it easy to define a generic public interface that works with any data structure?

Haskell seems like an awesome suggestion, but maybe a bit hardcore. At least I'm a little bit afraid of Haskell (it's a language whose code always inspires me, but I never actually got the nerve to try anything substantial).

I'd personally recommend C++ for this since the code generation of C++ templates allows you to eliminate any abstraction cost (dynamic dispatch, i.e.) out of the picture and just focus on the efficiency of the data structures themselves while likewise mutating the data structure easily (might be a little bit hard in functional languages without kind of changing the whole way you approach data structures). It's one of the few languages I personally know where you can write a contiguous data structure which performs just as well for random access as a plain old array, e.g., since the optimizer just squashes all that code structure you built down to smithereens.

It also comes with a pretty complete set of standard containers (though missing a few semi-common ones like tries) with a "near" data structure-agnostic interface. A little bit of wrapping should give you a universal interface that lets you do whatever you want, at least for value types (set vs. map). Key/value associative containers are a bit harder to generalize and might need to be in their own category, simply because they tend to call for a very different interface design.

The key to doing this to me is to define your universal interface. A C++ standard sequence like vector has these functions:

push_back -- appends an element to the back of the container.
insert -- inserts an element to any place in the container.
erase -- erases an element from any place in the container.
range insert -- inserts multiple elements to any place in the container.
range erase -- removes a range of elements from any place in the container.
empty -- returns size() == 0.
size -- returns the number of elements.
clear -- removes all elements from the container.
begin -- returns an iterator pointing to the beginning of the container.
end -- returns an iterator pointing to the end of the container.

There's also a fill constructor, range constructor, etc. (and you can even pass in your own memory allocator which usually isn't that helpful for something like vector but can make a huge difference for linked structures).

The linked-list, std::list, conforms to the same interface requirements except with some minor differences in this context like a push_front member function which is omitted from std::vector deliberately to discourage its use there.

You can easily wrap all these containers and, with little effort, apply a universal interface... maybe with functions like so:

push_front -- insert to front.
push_back -- insert to back.
erase -- erase anywhere.
insert -- insert anywhere with no regard about where the element goes.
insert_sorted -- do an insertion sort.
...

Etc. It won't take much time to wrap all applicable existing C++ containers to conform to this universal interface of your design as well as implement new ones that conform to it, and then you can benchmark your heart out and generate graphs and whatever you want.

A major thing to note about C++ is the iterator design driving algorithms. You can implement a custom data structure there, and by merely exposing iterators, hundreds of existing algorithms (not just standard but also third party) suddenly become applicable to your data structure with no extra effort. There's no need to implement like a sort method for your custom data structure, for example, as std::sort will work on it once you expose iterators to it.