initial checkin

git-svn-id: https://phat.googlecode.com/svn/trunk@2 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d

5 files changed, 495 insertions, 0 deletions

diff --git a/include/phat/representations/abstract_pivot_column.h b/include/phat/representations/abstract_pivot_column.h
new file mode 100644
index 0000000..a84e013
--- /dev/null
+++ b/include/phat/representations/abstract_pivot_column.h
@@ -0,0 +1,158 @@
+/*  Copyright 2013 IST Austria

+    Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus

+

+    This file is part of PHAT.

+

+    PHAT is free software: you can redistribute it and/or modify

+    it under the terms of the GNU Lesser General Public License as published by

+    the Free Software Foundation, either version 3 of the License, or

+    (at your option) any later version.

+

+    PHAT 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 Lesser General Public License for more details.

+

+    You should have received a copy of the GNU Lesser General Public License

+    along with PHAT.  If not, see <http://www.gnu.org/licenses/>. */

+

+#pragma once

+

+#include <phat/helpers/misc.h>

+#include <phat/representations/vector_vector.h>

+

+namespace phat {

+

+    // Note: We could even make the rep generic in the underlying Const representation

+    //       But I cannot imagine that anything else than vector<vector<index>> would

+    //       make sense

+    template< typename PivotColumn >

+    class abstract_pivot_column : public vector_vector {

+    public:

+        

+    protected:

+        typedef vector_vector Base;

+        typedef PivotColumn pivot_column;

+

+        // For parallization purposes, it could be more than one full column

+        mutable thread_local_storage< pivot_column > _pivot_columns;

+        mutable thread_local_storage< index > pos_of_pivot_columns;

+

+        pivot_column& get_pivot_column() const {

+            return _pivot_columns();

+        }

+

+        bool is_represented_by_pivot_column( index idx ) const {

+            return pos_of_pivot_columns() == idx;

+        }

+      

+        void unset_pos_of_pivot_column() {

+            index idx = pos_of_pivot_columns();

+            if( idx != -1 ) {

+                _pivot_columns().get_column_and_clear( this->matrix[ idx ] );

+            }

+            pos_of_pivot_columns() = -1;

+        }

+        

+        void represent_by_pivot_column( index idx ) {

+            pos_of_pivot_columns() = idx;

+            get_pivot_column().add_column( matrix[ idx ] );

+        }

+

+    public:  

+

+        void _set_num_cols( index nr_of_columns ) {

+            #pragma omp parallel for

+            for( int tid = 0; tid < omp_get_num_threads(); tid++ ) {

+                _pivot_columns[ tid ].init( nr_of_columns );

+                pos_of_pivot_columns[ tid ] = -1;

+            }

+            Base::_set_num_cols( nr_of_columns );

+        }

+        // replaces(!) content of 'col' with boundary of given index

+        void _get_col( index idx, column& col  ) const {

+            col.clear();

+            if( is_represented_by_pivot_column( idx ) ) {

+                pivot_column& pivot_column = get_pivot_column();

+                pivot_column.get_column_and_clear( col );

+                pivot_column.add_column( col );

+            } else {

+                Base::_get_col( idx, col );

+            }

+        }

+        

+        // true iff boundary of given idx is empty

+        bool _is_empty( index idx ) const {

+            return is_represented_by_pivot_column( idx ) ? get_pivot_column().empty() : Base::_is_empty( idx );

+        }

+

+        // largest row index of given column idx (new name for lowestOne())

+        index _get_max_index( index idx ) const {

+            if( is_represented_by_pivot_column( idx ) ) {

+                pivot_column& pivot_column = get_pivot_column();

+                if( pivot_column.empty() ) {

+                    return -1;

+                } else {

+                    return pivot_column.max_index();

+                }

+            } else {

+                return Base::_get_max_index( idx );

+            }

+        }

+

+        // adds column 'source' to column 'target'

+        void _add_to( index source, index target ) {

+            if( !is_represented_by_pivot_column( target ) ) {

+                unset_pos_of_pivot_column();

+                represent_by_pivot_column( target );

+            } 

+            get_pivot_column().add_column( matrix[source] );

+        }

+

+        // clears given column

+        void _clear( index idx ) {

+            if( is_represented_by_pivot_column( idx ) ) {

+                column dummy;

+                get_pivot_column().get_column_and_clear(dummy);

+            } else {

+                Base::_clear( idx );

+            }

+        }

+

+        void _set_col( index idx, const column& col  ) {

+            if( is_represented_by_pivot_column( idx ) ) {

+                column dummy;

+                pivot_column& pivot_column = get_pivot_column();

+                pivot_column.get_column_and_clear( dummy );

+                pivot_column.add_column( col );

+            } else {

+                Base::_set_col( idx, col );

+            }

+        }

+

+        // removes the maximal index of a column

+        void _remove_max( index idx ) {

+            _toggle( idx, _get_max_index( idx ) );

+        }

+

+        //// toggles given index pair

+        void _toggle( index col_idx, index row_idx ) {

+            if( !is_represented_by_pivot_column( col_idx ) ) {

+                unset_pos_of_pivot_column();

+                represent_by_pivot_column( col_idx );

+            } 

+            get_pivot_column().add_index( row_idx );

+        }

+

+        // syncronizes all data structures (essential for openmp stuff)

+        // has to be called before and after any multithreaded access!

+        void _sync() { 

+            #pragma omp parallel for

+            for( int tid = 0; tid < omp_get_num_threads(); tid++ )

+                unset_pos_of_pivot_column();

+        } 

+

+    };

+}

