[Gambas-devel] Should we provide different implementations to the same abstract datatype?

[Tobias Boege]

On Thu, 24 Apr 2014, Beno?t Minisini wrote:
> Le 24/04/2014 13:45, Tobias Boege a ?crit :
> > Hi Benoit,
> >
> > I want to implement a Graph class for gb.data and I'm struggling with what
> > internal representation to use because depending on the application, one
> > data structure may perform badly and another one well. This may invert for
> > a different application.
> >
> > To have a well-performing Graph in their application, the programmer should
> > choose the internals themselves and I'm thinking that I can do the following
> > to support that:
> >
> >   - Create a non-creatable class Graph that provides a common interface
> >      - Create a GraphAdjMatrix class which Inherits Graph and overrides its
> >        methods and properties to be an adjacency matrix based implementation
> >      - Create a GraphAdjList class " to be an adjacency list based
> >        implementation
> >      - etc.
> >   - If the user cares, they can explicitly request, e.g., an adjacency
> >     matrix. Maybe there will be a Graph._call() static method that returns a
> >     default implementation's object for those that don't care.
> >   - Method signatures will only need to refer to the Graph class so that a
> >     non-expert user (not familiar with that inheritance tree) doesn't need to
> >     be confused. But still the correct methods are applied to the objects as
> >     Gambas uses virtual dispatching.
> >
> > [ For a more intuitive feeling, I can also make Graph creatable and do the
> >    same in _new() that I planned to do in _call()... right? ]
> >
> > Does that sound reasonable? If you don't have strong objections, I would
> > really like to do it that way. Maybe I can also introduce an abstract
> > SearchTree class and have AvlTree (the only search tree at present) inherit
> > from this class - because there it is the same principle but better
> > developed as there are plenty of search tree implementations with a common
> > set of operations.
> >
> > This way, there would be some analogon to the UserControl class of gb.qt4
> > for abstract datatypes, i.e. the user can also design Graph/SearchTree/...
> > implementations in Gambas and pass them equally to all the methods that
> > accept abstract Graph/SearchTree/... objects, i.e. methods that are agnostic
> > about the implementation.
> >
> > Regards,
> > Tobi
> >
> 
> AFAIK, there are a lot of different graph types. Maybe you cannot create 
> a common parent class for all of them. But in all cases, you should 
> provide the same interface to the user, at most as possible.
> 

Good point. I was only thinking about ordinary directed graphs in the Graph
class, not about weights or undirected stuff... (That's what you were
targetting, right?)

I could solve that by having the most powerful Graph (weighted and directed)
with a default weight and the option to have each inserted edge (directed)
also automatically inserted in the reverse direction, which would make the
Graph practically undirected... maybe.

For the other Graph types that Wikipedia lists, e.g. Multigraph, Hypergraph,
Quiver, distinct classes should be made (if anyone cares about them). But
for directed vs. undirected and weighted vs. unweighted, distinct classes
are painful.

> In other words, the user does not care if there is a common parent 
> class. But he will be not happy if he has to use a different interface 
> for each different Graph class.
> 
> As for using a common parent class, it's up to you. Of course it's better.
> 
> Another possibility is having one Graph class, and using a property to 
> define how to store the data. All the virtual dispatching is done inside 
> the component. For me, it may be a better idea (less classes to write, 
> document and learn, just one line of code to change if the user wants to 
> change its algorithm...). Same remark for SearchTree.
> 
> What do you think about that?
> 

Also possible. But if I integrate the four "ordinary" Graph types into the
Graph class AND add stuff to change the internal data layout, I fear that
the class just becomes too bulky with a dozen possible configurations of its
behaviour.

I admit that I would find it a bit strange to say:

  Dim hTree As New SearchTree(SearchTree.AvlTree) ' get me an AvlTree

or

  hTree.Type = SearchTree.RedBlackTree

instead of having the classes ready:

  Dim hTree As New AvlTree ' Inherits SearchTree

I'll start with the inheritance approach and see how far I get...

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk