Class DS_MULTIARRAYED_HASH_TABLE

indexing

description:

    "Hash tables implemented with multi-arrays. %
    %Keys are hashed using hash_code from HASHABLE."

library:    "Gobo Eiffel Structure Library"
author:     "Eric Bezault <ericb@gobosoft.com>"
copyright:  "Copyright (c) 2001, Eric Bezault and others"
license:    "Eiffel Forum Freeware License v1 (see forum.txt)"

class interface

DS_MULTIARRAYED_SPARSE_TABLE [G, K -> HASHABLE]

inherit

DS_MULTIARRAYED_SPARSE_TABLE [G, K]
    DS_SPARSE_TABLE [G, K]
        DS_TABLE [G, K]
            DS_CONTAINER [G]
        DS_BILINEAR [G]
            DS_LINEAR [G]
                DS_TRAVERSABLE [G]
                    DS_CONTAINER [G]
                DS_SEARCHABLE [G]
                    DS_CONTAINER [G]
        DS_RESIZABLE [G]
            DS_CONTAINER [G]

creation

make (n: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of default_chunk_size.
        -- Use `=' as comparison criterion for items.
        -- Use equal as comparison criterion for keys.
        -- (From DS_SPARSE_TABLE.)
    require
        positive_n: n >= 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = default_chunk_size
        before: before

make_equal (n: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of default_chunk_size.
        -- Use equal as comparison criterion for items.
        -- Use equal as comparison criterion for keys.
        -- (From DS_SPARSE_TABLE.)
    require
        positive_n: n >= 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = default_chunk_size
        before: before

make_with_chunk_size (n: INTEGER; a_chunk_size: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of a_chunk_size.
        -- Use `=' as comparison criterion for items.
        -- Use equal as comparison criterion for keys.
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)
    require
        positive_n: n >= 0
        a_chunk_size_positive: a_chunk_size > 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = a_chunk_size
        before: before

make_equal_with_chunk_size (n: INTEGER; a_chunk_size: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of a_chunk_size.
        -- Use equal as comparison criterion for items.
        -- Use equal as comparison criterion for keys.
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)
    require
        positive_n: n >= 0
        a_chunk_size_positive: a_chunk_size > 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = a_chunk_size
        before: before

make_default
        -- Create an empty table and allocate memory space
        -- for at least default_capacity items.  Array
        -- chunks will have a size of default_chunk_size.
        -- Use `=' as comparison criterion for items.
        -- Use equal as comparison criterion for keys.
        -- (From DS_CONTAINER.)
    ensure
        empty: is_empty
        capacity_set: capacity = default_capacity
        chunk_size_set: chunk_size = default_chunk_size
        before: before

make_map (n: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of default_chunk_size.
        -- Use `=' as comparison criterion for items.
        -- Use `=' as comparison criterion for keys.
        -- (From DS_SPARSE_TABLE.)
    require
        positive_n: n >= 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = default_chunk_size
        before: before

make_map_equal (n: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of default_chunk_size.
        -- Use equal as comparison criterion for items.
        -- Use `=' as comparison criterion for keys.
        -- (From DS_SPARSE_TABLE.)
    require
        positive_n: n >= 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = default_chunk_size
        before: before

make_map_with_chunk_size (n: INTEGER; a_chunk_size: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of a_chunk_size.
        -- Use `=' as comparison criterion for items.
        -- Use `=' as comparison criterion for keys.
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)
    require
        positive_n: n >= 0
        a_chunk_size_positive: a_chunk_size > 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = a_chunk_size
        before: before

