list.h

   1 /*
   2  * Copyright (c) 2001, Robert Collins.
   3  *
   4  *     This program is free software; you can redistribute it and/or modify
   5  *     it under the terms of the GNU General Public License as published by
   6  *     the Free Software Foundation; either version 2 of the License, or
   7  *     (at your option) any later version.
   8  *
   9  *     A copy of the GNU General Public License can be found at
  10  *     http://www.gnu.org/
  11  *
  12  * Written by Robert Collins  <rbtcollins@hotmail.com>
  13  *
  14  */
  15
  16 #ifndef _LIST_H_
  17 #define _LIST_H_
  18
  19 #include "stdlib.h"
  20 #include "sys/types.h"
  21
  22 /* Creates a list/array of type T (must have a field key of type U),
  23  * with index type U and U comparison Ucmp.
  24  */
  25 template < class T, class U, int
  26 Ucmp (U, U) >
  27 class list
  28 {
  29   T **pointerblock;
  30   size_t _number;
  31   size_t _space;
  32
  33 public:
  34 list ():pointerblock (0), _number (0), _space (0)
  35   {
  36   };
  37   // ~list () ...
  38   /* get an element if it exists */
  39   T *getbykey (const U);
  40   /* add an element if it does not exist and return a reference */
  41   T & registerbykey (U);
  42   /* add an element if one with the same key does not exist */
  43   T & registerbyobject (T &);
  44   /* remove by index */
  45   T *removebyindex (size_t);
  46   size_t number () const
  47   {
  48     return _number;
  49   };
  50   /* get by offset - not thread safe - starts at 1 */
  51   T *operator [] (size_t n) const
  52   {
  53     return n && n <= _number ? pointerblock[n - 1] : 0;
  54   };
  55   /* TODO: delete */
  56 private:
  57   // ensure there is enough array space.
  58   void checksize (void);
  59   // perform an insertion.
  60   void insert (size_t, T *);
  61 };
  62
  63 template < class T, class U, int
  64 Ucmp (U, U) >
  65 T * list < T, U, Ucmp >::getbykey (const U key)
  66 {
  67   for (size_t n = 0; n < _number; n++)
  68     if (Ucmp (pointerblock[n]->key, key) == 0)
  69       return pointerblock[n];
  70   return 0;
  71 }
  72
  73
  74 template < class T, class U, int
  75 Ucmp (U, U) >
  76 T & list < T, U, Ucmp >::registerbykey (U key)
  77 {
  78   T *tempT = getbykey (key);
  79   if (!tempT)
  80     {
  81       tempT = new T (key);
  82       size_t n;
  83       for (n = 0;
  84            n < _number && Ucmp (pointerblock[n]->key, tempT->key) < 0; n++);
  85       insert (n, tempT);
  86     }
  87   return *tempT;
  88 }
  89
  90 /* TODO: factor both insertion routines into one */
  91 template < class T, class U, int
  92 Ucmp (U, U) >
  93 T & list < T, U, Ucmp >::registerbyobject (T & newobj)
  94 {
  95   T *tempT = getbykey (newobj.key);
  96   if (!tempT)
  97     {
  98       tempT = &newobj;
  99       size_t n;
 100       for (n = 0;
 101            n < _number && Ucmp (pointerblock[n]->key, tempT->key) < 0; n++);
 102       insert (n, tempT);
 103     }
 104   return *tempT;
 105 }
 106
 107 template < class T, class U, int
 108 Ucmp (U, U) >
 109 T * list < T, U, Ucmp >::removebyindex (size_t index)
 110 {
 111   if (index && index <= _number)
 112     {
 113       T *rv = pointerblock[index - 1];
 114       /* remove from index - 1 */
 115       for (size_t i = index; i < _number; ++i)
 116         pointerblock[i - 1] = pointerblock[i];
 117       --_number;
 118       return rv;
 119     }
 120   return 0;
 121 }
 122
 123 template < class T, class U, int
 124      Ucmp (U, U) > void
 125      list < T, U, Ucmp >::checksize ()
 126 {
 127   if (_number == _space)
 128     {
 129       T **newptr = new (T *)[_space + 20];
 130       if (!newptr)
 131         {
 132           //die - todo enable exceptions
 133           exit (100);
 134         }
 135       for (size_t i = 0; i < _number; ++i)
 136         newptr[i] = pointerblock[i];
 137       delete[]pointerblock;
 138       pointerblock = newptr;
 139       /* TODO: Parameterise this too */
 140       _space += 20;
 141     }
 142 }
 143 template < class T, class U, int
 144      Ucmp (U, U) > void
 145      list < T, U, Ucmp >::insert (size_t where, T * someT)
 146 {
 147   // doesn't change where
 148   checksize ();
 149   /* insert at where */
 150   for (size_t i = _number; where < i; --i)
 151     pointerblock[i] = pointerblock[i - 1];
 152   pointerblock[where] = someT;
 153   ++_number;
 154 }
 155
 156
 157 #endif /* _LIST_H_ */