TWiki > Doc > CodeExamples > LazyVectorExample	TWiki webs: Dev | Doc | Main | TWiki | Sandbox
	Doc . { Changes | Index | Search | Go }

Using a technique known as memoization, the elements of the LazyVector are saved for future use once they've been computed. So you only pay the cost of computation the first time you access a given index.

If you want your LazyVector to end eventually, your generator function should throw ArrayIndexOutOfBoundsException when it's been called too many times.

<Any T> LazyVector<T> makeLV(()->T func) = new LazyVector(elements: cast(new T[10]),
                      length: 0,
                      generator: func);
                     

class LazyVector<T> extends Vector<T> {
  boolean forced = false;
  ()->T generator;
  Vector<T> adds = makeVector(5);

  void raw_add(T element) {
    if(this.elements==null) {
      this.elements = cast(new T[10]);
      this.length = 0;
    }
    
    if (this.length >= this.elements.length)
      this.elements = this.elements.resize(this.length * 2);
    
    this.elements.set(this.length, element);
    this.length = this.length+1;
  }
  
  void force(int index = -1) {
    while(!this.forced && (index < 0 || this.length <= index)) {
      try {
   this.raw_add((this.generator)());
      } catch (ArrayIndexOutOfBoundsException e) {
   this.adds.foreach(T item => this.raw_add(item));
   this.forced = true;
   break;
      }
    }
  }

  boolean isForced() {
    return this.forced;
  }

  size() {
    if (!this.forced)
      this.force();
    return this.length;
  }

  add(item) {
    if (this.forced) {
      this.raw_add(item);
    } else {
      this.adds.add(item);
    }
  }

  get(index) {
    if (!this.forced)
      this.force(index);
    return this.elements[index];
  }

  set(index, value) {
    if (!this.forced)
      this.force(index);
    this.elements[index] = value;
  }

  foreach(func) {
    for(int i = 0; i < this.length || !this.forced; i++) {
      func(this[i]);
    }
  }

  map<C,T,U>(func) {
    int currentIndex = 0;
    LazyVector<U> lvec = makeLV(() => {
      T item = this[currentIndex];
      currentIndex++;
      return func(item);
    });    
    return lvec;
  }


 filter<C,T>(test) {
   int currentIndex = 0;
   LazyVector<T> lvec = makeLV(() => {
     T item = this[currentIndex];
     while (!(test(item))) {
       item = this[++currentIndex];
     }
     currentIndex++;
     return item;
   }
   );
   return lvec;
 } 

}

void indexError() {
  throw new ArrayIndexOutOfBoundsException();
}

//Temporary replacement for assert. :-)
void shouldBe(boolean res, String err = "Error!") {
  if (!res)
    throw new RuntimeException(err);
}
  
main(args) {
  LazyVector<int> ones = makeLV(()=> 1);
  shouldBe(ones[0] == 1);
  shouldBe(ones[250] == 1);
  shouldBe(ones[300] == 1);
//   try {
//     size(ones);
//   } catch (StackOverflowError e) {
//     ones = cast(null); //Let ones be GC'd. Not safe for general use.
//   } catch (OutOfMemoryError e) {
//     ones = cast(null); //Let ones be GC'd. Not safe for general use.
//   }
  int->()->int natsFrom = int start => {
    return () => {return start++;};
  };
  LazyVector<int> natsFromFive = makeLV(natsFrom(5));
  shouldBe(natsFromFive[0] == 5);
  shouldBe(natsFromFive[1] == 6);
  shouldBe(natsFromFive[2] == 7);
  LazyVector<int> evens = makeLV(natsFrom(1)).filter(int num => num % 2 == 0);
  shouldBe(evens[0] == 2, toString(evens[0]));
  shouldBe(evens[1] == 4, toString(evens[1]));
  shouldBe(evens[2] == 6);
  LazyVector<String> toStrings = evens.map(int i => toString(i));
  for(int i = 0; i < 10; i++) {
    println(toStrings[i]);
  }
  shouldBe(equals(toStrings[0],"2"), toStrings[0]);
  shouldBe(equals(toStrings[1],"4"), toStrings[1]);
  shouldBe(equals(toStrings[2],"6"), toStrings[2]);

  int->()->int intsTo9 = int start => {
    return () => {
      if (start > 9)
        indexError();
//    throw new ArrayIndexOutOfBoundsException();
      return start++;
    };
  };
  
  LazyVector<int> finiteSeq = makeLV(intsTo9(0));

  println("Sizing...");
  shouldBe(size(finiteSeq) == 10);
  shouldBe(finiteSeq[0] == 0);
  shouldBe(finiteSeq[9] == 9);
  try {
    finiteSeq[10];
    throw new RuntimeException("Shouldn't get here!");
  } catch (ArrayIndexOutOfBoundsException e) {
    //pass
  }
  println("Tests complete");
    
}

