d5/d41/arrayqueue_8cc_source.html

/*

                          Aleph_w


  Data structures & Algorithms

  version 2.0.0b

  https://github.com/lrleon/Aleph-w


  This file is part of Aleph-w library


  Copyright (c) 2002-2026 Leandro Rabindranath Leon


  Permission is hereby granted, free of charge, to any person obtaining a copy

  of this software and associated documentation files (the "Software"), to deal

  in the Software without restriction, including without limitation the rights

  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

  copies of the Software, and to permit persons to whom the Software is

  furnished to do so, subject to the following conditions:


  The above copyright notice and this permission notice shall be included in all

  copies or substantial portions of the Software.


  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

  SOFTWARE.

*/


# include <gtest/gtest.h>


# include <tpl_arrayQueue.H>


# include <ahFunctional.H>


using namespace std;

using namespace testing;

using namespace Aleph;


constexpr size_t N = 17;


struct SimpleQueue : public Test

{

  size_t n = 0;

  ArrayQueue<int> q;


  SimpleQueue()

  {

    for (size_t i = 0; i < N; ++i, ++n)

      q.put(i);

  }


  void print() const

  {

    cout << "q ="; q.for_each([] (auto i) { cout << " " << i; }); cout << endl;

  }


};


struct ComplexQueue : public Test

{

  size_t n = 0;

  ArrayQueue<DynList<int>> q;


  ComplexQueue()

  {

    for (size_t i = 0; i < N; ++i, ++n)

      q.put({ int(i), 1, 2, int(i) });

  }


};


TEST(ArrayQueue, empty_queue)

{

  ArrayQueue<int> q;

  EXPECT_TRUE(q.is_empty());

  EXPECT_EQ(q.size(), 0);

  EXPECT_THROW(q.rear(), range_error);

  EXPECT_THROW(q.front(), range_error);

  EXPECT_THROW(q.rear(2), range_error);

  EXPECT_THROW(q.front(2), range_error);

  EXPECT_THROW(q.rear(q.capacity()), range_error);

  EXPECT_THROW(q.front(q.capacity()), range_error);

  EXPECT_THROW(q.get(), underflow_error);

  EXPECT_THROW(q.getn(0), underflow_error);

  EXPECT_THROW(q.getn(1), underflow_error);

  EXPECT_THROW(q.getn(q.capacity()), underflow_error);

}


TEST(ArrayQueue, fill_and_empty_queue)

{

  ArrayQueue<int> q;

  const size_t N = q.capacity();

  for (int i = 0; i < N; ++i)

    {

      ASSERT_EQ(q.put(i), i);

      ASSERT_EQ(q.rear(), i);

      ASSERT_EQ(q.front(), 0);

    }

  EXPECT_EQ(q.size(), N);

  EXPECT_FALSE(q.is_empty());


  for (int i = 0; i < N; ++i)

    {

      ASSERT_EQ(q.front(i), i);

      ASSERT_EQ(q.rear(i), N - i - 1);

    }


  for (int i = 0; i < N; ++i)

    {

      ASSERT_EQ(q.front(), i);

      ASSERT_EQ(q.rear(), N - 1);

      ASSERT_EQ(q.get(), i);

    }

  EXPECT_TRUE(q.is_empty());

  EXPECT_EQ(q.size(), 0);

  EXPECT_EQ(q.capacity(), N);

}


TEST_F(SimpleQueue, put_and_get_stress)