+

+

diff --git a/include/phat/representations/full_pivot_column.h b/include/phat/representations/full_pivot_column.h
new file mode 100644
index 0000000..9e0c348
--- /dev/null
+++ b/include/phat/representations/full_pivot_column.h
@@ -0,0 +1,81 @@
+/*  Copyright 2013 IST Austria

+    Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus

+

+    This file is part of PHAT.

+

+    PHAT is free software: you can redistribute it and/or modify

+    it under the terms of the GNU Lesser General Public License as published by

+    the Free Software Foundation, either version 3 of the License, or

+    (at your option) any later version.

+

+    PHAT 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 Lesser General Public License for more details.

+

+    You should have received a copy of the GNU Lesser General Public License

+    along with PHAT.  If not, see <http://www.gnu.org/licenses/>. */

+

+#pragma once

+

+#include <phat/helpers/misc.h>

+#include <phat/representations/abstract_pivot_column.h>

+

+namespace phat {

+    class full_column {

+

+    protected:

+        std::priority_queue< index > m_history;

+        std::vector< char > m_isInHistory;

+        std::vector< char > m_data;

+

+    public:

+        void init( const index total_size ) {

+            m_data.resize( total_size, false );

+            m_isInHistory.resize( total_size, false );

+        }

+

+        void add_column( const column& col ) {

+            for( index idx = 0; idx < (index) col.size(); idx++ ) {

+                add_index( col[ idx ] );

+            }

+        }

+        void add_index( const index idx ) {

+            if( !m_isInHistory[ idx ] ) {

+                m_history.push( idx );

+                m_isInHistory[ idx ] = true; 

+            }

+

+            m_data[ idx ] = !m_data[ idx ];

+        }

+

+        index max_index() {

+            while( m_history.size() > 0 ) {

+                index topIndex = m_history.top();

+                if( m_data[ topIndex ] ) {

+                    return topIndex;

+                } else {

+                    m_history.pop();

+                    m_isInHistory[ topIndex ] = false;

+                }

+            }

+    

+            return -1;

+        }

+

+        void get_column_and_clear( column& col ) {

+            col.clear();

+            while( !empty() ) {

+                col.push_back( max_index() );

+                add_index( max_index() );

+            }

+            std::reverse( col.begin(), col.end() );

+        }

+

+        bool empty() {

+            return (max_index() == -1);   

+        }

+    };

+

+    typedef abstract_pivot_column< full_column > full_pivot_column;

+}

