d1/d02/dlink_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 <dlink.H>


using namespace std;

using namespace testing;

using namespace Aleph;


TEST(Dlink, Well_initialized)

{

  Dlink l;

  EXPECT_TRUE(l.is_empty());

  EXPECT_EQ(l.get_next(), &l);

  EXPECT_EQ(l.get_prev(), &l);

}


TEST(Dlink, Operations_with_empty_list)

{

  Dlink l, laux;

  l.swap(laux);                              // swap between empty list

  EXPECT_TRUE(l.is_empty());

  EXPECT_EQ(l.get_next(), &l);

  EXPECT_EQ(l.get_prev(), &l);

  EXPECT_TRUE(laux.is_empty());

  EXPECT_EQ(laux.get_next(), &laux);

  EXPECT_EQ(laux.get_prev(), &laux);


  l = move(laux);                           // assignment of rvalue empty list

  EXPECT_TRUE(l.is_empty());

  EXPECT_EQ(l.get_next(), &l);

  EXPECT_EQ(l.get_prev(), &l);

  EXPECT_TRUE(laux.is_empty());

  EXPECT_EQ(laux.get_next(), &laux);

  EXPECT_EQ(laux.get_prev(), &laux);


  l = laux;                            // assignment of empty list

  EXPECT_TRUE(l.is_empty());

  EXPECT_EQ(l.get_next(), &l);

  EXPECT_EQ(l.get_prev(), &l);

  EXPECT_TRUE(laux.is_empty());

  EXPECT_EQ(laux.get_next(), &laux);

  EXPECT_EQ(laux.get_prev(), &laux);


  l = laux;                            // assignment of rvalue empty list

  EXPECT_TRUE(l.is_empty());

  EXPECT_EQ(l.get_next(), &l);

  EXPECT_EQ(l.get_prev(), &l);

  EXPECT_TRUE(laux.is_empty());

  EXPECT_EQ(laux.get_next(), &laux);

  EXPECT_EQ(laux.get_prev(), &laux);


  {

    Dlink llaux(move(laux));       // copy constructor of empty rvalue list

    EXPECT_TRUE(laux.is_empty());

    EXPECT_EQ(laux.get_next(), &laux);

    EXPECT_EQ(laux.get_prev(), &laux);

    EXPECT_TRUE(llaux.is_empty());

    EXPECT_EQ(llaux.get_next(), &llaux);

    EXPECT_EQ(llaux.get_prev(), &llaux);

  }


  {

    Dlink llaux(laux);   // copy constructor of empty list

    EXPECT_TRUE(laux.is_empty());

    EXPECT_EQ(laux.get_next(), &laux);

    EXPECT_EQ(laux.get_prev(), &laux);

    EXPECT_TRUE(llaux.is_empty());

    EXPECT_EQ(llaux.get_next(), &llaux);

    EXPECT_EQ(llaux.get_prev(), &llaux);

  }


  l.append_list(&laux);

  EXPECT_TRUE(l.is_empty());

  EXPECT_TRUE(laux.is_empty());


  l.insert_list(&laux);

  EXPECT_TRUE(l.is_empty());

  EXPECT_TRUE(laux.is_empty());

}


TEST(Dlink, Basic_operations)

