//  Copyright (c) CNES  2008
//
//  This software is part of CelestLab, a CNES toolbox for Scilab
//
//  This software is governed by the CeCILL  license under French law and
//  abiding by the rules of distribution of free software.  You can  use,
//  modify and/ or redistribute the software under the terms of the CeCILL
//  license as circulated by CEA, CNRS and INRIA at the following URL
//  'http://www.cecill.info'.

function [ires] = CL_intervUnion(varargin)
// Union of sets of intervals
//
// Calling Sequence
// ires = CL_intervUnion(i1 [,i2,i3,...,ip])
//
// Description
// <itemizedlist><listitem>
// <p>Computes the union of sets of intervals.</p>
// <p>The intervals are gathered in different sets (i1, i2,...,ip). </p>
// <p>A real number x belongs to the union of (i1, i2,...,ip) if it belongs to at least one interval in one 
// of the sets. </p>
// <inlinemediaobject><imageobject><imagedata fileref="union.gif"/></imageobject></inlinemediaobject>
// <p></p></listitem>
// <listitem>
// <p><b>Notes:</b></p>
// <p> - Only one set may be given. The result is then the union of the intervals that belong to the set. </p>
// <p> - Intervals of length equal to 0 are discarded. (length = end of interval minus beginning of interval) </p>
// <p> - Sets of intervals may be empty: CL_intervUnion(i1,[]) = CL_intervUnion(i1)</p>
// <p> - Resulting set of intervals are sorted in ascending order (first row) </p>
// </listitem>
// </itemizedlist>
//
// Parameters
// i1: Set of intervals [start ; end] (2xN)
// i2: Set of intervals [start ; end] (2xN2)
// ip: Set of intervals [start ; end] (2xNp)
// ires: Union of i1,i2...,iN (2xM)
//
// See also
// CL_intervInters
// CL_intervInv
//
// Authors
// CNES - DCT/SB
//
// Examples
// i1 = [[1;3], [5;6], [10;12]];
// i2 = [[2;4], [5.5;5.7], [5.6;15]];
// ires = CL_intervUnion(i1,i2);

// Declarations:


// Code:

itot = [];

for (i = 1 : size(varargin))
  if (varargin(i) <> [])
    if (size(varargin(i),1) <> 2)
      CL__error("Invalid size for interval " + msprintf("%d", i));
    end
    itot = [itot, varargin(i)];
  end
end


// suppression of intervals of zero length
itot(:, find(itot(2,:) == itot(1,:))) = []; 

// if empty array => exit
if (itot == []) 
  ires = []; 
  return; 
end

// check lower bound < upper bound
if (find(itot(2,:) < itot(1,:)) <> [])
  CL__error("Invalid intervals (lower bound > upper bound)");
end

// itot: sorted in increasing order
itot = CL_sortMat(itot, itot(1,:));

N = size(itot,2);

// Initialization of union of intervals: 
// only the 1st element is valid 
ires = itot;

j = 1; // index for ires  (j = last initialized) 
k = 0; // index for itot (k = last processed) 

while (k < N)
  I = find(itot(2,k+1:$) > ires(2,j)); 
  
  if (I == [])
    break; 
  end
  
  k = k + I(1); 
  
  // Note: itot(1,k) >= ires(1,j)
  
  if (itot(1,k) > ires(2,j))
    j = j+1; 
    ires(:,j) = itot(:,k); 
  else
    ires(2,j) = itot(2,k); 
  end
  
end

ires = ires(:, 1:j); 
 
endfunction