{

  EXPECT_LT(q.size(), q.capacity());


  // fill until complete initial_cap

  for (int i = q.size(); i < q.capacity(); ++i)

    ASSERT_EQ(q.put(i), i);


  EXPECT_EQ(q.size(), q.capacity());


  for (size_t i = 0; i < q.size(); ++i)

    {

      ASSERT_EQ(q.front(i), i);

      ASSERT_EQ(q.rear(i), q.size() - i - 1);

    }


  // now put more entries

  for (size_t i = q.size(), n = 2*q.size(); i < n; ++i)

    ASSERT_EQ(q.put(i), i);


  EXPECT_EQ(q.size(), q.capacity());


  const size_t nn = q.size();


  // get out the half

  for (size_t i = 0; i < nn/2; ++i)

    ASSERT_EQ(q.get(), i);


  EXPECT_EQ(q.size(), nn/2);


  // test consistency of remaining items

  for (size_t i = 0; i < nn/2; ++i)

    ASSERT_EQ(q.front(i), i + nn/2);


  // now extract them all

  for (size_t i = 0; i < nn/2; ++i)

    ASSERT_EQ(q.get(), i + nn/2);


  EXPECT_EQ(q.size(), 0);

  EXPECT_TRUE(q.is_empty());


  // now we put the queue thus

  //

  // xxx------xxxxxxx

  //

  // where x is an item

  const size_t cap = 16;

  for (size_t i = 0; i < cap; ++i)

    ASSERT_EQ(q.put(i), i);


  for (size_t i = 0; i < cap/4; ++i) // extract a fourth

    ASSERT_EQ(q.get(), i);


  ASSERT_FALSE(q.is_empty());

  ASSERT_EQ(q.size(), 3*cap/4);


  for (size_t i = 0; i < cap/4; ++i) // put them again

    ASSERT_EQ(q.put(i), i);


  for (size_t i = 0; i < 3*cap/4; ++i) // extract and verify the 3/4 oldest

    ASSERT_EQ(q.get(), cap/4 + i);


  // now extract and verify the 1/4 remaining

  for (size_t i = 0; i < cap/4; ++i)

    ASSERT_EQ(q.get(), i);

}


TEST_F(ComplexQueue, put_and_stress_capacity)