{

  Dlink l, l1, l2;


  l.reverse_list();               // revese of empty list

  EXPECT_TRUE(l.is_empty());


  l.append(&l2);

  EXPECT_FALSE(l.is_empty());

  EXPECT_TRUE(l.is_unitarian());

  EXPECT_TRUE(l.is_unitarian_or_empty());

  EXPECT_EQ(l.get_first(), &l2);

  EXPECT_EQ(l.get_first(), l.get_next());

  EXPECT_EQ(l.get_last(), &l2);

  EXPECT_EQ(l.get_last(), l.get_prev());


  l.reverse_list();                // reverse with one item

  EXPECT_EQ(l.get_first(), &l2);

  EXPECT_EQ(l.get_first(), l.get_next());

  EXPECT_EQ(l.get_last(), &l2);

  EXPECT_EQ(l.get_last(), l.get_prev());


  l.insert(&l1);

  EXPECT_FALSE(l.is_unitarian());

  EXPECT_FALSE(l.is_unitarian_or_empty());

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_EQ(l.get_last(), &l2);


  l.reverse_list();                // reverse of list of two items

  EXPECT_EQ(l.get_first(), &l2);

  EXPECT_EQ(l.get_last(), &l1);


  l.reverse_list();


  EXPECT_EQ(l.remove_first(), &l1);

  EXPECT_EQ(l.get_first(), &l2);

  EXPECT_EQ(l.get_last(), &l2);

  EXPECT_FALSE(l.is_empty());

  EXPECT_TRUE(l.is_unitarian());

  EXPECT_TRUE(l.is_unitarian_or_empty());


  l.insert(&l1);

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_FALSE(l.is_empty());

  EXPECT_FALSE(l.is_unitarian());

  EXPECT_FALSE(l.is_unitarian_or_empty());

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_EQ(l.get_last(), &l2);


  EXPECT_EQ(l.remove_last(), &l2);

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_EQ(l.get_last(), &l1);

  EXPECT_FALSE(l.is_empty());

  EXPECT_TRUE(l.is_unitarian());

  EXPECT_TRUE(l.is_unitarian_or_empty());


  l.append(&l2);

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_FALSE(l.is_empty());

  EXPECT_FALSE(l.is_unitarian());

  EXPECT_FALSE(l.is_unitarian_or_empty());

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_EQ(l.get_last(), &l2);


  l1.del();

  EXPECT_TRUE(l1.is_empty());

  EXPECT_TRUE(l.is_unitarian());

  EXPECT_EQ(l.get_first(), &l2);


  l.insert(&l1);

  EXPECT_FALSE(l.is_empty());

  EXPECT_FALSE(l.is_unitarian());

  EXPECT_FALSE(l.is_unitarian_or_empty());

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_EQ(l.get_last(), &l2);


  l2.del();

  EXPECT_TRUE(l2.is_empty());

  EXPECT_TRUE(l.is_unitarian());

  EXPECT_EQ(l.get_first(), &l1);


  l.append(&l2);

  EXPECT_FALSE(l.is_empty());

  EXPECT_FALSE(l.is_unitarian());

  EXPECT_FALSE(l.is_unitarian_or_empty());

  EXPECT_EQ(l.get_first(), &l1);

  EXPECT_EQ(l.get_last(), &l2);

}


TEST(Dlink, Very_simple_iterator_operations)

{

  Dlink l;

  Dlink::Iterator it = l;


  EXPECT_FALSE(it.has_curr());

  EXPECT_THROW(it.get_curr(), overflow_error);

  EXPECT_FALSE(it.is_last());

  EXPECT_FALSE(it.is_in_first());


  it.reset_first();

  EXPECT_FALSE(it.has_curr());

  EXPECT_THROW(it.get_curr(), overflow_error);

  EXPECT_FALSE(it.is_last());

  EXPECT_FALSE(it.is_in_first());


  it.reset_last();

  EXPECT_FALSE(it.has_curr());

  EXPECT_THROW(it.get_curr(), overflow_error);

  EXPECT_FALSE(it.is_last());

  EXPECT_FALSE(it.is_in_first());

}


struct List_of_5_nodes : public testing::Test

{

  Dlink list, l1, l2, l3, l4, l5;


  List_of_5_nodes()

  {

    list.append(&l1);

    list.append(&l2);

    list.append(&l3);

    list.append(&l4);

    list.append(&l5);

  }


};


TEST_F(List_of_5_nodes, Iterator)