-- BrynKeller - 24 Jul 2002

This is a nice example. I had two concerns:

LazyVector extends Vector, but much of the code seems to be duplicated (e.g. raw_add looks very much like Vector's add). The need to use the unsafe cast, which generated runtime bugs in the begining of writing this class. Here is a slightly modified version: it contains a Vector instead of extending it, so it can delegate the addition work instead of duplicating it. In addition it does not need cast: we only add elements to the vector when they are computed, and then they have the right type.

It is porbably possible to improve it further, but you will do that better than me. In particular I don't really understand what adds is. My class implements Sequence and not list because it does not implement remove (at least). Therefore I add to declare add, not just implement it. Feel free to change that.

Here is the class. The unchanged tests run correctly on it. Note that makeLV should not be needed anymore, it could be replaced with new LazyVector?(...).

<Any T> LazyVector<T> makeLV(()->T func) = new LazyVector(generator: func);
                     

class LazyVector<T> implements Sequence<T> finally implements Collection<T> {
  Vector<T> elements = makeVector(10);
  boolean forced = false;
  ()->T generator;
  Vector<T> adds = makeVector(5);

  void raw_add(T element) {
    this.elements.add(element);
  }
  
  void force(int index = -1) {
    while(!this.forced && (index < 0 || this.elements.size() <= index)) {
      try {
   this.raw_add((this.generator)());
      } catch (ArrayIndexOutOfBoundsException e) {
   this.adds.foreach(T item => this.raw_add(item));
   this.forced = true;
   break;
      }
    }
  }

  boolean isForced() {
    return this.forced;
  }

  size() {
    if (!this.forced)
      this.force();
    return this.elements.size();
  }

  void add(T item) {
    if (this.forced) {
      this.raw_add(item);
    } else {
      this.adds.add(item);
    }
  }

  get(index) {
    if (!this.forced)
      this.force(index);
    return this.elements[index];
  }

  set(index, value) {
    if (!this.forced)
      this.force(index);
    this.elements[index] = value;
  }

  foreach(func) {
    for(int i = 0; i < this.size() || !this.forced; i++) {
      func(this[i]);
    }
  }

  map<C,T,U>(func) {
    int currentIndex = 0;
    LazyVector<U> lvec = makeLV(() => {
      T item = this[currentIndex];
      currentIndex++;
      return func(item);
    });    
    return lvec;
  }


 filter<C,T>(test) {
   int currentIndex = 0;
   LazyVector<T> lvec = makeLV(() => {
     T item = this[currentIndex];
     while (!(test(item))) {
       item = this[++currentIndex];
     }
     currentIndex++;
     return item;
   }
   );
   return lvec;
 } 

}

-- DanielBonniot - 25 Jul 2002

Daniel wrote:

This is a nice example. I had two concerns: LazyVector extends Vector, but much of the code seems to be duplicated (e.g. raw_add looks very much like Vector's add). The need to use the unsafe cast, which generated runtime bugs in the begining of writing this class.

The only duplicated code is that raw_add method, which should really be eliminated, and a call to super.add() used in place of the call to raw_add. I'll make this change later. The unsafe cast is needed to initialize Vector 's elements member, not for LazyVector. Using super in the constructor to initialize the Vector parts would solve this too - but we don't have constructors, and Vector doesn't define an init method that we can use in this fashion. If we had requirements (say, an existing library which only accepted Vector arguments) which dictated that we must make LazyVector a subclass of Vector , how can we initialize Vector.elements without an unsafe cast? My biggest concern with making it a subclass of Vector is that it can break the contract of size (because it may diverge). This concern applies to making LazyVector implement Collection as well, however. I don't see any good solution for this problem. Also:

It is probably possible to improve it further, but you will do that better than me. In particular I don't really understand what adds is. My class implements Sequence and not list because it does not implement remove (at least). Therefore I add to declare add, not just implement it. Feel free to change that. I should have added a remove method, I'll do that soon also. The adds member is where we keep things that have been added to the LazyVector before it's been completely forced. So, for example:

  LazyVector<int> finiteSeq = makeLV(intsTo9(0));
  finiteSeq.add(35); //Still no elements have been computed
  shouldBe(finiteSeq[0] == 0); //Computed first element
  shouldBe(finiteSeq[9] == 9); //Computed all computable elements 
  shouldBe(finiteSeq[10] == 35); //Appended things from 'adds'.

I'll add this to the tests.

-- BrynKeller - 25 Jul 2002