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

(--DOC
  The elements of an ordered collection appear in some well-defined
  order, i.e., `do' returns the elements in the same order each time
  called (specific subclasses define how that order is
  determined). Since all the classes in this section inherit from
  `collection', they support `length', `is_empty', `do', `pick_any',
  `includes', `find', `copy', and other `collection' operations.
--)


abstract object ordered_collection[T] isa collection[T];
  extend type ordered_collection[`T] subtypes ordered_collection[`S >= T];

----------
-- Iteration behavior
----------

--DOC One through four ordered collections can be iterated through in
--DOC parallel using `do'; the iteration exits when the smallest collection
--DOC is exhausted.

method do(c1@:ordered_collection[`T1], c2@:ordered_collection[`T2],
	  c:&(T1,T2):void):void {
    let s1:stream[T1] := view_stream(c1);
    let s2:stream[T2] := view_stream(c2);
    loop_exit(&(exit:&():none){
	eval(c, next(s1, exit), next(s2, exit));
    });
}
method do(c1@:ordered_collection[`T1], c2@:ordered_collection[`T2],
	  c3@:ordered_collection[`T3], c:&(T1,T2,T3):void):void {
    let s1:stream[T1] := view_stream(c1);
    let s2:stream[T2] := view_stream(c2);
    let s3:stream[T3] := view_stream(c3);
    loop_exit(&(exit:&():none){
	eval(c, next(s1, exit), next(s2, exit), next(s3, exit));
    });
}
method do(c1@:ordered_collection[`T1], c2@:ordered_collection[`T2],
	  c3@:ordered_collection[`T3], c4@:ordered_collection[`T4],
	  c:&(T1,T2,T3,T4):void):void {
    let s1:stream[T1] := view_stream(c1);
    let s2:stream[T2] := view_stream(c2);
    let s3:stream[T3] := view_stream(c3);
    let s4:stream[T4] := view_stream(c4);
    loop_exit(&(exit:&():none){
	eval(c, next(s1, exit), next(s2, exit), next(s3, exit), next(s4, exit));
    });
}

--DOC An ordered collection can be iterated through in reverse order,
--DOC and a sequence can be constructed from the ordered collection in
--DOC reverse order.

signature reverse_do(ordered_collection[`T], cl:&(T):void):void;

method reverse(s@:ordered_collection[`T]):sequence[T] {
    let var new:simple_list[T] := nil[T];
    do(s, &(e:T){ new := cons(e, new); });
    new }


--DOC Ordered collections of comparable, partially-ordered,
--DOC totally-ordered, or hashable elements are themselves comparable,
--DOC partially-ordered, totally-ordered, or hashable, respectively. Two
--DOC ordered collections are equal (`=') if they have equal elements in the
--DOC same order.  Lexicographic (dictionary) ordering is used to compare
--DOC two collections.

----------
-- equality comparing behavior
----------

extend ordered_collection[`T <= comparable[T]]
		isa comparable[ordered_collection[T]];

method =(c1@:ordered_collection[`T <= comparable[T]],
	 c2@:ordered_collection[T]):bool {
    c1 == c2 | {
    c1.length = c2.length & {
        do(c1, c2, &(e1:T, e2:T){ if(e1 != e2, { ^ false }); });
	true } } }


----------
-- lexicographic ordering behavior
----------

extend ordered_collection[`T <= ordered[T]]
		isa ordered_using_compare[ordered_collection[T]];

-- < etc. are defined in terms of compare:
method compare(c1@:ordered_collection[`T <= ordered[T]],
	       c2@:ordered_collection[`T <= ordered[T]],
	       if_less:&():`S, if_equal:&():`S, if_greater:&():`S
	       ):S (** recursive_customization **) {
    if(c1 == c2, { ^ eval(if_equal) });
    do(c1, c2, &(e1:T, e2:T){
	compare(e1, e2, { ^ eval(if_less) }, {}, { ^ eval(if_greater) });
    });
    -- answer depends on lengths
    compare(c1.length, c2.length, if_less, if_equal, if_greater) }


----------
-- Hashing behavior
----------

extend ordered_collection[`T <= hashable[T]]
		isa hashable[ordered_collection[T]];

extend ordered_collection[`T <= ordered_hashable[T]]
		isa ordered_hashable[ordered_collection[T]];

-- If you change this, be sure and go change the hard-coded primitive version
-- for strings in specialized.cecil.
let hash_shift:int := 4;
let num_hash_bits:int := round_down(num_int_bits, hash_shift);
method hash(c@:ordered_collection[`T <= hashable[T]], range:int):int {
    let var h:int := 0;
    let right_shift := num_hash_bits - hash_shift;  -- loop invariant
    do(c, &(x:T){
	h := (h << hash_shift) + hash(x, range);
	let g := h >>_logical right_shift; -- higher-order 4 bits of hash
	if(g != 0, {
	    h := (h _bit_xor g) _bit_xor (g << right_shift);
	});
    });
    abs(h) % range }


----------
-- Conversion and Views
----------

--DOC Ordered collections of characters can be converted to `vstring' or
--DOC `m_vstring' representations, and any ordered collection can be viewed
--DOC as a stream. (In the future, we plan to build a more general
--DOC mechanism for converting collections to different representations.)

method as_ordered_collection(c@:ordered_collection[`T]):ordered_collection[T] {
    c }

method as_vstring(c@:ordered_collection[char]):vstring { c.as_m_vstring }

method as_m_vstring(c@:ordered_collection[char]):m_vstring {
    let s:m_vstring := new_m_vstring_no_init(c.length);
    let var i:int := 0;
    c.do(&(e:char){ s!i := e; i := i.succ; });
    s }

signature view_stream(ordered_collection[`T]):stream[T];

signature copy(ordered_collection[`T]):ordered_collection[T];


----------
-- element selection
----------

--DOC Elements may be extracted from ordered collections; however, these
--DOC operations may be inefficient, particularly `fetch', `next_to_last',
--DOC and `last'.  Objects of type `indexed' afford fast access to any
--DOC element.

method fetch(a@:ordered_collection[`T], i:int):T {
    assert(i >= 0, "Index must be non-negative");
    let var cur_i:int := i;
    do(a, &(e:T){ if(cur_i == 0, { ^e }, { cur_i := cur_i.pred; }) });
    error("Argument out of range");
}
method !(a@:ordered_collection[`T], i:int):T { fetch(a, i); }

method first (a@:ordered_collection[`T]):T { a!0 }
method second(a@:ordered_collection[`T]):T { a!1 }
method third (a@:ordered_collection[`T]):T { a!2 }
method fourth(a@:ordered_collection[`T]):T { a!3 }
method next_to_last(a@:ordered_collection[`T]):T { a!(a.length-2) }
method last  (a@:ordered_collection[`T]):T { a!a.length.pred }


----------
-- useful methods
----------

--DOC Ordered collections of strings can be flattened into a single string,
--DOC optionally inserting a separator string element strings (only between
--DOC non-empty element strings, for `flatten_ignoring_empty').  Similarly,
--DOC any ordered collection can be flattened into a string using a
--DOC user-defined closure to convert from the collection element to a
--DOC string element.

-- flatten takes a collection of strings and a separator string.  It
-- produces a string that contains all of the non-empty strings in the
-- collection, with a separator between them.
-- For example, ["hi","","","","there"].flatten_ignoring_empty(" ")
-- produces "hi there", not "hi    there".

method flatten(c@:ordered_collection[string]):string {
    -- Special case of flatten when the separator is empty;
    -- same result as flatten(c, ""), but more efficient
    let var total_len:int := 0;
    c.do(&(s:string){
	total_len := total_len + s.length;
    });
    let result:m_vstring := new_m_vstring_no_init(total_len);
    let var pos:int := 0;
    do(c, &(s:string){
	s.write_into_string_at_pos(result, pos);
	pos := pos + s.length;
    });
    result }

method flatten(c@:ordered_collection[string], sep:string):string {
    let num_strings:int := c.length;
    if(num_strings = 0, { ^ "" });
    let sep_len:int := sep.length;
    let var total_len:int := (c.length-1) * sep_len;
    let var first:bool := true;
    c.do(&(s:string){
	let len:int := s.length;
	total_len := total_len + len;
    });
    let result:m_vstring := new_m_vstring_no_init(total_len);
    let var pos:int := 0;
    first := true;
    do(c, &(s:string){
	if(first, {
	    first := false;
	}, {
	    sep.write_into_string_at_pos(result, pos);
	    pos := pos + sep_len;
	});
	s.write_into_string_at_pos(result, pos);
	pos := pos + s.length;
    });
    assert(pos = total_len);
    result }

method flatten_ignoring_empty(c@:ordered_collection[string],
			      sep:string):string {
    let sep_len:int := sep.length;
    let num_strings:int := c.length;
    let var total_len:int := 0;
    let var first:bool := true;
    c.do(&(s:string){
	let len:int := s.length;
	if(len > 0, {
	    if(first, {
		first := false;
	    }, {
		total_len := total_len + sep_len;
	    });
	    total_len := total_len + len;
	});
    });
    let result:m_vstring := new_m_vstring_no_init(total_len);
    let var pos:int := 0;
    first := true;
    do(c, &(s:string){
	if(s.non_empty, {
	    if(first, {
		first := false;
	    }, {
		sep.write_into_string_at_pos(result, pos);
		pos := pos + sep_len;
	    });
	    s.write_into_string_at_pos(result, pos);
	    pos := pos + s.length;
	});
    });
    assert(pos = total_len);
    result }

method flatten_eval(c@:collection[`T], cl:&(T):string):string {
    let v:vector[string] :=
      new_i_vector_init_from[string](c.as_ordered_collection, cl);
    v.flatten }
method flatten_eval(c@:collection[`T], sep:string, cl:&(T):string):string {
    let v:vector[string] :=
      new_i_vector_init_from[string](c.as_ordered_collection, cl);
    v.flatten(sep) }
method flatten_eval_ignoring_empty(c@:collection[`T], sep:string,
				   cl:&(T):string):string {
    let v:vector[string] :=
      new_i_vector_init_from[string](c.as_ordered_collection, cl);
    v.flatten_ignoring_empty(sep) }

-- a convenient alias
method elems_print_string(c@:collection[`T], sep:string):string {
    flatten_eval(c, sep, &(t:T){ t.print_string }) }