{

  Dlink::Iterator it = list;


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

    {

      EXPECT_TRUE(it.has_curr());

      EXPECT_TRUE(it.is_in_first());

      EXPECT_EQ(it.get_curr(), &l1);

      it.next();


      EXPECT_TRUE(it.has_curr());

      EXPECT_EQ(it.get_curr(), &l2);

      it.next();


      EXPECT_TRUE(it.has_curr());

      EXPECT_EQ(it.get_curr(), &l3);

      it.next();


      EXPECT_TRUE(it.has_curr());

      EXPECT_EQ(it.get_curr(), &l4);

      EXPECT_FALSE(it.is_last());

      it.next();


      EXPECT_TRUE(it.has_curr());

      EXPECT_TRUE(it.is_in_last());

      EXPECT_EQ(it.get_curr(), &l5);

      EXPECT_TRUE(it.is_last());

      it.next();


      EXPECT_FALSE(it.has_curr());

      EXPECT_THROW(it.get_curr(), overflow_error);


      it.reset_first();

    }


  it.reset_last();

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

    {

      EXPECT_TRUE(it.has_curr());

      EXPECT_TRUE(it.is_in_last());

      EXPECT_EQ(it.get_curr(), &l5);

      it.prev();


      EXPECT_TRUE(it.has_curr());

      EXPECT_EQ(it.get_curr(), &l4);

      it.prev();


      EXPECT_TRUE(it.has_curr());

      EXPECT_EQ(it.get_curr(), &l3);

      it.prev();


      EXPECT_TRUE(it.has_curr());

      EXPECT_EQ(it.get_curr(), &l2);

      EXPECT_FALSE(it.is_last());

      it.prev();


      EXPECT_TRUE(it.has_curr());

      EXPECT_EQ(it.get_curr(), &l1);

      EXPECT_TRUE(it.is_in_first());

      it.prev();


      EXPECT_FALSE(it.has_curr());

      EXPECT_THROW(it.get_curr(), overflow_error);


      it.reset_last();

    }


  it.reset_first();

  EXPECT_EQ(it.del(), &l1);

  EXPECT_TRUE(it.has_curr());


  EXPECT_EQ(it.del(), &l2);

  EXPECT_TRUE(it.has_curr());


  EXPECT_EQ(it.del(), &l3);

  EXPECT_TRUE(it.has_curr());


  EXPECT_EQ(it.del(), &l4);

  EXPECT_TRUE(it.has_curr());


  EXPECT_EQ(it.del(), &l5);

  EXPECT_FALSE(it.has_curr());

  EXPECT_TRUE(list.is_empty());

}


TEST_F(List_of_5_nodes, swap)

{

  Dlink laux;

  list.swap(&laux);


  EXPECT_TRUE(list.is_empty());

  EXPECT_FALSE(laux.is_empty());

  EXPECT_EQ(laux.get_first(), &l1);

  EXPECT_EQ(laux.get_last(), &l5);


  laux.swap(&list);


  EXPECT_TRUE(laux.is_empty());

  EXPECT_FALSE(list.is_empty());

  EXPECT_EQ(list.get_first(), &l1);

  EXPECT_EQ(list.get_last(), &l5);

}


TEST_F(List_of_5_nodes, append_insert_cut_splice_concat_of_lists)

{

  Dlink laux, n1, n2, n3;

  laux.append(&n1);

  laux.append(&n2);

  laux.append(&n3);                // laux = { n1, n2, n3 }


  list.append_list(&laux);         // l = { l1, l2, l3, l4, l5, n1, n2 ,n3 }

  EXPECT_TRUE(laux.is_empty());

  EXPECT_EQ(list.get_first(), &l1);

  EXPECT_EQ(list.get_last(), &n3);


  laux = list.cut_list(&n1);       // l = { l1, l2, l3, l4, l5 }, laux = { n1, n2, n3 }

  EXPECT_EQ(laux.get_first(), &n1);

  EXPECT_EQ(laux.get_last(), &n3);

  EXPECT_EQ(list.get_first(), &l1);

  EXPECT_EQ(list.get_last(), &l5);


  Dlink lr = list.cut_list(&l1);   // l = {}, lr = { l1, l2, l3, l4, l5 }

  EXPECT_TRUE(list.is_empty());

  EXPECT_EQ(lr.get_first(), &l1);

  EXPECT_EQ(lr.get_last(), &l5);


  list.insert_list(&lr);            // list = { l1, l2, l3, l4, l5 }

  EXPECT_TRUE(lr.is_empty());

  EXPECT_EQ(list.get_first(), &l1);

  EXPECT_EQ(list.get_last(), &l5);

  EXPECT_FALSE(list.is_empty());


  list.insert_list(&laux);        // list = { n1, n2, n3, l1, l2, l3, l4, l5 }

  EXPECT_TRUE(laux.is_empty());

  EXPECT_EQ(list.get_first(), &n1);

  EXPECT_EQ(list.get_last(), &l5);


  Dlink n0;

  list.insert(&n0);     // list = { n0, n1, n2, n3, l1, l2, l3, l4, l5 }

  EXPECT_EQ(list.get_first(), &n0);

  EXPECT_EQ(list.get_last(), &l5);


  Dlink m1, m2, m3; // laux = { m1, m2, m3 }

  laux.append(&m1);

  laux.append(&m2);

  laux.append(&m3);

  EXPECT_EQ(laux.get_first(), &m1);

  EXPECT_EQ(laux.get_first()->get_next(), &m2);

  EXPECT_EQ(laux.get_last()->get_prev(), &m2);

  EXPECT_EQ(laux.get_last(), &m3);


  EXPECT_EQ(laux.remove_last(), &m3);

  EXPECT_EQ(laux.remove_first(), &m1);

  EXPECT_EQ(laux.remove_first(), &m2);

  laux.append(&m2);

  EXPECT_EQ(laux.get_first(), &m2);

  EXPECT_EQ(laux.get_last(), &m2);

  EXPECT_TRUE(laux.is_unitarian());

  EXPECT_EQ(laux.remove_last(), &m2);


  laux.append(&m1); // laux = { m1, m2, m3 }

  laux.append(&m2);

  laux.append(&m3);


  n3.append_list(&laux); // list = { n0, n1, n2, n3, m1, m2, m3, l1, l2, l3, l4, l5 }

  EXPECT_TRUE(laux.is_empty());

  EXPECT_EQ(list.get_first(), &n0);

  EXPECT_EQ(list.get_first()->get_next()->get_next()->get_next(), &m1);

  EXPECT_EQ(list.get_last(), &l5);


  laux.append(m1.del());

  laux.append(m2.del());

  laux.append(m3.del());     // laux = { m1, m2, m3 }

  EXPECT_EQ(laux.get_first(), &m1);

  EXPECT_EQ(laux.get_first()->get_next(), &m2);

  EXPECT_EQ(laux.get_last(), &m3);

  EXPECT_EQ(laux.get_last()->get_prev(), &m2);

  EXPECT_EQ(m2.get_prev(), &m1);

  EXPECT_EQ(m2.get_next(), &m3);


  Dlink l, r;

  list.split_list(l, r); // l = { n0, n1, n2, n3, l1 } r = { l2, l3, l4, l5 }

  EXPECT_TRUE(list.is_empty());

  EXPECT_EQ(l.get_first(), &n0);

  EXPECT_EQ(l.get_last(), &l1);

  EXPECT_EQ(r.get_first(), &l2);

  EXPECT_EQ(r.get_last(), &l5);

}


