gistfile1.hh

<?hh // strict

class Queue<T> {
  private int $cleanupThreshold = 100;
  private int $pos = 0;
  private Vector<T> $items;

  public function __construct(?Traversable<T> $init) {
    $this->items = Vector {};
    if ($init !== null) {
      $this->items->addAll($init);
    }
  }

  public function setCleanupThreshold(int $threshold): this {
    $this->cleanupThreshold = $threshold;
    return $this;
  }

  public function count(): int {
    return $this->items->count() - $this->pos;
  }

  public function isEmpty(): bool {
    return $this->items->count() <= $this->pos;
  }

  public function enqueue(T $item): this {
    $this->items->add($item);

    return $this;
  }

  public function dequeue(): T {
    if ($this->isEmpty()) {
      throw new Exception('No more items in Queue!');
    }

    $item = $this->items->at($this->pos);
    $this->pos++;

    if ($this->pos > $this->cleanupThreshold && $this->pos > $this->items->count() / 2) {
      $items = Vector {};
      $items->reserve($this->items->count() - $this->pos);
      for(; $this->pos < $this->items->count(); $this->pos++) {
        $items->add($this->items->at($this->pos));
      }
      $this->items = $items;
      $this->pos = 0;
    }

    return $item;
  }
}