PLearn 0.1
|
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 :