COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 8 years ago

#73 assigned task

Port the remaining miscellaneous tools

Reported by: alpar Owned by: alpar
Priority: major Milestone:
Component: core Version:
Keywords: Cc:
Revision id:

Description (last modified by deba)

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

Attachments (2)

7bda7860e0a8.patch (33.9 KB) - added by deba 8 years ago.
Patch for iterable maps
73-iterable-71939d63ae77.patch (21.3 KB) - added by kpeter 8 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 9 years ago by alpar

  • Type changed from defect to task

comment:2 Changed 9 years ago by alpar

  • Milestone changed from LEMON 1.0 release to Post 1.0

comment:3 Changed 9 years ago by kpeter

lemon/concept_check.h has already been ported.

comment:4 Changed 9 years ago by alpar

  • Status changed from new to assigned

comment:5 Changed 9 years ago by kpeter

  • Description modified (diff)

comment:6 Changed 9 years ago by alpar

  • Milestone LEMON 1.1 release deleted

Changed 8 years ago by deba

Patch for iterable maps

comment:7 follow-up: Changed 8 years ago by deba

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

comment:8 in reply to: ↑ 7 ; follow-up: Changed 8 years ago by alpar

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?

Changed 8 years ago by kpeter

comment:9 Changed 8 years ago by kpeter

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

comment:10 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by 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.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 8 years ago by 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.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 8 years ago by alpar

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?

comment:13 in reply to: ↑ 12 Changed 8 years ago by kpeter

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.

comment:14 Changed 8 years ago by alpar

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

comment:15 Changed 8 years ago by deba

  • Description modified (diff)
Note: See TracTickets for help on using tickets.