I am trying to implement a persistent Stack
data structure. I want to implement this as an algebraic data type, so it has two concrete subtypes: empty and non empty:
abstract class Stack<T> {
factory Stack.empty() => const _EmptyStack._();
T get data;
Stack<T> get bottom;
bool get isEmpty;
Stack<T> put(T item) => new _StackImpl(item, this);
}
class _StackImpl<T> extends Stack<T> {
final T _data;
final Stack<T> _bottom;
_StackImpl(T this._data, Stack<T> this._bottom);
T get data => _data;
Stack<T> get bottom => _bottom;
bool get isEmpty => false;
}
class _EmptyStack<T> extends Stack<T> {
const _EmptyStack._();
T get data => throw new CollectionIsEmpty();
Stack<T> get bottom => throw new CollectionIsEmpty();
bool get isEmpty => true;
}
This code raises two errors in concrete implementations:
[error] The class 'Stack' does not have a default generative constructor
I found a sample code which seem to address this problem here, so I've fixed it by putting a parameterless constructor in Stack<T>
class:
abstract class Stack<T> {
Stack();
// ...
but now this causes problem with _EmptyStack<T>
constructor, which is constant:
Constant constructor cannot call non-constant super constructor of 'Stack<T>'
Additionally the added Stack()
constructor prevents from using the class as a mixin.
These restrictions seem to enforce on the class author to think about how the class would be extended. The way of extending List
class from dart:collection
package seem to confirm this conclusion - there is an entire separate class to use for extension, I can't directly extend the List
class itself.
My question is more general then the problem described above: how can I write a class so that it can be flexible enough to extend? That includes allowing the use of features like:
- factory constructors in super class
- normal constructors in sub class
const
constructors in sub class- be used as a mixin
While I understand that the use as mixin might be impossible or even unwanted, other points are still valid. Most importantly the question stands: why can't I extend
a class with a factory constructor? This is a behavior unlike any other OO language I'm familiar with.
Also related questions:
- Extending a class with only one factory constructor
- Extending the Exception class in Dart
EDIT: Thanks to Günter Zöchbauer answer I've improved the code, so now it is fully operational (see below). The most important question that I am now left with is: why factory constructor breaks the ability to extend the class? And how to get around it (aside from using the base class as interface)? A simpler example to make the point:
class Base {
}
class _Sub extends Base {
int someValue;
_Sub(int this.someValue);
}
Everything is fine with this code. But let's say I get back to my Base
class in time and want to add factory method:
class Base {
factory Base.empty() => new _Sub(0);
}
Now each class which extends Base
is broken because of unresolved implicit call to super constructor
. What do I do then?
Corrected code from original question for reference:
abstract class Stack<T> {
const Stack._();
factory Stack.empty() => const _EmptyStack._();
T get data;
Stack<T> get bottom;
bool get isEmpty;
Stack<T> put(T item) => new _StackImpl(item, this);
}
class _StackImpl<T> extends Stack<T> {
final T _data;
final Stack<T> _bottom;
_StackImpl(T this._data, Stack<T> this._bottom) : super._();
T get data => _data;
Stack<T> get bottom => _bottom;
bool get isEmpty => false;
}
class _EmptyStack<T> extends Stack<T> {
const _EmptyStack._() : super._();
T get data => throw new CollectionIsEmpty();
Stack<T> get bottom => throw new CollectionIsEmpty();
bool get isEmpty => true;
}
void main(){
group('stack', (){
test('empty stack', (){
var emptyStack = new Stack.empty();
expect(emptyStack.isEmpty, isTrue);
expect(() => emptyStack.data, throwsA(new isInstanceOf<CollectionIsEmpty>()));
expect(() => emptyStack.bottom, throwsA(new isInstanceOf<CollectionIsEmpty>()));
var emptyStack2 = new Stack.empty();
expect(emptyStack == emptyStack2, isTrue);
});
test('adding to stack', (){
var stack = new Stack<String>.empty().put("a").put("b").put("c");
expect(stack.data, equals('c'));
expect(stack.bottom.data, equals('b'));
expect(stack.bottom.bottom.data, equals('a'));
});
});
}