- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

# C:/Musimathics_local/Musimat/include/List.h

Go to the documentation of this file.

    00001 /* $Revision: 1.2 $ $Date: 2006/09/09 06:22:53 $ $Author: dgl $ $Name:  $ $Id: _list_8h-source.html,v 1.2 2006/09/09 06:22:53 dgl Exp $ */
    00002 #ifndef LIST_H
    00003 #define LIST_H
    00004
    00005 // The Musimat Tutorial © 2006 Gareth Loy
    00006 // Derived from Chapter 9 and Appendix B of "Musimathics Vol. 1" © 2006 Gareth Loy
    00007 // and published exclusively by The MIT Press.
    00008 // This program is released WITHOUT ANY WARRANTY; without even the implied
    00009 // warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
    00010 // For information on usage and redistribution, and for a DISCLAIMER OF ALL
    00011 // WARRANTIES, see the file, "LICENSE.txt," in this distribution.
    00012 // "Musimathics" is available here:     http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10916
    00013 // Gareth Loy's Musimathics website:    http://www.musimathics.com/
    00014 // The Musimat website:                 http://www.musimat.com/
    00015 // This program is released under the terms of the GNU General Public License
    00016 // available here:                      http://www.gnu.org/licenses/gpl.txt
    00017
    00020
    00021 #include <assert.h>
    00022 #include <memory.h>
    00023 #include <iostream>
    00024 using namespace std;
    00025
    00030
    00031 template <class Type>
    00032 class List
    00033 {
    00036         friend ostream& operator<<(ostream& os,Const List& r) {
    00037                 If (r.m_len > 0)
    00038                         os << "(";
    00039                 for (Integer i = 0; i < r.m_len; i++) {
    00040                         os << r.m_val[i];
    00041                         If (i != r.m_len-1)
    00042                                 os << ", ";
    00043                         Else
    00044                                 os << ")";
    00045                 }
    00046                 os << endl;
    00047                 Return os;
    00048          }
    00049
    00053          friend Void adjustSize(Integer len, List& r) {
    00054                 If (r.m_val == 0) {
    00055                         r.m_val = new Type [ r.m_len = len+1 ];
    00056                 } Else If (r.m_len <= len) {
    00057                         r.m_len = len+1;
    00058                         r.m_val = (Type*) realloc( r.m_val, r.m_len * sizeof(Type));
    00059                 }
    00060          }
    00061
    00064          friend istream& operator>>(istream& is, List& r) {
    00065                  char ch;
    00066                  Type t;
    00067                  Integer len = 0;
    00068                  is >> ch;
    00069                  If (ch != '{' And ch != '(')
    00070                          Return is;
    00071                  While (is >> t >> ch And ch == ',') {
    00072                         adjustSize(len, r);
    00073                         r.m_val[len++] = t;
    00074                  }
    00075                 adjustSize(len, r);
    00076                 r.m_val[len++] = t;
    00077                 assert( ch == '}' || ch == ')');
    00078                 Return is;
    00079          }
    00080
    00081 public:
    00082
    00085         List() : m_val(0), m_len(0) { }
    00086
    00091         List( List Const& L ) {
    00092                 m_val = new Type [ m_len = L.m_len ];
    00093                 memcpy(m_val, L.m_val, sizeof(Type) * m_len);
    00094         }
    00095
    00100         List(Type i_) {
    00101                 m_val = new Type [ m_len = 1 ];
    00102                 m_val[0] = i_;
    00103         }
    00104
    00110         List(Type i1_, Type i2_)  {
    00111                 m_val = new Type [ m_len = 2 ];
    00112                 m_val[0] = i1_;
    00113                 m_val[1] = i2_;
    00114         }
    00115
    00117         List(Type i1_, Type i2_, Type i3_)  {
    00118                 m_val = new Type [ m_len = 3 ];
    00119                 m_val[0] = i1_;
    00120                 m_val[1] = i2_;
    00121                 m_val[2] = i3_;
    00122         }
    00123
    00125         List(Type i1_, Type i2_, Type i3_, Type i4_)  {
    00126                 m_val = new Type [ m_len = 4 ];
    00127                 m_val[0] = i1_;
    00128                 m_val[1] = i2_;
    00129                 m_val[2] = i3_;
    00130                 m_val[3] = i4_;
    00131         }
    00132
    00134         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_)  {
    00135                 m_val = new Type [ m_len = 5 ];
    00136                 m_val[0] = i1_;
    00137                 m_val[1] = i2_;
    00138                 m_val[2] = i3_;
    00139                 m_val[3] = i4_;
    00140                 m_val[4] = i5_;
    00141         }
    00142
    00144         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_)  {
    00145                 m_val = new Type [ m_len = 6 ];
    00146                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;
    00147         }
    00148
    00150         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_)  {
    00151                 m_val = new Type [ m_len = 7 ];
    00152                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;
    00153         }
    00154
    00156         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_)  {
    00157                 m_val = new Type [ m_len = 8 ];
    00158                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00159         }
    00160
    00162         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_)  {
    00163                 m_val = new Type [ m_len = 9 ];
    00164                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00165                 m_val[8] = i9_;
    00166         }
    00167
    00169         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_, Type i10_)  {
    00170                 m_val = new Type [ m_len = 10 ];
    00171                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00172                 m_val[8] = i9_; m_val[9] = i10_;
    00173         }
    00174
    00176         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_, Type i10_, Type i11_)  {
    00177                 m_val = new Type [ m_len = 11 ];
    00178                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00179                 m_val[8] = i9_; m_val[9] = i10_; m_val[10] = i11_;
    00180         }
    00181
    00183         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_, Type i10_, Type i11_, Type i12_)  {
    00184                 m_val = new Type [ m_len = 12 ];
    00185                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00186                 m_val[8] = i9_; m_val[9] = i10_; m_val[10] = i11_; m_val[11] = i12_;
    00187         }
    00188
    00190         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_, Type i10_, Type i11_, Type i12_, Type i13_)  {
    00191                 m_val = new Type [ m_len = 13 ];
    00192                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00193                 m_val[8] = i9_; m_val[9] = i10_; m_val[10] = i11_; m_val[11] = i12_; m_val[12] = i13_;
    00194         }
    00195
    00197         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_, Type i10_, Type i11_, Type i12_, Type i13_, Type i14_ )  {
    00198                 m_val = new Type [ m_len = 14 ];
    00199                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00200                 m_val[8] = i9_; m_val[9] = i10_; m_val[10] = i11_; m_val[11] = i12_; m_val[12] = i13_; m_val[13] = i14_;
    00201         }
    00202
    00204         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_, Type i10_, Type i11_, Type i12_, Type i13_, Type i14_, Type i15_ )  {
    00205                 m_val = new Type [ m_len = 15 ];
    00206                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00207                 m_val[8] = i9_; m_val[9] = i10_; m_val[10] = i11_; m_val[11] = i12_; m_val[12] = i13_; m_val[13] = i14_; m_val[14] = i15_;
    00208         }
    00209
    00211         List(Type i1_, Type i2_, Type i3_, Type i4_, Type i5_, Type i6_, Type i7_, Type i8_, Type i9_, Type i10_, Type i11_, Type i12_, Type i13_, Type i14_, Type i15_,
    00212                 Type i16_, Type i17_, Type i18_, Type i19_, Type i20_, Type i21_, Type i22_ )  {
    00213                 m_val = new Type [ m_len = 22 ];
    00214                 m_val[0] = i1_; m_val[1] = i2_;  m_val[2] = i3_; m_val[3] = i4_; m_val[4] = i5_; m_val[5] = i6_;  m_val[6] = i7_;  m_val[7] = i8_;
    00215                 m_val[8] = i9_; m_val[9] = i10_; m_val[10] = i11_; m_val[11] = i12_; m_val[12] = i13_; m_val[13] = i14_; m_val[14] = i15_;
    00216                 m_val[15] = i16_; m_val[16] = i17_; m_val[17] = i18_; m_val[18] = i19_; m_val[19] = i20_; m_val[20] = i21_; m_val[21] = i22_;
    00217         }
    00218
    00220         ~List() {
    00221                 If ( m_val )
    00222                         delete [] m_val;
    00223                 m_val = 0;
    00224                 m_len = 0;
    00225         }
    00226
    00229         Bool operator==( Const List& L ) {
    00230                 If ( L.m_len != m_len )
    00231                         Return(False);
    00232                 For( Integer i = 0; i < length(); i++ ) {
    00233                         If ( L.m_val[i] != m_val[i] )
    00234                                 Return( False );
    00235                 }
    00236                 Return( True );
    00237         }
    00238
    00240         Bool operator!=( Const List& L ) {
    00241                 If ( L.m_len != m_len )
    00242                         Return(True);
    00243                 Integer cnt = 0;
    00244                 For( Integer i = 0; i < length(); i++ ) {
    00245                         If ( L.m_val[i] == m_val[i] )
    00246                                 cnt++;
    00247                 }
    00248                 Return( cnt != m_len );
    00249         }
    00250
    00254         List& operator+=( Const List& L ) {
    00255                 m_val = (Type*) realloc( m_val, (m_len + L.m_len) * sizeof(Type));
    00256                 memcpy(&m_val[m_len], L.m_val, sizeof(Type) * L.m_len);
    00257                 m_len += L.m_len;
    00258                 Return( *this );
    00259         }
    00260
    00264         List operator+( Const List &L ) {
    00265                 List r = *this;
    00266                 r += L;
    00267                 Return r;
    00268         }
    00269
    00273         List& operator=( Const List& L ) {
    00274                 If (this == &L)
    00275                         Return *this;
    00276                 If (m_val != 0)
    00277                         delete [] m_val;
    00278                 m_val = new Type [ m_len = L.m_len ];
    00279                 memcpy(m_val, L.m_val, sizeof(Type) * m_len);
    00280                 Return( *this );
    00281         }
    00282
    00287         Type& operator[]( Integer elem ) {
    00288                 assert( elem >= 0);
    00289                 checkSize(elem);
    00290                 Return m_val[elem];
    00291         }
    00292
    00296         List& operator+=( Const Type x ) {
    00297                 For ( Integer i = 0; i < m_len; i++ )
    00298                         m_val[i] += x;
    00299                 Return( *this );
    00300         }
    00301
    00305         List& operator-=( Const Type x ) {
    00306                 For ( Integer i = 0; i < m_len; i++ )
    00307                         m_val[i] -= x;
    00308                 Return( *this );
    00309         }
    00310
    00314         List& operator+( Const Type x ) {
    00315                 List* t = new List (*this);
    00316                 *t = *this; // copy this
    00317                 For ( Integer i = 0; i < m_len; i++ )
    00318                         t->m_val[i] += x;
    00319                 Return( *t );
    00320         }
    00321
    00325         List& operator-( Const Type x ) {
    00326                 List* t = new List [ m_len ];
    00327                 *t = *this; // copy this
    00328                 For ( Integer i = 0; i < m_len; i++ )
    00329                         t->m_val[i] -= x;
    00330                 Return( *t );
    00331         }
    00332
    00336         List& operator*( Const Type x ) {
    00337                 List* t = new List (*this);
    00338                 *t = *this; // copy this
    00339                 For ( Integer i = 0; i < m_len; i++ )
    00340                         t->m_val[i] *= x;
    00341                 Return( *t );
    00342         }
    00343
    00347         List& operator/( Const Type x ) {
    00348                 List* t = new List [ m_len ];
    00349                 *t = *this; // copy this
    00350                 For ( Integer i = 0; i < m_len; i++ )
    00351                         t->m_val[i] /= x;
    00352                 Return( *t );
    00353         }
    00354
    00358         //List& operator+=( Const Real x ) {
    00359         //      For ( Integer i = 0; i < m_len; i++ )
    00360         //              m_val[i] += Type(x);
    00361         //      Return( *this );
    00362         //}
    00363
    00367         //List& operator-=( Const Real x ) {
    00368         //      For ( Integer i = 0; i < m_len; i++ )
    00369         //              m_val[i] -= Type(x);
    00370         //      Return( *this );
    00371         //}
    00372
    00376         //List& operator+( Const Real x ) {
    00377         //      List* t = new List (*this);
    00378         //      *t = *this; // copy this
    00379         //      For ( Integer i = 0; i < m_len; i++ )
    00380         //              t->m_val[i] += Type(x);
    00381         //      Return( *t );
    00382         //}
    00383
    00387         //List& operator-( Const Real x ) {
    00388         //      List* t = new List [ m_len ];
    00389         //      *t = *this; // copy this
    00390         //      For ( Integer i = 0; i < m_len; i++ )
    00391         //              t->m_val[i] -= Type(x);
    00392         //      Return( *t );
    00393         //}
    00394
    00398         //List& operator*( Const Real x ) {
    00399         //      List* t = new List (*this);
    00400         //      *t = *this; // copy this
    00401         //      For ( Integer i = 0; i < m_len; i++ )
    00402         //              t->m_val[i] *= Type(x);
    00403         //      Return( *t );
    00404         //}
    00405
    00409         //List& operator/( Const Real x ) {
    00410         //      List* t = new List;
    00411         //      *t = *this;
    00412         //      For ( Integer i = 0; i < m_len; i++ )
    00413         //              t->m_val[i] /= Type(x);
    00414         //      Return( *t );
    00415         //}
    00416
    00419         Void print(String s = 0) {
    00420                 If (s)
    00421                         cout << s;
    00422                 cout << "{ ";
    00423                 cout.precision(2);
    00424                 For (Integer i = 0; i < m_len-1; i++)
    00425                         cout << m_val[i] << ", ";
    00426                 cout << m_val[m_len-1];
    00427                 cout << " }" << endl;
    00428         }
    00429
    00431         Void SetListSize(Integer n) {
    00432         If(m_val)
    00433                         delete[] m_val;
    00434         If (n > 0) {
    00435             m_val = new Type[n];
    00436             memset( m_val, 0, sizeof(Type) * n / sizeof(char) );
    00437         }
    00438         Else
    00439                         m_val = NULL;
    00440         m_len = n;
    00441     }
    00442
    00448         Void checkSize(Integer len) {
    00449                 If (m_val == 0)
    00450                         m_val = new Type [ m_len = len+1 ];
    00451                 Else If (m_len <= len) {
    00452                         m_len = len+1;
    00453                         m_val = (Type*) realloc( m_val, m_len * sizeof(Type));
    00454                 }
    00455         }
    00456
    00459         Integer length() {
    00460                 Return m_len;
    00461         }
    00462
    00465         Type max() {
    00466                 assert(m_len > 0);
    00467                 Type max = m_val[0];
    00468                 For ( Integer i = 1; i < m_len; i++ )
    00469                         max = m_val[i] < max ? max : m_val[i];
    00470                 Return max;
    00471         }
    00472
    00476         Integer maxPos() {
    00477                 assert(m_len > 0);
    00478                 Type max = m_val[0];
    00479                 Integer mp = 0;
    00480                 For ( Integer i = 1; i < m_len; i++ ) {
    00481                         If ( m_val[i] > max ) {
    00482                                 max = m_val[i];
    00483                                 mp = i;
    00484                         }
    00485                 }
    00486                 Return mp;
    00487         }
    00488
    00491         Type min() {
    00492                 assert(m_len > 0);
    00493                 Type min = m_val[0];
    00494                 For ( Integer i = 1; i < m_len; i++ )
    00495                         min = m_val[i] < min ? m_val[i] : min;
    00496                 Return min;
    00497         }
    00498
    00502         Integer minPos() {
    00503                 assert(m_len > 0);
    00504                 Type min = m_val[0];
    00505                 Integer mp = 0;
    00506                 For ( Integer i = 1; i < m_len; i++ ) {
    00507                         If ( m_val[i] < min ) {
    00508                                 min = m_val[i];
    00509                                 mp = i;
    00510                         }
    00511                 }
    00512                 Return mp;
    00513         }
    00514
    00518         Void rotate( Integer n, Integer i = 0 ) {
    00519                 n = Mod( n, length() );                 // constrain rotation to length of list
    00520                 Type x = m_val[ i ];                    // store f[ i ] for use after recursion
    00521                 If ( i < length() - 1 )                 // reached the end?
    00522                         rotate( n, i+1 );                       // no, set up next element via recursion
    00523                 // We continue from here when the recursion unwinds
    00524                 Integer pos = PosMod( i+n, length() );  // index list modulo its length
    00525                 m_val[ pos ] = x;                               // assign value of x saved above
    00526         }
    00527
    00532         Void transpose( Type t, Type lim ) {
    00533                 For ( Integer i = 0; i < length(); i = i + 1 ) {
    00534                         Type x = m_val[ i ] + t;
    00535                         m_val[ i ] = PosMod(x, lim);
    00536                 }
    00537         }
    00538
    00541         Void invert( Type lim ) {
    00542                 For ( Integer i = 0; i < length(); i = i + 1 ) {
    00543                         m_val[ i ] = ( lim - m_val[ i ] ) % lim;
    00544                 }
    00545         }
    00546
    00548         Void retrograde( ) {
    00549                 Integer n = length( );
    00550                 Type* t = new Type [ m_len ];
    00551                 memcpy(t, m_val, sizeof(Type) * m_len);
    00552                 For ( Integer i = 0; i < n; i = i + 1 )
    00553                         m_val[ i ] = t[ n - i - 1 ];
    00554         }
    00555
    00556 private:
    00557         Type* m_val;
    00558         Integer m_len;
    00559 };
    00560
    00561
    00562
    00564 template<class Type> inline Integer Length( Type& L )  { Return( L.length() ); }
    00565
    00566
    00572
    00574 template<class Type> Type inline Join( Type& L1, Type& L2 ) { Return ( L1 + L2 ); }
    00575
    00577 template<class Type> Type inline Join( Type& L1, Type& L2, Type& L3) { Return L1 + L2 + L3; }
    00578
    00580 template<class Type> Type inline Join( Type& L1, Type& L2, Type& L3, Type& L4) { Return L1 + L2 + L3 + L4; }
    00581
    00583 template<class Type> Type inline Join( Type& L1, Type& L2, Type& L3, Type& L4, Type& L5) { Return L1 + L2 + L3 + L4 + L5; }
    00584
    00586 template<class Type> Type inline Join( Type& L1, Type& L2, Type& L3, Type& L4, Type& L5, Type& L6) { Return L1 + L2 + L3 + L4 + L5 + L6; }
    00587
    00589 template<class Type> Type inline Join( Type& L1, Type& L2, Type& L3, Type& L4, Type& L5, Type& L6, Type& L7) { Return L1 + L2 + L3 + L4 + L5 + L6 + L7; }
    00591
    00593 template<class TargetListType, class ElementType, class ListType> TargetListType Map( ListType L, ElementType (*fn)(ElementType) )
    00594 {
    00595         For( Integer i = 0; i < Length( L ); i++ )
    00596                 L[i] = fn( L[i] );
    00597         Return( L );
    00598 }
    00599
    00600 #endif // LIST_H