path: root/gee/traversable.vala

/* traversable.vala
 *
 * Copyright (C) 2011-2012  Maciej Piechotka
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.

 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.

 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
 *
 * Author:
 * 	Maciej Piechotka <uzytkownik2@gmail.com>
 */

namespace Gee {
	public delegate A FoldFunc<A, G> (owned G g, owned A a);
	public delegate bool ForallFunc<G> (owned G g);
	public delegate Lazy<A>? UnfoldFunc<A> ();
	public delegate Traversable.Stream StreamFunc<G, A> (Traversable.Stream state, owned Lazy<G>? g, out Lazy<A>? lazy);
	public delegate A MapFunc<A, G> (owned G g);
	public delegate bool Predicate<G> (G g);
}

/**
 * It's a common interface for {@link Iterator} and {@link Iterable}. It
 * provides a fast, high level functions.
 *
 * ''{@link Iterator} implementation:'' Please note that most of the functions
 * affect the state of the iterator by moving it forward.
 * Even if the iterator is {@link BidirIterator} it ''must not''
 * rewind the state.
 *
 * ''{@link Iterable} implementation:'' validy ({@link Iterator.valid})
 * of returned iterator is the same as for invalid
 * iterator. In other words the following code is semantically equivalent:
 *
 * {{{
 *     var x = iterable.function (args);
 *     var x = iterable.iterator ().function(args);
 * }}}
 *
 * @since 0.7.0
 */
[GenericAccessors]
public interface Gee.Traversable<G> : Object {
	/**
	 * Apply function to each element returned by iterator untill last element
	 * or function return ''false''.
	 *
	 * ''{@link Iterator} implementation:'' Operation moves the iterator
	 * to last element in iteration or the first element that returned ''false''.
	 * If iterator points at some element it will be included in iteration.
	 *
	 * @param f function applied to every element of the collection
	 *
	 * @return ''false'' if the argument returned ''false'' at last invocation and
	 *         ''true'' otherwise.
	 */
	[CCode (ordering = 0)]
	public new abstract bool foreach (ForallFunc<G> f);

	/**
	 * Stream function is an abstract function allowing writing many
	 * operations.
	 *
	 * The stream function accepts three parameter:
	 *
	 *   1. state. It is usually the last returned value from function but
	 *      it may be {@link Stream.END} when {@link Stream.CONTINUE} was
	 *      returned and there was no more elements.
	 *   1. input. It is valid only if first argument is
	 *      {@link Stream.CONTINUE}
	 *   1. output. It is valid only if result is Stream.YIELD
	 *
	 * It may return one of 3 results:
	 *
	 *   1. {@link Stream.YIELD}. It means that value was yielded and can
	 *      be passed to outgoing iterator.
	 *   1. {@link Stream.CONTINUE}. It means that the function needs to be
	 *      called with next element or with {@link Stream.END} if it is
	 *      end of stream). If the state element was Stream.END during the
	 *      current iteration function ''must not'' return {@link Stream.CONTINUE}.
	 *   1. {@link Stream.WAIT}. Simply denotes that iterator should skip an element.
	 *      Usually the function is called once again with {@link Stream.WAIT} as
	 *      state however it do affect the initial validity of iterator.
	 *   1. {@link Stream.END}. It means that the last argument was yielded.
	 *
	 * If the function yields the value immediately then the returning iterator
	 * is {@link Iterator.valid} and points to this value as well as in case when the
	 * parent iterator is {@link Iterator.valid} and function yields
	 * after consuming 1 input. In other case returned iterator is invalid including
	 * when the first value returned is {@link Stream.WAIT}.
	 *
	 * Note: In {@link Iterator} implementation: if iterator is
	 *    {@link Iterator.valid} the current value should be fed
	 *    immediately to function if during initial call function returns
	 *    {@link Stream.CONTINUE}. The parent iterator cannot be used before
	 *    the functions return {@link Stream.END} afterwards it points on the
	 *    last element consumed.
	 *
	 * @param f function generating stream
	 * @return iterator containing values yielded by stream
	 */
	[CCode (ordering = 1)]
	public virtual Iterator<A> stream<A> (owned StreamFunc<G, A> f) {
		unowned Iterator<G>? self;
		unowned Iterable<G>? iself;
		// Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
		if ((self = this as Iterator<G>) != null) {
			return new StreamIterator<A, G> (self, (owned)f);
		} else if ((iself = this as Iterable<G>) != null) {
			return iself.iterator().stream<A> ((owned) f);
		} else {
			assert_not_reached ();
		}
	}

