4.0

4.0 | 2 ratings Rate this file 12 Downloads (last 30 days) File Size: 32.3 KB File ID: #25024
image thumbnail

Data Structure: A Cell Array List Container

by

 

14 Aug 2009 (Updated )

Provides a useful 1D container for storing an ordered heterogeneous set of elements

| Watch this File

File Information
Description

Intent: Provides a useful 1D data structure (or container) for storing an ordered heterogeneous set of elements.

Motivation: MATLAB® R2009a provides the "containers.Map" data structure for storing an unordered heterogeneous set of elements - the Map ADT is a container that is indexed with a "key" of any data type. A List ADT is a data container that is indexed by integers. The benefit in using a List ADT opposed to a native MATLAB cell array is the List ADT hides the complexity in implementation of the operations you would perform to insert and remove elements in/from arbitrary positions, for example.

Implementation: Class 'CellArrayList' is a concrete realisation of the the List ADT which uses a "native" MATLAB cell array as its storage mechanism.

The source files are contained in the zip file 'CellArrayList.zip'. Refer to the comments in 'List.m' and 'CellArrayList.m' for full details on the motivation and implementation. The script 'testCellArrayList.m' demonstrates the use of 'CellArrayList.m'. Further, a corresponding UML class diagram is illustrated in 'CellArrayList_UML_Diagram.pdf'.
   
Written by Bobby Nedelkovski
MathWorks Australia
Copyright 2009-2010, The MathWorks, Inc.

Acknowledgements

This file inspired Design Pattern: Iterator (Behavioural).

MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (6)
11 Apr 2010 Bobby Nedelkovski

Thank you for your feedback and suggestions Joao.

I appreciate you pointing out the bug with the add() method in class CellArrayList. The bug (infinite while-loop) occurs when capacity = numElts and remove() is called numElts consecutive times to reduce capacity to 0. Subsequently, if you call add(), the while-loop used to re-allocate memory for the list cell array container won’t exit!

I have since fixed this issue and have submitted an update which will be published on the File Exchange soon.

Your suggestions of overloading critical MATLAB system methods such as ‘subsref’ and ‘subsasgn’ for the short-term benefits of element/property replacement is dangerous. Experienced MATLAB programmers will know that natural index notation is used to index into arrays of data types e.g. array of structs or array of cell arrays or array of char arrays or in this case, array of CellArrayLists!

Incidentally, I have just uncovered another bug with reference to how I’ve implemented all my methods with respect to the creation of arrays of CellArrayLists – i.e. myList = CellArrayList(); myList(2) = CellArrayList(); – and the way in which I’ve overloaded system methods ‘isempty’, ‘length’ and ‘display’!

This just goes to show that you need to be extremely cautious when deciding to overload MATLAB system methods! However, I like the idea of having a specialised ‘replace’ method which will effectively execute the ‘remove’ method followed by the ‘add’ method. In this way, you can easily replace elements in the list yet according to OOP practice, it is still perfectly acceptable for programmers to retrieve ADT elements and simply modify properties (this is all you need to do for objects of reference behaviour) and insert them back into the list (for objects of copy behaviour).

Joao, please feel free to contribute to the development of the ‘replace’ method. I can review your code if you send it to me by email which you can find off my File Exchange profile page (just click on the hyperlink ‘Bobby Nedelkovski’ on this page).

05 Apr 2010 Joao Henriques

Bug found: if you remove all elements, capacity will be 0. It will then, when adding a new element, enter an infinite loop (!) trying to multiply the capacity by 2 until it reaches the desired number of elements, which will never happen. Since the simple behavior of "adding some elements, removing them, adding some more" was never tested, I'm starting to get the impression that this class never got much use by the author... =|

01 Apr 2010 Joao Henriques

Ah, one important feature is missing: "set". You can "get" elements, but not write to them! Removing and then adding incurs unnecessary overhead. It would also be nice if you overloaded standard methods such as "subsref" and "subsasgn" so we can use index notation instead of get/set methods.

31 Mar 2010 Joao Henriques

Pretty cool! Now if there was a realization of the abstract class as a C-implemented linked list...

20 Sep 2009 Bobby Nedelkovski

Thank you for your feedback Kun-Chul.

