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 void 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.
  56          *
  57          * ''{@link Iterator} implementation:'' Operation moves the iterator
  58          * to last element in iteration. If iterator points at some element it
  59          * will be included in iteration.
  60          */
  61         public new abstract void foreach (ForallFunc<G> f);
  62
  63         /**
  64          * Stream function is an abstract function allowing writing many
  65          * operations.
  66          *
  67          * The stream function accepts three parameter:
  68          *
  69          *   1. state. It is usually the last returned value from function but
  70          *      it may be {@link Stream.END} when {@link Stream.CONTINUE} was
  71          *      returned and there was no more elements.
  72          *   1. input. It is valid only if first argument is
  73          *      {@link Stream.CONTINUE}
  74          *   1. output. It is valid only if result is Stream.YIELD
  75          *
  76          * It may return one of 3 results:
  77          *
  78          *   1. {@link Stream.YIELD}. It means that value was yielded and can
  79          *      be passed to outgoing iterator.
  80          *   1. {@link Stream.CONTINUE}. It means that the function needs to be
  81          *      called with next element or with {@link Stream.END} if it is
  82          *      end of stream). If the state element was Stream.END during the
  83          *      current iteration function ''must not'' return {@link Stream.CONTINUE}
  84          *   1. Stream.END. It means that the last argument was yielded.
  85          *
  86          * If the function yields the value immediately then the returning iterator
  87          * is {@link Iterator.valid} and points to this value as well as in case when the
  88          * parent iterator is {@link Iterator.valid} and function yields
  89          * after consuming 1 input. In other case returned iterator is invalid.
  90          *
  91          * Note: In {@link Iterator} implementation: if iterator is
  92          *    {@link Iterator.valid} the current value should be fed
  93          *    immediately to function if during initial call function returns
  94          *    {@link Stream.CONTINUE}. The parent iterator cannot be used before
  95          *    the functions return {@link Stream.END} afterwards it points on the
  96          *    last element consumed.
  97          *
  98          * @param f function generating stream
  99          * @return iterator containing values yielded by stream
 100          */
 101         public virtual Iterator<A> stream<A> (owned StreamFunc<G, A> f) {
 102                 Iterator<G>? self;
 103                 Iterable<G>? iself;
 104                 // Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
 105                 if ((self = this as Iterator<G>) != null) {
 106                         Traversable.Stream str;
 107                         Lazy<A>? initial = null;
 108                         bool need_next = true;
 109                         str = f (Stream.YIELD, null, out initial);
 110                         switch (str) {
 111                         case Stream.CONTINUE:
 112                                 if (self.valid) {
 113                                         str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get ();}), out initial);
 114                                         switch (str) {
 115                                         case Stream.YIELD:
 116                                         case Stream.CONTINUE:
 117                                                 break;
 118                                         case Stream.END:
 119                                                 return Iterator.unfold<A> (() => {return null;});
 120                                         default:
 121                                                 assert_not_reached ();
 122                                         }
 123                                 }
 124                                 break;
 125                         case Stream.YIELD:
 126                                 if (self.valid)
 127                                         need_next = false;
 128                                 break;
 129                         case Stream.END:
 130                                 return Iterator.unfold<A> (() => {return null;});
 131                         default:
 132                                 assert_not_reached ();
 133                         }
 134                         return Iterator.unfold<A> (() => {
 135                                 Lazy<A>? val = null;
 136                                 if (str != Stream.CONTINUE)
 137                                         str = f (Traversable.Stream.YIELD, null, out val);
 138                                 while (str == Stream.CONTINUE) {
 139                                         if (need_next) {
 140                                                 if (!self.next ()) {
 141                                                         str = f (Traversable.Stream.END, null, out val);
 142                                                         assert (str != Traversable.Stream.CONTINUE);
 143                                                         break;
 144                                                 }
 145                                         } else {
 146                                                 need_next = true;
 147                                         }
 148                                         str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get ();}), out val);
 149                                 }
 150                                 switch (str) {
 151                                 case Stream.YIELD:
 152                                         return val;
 153                                 case Stream.END:
 154                                         return null;
 155                                 default:
 156                                         assert_not_reached ();
 157                                 }
 158                         }, initial);
 159                 } else if ((iself = this as Iterable<G>) != null) {
 160                         return iself.iterator().stream<A> ((owned) f);
 161                 } else {
 162                         assert_not_reached ();
 163                 }
 164         }
 165
 166         /**
 167          * Standard aggregation function.
 168          *
 169          * It takes a function, seed and first element, returns the new seed and
 170          * progress to next element when the operation repeats.
 171          *
 172          * Note: Default implementation uses {@link foreach}.
 173          *
 174          * Note: In {@link Iterator} implementation operation moves the
 175          *    iterator to last element in iteration. If iterator is
 176          *    {@link Iterator.valid} the current element will be considered
 177          *    as well.
 178          *
 179          */
 180         public virtual A fold<A> (FoldFunc<A, G> f, owned A seed)
 181         {
 182                 this.foreach ((item) => {seed = f ((owned) item, (owned) seed);});
 183                 return (owned) seed;
 184         }
 185
 186         /**
 187          * Produces an iterator pointing at elements generated by function passed.
 188          *
 189          * Iterator is lazy evaluated but value is force-evaluated when
 190          * iterator moves to next element. ({@link Iterator.next})
 191          *
 192          * Note: Default implementation uses {@link stream}.
 193          *
 194          * Note: In {@link Iterator} implementation if the parent iterator is
 195          *    {@link Iterator.valid} so is the returned one. Using the parent
 196          *    iterator is not allowed before the inner iterator {@link Iterator.next}
 197          *    return false and then it points on its last element.
 198          *    The resulting iterator is {@link Iterator.valid} if the parent
 199          *    iterator is.
 200          *
 201          * @param f Mapping function
 202          * @return Iterator listing mapped value
 203          */
 204         public virtual Iterator<A> map<A> (MapFunc<A, G> f) {
 205                 return stream<A>((state, item, out val) => {
 206                         switch (state) {
 207                         case Stream.YIELD:
 208                                 val = null;
 209                                 return Stream.CONTINUE;
 210                         case Stream.CONTINUE:
 211                                 val = new Lazy<A>(() => {
 212                                         A tmp = item.get ();
 213                                         item = null;
 214                                         return (f ((owned)tmp));
 215                                 });
 216                                 return Stream.YIELD;
 217                         case Stream.END:
 218                                 val = null;
 219                                 return Stream.END;
 220                         default:
 221                                 assert_not_reached ();
 222                         }
 223                 });
 224         }
 225
 226         /**
 227          * Creates a new iterator that is initially pointing to seed. Then
 228          * subsequent values are obtained after applying the function to previous
 229          * value and the subsequent items.
 230          *
 231          * The resulting iterator is always valid and it contains the seed value.
 232          *
 233          * Note: Default implementation uses {@link stream}.
 234          *
 235          * Note: When the method is called on {@link Iterator} using the parent
 236          *    iterator is not allowed befor the inner iterator
 237          *    {@link Iterator.next} return false and then it points on its last
 238          *    element. The resulting iterator is {@link Iterator.valid}.
 239          *
 240          * @param f Folding function
 241          * @param seed original seed value
 242          * @return Iterator containing values of subsequent values of seed
 243          */
 244         public virtual Iterator<A> scan<A> (FoldFunc<A, G> f, owned A seed) {
 245                 bool seed_emitted = false;
 246                 return stream<A>((state, item, out val) => {
 247                         switch (state) {
 248                         case Stream.YIELD:
 249                                 if (seed_emitted) {
 250                                         val = null;
 251                                         return Stream.CONTINUE;
 252                                 } else {
 253                                         val = new Lazy<A>.from_value (seed);
 254                                         seed_emitted = true;
 255                                         return Stream.YIELD;
 256                                 }
 257                         case Stream.CONTINUE:
 258                                 val = new Lazy<A> (() => {
 259                                         A tmp = item.get ();
 260                                         item = null;
 261                                         seed = f ((owned) tmp, (owned) seed);
 262                                         return seed;
 263                                 });
 264                                 return Stream.YIELD;
 265                         case Stream.END:
 266                                 val = null;
 267                                 return Stream.END;
 268                         default:
 269                                 assert_not_reached ();
 270                         }
 271                 });
 272         }
 273
 274         /**
 275          * Creates a new iterator that contains only values that fullfills the
 276          * predicate.
 277          *
 278          * Note: When the method is called on {@link Iterator} using the parent
 279          *    iterator is not allowed befor the inner iterator
 280          *    {@link Iterator.next} return false and then it points on its last
 281          *    element. The resulting iterator is {@link Iterator.valid} if parent
 282          *    iterator is {@link Iterator.valid} and value it is pointing on
 283          *    fullfills the predicate.
 284          *
 285          * @param f Folding function
 286          * @return Iterator containing values of subsequent values of seed
 287          */
 288         public virtual Iterator<G> filter (owned Predicate<G> pred) {
 289                 return stream<G> ((state, item, out val) => {
 290                         switch (state) {
 291                         case Stream.YIELD:
 292                                 val = null;
 293                                 return Stream.CONTINUE;
 294                         case Stream.CONTINUE:
 295                                 G g = item.get ();
 296                                 if (pred (g)) {
 297                                         val = item;
 298                                         return Stream.YIELD;
 299                                 } else {
 300                                         val = null;
 301                                         return Stream.CONTINUE;
 302                                 }
 303                         case Stream.END:
 304                                 val = null;
 305                                 return Stream.END;
 306                         default:
 307                                 assert_not_reached ();
 308                         };
 309                 });
 310         }
 311
 312         /**
 313          * Creates a new iterator which contains elements from iterable. The
 314          * first argument states the offset i.e. number of elements the iterator
 315          * skips by default.
 316          *
 317          * Note: In {@link Iterator} implementation resulting iterator is
 318          *    {@link Iterator.valid} when parent iterator is
 319          *    {@link Iterator.valid} and the offset is 0. Using the parent
 320          *    iterator is not allowed before the inner iterator
 321          *    {@link Iterator.next} return false and then it points on its last
 322          *    element.
 323          *
 324          * @param offset the offset to first element the iterator is pointing to
 325          * @param length maximum number of elements iterator may return. Negative
 326          *        value means that the number is unbounded
 327          */
 328         public virtual Iterator<G> chop (int offset, int length = -1) {
 329                 assert (offset >= 0);
 330                 return stream<G> ((state, item, out val) => {
 331                         switch (state) {
 332                         case Stream.YIELD:
 333                                 val = null;
 334                                 if (offset > 0) {
 335                                         return Stream.CONTINUE;
 336                                 } else if (length > 0) {
 337                                         length--;
 338                                         return length != 0 ? Stream.CONTINUE : Stream.END;
 339                                 } else if (length == 0) {
 340                                         return Stream.END;
 341                                 } else {
 342                                         return Stream.CONTINUE;
 343                                 }
 344                         case Stream.CONTINUE:
 345                                 if (offset == 0) {
 346                                         val = item;
 347                                         return Stream.YIELD;
 348                                 } else {
 349                                         val = null;
 350                                         offset--;
 351                                         return Stream.CONTINUE;
 352                                 }
 353                         case Stream.END:
 354                                 val = null;
 355                                 return Stream.END;
 356                         default:
 357                                 assert_not_reached ();
 358                         };
 359                 });
 360         }
 361
 362
 363         /**
 364          * The type of the elements in this collection.
 365          */
 366         public virtual Type element_type { get { return typeof (G); } }
 367
 368         public enum Stream {
 369                 YIELD,
 370                 CONTINUE,
 371                 END
 372         }
 373
 374 }
 375