Hi Eddie,
Attached an alternative based on linked list implementation from CS book
"Data Structures and Problem Solving Using C++" which closely follows
standard library. Havent been tested thoroughly though. Named DList as I am
using Jason's implementation elsewhere as well.
Beyers
On 3/12/07, Eddie Kohler <[EMAIL PROTECTED]> wrote:
I like Jason's linked list, but I also wish that a couple of its aspects
were
different. In particular, I wish that it was, by default, an "intrinsic"
linked list: i.e., List<T> would use properties like T.next and T.prev
. Also
the interface needs an audit to make sure it follows the C++ standard
library
interface as much as possible. Perhaps I'll send more info on this
soon...I
had wanted to really think it through first.
Eddie
Beyers Cronje wrote:
> Hi Jason,
>
> Just to let you know been using your list class as well, it works
> beautifully. I haven't picked up any issues with my use so far.
>
> Eddie, any chance you could include this or something simmilar in Click
?
>
> Regards
>
> Beyers Cronje
>
> On 1/29/07, *Jason Park* <[EMAIL PROTECTED]
> <mailto:[EMAIL PROTECTED]>> wrote:
>
> HI,
>
>
>
> Here I attach double linkedlist for click that Beyers mentioned.
>
> I was fixed trivially since I posted.
>
> It works well, but I don't know whether click has plan to include in
it.
>
>
>
> Please put them into these locations.
>
> include/click/list.hh
>
> elements/test/listtest.hh
>
> elements/test/listtest.cc
>
>
>
> In addition to List, I'm working multi index container (memory db)
for
> click. If someone or click needs it,
>
> I'll post it. It's similar to the thing of Boost Multi-index
> <http://www.boost.org/libs/multi_index/doc/index.html
> <http://www.boost.org/libs/multi_index/doc/index.html>> Containers
> Library
> and including MPL like (THE BOOST MPL
> <http://www.boost.org/libs/mpl/doc/index.html> LIBRARY) also.
>
>
>
> Bye.
>
>
>
> Jason Park.
>
> _____
>
> From: Beyers Cronje [mailto:[EMAIL PROTECTED]
> <mailto:[EMAIL PROTECTED]>]
> Sent: Monday, January 29, 2007 4:28 AM
> To: [EMAIL PROTECTED] <mailto:
[EMAIL PROTECTED]>
> Cc: [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>;
> Jason Park
> Subject: Re: [Click] LinkedList in click
>
>
>
> Hi Roberto,
>
> See previous post by Jason.
>
https://amsterdam.lcs.mit.edu/pipermail/click/2006-October/005255.html
>
> I havent used his patch so it's maybe best if Jason comments
directly.
>
> Beyers
>
> On 1/28/07, Roberto Riggio <[EMAIL PROTECTED]
> <mailto:[EMAIL PROTECTED]>> wrote:
>
> Hi,
>
> as in the subject, are there any plans to include a (double)
> linkedlist in
> click?
>
> Bye
> Roberto
>
> --
> ========================================
> Roberto Riggio, Ph. D. Student
> CREATE-NET
> via Solteri 38
> 38100 -- Trento (Italy)
> tel: +39.0461.82.85.84
> fax: +39.0461.42.11.57
> e-mail: [EMAIL PROTECTED]
> <mailto:[EMAIL PROTECTED]>
> web page: http://dit.unitn.it/~riggio/
> =======================================
> _______________________________________________
> click mailing list
> click@amsterdam.lcs.mit.edu
> <mailto:click@amsterdam.lcs.mit.edu> <mailto:
click@amsterdam.lcs.mit.edu
> <mailto:click@amsterdam.lcs.mit.edu>>
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click
>
>
>
>
> _______________________________________________
> click mailing list
> click@amsterdam.lcs.mit.edu <mailto:click@amsterdam.lcs.mit.edu>
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click
>
>
>
#ifndef CLICK_DLIST_HH
#define CLICK_DLIST_HH
template <class T>
class ListNode;
template <class T>
class ConstListIter;
template <class T>
class ListIter;
template <class T>
class DList
{
public:
typedef ListIter<T> iterator;
typedef ConstListIter<T> const_iterator;
DList();
~DList();
DList(const DList& rhs);
const DList & operator=(const DList& rhs);
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
int size() const;
bool empty() const;
T& front();
const T& front() const;
T& back();
const T& back() const;
void push_front(const T& e);
void push_back(const T& e);
void pop_front();
void pop_back();
iterator insert(iterator itr, const T& e);
iterator erase(iterator itr);
iterator erase(iterator start, iterator end);
friend class ConstListIter<T>;
friend class ListIter<T>;
private:
typedef ListNode<T> node;
int _n;
node *_head;
node *_tail;
void init();
void makeEmpty();
};
template <class T>
class ListNode
{
private:
ListNode(const T &d = T(), ListNode *p = NULL, ListNode *n = NULL) :
_data(d), _prev(p), _next(n) { }
T _data;
ListNode *_prev;
ListNode *_next;
friend class ConstListIter<T>;
friend class ListIter<T>;
friend class DList<T>;
};
template <class T>
class ConstListIter
{
public:
ConstListIter();
virtual ~ConstListIter() { }
virtual const T& operator*() const;
ConstListIter& operator++();
ConstListIter operator++(int);
ConstListIter& operator--();
ConstListIter operator--(int);
bool operator==(const ConstListIter& rhs) const;
bool operator!=(const ConstListIter& rhs) const;
protected:
typedef ListNode<T> node;
node *_head;
node *_current;
friend class DList<T>;
void assertIsInitialized() const;
void assertIsValid() const;
void assertCanAdvance() const;
void assertCanRetreat() const;
T& retrieve() const;
ConstListIter(const DList<T>& source, node *p);
};
template <class T>
class ListIter : public ConstListIter<T>
{
public:
ListIter();
T& operator*();
const T& operator*() const;
ListIter& operator++();
ListIter operator++(int);
ListIter& operator--();
ListIter operator--(int);
T& value();
protected:
typedef ListNode<T> node;
friend class DList<T>;
ListIter(const DList<T>& source, node *p);
};
#endif
#include "dlist.hh"
template <class T>
DList<T>::DList()
{
init();
}
template <class T>
void DList<T>::init()
{
_n = 0;
_head = new node;
_tail = new node;
_head->_next = _tail;
_tail->_prev = _head;
}
template <class T>
DList<T>::~DList()
{
makeEmpty();
delete _head;
delete _tail;
}
template <class T>
void DList<T>::makeEmpty()
{
while (!empty())
pop_front();
}
template <class T>
DList<T>::DList(const DList<T>& rhs)
{
init();
*this = rhs;
}
template <class T>
const DList<T>& DList<T>::operator=(const DList& rhs)
{
if (this == &rhs)
return *this;
makeEmpty();
const_iterator itr = rhs.begin();
while (itr != rhs.end())
push_back(*itr++);
return *this;
}
template <class T>
typename DList<T>::iterator DList<T>::begin()
{
iterator itr(*this, _head);
return ++itr;
}
template <class T>
typename DList<T>::const_iterator DList<T>::begin() const
{
const_iterator itr(*this, _head);
return ++itr;
}
template <class T>
typename DList<T>::iterator DList<T>::end()
{
return iterator(*this, _tail);
}
template <class T>
typename DList<T>::const_iterator DList<T>::end() const
{
return const_iterator(*this, _tail);
}
template <class T>
int DList<T>::size() const
{
return _n;
}
template <class T>
bool DList<T>::empty() const
{
return size() == 0;
}
template <class T>
T& DList<T>::front()
{
return *begin();
}
template <class T>
const T& DList<T>::front() const
{
return *begin();
}
template <class T>
T& DList<T>::back()
{
return *--end();
}
template <class T>
const T& DList<T>::back() const
{
return *--end();
}
template <class T>
void DList<T>::push_front(const T& e)
{
insert(begin(), e);
}
template <class T>
void DList<T>::push_back(const T& e)
{
insert(end(), e);
}
template <class T>
void DList<T>::pop_front()
{
erase(begin());
}
template <class T>
void DList<T>::pop_back()
{
erase(--end());
}
// Insert e before itr
template <class T>
typename DList<T>::iterator DList<T>::insert(iterator itr, const T& e)
{
itr.assertIsValid();
assert(itr._head == _head); // itr is not in this list
node *p = itr._current;
p->_prev->_next = new node(e, p->_prev, p);
p->_prev = p->_prev->_next;
_n++;
return iterator(*this, p->_prev);
}
// Erase item at itr
template <class T>
typename DList<T>::iterator DList<T>::erase(iterator itr)
{
itr.assertIsValid();
assert(itr != end());
assert(itr._head == _head);
node *p = itr._current;
iterator retVal(*this, p->_next);
p->_prev->_next = p->_next;
p->_next->_prev = p->_prev;
delete p;
_n--;
return retVal;
}
// Erate items in the range (from, to)
template <class T>
typename DList<T>::iterator DList<T>::erase(iterator from, iterator to)
{
for (iterator itr = from; itr != to; )
itr = erase(itr);
return to;
}
template <class T>
ConstListIter<T>::ConstListIter() : _head(NULL), _current(NULL)
{
}
template <class T>
ConstListIter<T>::ConstListIter(const DList<T>& source, node *p)
: _head(source._head), _current(p)
{
}
template <class T>
ListIter<T>::ListIter()
{
}
template <class T>
ListIter<T>::ListIter(const DList<T>& source, node *p)
: ConstListIter<T>(source, p)
{
}
template <class T>
void ConstListIter<T>::assertIsInitialized() const
{
assert(_head != NULL && _current != NULL);
}
template <class T>
void ConstListIter<T>::assertIsValid() const
{
assertIsInitialized();
assert(_current != _head);
}
template <class T>
void ConstListIter<T>::assertCanAdvance() const
{
assertIsInitialized();
assert(_current->_next != NULL);
}
template <class T>
void ConstListIter<T>::assertCanRetreat() const
{
assertIsValid();
assert(_current->_prev != _head);
}
template <class T>
const T& ConstListIter<T>::operator*() const
{
return retrieve();
}
template <class T>
const T& ListIter<T>::operator*() const
{
return ConstListIter<T>::operator*();
}
template <class T>
T& ListIter<T>::operator*()
{
return ConstListIter<T>::retrieve();
}
template <class T>
T& ConstListIter<T>::retrieve() const
{
assertIsValid();
assert(_current->_next != NULL);
return _current->_data;
}
// prefix
template <class T>
ConstListIter<T>& ConstListIter<T>::operator++()
{
assertCanAdvance();
_current = _current->_next;
return *this;
}
// postfix
template <class T>
ConstListIter<T> ConstListIter<T>::operator++(int)
{
ConstListIter<T> old = *this;
++(*this);
return old;
}
// prefix
template <class T>
ListIter<T>& ListIter<T>::operator++()
{
ConstListIter<T>::assertCanAdvance();
ConstListIter<T>::_current = ConstListIter<T>::_current->_next;
return *this;
}
// postfix
template <class T>
ListIter<T> ListIter<T>::operator++(int)
{
ListIter<T> old = *this;
++(*this);
return old;
}
// prefix
template <class T>
ConstListIter<T>& ConstListIter<T>::operator--()
{
assertCanRetreat();
_current = _current->_prev;
return *this;
}
// postfix
template <class T>
ConstListIter<T> ConstListIter<T>::operator--(int)
{
ConstListIter<T> old = *this;
--(*this);
return old;
}
// prefix
template <class T>
ListIter<T>& ListIter<T>::operator--()
{
ConstListIter<T>::assertCanRetreat();
ConstListIter<T>::_current = ConstListIter<T>::_current->_prev;
return *this;
}
// postfix
template <class T>
ListIter<T> ListIter<T>::operator--(int)
{
ListIter<T> old = *this;
--(*this);
return old;
}
template <class T>
bool ConstListIter<T>::operator==(const ConstListIter& rhs) const
{
return _current == rhs._current;
}
template <class T>
bool ConstListIter<T>::operator!=(const ConstListIter& rhs) const
{
return !(*this == rhs);
}
template <class T>
T& ListIter<T>::value()
{
return ConstListIter<T>::retrieve();
}_______________________________________________
click mailing list
click@amsterdam.lcs.mit.edu
https://amsterdam.lcs.mit.edu/mailman/listinfo/click