TEST(Dlink, As_stack)

{

  Dlink stack;

  EXPECT_TRUE(stack.is_empty());

  EXPECT_THROW(stack.top(), underflow_error);

  EXPECT_THROW(stack.pop(), underflow_error);

  EXPECT_TRUE(stack.is_unitarian_or_empty());

  Dlink n1, n2, n3;

  stack.push(&n3);


  EXPECT_FALSE(stack.is_empty());

  EXPECT_TRUE(stack.is_unitarian());


  stack.push(&n2);

  stack.push(&n1);

  EXPECT_EQ(stack.top(), &n1);

  EXPECT_EQ(stack.pop(), &n1);

  EXPECT_EQ(stack.top(), &n2);

  EXPECT_EQ(stack.pop(), &n2);


  EXPECT_TRUE(stack.is_unitarian());


  EXPECT_EQ(stack.top(), &n3);

  EXPECT_EQ(stack.pop(), &n3);

  EXPECT_FALSE(stack.is_unitarian());

  EXPECT_TRUE(stack.is_empty());

}


TEST_F(List_of_5_nodes, reverse)

{

  list.reverse_list();

  EXPECT_EQ(list.get_first(), &l5);

  EXPECT_EQ(list.get_last(), &l1);

}


Aleph::Dlink::Iterator
Iterator on Dlink lists.
Definition dlink.H:647

Aleph::Dlink::Iterator::is_in_last
bool is_in_last() const noexcept
Return true if the iterator is positiones on the last item.
Definition dlink.H:752

Aleph::Dlink::Iterator::is_in_first
constexpr bool is_in_first() const noexcept
Return true if the iterator is positiones on the first item.
Definition dlink.H:746

Aleph::Dlink::Iterator::has_curr
bool has_curr() const noexcept
Return true if the iterator has current item.
Definition dlink.H:715

Aleph::Dlink::Iterator::get_curr
Dlink * get_curr() const
Return the current node of iterator.
Definition dlink.H:738

Aleph::Dlink::Iterator::next
void next()
Move the iterator one position forward.
Definition dlink.H:776

Aleph::Dlink::Iterator::del
Dlink * del()
Remove from the list the current node and move the iterator one position forward.
Definition dlink.H:795