	/**
	 * Standard aggregation function.
	 *
	 * It takes a function, seed and first element, returns the new seed and
	 * progress to next element when the operation repeats.
	 *
	 * Note: Default implementation uses {@link foreach}.
	 *
	 * Note: In {@link Iterator} implementation operation moves the
	 *    iterator to last element in iteration. If iterator is
	 *    {@link Iterator.valid} the current element will be considered
	 *    as well.
	 *
	 */
	[CCode (ordering = 2)]
	public virtual A fold<A> (FoldFunc<A, G> f, owned A seed)
	{
		this.foreach ((item) => {seed = f ((owned) item, (owned) seed); return true; });
		return (owned) seed;
	}

	/**
	 * Produces an iterator pointing at elements generated by function passed.
	 *
	 * Iterator is lazy evaluated but value is force-evaluated when
	 * iterator moves to next element. ({@link Iterator.next})
	 *
	 * Note: Default implementation uses {@link stream}.
	 *
	 * Note: In {@link Iterator} implementation if the parent iterator is
	 *    {@link Iterator.valid} so is the returned one. Using the parent
	 *    iterator is not allowed before the inner iterator {@link Iterator.next}
	 *    return false and then it points on its last element.
	 *    The resulting iterator is {@link Iterator.valid} if the parent
	 *    iterator is.
	 *
	 * @param f Mapping function
	 * @return Iterator listing mapped value
	 */
	[CCode (ordering = 3)]
	public virtual Iterator<A> map<A> (MapFunc<A, G> f) {
		return stream<A>((state, item, out val) => {
			switch (state) {
			case Stream.YIELD:
				val = null;
				return Stream.CONTINUE;
			case Stream.CONTINUE:
				val = new Lazy<A>(() => {
					A tmp = item.get ();
					item = null;
					return (f ((owned)tmp));
				});
				return Stream.YIELD;
			case Stream.END:
				val = null;
				return Stream.END;
			default:
				assert_not_reached ();
			}
		});
	}

	/**
	 * Creates a new iterator that is initially pointing to seed. Then
	 * subsequent values are obtained after applying the function to previous
	 * value and the subsequent items.
	 *
	 * The resulting iterator is always valid and it contains the seed value.
	 *
	 * Note: Default implementation uses {@link stream}.
	 *
	 * Note: When the method is called on {@link Iterator} using the parent
	 *    iterator is not allowed befor the inner iterator
	 *    {@link Iterator.next} return false and then it points on its last
	 *    element. The resulting iterator is {@link Iterator.valid}.
	 *
	 * @param f Folding function
	 * @param seed original seed value
	 * @return Iterator containing values of subsequent values of seed
	 */
	[CCode (ordering = 4)]
	public virtual Iterator<A> scan<A> (FoldFunc<A, G> f, owned A seed) {
		bool seed_emitted = false;
		return stream<A>((state, item, out val) => {
			switch (state) {
			case Stream.YIELD:
				if (seed_emitted) {
					val = null;
					return Stream.CONTINUE;
				} else {
					val = new Lazy<A>.from_value (seed);
					seed_emitted = true;
					return Stream.YIELD;
				}
			case Stream.CONTINUE:
				val = new Lazy<A> (() => {
					A tmp = item.get ();
					item = null;
					seed = f ((owned) tmp, (owned) seed);
					return seed;
				});
				return Stream.YIELD;
			case Stream.END:
				val = null;
				return Stream.END;
			default:
				assert_not_reached ();
			}
		});
	}

	/**
	 * Creates a new iterator that contains only values that fullfills the
	 * predicate.
	 *
	 * Note: When the method is called on {@link Iterator} using the parent
	 *    iterator is not allowed befor the inner iterator
	 *    {@link Iterator.next} return false and then it points on its last
	 *    element. The resulting iterator is {@link Iterator.valid} if parent
	 *    iterator is {@link Iterator.valid} and value it is pointing on
	 *    fullfills the predicate.
	 *
	 * @param pred predicate to check should the value be retained
	 * @return Iterator containing values of subsequent values of seed
	 */
	[CCode (ordering = 5)]
	public virtual Iterator<G> filter (owned Predicate<G> pred) {
		return stream<G> ((state, item, out val) => {
			switch (state) {
			case Stream.YIELD:
				val = null;
				return Stream.CONTINUE;
			case Stream.CONTINUE:
				G g = item.get ();
				if (pred (g)) {
					val = item;
					return Stream.YIELD;
				} else {
					val = null;
					return Stream.CONTINUE;
				}
			case Stream.END:
				val = null;
				return Stream.END;
			default:
				assert_not_reached ();
			};
		});
	}

