Ordered table datastructure

Question

I have data structured in a table form

+------+------+------+------+
|      | Col1 | Col2 | Col3 |
+------+------+------+------+
| Row1 |    1 |    2 |    3 |
| Row2 |    5 |    5 |    6 |
| Row3 |    9 |    2 |    7 |
+------+------+------+------+

I'm looking for a data structure that allows the following:

• Fast Iteration of column and rows (get the values for the column or the rows. (It should not be more expensive to iterate in one direction than in the other)
• Fast adding and removing of entire rows and columns (again both operations should be equally fast and should be at most O(n) )
• Order based on insertion order and reorderable. Order would be calculated with some comparators and is usually depended on the data in the row or column, but not on any names or such
• Store data other than numbers (We have mixed data, but I plan to use a container class for the actual data anyways)

Additionally rows and columns will have metadata (name, color and stuff like that). All these operations happen often in our system. Currently we store the data row based and the columns have no reference to the data related to them. This makes deleting a column or iterating over its data very tedious.

The first thing that sprang to my mind is the Guava Table but that is not ordered and I'm not sure if it is easy to delete an entire row or column, although clearing the row or column map might do it.

Arrays as backing storage will not work because of adding and removing required. (Although I could predict how large the table will be and create new tables for the removing, but I don't like that solution, even if it could be hidden from the user)

I would be grateful for any ideas on how to implement such a data structure.

To clarify, I don't need a finished library that does this, but I'm looking for a data structure that would allow me do create this. I already know that I will be storing row and column meta-data in separate lists for example

Answer 1

Thank you all for your help and ideas. I've come to the conclusion that I will keep the current structure of the table consisting of a list of rows who each have a list of cells. While this makes it difficult to iterate over columns or deleting columns, our tables are usually quite small ( < 15 rows, <100 columns) and the main bottleneck of our current implementation is that the data is stored in strings instead of being typed (Double.parse can be quite expensive if you do it too often). While it would be very interesting to develop a data-structure that fulfils all of the requirements in my original question, the reality is that I can't spend that much time on working on this.

Answer 2

Guava Tables can certainly be ordered. ImmutableTable provides "reliable user-specified iteration order" and (from the Builder docs) "by default, the order in which cells are added to the builder determines the iteration ordering of all views in the returned table".

Or TreeBasedTable can be used if you need mutable a Table and want a RowSortedTable.

You could also implement your own LinkedHashBasedTable class pretty easily. Either with ForwardingTable and a LinkedHashSet to store your desired iteration order, or simply call Tables.newCustomTable() with a LinkedHashMap as the first argument (and the result of the Supplier, if needed).

---

Most Table implementations provide O(1) or O(n) (where n is the row/colum count) implementations for all the standard methods, and the methods that return views (like row() and colum()) are directly backed by the original Table, so they're similarly efficient.

If you're really concerned that all the available Table implementations (including .newCustomTable()) are too slow, you should benchmark this. They're more than efficient enough for all normal uses, and without proof that Tables are your bottleneck creating your own data structure is a clear instance of premature optimization.