queue.h

// This file if part of the llir-opt project.
// Licensing information can be found in the LICENSE file.
// (C) 2018 Nandor Licker. All rights reserved.
 
#pragma once
 
#include <vector>
 
 
 
template<typename T>
class Queue final {
public:
  void Push(ID<T> item)
  {
    if (item >= dedup_.size()) {
      dedup_.resize(item + 1);
    }
    if (!dedup_[item]) {
      dedup_[item] = true;
      placeQ_.push_back(item);
    }
  }
 
  ID<T> Pop()
  {
    if (takeQ_.empty()) {
      takeQ_.reserve(placeQ_.size());
      for (size_t i = 0, n = placeQ_.size(); i < n; ++i) {
        takeQ_.push_back(placeQ_[n - i - 1]);
      }
      placeQ_.clear();
    }
 
    const auto &item = takeQ_.back();
    takeQ_.pop_back();
    dedup_[item] = false;
    return item;
  }
 
  bool Empty() const
  {
    return takeQ_.empty() && placeQ_.empty();
  }
 
  size_t Size() const { return placeQ_.size() + takeQ_.size(); }
 
private:
  std::vector<ID<T>> placeQ_;
  std::vector<ID<T>> takeQ_;
  std::vector<bool> dedup_;
};