To provide clarification to the comment "good implementation for the oo design principle: polymorphism!!":

The CellArrayList implementation of the List ADT provides 'polymorphism' at the element level as I've indicated in File Exchange item #25024 by stating that CellArrayList is a storage container for a *heterogeneous* set of elements.

On the other hand, polymorphism at the list object creation level can't be generally enforced since MATLAB is loosly typed. Ideally, to conform with good software engineering practice, it would be beneficial to declare an identifier using an interface/abstract class so you just need to change the instantiating class if you simply want to switch from one implementation of List to another (i.e. you cannot perform "List myList = CellArrayList();" so then you would simply need to modify this line to use another implementation "List myList = AnotherImplList();"). So in this case, polymorphism is not apparent in MATLAB OOP.

On the alternative implementation of method 'locationsOf' (i.e. "locs = find(cellfun('isclass',obj.list,class(elt)));"), I have asserted in the comments for 'locationsOf' in abstract class 'List.m' that it should return the locations of all occurances of a single element in the list; speed shouldn't be necessarily the issue here. Hence why I use a strict equality test in "locs = find(cellfun(@(c)isequal(c,elt),obj.list));" *not* simply checking the element type. For example, if I define a list of the sort "x = [1,2,{3,4;5,6},{7,8;9,10},11]" and test x.locationsOf(2), the 'isequal' implementations yields the correct result of 2. The 'isclass' implementation will yield the relative locations of elements 1,2 and 11 given their data type matches the data type of the input argument. This is then contrary to the "contractual agreement" defined in the comments for 'locationsOf' in the abstract class 'List.m'. Sure, though you are welcome to have specialised methods in your custom subclasses of the List ADT - for example, perhaps an 'isclass' operation could be be encapsulated in a method called 'classTypeLocationsOf'.

Finally, to comment on "I hope Mathworks to develop cell array vectorization for matlab oop...", the idea of this CellArrayList realisation of the List ADT and OOP in general is to hide the low-level detail in implementation of certain functionality (like performing "find(cellarray..." or even for that matter "find(listObj==obj)" as suggested) since the user of CellArrayList only needs to know how to use 'locationsOf'. So the onus is on the developer to create their own implementations of specific class methods using base MATLAB functionality; therefore OOP shouldn't be seen as a replacement for or thought of as superseding base MATLAB functionality since functions like 'cellfun' still have their place.

18 Sep 2009 Kun-Chul

good implementation for the oo design principle: polymorphism!!

I also used cell array for the objects container ( list container)
for the objects from different classes (but, those different classes inhereted from a same super class)

cell list class is more useful and powerful for the object list container.

however, try this code for the 'locationOf' method (much faster):
locs = find(cellfun('isclass',obj.list,class(elt))
, since cellfun is slow when suing function handle
(but, know the limitation of the code above:
if obj.list contains the object from a same class, then 'find' function returns matching index array.

I hope Mathworks to develop cell array vectorization for matlab oop

for example, objList is cell array contain

find(objList==obj) %this function does not support for cell array

while find(objArray==obj) is supported when objArray is array container of the object from a same class.

Updates
02 Sep 2009

Minor fix in comments of 'testCellArrayList.m'. Removed abstract declaration 'list' from abstract class 'List' as this presumes a List ADT is implemented using a flat array-like data structure. UML Diagram has been updated to reflect the change.

02 Sep 2009

Minor fix in comments of 'testCellArrayList.m'. Removed abstract declaration 'list' from abstract class 'List' as this presumes a List ADT is implemented using a flat array-like data structure. UML Diagram has been updated to reflect the change.

05 Oct 2009

Property 'numElts' changed to concrete protected in abstract class List - conforms with R2009b OOP. Updated UML diagram to reflect this change. Bug fix with remove() method in CellArrayList.

06 Apr 2010

Bug fix (much thanks to João Henriques) to avoid infinite while-loop in add() method when capacity reaches 0. Added constant property INITIAL_CAPACITY due to bug fix. UML Diagram has been updated to reflect the change.

19 Jul 2010

Bug fix to allow creation of N-D arrays of CellArrayLists - see my comment under 'Comments and Ratings' on '11 Apr 2010'. All methods including overloaded system functions 'isempty', 'length' and 'display' have been updated in class CellArrayList.

Contact us