Hi all,

I've been reading about multiple inheritance in the list archives, and from what I gather, it is only supported through a combination of "interfaces" and classes; one cannot inherit from two classes.

As far as I can tell, interface types do not allow implemented virtual methods -- only abstract ones.

Given these constraints, I'm wondering how to go about creating my types. Perhaps what I want to do is not possible, or perhaps I just don't know how? Here is the plain english description:

I'd like to create a "double-list" type, which maintains two parallel lists containing the same elements: one sorted, one unsorted. The reason to have both: sorted -> fast search; unsorted -> sequential navigation through the list while elements are being added.

I created a list_base, which contains variables and methods common to both unsorted and sorted lists (capacity, used_length, method increment_capacity_counter). The sorted_list has a "find" method, whereas the unsorted_list has a "next" method that increments a progress index.

The sorted and unsorted list types implement "add" differently, so the double-list would need to call both of the inherited "add" methods (or manually rewrite the same functionality)

I can't figure out how to do it legally.

For those who like code, here's a class description that uses illegal multiple class inheritance ;) There are a few notes below.

type
class_type = class
  end;
t_list_base = class (TObject)
  private
    f_capacity, f_used_length : longint;
    f_cs : TRTLCriticalSection;
    function inc_capacity : boolean; virtual;
    function grow_if_needed : boolean; virtual;	abstract;
    function internal_add (const class_in : class_type) : boolean;
        virtual; abstract;
  public
    property count : longint read f_used_length;
  end;
t_unsorted_list = class (t_list_frame)
  private
    f_ulist : array of class_type; // ulist = unsorted list
    f_next_index : longint;
    function get_pending_count : longint;  // used_length - next_index
    function grow_if_needed : boolean; override;
    function internal_add (const class_in : class_type) : boolean;
        override;
  public
    function next (out class_out : class_type) : boolean; virtual;
    property pending_count : longint read get_pending_count;
  end;
t_sorted_list = class (t_list_frame)
  private
    f_slist : array of class_type; // slist = sorted list
    function grow_if_needed : boolean; override;
    function internal_add (const class_in : class_type) : boolean;
        override;
  public
    function find (const target : longint) : bsearch_res_type; virtual;
  end;
t_double_list = class (t_unsorted_list, t_sorted_list)
  private
    function grow_if_needed : boolean; override;
    function internal_add (const class_in : class_type) : boolean;
        override;
  end;

small notes / questions:

class_type = class
  end;  // is this equivalent to TObject?

t_list_base = class (TObject) // is TPersistent or no ancestor better? regarding inc_capacity:
- if f_used_length<f_capacity then inc_capacity just returns false
- virtual so that other memory management algorithms can override it. regarding grow_if_needed:
- will setlength on the list, but list_base has no list! so abstract regarding internal_add:
- maybe it's best not to list this abstract here, as doing so sepersedes the possibility of using list_base for, e.g., a list of longints. Or perhaps this is a good place to use a variant type?

David Emerson wrote

I'd like to create a "double-list" type, which maintains two parallel lists containing the same elements: one sorted, one unsorted. The reason to have both: sorted -> fast search; unsorted -> sequential navigation through the list while elements are being added.

It can be achieved without need of multiple inheritance.

In your sample t_double_list should also inherit from t_sorted_list, rather than a t_unsorted_list or t_sorted_list.

t_double_list, can be implemented in the following way. As you can see, t_double_list even more flexible, than t_double_list with multiple-inheritance, because actual types of list1 and list2 can be controlled. For example, if you need to use list1 with sorting A, and list2 with sorting B... etc.

t_double_list = class (t_list_frame)
private
  flist1  : t_list_frame;
  flist2  : t_list_frame;
  function internal_add (const class_in : class_type) : boolean;
end;
....
constructor t_double_list.create;
begin
  flist1  := t_sorted_list.create;  // any type of list can be used here
  flist2  := t_unsorted_list.create;
end;
function t_double_list.internal_add (const class_in : class_type) : boolean;
begin
  flist1.add(class);
  flist2.add(class);
  Result := true;
end;

thanks,
dmitry

David Emerson wrote

lists containing the same elements: one sorted, one unsorted. The reason to have both: sorted -> fast search; unsorted -> sequential navigation through the list while elements are being added.

It's not as if combining those gives you the best of both worlds ... if the sorted list needs to keep its list sorted, having the sequential list won't make iterating faster ...

Micha

Having a sequential list makes iterating through the list *possible*, if items are being added at the same time that iteration is happening. I have a multi-threaded app here, so several threads are iterating through the sequential "unsorted" list, at the same time that other threads are attempting to add to the list.

Additions need to be checked for duplicate entries, thus necessitating a sorted list for fast lookup.

I suppose I could have specified that list elements won't be changed once they are in.

Thanks for the response, though
Cheers,
David

The idea behind my concept of t_double_list is that it is essentially one list which is both sorted and sequential at the same time.

One of the great things about OOP is that it helps reduce coding redundancy. That was one of the primary objectives in my design: code the stuff for unsorted lists once, code the stuff for sorted lists once, and code the common ancestor stuff once. I don't want to have to maintain three nearly-identical versions of find_via_binary_search.

The construct you've created here and named "t_double_list" is not a list at all; rather, it is a container which holds two lists which must be maintained independently of one another. Instead of simply inheriting the methods I need, I must completely rewrite them as methods of the container class. So this really isn't what I'm looking for.

Thanks for replying, though!

For now I've just inherited from t_unsorted_list, redundantly adding the sorted_list stuff. Not at all the elegant solution I'm looking for, but it seems to be the best that can be done.

Cheers,
David