Where would a sortedSet go in this UML diagram?

Question

I am self guiding myself through a Python Data Structures book and came across this problem for one of the exercises regarding the chapter regarding inheritance. I am very puzzled.

The problem: A sorted set behaves just like a set, but allows the user to visit its items in ascending order with a for loop, and supports a logarithmic search for an item. Draw a class diagram that shows where you would place a new class for sorted sets in the collection framework shown in the figure below:

I am confused on where a new class for a sorted set would go in this diagram. My gut tells me, it would be a be added as a third bag interface? For example LinkedBag, ArrayBag and a new SetBag point to bag interface and abstract bag, and SetSortedBag points to SetBag?

Is this on the right track? I find this question sorta odd.

Answer 1

Assuming that LinkedBag refers to the LinkedList data structure, then yes you are correct in that Set would be a third section, with SortedSet inheriting from it. However, I would not define it as an "interface".

Interfaces are a type of class which is generally used as a blueprint for inheriting classes to follow, and does not implement their own class functions. Instead, they declare functions which their derivative classes will implement. For additional information, Abstract Classes are similar, except that they can implement their class functions. Neither Interfaces nor Abstract classes can (usually) be initialized as an object. This becomes a lot more blurry in Python which uses the general "Python Abstract Base Classes" and doesn't do Interfaces directly, but can be mocked through the abstract classes. However, as a term for general programming, the distinctions between normal classes, interfaces, and abstract classes can be important, especially since interfaces and abstract classes (usually) are not/ can not be initialized as objects. The exact rules of inheritance regarding Interfaces and Abstract Classes can differ between languages, for example in Java you can't inherit from more than one abstract class, so I won't directly address it here.

Since a Set is a data structure on its own that can, and usually should, have functionality separate from a sorted set, you would not make the set an interface, but rather a normal class. You can still inherit from normal classes, which is what you would do with SortedSet inheriting from Set.

Answer 2

A sorted set according to the narrative is a set, but with some variations in some behavior:

A sorted set behaves just like a set, but allows the user to visit its items in ascending order with a for loop, and supports a logarithmic search for an item.

This means that SortedSet would inherit from Set, just like SortedArrayBag inherits from ArrayBag. Inheritance should by the way shown in UML with a big hollow array head (small arrows like in your diagram mean a navigable association, which has nothing to do with inheritance).

A set is however not a bag. A set contains an item at maximum once, whereas a bag may contain multiple times the same item. This could lead to a completely different interface (e.g. membership on an item is a boolean for a set, whereas it could be an integer for a bag). The safe approach would therefore be to insert an AbstractSet inheriting from AbstractCollection:

A shortcut could be to deal with the set like a bag, and return a count of 1 for any item belonging to the set, ignoring multiple inserts. This would not be compliant with the Liskov Substitution Principle, since it would not respect all the invariants and weaken post-conditions.

But if you'd nevertheless go this way, you should insert Set as extending AbstractBag, and SortedSet as a specialization of Set. In this case, your set (and sorted set) would also realise the BagInterface (even if it'd twist it). Shorn's answer analyses this situation very well.