gee/traversable.vala

   1 /* traversable.vala
   2  *
   3  * Copyright (C) 2011-2012  Maciej Piechotka
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  18  *
  19  * Author:
  20  *      Maciej Piechotka <uzytkownik2@gmail.com>
  21  */
  22
  23 namespace Gee {
  24         public delegate A FoldFunc<A, G> (owned G g, owned A a);
  25         public delegate bool ForallFunc<G> (owned G g);
  26         public delegate Lazy<A>? UnfoldFunc<A> ();
  27         public delegate Traversable.Stream StreamFunc<G, A> (Traversable.Stream state, owned Lazy<G>? g, out Lazy<A>? lazy);
  28         public delegate A MapFunc<A, G> (owned G g);
  29         public delegate bool Predicate<G> (G g);
  30 }
  31
  32 /**
  33  * It's a common interface for {@link Iterator} and {@link Iterable}. It
  34  * provides a fast, high level functions.
  35  *
  36  * ''{@link Iterator} implementation:'' Please note that most of the functions
  37  * affect the state of the iterator by moving it forward.
  38  * Even if the iterator is {@link BidirIterator} it ''must not''
  39  * rewind the state.
  40  *
  41  * ''{@link Iterable} implementation:'' validy ({@link Iterator.valid})
  42  * of returned iterator is the same as for invalid
  43  * iterator. In other words the following code is semantically equivalent:
  44  *
  45  * {{{
  46  *     var x = iterable.function (args);
  47  *     var x = iterable.iterator ().function(args);
  48  * }}}
  49  *
  50  * @since 0.7.0
  51  */
  52 [GenericAccessors]
  53 public interface Gee.Traversable<G> : Object {
  54         /**
  55          * Apply function to each element returned by iterator untill last element
  56          * or function return ''false''.
  57          *
  58          * ''{@link Iterator} implementation:'' Operation moves the iterator
  59          * to last element in iteration or the first element that returned ''false''.
  60          * If iterator points at some element it will be included in iteration.
  61          *
  62          * @param f function applied to every element of the collection
  63          *
  64          * @return ''false'' if the argument returned ''false'' at last invocation and
  65          *         ''true'' otherwise.
  66          */
  67         public new abstract bool foreach (ForallFunc<G> f);
  68
  69         /**
  70          * Stream function is an abstract function allowing writing many
  71          * operations.
  72          *
  73          * The stream function accepts three parameter:
  74          *
  75          *   1. state. It is usually the last returned value from function but
  76          *      it may be {@link Stream.END} when {@link Stream.CONTINUE} was
  77          *      returned and there was no more elements.
  78          *   1. input. It is valid only if first argument is
  79          *      {@link Stream.CONTINUE}
  80          *   1. output. It is valid only if result is Stream.YIELD
  81          *
  82          * It may return one of 3 results:
  83          *
  84          *   1. {@link Stream.YIELD}. It means that value was yielded and can
  85          *      be passed to outgoing iterator.
  86          *   1. {@link Stream.CONTINUE}. It means that the function needs to be
  87          *      called with next element or with {@link Stream.END} if it is
  88          *      end of stream). If the state element was Stream.END during the
  89          *      current iteration function ''must not'' return {@link Stream.CONTINUE}
  90          *   1. Stream.END. It means that the last argument was yielded.
  91          *
  92          * If the function yields the value immediately then the returning iterator
  93          * is {@link Iterator.valid} and points to this value as well as in case when the
  94          * parent iterator is {@link Iterator.valid} and function yields
  95          * after consuming 1 input. In other case returned iterator is invalid.
  96          *
  97          * Note: In {@link Iterator} implementation: if iterator is
  98          *    {@link Iterator.valid} the current value should be fed
  99          *    immediately to function if during initial call function returns
 100          *    {@link Stream.CONTINUE}. The parent iterator cannot be used before
 101          *    the functions return {@link Stream.END} afterwards it points on the
 102          *    last element consumed.
 103          *
 104          * @param f function generating stream
 105          * @return iterator containing values yielded by stream
 106          */
 107         public virtual Iterator<A> stream<A> (owned StreamFunc<G, A> f) {
 108                 Iterator<G>? self;
 109                 Iterable<G>? iself;
 110                 // Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
 111                 if ((self = this as Iterator<G>) != null) {
 112                         Traversable.Stream str;
 113                         Lazy<A>? initial = null;
 114                         bool need_next = true;
 115                         str = f (Stream.YIELD, null, out initial);
 116                         switch (str) {
 117                         case Stream.CONTINUE:
 118                                 if (self.valid) {
 119                                         str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get ();}), out initial);
 120                                         switch (str) {
 121                                         case Stream.YIELD:
 122                                         case Stream.CONTINUE:
 123                                                 break;
 124                                         case Stream.END:
 125                                                 return Iterator.unfold<A> (() => {return null;});
 126                                         default:
 127                                                 assert_not_reached ();
 128                                         }
 129                                 }
 130                                 break;
 131                         case Stream.YIELD:
 132                                 if (self.valid)
 133                                         need_next = false;
 134                                 break;
 135                         case Stream.END:
 136                                 return Iterator.unfold<A> (() => {return null;});
 137                         default:
 138                                 assert_not_reached ();
 139                         }
 140                         return Iterator.unfold<A> (() => {
 141                                 Lazy<A>? val = null;
 142                                 if (str != Stream.CONTINUE)
 143                                         str = f (Traversable.Stream.YIELD, null, out val);
 144                                 while (str == Stream.CONTINUE) {
 145                                         if (need_next) {
 146                                                 if (!self.next ()) {
 147                                                         str = f (Traversable.Stream.END, null, out val);
 148                                                         assert (str != Traversable.Stream.CONTINUE);
 149                                                         break;
 150                                                 }
 151                                         } else {
 152                                                 need_next = true;
 153                                         }
 154                                         str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get ();}), out val);
 155                                 }
 156                                 switch (str) {
 157                                 case Stream.YIELD:
 158                                         return val;
 159                                 case Stream.END:
 160                                         return null;
 161                                 default:
 162                                         assert_not_reached ();
 163                                 }
 164                         }, initial);
 165                 } else if ((iself = this as Iterable<G>) != null) {
 166                         return iself.iterator().stream<A> ((owned) f);
 167                 } else {
 168                         assert_not_reached ();
 169                 }
 170         }
 171
 172         /**
 173          * Standard aggregation function.
 174          *
 175          * It takes a function, seed and first element, returns the new seed and
 176          * progress to next element when the operation repeats.
 177          *
 178          * Note: Default implementation uses {@link foreach}.
 179          *
 180          * Note: In {@link Iterator} implementation operation moves the
 181          *    iterator to last element in iteration. If iterator is
 182          *    {@link Iterator.valid} the current element will be considered
 183          *    as well.
 184          *
 185          */
 186         public virtual A fold<A> (FoldFunc<A, G> f, owned A seed)
 187         {
 188                 this.foreach ((item) => {seed = f ((owned) item, (owned) seed); return true; });
 189                 return (owned) seed;
 190         }
 191
 192         /**
 193          * Produces an iterator pointing at elements generated by function passed.
 194          *
 195          * Iterator is lazy evaluated but value is force-evaluated when
 196          * iterator moves to next element. ({@link Iterator.next})
 197          *
 198          * Note: Default implementation uses {@link stream}.
 199          *
 200          * Note: In {@link Iterator} implementation if the parent iterator is
 201          *    {@link Iterator.valid} so is the returned one. Using the parent
 202          *    iterator is not allowed before the inner iterator {@link Iterator.next}
 203          *    return false and then it points on its last element.
 204          *    The resulting iterator is {@link Iterator.valid} if the parent
 205          *    iterator is.
 206          *
 207          * @param f Mapping function
 208          * @return Iterator listing mapped value
 209          */
 210         public virtual Iterator<A> map<A> (MapFunc<A, G> f) {
 211                 return stream<A>((state, item, out val) => {
 212                         switch (state) {
 213                         case Stream.YIELD:
 214                                 val = null;
 215                                 return Stream.CONTINUE;
 216                         case Stream.CONTINUE:
 217                                 val = new Lazy<A>(() => {
 218                                         A tmp = item.get ();
 219                                         item = null;
 220                                         return (f ((owned)tmp));
 221                                 });
 222                                 return Stream.YIELD;
 223                         case Stream.END:
 224                                 val = null;
 225                                 return Stream.END;
 226                         default:
 227                                 assert_not_reached ();
 228                         }
 229                 });
 230         }
 231
 232         /**
 233          * Creates a new iterator that is initially pointing to seed. Then
 234          * subsequent values are obtained after applying the function to previous
 235          * value and the subsequent items.
 236          *
 237          * The resulting iterator is always valid and it contains the seed value.
 238          *
 239          * Note: Default implementation uses {@link stream}.
 240          *
 241          * Note: When the method is called on {@link Iterator} using the parent
 242          *    iterator is not allowed befor the inner iterator
 243          *    {@link Iterator.next} return false and then it points on its last
 244          *    element. The resulting iterator is {@link Iterator.valid}.
 245          *
 246          * @param f Folding function
 247          * @param seed original seed value
 248          * @return Iterator containing values of subsequent values of seed
 249          */
 250         public virtual Iterator<A> scan<A> (FoldFunc<A, G> f, owned A seed) {
 251                 bool seed_emitted = false;
 252                 return stream<A>((state, item, out val) => {
 253                         switch (state) {
 254                         case Stream.YIELD:
 255                                 if (seed_emitted) {
 256                                         val = null;
 257                                         return Stream.CONTINUE;
 258                                 } else {
 259                                         val = new Lazy<A>.from_value (seed);
 260                                         seed_emitted = true;
 261                                         return Stream.YIELD;
 262                                 }
 263                         case Stream.CONTINUE:
 264                                 val = new Lazy<A> (() => {
 265                                         A tmp = item.get ();
 266                                         item = null;
 267                                         seed = f ((owned) tmp, (owned) seed);
 268                                         return seed;
 269                                 });
 270                                 return Stream.YIELD;
 271                         case Stream.END:
 272                                 val = null;
 273                                 return Stream.END;
 274                         default:
 275                                 assert_not_reached ();
 276                         }
 277                 });
 278         }
 279
 280         /**
 281          * Creates a new iterator that contains only values that fullfills the
 282          * predicate.
 283          *
 284          * Note: When the method is called on {@link Iterator} using the parent
 285          *    iterator is not allowed befor the inner iterator
 286          *    {@link Iterator.next} return false and then it points on its last
 287          *    element. The resulting iterator is {@link Iterator.valid} if parent
 288          *    iterator is {@link Iterator.valid} and value it is pointing on
 289          *    fullfills the predicate.
 290          *
 291          * @param pred predicate to check should the value be retained
 292          * @return Iterator containing values of subsequent values of seed
 293          */
 294         public virtual Iterator<G> filter (owned Predicate<G> pred) {
 295                 return stream<G> ((state, item, out val) => {
 296                         switch (state) {
 297                         case Stream.YIELD:
 298                                 val = null;
 299                                 return Stream.CONTINUE;
 300                         case Stream.CONTINUE:
 301                                 G g = item.get ();
 302                                 if (pred (g)) {
 303                                         val = item;
 304                                         return Stream.YIELD;
 305                                 } else {
 306                                         val = null;
 307                                         return Stream.CONTINUE;
 308                                 }
 309                         case Stream.END:
 310                                 val = null;
 311                                 return Stream.END;
 312                         default:
 313                                 assert_not_reached ();
 314                         };
 315                 });
 316         }
 317
 318         /**
 319          * Creates a new iterator which contains elements from iterable. The
 320          * first argument states the offset i.e. number of elements the iterator
 321          * skips by default.
 322          *
 323          * Note: In {@link Iterator} implementation resulting iterator is
 324          *    {@link Iterator.valid} when parent iterator is
 325          *    {@link Iterator.valid} and the offset is 0. Using the parent
 326          *    iterator is not allowed before the inner iterator
 327          *    {@link Iterator.next} return false and then it points on its last
 328          *    element.
 329          *
 330          * @param offset the offset to first element the iterator is pointing to
 331          * @param length maximum number of elements iterator may return. Negative
 332          *        value means that the number is unbounded
 333          */
 334         public virtual Iterator<G> chop (int offset, int length = -1) {
 335                 assert (offset >= 0);
 336                 return stream<G> ((state, item, out val) => {
 337                         switch (state) {
 338                         case Stream.YIELD:
 339                                 val = null;
 340                                 if (offset > 0) {
 341                                         return Stream.CONTINUE;
 342                                 } else if (length > 0) {
 343                                         return length != 0 ? Stream.CONTINUE : Stream.END;
 344                                 } else if (length == 0) {
 345                                         return Stream.END;
 346                                 } else {
 347                                         return Stream.CONTINUE;
 348                                 }
 349                         case Stream.CONTINUE:
 350                                 if (offset == 0) {
 351                                         val = item;
 352                                         length--;
 353                                         return Stream.YIELD;
 354                                 } else {
 355                                         val = null;
 356                                         offset--;
 357                                         return Stream.CONTINUE;
 358                                 }
 359                         case Stream.END:
 360                                 val = null;
 361                                 return Stream.END;
 362                         default:
 363                                 assert_not_reached ();
 364                         };
 365                 });
 366         }
 367
 368
 369         /**
 370          * The type of the elements in this collection.
 371          */
 372         public virtual Type element_type { get { return typeof (G); } }
 373
 374         public enum Stream {
 375                 YIELD,
 376                 CONTINUE,
 377                 END
 378         }
 379
 380 }
 381