Repository: AlexandreDecan/portion

Issue:
Add capability for combine() to merge an arbitrary number of IntervalDicts
It would be convenient if the `combine()` method could work with more than two `IntervalDict` objects at a time.  I know that I can chain `combine()` methods together to get the same result.  But, that means that I have to write more than one `how` function.  It would be conceptually simpler, easier to read and less error prone to have a single `how` function that accepts more than two arguments, and only call `combine()` once.

Hints from issue comments:
@AlexandreDecan: Hello, 

I agree this would be convenient, but if we do that for `.combine`, we should do that for all other operations (including those on interval instances) for consistency. That said, and it relates to #33 and #62, the idiomatic way for doing so is to rely on `reduce`.
@marcsarrel: Hi,

Thank you for the reply.  Unfortunately, `reduce` doesn't help in this case, unlike with other operations like `union` in #33.  The reason is that I have two different `how` functions.  Here are a few lines from my current code:

```
how_A = lambda x, y: something...
how_B = lambda x, y: something else...

result = int_dict_X.combine(int_dict_Y, how=how_A).combine(int_dict_Z, how=how_B)
```@AlexandreDecan: Oh I think I misunderstood the first comment. I see indeed some benefits in having this, but how to deal with keys that are missing in some dict? @AlexandreDecan: So, correct me if I'm wrong: my understanding of the initial comment is that you would like to have a `.combine` function accepting multiple `IntervalDict` instances and a *single* `how` function. This `how` function accepts as many parameters as the number of `IntervalDict` instances provided, plus the one on which the method is called. Right? 

If my understanding is correct, then the question I had in my previous comment holds: what do we do for keys that are not in some intervals? We have several options: 
(1) Only keys (i.e., overlapping intervals) are considered. This is different from the `combine` method we currently have, since it also takes into account non-overlapping intervals (their values are kept as-is); 
(2) We extend the current behaviour of `combine` by only considering keys that are in the "left-most" dict (i.e., the one on which `combine` is applied). But I don't see why we should do that; 
(3) We call the `how` functions with a variable number of arguments, depending on how many `IntervalDict` instances have an overlap on the keys (but this behaviour does not align with the existing `combine` method);
(4) We call the `how` functions with a fixed number of arguments, providing a special value (`None`? But `None` is not so special) for `IntervalDict` instances that do no overlap the current key (again, this is different from what we currently have for `combine` with 2 dicts); 
(5) We define a new function, parallel to `combine`, that only supports an "inner" join on multiple `IntervalDict`.

