Port the remaining miscellaneous tools

[Alpar Juttner]

The following files should be considered.

• lemon/dist_log.h
• lemon/refptr.h
• lemon/iterable_maps.h
• lemon/bits/debug_map.h
• lemon/matrix_maps.h
• lemon/polynomial.h
• lemon/concepts/matrix_maps.h
• lemon/map_iterator.h

[Peter Kovacs]

lemon/concept_check.h has already been ported.

[Balazs Dezso]

Patch for iterable maps

[Balazs Dezso]

The patch [7bda7860e0a8] contains the port of the iterable maps and new unit tests for them.

[Alpar Juttner]

Replying to deba:

The patch [7bda7860e0a8] contains the port of the iterable maps and new unit tests for them.

According to the doc IterableIntMap can store any integer value, but can only iterate through the keys belonging to the non-negative ones. It is true? That's the rational behind it?

[Peter Kovacs]

[71939d63ae77] contains small improvements for these classes (mainly in the doc).

[Peter Kovacs]

Replying to alpar:

According to the doc IterableIntMap can store any integer value, but can only iterate through the keys belonging to the non-negative ones. It is true? That's the rational behind it?

Yes, it is true. Probably the ease of implementation motivated this design. The items are laced in linked lists corresponding to the values. The "head pointers" of the lists are stored in a vector that is indexed by the value itself.

The structure could be modified to support iteration for all values by e.g. adding a separate vector for storing the first item of the lists for negative values.

[Balazs Dezso]

Replying to kpeter:

Replying to alpar:

According to the doc IterableIntMap can store any integer value, but can only iterate through the keys belonging to the non-negative ones. It is true? That's the rational behind it?

Yes, it is true. Probably the ease of implementation motivated this design. The items are laced in linked lists corresponding to the values. The "head pointers" of the lists are stored in a vector that is indexed by the value itself.

The structure could be modified to support iteration for all values by e.g. adding a separate vector for storing the first item of the lists for negative values.

I think the main reason is the simple implementation and efficiency, but it has one more reason. In my opinion, this class is intended to be used where each value is small non-negative integer. For example, when the map values are component identifiers, and the identifiers come from range [0..n-1]. Perhaps there are applications, where we want to store small negative values as well, but I think they are not so frequent.

[Alpar Juttner]

Replying to deba:

Replying to kpeter:

Replying to alpar:

According to the doc IterableIntMap can store any integer value, but can only iterate through the keys belonging to the non-negative ones. It is true? That's the rational behind it?

Yes, it is true. Probably the ease of implementation motivated this design. The items are laced in linked lists corresponding to the values. The "head pointers" of the lists are stored in a vector that is indexed by the value itself.

The structure could be modified to support iteration for all values by e.g. adding a separate vector for storing the first item of the lists for negative values.

I think the main reason is the simple implementation and efficiency, but it has one more reason. In my opinion, this class is intended to be used where each value is small non-negative integer. For example, when the map values are component identifiers, and the identifiers come from range [0..n-1]. Perhaps there are applications, where we want to store small negative values as well, but I think they are not so frequent.

Then why don't we say that this map stores non-negative integers? Is there any use-case for also storing negative values but never iterating over them?

[Peter Kovacs]

Replying to alpar:

Then why don't we say that this map stores non-negative integers? Is there any use-case for also storing negative values but never iterating over them?

I have never used this strucutre, but I could imagine such use cases, e.g. negative values (-1) mean something invalid/irrelevant. Then iterating on the keys with "invalid" values is probably not necessary.

[Alpar Juttner]

Iterable maps ([7bda7860e0a8] and [7bda7860e0a8]) has been merged to the main.