-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

(--DOC
  Sequences support the `||' concatenation operator. However, for long series
  of concatenations, using `||' many times can be inefficient and imply lots
  of copying. The `collector' extensible sequence data structure supports
  accumulating sequences for latter concatenation in one fell swoop.

  Collectors can be created (optionally with a non-binding guess as to
  how many things will be collected together) using new_collector. The
  infix `&&' operation is the more common way to construct
  collectors. Collectors are flattened into a vector form using
  `flat_vector', and collectors of character sequences can be flattened
  into a simple string using `flat_string'. To illustrate the use of
  collectors versus concatenation:
  <EXAMPLE>
    ("hi" && "there" && "bob").flat_string = "hi" || "there" || "bob"
  <ENDEXAMPLE>
--)

-- A collector accumulates a sequence of sequences to be concatenated.
-- The elements in the collector can later be flattened to produce a
-- collection with all the elements actually concatenated.  Reduces the cost
-- of building up a collection from N shorter collections from O(N^2) to O(N).

-- It is assumed that the elements in the collector don't change once they've
-- been added.  If they do, the flat_length value may be incorrect.

-- [don't make a collector a subtype of sequence, so that && on collectors
--  and sequences is unambiguous.]
forall S: template object collector[T <= sequence[S]];
-- BUG: can't combine this with above decl, yet.
extend collector[`T] isa ordered_collection[T];

  -- collector subtyping is covariant in the parameter type
  forall S, T <= sequence[S], T1 >= T, T1 <= sequence[S]:
      extend type collector[T] subtypes collector[T1];

  -- don't let external clients treat a collector as an array:
  private extend representation collector[`T] inherits array[T];

  private put var field flat_length(@:collector[`T]):int := 0;


-- flatten the collector into a vector
method flat_vector(c@:collector[`T <= sequence[`S]]):vector[S] {
    let v:m_vector[S] := new_m_vector[S](c.flat_length);
    let var index:int := 0;
    c.do(&(s:sequence[S]){
	s.do(&(x:S){
	    v!index := x;
	    index := index.succ;
	});
    });
    v }


-- the two resends don't typecheck w/ private inheritance
method add_first(c@:collector[`T], x:`T):void (** no_typecheck **) {
  -- Adding something which is not a collector.
  c.flat_length := c.flat_length + x.length;
  resend;
}

method add_last(c@:collector[`T], x:T):void (** no_typecheck **) {
  c.flat_length := c.flat_length + x.length;
  resend;
}

method new_collector[T <= sequence[`S]]():collector[T] {
    concrete object isa collector[T] }
-- w/ private inheritance from array, don't know about array's fields
method new_collector[T <= sequence[`S]](size:int):collector[T]
							(** no_typecheck **) {
    concrete object isa collector[T] {
	contents := new_m_vector[T](size), first_elem := size / 3 } }

method copy(c@:collector[`T]):collector[T] {
  let newC:collector[T] := new_collector[T]();
  c.do(&(el:T){ newC.add_last(el); });
  newC }

method collection_name(@:collector[`T]):string { "collector" }


-- operations specific to collectors of character sequences

signature flat_string(string|collector[string]):string;
method flat_string(c@:collector[string]):string {
    c.flatten }
method flat_string(c@:string):string {
    -- define this method so you can send flat_string to something that might
    -- or might not be a string collector
    c }

signature write(unix_file, indexed[char] | collector[indexed[char]],
		if_error:&(int):void):void;
method write(f@:unix_file, c@:collector[indexed[char]],
	     if_error:&(int):void):void {
  c.do(&(s:indexed[char]){
      f.write(s, s.length, &(i:int){ eval(if_error, i); ^ });
  });
}
signature write(unix_file, indexed[char] | collector[indexed[char]]):void;
method write(f@:unix_file, c@:collector[indexed[char]]):void {
  write(f, c, &(i:int){ unix_error(i, "writing file") }) }



-- && adds an element to a collector.  If e is an element and
-- c is a collector, then:
--    c  && e   adds e onto the end of the collector
--    e  && c   adds e onto the front of the collector
--    e1 && e2  is a constructor which creates a new collector
--    c1 && c2  adds the elements of c2 to the end of c1

precedence && left_associative with ||;

signature &&((`T <= sequence[`S]) | collector[`T],
	     (`T <= sequence[`S]) | collector[`T]):collector[T];

method &&(s1@sequence[`S]:`T <= sequence[`S],
	  s2@sequence[`S]:`T <= sequence[`S]):collector[T] {
  let c:collector[T] := new_collector[T]();
  c.add_last(s1);
  c.add_last(s2);
  c }
method &&(s1@sequence[`S]:`T <= sequence[`S], c@:collector[`T]):collector[T] {
  c.add_first(s1);
  c }
method &&(c@:collector[`T], s2@sequence[`S]:`T <= sequence[`S]):collector[T] {
  c.add_last(s2);
  c }
method &&(c1@:collector[`T], c2@:collector[`T]):collector[T] {
  c2.do(&(e:T){ c1.add_last(e); });
  c1 }


-- the standard concatenate operation for sequences
method ||(c1@:collector[`T], c2@:collector[`T]):collector[T] {
  new_collector[T]() && c1 && c2 }