Sparse array using hybrid of SPECIAL and HASH_TABLE

[Finnian Reilly]

Sparse array using hybrid of SPECIAL and HASH_TABLE

The attached class EL_SPARSE_ARRAY_TABLE [G, K -> HASHABLE] demonstrates an abstract implementation of HASH_TABLE that dynamically adjusts itself to being an array lookup if the range of keys converted to an integer, allows a memory saving over a hash table implementation. It is designed for expanded numeric types that can be converted to an array index, i.e. an INTEGER_32 value. For not too sparsely spaced integer keys this allows both a memory saving and a performance boost.

The class also demonstrates copying of unexported attributes via a reflection mechanism.

It is useful for implementing enumeration type classes or error code lookup tables.

To use the class you only have to implement the function

   as_integer (a_key: K): INTEGER

It is designed to be a read-only table and is initialised from another table (you can't add new items). The attributes of the other table are copied into the EL_SPARSE_ARRAY_TABLE object if the equivalent array consumes more memory.

It passes the following test set:

   test_sparse_array_table
      -- HASH_TABLE_TEST_SET.test_sparse_array_table
      local
         sparse_table: COMPUTED_INTEGER_64_TABLE; format: EL_FORMAT_INTEGER
         source_table: EL_HASH_TABLE [INTEGER_64, INTEGER_16]; square: INTEGER_64
         n, multiplier: INTEGER_16
      do
         create format.make_width (1)
         across << 1 , 10 >> as step_size loop
            multiplier := step_size.item.to_integer_16
            create source_table.make (50)
            across -25 |..| 25 as list loop
               n := list.item.to_integer_16 * multiplier
               square := n.to_integer_64 * n.to_integer_64
               source_table.extend (square, n)
            end
            create sparse_table.make (source_table)
            across -25 |..| 25 as list loop
               n := list.item.to_integer_16 * multiplier
               assert ("same spelling", source_table [n] = sparse_table [n])
            end
            assert ("not array indexed", multiplier > 1 implies not sparse_table.is_array_indexed)
         end

[Finnian Reilly]

Forgot to attach it. Here it is.