PLearn 0.1
DoublyLinkedList.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // PLearn (A C++ Machine Learning Library)
00004 // Copyright (C) 1998 Pascal Vincent
00005 // Copyright (C) 1999-2002 Pascal Vincent, Yoshua Bengio and University of Montreal
00006 //
00007 
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions are met:
00010 // 
00011 //  1. Redistributions of source code must retain the above copyright
00012 //     notice, this list of conditions and the following disclaimer.
00013 // 
00014 //  2. Redistributions in binary form must reproduce the above copyright
00015 //     notice, this list of conditions and the following disclaimer in the
00016 //     documentation and/or other materials provided with the distribution.
00017 // 
00018 //  3. The name of the authors may not be used to endorse or promote
00019 //     products derived from this software without specific prior written
00020 //     permission.
00021 // 
00022 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
00023 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00024 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
00025 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00026 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00027 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00028 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00029 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00030 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00031 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00032 // 
00033 // This file is part of the PLearn library. For more information on the PLearn
00034 // library, go to the PLearn Web site at www.plearn.org
00035 
00036 
00037  
00038 
00039 /* *******************************************************      
00040  * $Id$
00041  * AUTHORS: Yoshua Bengio
00042  * This file is part of the PLearn library.
00043  ******************************************************* */
00044 
00045 
00048 #ifndef DoublyLinkedList_INC
00049 #define DoublyLinkedList_INC
00050 
00051 #include <plearn/base/plerror.h>
00052 
00053 namespace PLearn {
00054 using namespace std;
00055 
00056 static bool dbg=false;
00057 
00064 template <class T>
00065 struct DoublyLinkedListElement {
00066     T entry;
00067     DoublyLinkedListElement* next;
00068     DoublyLinkedListElement* previous;
00069     DoublyLinkedListElement(T e, DoublyLinkedListElement* n=0, DoublyLinkedListElement* p=0) : entry(e), next(n), previous(p) {}
00070 };
00071 
00078 template <class T>
00079 class DoublyLinkedList {
00080 public:
00081     DoublyLinkedListElement<T>* first;
00082     DoublyLinkedListElement<T>* last;
00083     int n_elements;
00084 
00085     inline DoublyLinkedList() : first(0), last(0), n_elements(0) {}
00086 
00087     inline DoublyLinkedListElement<T>* pushOnTop(T entry) {
00088         if (dbg) 
00089             cout << "calling DoublyLinkedList::pushOnTop(" << entry << endl;
00090         DoublyLinkedListElement<T>* new_element = new DoublyLinkedListElement<T>(entry,first);
00091         if (!last) 
00092             last=new_element;
00093         if (first) 
00094             first->previous=new_element;
00095         first=new_element;
00096         n_elements++;
00097         return new_element;
00098     }
00099 
00100     inline void moveToFront(DoublyLinkedListElement<T>* element)
00101     {
00102 #ifdef BOUNDCHECK
00103         if (dbg) 
00104             cout << "calling DoublyLinkedList::moveToFront(" << element << endl;
00105         if (!element) PLERROR("DoublyLinkedList::moveToFront called with NULL element\n");
00106 #endif
00107         if (element!=first)
00108         {
00109             DoublyLinkedListElement<T>* next = element->next;
00110             DoublyLinkedListElement<T>* previous = element->previous;
00111             // there must be a previous o/w element would have been first
00112 #ifdef BOUNDCHECK
00113             if (!previous)
00114                 PLERROR("DoublyLinkedList::moveToFront called on incorrect element or corrupted list\n");
00115             if (previous->next != element)
00116                 PLERROR("DoublyLinkedList::moveToFront called on element not part of list (previous->next != element)\n");
00117             if (next && next->previous != element)
00118                 PLERROR("DoublyLinkedList::moveToFront called on element not part of list (next->previous != element)\n");
00119 #endif
00120             element->next = first;
00121             element->previous = 0;
00122             previous->next = next; 
00123             if (next)
00124                 next->previous = previous;
00125             first->previous = element;
00126             first = element;
00127             if (element==last)
00128                 last = previous;
00129         }
00130         
00131     }
00132 
00133     inline void removeLast() {
00134         if (dbg) 
00135             cout << "calling DoublyLinkedList::removeLast()" << endl;
00136         if (last)
00137         {
00138             DoublyLinkedListElement<T>* before_last = last->previous;
00139             if (first == last)
00140                 first = 0;
00141             last->previous=last->next=0; delete last;
00142             last = before_last;
00143             if (last)
00144                 last->next = 0;
00145             n_elements--;
00146         }
00147     }
00148 
00149     inline int nElements() { return n_elements; }
00150 
00151     inline virtual ~DoublyLinkedList() {
00152         while (first)
00153         {
00154             DoublyLinkedListElement<T>* next = first->next;
00155             delete first;
00156             first = next;
00157         }
00158     }
00159 };
00160 
00161 template <class T>
00162 inline int sizeInBytes(const DoublyLinkedListElement<T>& element) { return 2*sizeof(DoublyLinkedListElement<T>*)+sizeInBytes(element.entry); }
00163 
00164 } // end of namespace PLearn
00165 
00166 
00167 #endif
00168 
00169 
00170 /*
00171   Local Variables:
00172   mode:c++
00173   c-basic-offset:4
00174   c-file-style:"stroustrup"
00175   c-file-offsets:((innamespace . 0)(inline-open . 0))
00176   indent-tabs-mode:nil
00177   fill-column:79
00178   End:
00179 */
00180 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines