Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/Todd-Coxeter/include/CosetTables.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: 
00003  */
00004 
00005 // Copyright (C) 1996 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 //
00008 // Contents: Definition of class CosetTable, CosetRow.
00009 //
00010 // Principal Author: Alexey Myasnikov
00011 //
00012 // Status: Useable
00013 //
00014 // Usage:
00015 //
00016 // Revision History:
00017 //
00018 //
00019 
00020 
00021 #ifndef _COSET_TABLES_H_
00022 #define _COSET_TABLES_H_
00023 
00024 #include "Word.h"
00025 #include "CosetRelations.h"
00026 #include "EasyList.h"
00027 #include "Integer.h"
00028 
00029 // Internal class to keep rows of Coset Tables.
00030 class CosetRow {
00031 public:
00032   CosetRow(int length):
00033     row(new int[length]),
00034     left(0),
00035     right(length)
00036   { 
00037     if (row == NULL)
00038       error ("Memory exhausted in Todd Coxeter algorithm");
00039      //    for (int i=0;i<length;i++)
00040      //        row[i] = 0;
00041   }
00042   
00043   ~CosetRow(){ delete[] row;}
00044   CosetRow(const CosetRow&);
00045   bool operator == (const CosetRow& cr);
00046   int getCell (int i)const {return row[i];}
00047   void setCell(int i,int index) {row[i]= index;}
00048   CosetRow operator = (const CosetRow& cr);
00049 
00050   int left;
00051   // Position of last filled cell in a row from the left
00052   int right;
00053   // Position of first filled cell in a row from the right
00054 private:
00055   void printOn(ostream& ostr=cout){
00056     cout << "left-"<<left<<"; right-"<<right<<endl;
00057   }
00058   int* row;
00059 };
00060 
00061 // --------------------- CosetTable --------------------//
00062 // Internal class of Todd-Coxeter
00063 
00064 class CosetTable {
00065 public:
00066   CosetTable(const Word& w,CosetRelationsSet& crs,
00067              VectorOf<Integer>& coset_nums,
00068              bool sgTable = false);
00069  
00070   // sgTable true if table represents subgroup generator.
00071   ~CosetTable();
00072   //////////////////////////////////////////////////////////////////////// 
00073   //                                                                   //
00074   // Methods                                                           //
00075   //                                                                   //
00076   ///////////////////////////////////////////////////////////////////////
00077 
00078   bool complete() const {return !filedTable.isEmpty() && 
00079                            currentTable.isEmpty();}
00080   // True if table is complete, i.e. All rows filled.
00081   bool addCoset(int coset_number,bool first_used = false);
00082   // Add a new coset to the table. If first_used filled with
00083   // coset_number first empty from the left cell. If the table
00084   // represents group relator, adds new row to the table.
00085   bool removeCosets(int bad);
00086   // Raplaces all entries equals to 'bad' with 'good' numbers.
00087   bool iterateTable();
00088   // Fills table with coset numbers.
00089   
00090   int numberOfRows() const {return activeOrder;}
00091   // returns current number of rows in the table.
00092   // It is equal to number of rows in filled and current tables
00093 
00094   //////////////////////////////////////////////////////////////////////// 
00095   //                                                                   //
00096   // Operators                                                         //
00097   //                                                                   //
00098   ///////////////////////////////////////////////////////////////////////
00099   
00100   friend ostream& operator << ( ostream& ostr, const CosetTable& ct )
00101   {
00102     ct.printOn(ostr);
00103     return ostr;
00104   }
00105 private:
00106 
00107   CosetTable(const CosetTable&);
00108   void printOn( ostream& ostr=cout)const;  
00109   bool iterateFromRight();
00110   // Fills table with coset numbers from the left.
00111   bool iterateFromLeft();
00112   // Fills table with coset numbers from the right.
00113 
00114   bool getClosed( );
00115   // Checks if current row in the current table was filled
00116   // moves it to the filled table and adds relations if needed
00117   Integer getCosetInRow(int i,CosetRow& row)const;
00118 
00119   int numOfLetters;
00120   // Length of 'relation'
00121   Word relation;
00122   // Word for which the table was bilt
00123   EasyList<CosetRow*> currentTable;
00124   // Table with rows,which was  not filled yet.
00125   EasyList<CosetRow*> filedTable;
00126   // Table with  filled rows.
00127   EasyList<CosetRow*> emptyTable;
00128   // Table with rows freed after conflicts.
00129   // I keep them for avoid extra operations with memory
00130   CosetRelationsSet& theRelationSet;
00131   // Reference to the set of relations. It suppose to be
00132   // common for all tables. 
00133   bool relatorsChanged;
00134   // true if relation was added to the relation set,
00135   // during last iteration
00136   int activeOrder;
00137   // Keeps current number of rows
00138   bool isSubgroupTable;
00139   // true if 'relation' is a subgroup generator
00140   VectorOf<Integer>& cosetNumbers;
00141 };
00142 #endif
00143 
00144 
00145 
00146 
00147 
00148 
00149 
00150 
00151 
00152 
00153 

Generated at Tue Jun 19 09:49:43 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001