class TestFilter extends TokenFilter {
    Random r;
    public TestFilter(TokenStream input, int seed) {
      super(input);
      r = new Random(seed);
    }
    boolean done = false;

  }

  class T1 extends TestFilter {
    public T1(TokenStream input, int seed) {
      super(input, seed);
    }

    LinkedList<Token> queue = new LinkedList<Token>();
    Token single = new Token();

    @Override
    public Token next() throws IOException {
      if (done) {
        if (queue.isEmpty()) return null;
        return queue.removeFirst();
      }

      if (queue.isEmpty() && r.nextBoolean()) {
        // Token t = input.next(single);
        Token t = r.nextBoolean() ? input.next(new Token()) : input.next();
        done = t==null;
        return t;
      }

      while(!done && (queue.isEmpty() || r.nextBoolean())) {
        Token t = r.nextBoolean() ? input.next(new Token()) : input.next();
        done = t==null;
        if (t!=null) queue.add(t);
      }
      if (queue.isEmpty()) return null;
      return queue.removeFirst();
    }
  }

  class T2 extends TestFilter {
    public T2(TokenStream input, int seed) {
      super(input, seed);
    }

    LinkedList<Token> queue = new LinkedList<Token>();

    @Override
    public Token next(Token target) throws IOException {
      if (done) {
        if (queue.isEmpty()) return null;
        return queue.removeFirst();
      }

      if (queue.isEmpty() && r.nextBoolean()) {
        Token t = input.next(target);
        done = t==null;
        return t;
      }

      while(!done && (queue.isEmpty() || r.nextBoolean())) {
        Token t = r.nextBoolean() ? input.next(new Token()) : input.next();
        done = t==null;
        if (t!=null) queue.add(t);
      }
      
      if (queue.isEmpty()) return null;
      return queue.removeFirst();
    }
  }

  class T3 extends TestFilter {
    public T3(TokenStream input, int seed) {
      super(input, seed);
    }

    LinkedList<AttributeSource.State> queue = new LinkedList<AttributeSource.State>();

    @Override
    public boolean incrementToken() throws IOException {
      // if we've read all the input, empty the queue
      if (done) {
        if (queue.isEmpty()) return false;
        restoreState(queue.removeFirst());
        return true;
      }

      // if the queue is empty, sometimes just bypass it and return the next token
      if (queue.isEmpty() && r.nextBoolean()) {
        done = !input.incrementToken();
        return !done;
      }

      // add a random number of items to the queue (at least 1 if the queue is empty)
      while(!done && (queue.isEmpty() || r.nextBoolean())) {
        done = !input.incrementToken();
        if (!done)
          queue.add(captureState());
      }

      if (queue.isEmpty()) return false;
      restoreState(queue.removeFirst());      
      return true;
    }

  }

  public void testBuffering() throws IOException {
    Random r = new Random(0);
    // TokenStream ts = new T1(new T2(new T3(new WhitespaceTokenizer(new StringReader(s)),3),2),1);

    for (int iter=0; iter<1000000; iter++) {
      StringBuilder input = new StringBuilder();
      int n = r.nextInt(10);
      while(n-->=0) input.append(Integer.toString(n)).append(' ');
      String s = input.toString();


      TokenStream source = new WhitespaceTokenizer(new StringReader(s));
      TokenStream ts = source;
      int depth = r.nextInt(5)+1;
      for (int i=0; i<depth; i++) {
        switch(r.nextInt(3)) {
          case 0: ts = new T1(ts,i); break;
          case 1: ts = new T2(ts,i); break;
          case 2: ts = new T3(ts,i); break;
        }
      }

      TermAttribute termAtt = (TermAttribute)ts.getAttribute(TermAttribute.class);
      ts.reset();

      StringBuilder sb = new StringBuilder();
      while (ts.incrementToken()) {
        sb.append(termAtt.term()).append(' ');
      }

      assertEquals(s, sb.toString());
    }
  }