	/**
	 * Creates a new iterator which contains elements from iterable. The
	 * first argument states the offset i.e. number of elements the iterator
	 * skips by default.
	 *
	 * Note: In {@link Iterator} implementation resulting iterator is
	 *    {@link Iterator.valid} when parent iterator is
	 *    {@link Iterator.valid} and the offset is 0. Using the parent
	 *    iterator is not allowed before the inner iterator
	 *    {@link Iterator.next} return false and then it points on its last
	 *    element.
	 *
	 * @param offset the offset to first element the iterator is pointing to
	 * @param length maximum number of elements iterator may return. Negative
	 *        value means that the number is unbounded
	 */
	[CCode (ordering = 6)]
	public virtual Iterator<G> chop (int offset, int length = -1) {
		assert (offset >= 0);
		return stream<G> ((state, item, out val) => {
			switch (state) {
			case Stream.YIELD:
				val = null;
				if (offset > 0) {
					return Stream.CONTINUE;
				} else if (length > 0) {
					return length != 0 ? Stream.CONTINUE : Stream.END;
				} else if (length == 0) {
					return Stream.END;
				} else {
					return Stream.CONTINUE;
				}
			case Stream.CONTINUE:
				if (offset == 0) {
					val = item;
					length--;
					return Stream.YIELD;
				} else {
					val = null;
					offset--;
					return Stream.CONTINUE;
				}
			case Stream.END:
				val = null;
				return Stream.END;
			default:
				assert_not_reached ();
			};
		});
	}

	/**
	 * The type of the elements in this collection.
	 */
	[CCode (ordering = 7)]
	public virtual Type element_type { get { return typeof (G); } }

	/**
	 * A fused concatinate and map. The function is applied to each element
	 * of iteration and the resulting values are concatinated.
	 *
	 * The iterator is lazy evaluated but value is force-evaluated when
	 * iterator is moved to next value.
	 *
	 * Note: Default implementation uses {@link stream}.
	 *
	 * Note: In {@link Iterator} implementation if the parent iterator is
	 *    {@link Iterator.valid} and function returns a valid iterator the
	 *    resulting iterator is also valid. Using the parent iterator is not
	 *    allowed before the inner iterator {@link Iterator.next}
	 *    return false and then it points on its last element.
	 *
	 * @since 0.11.1
	 * @param f mapping function
	 * @return Iterator over returned values
	 */
	[CCode (ordering = 8)]
	public virtual Iterator<A> flat_map<A>(owned FlatMapFunc<A, G> f) {
		Iterator<A>? current = null;
		return stream<A> ((state, item, out val) => {
			switch (state) {
			case Stream.YIELD:
				if (current == null || !current.next ()) {
					val = null;
					return Stream.CONTINUE;
				} else {
					val = new Lazy<A> (() => {return current.get ();});
					return Stream.YIELD;
				}
			case Stream.CONTINUE:
				current = f (item.get ());
				if (current.valid) {
					val = new Lazy<A> (() => {return current.get ();});
					return Stream.YIELD;
				} else {
					val = null;
					return Stream.WAIT;
				}
			case Stream.WAIT:
				if (current.next()) {
					val = new Lazy<A> (() => {return current.get ();});
					return Stream.YIELD;
				} else {
					val = null;
					return Stream.CONTINUE;
				}
			case Stream.END:
				val = null;
				return Stream.END;
			default:
				assert_not_reached ();
			}
		});
	}