The other question I've in mind is whether we can write `combine` for multiple instances faster than chaining them. If we can, then definitely I think something should be added to portion to support this use-case. If we can't, then I see little value in adding this to portion, except the syntactic sugar it may provide (and I'm not strongly against this). 
@marcsarrel: > So, correct me if I'm wrong: my understanding of the initial comment is that you would like to have a `.combine` function accepting multiple `IntervalDict` instances and a single `how` function. This `how` function accepts as many parameters as the number of `IntervalDict` instances provided, plus the one on which the method is called. Right?

Yes, that is correct.

> (1) Only keys (i.e., overlapping intervals) are considered. This is different from the `combine` method we currently have, since it also takes into account non-overlapping intervals (their values are kept as-is);

This is less desirable.  It's roughly equivalent to doing an inner join.

>(2) We extend the current behaviour of `combine` by only considering keys that are in the "left-most" dict (i.e., the one on which `combine` is applied). But I don't see why we should do that;

Agree -- not so desirable.

>(3) We call the `how` functions with a variable number of arguments, depending on how many `IntervalDict` instances have an overlap on the keys (but this behaviour does not align with the existing `combine` method);

Agree -- not so desirable.

>(4) We call the `how` functions with a fixed number of arguments, providing a special value (`None`? But `None` is not so special) for `IntervalDict` instances that do no overlap the current key (again, this is different from what we currently have for `combine` with 2 dicts);

This is the most appealing, but I agree that `None` is not so special.  There is a large risk that someone will use `None` as a value in their `IntervalDict`.

**An alternative might be to pass _two_ values to `how` for each interval `IntervalDict`.  The first value would be the value from the `IntervalDict` for the current segment of the domain.  The second value would be a `bool` flag to indicate if the key is defined for the current segment of the domain.  Suggest using a `@dataclass(kw_only=True)` to pair the value and the flag.  This `@dataclass` would help with static type checking when users write their `how` functions**

>(5) We define a new function, parallel to `combine`, that only supports an "inner" join on multiple `IntervalDict`.

I think this is the same as (1), and not desirable.
@marcsarrel: Another option would be to make a `@dataclass(kw_only=True)` with a single property named `value`.  That is, omit the `valid` flag property.  If there is no value defined in the current segment of the domain, leave the `value` property undefined.  The user can then test for the presence of the `value` property and decide what to do.@AlexandreDecan: I don't really like this solution as this implies one cannot use "traditional" functions for "how" and would have to wrap them. At the same time, I've no better alternative... I need to think about that... Perhaps an in-between solution would be a "gather" function taking multiple dict, behaving somewhat like get, and doing an inner join to provide values as a tuple? This doesn't solve the case of this issue, though... @marcsarrel: Ok, I understand.  Please let me know what you decide.

However, even with my current solution of chaining two `combine` methods together as shown [above](https://github.com/AlexandreDecan/portion/issues/95#issuecomment-2347135086), I do not have full control of the `result` `IntervalDict`.

For those portions of the merged domain where not all of the input `IntervalDicts` are defined, I must accept what the `combine` method returns because it won't call my `how` function.  I can have some control by re-ordering the `IntervalDict`s in the chain of `combine` methods.  But, I doubt that would be a general solution.

Maybe you could also provide a generic wrapper function that users could call.@marcsarrel: For option (4) above, maybe you could steal this idea to create an `undefined` value in the Portion library.

https://pypi.org/project/undefined

In effect, you make your own special value for `Undefined` that lives in the `portion` namespace.  Therefore, it is not a big restriction to say that users may not make it a value in their `IntervalDict`s.  You can give it whatever other properties you want with `__str__()`, `__repr__()`, etc., assuming it's a singleton object.@AlexandreDecan: Thanks, that's what I had in mind yesterday. Basically, either we put in the doctstring that `missing_value` (name to be defined) can be passed to set the value that will be provided to `how` if a key is missing (we can use `**kwargs` to detect whether it is set or not, so it won't clash with `None`), or we can use a sentinel value for this sole purpose (as is made above in `undefined`). 

That said, I still need to think how to combine multiple dicts efficiently at once. That won't be easy. In the meantime, what I can do is to add this `missing_value` parameter to `combine` so that `how` will be called even when some keys are missing (hence it will be easier for you to chain `combine`).

I'll see if I can find some time to work on this. This shouldn't be hard to implement, since we mostly need to iterate on all key/value of the left dict and right dict separately and call the how function appropriately. 
@AlexandreDecan: Could you please have a look at #96 ? It doesn't solve the current issue, but is an interesting, I think, step towards making it easier to chain calls to `.combine` to gather values from multiple `IntervalDict`. I think that, based on this change, one would be able to create a recipe for a `.combine` method accepting more than 2 dicts and a `how` function accepting `n` parameters. First step would be to collect all values from all dicts using appropriate `how` functions in chained calls to `combine`, then second step would be to apply/map the n-ary `how` function on the resulting `IntervalDict`. This won't be efficient, but it can be very convenient. @AlexandreDecan: Hello, 

The following recipe can be used to combine multiple IntervalDict instances. The `how` function is called with a variable number of parameters. The main steps are: 
1. Create an IntervalDict to initialize the whole domain with a tuple; 
2. Use an accumulator function to add items to tuples, one by one; 
3. Chain `.combine` calls to accumulate parameters from input IntervalDict; 
4. Do a kind of "map" on the resulting IntervalDict to call the `how` function on these parameters;
5. During this map, exclude empty tuples (they correspond to ranges on the domain where there is no value in the given IntervalDict instances).

```python
def combine_all(dicts, how):
    d = P.IntervalDict([(P.open(-P.inf, P.inf), tuple())])
    acc = lambda t, v: (*t, v)

    for o in dicts:
        d = d.combine(o, acc)

    r = []
    for i, v in d.items():
        if len(v) > 0:
            r.append((i, how(*v)))

    return P.IntervalDict(r)
```

Applied on the following dicts, as an example: 

```python
d1 = P.IntervalDict([(P.closed(1, 3) | P.closed(5, 7), 1)])
d2 = P.IntervalDict([(P.closed(2, 4) | P.closed(6, 8), 2)])
d3 = P.IntervalDict([(P.closed(3, 5), 4)])

print(combine_all([d1, d2, d3], lambda *x: sum(x)))
```

... outputs `{[1,2) | (5,6): 1, [2,3) | [6,7]: 3, [3]: 7, (3,4]: 6, (4,5): 4, [5]: 5, (7,8]: 2}`.

It is quite easy to transform this to an "inner join" (instead of an "outer" one) by changing `if len(v) > 0:` to `if len(v) == len(dicts)`. It is also quite easy to integrate the new `missing` parameter of `combine`, (1) by adding it to the calls to `combine` obviously and (2) by changing `if len(v) > 0` to check that any one item in the tuple is not `missing` (i.e., if all entries are `missing`, drop it). 

I'll add a reference to this snippet in the documentation, but I do not plan to integrate it as part of the API since it is really inefficient and a bit of a "hack" :-) @marcsarrel: Thank you.  I will give it a try...@AlexandreDecan: Keep me informed so I can release v2.1.5 or make changes before it's release. @marcsarrel: I thought you weren't going to release `combine_all()` as part of Portion?@AlexandreDecan: I won't, but the "missing" parameter for "combine" deserves a release. It is very convenient for this recipe when intervals do not share a same domain. 

Solution patch:
diff --git a/.github/workflows/deploy.yaml b/.github/workflows/deploy.yaml
index e32bcd9..178aa00 100644
--- a/.github/workflows/deploy.yaml
+++ b/.github/workflows/deploy.yaml
@@ -8,9 +8,9 @@ jobs:
   deploy:
     runs-on: ubuntu-latest
     steps:
-      - uses: actions/checkout@v3
+      - uses: actions/checkout@v4
       - name: Set up Python
-        uses: actions/setup-python@v4
+        uses: actions/setup-python@v5
         with:
           python-version: 3.12
       - name: Install dependencies
diff --git a/.github/workflows/test.yaml b/.github/workflows/test.yaml
index 7a7e868..a6c71d7 100644
--- a/.github/workflows/test.yaml
+++ b/.github/workflows/test.yaml
@@ -14,9 +14,9 @@ jobs:
       matrix:
         python-version: ["3.8", "3.9", "3.10", "3.11", "3.12"]
     steps:
-      - uses: actions/checkout@v3
+      - uses: actions/checkout@v4
       - name: Set up Python
-        uses: actions/setup-python@v4
+        uses: actions/setup-python@v5
         with:
           python-version: ${{ matrix.python-version }}
       - name: Install dependencies
@@ -29,9 +29,8 @@ jobs:
         run: black --check portion
       - name: Execute tests
         run: coverage run --source portion -m pytest
-      - name: Upload coverage
+      - name: Upload coverage to Coveralls
+        uses: coverallsapp/github-action@v2
         env:
           GITHUB_TOKEN: ${{ secrets.GITHUB_TOKEN }}
-        run: |
-          pip install coveralls
-          coveralls --service=github
+
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 564c54b..fc92006 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,7 +1,10 @@
 # Changelog
 
 
-## Next release
+## Next release (2.5.0)
+
+### Added
+ - The `combine` method of an `IntervalDict` accepts a `missing` parameter to fill values for non-overlapping keys (see [#95](https://github.com/AlexandreDecan/portion/issues/95)).
 
 ### Changed
  - Drop official support for Python 3.7.
@@ -11,7 +14,7 @@
 ## 2.4.2 (2023-12-06)
 
 ### Fixed
- - Import error when using `create_api` in Python 3.10+ (see [#87](https://github.com/AlexandreDecan/portion/issues/85)).
+ - Import error when using `create_api` in Python 3.10+ (see [#87](https://github.com/AlexandreDecan/portion/issues/87)).
 
 
 
diff --git a/README.md b/README.md
index 2bbe9ea..8151752 100644
--- a/README.md
+++ b/README.md
@@ -697,9 +697,11 @@ See [#44](https://github.com/AlexandreDecan/portion/issues/44#issuecomment-71019
 
 Two `IntervalDict` instances can be combined together using the `.combine` method.
 This method returns a new `IntervalDict` whose keys and values are taken from the two
-source `IntervalDict`. Values corresponding to non-intersecting keys are simply copied,
-while values corresponding to intersecting keys are combined together using the provided
-function, as illustrated hereafter:
+source `IntervalDict`.
+The values corresponding to intersecting keys (i.e., when the two instances overlap)
+are combined using the provided `how` function, while values corresponding to
+non-intersecting keys are simply copied (i.e., the `how` function is not called
+for them), as illustrated hereafter:
 
 ```python
 >>> d1 = P.IntervalDict({P.closed(0, 2): 'banana'})
@@ -710,6 +712,16 @@ function, as illustrated hereafter:
 
 ```
 
+The `combine` method also accepts a `missing` parameter. When `missing` is set,
+the `how` function is called even for non-intersecting keys, using the value of
+`missing` to replace the missing values:
+
+```python
+>>> d1.combine(d2, how=concat, missing='kiwi')
+{[0,1): 'banana/kiwi', [1,2]: 'banana/orange', (2,3]: 'kiwi/orange'}
+
+```
+
 Resulting keys always correspond to an outer join. Other joins can be easily simulated
 by querying the resulting `IntervalDict` as follows:
 
@@ -724,6 +736,8 @@ by querying the resulting `IntervalDict` as follows:
 
 ```
 
+
+
 Finally, similarly to a `dict`, an `IntervalDict` also supports `len`, `in` and `del`, and defines
 `.clear`, `.copy`, `.update`, `.pop`, `.popitem`, and `.setdefault`.
 For convenience, one can export the content of an `IntervalDict` to a classical Python `dict` using
diff --git a/portion/dict.py b/portion/dict.py
index 1f4890d..88dead8 100644
--- a/portion/dict.py
+++ b/portion/dict.py
@@ -218,26 +218,37 @@ class IntervalDict(MutableMapping):
         for i, v in data:
             self[i] = v
 
-    def combine(self, other, how):
+    def combine(self, other, how, *, missing=...):
         """
         Return a new IntervalDict that combines the values from current and
-        provided ones.
+        provided IntervalDict.
 
         If d = d1.combine(d2, f), then d contains (1) all values from d1 whose
         keys do not intersect the ones of d2, (2) all values from d2 whose keys
         do not intersect the ones of d1, and (3) f(x, y) for x in d1, y in d2 for
         intersecting keys.
 
+        When missing is set, the how function is called even for non-intersecting
+        keys using the value of missing to replace the missing values. This is,
+        case (1) corresponds to f(x, missing) and case (2) to f(missing, y).
+
         :param other: another IntervalDict instance.
         :param how: a function of two parameters that combines values.
+        :param missing: if set, use this value for missing values when calling "how".
         :return: a new IntervalDict instance.
         """
         new_items = []
 
         dom1, dom2 = self.domain(), other.domain()
 
-        new_items.extend(self[dom1 - dom2].items())
-        new_items.extend(other[dom2 - dom1].items())
+        if missing is Ellipsis:
+            new_items.extend(self[dom1 - dom2].items())
+            new_items.extend(other[dom2 - dom1].items())
+        else:
+            for i, v in self[dom1 - dom2].items():
+                new_items.append((i, how(v, missing)))
+            for i, v in other[dom2 - dom1].items():
+                new_items.append((i, how(missing, v)))
 
         intersection = dom1 & dom2
         d1, d2 = self[intersection], other[intersection]
diff --git a/setup.py b/setup.py
index 1127e6e..228840d 100644
--- a/setup.py
+++ b/setup.py
@@ -9,7 +9,7 @@ with open(
 
 setup(
     name="portion",
-    version="2.4.2",
+    version="2.5.0",
     license="LGPLv3",
     author="Alexandre Decan",
     url="https://github.com/AlexandreDecan/portion",


Test patch:
diff --git a/tests/test_dict.py b/tests/test_dict.py
index 1a30dd4..fe0dc8d 100644
--- a/tests/test_dict.py
+++ b/tests/test_dict.py
@@ -152,6 +152,7 @@ class TestIntervalDict:
 
     def test_combine_nonempty(self):
         def add(x, y): return x + y
+
         d1 = P.IntervalDict([(P.closed(1, 3) | P.closed(5, 7), 1)])
         d2 = P.IntervalDict([(P.closed(2, 4) | P.closed(6, 8), 2)])
         assert d1.combine(d2, add) == d2.combine(d1, add)
@@ -180,6 +181,31 @@ class TestIntervalDict:
             P.openclosed(4, 5): 1,
         })
 
+    def test_combine_missing(self):
+        def how(x, y): return x, y
+
+        d1 = P.IntervalDict([(P.closed(1, 3), 1)])
+        d2 = P.IntervalDict([(P.closed(2, 4), 2)])
+        assert d1.combine(d2, how=how, missing=None) == P.IntervalDict([
+            (P.closedopen(1, 2), (1, None)),
+            (P.closed(2, 3), (1, 2)),
+            (P.openclosed(3, 4), (None, 2))
+        ])
+
+        assert d2.combine(d1, how=how, missing=None) == P.IntervalDict([
+            (P.closedopen(1, 2), (None, 1)),
+            (P.closed(2, 3), (2, 1)),
+            (P.openclosed(3, 4), (2, None))
+        ])
+
+        def add(x, y): return x + y
+        assert d2.combine(d1, how=add, missing=3) == P.IntervalDict([
+            (P.closedopen(1, 2), 4),
+            (P.closed(2, 3), 3),
+            (P.openclosed(3, 4), 5)
+        ])
+
+
     def test_containment(self):
         d = P.IntervalDict([(P.closed(0, 3), 0)])
         assert 0 in d