kqueue.hh

#pragma once

/*
  Copyright (c) 2003-2021 Tommi Junttila
  Released under the GNU Lesser General Public License version 3.
  
  This file is part of bliss.
  
  bliss is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, version 3 of the License.

  bliss is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with bliss.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <new>
#include <cassert>

namespace bliss {

template <class Type>
class KQueue
{
public:
  KQueue();

  ~KQueue();

  void init(const unsigned int N);
  
  bool is_empty() const;

  unsigned int size() const;

  void clear();

  Type front() const;

  Type pop_front();

  void push_front(Type e);

  Type pop_back();

  void push_back(Type e);
private:
  Type *entries, *end;
  Type *head, *tail;
};

template <class Type>
KQueue<Type>::KQueue()
{
  entries = nullptr;
  end = nullptr;
  head = nullptr;
  tail = nullptr;
}

template <class Type>
KQueue<Type>::~KQueue()
{
  delete[] entries;
  entries = nullptr;
  end = nullptr;
  head = nullptr;
  tail = nullptr;
}

template <class Type>
void KQueue<Type>::init(const unsigned int k)
{
  assert(k > 0);
  delete[] entries;
  entries = new Type[k+1];
  end = entries + k + 1;
  head = entries;
  tail = head;
}

template <class Type>
void KQueue<Type>::clear()
{
  head = entries;
  tail = head;
}

template <class Type>
bool KQueue<Type>::is_empty() const
{
  return head == tail;
}

template <class Type>
unsigned int KQueue<Type>::size() const
{
  if(tail >= head)
    return(tail - head);
  return (end - head) + (tail - entries);
}

template <class Type>
Type KQueue<Type>::front() const
{
  assert(head != tail);
  return *head;
}

template <class Type>
Type KQueue<Type>::pop_front()
{
  assert(head != tail);
  Type *old_head = head;
  head++;
  if(head == end)
    head = entries;
  return *old_head;
}

template <class Type>
void KQueue<Type>::push_front(Type e)
{
  if(head == entries)
    head = end - 1;
  else
    head--;
  assert(head != tail);
  *head = e;
}

template <class Type>
void KQueue<Type>::push_back(Type e)
{
  *tail = e;
  tail++;
  if(tail == end)
    tail = entries;
  assert(head != tail);
}

} // namespace bliss