16.1.3 Adding and removing elements

// Add an element to the sorted sequence
define method add! 
    (sorted-sequence :: <sorted-sequence>, new-element :: <object>) 
 => (sorted-sequence :: <sorted-sequence>)
  let element-value = sorted-sequence.value-function;
  let compare = sorted-sequence.comparison-function;
  add!(sorted-sequence.data, new-element);
  sorted-sequence.data 
    := sort!(sorted-sequence.data, 
             test: method (e1, e2) 
                     compare(element-value(e1), element-value(e2))
                   end);
  sorted-sequence;
end method add!; 

// Remove the item at the top of the sorted sequence
define method pop (sorted-sequence :: <sorted-sequence>) 
    => (top-of-sorted-sequence :: <object>)
  let data-vector = sorted-sequence.data;
  let top-of-sorted-sequence = data-vector[0];
  let sorted-sequence-size = data-vector.size;
  if (empty?(sorted-sequence))
    error("Trying to pop empty sorted-sequence %=.", sorted-sequence); 

  else
    // Shuffle up existing data, removing the top element from the 
    // sorted sequence
    for (i from 0 below sorted-sequence-size - 1)
      data-vector[i] := data-vector[i + 1];
    end for;
    // Decrease the size of the data vector, and return the top element
    data-vector.size := sorted-sequence-size - 1;
    top-of-sorted-sequence;
  end if;
end method pop; 

// Remove a particular element from the sorted sequence
define method remove!
    (sorted-sequence :: <sorted-sequence>, value :: <object>, 
     #key test = \==, count = #f)
 => (sorted-sequence :: <sorted-sequence>)
  let data-vector = sorted-sequence.data;
  let sorted-sequence-size = data-vector.size;
  for (deletion-point from 0,
        // If we have reached the end of the sequence, or we have reached
        // the user-specified limit, we are done
        // Note that specifying a bound in the preceding clause for
        //deletion-point does not work, because bounds are computed only
        // once, and we change sorted-sequence-size in the body
       until: (deletion-point >= sorted-sequence-size) 
              | (count & count = 0)) 
    // Otherwise, if we found a matching element, remove it from the 
    // sorted sequence.
    if (test(data-vector[deletion-point], value))
      for (i from deletion-point below sorted-sequence-size - 1)
        data-vector[i] := data-vector[i + 1]
      end for;
      sorted-sequence-size 
         := (data-vector.size := sorted-sequence-size - 1);
      if (count) count := count - 1 end;
    end if;
  end for;
  sorted-sequence;
end method remove!;