linked_list.cpp

00001 /*
00002  * Copyright (C) 2014 Pavel Kirienko <pavel.kirienko@gmail.com>
00003  */
00004 
00005 #include <gtest/gtest.h>
00006 #include <uavcan/util/linked_list.hpp>
00007 
00008 struct ListItem : uavcan::LinkedListNode<ListItem>
00009 {
00010     int value;
00011 
00012     ListItem(int value = 0)
00013         : value(value)
00014     { }
00015 
00016     struct GreaterThanComparator
00017     {
00018         const int compare_with;
00019 
00020         GreaterThanComparator(int compare_with)
00021             : compare_with(compare_with)
00022         { }
00023 
00024         bool operator()(const ListItem* item) const
00025         {
00026             return item->value > compare_with;
00027         }
00028     };
00029 
00030     void insort(uavcan::LinkedListRoot<ListItem>& root)
00031     {
00032         root.insertBefore(this, GreaterThanComparator(value));
00033     }
00034 };
00035 
00036 TEST(LinkedList, Basic)
00037 {
00038     uavcan::LinkedListRoot<ListItem> root;
00039 
00040     /*
00041      * Insert/remove
00042      */
00043     EXPECT_EQ(0, root.getLength());
00044 
00045     ListItem item1;
00046     root.insert(&item1);
00047     root.insert(&item1);         // Insert twice - second will be ignored
00048     EXPECT_EQ(1, root.getLength());
00049 
00050     root.remove(&item1);
00051     root.remove(&item1);
00052     EXPECT_EQ(0, root.getLength());
00053 
00054     ListItem items[3];
00055     root.insert(&item1);
00056     root.insert(items + 0);
00057     root.insert(items + 1);
00058     root.insert(items + 2);
00059     EXPECT_EQ(4, root.getLength());
00060 
00061     /*
00062      * Order persistence
00063      */
00064     items[0].value = 10;
00065     items[1].value = 11;
00066     items[2].value = 12;
00067     const int expected_values[] = {12, 11, 10, 0};
00068     ListItem* node = root.get();
00069     for (int i = 0; i < 4; i++)
00070     {
00071         EXPECT_EQ(expected_values[i], node->value);
00072         node = node->getNextListNode();
00073     }
00074 
00075     root.remove(items + 0);
00076     root.remove(items + 2);
00077     root.remove(items + 2);
00078     EXPECT_EQ(2, root.getLength());
00079 
00080     const int expected_values2[] = {11, 0};
00081     node = root.get();
00082     for (int i = 0; i < 2; i++)
00083     {
00084         EXPECT_EQ(expected_values2[i], node->value);
00085         node = node->getNextListNode();
00086     }
00087 
00088     root.insert(items + 2);
00089     EXPECT_EQ(3, root.getLength());
00090     EXPECT_EQ(12, root.get()->value);
00091 
00092     /*
00093      * Emptying
00094      */
00095     root.remove(&item1);
00096     root.remove(items + 0);
00097     root.remove(items + 1);
00098     root.remove(items + 2);
00099     EXPECT_EQ(0, root.getLength());
00100 }
00101 
00102 TEST(LinkedList, Sorting)
00103 {
00104     uavcan::LinkedListRoot<ListItem> root;
00105     ListItem items[6];
00106     for (int i = 0; i < 6; i++)
00107     {
00108         items[i].value = i;
00109     }
00110 
00111     EXPECT_EQ(0, root.getLength());
00112 
00113     items[2].insort(root);
00114     EXPECT_EQ(1, root.getLength());
00115 
00116     items[2].insort(root);              // Making sure the duplicate will be removed
00117     EXPECT_EQ(1, root.getLength());
00118 
00119     items[3].insort(root);
00120 
00121     items[0].insort(root);
00122 
00123     items[4].insort(root);
00124     EXPECT_EQ(4, root.getLength());
00125 
00126     items[1].insort(root);
00127     EXPECT_EQ(5, root.getLength());
00128 
00129     items[1].insort(root);              // Another duplicate
00130     EXPECT_EQ(5, root.getLength());
00131 
00132     items[5].insort(root);
00133 
00134     EXPECT_EQ(6, root.getLength());
00135 
00136     int prev_val = -100500;
00137     const ListItem* item = root.get();
00138     while (item)
00139     {
00140         //std::cout << item->value << std::endl;
00141         EXPECT_LT(prev_val, item->value);
00142         prev_val = item->value;
00143         item = item->getNextListNode();
00144     }
00145 }