Aleph::Dlink::Iterator::prev
void prev()
Move the iterator one position backward.
Definition dlink.H:762

Aleph::Dlink::Iterator::reset_last
void reset_last() noexcept
Reset the iterator to the last item of list.
Definition dlink.H:702

Aleph::Dlink::Iterator::reset_first
void reset_first() noexcept
Reset the iterator to the first item of list.
Definition dlink.H:695

Aleph::Dlink::Iterator::is_last
bool is_last() const noexcept
Definition dlink.H:721

Aleph::Dlink
Doubly linked circular list node.
Definition dlink.H:100

Aleph::Dlink::top
Dlink * top() const
Definition dlink.H:523

Aleph::Dlink::is_unitarian_or_empty
constexpr bool is_unitarian_or_empty() const noexcept
Return true if this (as header node) has zero or one element.
Definition dlink.H:252

Aleph::Dlink::get_last
constexpr Dlink *& get_last() const noexcept
If this is a header node, it return the last node of this
Definition dlink.H:318

Aleph::Dlink::get_first
constexpr Dlink *& get_first() const noexcept
If this is a header node, it return the first node of this
Definition dlink.H:315

Aleph::Dlink::is_empty
constexpr bool is_empty() const noexcept
Return true if this (as header node) is empty.
Definition dlink.H:246

Aleph::Dlink::append
void append(Dlink *node) noexcept
Insert node before this.
Definition dlink.H:282

Aleph::Dlink::del
Dlink * del() noexcept
Remove this from the list. this must not be a header node.
Definition dlink.H:443

Aleph::Dlink::is_unitarian
constexpr bool is_unitarian() const noexcept
Return true if this (as header node) has exactly one element.
Definition dlink.H:249

Aleph::Dlink::pop
Dlink * pop()
Definition dlink.H:530

Aleph::Dlink::push
void push(Dlink *node) noexcept
Definition dlink.H:272

Aleph::Dlink::append_list
void append_list(Dlink *head) noexcept
Insert the list head after this
Definition dlink.H:383

Aleph::Dlink::insert
void insert(Dlink *node) noexcept
Insert node after this.
Definition dlink.H:259

Aleph::DynList::insert
T & insert(const T &item)
Insert a new item by copy.
Definition htlist.H:1502

Aleph::DynList::append
T & append(const T &item)
Append a new item by copy.
Definition htlist.H:1562

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::remove_first
T remove_first()
Definition htlist.H:1628

Aleph::DynList::swap
DynList & swap(DynList &l) noexcept
Swap this with l.
Definition htlist.H:1448

Aleph::HTList::reverse_list
size_t reverse_list() noexcept
Definition htlist.H:1002

Aleph::HTList::cut_list
void cut_list(Slinknc *link, HTList &list) noexcept
Definition htlist.H:1037

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

Aleph::HTList::split_list
size_t split_list(HTList &l, HTList &r) noexcept
It divides 'this' into two equal lists without modifying elements order.
Definition htlist.H:930

Aleph::HTList::is_unitarian
bool is_unitarian() const noexcept
Return true if the list contains exactly just one element.
Definition htlist.H:528

Aleph::HTList::is_unitarian_or_empty
bool is_unitarian_or_empty() const noexcept
Return true if list contains one element or is empty.
Definition htlist.H:535

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

dlink.H
Doubly linked circular list implementation.

TEST_F
TEST_F(List_of_5_nodes, Iterator)
Definition dlink.cc:244

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

Aleph::reverse
void reverse(Itor beg, Itor end)
Reverse elements in a range.
Definition ahAlgo.H:1094

Aleph::swap
T & swap(T &t1, T &t2)
Generic swap using object's swap method.
Definition ahTypes.H:121

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

std
STL namespace.

List_of_5_nodes
Definition dlink.cc:232

List_of_5_nodes::l5
Dlink l5
Definition dlink.cc:233

List_of_5_nodes::l2
Dlink l2
Definition dlink.cc:233

List_of_5_nodes::List_of_5_nodes
List_of_5_nodes()
Definition dlink.cc:234

List_of_5_nodes::l3
Dlink l3
Definition dlink.cc:233

List_of_5_nodes::l4
Dlink l4
Definition dlink.cc:233

List_of_5_nodes::l1
Dlink l1
Definition dlink.cc:233

List_of_5_nodes::list
Dlink list
Definition dlink.cc:233

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