diff --git a/include/phat/representations/sparse_pivot_column.h b/include/phat/representations/sparse_pivot_column.h
new file mode 100644
index 0000000..c851a2b
--- /dev/null
+++ b/include/phat/representations/sparse_pivot_column.h
@@ -0,0 +1,62 @@
+/*  Copyright 2013 IST Austria

+    Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus

+

+    This file is part of PHAT.

+

+    PHAT is free software: you can redistribute it and/or modify

+    it under the terms of the GNU Lesser General Public License as published by

+    the Free Software Foundation, either version 3 of the License, or

+    (at your option) any later version.

+

+    PHAT 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 Lesser General Public License for more details.

+

+    You should have received a copy of the GNU Lesser General Public License

+    along with PHAT.  If not, see <http://www.gnu.org/licenses/>. */

+

+#pragma once

+

+#include <phat/helpers/misc.h>

+#include <phat/representations/abstract_pivot_column.h>

+

+namespace phat {

+    class sparse_column {

+

+    protected:

+        std::set< index > m_data;

+

+    public:

+        void init( const index total_size ) {

+            m_data.clear(); 

+        }

+

+        void add_column( const column& col ) {

+            for( index idx = 0; idx < (index) col.size(); idx++ )

+                add_index( col[ idx ] );

+        }

+

+        void add_index( const index idx ) {

+            std::pair< std::set< index >::iterator, bool > result = m_data.insert( idx );

+            if( result.second == false )

+                m_data.erase( result.first );

+        }

+

+        index max_index() {

+            return m_data.empty() ? -1 : *m_data.rbegin();

+        }

+

+        void get_column_and_clear( column& col ) {

+            col.clear();

+            col.assign( m_data.begin(), m_data.end() );

+            m_data.clear();

+        }

+

+        bool empty() {

+            return m_data.empty();

+        }

+    };

+

+    typedef abstract_pivot_column< sparse_column > sparse_pivot_column;

+}

diff --git a/include/phat/representations/vector_set.h b/include/phat/representations/vector_set.h
new file mode 100644
index 0000000..2ce0c56
--- /dev/null
+++ b/include/phat/representations/vector_set.h
@@ -0,0 +1,104 @@
+/*  Copyright 2013 IST Austria
+    Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus
+
+    This file is part of PHAT.
+
+    PHAT is free software: you can redistribute it and/or modify
+    it under the terms of the GNU Lesser General Public License as published by
+    the Free Software Foundation, either version 3 of the License, or
+    (at your option) any later version.
+
+    PHAT 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 Lesser General Public License for more details.
+
+    You should have received a copy of the GNU Lesser General Public License
+    along with PHAT.  If not, see <http://www.gnu.org/licenses/>. */
+
+#pragma once
+
+#include <phat/helpers/misc.h>
+
+namespace phat {
+    class vector_set {
+
+    protected:
+        typedef std::set< index > internal_column; 
+        std::vector< dimension > dims;
+        std::vector< internal_column > matrix;
+
+    public:
+        // overall number of cells in boundary_matrix
+        index _get_num_cols() const {
+            return (index)matrix.size(); 
+        }
+        void _set_num_cols( index nr_of_columns ) {
+            dims.resize( nr_of_columns );
+            matrix.resize( nr_of_columns );
+        }
+
+         // dimension of given index
+        dimension _get_dim( index idx ) const { 
+            return dims[ idx ]; 
+        }
+        void _set_dim( index idx, dimension dim ) { 
+            dims[ idx ] = dim; 
+        }
+
+        // replaces(!) content of 'col' with boundary of given index
+        void _get_col( index idx, column& col  ) const {
+            col.clear();
+            col.reserve( matrix[idx].size() );
+            std::copy (matrix[idx].begin(), matrix[idx].end(), std::back_inserter(col) );
+            std::sort( col.begin(), col.end() );
+        }
+        void _set_col( index idx, const column& col  ) {
+            matrix[ idx ].clear();
+            matrix[ idx ].insert( col.begin(), col.end() );
+        }
+
+        // true iff boundary of given idx is empty
+        bool _is_empty( index idx ) const {
+            return matrix[ idx ].empty();    
+        }
+
+        // largest row index of given column idx (new name for lowestOne())
+        index _get_max_index( index idx ) const {
+            return matrix[ idx ].empty() ? -1 : *matrix[ idx ].rbegin();
+        }
+
+        // removes the maximal index of a column
+        void _remove_max( index idx ) {
+            internal_column::iterator it = matrix[ idx ].end();
+            it--;
+            matrix[ idx ].erase( it );
+        }
+        
+        // clears given column
+        void _clear( index idx ) {
+            matrix[ idx ].clear();    
+        }
+
+        // syncronizes all data structures (essential for openmp stuff)
+        void _sync() {}
+
+        // adds column 'source' to column 'target'
+        void _add_to( index source, index target ) {
+            internal_column& source_col = matrix[ source ];
+            for( internal_column::const_iterator source_it = source_col.begin(); 
+                 source_it != source_col.end(); source_it++ ) {
+                _toggle(target, *source_it);
+            }
+        }
+
+        //// toggles given index pair
+        void _toggle( index col_idx, index row_idx ) {
+            internal_column& col = matrix[ col_idx ];
+            std::pair< internal_column::iterator, bool > result = col.insert( row_idx );
+            if( !result.second ) {
+                col.erase( result.first );
+            }
+        }
+    };
+}
diff --git a/include/phat/representations/vector_vector.h b/include/phat/representations/vector_vector.h
new file mode 100644
index 0000000..c313c20
--- /dev/null
+++ b/include/phat/representations/vector_vector.h
@@ -0,0 +1,90 @@
+/*  Copyright 2013 IST Austria

+    Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus

+

+    This file is part of PHAT.

+

+    PHAT is free software: you can redistribute it and/or modify

+    it under the terms of the GNU Lesser General Public License as published by

+    the Free Software Foundation, either version 3 of the License, or

+    (at your option) any later version.

+

+    PHAT 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 Lesser General Public License for more details.

+

+    You should have received a copy of the GNU Lesser General Public License

+    along with PHAT.  If not, see <http://www.gnu.org/licenses/>. */