	/**
	 * Splits the traversable into multiple ones, caching the result if needed.
	 *
	 * Note: In {@link Iterator} implementation using the parent iterator is
	 *   not allowed. However if any of the forked iterators {@link next}
	 *   return false then it is treated as if the parent iterator
	 *   {@link next} returned false.
	 *
	 * Note: The returned arrey might contain parent iterator if it is allowed
	 *   by implementation. For example the iteration over collection does
	 *   not need to generate and cache the results.
	 *   In such case it is recommended to return the value as the first element
	 *   of the array. This allows the consumer to check just the first element
	 *   if it can perform optimizations for such case. However it //must// not
	 *   depend on the order (that's for optimization only).
	 *
	 * Note: The resulting iterators does not need to be thread safe.
	 *
	 * @param forks Number of iterators in array
	 * @return An array with created iterators
	 * @since 0.11.5
	 */
	[CCode (ordering = 9)]
	public virtual Iterator<G>[] tee (uint forks) {
		unowned Iterator<G>? self;
		unowned Iterable<G>? iself;
		// Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
		if ((self = this as Iterator<G>) != null) {
			if (forks == 0) {
				return new Iterator<G>[0];
			} else if (forks == 1) {
				return new Iterator<G>[1]{self};
			} else {
				Iterator<G>[] result = new Iterator<G>[forks];
				Lazy<G>? data;
				bool is_valid = self.valid;
				if (is_valid) {
					data = new Lazy<G>(() => {return self.get ();});
				} else {
					data = new Lazy<G>.from_value (null);
				}
				var head = new TeeIterator.Node<G> (data, TeeIterator.create_nodes<G> (self, data));
				for (uint i = 0; i < forks; i++) {
					result[i] = new TeeIterator<G> (head, is_valid);
				}
				return result;
			}
		} else if ((iself = this as Iterable<G>) != null) {
			var result = new Iterator<G>[forks];
			for (uint i = 0; i < forks; i++) {
				result[i] = iself.iterator ();
			}
			return result;
		} else {
			assert_not_reached ();
		}
	}

	/**
	 * Returns the first element that matches a given condition
	 *
	 * @param pred Predicate to be called to check for matches
	 * @return The first element that matches or null
	 * @since 0.19.91
	 */
	[CCode (ordering = 10)]
	public virtual G? first_match (owned Predicate<G> pred) {
		G? result = null;
		this.foreach ((item) => {
			if (pred (item)) {
				result = item;
				return false;
			}
			return true;
		});
		return (owned) result;
	}

	/**
	 * Returns whether any element matches the given predicate.
	 *
	 * This is similar to @first_match, with the difference that it
	 * just returns whether there is a match or not, not the value
	 * of the match.
	 *
	 * @param pred Predicate to be called to check for matches
	 * @return Whether there was a match or not
	 * @since 0.19.91
	 */
	[CCode (ordering = 11)]
	public virtual bool any_match (owned Predicate<G> pred) {
		return this.first_match ((owned) pred) != null;
	}

	/**
	 * Checks whether all elements match the given predicate.
	 *
	 * @param pred Predicate to be called to check for matches
	 * @return Whether all elements match or not
	 * @since 0.19.91
	 */
	[CCode (ordering = 12)]
	public virtual bool all_match (owned Predicate<G> pred) {
		bool result = true;
		this.foreach ((item) => {
			if (!pred (item)) {
				result = false;
				return false;
			}
			return true;
		});
		return result;
	}

	/**
	 * Returns the item in the sequence that contains the max value
	 * based on the given compare function.
	 *
	 * @param compare Function to be called for comparisons
	 * @return The item containing the max value.
	 * @since 0.19.91
	 */
	[CCode (ordering = 13)]
	public virtual G max (owned CompareDataFunc<G> compare) {
		G max_value = null;
		this.foreach ((item) => {
			if (max_value == null || compare (max_value, item) > 0) {
				max_value = item;
			}
			return true;
		});
		return max_value;
	}

	/**
	 * Returns the item in the sequence that contains the min value
	 * based on the given compare function.
	 *
	 * @param compare Function to be called for comparisons
	 * @return The item containing the min value.
	 * @since 0.19.91
	 */
	[CCode (ordering = 14)]
	public virtual G min (owned CompareDataFunc<G> compare) {
		G min_value = null;
		this.foreach ((item) => {
			if (min_value == null || compare (min_value, item) < 0) {
				min_value = item;
			}
			return true;
		});
		return min_value;
	}

	/**
	 * Returns a new iterator containing the elements in the source
	 * ordered as specified by the comparison function.
	 *
	 * @param compare Comparison function
	 * @return A new iterator with the source elements sorted.
	 * @since 0.19.91
	 */
	[CCode (ordering = 15)]
	public virtual Iterator<G> order_by (owned CompareDataFunc<G>? compare = null) {
		ArrayList<G> result = new ArrayList<G> ();
		this.foreach ((item) => result.add (item));
		result.sort ((owned) compare);
		return result.iterator ();
	}

	public enum Stream {
		YIELD,
		CONTINUE,
		END,
		WAIT
	}
}

namespace Gee {
	// Placed here to workaround bug #703710
	public delegate Iterator<A> FlatMapFunc<A, G>(owned G g);
}