make_map_equal_with_chunk_size (n: INTEGER; a_chunk_size: INTEGER)
        -- Create an empty table and allocate memory space
        -- for at least n items. Array chunks will have
        -- a size of a_chunk_size.
        -- Use equal as comparison criterion for items.
        -- Use `=' as comparison criterion for keys.
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)
    require
        positive_n: n >= 0
        a_chunk_size_positive: a_chunk_size > 0
    ensure
        empty: is_empty
        capacity_set: capacity = n
        chunk_size_set: chunk_size = a_chunk_size
        before: before

make_map_default
        -- Create an empty table and allocate memory space
        -- for at least default_capacity items.  Array
        -- chunks will have a size of default_chunk_size.
        -- Use `=' as comparison criterion for items.
        -- Use `=' as comparison criterion for keys.
        -- (From DS_SPARSE_TABLE.)
    ensure
        empty: is_empty
        capacity_set: capacity = default_capacity
        chunk_size_set: chunk_size = default_chunk_size
        before: before

make_with_equality_testers (n: INTEGER;
    an_item_tester: like equality_tester;
    a_key_tester: like key_equality_tester)
        -- Create an empty table and allocate memory space for at
        -- least n items. Array chunks will have a size of
        -- default_chunk_size.
        -- Use an_item_tester as comparison criterion for items.
        -- Use a_key_tester as comparison criterion for keys.
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)
    require
        positive_n: n >= 0
    ensure
        empty: is_empty
        capacity_set: capacity = default_capacity
        chunk_size_set: chunk_size = default_chunk_size
        before: before
        equality_tester_set: equality_tester = an_item_tester
        key_equality_tester_set: key_equality_tester = a_key_tester

make_with_chunk_size_and_equality_testers (n: INTEGER;
    a_chunk_size: INTEGER; an_item_tester: like equality_tester;
    a_key_tester: like key_equality_tester)
        -- Create an empty table and allocate memory space for at
        -- least n items. Array chunks will have a size of a_chunk_size.
        -- Use an_item_tester as comparison criterion for items.
        -- Use a_key_tester as comparison criterion for keys.
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)
    require
        positive_n: n >= 0
    ensure
        empty: is_empty
        capacity_set: capacity = default_capacity
        chunk_size_set: chunk_size = a_chunk_size
        before: before
        equality_tester_set: equality_tester = an_item_tester
        key_equality_tester_set: key_equality_tester = a_key_tester

feature -- Access

infix "@", item (k: K): G
        -- Item associated with k
        -- (From DS_TABLE.)
    require
        valid_entry: has (k)

key (k: K): K
        -- Key associated with k
        -- (From DS_SPARSE_TABLE.)
    require
        has_k: has (k)

found_item: G
        -- Item found by last call to search
        -- (From DS_SPARSE_TABLE.)
    require
        item_found: found

found_key: K
        -- Key of item found by last call to search
        -- (From DS_SPARSE_TABLE.)
    require
        key_found: found

item_for_iteration: G
        -- Item at internal cursor position
        -- (From DS_TRAVERSABLE.)
    require
        not_off: not off

key_for_iteration: K
        -- Key at internal cursor position
        -- (From DS_SPARSE_TABLE.)
    require
        not_off: not off

first: G
        -- First item in table
        -- (From DS_LINEAR.)
    require
        not_empty: not is_empty
    ensure
        has_first: has_item (Result)

last: G
        -- Last item in table
        -- (From DS_BILINEAR.)
    require
        not_empty: not is_empty
    ensure
        has_last: has_item (Result)

new_cursor: DS_MULTIARRAYED_HASH_TABLE_CURSOR [G, K]
        -- New external cursor for traversal
        -- (From DS_TRAVERSABLE.)
    ensure
        cursor_not_void: Result /= Void
        valid_cursor: valid_cursor (Result)

equality_tester: DS_EQUALITY_TESTER [G]
        -- Equality tester;
        -- A void equality tester means that `='
        -- will be used as comparison criterion.
        -- (From DS_SEARCHABLE.)

key_equality_tester: DS_EQUALITY_TESTER [K]
        -- Equality tester for keys;
        -- A void equality tester means that `='
        -- will be used as comparison criterion.
        -- (From DS_SPARSE_TABLE.)

feature -- Measurement

count: INTEGER
        -- Number of items in table
        -- (From DS_CONTAINER.)

capacity: INTEGER
        -- Maximum number of items in table
        -- (From DS_RESIZABLE.)

default_capacity: INTEGER
        -- Initial capacity in make_default
        -- (Default value: 10)
        -- (From DS_RESIZABLE.)
    ensure
        default_capacity_positive: Result >= 0

chunk_size: INTEGER
        -- Size of array chunks
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)

default_chunk_size: INTEGER
        -- Default value for chunk_size
        -- (Default value: 30000)
        -- (From DS_MULTIARRAYED_SPARSE_TABLE.)
    ensure
        default_chunk_size_positive: Result > 0

occurrences (v: G): INTEGER
        -- Number of times v appears in table
        -- (Use equality_tester's comparison criterion
        -- if not void, use `=' criterion otherwise.)
        -- (From DS_SEARCHABLE.)
    ensure
        positive: Result >= 0
        has: has_item (v) implies Result >= 1

feature -- Status report

has (k: K): BOOLEAN
        -- Is there an item associated with k?
        -- (From in DS_TABLE.)
    ensure
        valid_key: Result implies valid_key (k)

has_item (v: G): BOOLEAN
        -- Does table include v?
        -- (Use equality_tester's comparison criterion
        -- if not void, use `=' criterion otherwise.)
        -- (From has in DS_SEARCHABLE.)
    ensure
        not_empty: Result implies not is_empty

found: BOOLEAN
        -- Did last call to search succeed?
        -- (From DS_SPARSE_TABLE.)

is_empty: BOOLEAN
        -- Is table empty?
        -- (From DS_CONTAINER.)

is_full: BOOLEAN
        -- Is table full?
        -- (From DS_RESIZABLE.)

is_first: BOOLEAN
        -- Is internal cursor on first item?
        -- (From DS_LINEAR.)
    ensure
        not_empty: Result implies not is_empty
        not_off: Result implies not off