libvdk2-dev 2.4.0-5.4 / usr / include / vdk2 / vdk / value_sem_list.h

/*
 * ===========================
 * VDK Visual Development Kit
 * Version 0.4
 * October 1998
 * ===========================
 *
 * Copyright (C) 1998, Mario Motta
 * Developed by Mario Motta <mmotta@guest.net>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA.
 */

/*!
  \class VDKValueList
  \brief provides a templatized double-linked list
  \par Overview
  VDKValueList has a value semantic, so all managed object are
  copied from original ones values.
  VDKValueList can manage all T type object provided that:
  \arg T t has a default constructor:    T::T()
  \arg T t has a copy initializer:       T::T(T& t)
  \arg T t has an assignement operator:  T& T::operator=(T& t)
  \arg T t has an equality operator:     int T::operator==(T& t)
  \arg T t has a less-than operator:     int T::operator<(T& t)
  \par Implementation notes
  I suggest to use typedef's like:
  \code
  typedef VDKValueList<someClass>         SomeClassVDKValueListList;
  typedef VDKValueListIterator<SomeClass> SomeClassVDKValueListIterator;
  \endcode
*/
#ifndef VALUE_SEM_LIST_H
#define VALUE_SEM_LIST_H
#include <assert.h>
#define nihil (VDKValueItem<T>*) 0

/*
  forward
*/
template <class T> class VDKValueList;
template <class T> class VDKValueListIterator;

/*!
  \class VDKValueItem,
  \brief all properties private.
*/
template <class T>
class VDKValueItem
{
  friend class VDKValueList<T>;
  friend class VDKValueListIterator<T>;
  T data;
  VDKValueItem *next,*prev;
  VDKValueItem(const T& data): data(data),next(nihil),prev(nihil) 
    {
    }
  ~VDKValueItem() 
    {
    }
};

/*
  class VDKValueList,
  inherits from Container
*/
template <class T>
class VDKValueList
{
  
 protected:
  VDKValueItem<T> *head,*tail;
  int count;
  
 public:
  /*!
    Constructor makes an empty list
   */
  VDKValueList():head(nihil),tail(nihil),count(0) {}
  /*!
    Copy-initializer
   */
  VDKValueList(const VDKValueList<T>& l);
  /*!
    Assignement operator
   */
  VDKValueList<T>& operator=(const VDKValueList<T>& l);
  /*!
    Destructor
   */
  virtual ~VDKValueList();
  /*!
    Append a type T to list
   */
  void add(const T& t);
  /*!
    Prepend a type T to list
   */
  void push( const T& t);
  /*!
    Insert in order
    \param unique if true denies duplicate key
   */
  int insert( const T& t, bool unique = false);
  /*!
    Flushes list
   */
  void flush();
  /*!
    Ordinal access
   */
  T& operator[](int n);
  /*!
    membership operator
    Returns T* NULL if not found
  */
  T* find(T& t);
  /*!
    Returns list size
  */
  int size() { return count; }
  /*!
    Unlink an element form list
    \param ndx ordinal position of the element to be removed
   */
  bool unlink(int ndx);
  /*!
    Returns ordinal position of an element
   */
  int at(T& t);
  
 protected:
  friend class VDKValueListIterator<T>;
  void assign(const VDKValueList<T>& l);
  VDKValueItem<T>* fetch(int n);
  void addToTail(VDKValueItem<T>* i);
  void addToHead(VDKValueItem<T>* i);
  int insertVDKValueItem(VDKValueItem<T>* i, bool unique);
  
};
/*!
  \class VDKValueListIterator
  \brief provides a VDKValueList iterator
  \par Programming tips
  Using iterators is straightforward:
  \code
  typedef VDKValueList<int> IntList;
  typedef VDKValueListIterator<int> IntListIterator;
  IntList list;
  // some code to fill list goes here..
  // ...
  // ...
  IntListIterator li(list);
  while(li)
    {
    // make whatever
    makewhatever(li.current());
    li++;
    }
  // or
  // for(IntListIterator li(list);li;li++)
  // printf("\n%d",li.current();
  \endcode
*/
template <class T>
class VDKValueListIterator
{
  VDKValueItem<T>* head,*tail,*p;
 public:
  /*!
    Default constructor (unuseful)
   */
  VDKValueListIterator():head(nihil),tail(nihil),p(nihil) {}
  /*!
    Constructor
    \param l a  VDKValueList reference
   */
  VDKValueListIterator(const VDKValueList<T>& l):
    head(l.head),tail(l.tail),p(l.head) {}
  /*!
    Destructor
  */
  virtual ~VDKValueListIterator() {}
  /*!
    Incremental operator (postfix)
   */
  void operator++() { p = p->next; }
  /*!
    Incremental operator (infix)
   */
  void operator++(int) { p = p->next; }
  /*!
    Decremental operator (postfix)
   */
  void operator--() { p = p->prev; }
  /*!
    Decremental operator (infix)
   */
  void operator--(int) { p = p->prev; }
  /*!
    Goes to list head
   */
  void first() { p = head; }
  /*!
    Goes to list tail
   */
  void last() { p = tail; }
  /*!
    Returns 0 at list end
   */
  operator int() { return p != nihil; }
  /*!
    Returns type T currently accessed
   */
  T& current() { return p->data; }
  /*!
    Rewinds operator
   */
  void restart() { p = head; }
};


