list.h

Go to the documentation of this file.

// See the end of this file for license information.

#ifndef TORSION_LIST_H
#define TORSION_LIST_H

#include "screen.h"


class List_node {
public:
  List_node* next;
  List_node* previous;
};


template <class Type>
class List_iterator {
public:
  List_node* node;

  List_iterator() { }
  List_iterator(List_node* node);
  List_iterator(Type* node);

  List_iterator&
  operator++();       // prefix ++

  List_iterator&
  operator--();       // prefix --

  List_iterator&
  operator++(int);      // postfix ++

  List_iterator&
  operator--(int);      // postfix --

  Type&
  operator*() const;

  Type*
  operator->() const;

  bool
  operator==(const List_iterator& iterator) const;

  bool
  operator!=(const List_iterator& iterator) const;
};

template <class Type>
inline
List_iterator<Type>::List_iterator(List_node* node) : node(node) { }

template <class Type>
inline
List_iterator<Type>::List_iterator(Type* node) : node((List_node*)node) { }

template <class Type>
inline List_iterator<Type>&
List_iterator<Type>::operator++() {
  node = node->next;
  return *this;
}

template <class Type>
inline List_iterator<Type>&
List_iterator<Type>::operator--() {
  node = node->previous;
  return *this;
}

template <class Type>
inline List_iterator<Type>&
List_iterator<Type>::operator++(int) {
  node = node->next;
  return *this;
}

template <class Type>
inline List_iterator<Type>&
List_iterator<Type>::operator--(int) {
  node = node->previous;
  return *this;
}

template <class Type>
inline Type&
List_iterator<Type>::operator*() const {
  return *(Type*)node;
}

template <class Type>
inline Type*
List_iterator<Type>::operator->() const {
  return (Type*)node; 
}

template <class Type>
inline bool
List_iterator<Type>::operator==(const List_iterator& iterator) const {
  return (node == iterator.node);
}

template <class Type>
inline bool
List_iterator<Type>::operator!=(const List_iterator& iterator) const {
  return (node != iterator.node);
}


template <class Type>
class List {
protected:
  List_node sentinel;

public:
  typedef List_iterator<Type> Iterator;

  List();

  void
  clear();
  
  void
  free_and_clear();
    
  Type*
  front();

  Type*
  back();

  Iterator
  begin();

  Iterator
  end();

  bool
  is_empty() const;

  unsigned
  size() const;

  Iterator
  insert(Iterator position, Type* element);

  Iterator
  insert_front(Type* element);

  Iterator
  insert_back(Type* element);

  Type*
  remove(Iterator position);
  
  Type*
  remove(Type* element);

  Type*
  remove_front();

  Type*
  remove_back();
  
  void
  print();
};

template <class Type>
inline
List<Type>::List() {
  clear();
}

template <class Type>
inline void
List<Type>::clear() {
  sentinel.next = &sentinel;
  sentinel.previous = &sentinel;
}

template <class Type>
inline void
List<Type>::free_and_clear() {
  // free each node in this list
  for (const List_node* node = sentinel.next; node != &sentinel; node = node->next)
    delete node;

  // clear the list itself
  clear();
}

template <class Type>
inline Type*
List<Type>::front() {
  return (Type*)sentinel.next;
}

template <class Type>
inline Type*
List<Type>::back() {
  return (Type*)sentinel.previous;
}

template <class Type>
inline List_iterator<Type>
List<Type>::begin() {
  return Iterator(sentinel.next);
}

template <class Type>
inline List_iterator<Type>
List<Type>::end() {
  return Iterator(&sentinel);
}

template <class Type>
inline bool
List<Type>::is_empty() const {
  return sentinel.next == &sentinel;
}

template <class Type>
unsigned
List<Type>::size() const {
  unsigned size = 0;

  for (const List_node* node = sentinel.next; node != &sentinel; node = node->next)
    size++;
   
  return size;
}

template <class Type>
inline List_iterator<Type>
List <Type>::insert(Iterator position, Type* element) {
  List_node* node = (List_node*)(element);

  if (node != position.node && node != position.node->previous) {
    node->next = position.node;
    node->previous = position.node->previous;
    position.node->previous = node;
    node->previous->next = node;
  }

  return Iterator(node);
}

template <class Type>
inline List_iterator<Type>
List<Type>::insert_front(Type* element) {
  return insert(begin(), element);
}

template <class Type>
inline List_iterator<Type>
List<Type>::insert_back(Type* element) {
  return insert(end(), element);
}

template <class Type>
inline Type*
List<Type>::remove(Iterator position) {
  remove((Type*)position.node);
  return (Type*)position.node;
}

template <class Type>
inline Type*
List<Type>::remove(Type* element) {
  if (element->next != NULL && element->previous != NULL) {
    element->previous->next = element->next;
    element->next->previous = element->previous;
    element->next = NULL;
    element->previous = NULL;
  }
  
  return element;
}

template <class Type>
inline Type*
List<Type>::remove_front() {
  return remove(Iterator(front()));
}

template <class Type>
inline Type*
List<Type>::remove_back() {
  return remove(Iterator(back()));
}

template <class Type>
void
List<Type>::print() {
  screen.print(this, false);
  screen.print(": ", false);

  unsigned i = 0;
  for (Iterator position = begin(); position != end() && i < 6; position++) {
    screen.print(&*position, false);
    screen.print(" ", false);
    i++;
  }
  if (i == 6)
    screen.print("...");
  screen.print();
}

#endif    

/* Torsion Operating System, Copyright (C) 2000-2004 Dan Helfman
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2 of the License, or (at your
 * option) any later version.
 * 
 * This program 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
 * General Public License for more details (in the COPYING file).
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

---

Torsion Operating System, Copyright (C) 2000-2004 Dan Helfman