+

+#pragma once

+

+#include <phat/helpers/misc.h>

+

+namespace phat {

+    class vector_vector {

+

+    protected:

+        std::vector< dimension > dims;

+        std::vector< column > matrix;

+

+    public:

+        // overall number of cells in boundary_matrix

+        index _get_num_cols() const {

+            return (index)matrix.size(); 

+        }

+        void _set_num_cols( index nr_of_columns ) {

+            dims.resize( nr_of_columns );

+            matrix.resize( nr_of_columns );

+        }

+

+        // dimension of given index

+        dimension _get_dim( index idx ) const { 

+            return dims[ idx ]; 

+        }

+        void _set_dim( index idx, dimension dim ) { 

+            dims[ idx ] = dim; 

+        }

+

+        // replaces(!) content of 'col' with boundary of given index

+        void _get_col( index idx, column& col  ) const { 

+            col = matrix[ idx ]; 

+        }

+        void _set_col( index idx, const column& col  ) { 

+            matrix[ idx ] = col; 

+        }

+

+        // true iff boundary of given idx is empty

+        bool _is_empty( index idx ) const { 

+            return matrix[ idx ].empty(); 

+        }

+

+        // largest row index of given column idx (new name for lowestOne())

+        index _get_max_index( index idx ) const { 

+            return matrix[ idx ].empty() ? -1 : matrix[ idx ].back(); 

+        }

+

+        // removes the maximal index of a column

+        void _remove_max( index idx ) {

+            matrix[ idx ].pop_back();

+        }

+

+        // clears given column

+        void _clear( index idx ) { 

+            matrix[ idx ].clear(); 

+        }

+

+        // syncronizes all data structures (essential for openmp stuff)

+        void _sync() {}

+

+        // adds column 'source' to column 'target'

+        void _add_to( index source, index target ) {

+            column& source_col = matrix[ source ];

+            column& target_col = matrix[ target ];

+            column temp_col = target_col;

+            target_col.clear();

+            std::set_symmetric_difference( temp_col.begin(), temp_col.end(),

+                                           source_col.begin(), source_col.end(),

+                                           std::back_inserter( target_col ) );

+        }

+    };

+}