/*
  copy initializer
*/
template <class T>
VDKValueList<T>::VDKValueList(const VDKValueList<T>& l)
{
  count = 0;
  head = tail = nihil;
  assign(l);
}
/*
  assignement
*/
template <class T>
VDKValueList<T>& VDKValueList<T>::operator=(const VDKValueList<T>& l)
{
  if(this != &l)
    {
      flush();
      assign(l);
    }
  return *this;
}
/*
  destructor
*/
template <class T>
VDKValueList<T>::~VDKValueList()
{
  flush();
}
/*
  flushes list
*/
template <class T>
void VDKValueList<T>::flush()
{
  VDKValueItem<T>* p = head;
  VDKValueItem<T>* p1;
  while(p)
    {
      p1 = p->next;
      delete p;
      p = p1;
    }
  head = tail = nihil;
  count = 0;
}
/*
  add a T type to list
*/
template <class T>
void VDKValueList<T>::add( const T& t)
{
  addToTail(new VDKValueItem<T>(t));
}
/*
  pushes a T type into list
*/
template <class T>
void VDKValueList<T>::push(const T& t)
{
  addToHead(new VDKValueItem<T>(t));
}
/*
  insert in order a T type into list
*/
template <class T>
int VDKValueList<T>::insert(const T& t, bool unique)
{
 
  return insertVDKValueItem(new VDKValueItem<T>(t), unique);
}
/*
  ordinal operator
*/
template <class T>
T& VDKValueList<T>::operator[](int n)
{
  assert(n<count);
  return fetch(n)->data;
}
/*
  find a T type value
*/
template <class T>
T* VDKValueList<T>::find(T& t)
{
  VDKValueItem<T>* p = head;
  for(; p && !(p->data == t); p = p->next);
  return p ? &(p->data): (T*) 0;
}
/*
 */
template <class T>
int 
VDKValueList<T>::at(T& x) {
  int t = 0;
  VDKValueItem<T>* p = head;
  for(; p && !(p->data == x);p = p->next,t++) ;
  return p ? t : -1;
}


template <class T>
bool
VDKValueList<T>::unlink(int ndx)
{
  VDKValueItem<T> *x = fetch(ndx);
  if(!x) return false;
  if(x->prev != nihil)
    x->prev->next = x->next;
  else
    head = x->next;
  if(x->next != nihil)
    x->next->prev = x->prev;
  else
    tail = x->prev;
  count--;
  delete x;
  return true;
}
/*
  private,
  copy VDKValueItems from a list 
  into this
*/
template <class T>
void VDKValueList<T>::assign(const VDKValueList<T>& l)
{
  for(VDKValueListIterator<T> li(l);li;li++)
    add(li.current());
}
/*
  private,
  fetches n-th VDKValueItem
*/
template <class T>
VDKValueItem<T>* VDKValueList<T>::fetch(int n)
{
  int t = 0;
  VDKValueItem<T>* p ;
  for(p = head; p && (t<n); t++, p = p->next);
  return p;
}
/*
  private,
  add an VDKValueItem to tail
*/
template <class T>
void VDKValueList<T>::addToTail(VDKValueItem<T>* i)
{
  if(! head) head = tail = i;
  else { tail->next = i; i->prev = tail; tail = i; }
  count++;
}
/*
  private,
  add an VDKValueItem to tail
*/
template <class T>
void VDKValueList<T>::addToHead(VDKValueItem<T>* i)
{
  if(! head) head = tail = i;
  else { head->prev = i; i->next = head; head = i; }
  count++;
}
/*
  private,
  add an VDKValueItem in order
  return inserted list index
*/
template <class T>
int VDKValueList<T>::insertVDKValueItem(VDKValueItem<T>* i,
					bool unique)
{
  VDKValueItem<T>* p;
  int t=0;
  for(p = head,t=0; p && (p->data < i->data); p = p->next,t++);
    // avoid key clush
  if(unique && p && (p->data == i->data))
    {
      delete i;
      return -1;
    }
  if(!p) 
    {
    addToTail(i);
    return count-1;
    }
  else if (p->prev)
    {
      p->prev->next = i;
      i->prev = p->prev;
      p->prev = i;
      i->next = p;
      count++;
      return t;
    }
  else 
    {
    addToHead(i);
    return 0;
    }
}
#endif