src/list.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
   4 **
   5 ** This file is part of Qt Jambi.
   6 **
   7 ** ** This file may be used under the terms of the GNU General Public
   8 ** License version 2.0 as published by the Free Software Foundation
   9 ** and appearing in the file LICENSE.GPL included in the packaging of
  10 ** this file.  Please review the following information to ensure GNU
  11 ** General Public Licensing requirements will be met:
  12 ** http://www.trolltech.com/products/qt/opensource.html
  13 **
  14 ** If you are unsure which license is appropriate for your use, please
  15 ** review the following information:
  16 ** http://www.trolltech.com/products/qt/licensing.html or contact the
  17 ** sales department at sales@trolltech.com.
  18
  19 **
  20 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  21 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  22 **
  23 ****************************************************************************/
  24
  25 /* This file is part of KDevelop
  26     Copyright (C) 2002-2005 Roberto Raggi <roberto@kdevelop.org>
  27
  28    This library is free software; you can redistribute it and/or
  29    modify it under the terms of the GNU Library General Public
  30    License version 2 as published by the Free Software Foundation.
  31
  32    This library is distributed in the hope that it will be useful,
  33    but WITHOUT ANY WARRANTY; without even the implied warranty of
  34    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  35    Library General Public License for more details.
  36
  37    You should have received a copy of the GNU Library General Public License
  38    along with this library; see the file COPYING.LIB.  If not, write to
  39    the Free Software Foundation, Inc., 51 Franklin Steet, Fifth Floor,
  40    Boston, MA 02110-1301, USA.
  41 */
  42
  43 #ifndef FASTLIST_H
  44 #define FASTLIST_H
  45
  46 #include "smallobject.h"
  47
  48 template <typename Tp>
  49 struct ListNode
  50 {
  51   Tp element;
  52   int index;
  53   mutable const ListNode<Tp> *next;
  54
  55   static ListNode *create(const Tp &element, pool *p)
  56   {
  57     ListNode<Tp> *node = new (p->allocate(sizeof(ListNode))) ListNode();
  58     node->element = element;
  59     node->index = 0;
  60     node->next = node;
  61
  62     return node;
  63   }
  64
  65   static ListNode *create(const ListNode *n1, const Tp &element, pool *p)
  66   {
  67     ListNode<Tp> *n2 = ListNode::create(element, p);
  68
  69     n2->index = n1->index + 1;
  70     n2->next = n1->next;
  71     n1->next = n2;
  72
  73     return n2;
  74   }
  75
  76   inline ListNode<Tp>() { }
  77
  78   inline const ListNode<Tp> *at(int index) const
  79   {
  80     const ListNode<Tp> *node = this;
  81     while (index != node->index)
  82       node = node->next;
  83
  84     return node;
  85   }
  86
  87   inline bool hasNext() const
  88   { return index < next->index; }
  89
  90   inline int count() const
  91   { return 1 + toBack()->index; }
  92
  93   inline const ListNode<Tp> *toFront() const
  94   { return toBack()->next; }
  95
  96   inline const ListNode<Tp> *toBack() const
  97   {
  98     const ListNode<Tp> *node = this;
  99     while (node->hasNext())
 100       node = node->next;
 101
 102     return node;
 103   }
 104 };
 105
 106 template <class Tp>
 107 inline const ListNode<Tp> *snoc(const ListNode<Tp> *list,
 108                                 const Tp &element, pool *p)
 109 {
 110   if (!list)
 111     return ListNode<Tp>::create(element, p);
 112
 113   return ListNode<Tp>::create(list->toBack(), element, p);
 114 }
 115
 116 #endif // FASTLIST_H
 117
 118 // kate: space-indent on; indent-width 2; replace-tabs on;
 119