COIN-OR::LEMON - Graph Library

Opened 11 years ago

Last modified 9 years ago

#73 assigned task

Port the remaining miscellaneous tools

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

Description (last modified by Balazs Dezso)

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 Balazs Dezso 9 years ago.
Patch for iterable maps
73-iterable-71939d63ae77.patch (21.3 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 11 years ago by Alpar Juttner

Type: defecttask

comment:2 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:3 Changed 11 years ago by Peter Kovacs

lemon/concept_check.h has already been ported.

comment:4 Changed 10 years ago by Alpar Juttner

Status: newassigned

comment:5 Changed 10 years ago by Peter Kovacs

Description: modified (diff)

comment:6 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

Changed 9 years ago by Balazs Dezso

Attachment: 7bda7860e0a8.patch added

Patch for iterable maps

comment:7 Changed 9 years ago by Balazs Dezso

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

comment:8 in reply to:  7 ; Changed 9 years ago by 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?

Changed 9 years ago by Peter Kovacs

comment:9 Changed 9 years ago by Peter Kovacs

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

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

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

comment:12 in reply to:  11 ; Changed 9 years ago by 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?

comment:13 in reply to:  12 Changed 9 years ago by 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.

comment:14 Changed 9 years ago by Alpar Juttner

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

comment:15 Changed 9 years ago by Balazs Dezso

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