{

  EXPECT_LT(q.size(), q.capacity());


  // fill until complete initial_cap

  for (int i = q.size(); i < q.capacity(); ++i)

    {

      auto & l = q.put({int(i), 1, 2, int(i)});

      ASSERT_EQ(l.get_first(), i);

      ASSERT_EQ(l.get_last(), i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  EXPECT_EQ(q.size(), q.capacity());


  for (size_t i = 0; i < q.size(); ++i)

    {

      auto & lf = q.front(i);

      ASSERT_EQ(lf.get_first(), i);

      ASSERT_EQ(lf.get_last(), i);

      ASSERT_EQ(lf.nth(1), 1);

      ASSERT_EQ(lf.nth(2), 2);


      auto & lr = q.rear(i);

      ASSERT_EQ(lr.get_first(), q.size() - i - 1);

      ASSERT_EQ(lr.get_last(),  q.size() - i - 1);

      ASSERT_EQ(lr.nth(1), 1);

      ASSERT_EQ(lr.nth(2), 2);

    }


  // now put more entries

  for (size_t i = q.size(), n = 2*q.size(); i < n; ++i)

    {

      auto & l = q.put({int(i), 1, 2, int(i)});

      ASSERT_EQ(l.get_first(), i);

      ASSERT_EQ(l.get_last(), i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  EXPECT_EQ(q.size(), q.capacity());


  const size_t nn = q.size();


  // get out the half

  for (size_t i = 0; i < nn/2; ++i)

    {

      auto l = q.get();

      ASSERT_EQ(l.get_first(), i);

      ASSERT_EQ(l.get_last(), i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  EXPECT_EQ(q.size(), nn/2);


  // test consistency of remaining items

  for (size_t i = 0; i < nn/2; ++i)

    {

      auto & l = q.front(i);

      ASSERT_EQ(l.get_first(), i + nn/2);

      ASSERT_EQ(l.get_last(), i + nn/2);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  // now extract them all

  for (size_t i = 0; i < nn/2; ++i)

    {

      auto l = q.get();

      ASSERT_EQ(l.get_first(), i + nn/2);

      ASSERT_EQ(l.get_last(), i + nn/2);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  EXPECT_EQ(q.size(), 0);

  EXPECT_TRUE(q.is_empty());


  // now we put the queue thus

  //

  // xxx------xxxxxxx

  //

  // where x is an item

  const size_t cap = 16;

  for (size_t i = 0; i < cap; ++i)

    {

      auto & l = q.put({int(i), 1, 2, int(i)});

      ASSERT_EQ(l.get_first(), i);

      ASSERT_EQ(l.get_last(), i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  for (size_t i = 0; i < cap/4; ++i) // extract a fourth

    {

      auto l = q.get();

      ASSERT_EQ(l.get_first(), i);

      ASSERT_EQ(l.get_last(), i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  ASSERT_FALSE(q.is_empty());

  ASSERT_EQ(q.size(), 3*cap/4);


  for (size_t i = 0; i < cap/4; ++i) // put them again

    {

      auto l = q.put({int(i), 1, 2, int(i)});

      ASSERT_EQ(l.get_first(), i);

      ASSERT_EQ(l.get_last(), i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  for (size_t i = 0; i < 3*cap/4; ++i) // extract and verify the 3/4 oldest

    {

      auto l = q.get();

      ASSERT_EQ(l.get_first(), cap/4 + i);

      ASSERT_EQ(l.get_last(), cap/4 + i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }


  // now extract and verify the 1/4 remaining

  for (size_t i = 0; i < cap/4; ++i)

    {

      auto l = q.get();

      ASSERT_EQ(l.get_first(), i);

      ASSERT_EQ(l.get_last(), i);

      ASSERT_EQ(l.nth(1), 1);

      ASSERT_EQ(l.nth(2), 2);

    }

}


TEST(ArrayQueue, Iterator_on_empty_queue)

{

  ArrayQueue<int> q;

  auto it = q.get_it();

  ASSERT_FALSE(it.has_curr());

  ASSERT_THROW(it.get_curr(), overflow_error);

  ASSERT_THROW(it.next(), overflow_error);

  ASSERT_THROW(it.prev(), underflow_error);

}


static size_t primes[] = {13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,

        61, 67, 71, 73, 79, 83, 89, 97, 197 };


TEST(ArrayQueue, Iterator)

{

  for (size_t i = 0, N = primes[i]; N < 100; ++i, N = primes[i])

    {

      ArrayQueue<int> q;


      for (size_t i = 0; i < N; ++i)

  ASSERT_EQ(q.put(i), i);


      int k = 0;

      for (auto it = q.get_it(); it.has_curr(); it.next(), ++k)

  ASSERT_EQ(it.get_curr(), k);

      ASSERT_EQ(k, N); // test that queue has been traversed


      // extract 1/4 of items

      for (size_t i = 0; i < N/4; ++i)

  ASSERT_EQ(q.get(), i);


      ASSERT_FALSE(q.is_empty());


      // Test iterator again

      k = N/4;

      for (auto it = q.get_it(); it.has_curr(); it.next(), ++k)

  ASSERT_EQ(it.get_curr(), k);

      ASSERT_EQ(k, N); // test that queue has been traversed


      // now put again N/4 for testing iterator on queue of form xxx----xxxxxxx

      for (size_t i = 0; i < N/4; ++i)

  ASSERT_EQ(q.put(i), i);

      ASSERT_EQ(q.size(), N);


      // now test if iterator still works

      k = 0;

      for (auto it = q.get_it(); it.has_curr(); it.next(), ++k)

  ASSERT_EQ(it.get_curr(), (k + N/4) % N);

      ASSERT_EQ(k, N); // test that queue has been traversed


      k = N - 1;

      auto it = q.get_it();

      it.reset_last();

      for (; it.has_curr(); it.prev(), --k)

  ASSERT_EQ(it.get_curr(), (k + N/4) % N);

      ASSERT_EQ(k, -1); // test that queue has been traversed

    }

}


TEST(ArrayQueue, traverse)

{

  for (size_t i = 0, N = primes[i]; N < 100; ++i, N = primes[i])

    {

      ArrayQueue<int> q;


      for (size_t i = 0; i < N; ++i)

  ASSERT_EQ(q.put(i), i);


      int k = 0;

      auto ret = q.traverse([&k] (int i) { return i == k++; });

      ASSERT_TRUE(ret);

      ASSERT_EQ(k, N);


      // extract 1/4 of items

      for (size_t i = 0; i < N/4; ++i)

  ASSERT_EQ(q.get(), i);


      ASSERT_FALSE(q.is_empty());


      // Test traverse

      k = N/4;

      ret = q.traverse([&k] (int i) { return i == k++; });

      ASSERT_TRUE(ret);

      ASSERT_EQ(k, N);


      // now put again N/4 for testing iterator on queue of form xxx----xxxxxxx

      for (size_t i = 0; i < N/4; ++i)

  ASSERT_EQ(q.put(i), i);

      ASSERT_EQ(q.size(), N);


      // now test if iterator still works

      k = 0;

      ret = q.traverse([&k, N] (int i) { return i == (k++ + N/4) % N; });

      ASSERT_TRUE(ret);

      ASSERT_EQ(k, N);


      // finally test partial traverse

      k = 0;

      ret = q.traverse([&k, n = N/4] (int) { return ++k < n; });

      ASSERT_FALSE(ret);

      ASSERT_EQ(k, N/4);

    }

}


TEST(ArrayQueue, copy_operations)

{

  size_t N = 31;

  {

    ArrayQueue<int> q;

    for (size_t i = 0; i < N; ++i)

      ASSERT_EQ(q.put(i), i);


    {

      ArrayQueue<int> qc = q;

      ASSERT_TRUE(eq(q, qc));

    }


    {

      ArrayQueue<int> qc = move(q);

      ASSERT_TRUE(q.is_empty());

      ASSERT_EQ(q.size(), 0);

      int k = 0;

      auto ret = qc.traverse([&k] (int i) { return i == k++; });

      ASSERT_TRUE(ret);

      ASSERT_EQ(k, qc.size());


      q.swap(qc);

      ASSERT_EQ(qc.size(), 0);

      ASSERT_TRUE(qc.is_empty());

      ASSERT_EQ(q.size(), N);

      ASSERT_FALSE(q.is_empty());

    }


    ArrayQueue<int> qc;

    qc = q;

    ASSERT_TRUE(eq(q, qc));


    qc.empty();

    ASSERT_EQ(qc.size(), 0);

    ASSERT_TRUE(qc.is_empty());


    qc = move(q);

    ASSERT_TRUE(q.is_empty());

    ASSERT_EQ(q.size(), 0);

    int k = 0;

    auto ret = qc.traverse([&k] (int i) { return i == k++; });

    ASSERT_TRUE(ret);

    ASSERT_EQ(k, qc.size());

  }

}


ahFunctional.H
Functional programming utilities for Aleph-w containers.

TEST_F
TEST_F(SimpleQueue, put_and_get_stress)
Definition arrayqueue.cc:123

primes
static size_t primes[]
Definition arrayqueue.cc:336

N
constexpr size_t N
Definition arrayqueue.cc:48

Aleph::ArrayQueue
Queue implemented with a single dynamic array.
Definition tpl_arrayQueue.H:79

Aleph::ArrayQueue::front
T & front(const size_t i=0) const
Return the i-th oldest item of the queue.
Definition tpl_arrayQueue.H:294

Aleph::ArrayQueue::traverse
bool traverse(Operation &operation)
Traverse all the elements from the youngest to the oldest and execute operation on each on them.
Definition tpl_arrayQueue.H:322

Aleph::ArrayQueue::getn
T & getn(const size_t i)
Remove the i oldest items of the queue.
Definition tpl_arrayQueue.H:275

Aleph::ArrayQueue::put
T & put(const T &item)
Copy and put an item in the queue.
Definition tpl_arrayQueue.H:183

Aleph::ArrayQueue::rear
T & rear(const size_t i=0) const
Return the i-th youngest item of the queue.
Definition tpl_arrayQueue.H:307

Aleph::ArrayQueue::get
T get()
Remove the oldest item of the queue and return a copy.
Definition tpl_arrayQueue.H:255

Aleph::ArrayQueue::swap
void swap(ArrayQueue &q) noexcept
Swap this with q
Definition tpl_arrayQueue.H:106

Aleph::DynList::get
T get()
Definition htlist.H:1637

Aleph::DynList::get_last
T & get_last() const
Return the last item of the list.
Definition htlist.H:1663

Aleph::DynList::get_first
T & get_first() const
Return the first item of the list.
Definition htlist.H:1675

Aleph::DynList::put
T & put(const T &item)
Definition htlist.H:1532

Aleph::DynList::empty
void empty() noexcept
empty the list
Definition htlist.H:1689

Aleph::HTList::is_empty
constexpr bool is_empty() const noexcept
Return true if list is empty.
Definition htlist.H:523

Aleph::HTList::size
size_t size() const noexcept
Count the number of elements of the list.
Definition htlist.H:1319

Aleph::MemArray::size
size_t size() const noexcept
Return the number of elements.
Definition tpl_memArray.H:268

Aleph::MemArray::capacity
constexpr size_t capacity() const noexcept
The type of element of array.
Definition tpl_memArray.H:265

Aleph::MemArray::is_empty
bool is_empty() const noexcept
Return true is the array is empty.
Definition tpl_memArray.H:271

FunctionalMethods::for_each
void for_each(Operation &operation)
Traverse all the container and performs an operation on each element.
Definition ah-dry.H:685

LocateFunctions::nth
Type & nth(const size_t n)
Return the n-th item of container.
Definition ah-dry.H:267

LocateFunctions::get_it
auto get_it() const
Return a properly initialized iterator positioned at the first item on the container.
Definition ah-dry.H:190

TEST
#define TEST(name)
Definition disjoint_sparse_table_test.cc:95

N
constexpr size_t N
Definition fixedqueue.cc:48

Aleph
Main namespace for Aleph-w library functions.
Definition ah-arena.H:89

Aleph::eq
bool eq(const C1 &c1, const C2 &c2, Eq e=Eq())
Check equality of two containers using a predicate.
Definition ahFunctional.H:960

Aleph::traverse
bool traverse(Node *root, Op op)
Definition tpl_binNodeUtils.H:2879

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

std
STL namespace.

ComplexQueue
Definition arrayqueue.cc:66

ComplexQueue::q
ArrayQueue< DynList< int > > q
Definition arrayqueue.cc:68

ComplexQueue::ComplexQueue
ComplexQueue()
Definition arrayqueue.cc:69

ComplexQueue::n
size_t n
Definition arrayqueue.cc:67

GenericTraverse::traverse
bool traverse(Operation &operation) noexcept(traverse_is_noexcept< Operation >())
Traverse the container via its iterator and performs a conditioned operation on each item.
Definition ah-dry.H:95

SimpleQueue
Definition arrayqueue.cc:51

SimpleQueue::SimpleQueue
SimpleQueue()
Definition arrayqueue.cc:54

SimpleQueue::q
ArrayQueue< int > q
Definition arrayqueue.cc:53

SimpleQueue::print
void print() const
Definition arrayqueue.cc:59

SimpleQueue::n
size_t n
Definition arrayqueue.cc:52

tpl_arrayQueue.H
Circular queue implementations backed by arrays.

l
DynList< int > l
Definition tree-node-common.H:69