Trait

From APIDesign

Trait is a delta - a difference - that you can mix-in when using modern OOP languages when creating your own class. Traits are frequently present in Scala.

Is C better than C++?

Recently I've noticed an interesting article describing why C is more effective than C++ and in general most of OOP languages. The article is well written and for a while I was nodding in an agreement. The claim that by using OOP and insisting on encapsulation one cannot implement linked list as effectively as in C is a very good one!

However later I realized that the take on OOP is really targeted to OOP languages of the past. In modern languages, like Scala, one can keep encapsulation and still be as effective as the old plain good C. As Martin Odersky once put it: there used to be a time when people were arguing whether we need goto statement to effectively find a particular number in a matrix. Those days are gone - we can focus on new problems. The same applies to effective and encapsulated list problem. I am not a Scala expert, but I knew its type system is powerful enough. It took me few hours to re-learn Scala, but finally I created the code...

Effective and Encapsulated List

To create as effective list as presented in C in the article one needs an orchestration between the list class and its elements. Fine, let's achieve that with traits. First of all define the prev and next pointers each type willing to participate in a list needs to provide:

Code from Listable.scala:

trait Listable[T] {
  private[effectivelist] var prev : T = _
  private[effectivelist] var next : T = _
}
 

Please note that the definition of Listable item is using private access modifiers giving access only to the List implementation that operates on top of such items. Its Java type would be class List<T extends Listable<T>> - e.g. list of elements of type T that have prev and next fields in side them pointing to T. The Scala version follows:

Code from List.scala:

final class List[T <: Listable[T]] {
  private var item : T = _
  private final var EMPTY : T = _
 
  final def get(index : Int) : T = {
    var pos : T = item;
    for (i <- 1 to index) {
      pos = pos.next;
      if (pos == item) {
        throw new IndexOutOfBoundsException()
      }
    }
    return pos
  }
 
  final def size() : Int = {
    if (item == EMPTY) {
      return 0
    }
    var size = 0
    var pos : T = item
    do {
      size = size + 1
      pos = pos.next
    } while (pos != item)
    return size
  }
 
  final def add(toAdd : T) : Boolean = {
    if (toAdd.prev != EMPTY) {
      return false
    }
 
    if (item == null) {
      item = toAdd
      toAdd.next = toAdd
      toAdd.prev = toAdd
      return true
    } else {
      toAdd.prev = item.prev
      item.prev.next = toAdd
      item.prev = toAdd
      toAdd.next = item
      return true
    }
  }
  final def remove(toRemove : T) : Boolean = {
    if (toRemove.prev == EMPTY) {
      return false
    } else {
      toRemove.prev.next = toRemove.next
      toRemove.next.prev = toRemove.prev;
      if (item.next == item) {
        item = EMPTY
      }
      if (item == toRemove) {
        item = toRemove.next
      }
      toRemove.next = EMPTY
      toRemove.prev = EMPTY
      return true
    }
  }
}
 

The List is the only class that operates the next and prev fields of its items - the encapsulation is guaranteed (thus the OOP principles are kept). Of course, given the implementation is a one-to-one copy of the C list, it is going to be as effective as the C one. Here is its sample usage:

Code from ListTest.scala:

case class Person(name : String, age : Int) extends Listable[Person]
 
var list : List[Person] = _
var p1, p2, p3, p4 : Person = _
 
@Before def initializeListAndValues: Unit = {
  list = new List[Person]
  p1 = new Person("Jarda", 39)
  p2 = new Person("Sona", 37)
  p3 = new Person("Anna", 7)
  p4 = new Person("Ondra", 6)
}
 
@Test def tryFewAdditions = {
  assertTrue(list.add(p1))
  assertTrue(list.add(p2))
  assertTrue(list.add(p3))
  assertTrue(list.add(p4))
 
  assertEquals("Jarda was inserted first", "Jarda", list.get(0).name)
  assertEquals("Sona was inserted 2nd", 37, list.get(1).age)
  assertEquals("Anna was inserted 3rd", "Anna", list.get(2).name)
  assertEquals("Anna was inserted 4th", 6, list.get(3).age)
}
 

Please note that there is no cast, everything is typed correctly, thanks to Scala's flexible type system. Good achievement, Scala guys! I've enjoyed using the language, this time.

Implicit Wrapper

Of course some may argue that it is too restrictive that every class one wants to use in the effective List needs to inherit from the Listable trait. What should one do when the type has been written by somebody else and does not inherit from Listable? Can one put following class into a list?

Code from ListMixinTest.scala:

class Point(val x: Int, val y : Int);
 

In fact, it is more than easy thanks to Scala's implicit conversion methods. One can create a subtype that mixes in the Point as well as Listable and define an implicit method that converts from Point to ListablePoint. Then one can add instances of Point class directly to the list:

Code from ListMixinTest.scala:

class ListablePoint(x: Int, y: Int)
extends Point(x,y) with Listable[ListablePoint] {
  def this(r : Point) = this(r.x, r.y)
}
implicit def toList(p : Point) : ListablePoint = new ListablePoint(p)
 
@Test def useThePlainOldPointInList : Unit = {
  val list = new List[ListablePoint]
  list.add(new Point(10, 20))
  assertEquals("One element", 1, list.size)
  assertEquals("X is 10", 10, list.get(0).x)
  assertEquals("y is 20", 20, list.get(0).y)
}
 

This is a nice example showing how much the OOP technology progressed during last two decades. Thanks Scala for moving the OOP further.

Can this be done in Java?

Sort of, just it would be more verbose (as usual in Java). Instead the Listable trait one needs to define a Java interface with setters and getters for the next and prev properties. Everyone would then have to implement bodies of these methods again and again. With Scala trait one's gets that for free (and moreover the access is properly encapsulated). The List implementation would basically remain the same - the Java type mechanism is as powerful as Scala's in this respect. The implicit conversion would however not be possible - it would have to be explicit (as usual in Java).

Can this be done in C++?

One question remains: Can this be emulated in C++? Mixins are inherently present in C++ as the language supports multiple inheritance. Implicit conversions are indeed there. The only question is whether one can type this correctly without using casts. My early 90ties knowledge of C++ would suggest, one needs casts, but maybe the C++ changed and improved meanwhile. Anyone knows?

<comments/>

NetBeans IDE has support for C and C++ and when you want to support a language in an IDE you probably need knowledge of various corner cases. That is why I asked Vladimir, the project lead. Vladimir suggests to write the Person&People example like this:

class person {
private:
  person* next;
  person* prev;
  friend class people;
 
  int age;
  char* name;
 
public;
  person(int age, const char* name)
}
 
class people {
	add(const person& p);
	remove(const person& p);
}

In this case people class is the only one to access the prev/next field. So the encapsulation is kept. On the other hand, this is not generic support. One needs to write the code again and again.

An attempt to provide general support for such list was provided on the discussion page, but while being generic and efficient, it is not really type-safe.