function new_list = update_interval_list(left,right,old_list)

% function new_list = update_interval_list(left,right,old_list)
%
% This function inserts the interval [left,right] into
% the array old_list.
% Each row of old_list contains the two endpoints of an
% interval.
% If [left,right] doesn't intersect an old interval,
% it is inserted in the list, keeping each column increasing.
% If [left,right] is inside some existing interval, 
%   the list is unchanged.
% Otherwise, one or more old intervals are combined with
%   the new one, so that each column of the list increases.
%
% update_interval_list  Dianne O'Leary 10/2006



%  See if either endpoint is in an existing interval.
%  iL = index of existing interval containing left  endpoint
%  iR = index of existing interval containing right endpoint

iL = find((left  >= old_list(:,1)) & ...
          (left  <= old_list(:,2)));

iR = find((right >= old_list(:,1)) & ...
          (right <= old_list(:,2)));

% Find the first interval whose left endpoint is greater than this 
% new left one.  Call it interval i.

i1 = find (old_list(:,1)> left);
i = i1(1);

% Find the first interval whose left endpoint is greater than this
% new right one.  Call it interval j.

i2 = find (old_list(:,1)> right );
if (isempty(i2))
   j = size(old_list,1);
else
   j = i2(1);
end

% Decide what to do with this interval.

           
if (isempty(iL))
   if(isempty(iR)) 
% Case 1: This is a new interval, either disjoint from
%         the others or fully containing old one(s).
      new_interval = [left, right];
      iend = i-1;
   else
% Case 2: Enlarge an existing interval on the left.
      new_interval = [left,old_list(iR,2)];
      iend = i-1;
   end
elseif (isempty(iR))
% Case 3: Enlarge an existing interval on the right.
   new_interval = [old_list(iL,1),right];
   iend = iL-1;
else
% Case 4: Merge some intervals.
   new_interval = [old_list(iL,1),old_list(iR,2)];
             iend = iL-1;
end
 
new_list = [ old_list(1:iend,:)
             new_interval
             old_list(j:end,:)];
         
% Diagnostic printing
%    disp(sprintf('new interval: %f %f',left,right))
%    disp(sprintf('iL,iR,i,j %d %d %d %d',iL,iR,i,j))
%    new_list

