--- a/examples/alphashapes/alpharadius.cpp Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/alphashapes/alpharadius.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -1,8 +1,8 @@
-#include <sys.h>
-#include <debug.h>
+#include <utilities/sys.h>
+#include <utilities/debug.h>
#include "alphashapes3d.h"
-#include <filtration.h>
+#include <topology/filtration.h>
#include <iostream>
#include <fstream>
--- a/examples/alphashapes/alphashapes3d.cpp Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/alphashapes/alphashapes3d.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -1,8 +1,8 @@
-#include <sys.h>
-#include <debug.h>
+#include <utilities/sys.h>
+#include <utilities/debug.h>
#include "alphashapes3d.h"
-#include <filtration.h>
+#include <topology/filtration.h>
#include <iostream>
#include <fstream>
--- a/examples/alphashapes/alphashapes3d.h Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/alphashapes/alphashapes3d.h Tue Aug 14 17:15:08 2007 -0400
@@ -9,8 +9,8 @@
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>
-#include <simplex.h>
-#include <types.h>
+#include <topology/simplex.h>
+#include <utilities/types.h>
#include <vector>
#include <set>
--- a/examples/cech-complex/cech-complex.cpp Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/cech-complex/cech-complex.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -1,8 +1,8 @@
-#include <sys.h>
-#include <debug.h>
+#include <utilities/sys.h>
+#include <utilities/debug.h>
-#include <simplex.h>
-#include <filtration.h>
+#include <topology/simplex.h>
+#include <topology/filtration.h>
#include "Miniball_dynamic_d.h"
#include <algorithm>
--- a/examples/grid/combustion-vineyard.cpp Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/grid/combustion-vineyard.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -3,8 +3,8 @@
* Department of Computer Science, Duke University, 2005
*/
-#include <sys.h>
-#include <debug.h>
+#include <utilities/sys.h>
+#include <utilities/debug.h>
#include <iostream>
#include <fstream>
--- a/examples/grid/grid2D.h Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/grid/grid2D.h Tue Aug 14 17:15:08 2007 -0400
@@ -18,7 +18,7 @@
#include <boost/serialization/split_member.hpp>
#include <boost/serialization/nvp.hpp>
-#include "types.h"
+#include "utilities/types.h"
#include <boost/serialization/export.hpp>
--- a/examples/grid/grid2Dvineyard.h Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/grid/grid2Dvineyard.h Tue Aug 14 17:15:08 2007 -0400
@@ -6,11 +6,11 @@
#ifndef __GRID2DVINEYARD_H__
#define __GRID2DVINEYARD_H__
-#include "sys.h"
-#include "debug.h"
+#include "utilities/sys.h"
+#include "utilities/debug.h"
#include "grid2D.h"
-#include "lowerstarfiltration.h"
+#include "topology/lowerstarfiltration.h"
#include <CGAL/Kinetic/Inexact_simulation_traits_1.h>
#include <CGAL/Kinetic/Sort.h>
--- a/examples/grid/pdbdistance-vineyard.cpp Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/grid/pdbdistance-vineyard.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -1,6 +1,6 @@
//#include <boost/archive/binary_oarchive.hpp>
-#include "sys.h"
-#include "debug.h"
+#include "utilities/sys.h"
+#include "utilities/debug.h"
#include "pdbdistance.h"
#include "grid2Dvineyard.h"
--- a/examples/grid/pdbdistance.h Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/grid/pdbdistance.h Tue Aug 14 17:15:08 2007 -0400
@@ -16,7 +16,7 @@
#include <boost/serialization/access.hpp>
-#include "types.h"
+#include "utilities/types.h"
#include "grid2D.h"
#include <boost/serialization/export.hpp>
--- a/examples/triangle/triangle.cpp Sun Jul 01 00:00:00 2007 -0400
+++ b/examples/triangle/triangle.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -1,5 +1,5 @@
-#include "filtration.h"
-#include "simplex.h"
+#include "topology/filtration.h"
+#include "topology/simplex.h"
#include <vector>
#include <iostream>
--- a/include/circular_list.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,259 +0,0 @@
-/**
- * Singly-linked circular list implementation by Donovan Rebbechi <elflord@pegasus.rutgers.edu>.
- * Tiny modifications by DM to make ISO C++ compliant (i.e., so that the compiler stops complaining),
- * added size(), and boost serialization
- */
-
-#ifndef __CIRCULAR_LIST_H__
-#define __CIRCULAR_LIST_H__
-
-#include <iterator>
-
-#include <boost/serialization/access.hpp>
-#include <boost/serialization/split_member.hpp>
-#include <boost/serialization/nvp.hpp>
-#include <boost/serialization/binary_object.hpp>
-
-#include "types.h"
-
-
-template <class T>
-class List
-{
- struct Node
- {
- Node(const T& x,Node* y = 0):m_data(x),m_next(y){}
- T m_data;
- Node* m_next;
-
- private:
- // Serialization
- friend class boost::serialization::access;
-
- template<class Archive>
- void serialize(Archive& ar, version_type )
- {
- ar & make_nvp("data", m_data);
- ar & make_nvp("next", m_next);
- }
- };
-
- Node* m_node;
- size_t sz;
-
- private:
- // Serialization
- friend class boost::serialization::access;
-
- template<class Archive>
- void serialize(Archive& ar, version_type )
- { ar & make_nvp("root", m_node); }
-
-public:
- class const_iterator;
-
- class iterator
- : public std::iterator<std::forward_iterator_tag, T>
- {
- Node* m_rep;
- public:
- friend class List;
- friend class const_iterator;
- typedef T value_type;
- typedef T& reference;
- typedef T* pointer;
- typedef int difference_type;
- typedef std::forward_iterator_tag iterator_category;
-
- inline iterator(Node* x=0):m_rep(x){}
- inline iterator(const iterator& x):m_rep(x.m_rep) {}
- inline iterator(const const_iterator& x):m_rep(const_cast<Node*>(x.m_rep)) {} // not very safe
- inline iterator& operator=(const iterator& x)
- {
- m_rep=x.m_rep; return *this;
- }
- inline iterator& operator++()
- {
- m_rep = m_rep->m_next; return *this;
- }
- inline iterator operator++(int)
- {
- iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
- }
- inline reference operator*() const { return m_rep->m_next->m_data; }
- inline pointer operator->() const { return m_rep->m_next; }
- inline bool operator==(const iterator& x) const
- {
- return m_rep == x.m_rep;
- }
- inline bool operator!=(const iterator& x) const
- {
- return m_rep != x.m_rep;
- }
-
- };
-
- class const_iterator
- : public std::iterator<std::forward_iterator_tag, const T>
- {
- const Node* m_rep;
- public:
- friend class List;
- friend class iterator;
- typedef T value_type;
- typedef T& reference;
- typedef T* pointer;
- typedef int difference_type;
- typedef std::forward_iterator_tag iterator_category;
- inline const_iterator(const Node* x=0):m_rep(x){}
- inline const_iterator(const const_iterator& x):m_rep(x.m_rep) {}
- inline const_iterator(const iterator& x):m_rep(x.m_rep){}
- inline const_iterator& operator=(const const_iterator& x)
- {
- m_rep=x.m_rep; return *this;
- }
- inline const_iterator& operator=(const iterator& x)
- {
- m_rep=x.m_rep; return *this;
- }
- inline const_iterator& operator++()
- {
- m_rep = m_rep->m_next; return *this;
- }
- inline const_iterator operator++(int)
- {
- const_iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
- }
- inline reference operator*() const { return m_rep->m_next->m_data; }
- inline pointer operator->() const { return m_rep->m_next; }
- inline bool operator==(const const_iterator& x) const
- {
- return m_rep == x.m_rep;
- }
- inline bool operator!=(const const_iterator& x) const
- {
- return m_rep != x.m_rep;
- }
- };
-
- typedef T& reference;
- typedef const T& const_reference;
- typedef T* pointer;
- typedef const T* const_pointer;
-
- List() : m_node(new Node(T())), sz(0) { m_node->m_next = m_node; }
-
- List(const List& L) : m_node(new Node(T())), sz(L.sz)
- {
- m_node->m_next=m_node;
- for ( const_iterator i = L.begin(); i!= L.end(); ++i )
- push_front(*i);
- reverse();
- }
-
- void reverse()
- {
- if (empty())
- return;
- Node* new_m_node = m_node->m_next->m_next;
- Node* p = m_node; Node* i = m_node->m_next; Node* n;
- do
- {
- n = i->m_next;
- i->m_next = p;
- p = i; i = n;
- }
- while (p!=m_node);
- m_node = new_m_node;
- }
-
- void swap(List& x)
- {
- std::swap(m_node, x.m_node);
- std::swap(sz, x.sz);
- }
-
- List& operator=(const List& x)
- {
- List tmp(x);
- swap(tmp);
- return *this;
- }
-
- ~List() { clear(); delete m_node; }
- void clear() { while (!empty()) pop_front(); sz = 0; }
-
-
- inline size_t size() const { return sz; }
-
- inline void push_front(const T&x)
- {
- insert (begin(),x);
- }
- inline void push_back(const T& x)
- {
- insert (end(),x);
- }
- inline void pop_front()
- {
- erase(begin());
- }
- inline bool empty() const { return m_node == m_node->m_next; }
-
- inline T& front() { return *begin(); }
- inline const T& front() const { return *begin(); }
- inline T& back() { return m_node->m_data; }
- inline const T& back() const { return m_node->m_data; }
-
- inline iterator begin() { return iterator(m_node->m_next); }
- inline iterator end() { return iterator(m_node); }
- inline const_iterator begin() const
- {
- return const_iterator(m_node->m_next);
- }
- inline const_iterator end() const
- {
- return const_iterator(m_node);
- }
-
- iterator erase (iterator x)
- {
- if (x == end())
- return x;
-
- if (x.m_rep->m_next == m_node)
- m_node = x.m_rep;
-
- Node* tmp = x.m_rep->m_next;
- x.m_rep->m_next = x.m_rep->m_next->m_next;
- delete tmp;
- --sz;
-
- return x;
- }
-
- iterator insert (iterator x, const T& y)
- {
- Node* tmp = new Node(y,x.m_rep->m_next);
- if (x.m_rep == m_node) // if inserting before end
- m_node = tmp;
- x.m_rep->m_next = tmp;
- ++sz;
-
- return x++; // x points to the new data, return it, and slide it over
- }
-
- // rotate x to beginning
- void rotate (iterator x)
- {
- if (x == end())
- return;
- Node* sentinel = m_node->m_next;
- m_node->m_next = m_node->m_next->m_next;
- sentinel->m_next = x.m_rep->m_next;
- x.m_rep->m_next = sentinel;
- m_node = x.m_rep;
- }
-};
-
-#endif // __CIRCULAR_LIST_H__
--- a/include/consistencylist.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,225 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2006
- */
-
-#ifndef __CONSISTENCYLIST_H__
-#define __CONSISTENCYLIST_H__
-
-#include "orderlist.h"
-
-#include <iterator>
-#include <iostream>
-#include <list>
-#include "types.h"
-
-#include <boost/utility.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
-//#include <boost/type_traits/is_convertible.hpp>
-//#include <boost/utility/enable_if.hpp>
-
-
-template<class T> struct ConsistencyListNode;
-template<class T> class ConsistencyListIterator;
-template<class T> class const_ConsistencyListIterator;
-
-/**
- * ConsistencyList adds consistency order to OrderList which remains unchanged
- * through the lifetime of the list.
- */
-template<class T>
-class ConsistencyList: public OrderList<ConsistencyListNode<T> >
-{
- public:
- class OrderComparison;
- class LessThanComparison;
- class GreaterThanComparison;
- class ConsistencyComparison;
-
- /// \name Comparison types
- /// @{
- // Explicit typedefs for Doxygen
- typedef LessThanComparison LessThanComparison;
- typedef GreaterThanComparison GreaterThanComparison;
- typedef ConsistencyComparison ConsistencyComparison;
- /// @}
-
- typedef ConsistencyListNode<T> NodeType;
- typedef ConsistencyList<T> Self;
- typedef OrderList<NodeType > Parent;
-
- typedef T value_type;
- typedef T& reference;
- typedef const T& const_reference;
- typedef ConsistencyListIterator<T> iterator;
- typedef const_ConsistencyListIterator<T> const_iterator;
-
- ConsistencyList(): sz(0) {}
- ~ConsistencyList() { clear(); }
-
- /// \name Order operations
- void swap(iterator i, iterator j); ///< Exchanges the order of simplices pointed to by i and j
- template<class BinaryPredicate>
- void sort(BinaryPredicate cmp); ///< Sorts the elements in accordance with cmp
-
- /// \name Container operations
- /// @{
- // Explicit calls instead of using declarations for Doxygen
- iterator push_back(const_reference x);
- iterator insert(iterator predecessor, const_reference x); ///< Inserts x immediately after predecessor (has to be a valid iterator)
- void erase(iterator x) { Parent::erase(x.get_base()); --sz; }
-
- void clear() { return Parent::clear(); }
- bool empty() const { return Parent::empty(); }
- SizeType size() const { return sz; }
- iterator begin() { return iterator(Parent::begin()); }
- const_iterator begin() const { return const_iterator(Parent::begin()); }
- iterator end() { return iterator(Parent::end()); }
- const_iterator end() const { return const_iterator(Parent::end()); }
- reference back() { return Parent::back(); }
- const_reference back() const { return Parent::back(); }
- void pop_back() { return Parent::pop_back(); }
-
- iterator last() { return iterator(boost::prior(end())); }
- const_iterator last() const { return const_iterator(boost::prior(end())); }
- /// @}
-
- private:
- unsigned int sz;
-};
-
-/// Basic comparison that LessThan and GreaterThan derive from
-template<class T>
-class ConsistencyList<T>::OrderComparison
-{
- public:
- typedef typename ConsistencyList<T>::const_iterator ComparableType;
-
- int compare(ComparableType a, ComparableType b) const; /// (-1,0,1) = a (precedes, ==, succeeds) b
-};
-
-/// Determines if the first element is less than the second one
-template<class T>
-class ConsistencyList<T>::LessThanComparison: public OrderComparison
-{
- public:
- typedef OrderComparison Parent;
- typedef typename Parent::ComparableType ComparableType;
-
- int compare(ComparableType a, ComparableType b) const;
- bool operator()(ComparableType a, ComparableType b) const;
-};
-
-/// Determines if the first element is greater than the second one
-template<class T>
-class ConsistencyList<T>::GreaterThanComparison: public OrderComparison
-{
- public:
- typedef OrderComparison Parent;
- typedef typename Parent::ComparableType ComparableType;
-
- int compare(ComparableType a, ComparableType b) const;
- bool operator()(ComparableType a, ComparableType b) const;
-};
-
-/// Determines the order of the two elements in the consistency order (that doesn't change during the execution)
-template<class T>
-class ConsistencyList<T>::ConsistencyComparison
-{
- public:
- typedef typename ConsistencyList<T>::const_iterator ComparableType;
-
- int compare(ComparableType a, ComparableType b) const; ///< (-1,0,1) = a (precedes, ==, succeeds) b
- bool operator()(ComparableType a, ComparableType b) const;
-};
-
-/// Structure storing auxilliary information requred for each node of ConsistencyList
-template<class T>
-struct ConsistencyListNode
-{
- ConsistencyListNode(const T& d, unsigned int c):
- data(d), consistency(c)
- {}
-
- T data;
- OrderType consistency;
-
- std::ostream& operator<<(std::ostream& out) const { return out << data << ": " << consistency; }
-};
-
-template<class T>
-std::ostream& operator<<(std::ostream& out, const ConsistencyListNode<T>& n) { return n.operator<<(out); }
-
-template<class T>
-class ConsistencyListIterator: public boost::iterator_adaptor<ConsistencyListIterator<T>,
- typename ConsistencyList<T>::Parent::iterator,
- T>
-{
- private:
- struct enabler {};
-
- public:
- typedef typename ConsistencyList<T>::Parent ConsistencyListParent;
- typedef boost::iterator_adaptor<ConsistencyListIterator<T>,
- typename ConsistencyListParent::iterator,
- T> Parent;
- typedef typename Parent::reference reference;
- typedef typename Parent::base_type base_type;
-
- ConsistencyListIterator() {}
- ConsistencyListIterator(const typename ConsistencyListParent::iterator& iter):
- ConsistencyListIterator::iterator_adaptor_(iter)
- {}
- ConsistencyListIterator(const ConsistencyListIterator<T>& other):
- ConsistencyListIterator::iterator_adaptor_(other.base())
- {}
-
- private:
- friend class boost::iterator_core_access;
- reference dereference() const { return Parent::base_reference()->data; }
- base_type& get_base() { return Parent::base_reference(); }
-
- friend class ConsistencyList<T>;
-};
-
-template<class T>
-class const_ConsistencyListIterator: public boost::iterator_adaptor<const_ConsistencyListIterator<T>,
- typename ConsistencyList<T>::Parent::const_iterator,
- const T>
-{
- private:
- struct enabler {};
-
- public:
- typedef typename ConsistencyList<T>::Parent ConsistencyListParent;
- typedef boost::iterator_adaptor<const_ConsistencyListIterator<T>,
- typename ConsistencyListParent::const_iterator,
- const T> Parent;
- typedef typename Parent::reference reference;
- typedef typename Parent::base_type base_type;
-
- const_ConsistencyListIterator() {}
- const_ConsistencyListIterator(const typename ConsistencyListParent::const_iterator& iter):
- const_ConsistencyListIterator::iterator_adaptor_(iter)
- {}
- const_ConsistencyListIterator(const const_ConsistencyListIterator<T>& other):
- const_ConsistencyListIterator::iterator_adaptor_(other.base())
- {}
- const_ConsistencyListIterator(const ConsistencyListIterator<T>& other):
- const_ConsistencyListIterator::iterator_adaptor_(other.base())
- {}
-
- private:
- friend class boost::iterator_core_access;
- reference dereference() const { return Parent::base_reference()->data; }
- const base_type&
- get_base() { return Parent::base_reference(); }
-
- friend class ConsistencyList<T>::OrderComparison;
- friend class ConsistencyList<T>::ConsistencyComparison;
-};
-
-
-#include "consistencylist.hpp"
-
-#endif // __CONSISTENCYLIST_H__
--- a/include/consistencylist.hpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,86 +0,0 @@
-/* Implementations */
-
-template<class T>
-void
-ConsistencyList<T>::
-swap(iterator i, iterator j)
-{
- Parent::swap(i.get_base(),j.get_base());
-}
-
-template<class T>
-template<class BinaryPredicate>
-void
-ConsistencyList<T>::
-sort(BinaryPredicate cmp)
-{
- Parent::sort(cmp);
- OrderType cur_order = 0;
- for (typename Parent::iterator cur = begin(); cur != end(); ++cur)
- cur->consistency = cur_order++;
-}
-
-
-template<class T>
-typename ConsistencyList<T>::iterator
-ConsistencyList<T>::
-push_back(const_reference x)
-{
- ++sz;
- return Parent::push_back(NodeType(x, sz));
-}
-
-template<class T>
-typename ConsistencyList<T>::iterator
-ConsistencyList<T>::
-insert(iterator p, const_reference x)
-{
- ++sz;
- return Parent::insert(p.get_base(), NodeType(x, sz));
-}
-
-
-/* OrderComparison */
-template<class T>
-int
-ConsistencyList<T>::
-OrderComparison::compare(ComparableType a, ComparableType b) const
-{
- typename Parent::OrderComparison cmp;
- return cmp.compare(a.get_base(), b.get_base());
-}
-
-
-/* LessThanComparison */
-template<class T>
-int ConsistencyList<T>::LessThanComparison::compare(ComparableType a, ComparableType b) const
-{ return Parent::compare(a,b); }
-
-template<class T>
-bool ConsistencyList<T>::LessThanComparison::operator()(ComparableType a, ComparableType b) const
-{ return compare(a,b) == -1; }
-
-
-/* GreaterThanComparison */
-template<class T>
-int ConsistencyList<T>::GreaterThanComparison::compare(ComparableType a, ComparableType b) const
-{ return -Parent::compare(a,b); }
-
-template<class T>
-bool ConsistencyList<T>::GreaterThanComparison::operator()(ComparableType a, ComparableType b) const
-{ return compare(a,b) == -1; }
-
-
-/* ConsistencyComparison */
-template<class T>
-int ConsistencyList<T>::ConsistencyComparison::compare(ComparableType a, ComparableType b) const
-{
- if (a.get_base()->consistency < b.get_base()->consistency) return -1;
- else if (a.get_base()->consistency == b.get_base()->consistency) return 0;
- else return 1;
-}
-
-template<class T>
-bool ConsistencyList<T>::ConsistencyComparison::operator()(ComparableType a, ComparableType b) const
-{ return compare(a,b) == -1; }
-
--- a/include/counter.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,68 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2005 -- 2006
- */
-
-#ifndef __COUNTER_H__
-#define __COUNTER_H__
-
-/* This should be integrated with the logging facilities. Written in the same framework. */
-
-#include <map>
-#include <string>
-#include <iostream>
-
-#ifndef COUNTERS
-#define Count(x)
-#define CountNum(x,y)
-#else // COUNTERS
-#define Count(x) counters.inc(x)
-#define CountNum(x,y) counters.inc(x,y)
-#endif
-
-typedef unsigned long CounterType;
-typedef std::string KeyType;
-
-class CounterFactory
-{
- private:
- typedef std::map<int, CounterType> CountersMap;
- typedef std::map<KeyType, CountersMap> KeyMap;
- KeyMap ctrs;
-
- public:
- ~CounterFactory()
- {
-#ifdef COUNTERS
- std::cout << "Counters:" << std::endl;
- for (KeyMap::const_iterator cur = ctrs.begin(); cur != ctrs.end(); ++cur)
- {
- std::cout << cur->first << ": ";
- if (cur->second.size() == 1)
- {
- std::cout << cur->second.begin()->second << std::endl;
- continue;
- }
- std::cout << std::endl;
- for (CountersMap::const_iterator ccur = cur->second.begin();
- ccur != cur->second.end();
- ++ccur)
- std::cout << " " << ccur->first << ": " << ccur->second << std::endl;
- }
-#endif // COUNTERS
- }
-
- void inc(const KeyType& key, int num = 0)
- {
- ctrs[key][num]++;
- }
-
- CounterType lookup(const KeyType& key, int num = 0) const
- {
- return const_cast<KeyMap&>(ctrs)[key][num];
- }
-};
-
-static CounterFactory counters;
-
-#endif // __COUNTER_H__
--- a/include/cycle.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,115 +0,0 @@
-/**
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2005-2006
- */
-
-#ifndef __CYCLE_H__
-#define __CYCLE_H__
-
-#include "sys.h"
-#include "debug.h"
-
-#include "types.h"
-#include "circular_list.h"
-#include <list>
-#include <boost/serialization/access.hpp>
-
-/**
- * Class storing a cycle of simplices. Stores items in the order defined by ConsistencyCmp.
- * The actual order of the elements is defined by OrderCmp. Instances of those
- * classes are not stored in Cycle for efficiency, and are passed as arguments to those methods
- * that require them.
- */
-template <class Itm, class OrderCmp, class ConsistencyCmp = OrderCmp>
-class Cycle: public List<Itm>
-{
- public:
- /// \name Template Parameters
- /// @{
- typedef Itm Item;
- typedef OrderCmp OrderComparison;
- typedef ConsistencyCmp ConsistencyComparison;
- /// @}
-
- typedef Cycle<Item, OrderComparison, ConsistencyCmp> Self;
- typedef List<Item> CycleRepresentation;
-
- /// \name Accessor typedefs
- /// @{
- typedef typename CycleRepresentation::iterator iterator;
- typedef typename CycleRepresentation::const_iterator const_iterator;
- typedef typename CycleRepresentation::const_reference const_reference;
- typedef typename CycleRepresentation::reference reference;
- typedef typename CycleRepresentation::pointer pointer;
- typedef typename CycleRepresentation::const_pointer const_pointer;
- /// @}
-
- public:
- Cycle();
- Cycle(const Cycle& c);
-
- /// \name Whole Cycle operations
- /// @{
- /** Add c to *this assuming both Cycles are sorted in increasing order according to cmp. */
- Self& add(const Self& c, const ConsistencyComparison& cmp);
- void swap(Cycle& c); ///< Swaps the contents of c and *this (like STL's swap destroys c)
- //void insertion_sort(const Comparison& cmp); ///< Sort list[i] using insertion sort
- void sort(const ConsistencyComparison& cmp); ///< Sort elements to enforce consistency
- using CycleRepresentation::empty;
- using CycleRepresentation::clear;
- using CycleRepresentation::size;
- /// @}
-
- /// \name Modifiers
- /// @{
- using CycleRepresentation::erase;
- void append(const_reference x, const ConsistencyComparison& cmp);
- /// @}
-
- /// \name Accessors
- /// @{
- using CycleRepresentation::begin;
- using CycleRepresentation::end;
- const_reference top(const OrderComparison& cmp) const; ///< First element in cmp order
- iterator get_second(const OrderComparison& cmp) const; ///< Second element in cmp order
- /// @}
-
- /// \name Block access optimizations
- // Between operations used in optimization of transpositions for regular vertices. Maybe we don't need these? TODO
- /// @{
- /** Return first after i, but before or equal j; return i if no such element found */
- const_reference first_between(const_reference i, const_reference j, const OrderComparison& cmp);
- /// Add lists and remove all elements after i and before or equal to j
- const_reference add_and_first_between(const Self& c, const ConsistencyComparison& consistency_cmp,
- const_reference i, const_reference j, const OrderComparison& order_cmp);
- /// Erase everything after i, but before or equal to j
- void erase_between(const_reference i, const_reference j, const OrderComparison& cmp);
- /// @}
-
- /// \name Debugging
- /// @{
- const_reference get_first(const OrderComparison& cmp) const; ///< First element in cmp order
- std::ostream& operator<<(std::ostream& out) const;
- /// @}
-
- private:
- typedef std::list<Item> TemporaryCycleRepresenation;
-
- using CycleRepresentation::push_back;
- using CycleRepresentation::insert;
-
- private:
- size_t sz;
-
- private:
- // Serialization
- typedef List<Item> Parent;
- friend class boost::serialization::access;
- template<class Archive>
- void serialize(Archive& ar, version_type );
-};
-
-#include "cycle.hpp"
-
-#endif // __CYCLE_H__
-
--- a/include/cycle.hpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,280 +0,0 @@
-#include <algorithm>
-#include <vector>
-
-#include <boost/serialization/split_member.hpp>
-#include <boost/serialization/nvp.hpp>
-#include <boost/serialization/binary_object.hpp>
-#include <boost/utility.hpp>
-
-using boost::serialization::make_nvp;
-using boost::serialization::make_binary_object;
-
-template<class I, class OrderCmp, class ConsistencyCmp>
-Cycle<I,OrderCmp,ConsistencyCmp>::
-Cycle(): sz(0)
-{}
-
-template<class I, class OrderCmp, class ConsistencyCmp>
-Cycle<I,OrderCmp,ConsistencyCmp>::
-Cycle(const Cycle& c): CycleRepresentation(c), sz(c.sz)
-{}
-
-template<class I, class OrderCmp, class ConsistencyCmp>
-void
-Cycle<I,OrderCmp,ConsistencyCmp>::
-append(const_reference x, const ConsistencyCmp& cmp)
-{
- // First try the special cases that x goes at the end
- const_reference last = CycleRepresentation::back();
- if (empty() || cmp(last, x))
- {
- push_back(x);
- return;
- }
-
- for (iterator cur = begin(); cur != end(); ++cur)
- if (cmp(x, *cur))
- {
- insert(cur, x);
- return;
- }
-}
-
-template<class I, class OrderCmp, class ConsistencyCmp>
-typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
-Cycle<I,OrderCmp,ConsistencyCmp>::
-top(const OrderComparison& cmp) const
-{
- AssertMsg(!empty(), "Cycle must not be empty for top()");
- const_iterator min = begin();
- for (const_iterator cur = ++begin(); cur != end(); ++cur)
- if (cmp(*cur, *min))
- min = cur;
- return *min;
-}
-
-template<class I, class OrderCmp, class ConsistencyCmp>
-void
-Cycle<I,OrderCmp,ConsistencyCmp>::
-swap(Cycle& c)
-{
- CycleRepresentation::swap(c);
- std::swap(sz, c.sz);
-}
-
-template<class I, class OrderCmp, class ConsistencyCmp>
-void
-Cycle<I,OrderCmp,ConsistencyCmp>::
-sort(const ConsistencyComparison& cmp)
-{
- std::vector<Item> tmp(begin(), end());
- std::sort(tmp.begin(), tmp.end(), cmp);
- std::copy(tmp.begin(), tmp.end(), begin());
-}
-
-template<class I, class OrderCmp, class ConsistencyCmp>
-typename Cycle<I,OrderCmp,ConsistencyCmp>::iterator
-Cycle<I,OrderCmp,ConsistencyCmp>::
-get_second(const OrderComparison& cmp) const
-{
- AssertMsg(!empty(), "Cycle must not be empty for get_second()");
- if (size() < 2) return begin(); // Indicates that there is no second.
-
- Dout(dc::cycle, "Looking for second");
- AssertMsg(size() >= 2, "Cycle must have at least two elements for get_second()");
- iterator min = begin();
- iterator second = ++begin();
- if (cmp(*second, *min))
- std::swap(min, second);
- for (iterator cur = boost::next(begin(),2); cur != end(); ++cur)
- {
- if (cmp(*cur, *min))
- {
- second = min;
- min = cur;
- } else if (cmp(*cur, *second))
- {
- second = cur;
- }
- }
-
- Dout(dc::cycle, "Looked up: " << **second);
- return second;
-}
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
-Cycle<I,OrderCmp,ConsistencyCmp>::
-first_between(const_reference i, const_reference j, const OrderComparison& cmp)
-{
- // Find the first element in ConsistencyComparison order (> i and <= j)
- const_pointer first = &i;
- iterator cur = begin();
- for (; cur != end(); ++cur)
- {
- if ((*cur == j) || (cmp(*cur, j) && cmp(i, *cur)))
- {
- first = &(*cur);
- break;
- }
- }
-
- // If no such element found, then we are done
- if (cur == end())
- return i;
-
- // Find first element in OrderComparison order (> i and <= j)
- for (++cur; cur != end(); ++cur)
- {
- if ((*cur == j) || (cmp(*cur, j) && cmp(i, *cur)))
- {
- if (cmp(*cur, *first))
- first = &(*cur);
- }
- }
- return *first;
-}
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-void
-Cycle<I,OrderCmp,ConsistencyCmp>::
-erase_between(const_reference i, const_reference j, const OrderComparison& cmp)
-{
- for (iterator cur = begin(); cur != end(); ++cur)
- while ((cur != end()) && ((*cur == j) || (cmp(*cur, j) && cmp(i, *cur))))
- {
- Dout(dc::cycle, "Iteration of the erase while loop");
- cur = erase(cur);
- }
-}
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-std::ostream&
-Cycle<I,OrderCmp,ConsistencyCmp>::
-operator<<(std::ostream& out) const
-{
- for (const_iterator cur = begin(); cur != end(); ++cur)
- {
- out << **cur << ", ";
- }
- // out << "(last: " << *last << ")"; // For debugging only
- return out;
-}
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-std::ostream&
-operator<<(std::ostream& out, const Cycle<I, OrderCmp, ConsistencyCmp>& c)
-{
- return c.operator<<(out);
-}
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-typename Cycle<I, OrderCmp, ConsistencyCmp>::Self&
-Cycle<I, OrderCmp, ConsistencyCmp>::
-add(const Self& c, const ConsistencyCmp& cmp)
-{
- Dout(dc::cycle, "Adding cycles: " << *this << " + " << c);
-
- iterator cur1 = begin();
- const_iterator cur2 = c.begin();
-
- while (cur2 != c.end())
- {
- if (cur1 == end())
- {
- while (cur2 != c.end())
- push_back(*cur2++);
- Dout(dc::cycle, "After addition: " << *this);
- return *this;
- }
-
- // mod 2
- int res = cmp.compare(*cur1, *cur2);
- Dout(dc::cycle, "Comparison result: " << res);
- if (res == 0) // *cur1 == *cur2
- {
- Dout(dc::cycle, "Equality");
- cur1 = erase(cur1); // erase cur1 --- as a result cur1 will be pointing at old_cur1++
- --sz;
- ++cur2;
- } else if (res < 0) // *cur1 < *cur2
- {
- Dout(dc::cycle, "Less than");
- cur1++;
- } else if (res > 0) // *cur1 > *cur2
- {
- Dout(dc::cycle, "Greater than");
- insert(cur1, *cur2);
- ++cur2;
- ++sz;
- }
- }
-
- Dout(dc::cycle, "After addition: " << *this);
- return *this;
-}
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
-Cycle<I,OrderCmp,ConsistencyCmp>::
-add_and_first_between(const Self& c, const ConsistencyComparison& consistency_cmp,
- const_reference i, const_reference j, const OrderComparison& order_cmp)
-{
- add(c, consistency_cmp);
- return first_between(i,j, order_cmp);
-}
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
-Cycle<I,OrderCmp,ConsistencyCmp>::
-get_first(const OrderComparison& cmp) const
-{ return top(cmp); }
-
-
-template<typename I, class OrderCmp, class ConsistencyCmp>
-template<class Archive>
-void
-Cycle<I,OrderCmp,ConsistencyCmp>::
-serialize(Archive& ar, version_type )
-{
- ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
- ar & make_nvp("size", sz);;
-}
-
-
-/*
-template<typename I, class Cmp>
-void
-Cycle<I, Cmp>::
-insertion_sort(const Comparison& cmp)
-{
- TemporaryCycleRepresenation tmp;
-
- // Insertion sort into the temporary list
- for (const_iterator cur = begin(); cur != end(); ++cur)
- {
- typename TemporaryCycleRepresenation::iterator tmp_cur = tmp.end();
- typename TemporaryCycleRepresenation::iterator tmp_next = tmp_cur--;
-
- while (tmp_next != tmp.begin())
- {
- if (cmp(*cur, *tmp_cur))
- tmp_next = tmp_cur--;
- else
- break;
- }
- tmp.insert(tmp_next, *cur);
- }
-
- // Copy temporary list back into ourselves
- iterator cur = begin();
- typename TemporaryCycleRepresenation::const_iterator tmp_cur = tmp.begin();
- while(tmp_cur != tmp.end())
- {
- *cur = *tmp_cur;
- ++cur; ++tmp_cur;
- }
-}
-*/
-
-
--- a/include/debug.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,90 +0,0 @@
-#ifndef DEBUG_H
-#define DEBUG_H
-
-#ifndef CWDEBUG
-
-#include <iostream> // std::cerr
-#include <cstdlib> // std::exit, EXIT_FAILURE
-#include <cassert>
-
-#define AllocTag1(p)
-#define AllocTag2(p, desc)
-#define AllocTag_dynamic_description(p, data)
-#define AllocTag(p, data)
-#define Debug(STATEMENT...)
-#define Dout(cntrl, data)
-#define DoutFatal(cntrl, data) LibcwDoutFatal(, , cntrl, data)
-#define ForAllDebugChannels(STATEMENT...)
-#define ForAllDebugObjects(STATEMENT...)
-#define LibcwDebug(dc_namespace, STATEMENT...)
-#define LibcwDout(dc_namespace, d, cntrl, data)
-#define LibcwDoutFatal(dc_namespace, d, cntrl, data) do { ::std::cerr << data << ::std::endl; ::std::exit(EXIT_FAILURE); } while(1)
-#define LibcwdForAllDebugChannels(dc_namespace, STATEMENT...)
-#define LibcwdForAllDebugObjects(dc_namespace, STATEMENT...)
-#define NEW(x) new x
-#define CWDEBUG_ALLOC 0
-#define CWDEBUG_MAGIC 0
-#define CWDEBUG_LOCATION 0
-#define CWDEBUG_LIBBFD 0
-#define CWDEBUG_DEBUG 0
-#define CWDEBUG_DEBUGOUTPUT 0
-#define CWDEBUG_DEBUGM 0
-#define CWDEBUG_DEBUGT 0
-#define CWDEBUG_MARKER 0
-#define AssertMsg(TEST,MSG)
-//#define AssertMsg(TEST,STRM,MSG)
-
-
-#else // CWDEBUG
-
-// This must be defined before <libcwd/debug.h> is included and must be the
-// name of the namespace containing your `dc' (Debug Channels) namespace
-// (see below). You can use any namespace(s) you like, except existing
-// namespaces (like ::, ::std and ::libcwd).
-#define DEBUGCHANNELS ::dionysus::debug::channels
-#include <libcwd/debug.h>
-
-namespace dionysus
-{
- namespace debug
- {
- void init(void); // Initialize debugging code from main().
- void init_thread(void); // Initialize debugging code from new threads.
-
- namespace channels // This is the DEBUGCHANNELS namespace, see above.
- {
- namespace dc // 'dc' is defined inside DEBUGCHANNELS.
- {
- using namespace libcwd::channels::dc;
- using libcwd::channel_ct;
-
- // Add the declaration of new debug channels here
- // and add their definition in a custom debug.cc file.
- extern channel_ct filtration;
- extern channel_ct transpositions;
- extern channel_ct vineyard;
- extern channel_ct cycle;
- extern channel_ct lsfiltration;
- extern channel_ct orderlist;
- } // namespace dc
- } // namespace DEBUGCHANNELS
- }
-}
-
-
-#define AssertMsg(TEST,MSG) \
- ( (TEST) ? (void)0 \
- : (std::cerr << __FILE__ ":" << __LINE__ \
- << ": Assertion failed " #TEST \
- << " - " << MSG << std::endl,abort()))
-/*
-#define AssertMsg(TEST,STRM,MSG) \
- ( (TEST) ? (void)0 \
- : (DoutFatal(STRM, __FILE__ "(" << __LINE__ \
- << "): Assertion failed " #TEST \
- << MSG << std::endl)))
-*/
-
-#endif // CWDEBUG
-
-#endif // DEBUG_H
--- a/include/filtration.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,133 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2005 -- 2006
- */
-
-#ifndef __FILTRATION_H__
-#define __FILTRATION_H__
-
-#include "sys.h"
-#include "debug.h"
-
-#include "filtrationcontainer.h"
-#include "filtrationsimplex.h"
-#include "vineyard.h"
-
-#include <map>
-#include <vector>
-
-#include <boost/serialization/access.hpp>
-
-/**
- * Filtration class. Serves as an (ordered) container for the simplices,
- * and provides pair_simplices() method that computes the RU-decomposition
- * for the simplex order stored in the filtration. Iterators remain valid
- * through all the operations.
- */
-template<class Smplx, class FltrSmplx = FiltrationSimplex<Smplx>, class Vnrd = Vineyard<FltrSmplx> >
-class Filtration: public FltrSmplx::Container
-{
- public:
- typedef Smplx Simplex;
- typedef FltrSmplx FiltrationSimplex;
- typedef Vnrd Vineyard;
-
- /// \name Container Types
- /// @{
- /** The actual container type (which is the parent of the Filtration) */
- typedef typename FiltrationSimplex::Container FiltrationContainer;
- typedef typename FiltrationContainer::Index Index;
- typedef typename FiltrationContainer::const_Index const_Index;
- /// @}
-
- /// \name Cycles and Trails
- /// @{
- typedef typename FiltrationContainer::GreaterThanComparison CyclesComparator;
- typedef typename FiltrationContainer::LessThanComparison TrailsComparator;
- typedef typename FiltrationContainer::ConsistencyComparison ConsistencyComparator;
- typedef typename FiltrationContainer::Cycle Cycle;
- typedef typename FiltrationContainer::Trail Trail;
- typedef typename Cycle::iterator CycleIterator;
- typedef typename Trail::iterator TrailIterator;
- /// @}
-
- typedef Filtration<Simplex, FiltrationSimplex, Vineyard> Self;
- typedef FiltrationContainer Parent;
-
- public:
- Filtration(Vineyard* vineyard);
-
- /// \name Core Functionality
- /// @{
- /// Computes RU decomposition of the simplices in [bg, end) range, assuming that everything before bg has been paired
- void pair_simplices(Index bg, Index end);
- void pair_simplices() { pair_simplices(begin(), end()); }
- bool transpose(Index i, bool maintain_lazy = true);
- bool is_paired() const;
- Index append(const Simplex& s); ///< Appends s to the filtration
- Index insert(Index prior, const Simplex& s); ///< Inserts s after prior
- const_Index get_index(const Simplex& s) const; /**< Returns the iterator pointing to s
- (end() if s not in filtration) */
- Index get_index(const Simplex& s); ///< \overload
- void fill_simplex_index_map(); ///< Fills the mapping for get_index()
- /// @}
-
- /// \name Accessors
- /// @{
- Vineyard* vineyard() { return vineyard_; }
- const Vineyard* vineyard() const { return vineyard_; }
- /// @}
-
- protected:
- using Parent::swap;
- bool transpose_simplices(Index i, bool maintain_lazy);
-
- public:
- /// \name Container Operations
- /// @{
- using Parent::size;
- using Parent::begin;
- using Parent::end;
- /// @}
-
- std::ostream& operator<<(std::ostream& out) const;
-
- protected:
- /// \name Comparator accessors (protected)
- /// @{
- const ConsistencyComparator& get_consistency_cmp() const { return consistency_cmp; }
- const CyclesComparator& get_cycles_cmp() const { return cycles_cmp; }
- const TrailsComparator& get_trails_cmp() const { return trails_cmp; }
- /// @}
-
- private:
- typedef std::map<Simplex, Index> SimplexMap;
-
- /// Initializes the cycle with the indices of the simplices in the boundary, and the trail with the index of this simplex
- void init_cycle_trail(Index j);
- void pairing_switch(Index i, Index j);
-
- bool paired;
- SimplexMap inverse_simplices;
-
- Vineyard* vineyard_;
-
- CyclesComparator cycles_cmp;
- TrailsComparator trails_cmp;
- ConsistencyComparator consistency_cmp;
-
- private:
- /* Serialization */
- friend class boost::serialization::access;
-
- typedef std::map<const_Index, SizeType, ConsistencyComparator> IndexIntMap;
- typedef std::vector<Index> IndexVector;
-
- template<class Archive> void save(Archive& ar, version_type ) const;
- template<class Archive> void load(Archive& ar, version_type );
- BOOST_SERIALIZATION_SPLIT_MEMBER()
-};
-
-#include "filtration.hpp"
-
-#endif // __FILTRATION_H__
--- a/include/filtration.hpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,463 +0,0 @@
-#include "counter.h"
-#include "types.h"
-#include <algorithm>
-
-#include <boost/utility.hpp>
-#include <boost/serialization/vector.hpp>
-#include <boost/serialization/nvp.hpp>
-#include <boost/serialization/list.hpp>
-#include <boost/serialization/is_abstract.hpp>
-
-using boost::serialization::make_nvp;
-
-/* Filtration Public */
-
-template<class S, class FS, class V>
-Filtration<S, FS, V>::
-Filtration(Vineyard* vnrd = 0): paired(false), vineyard_(vnrd)
-{}
-
-template<class S, class FS, class V>
-void
-Filtration<S, FS, V>::
-pair_simplices(Index bg, Index end)
-{
- Dout(dc::filtration, "Entered: compute_pairing");
- for (Index j = bg; j != end; ++j)
- {
- Dout(dc::filtration|flush_cf|continued_cf, *j << ": ");
- init_cycle_trail(j);
- Cycle& bdry = j->cycle();
- Dout(dc::finish, bdry);
-
- CountNum("Boundaries", j->dimension());
- Count("SimplexCount");
-
- while(!bdry.empty())
- {
- Index i = bdry.top(cycles_cmp);
- Dout(dc::filtration, *i << ": " << *(i->pair()));
- AssertMsg(!cycles_cmp(i, j), "Simplices in the cycle must precede current simplex: " <<
- "(" << *i << " in cycle of " << *j << ")");
-
- // i is not paired, so we pair j with i
- if (i->pair() == i)
- {
- Dout(dc::filtration, "Pairing " << *i << " and " << *j << " with cycle " << j->cycle());
- i->set_pair(j);
- j->set_pair(i);
- CountNum("DepositedCycleLength", j->cycle().size());
- break;
- }
-
- // continue searching --- change the Dout to the continued mode with newlines FIXME
- Dout(dc::filtration, " Adding: [" << bdry << "] + ");
- Dout(dc::filtration, " [" << i->pair()->cycle() << "]");
- bdry.add(i->pair()->cycle(), get_consistency_cmp());
- i->pair()->trail().append(j, get_consistency_cmp());
- Dout(dc::filtration, "After addition: " << bdry);
- }
- Dout(dc::filtration, "Finished with " << *j << ": " << *(j->pair()));
- }
- paired = true;
-}
-
-template<class S, class FS, class V>
-bool
-Filtration<S, FS, V>::
-is_paired() const
-{ return paired; }
-
-/**
- * Transposes simplices at i and i+1, and records the knee in the vineyard if there is a change in pairing.
- * Returns true if the pairing changed.
- */
-template<class S, class FS, class V>
-bool
-Filtration<S,FS,V>::
-transpose(Index i, bool maintain_lazy)
-{
- AssertMsg(vineyard() != 0, "We must have a vineyard for transpositions");
-
- Index i_orig = i++;
-
- AssertMsg(i_orig->pair() != i, "Transposing simplices must not be paired");
- bool result = transpose_simplices(i_orig, maintain_lazy);
- AssertMsg(i_orig == boost::next(i), "Wrong indices after transposition");
-
- if (result) vineyard()->switched(i, i_orig);
- return result;
-}
-
-template<class S, class FS, class V>
-typename Filtration<S, FS, V>::Index
-Filtration<S, FS, V>::
-append(const Simplex& s)
-{
- Index i = push_back(FiltrationSimplex(s));
- return i;
-}
-
-template<class S, class FS, class V>
-typename Filtration<S, FS, V>::Index
-Filtration<S, FS, V>::
-insert(Index prior, const Simplex& s)
-{
- Index i = Parent::insert(prior, FiltrationSimplex(s));
- paired = false;
-
- return i;
-}
-
-template<class S, class FS, class V>
-typename Filtration<S, FS, V>::const_Index
-Filtration<S, FS, V>::
-get_index(const Simplex& s) const
-{
- typename SimplexMap::const_iterator i = inverse_simplices.find(s);
- if (i == inverse_simplices.end())
- return end();
- else
- return i->second;
-}
-
-template<class S, class FS, class V>
-typename Filtration<S, FS, V>::Index
-Filtration<S, FS, V>::
-get_index(const Simplex& s)
-{
- typename SimplexMap::const_iterator i = inverse_simplices.find(s);
- if (i == inverse_simplices.end())
- return end();
- else
- return i->second;
-}
-
-template<class S, class FS, class V>
-void
-Filtration<S, FS, V>::
-fill_simplex_index_map()
-{
- for (Index i = begin(); i != end(); ++i)
- inverse_simplices[*i] = i;
-}
-
-template<class S, class FS, class V>
-std::ostream&
-Filtration<S, FS, V>::
-operator<<(std::ostream& out) const
-{
- out << "Pairing: " << std::endl;
- for (const_Index i = begin(); i != end(); ++i)
- {
- out << "(" << *i << ", " << *(i->pair()) << "): ";
- out << i->cycle() << std::endl;
- }
- out << std::endl << std::endl;
-
- return out;
-}
-
-
-/* Filtration Protected */
-/// Transposes simplices at i and i+1. Returns true if the pairing switched.
-template<class S, class FS, class V>
-bool
-Filtration<S,FS,V>::
-transpose_simplices(Index i, bool maintain_lazy)
-{
- AssertMsg(is_paired(), "Pairing must be computed before transpositions");
- Count("SimplexTransposition");
-
- Index i_prev = i++;
-
- if (i_prev->dimension() != i->dimension())
- {
- swap(i_prev, i);
- Dout(dc::transpositions, "Different dimension");
- Count("Case DiffDim");
- return false;
- }
-
- bool si = i_prev->sign(), sii = i->sign();
- if (si && sii)
- {
- Dout(dc::transpositions, "Trail prev: " << i_prev->trail());
-
- // Case 1
- TrailIterator i_in_i_prev = std::find(i_prev->trail().begin(), i_prev->trail().end(), i);
- if (i_in_i_prev != i_prev->trail().end())
- {
- Dout(dc::transpositions, "Case 1, U[i,i+1] = 1");
- i_prev->trail().erase(i_in_i_prev);
- }
-
- Index k = i_prev->pair();
- Index l = i->pair();
-
- // Explicit treatment of unpaired simplex
- if (l == i)
- {
- swap(i_prev, i);
- Dout(dc::transpositions, "Case 1.2 --- unpaired");
- Dout(dc::transpositions, *i_prev);
- Count("Case 1.2");
- return false;
- } else if (k == i_prev)
- {
- if (std::find(l->cycle().begin(), l->cycle().end(), i_prev) == l->cycle().end())
- {
- // Case 1.2
- swap(i_prev, i);
- Dout(dc::transpositions, "Case 1.2 --- unpaired");
- Dout(dc::transpositions, *i_prev);
- Count("Case 1.2");
- return false;
- } else
- {
- // Case 1.1.2 --- special version (plain swap, but pairing switches)
- swap(i_prev, i);
- pairing_switch(i_prev, i);
- Dout(dc::transpositions, "Case 1.1.2 --- unpaired");
- Dout(dc::transpositions, *i_prev);
- Count("Case 1.1.2");
- return true;
- }
- }
-
- Dout(dc::transpositions, "l cycle: " << l->cycle());
- if (std::find(l->cycle().begin(), l->cycle().end(), i_prev) == l->cycle().end())
- {
- // Case 1.2
- if (maintain_lazy)
- {
- TrailIterator k_in_l = std::find(l->trail().begin(), l->trail().end(), k);
- if (k_in_l != l->trail().end())
- {
- l->trail().add(k->trail(), Filtration::get_consistency_cmp()); // Add row k to l
- k->cycle().add(l->cycle(), Filtration::get_consistency_cmp()); // Add column l to k
- }
- }
- swap(i_prev, i);
- Dout(dc::transpositions, "Case 1.2");
- Count("Case 1.2");
- return false;
- } else
- {
- // Case 1.1
- if (trails_cmp(k,l))
- {
- // Case 1.1.1
- swap(i_prev, i);
- l->cycle().add(k->cycle(), Filtration::get_consistency_cmp()); // Add column k to l
- k->trail().add(l->trail(), Filtration::get_consistency_cmp()); // Add row l to k
- Dout(dc::transpositions, "Case 1.1.1");
- Count("Case 1.1.1");
- return false;
- } else
- {
- // Case 1.1.2
- swap(i_prev, i);
- k->cycle().add(l->cycle(), Filtration::get_consistency_cmp()); // Add column l to k
- l->trail().add(k->trail(), Filtration::get_consistency_cmp()); // Add row k to l
- pairing_switch(i_prev, i);
- Dout(dc::transpositions, "Case 1.1.2");
- Count("Case 1.1.2");
- return true;
- }
- }
- } else if (!si && !sii)
- {
- // Case 2
- if (std::find(i_prev->trail().begin(), i_prev->trail().end(), i) == i_prev->trail().end())
- {
- // Case 2.2
- swap(i_prev, i);
- Dout(dc::transpositions, "Case 2.2");
- Count("Case 2.2");
- return false;
- } else
- {
- // Case 2.1
- Index low_i = i_prev->pair();
- Index low_ii = i->pair();
- i_prev->trail().add(i->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
- i->cycle().add(i_prev->cycle(), Filtration::get_consistency_cmp()); // Add column i_prev to i
- swap(i_prev, i);
- if (Filtration::get_trails_cmp()(low_ii, low_i))
- {
- // Case 2.1.2
- i_prev->cycle().add(i->cycle(), Filtration::get_consistency_cmp()); // Add column i to i_prev (after transposition)
- i->trail().add(i_prev->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
- pairing_switch(i_prev, i);
- Dout(dc::transpositions, "Case 2.1.2");
- Count("Case 2.1.2");
- return true;
- }
-
- // Case 2.1.1
- Dout(dc::transpositions, "Case 2.1.1");
- Count("Case 2.1.1");
- return false;
- }
- } else if (!si && sii)
- {
- // Case 3
- if (std::find(i_prev->trail().begin(), i_prev->trail().end(), i) == i_prev->trail().end())
- {
- // Case 3.2
- swap(i_prev, i);
- Dout(dc::transpositions, "Case 3.2");
- Count("Case 3.2");
- return false;
- } else
- {
- // Case 3.1
- i_prev->trail().add(i->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
- i->cycle().add(i_prev->cycle(), Filtration::get_consistency_cmp()); // Add column i_prev to i
- swap(i_prev, i);
- i_prev->cycle().add(i->cycle(), Filtration::get_consistency_cmp()); // Add column i_prev to i (after transposition)
- i->trail().add(i_prev->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
- pairing_switch(i_prev, i);
- Dout(dc::transpositions, "Case 3.1");
- Count("Case 3.1");
- return true;
- }
- } else if (si && !sii)
- {
- // Case 4
- TrailIterator i_in_i_prev = std::find(i_prev->trail().begin(), i_prev->trail().end(), i);
- if (i_in_i_prev != i_prev->trail().end())
- {
- Dout(dc::transpositions, "Case 4, U[i,i+1] = 1");
- i_prev->trail().erase(i_in_i_prev);
- }
- swap(i_prev, i);
- Dout(dc::transpositions, "Case 4");
- Count("Case 4");
- return false;
- }
-
- return false; // to avoid compiler complaints, should never reach this point
-}
-
-
-/* Filtration Private */
-template<class S, class FS, class V>
-void
-Filtration<S, FS, V>::
-init_cycle_trail(Index j)
-{
- typename Simplex::Cycle bdry = j->boundary();
-
- for (typename Simplex::Cycle::const_iterator cur = bdry.begin(); cur != bdry.end(); ++cur)
- {
- Dout(dc::filtration, "Appending in init_cycle_trail(): " << *cur);
- AssertMsg(get_index(*cur) != end(), "Non-existent simplex in the cycle");
- j->cycle().append(get_index(*cur), get_consistency_cmp());
- }
- j->trail().append(j, get_consistency_cmp());
- j->set_pair(j);
-}
-
-/// Update the pairing, so that whoever was paired with i is now paired with j and vice versa.
-template<class S, class FS, class V>
-void
-Filtration<S,FS,V>::
-pairing_switch(Index i, Index j)
-{
- Index i_pair = i->pair();
- Index j_pair = j->pair();
-
- if (i_pair == i)
- j->set_pair(j);
- else
- {
- j->set_pair(i_pair);
- i_pair->set_pair(j);
- }
-
- if (j_pair == j)
- i->set_pair(i);
- else
- {
- i->set_pair(j_pair);
- j_pair->set_pair(i);
- }
-}
-
-/* Serialization */
-template<class S, class FS, class V>
-template<class Archive>
-void
-Filtration<S, FS, V>::
-save(Archive& ar, version_type ) const
-{
- ar << BOOST_SERIALIZATION_NVP(paired);
- ar << BOOST_SERIALIZATION_NVP(cycles_cmp);
- ar << BOOST_SERIALIZATION_NVP(trails_cmp);
- ar << BOOST_SERIALIZATION_NVP(consistency_cmp);
-
- SizeType sz = size();
- ar << make_nvp("size", sz);
- Dout(dc::filtration, "Size: " << sz);
-
- /* Record integer indices */
- IndexIntMap index_map; SizeType i = 0;
- for (const_Index cur = begin(); cur != end(); ++cur)
- { index_map[cur] = i++; }
-
- /* Save the simplices */
- int count = 0;
- for (const_Index cur = begin(); cur != end(); ++cur)
- {
- count++;
- // FIXME
- //FiltrationSimplexSerialization simplex = FiltrationSimplexSerialization(*cur, index_map);
- //ar << make_nvp("FiltrationSimplex", simplex);
- }
- Dout(dc::filtration, count << " simplices serialized");
-}
-
-template<class S, class FS, class V>
-template<class Archive>
-void
-Filtration<S, FS, V>::
-load(Archive& ar, version_type )
-{
- Dout(dc::filtration, "Starting to read filtration");
- ar >> BOOST_SERIALIZATION_NVP(paired);
- ar >> BOOST_SERIALIZATION_NVP(cycles_cmp);
- ar >> BOOST_SERIALIZATION_NVP(trails_cmp);
- ar >> BOOST_SERIALIZATION_NVP(consistency_cmp);
- Dout(dc::filtration, "In Filtration: first block read");
-
- SizeType sz;
- ar >> make_nvp("size", sz);
- Dout(dc::filtration, "In Filtration: size read " << sz);
-
- IndexVector index_vector(sz);
- for (SizeType i = 0; i < sz; ++i)
- {
- index_vector[i] = append(Simplex());
- }
-
- int count = 0;
- for (SizeType i = 0; i < sz; ++i)
- {
- // FIXME
- //FiltrationSimplexSerialization simplex;
- //ar >> make_nvp("FiltrationSimplex", simplex);
- count++;
- Dout(dc::filtration, "In Filtration: simplex read (" << count << ")");
- //simplex.set_filtration_simplex(*index_vector[i], index_vector);
- }
- Dout(dc::filtration, "In Filtration: simplices read");
-}
-
-template<class S, class FS, class V>
-std::ostream&
-operator<<(std::ostream& out, const Filtration<S, FS, V>& f)
-{ return f.operator<<(out); }
-
-
--- a/include/filtrationcontainer.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,45 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2006
- */
-
-#ifndef __FILTRATIONCONTAINER_H__
-#define __FILTRATIONCONTAINER_H__
-
-#include "consistencylist.h"
-#include "cycle.h"
-
-/**
- * FiltrationContainer class. Serves as a parent of Filtration that
- * describes the container functionality. Used by FiltrationSimplex
- * to get Cycle representation.
- */
-template<class FltrSmplx>
-class FiltrationContainer: public ConsistencyList<FltrSmplx>
-{
- public:
- typedef FltrSmplx FiltrationSimplex;
- typedef ConsistencyList<FiltrationSimplex> ConsistencyList;
-
- /// \name Cycles and Trails
- /// @{
- /// Index is and therfore acts like an iterator. The name is preserved for historical reasons.
- typedef typename ConsistencyList::iterator Index;
- /// const_Index is a const_iterator
- typedef typename ConsistencyList::const_iterator const_Index;
- /// @}
-
- /// \name Cycles and Trails
- /// @{
- typedef typename ConsistencyList::GreaterThanComparison CyclesComparator;
- typedef typename ConsistencyList::LessThanComparison TrailsComparator;
- typedef typename ConsistencyList::ConsistencyComparison ConsistencyComparator;
- typedef ::Cycle<Index, CyclesComparator, ConsistencyComparator> Cycle;
- typedef ::Cycle<Index, TrailsComparator, ConsistencyComparator> Trail;
- /// @}
-
- template<class U>
- struct rebind { typedef FiltrationContainer<U> other; };
-};
-
-#endif // __FILTRATIONCONTAINER_H__
--- a/include/filtrationsimplex.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,89 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2006
- */
-
-#ifndef __FILTRATIONSIMPLEX_H__
-#define __FILTRATIONSIMPLEX_H__
-
-#include "sys.h"
-#include "debug.h"
-
-#include "filtrationcontainer.h"
-#include "vineyard.h"
-#include "types.h"
-
-#include <list>
-
-#if 0
-#include <boost/serialization/access.hpp>
-#include <boost/serialization/nvp.hpp>
-#include <boost/serialization/list.hpp>
-#endif
-
-/**
- * Evaluator is a base class for the structures that are able to return a value
- * given a simplex.
- */
-template<class Smplx>
-class Evaluator
-{
- public:
- typedef Smplx Simplex;
-
- virtual RealType time() { return 0; }
- virtual RealType value(const Simplex& s) { return 0; }
-};
-
-/**
- * FiltrationSimplex stores information needed for the RU-decomposition:
- * cycle (column of R), trail (row of U), and pair.
- */
-template<class Smplx>
-class FiltrationSimplex: public Smplx
-{
- public:
- typedef Smplx Simplex;
- typedef FiltrationSimplex<Simplex> Self;
- typedef FiltrationContainer<Self> Container;
- typedef Simplex Parent;
-
- typedef Vine<Simplex> Vine;
- typedef typename Container::Cycle Cycle;
- typedef typename Container::Trail Trail;
- typedef typename Container::Index Index;
-
- typedef Evaluator<Simplex> Evaluator;
-
- FiltrationSimplex(const Simplex& s):
- Simplex(s), vine_(0) {}
-
-
- /// \name Core functionality
- /// @{
- void set_pair(Index pair) { pair_ = pair; }
- bool sign() const { return cycles_column.empty(); }
- bool is_paired() const { return pair() != pair()->pair(); }
- void set_vine(Vine* v) { vine_ = v; }
- using Parent::dimension;
- /// @}
-
-
- /// \name Accessors
- /// @{
- Cycle& cycle() { return cycles_column; }
- Trail& trail() { return trails_row; }
- const Cycle& cycle() const { return cycles_column; }
- const Trail& trail() const { return trails_row; }
- Index pair() const { return pair_; }
- Vine* vine() const { return vine_; }
- /// @}
-
- private:
- Cycle cycles_column;
- Trail trails_row;
- Index pair_;
- Vine* vine_;
-};
-
-#endif // __FILTRATIONSIMPLEX_H__
--- a/include/geometry/eventqueue.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,71 +0,0 @@
-#ifndef __EVENTQUEUE_H__
-#define __EVENTQUEUE_H__
-
-#include <list>
-#include <functional>
-#include <boost/utility.hpp>
-
-#include <iostream>
-#include <cassert> // TODO: switch to internal debugging system
-#include <string>
-
-// TODO: change inefficient list-based implementation to something heap-based
-// Need a queue that supports deleting arbitrary items (given by iterator),
-// and maintaining correctness of iterators when different operations (notably
-// remove and update are performed)
-
-template<class Event_, class EventComparison_>
-class EventQueue
-{
-
- public:
- typedef Event_ Event;
- typedef EventComparison_ EventComparison;
-
- typedef std::list<Event> QueueRepresentation;
- typedef typename QueueRepresentation::iterator iterator;
- typedef typename QueueRepresentation::const_iterator const_iterator;
-
- EventQueue() {}
-
- const_iterator top() const { assert(!empty()); return queue_.begin(); }
- iterator top() { assert(!empty()); return queue_.begin(); }
- iterator push(Event e) { queue_.push_front(e); iterator i = top(); update(i); return i; }
- void pop() { assert(!empty()); queue_.erase(queue_.begin()); }
- void remove(iterator i) { queue_.erase(i); }
- void update(iterator i);
-
- iterator end() { return queue_.end(); }
- const_iterator end() const { return queue_.end(); }
- bool empty() const { return queue_.empty(); }
- size_t size() const { return queue_.size(); }
-
- std::ostream& print(std::ostream& out, const std::string& prefix) const;
-
- private:
- QueueRepresentation queue_;
-};
-
-
-template<class Event_, class EventComparison_>
-void
-EventQueue<Event_, EventComparison_>::
-update(iterator i)
-{
- QueueRepresentation tmp;
- tmp.splice(tmp.end(), queue_, i);
- iterator pos = std::find_if(queue_.begin(), queue_.end(), std::not1(std::bind2nd(EventComparison(), *i)));
- queue_.splice(pos, tmp);
-}
-
-template<class Event_, class EventComparison_>
-std::ostream&
-EventQueue<Event_, EventComparison_>::
-print(std::ostream& out, const std::string& prefix) const
-{
- for (typename QueueRepresentation::const_iterator cur = queue_.begin(); cur != queue_.end(); ++cur)
- (*cur)->print(out << prefix) << std::endl;
- return out;
-}
-
-#endif // __EVENTQUEUE_H__
--- a/include/geometry/simulator.h Sun Jul 01 00:00:00 2007 -0400
+++ b/include/geometry/simulator.h Tue Aug 14 17:15:08 2007 -0400
@@ -1,7 +1,7 @@
#ifndef __SIMULATOR_H__
#define __SIMULATOR_H__
-#include "eventqueue.h"
+#include "utilities/eventqueue.h"
#include "polynomial.h"
template<class Comparison> class IndirectComparison;
--- a/include/lowerstarfiltration.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,114 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2005 -- 2006
- */
-
-#ifndef __LOWERSTARFILTRATION_H__
-#define __LOWERSTARFILTRATION_H__
-
-#include "sys.h"
-#include "debug.h"
-
-#include "filtration.h"
-#include "simplex.h"
-#include "consistencylist.h"
-#include <boost/utility.hpp>
-#include <list>
-#include "types.h"
-
-#include <boost/serialization/access.hpp>
-#include <boost/serialization/vector.hpp>
-#include <boost/serialization/map.hpp>
-#include <boost/serialization/base_object.hpp>
-#include <boost/serialization/nvp.hpp>
-
-
-template<class VI,
- class Smplx = SimplexWithAttachment<VI>,
- class FltrSmplx = FiltrationSimplex<Smplx>,
- class Vnrd = Vineyard<FltrSmplx> >
-class LowerStarFiltration: public Filtration<Smplx, FltrSmplx, Vnrd>
-{
- public:
- // Treat VertexIndex as an iterator
- typedef VI VertexIndex;
- typedef Smplx Simplex;
- typedef Filtration<Simplex> Parent;
- typedef typename Parent::Vineyard Vineyard;
-
- typedef typename Parent::Index Index;
- typedef typename Parent::const_Index const_Index;
- typedef typename Parent::Cycle Cycle;
- typedef typename Parent::Trail Trail;
- typedef typename Simplex::Cycle SimplexBoundaryCycle;
-
- struct VertexDescriptor;
- typedef ConsistencyList<VertexDescriptor> VertexOrder;
- typedef typename VertexOrder::iterator VertexOrderIndex;
- typedef typename VertexOrder::const_iterator const_VertexOrderIndex;
- typedef typename VertexOrder::LessThanComparison VertexOrderComparison;
- struct SimplexAttachmentComparison;
-
- public:
- template<class VertexCmp>
- LowerStarFiltration(VertexIndex begin, VertexIndex end, const VertexCmp& cmp, Vineyard* vineyard);
-
- using Parent::size;
- using Parent::begin;
- using Parent::end;
- VertexIndex num_vertices() const { return vertex_order.size(); }
- const VertexOrderComparison&
- get_vertex_cmp() const { return vertex_cmp; }
-
- Index append(const Simplex& s);
- bool transpose_vertices(const VertexOrderIndex& voi);
-
- protected:
- /// Hint function: if unsure, should return true
- virtual bool neighbors(VertexIndex v1, VertexIndex v2) const { return true; }
-
- private:
- bool transpose(Index i);
- void assert_pairing(Index i);
-
- private:
- VertexOrder vertex_order;
- VertexOrderComparison vertex_cmp;
-
- /* Serialization */
- protected:
- LowerStarFiltration() {}
-
- private:
- friend class boost::serialization::access;
-
- template<class Archive>
- void save(Archive& ar, version_type ) const { ar << BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent); }
-
- template<class Archive>
- void load(Archive& ar, version_type );
-
- BOOST_SERIALIZATION_SPLIT_MEMBER()
-};
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-struct LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::VertexDescriptor
-{
- VertexDescriptor(VertexIndex vi, Index si):
- vertex_index(vi), simplex_index(si)
- {}
-
- VertexIndex vertex_index;
- Index simplex_index;
-};
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-struct LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::SimplexAttachmentComparison
-{
- bool operator()(const Simplex& first, const Simplex& second) const;
- VertexOrderComparison vertex_cmp;
-};
-
-#include "lowerstarfiltration.hpp"
-
-#endif // __LOWERSTARFILTRATION_H__
--- a/include/lowerstarfiltration.hpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,217 +0,0 @@
-/* Implementations */
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-template<class VertexCmp>
-LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
-LowerStarFiltration(VertexIndex begin, VertexIndex end, const VertexCmp& cmp, Vineyard* vineyard):
- Parent(vineyard)
-{
- // Record VertexIndexes in a temporary list
- typedef std::list<VertexIndex> VertexIndexList;
- VertexIndexList tmp_list;
- while (begin != end)
- tmp_list.push_back(begin++);
-
- // Sort the temporary list
- tmp_list.sort(cmp);
-
- // Record vertex order
- for(typename VertexIndexList::const_iterator cur = tmp_list.begin(); cur != tmp_list.end(); ++cur)
- (*cur)->set_order(vertex_order.push_back(VertexDescriptor(*cur, Parent::append(Simplex(*cur)))));
-}
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-typename LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::Index
-LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
-append(const Simplex& s)
-{
- AssertMsg(s.dimension() != 0, "All vertices must have been inserted in the constructor");
-
- // Find the highest vertex
- typename Simplex::VertexContainer::const_iterator cur = s.vertices().begin(), max = cur++;
- for (; cur != s.vertices().end(); ++cur)
- if (!vertex_cmp((*cur)->get_order(), (*max)->get_order()))
- max = cur;
-
- Index ms = (*max)->get_order()->simplex_index; Index prior;
- do { prior = ms++; } while (ms->dimension() <= s.dimension() && ms != Parent::end() && ms->get_attachment() == *max);
-
- Index i = Parent::insert(prior, s);
- i->set_attachment(*max);
-
- return i;
-}
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-bool
-LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::SimplexAttachmentComparison::
-operator()(const Simplex& first, const Simplex& second) const
-{
- int cmp = vertex_cmp.compare(first.get_attachment()->get_order(), second.get_attachment()->get_order());
- if (cmp == 0)
- return first.dimension() < second.dimension();
- else
- return cmp == -1;
-}
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-bool
-LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
-transpose_vertices(const VertexOrderIndex& order)
-{
- Count("VertexTransposition");
-
-#if COUNTERS
- if ((counters.lookup("VertexTransposition") % 1000000) == 0)
- {
- Dout(dc::lsfiltration, "Vertex transpositions: " << counters.lookup("VertexTransposition"));
- Dout(dc::lsfiltration, "Simplex transpositions: " << counters.lookup("SimplexTransposition"));
- Dout(dc::lsfiltration, "Attachment changed: " << counters.lookup("ChangedAttachment"));
- Dout(dc::lsfiltration, "Regular disconnected: " << counters.lookup("RegularDisconnected"));
- Dout(dc::lsfiltration, "Pairing Changed: " << counters.lookup("ChangedPairing"));
- Dout(dc::lsfiltration, "------------------------");
- }
-#endif // COUNTERS
-
- Dout(dc::lsfiltration, "Transposing vertices (" << order->vertex_index << ", "
- << boost::next(order)->vertex_index << ")");
-
- Index i = order->simplex_index;
- Index i_prev = boost::prior(i);
- Index i_next = boost::next(order)->simplex_index;
- Index i_next_prev = boost::prior(i_next); // transpositions are done in terms of the first index in the pair
- Index j = boost::next(i_next);
-
- const VertexIndex& v_i = order->vertex_index;
- const VertexIndex& v_i_next = boost::next(order)->vertex_index;
- bool nbghrs = neighbors(v_i, v_i_next);
-
- bool result = false;
-
- // First, move the vertex --- this can be sped up if we devise special "vertex transpose" operation
- while (i_next_prev != i_prev)
- {
- result |= transpose(i_next_prev);
- i_next_prev = boost::prior(i_next);
- }
- Dout(dc::lsfiltration, "Done moving the vertex");
-
- // Second, move the simplices attached to it
- Dout(dc::lsfiltration, "Moving attached simplices");
- while (j != Parent::end() && j->get_attachment() == v_i_next)
- {
- Dout(dc::lsfiltration, " Considering " << *j);
- if (nbghrs && j->contains(v_i)) // short circuit
- {
- Count("ChangedAttachment");
- Dout(dc::lsfiltration, " Attachment changed for " << *j);
- j->set_attachment(v_i);
- ++j;
- continue;
- }
-
- Index j_prev = j; ++j;
- while ((--j_prev)->get_attachment() != v_i_next) // i.e., until we have reached v_i_next
- // (and the simplices that follow it) again
- {
- Dout(dc::lsfiltration, " Moving: " << *j_prev << ", " << *boost::next(j_prev));
- AssertMsg(j_prev->get_attachment() == v_i, "Simplex preceding the one being moved must be attached to v_i");
- result |= transpose(j_prev);
- --j_prev;
- }
- }
- Dout(dc::lsfiltration, "Done moving attached simplices");
- vertex_order.swap(order, boost::next(order));
-
- return result;
-}
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-bool
-LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
-transpose(Index i)
-{
- Index j = boost::next(i);
-
- Dout(dc::lsfiltration, " Transposing (" << *i << ", " << *(i->pair()) << ") and ("
- << *j << ", " << *(j->pair()) << ")");
-
- assert_pairing(i);
- assert_pairing(j);
-
- bool res = Parent::transpose(i, false);
- Dout(dc::lsfiltration, " " << *j << ": " << *(j->pair()) << ", " << *i << ": " << *(i->pair()));
-
- assert_pairing(j);
- assert_pairing(i);
-
- return res;
-}
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-void
-LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
-assert_pairing(Index i)
-{
-#ifndef NDEBUG
- AssertMsg(i != Parent::end(), "Cannot assert pairing of end()");
- if (!i->sign())
- {
- if (i->pair() != i->cycle().top(Parent::get_cycles_cmp()))
- {
- Dout(dc::lsfiltration, "i (negative): " << *i);
- Dout(dc::lsfiltration, "pair(i): " << *(i->pair()));
- Dout(dc::lsfiltration, "i->cycle().top(): " << *(i->cycle().top(Parent::get_cycles_cmp())));
- DoutFatal(dc::fatal, "Pairing not matching the matrix at " << *i);
- }
- } else
- {
- if (i->pair() != i)
- {
- if (i->pair()->cycle().top(Parent::get_cycles_cmp()) != i)
- {
- Dout(dc::lsfiltration, "i (positive): " << *i);
- Dout(dc::lsfiltration, "pair(i): " << *(i->pair()));
- Dout(dc::lsfiltration, "pair(i)->cycle(): " << i->pair()->cycle());
- Dout(dc::lsfiltration, "pair->cycle().top(): " << *(i->pair()->cycle().top(Parent::get_cycles_cmp())));
- DoutFatal(dc::fatal, "Pairing not matching the matrix at " << *(i->pair()));
- }
- }
- }
-#endif
-}
-
-
-template<class VI, class Smplx, class FltrSmplx, class Vnrd>
-template<class Archive>
-void
-LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
-load(Archive& ar, version_type )
-{
-/*
- ar >> BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
-
- // Count the number of vertices
- VertexIndex num_vertices = 0;
- for (Index cur = begin(); cur != end(); ++cur)
- if (dimension(cur) == 0)
- num_vertices++;
-
- // Second pass to record vertex_order
- vertex_order.resize(num_vertices);
- inverse_vertex_order.resize(num_vertices);
- num_vertices = 0;
- for (Index cur = begin(); cur != end(); ++cur)
- {
- if (dimension(cur) == 0)
- {
- vertex_order[num_vertices].index = cur;
- vertex_order[num_vertices].vertex_index = *(cur->get_vertices().begin());
- inverse_vertex_order[vertex_order[num_vertices].vertex_index] = num_vertices;
- ++num_vertices;
- }
- }
-*/
-}
-
-
--- a/include/orderlist.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,212 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2006
- *
- * Implements the simplified order list data strcutre given in ``Two Simplified
- * Algorithms for Maintaining Order in a List'' by Bender et al.
- *
- * Indirection is not implemented, so the insertion cost is amortized O(log n),
- * while comparison and deletion are O(1).
- */
-
-#ifndef __ORDERLIST_H__
-#define __ORDERLIST_H__
-
-#include "sys.h"
-#include "debug.h"
-
-#include <iterator>
-#include <iostream>
-#include <list>
-
-#include "types.h"
-//#include "counter.h"
-
-#include <boost/utility.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
-//#include <boost/type_traits/is_convertible.hpp>
-//#include <boost/utility/enable_if.hpp>
-
-
-typedef unsigned int OrderType;
-
-template<class T> struct OrderListNode;
-template<class T> class OrderListIterator;
-template<class T> class const_OrderListIterator;
-
-/**
- * OrderList stores a list of objects while maintaining their total order under
- * the operations of insert(), swap(), and delete(). push_back() is provided for
- * uniformity, OrderComparison member class carries out comparison of the
- * elements.
- */
-template<class T>
-class OrderList: public std::list<OrderListNode<T> >
-{
- public:
- class OrderComparison;
-
- /// OrderComparison type
- typedef OrderComparison OrderComparison;
-
- typedef OrderListNode<T> NodeType;
- typedef OrderList<T> Self;
- typedef std::list<NodeType > Parent;
-
- typedef T value_type;
- typedef T& reference;
- typedef const T& const_reference;
- typedef OrderListIterator<T> iterator;
- typedef const_OrderListIterator<T> const_iterator;
-
- OrderList() {}
- ~OrderList() { clear(); }
-
- /// \name Order operations
- void swap(iterator i, iterator j); ///< Exchanges the order of simplices pointed to by i and j
- template<class BinaryPredicate>
- void sort(BinaryPredicate cmp); ///< Sorts the elements in accordance with cmp
-
- /// \name Container operations
- /// @{
- // Explicit calls instead of using declarations for Doxygen
- iterator push_back(const_reference x);
- iterator insert(iterator predecessor, const_reference x); ///< Inserts x immediately after predecessor (has to be a valid iterator)
- void erase(iterator x) { Parent::erase(x.get_base()); }
-
- void clear() { return Parent::clear(); }
- bool empty() const { return Parent::empty(); }
- SizeType size() const { return Parent::size(); }
- iterator begin() { return iterator(Parent::begin()); }
- const_iterator begin() const { return const_iterator(Parent::begin()); }
- iterator end() { return iterator(Parent::end()); }
- const_iterator end() const { return const_iterator(Parent::end()); }
- reference back() { return Parent::back(); }
- const_reference back() const { return Parent::back(); }
- void pop_back() { return Parent::pop_back(); }
-
- iterator last() { return iterator(boost::prior(end())); }
- const_iterator last() const { return const_iterator(boost::prior(end())); }
- /// @}
-
- /// \name Debugging operations
- /// @{
- void show_elements() const;
- /// @}
-
- private:
- static const float density_threshold = 1.2;
-};
-
-/// Basic comparison that LessThan and GreaterThan derive from
-template<class T>
-class OrderList<T>::OrderComparison
-{
- public:
- typedef typename OrderList<T>::const_iterator ComparableType;
- int compare(ComparableType a, ComparableType b) const; /// (-1,0,1) = a (precedes, ==, succeeds) b
- bool operator()(ComparableType a, ComparableType b) const;
-};
-
-/// Structure storing auxilliary information requred for each node of OrderList
-template<class T>
-struct OrderListNode
-{
- OrderListNode(const T& d, unsigned int t):
- data(d), tag(t)
- {}
-
- T data;
- OrderType tag;
-
- std::ostream& operator<<(std::ostream& out) const { return out << data << ": " << tag; }
-};
-
-template<class T, class BinaryPredicate>
-class OrderListNodeComparison
-{
- public:
- typedef OrderListNode<T> Node;
- OrderListNodeComparison(BinaryPredicate cmp): cmp_(cmp) {}
- bool operator()(const Node& a, const Node& b) const { return cmp_(a.data, b.data); }
-
- private:
- BinaryPredicate cmp_;
-};
-
-template<class T>
-std::ostream& operator<<(std::ostream& out, const OrderListNode<T>& n) { return n.operator<<(out); }
-
-template<class T>
-class OrderListIterator: public boost::iterator_adaptor<OrderListIterator<T>,
- typename OrderList<T>::Parent::iterator,
- T>
-{
- private:
- struct enabler {};
-
- public:
- typedef typename OrderList<T>::Parent OrderListParent;
- typedef boost::iterator_adaptor<OrderListIterator<T>,
- typename OrderListParent::iterator,
- T> Parent;
- typedef typename Parent::reference reference;
- typedef typename Parent::base_type base_type;
-
- OrderListIterator() {}
- OrderListIterator(const typename OrderListParent::iterator& iter):
- OrderListIterator::iterator_adaptor_(iter)
- {}
- OrderListIterator(const OrderListIterator<T>& other):
- OrderListIterator::iterator_adaptor_(other.base())
- {}
-
- private:
- friend class boost::iterator_core_access;
- reference dereference() const { return Parent::base_reference()->data; }
- base_type& get_base() { return Parent::base_reference(); }
-
- friend class OrderList<T>;
-};
-
-template<class T>
-class const_OrderListIterator: public boost::iterator_adaptor<const_OrderListIterator<T>,
- typename OrderList<T>::Parent::const_iterator,
- const T>
-{
- private:
- struct enabler {};
-
- public:
- typedef typename OrderList<T>::Parent OrderListParent;
- typedef boost::iterator_adaptor<const_OrderListIterator<T>,
- typename OrderListParent::const_iterator,
- const T> Parent;
- typedef typename Parent::reference reference;
- typedef typename Parent::base_type base_type;
-
- const_OrderListIterator() {}
- const_OrderListIterator(const typename OrderListParent::const_iterator& iter):
- const_OrderListIterator::iterator_adaptor_(iter)
- {}
- const_OrderListIterator(const const_OrderListIterator<T>& other):
- const_OrderListIterator::iterator_adaptor_(other.base())
- {}
- const_OrderListIterator(const OrderListIterator<T>& other):
- const_OrderListIterator::iterator_adaptor_(other.base())
- {}
-
- private:
- friend class boost::iterator_core_access;
- reference dereference() const { return Parent::base_reference()->data; }
- const base_type&
- get_base() { return Parent::base_reference(); }
-
- friend class OrderList<T>;
- friend class OrderList<T>::OrderComparison;
-};
-
-
-#include "orderlist.hpp"
-
-#endif // __ORDERLIST_H__
--- a/include/orderlist.hpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,118 +0,0 @@
-/* Implementations */
-
-template<class T>
-void
-OrderList<T>::
-swap(iterator i, iterator j)
-{
- typename Parent::iterator i_base = i.get_base();
- typename Parent::iterator j_base = j.get_base();
- std::swap(i_base->tag, j_base->tag);
-
- // Exchange the actual elements in the list --- so that iterators behave as expected
- typename Parent::iterator after_j = boost::next(j_base);
- Parent::splice(i_base, *this, j_base);
- Parent::splice(after_j, *this, i_base);
-}
-
-template<class T>
-template<class BinaryPredicate>
-void
-OrderList<T>::
-sort(BinaryPredicate cmp)
-{
- Parent::sort(OrderListNodeComparison<T, BinaryPredicate>(cmp));
- OrderType cur_order = 0;
- for (typename Parent::iterator cur = Parent::begin(); cur != Parent::end(); ++cur)
- cur->tag = cur_order++;
-}
-
-template<class T>
-typename OrderList<T>::iterator
-OrderList<T>::
-push_back(const_reference x)
-{
- if (empty())
- Parent::push_back(NodeType(x, 0));
- else
- Parent::push_back(NodeType(x, last().get_base()->tag + 1));
-
- return last();
-}
-
-template<class T>
-typename OrderList<T>::iterator
-OrderList<T>::
-insert(iterator p, const_reference x)
-{
- typename Parent::iterator p_base = p.get_base();
- OrderType tag = (p_base++)->tag + 1;
- typename Parent::iterator new_base = Parent::insert(p_base, NodeType(x, tag));
-
- if (p_base->tag != tag)
- return iterator(new_base);
-
- // Find non-overflowing region
- unsigned int num_elements = 1, maximum = 1, lower = tag, upper = tag, level = 0;
- float inv_density = 1;
- typename Parent::iterator prev = p_base, next = p_base;
- --(--prev); ++next; // move prev back twice to skip over the newly inserted element
-
- do
- {
- lower &= ~(1 << level);
- upper |= (1 << level);
- maximum <<= 1; inv_density *= density_threshold;
- ++level;
-
- while (prev != Parent::end() && prev->tag >= lower) { --prev; ++num_elements; }
- while (next != Parent::end() && next->tag <= upper) { ++next; ++num_elements; }
- } while (inv_density * num_elements >= maximum);
- ++num_elements; // for the extra element inserted
-
- Dout(dc::orderlist, num_elements << ", " << lower << ", " << upper);
- Dout(dc::orderlist, "prev is at the end: " << (prev == Parent::end()));
- Dout(dc::orderlist, "next is at the end: " << (next == Parent::end()));
-
- // Reorder
- AssertMsg((upper - lower + 1)/num_elements > 0, "Spacing between new tags must be non-zero");
- for (int i = 0; i < num_elements; ++i)
- {
- (++prev)->tag = lower + i*((upper - lower + 1)/num_elements);
- Dout(dc::orderlist, prev->tag);
- AssertMsg(prev->tag != 0 || prev == Parent::begin(), "Cannot assign 0 tag except at the beginning of OrderList");
- }
-
- AssertMsg(++prev == next, "prev + num_elements != next in OrderList::insert()");
-
- return iterator(new_base);
-}
-
-template<class T>
-void
-OrderList<T>::
-show_elements() const
-{
- for (const_iterator cur = begin(); cur != end(); ++cur)
- std::cout << *(cur.get_base()) << std::endl;
- std::cout << std::endl;
-}
-
-/* OrderComparison */
-template<class T>
-int
-OrderList<T>::OrderComparison::
-compare(ComparableType a, ComparableType b) const
-{
- if (a.get_base()->tag == b.get_base()->tag) return 0;
- if (a.get_base()->tag < b.get_base()->tag) return -1;
- return 1;
-}
-
-template<class T>
-bool
-OrderList<T>::OrderComparison::
-operator()(ComparableType a, ComparableType b) const
-{
- return (compare(a,b) < 0);
-}
--- a/include/simplex.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,170 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2005 -- 2006
- */
-
-#ifndef __SIMPLEX_H__
-#define __SIMPLEX_H__
-
-#include "sys.h"
-#include "debug.h"
-
-#include <set>
-#include <list>
-#include <iostream>
-
-#include "types.h"
-
-#include <boost/serialization/access.hpp>
-
-
-/**
- * SimplexWithVertices is a basic simplex class. It stores vertices of a given type,
- * and knows how to compute its own boundary. It should probably be used as a base
- * class for any explicit simplex representation.
- */
-template<class V>
-class SimplexWithVertices
-{
- public:
- typedef V Vertex;
- typedef SimplexWithVertices<Vertex> Self;
-
- typedef std::set<Vertex> VertexContainer;
- typedef std::list<Self> Cycle;
-
- /// \name Constructors
- /// @{
- SimplexWithVertices() {}
- SimplexWithVertices(const Self& s):
- vertices_(s.vertices_) {}
- template<class Iterator>
- SimplexWithVertices(Iterator bg, Iterator end):
- vertices_(bg, end) {}
- SimplexWithVertices(const VertexContainer& v):
- vertices_(v) {}
- SimplexWithVertices(Vertex v):
- vertices_() { vertices_.insert(v); }
- /// @}
-
- /// \name Core
- /// @{
- Cycle boundary() const;
- Dimension dimension() const { return vertices_.size()-1; }
- /// @}
-
- /// \name Vertex manipulation
- /// @{
- bool contains(const Vertex& v) const { return (vertices_.find(v) != vertices_.end()); }
- const VertexContainer& vertices() const { return vertices_; }
- void add(const Vertex& v) { vertices_.insert(v); }
- /// @}
-
- /// \name Assignment and comparison
- /// Gives an ordering on simplices (for example, so that simplices can be used as keys for std::map)
- /// @{
- const Self& operator=(const Self& s) { vertices_ = s.vertices_; return *this; }
- bool operator==(const Self& s) const { return vertices_ == s.vertices_; }
- bool operator<(const Self& s) const { return vertices_ < s.vertices_; }
- /// @}
-
- std::ostream& operator<<(std::ostream& out) const;
-
- private:
- VertexContainer vertices_;
-
- private:
- /* Serialization */
- friend class boost::serialization::access;
-
- template<class Archive>
- void serialize(Archive& ar, version_type );
-};
-
-/**
- * SimplexWithValue explicitly adds a RealType value to the SimplexWithVertices.
- */
-template<class Vert>
-class SimplexWithValue: public SimplexWithVertices<Vert>
-{
- public:
- typedef Vert Vertex;
- typedef RealType Value;
- typedef SimplexWithValue<Vertex> Self;
- typedef SimplexWithVertices<Vertex> Parent;
-
- typedef typename Parent::VertexContainer VertexContainer;
-
- /// \name Constructors
- /// @{
- SimplexWithValue(Value value = 0): val(value) {}
- SimplexWithValue(const Self& s):
- Parent(s), val(s.val) {}
- SimplexWithValue(const Parent& s, Value value = 0):
- Parent(s), val(value) {}
- template<class Iterator>
- SimplexWithValue(Iterator bg, Iterator end, Value value = 0):
- Parent(bg, end), val(value) {}
- SimplexWithValue(const VertexContainer& v, Value value = 0):
- Parent(v), val(value) {}
- /// @}
-
- /// \name Core
- /// @{
- void set_value(Value value) { val = value; }
- Value get_value() const { return val; }
- /// @}
-
- const Self& operator=(const Self& s);
- std::ostream& operator<<(std::ostream& out) const;
-
- private:
- Value val;
-
- /* Serialization */
- friend class boost::serialization::access;
-
- template<class Archive>
- void serialize(Archive& ar, version_type );
-};
-
-/**
- * SimplexWithAttachment stores the vertex to which the simplex is attached (meant for lower-star filtrations)
- */
-template<typename V>
-class SimplexWithAttachment: public SimplexWithVertices<V>
-{
- public:
- typedef V VertexIndex;
- typedef SimplexWithVertices<VertexIndex> Parent;
-
- /// \name Constructors
- /// @{
- SimplexWithAttachment():
- attachment(VertexIndex()) {}
- template<class Iterator>
- SimplexWithAttachment(Iterator bg, Iterator end):
- Parent(bg, end) {}
- SimplexWithAttachment(const Parent& s):
- Parent(s) {}
- SimplexWithAttachment(VertexIndex vi):
- Parent(vi), attachment(vi) {}
- /// @}
-
- void set_attachment(VertexIndex v) { attachment = v; }
- VertexIndex get_attachment() const { return attachment; }
-
- private:
- VertexIndex attachment;
-
- private:
- // Serialization
- friend class boost::serialization::access;
-
- template<class Archive>
- void serialize(Archive& ar, version_type );
-};
-
-#include "simplex.hpp"
-
-#endif // __SIMPLEX_H__
--- a/include/simplex.hpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,94 +0,0 @@
-#include <boost/serialization/base_object.hpp>
-#include <boost/serialization/set.hpp>
-#include <boost/serialization/nvp.hpp>
-
-
-/* Implementations */
-
-/* SimplexWithVertices */
-template<class V>
-typename SimplexWithVertices<V>::Cycle
-SimplexWithVertices<V>::
-boundary() const
-{
- Cycle bdry;
- if (dimension() == 0) return bdry;
-
- for (typename VertexContainer::const_iterator cur = vertices_.begin(); cur != vertices_.end(); ++cur)
- {
- bdry.push_back(*this);
- Self& s = bdry.back();
- s.vertices_.erase(*cur);
- }
-
- return bdry;
-}
-
-template<class V>
-std::ostream&
-SimplexWithVertices<V>::
-operator<<(std::ostream& out) const
-{
- for (typename VertexContainer::const_iterator cur = vertices_.begin(); cur != vertices_.end(); ++cur)
- out << *cur << ' ';
-
- return out;
-}
-
-template<class V>
-template<class Archive>
-void
-SimplexWithVertices<V>::
-serialize(Archive& ar, version_type )
-{ ar & BOOST_SERIALIZATION_NVP(vertices_); }
-
-template<class V>
-std::ostream& operator<<(std::ostream& out, const SimplexWithVertices<V>& s)
-{ return s.operator<<(out); }
-
-
-/* SimplexWithValue */
-template<class V>
-std::ostream&
-SimplexWithValue<V>::
-operator<<(std::ostream& out) const
-{
- Parent::operator<<(out);
- out << "(val = " << val << ")";
- return out;
-}
-
-template<class V>
-const typename SimplexWithValue<V>::Self&
-SimplexWithValue<V>::
-operator=(const Self& s)
-{
- Parent::operator=(s);
- val = s.val;
- return *this;
-}
-
-template<class V>
-template<class Archive>
-void
-SimplexWithValue<V>::
-serialize(Archive& ar, version_type )
-{
- ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
- ar & BOOST_SERIALIZATION_NVP(val);
-}
-
-template<typename V>
-template<class Archive>
-void
-SimplexWithAttachment<V>::
-serialize(Archive& ar, version_type )
-{
- ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
- ar & BOOST_SERIALIZATION_NVP(attachment);
-}
-
-
-template<class V>
-std::ostream& operator<<(std::ostream& out, const SimplexWithValue<V>& s)
-{ return s.operator<<(out); }
--- a/include/sys.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,26 +0,0 @@
-// sys.h
-//
-// This header file is included at the top of every source file,
-// before any other header file.
-// It is intended to add defines that are needed globally and
-// to work around Operating System dependend incompatibilities.
-
-// EXAMPLE: If you use autoconf you can add the following here.
-// #ifdef HAVE_CONFIG_H
-// #include "config.h"
-// #endif
-
-// EXAMPLE: You could add stuff like this here too
-// (Otherwise add -DCWDEBUG to your CFLAGS).
-// #if defined(WANTSDEBUGGING) && defined(HAVE_LIBCWD_BLAHBLAH)
-// #define CWDEBUG
-// #endif
-
-// The following is the libcwd related mandatory part.
-// It must be included before any system header file is included!
-#ifdef CWDEBUG
-#ifndef _GNU_SOURCE
-#define _GNU_SOURCE
-#endif
-#include <libcwd/sys.h>
-#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/cycle.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,115 @@
+/**
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2005-2006
+ */
+
+#ifndef __CYCLE_H__
+#define __CYCLE_H__
+
+#include "utilities/sys.h"
+#include "utilities/debug.h"
+
+#include "utilities/types.h"
+#include "utilities/circular_list.h"
+#include <list>
+#include <boost/serialization/access.hpp>
+
+/**
+ * Class storing a cycle of simplices. Stores items in the order defined by ConsistencyCmp.
+ * The actual order of the elements is defined by OrderCmp. Instances of those
+ * classes are not stored in Cycle for efficiency, and are passed as arguments to those methods
+ * that require them.
+ */
+template <class Itm, class OrderCmp, class ConsistencyCmp = OrderCmp>
+class Cycle: public List<Itm>
+{
+ public:
+ /// \name Template Parameters
+ /// @{
+ typedef Itm Item;
+ typedef OrderCmp OrderComparison;
+ typedef ConsistencyCmp ConsistencyComparison;
+ /// @}
+
+ typedef Cycle<Item, OrderComparison, ConsistencyCmp> Self;
+ typedef List<Item> CycleRepresentation;
+
+ /// \name Accessor typedefs
+ /// @{
+ typedef typename CycleRepresentation::iterator iterator;
+ typedef typename CycleRepresentation::const_iterator const_iterator;
+ typedef typename CycleRepresentation::const_reference const_reference;
+ typedef typename CycleRepresentation::reference reference;
+ typedef typename CycleRepresentation::pointer pointer;
+ typedef typename CycleRepresentation::const_pointer const_pointer;
+ /// @}
+
+ public:
+ Cycle();
+ Cycle(const Cycle& c);
+
+ /// \name Whole Cycle operations
+ /// @{
+ /** Add c to *this assuming both Cycles are sorted in increasing order according to cmp. */
+ Self& add(const Self& c, const ConsistencyComparison& cmp);
+ void swap(Cycle& c); ///< Swaps the contents of c and *this (like STL's swap destroys c)
+ //void insertion_sort(const Comparison& cmp); ///< Sort list[i] using insertion sort
+ void sort(const ConsistencyComparison& cmp); ///< Sort elements to enforce consistency
+ using CycleRepresentation::empty;
+ using CycleRepresentation::clear;
+ using CycleRepresentation::size;
+ /// @}
+
+ /// \name Modifiers
+ /// @{
+ using CycleRepresentation::erase;
+ void append(const_reference x, const ConsistencyComparison& cmp);
+ /// @}
+
+ /// \name Accessors
+ /// @{
+ using CycleRepresentation::begin;
+ using CycleRepresentation::end;
+ const_reference top(const OrderComparison& cmp) const; ///< First element in cmp order
+ iterator get_second(const OrderComparison& cmp) const; ///< Second element in cmp order
+ /// @}
+
+ /// \name Block access optimizations
+ // Between operations used in optimization of transpositions for regular vertices. Maybe we don't need these? TODO
+ /// @{
+ /** Return first after i, but before or equal j; return i if no such element found */
+ const_reference first_between(const_reference i, const_reference j, const OrderComparison& cmp);
+ /// Add lists and remove all elements after i and before or equal to j
+ const_reference add_and_first_between(const Self& c, const ConsistencyComparison& consistency_cmp,
+ const_reference i, const_reference j, const OrderComparison& order_cmp);
+ /// Erase everything after i, but before or equal to j
+ void erase_between(const_reference i, const_reference j, const OrderComparison& cmp);
+ /// @}
+
+ /// \name Debugging
+ /// @{
+ const_reference get_first(const OrderComparison& cmp) const; ///< First element in cmp order
+ std::ostream& operator<<(std::ostream& out) const;
+ /// @}
+
+ private:
+ typedef std::list<Item> TemporaryCycleRepresenation;
+
+ using CycleRepresentation::push_back;
+ using CycleRepresentation::insert;
+
+ private:
+ size_t sz;
+
+ private:
+ // Serialization
+ typedef List<Item> Parent;
+ friend class boost::serialization::access;
+ template<class Archive>
+ void serialize(Archive& ar, version_type );
+};
+
+#include "cycle.hpp"
+
+#endif // __CYCLE_H__
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/cycle.hpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,280 @@
+#include <algorithm>
+#include <vector>
+
+#include <boost/serialization/split_member.hpp>
+#include <boost/serialization/nvp.hpp>
+#include <boost/serialization/binary_object.hpp>
+#include <boost/utility.hpp>
+
+using boost::serialization::make_nvp;
+using boost::serialization::make_binary_object;
+
+template<class I, class OrderCmp, class ConsistencyCmp>
+Cycle<I,OrderCmp,ConsistencyCmp>::
+Cycle(): sz(0)
+{}
+
+template<class I, class OrderCmp, class ConsistencyCmp>
+Cycle<I,OrderCmp,ConsistencyCmp>::
+Cycle(const Cycle& c): CycleRepresentation(c), sz(c.sz)
+{}
+
+template<class I, class OrderCmp, class ConsistencyCmp>
+void
+Cycle<I,OrderCmp,ConsistencyCmp>::
+append(const_reference x, const ConsistencyCmp& cmp)
+{
+ // First try the special cases that x goes at the end
+ const_reference last = CycleRepresentation::back();
+ if (empty() || cmp(last, x))
+ {
+ push_back(x);
+ return;
+ }
+
+ for (iterator cur = begin(); cur != end(); ++cur)
+ if (cmp(x, *cur))
+ {
+ insert(cur, x);
+ return;
+ }
+}
+
+template<class I, class OrderCmp, class ConsistencyCmp>
+typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
+Cycle<I,OrderCmp,ConsistencyCmp>::
+top(const OrderComparison& cmp) const
+{
+ AssertMsg(!empty(), "Cycle must not be empty for top()");
+ const_iterator min = begin();
+ for (const_iterator cur = ++begin(); cur != end(); ++cur)
+ if (cmp(*cur, *min))
+ min = cur;
+ return *min;
+}
+
+template<class I, class OrderCmp, class ConsistencyCmp>
+void
+Cycle<I,OrderCmp,ConsistencyCmp>::
+swap(Cycle& c)
+{
+ CycleRepresentation::swap(c);
+ std::swap(sz, c.sz);
+}
+
+template<class I, class OrderCmp, class ConsistencyCmp>
+void
+Cycle<I,OrderCmp,ConsistencyCmp>::
+sort(const ConsistencyComparison& cmp)
+{
+ std::vector<Item> tmp(begin(), end());
+ std::sort(tmp.begin(), tmp.end(), cmp);
+ std::copy(tmp.begin(), tmp.end(), begin());
+}
+
+template<class I, class OrderCmp, class ConsistencyCmp>
+typename Cycle<I,OrderCmp,ConsistencyCmp>::iterator
+Cycle<I,OrderCmp,ConsistencyCmp>::
+get_second(const OrderComparison& cmp) const
+{
+ AssertMsg(!empty(), "Cycle must not be empty for get_second()");
+ if (size() < 2) return begin(); // Indicates that there is no second.
+
+ Dout(dc::cycle, "Looking for second");
+ AssertMsg(size() >= 2, "Cycle must have at least two elements for get_second()");
+ iterator min = begin();
+ iterator second = ++begin();
+ if (cmp(*second, *min))
+ std::swap(min, second);
+ for (iterator cur = boost::next(begin(),2); cur != end(); ++cur)
+ {
+ if (cmp(*cur, *min))
+ {
+ second = min;
+ min = cur;
+ } else if (cmp(*cur, *second))
+ {
+ second = cur;
+ }
+ }
+
+ Dout(dc::cycle, "Looked up: " << **second);
+ return second;
+}
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
+Cycle<I,OrderCmp,ConsistencyCmp>::
+first_between(const_reference i, const_reference j, const OrderComparison& cmp)
+{
+ // Find the first element in ConsistencyComparison order (> i and <= j)
+ const_pointer first = &i;
+ iterator cur = begin();
+ for (; cur != end(); ++cur)
+ {
+ if ((*cur == j) || (cmp(*cur, j) && cmp(i, *cur)))
+ {
+ first = &(*cur);
+ break;
+ }
+ }
+
+ // If no such element found, then we are done
+ if (cur == end())
+ return i;
+
+ // Find first element in OrderComparison order (> i and <= j)
+ for (++cur; cur != end(); ++cur)
+ {
+ if ((*cur == j) || (cmp(*cur, j) && cmp(i, *cur)))
+ {
+ if (cmp(*cur, *first))
+ first = &(*cur);
+ }
+ }
+ return *first;
+}
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+void
+Cycle<I,OrderCmp,ConsistencyCmp>::
+erase_between(const_reference i, const_reference j, const OrderComparison& cmp)
+{
+ for (iterator cur = begin(); cur != end(); ++cur)
+ while ((cur != end()) && ((*cur == j) || (cmp(*cur, j) && cmp(i, *cur))))
+ {
+ Dout(dc::cycle, "Iteration of the erase while loop");
+ cur = erase(cur);
+ }
+}
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+std::ostream&
+Cycle<I,OrderCmp,ConsistencyCmp>::
+operator<<(std::ostream& out) const
+{
+ for (const_iterator cur = begin(); cur != end(); ++cur)
+ {
+ out << **cur << ", ";
+ }
+ // out << "(last: " << *last << ")"; // For debugging only
+ return out;
+}
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+std::ostream&
+operator<<(std::ostream& out, const Cycle<I, OrderCmp, ConsistencyCmp>& c)
+{
+ return c.operator<<(out);
+}
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+typename Cycle<I, OrderCmp, ConsistencyCmp>::Self&
+Cycle<I, OrderCmp, ConsistencyCmp>::
+add(const Self& c, const ConsistencyCmp& cmp)
+{
+ Dout(dc::cycle, "Adding cycles: " << *this << " + " << c);
+
+ iterator cur1 = begin();
+ const_iterator cur2 = c.begin();
+
+ while (cur2 != c.end())
+ {
+ if (cur1 == end())
+ {
+ while (cur2 != c.end())
+ push_back(*cur2++);
+ Dout(dc::cycle, "After addition: " << *this);
+ return *this;
+ }
+
+ // mod 2
+ int res = cmp.compare(*cur1, *cur2);
+ Dout(dc::cycle, "Comparison result: " << res);
+ if (res == 0) // *cur1 == *cur2
+ {
+ Dout(dc::cycle, "Equality");
+ cur1 = erase(cur1); // erase cur1 --- as a result cur1 will be pointing at old_cur1++
+ --sz;
+ ++cur2;
+ } else if (res < 0) // *cur1 < *cur2
+ {
+ Dout(dc::cycle, "Less than");
+ cur1++;
+ } else if (res > 0) // *cur1 > *cur2
+ {
+ Dout(dc::cycle, "Greater than");
+ insert(cur1, *cur2);
+ ++cur2;
+ ++sz;
+ }
+ }
+
+ Dout(dc::cycle, "After addition: " << *this);
+ return *this;
+}
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
+Cycle<I,OrderCmp,ConsistencyCmp>::
+add_and_first_between(const Self& c, const ConsistencyComparison& consistency_cmp,
+ const_reference i, const_reference j, const OrderComparison& order_cmp)
+{
+ add(c, consistency_cmp);
+ return first_between(i,j, order_cmp);
+}
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+typename Cycle<I,OrderCmp,ConsistencyCmp>::const_reference
+Cycle<I,OrderCmp,ConsistencyCmp>::
+get_first(const OrderComparison& cmp) const
+{ return top(cmp); }
+
+
+template<typename I, class OrderCmp, class ConsistencyCmp>
+template<class Archive>
+void
+Cycle<I,OrderCmp,ConsistencyCmp>::
+serialize(Archive& ar, version_type )
+{
+ ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
+ ar & make_nvp("size", sz);;
+}
+
+
+/*
+template<typename I, class Cmp>
+void
+Cycle<I, Cmp>::
+insertion_sort(const Comparison& cmp)
+{
+ TemporaryCycleRepresenation tmp;
+
+ // Insertion sort into the temporary list
+ for (const_iterator cur = begin(); cur != end(); ++cur)
+ {
+ typename TemporaryCycleRepresenation::iterator tmp_cur = tmp.end();
+ typename TemporaryCycleRepresenation::iterator tmp_next = tmp_cur--;
+
+ while (tmp_next != tmp.begin())
+ {
+ if (cmp(*cur, *tmp_cur))
+ tmp_next = tmp_cur--;
+ else
+ break;
+ }
+ tmp.insert(tmp_next, *cur);
+ }
+
+ // Copy temporary list back into ourselves
+ iterator cur = begin();
+ typename TemporaryCycleRepresenation::const_iterator tmp_cur = tmp.begin();
+ while(tmp_cur != tmp.end())
+ {
+ *cur = *tmp_cur;
+ ++cur; ++tmp_cur;
+ }
+}
+*/
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/filtration.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,133 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2005 -- 2006
+ */
+
+#ifndef __FILTRATION_H__
+#define __FILTRATION_H__
+
+#include "utilities/sys.h"
+#include "utilities/debug.h"
+
+#include "filtrationcontainer.h"
+#include "filtrationsimplex.h"
+#include "vineyard.h"
+
+#include <map>
+#include <vector>
+
+#include <boost/serialization/access.hpp>
+
+/**
+ * Filtration class. Serves as an (ordered) container for the simplices,
+ * and provides pair_simplices() method that computes the RU-decomposition
+ * for the simplex order stored in the filtration. Iterators remain valid
+ * through all the operations.
+ */
+template<class Smplx, class FltrSmplx = FiltrationSimplex<Smplx>, class Vnrd = Vineyard<FltrSmplx> >
+class Filtration: public FltrSmplx::Container
+{
+ public:
+ typedef Smplx Simplex;
+ typedef FltrSmplx FiltrationSimplex;
+ typedef Vnrd Vineyard;
+
+ /// \name Container Types
+ /// @{
+ /** The actual container type (which is the parent of the Filtration) */
+ typedef typename FiltrationSimplex::Container FiltrationContainer;
+ typedef typename FiltrationContainer::Index Index;
+ typedef typename FiltrationContainer::const_Index const_Index;
+ /// @}
+
+ /// \name Cycles and Trails
+ /// @{
+ typedef typename FiltrationContainer::GreaterThanComparison CyclesComparator;
+ typedef typename FiltrationContainer::LessThanComparison TrailsComparator;
+ typedef typename FiltrationContainer::ConsistencyComparison ConsistencyComparator;
+ typedef typename FiltrationContainer::Cycle Cycle;
+ typedef typename FiltrationContainer::Trail Trail;
+ typedef typename Cycle::iterator CycleIterator;
+ typedef typename Trail::iterator TrailIterator;
+ /// @}
+
+ typedef Filtration<Simplex, FiltrationSimplex, Vineyard> Self;
+ typedef FiltrationContainer Parent;
+
+ public:
+ Filtration(Vineyard* vineyard);
+
+ /// \name Core Functionality
+ /// @{
+ /// Computes RU decomposition of the simplices in [bg, end) range, assuming that everything before bg has been paired
+ void pair_simplices(Index bg, Index end);
+ void pair_simplices() { pair_simplices(begin(), end()); }
+ bool transpose(Index i, bool maintain_lazy = true);
+ bool is_paired() const;
+ Index append(const Simplex& s); ///< Appends s to the filtration
+ Index insert(Index prior, const Simplex& s); ///< Inserts s after prior
+ const_Index get_index(const Simplex& s) const; /**< Returns the iterator pointing to s
+ (end() if s not in filtration) */
+ Index get_index(const Simplex& s); ///< \overload
+ void fill_simplex_index_map(); ///< Fills the mapping for get_index()
+ /// @}
+
+ /// \name Accessors
+ /// @{
+ Vineyard* vineyard() { return vineyard_; }
+ const Vineyard* vineyard() const { return vineyard_; }
+ /// @}
+
+ protected:
+ using Parent::swap;
+ bool transpose_simplices(Index i, bool maintain_lazy);
+
+ public:
+ /// \name Container Operations
+ /// @{
+ using Parent::size;
+ using Parent::begin;
+ using Parent::end;
+ /// @}
+
+ std::ostream& operator<<(std::ostream& out) const;
+
+ protected:
+ /// \name Comparator accessors (protected)
+ /// @{
+ const ConsistencyComparator& get_consistency_cmp() const { return consistency_cmp; }
+ const CyclesComparator& get_cycles_cmp() const { return cycles_cmp; }
+ const TrailsComparator& get_trails_cmp() const { return trails_cmp; }
+ /// @}
+
+ private:
+ typedef std::map<Simplex, Index> SimplexMap;
+
+ /// Initializes the cycle with the indices of the simplices in the boundary, and the trail with the index of this simplex
+ void init_cycle_trail(Index j);
+ void pairing_switch(Index i, Index j);
+
+ bool paired;
+ SimplexMap inverse_simplices;
+
+ Vineyard* vineyard_;
+
+ CyclesComparator cycles_cmp;
+ TrailsComparator trails_cmp;
+ ConsistencyComparator consistency_cmp;
+
+ private:
+ /* Serialization */
+ friend class boost::serialization::access;
+
+ typedef std::map<const_Index, SizeType, ConsistencyComparator> IndexIntMap;
+ typedef std::vector<Index> IndexVector;
+
+ template<class Archive> void save(Archive& ar, version_type ) const;
+ template<class Archive> void load(Archive& ar, version_type );
+ BOOST_SERIALIZATION_SPLIT_MEMBER()
+};
+
+#include "filtration.hpp"
+
+#endif // __FILTRATION_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/filtration.hpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,463 @@
+#include "utilities/counter.h"
+#include "utilities/types.h"
+#include <algorithm>
+
+#include <boost/utility.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/serialization/nvp.hpp>
+#include <boost/serialization/list.hpp>
+#include <boost/serialization/is_abstract.hpp>
+
+using boost::serialization::make_nvp;
+
+/* Filtration Public */
+
+template<class S, class FS, class V>
+Filtration<S, FS, V>::
+Filtration(Vineyard* vnrd = 0): paired(false), vineyard_(vnrd)
+{}
+
+template<class S, class FS, class V>
+void
+Filtration<S, FS, V>::
+pair_simplices(Index bg, Index end)
+{
+ Dout(dc::filtration, "Entered: compute_pairing");
+ for (Index j = bg; j != end; ++j)
+ {
+ Dout(dc::filtration|flush_cf|continued_cf, *j << ": ");
+ init_cycle_trail(j);
+ Cycle& bdry = j->cycle();
+ Dout(dc::finish, bdry);
+
+ CountNum("Boundaries", j->dimension());
+ Count("SimplexCount");
+
+ while(!bdry.empty())
+ {
+ Index i = bdry.top(cycles_cmp);
+ Dout(dc::filtration, *i << ": " << *(i->pair()));
+ AssertMsg(!cycles_cmp(i, j), "Simplices in the cycle must precede current simplex: " <<
+ "(" << *i << " in cycle of " << *j << ")");
+
+ // i is not paired, so we pair j with i
+ if (i->pair() == i)
+ {
+ Dout(dc::filtration, "Pairing " << *i << " and " << *j << " with cycle " << j->cycle());
+ i->set_pair(j);
+ j->set_pair(i);
+ CountNum("DepositedCycleLength", j->cycle().size());
+ break;
+ }
+
+ // continue searching --- change the Dout to the continued mode with newlines FIXME
+ Dout(dc::filtration, " Adding: [" << bdry << "] + ");
+ Dout(dc::filtration, " [" << i->pair()->cycle() << "]");
+ bdry.add(i->pair()->cycle(), get_consistency_cmp());
+ i->pair()->trail().append(j, get_consistency_cmp());
+ Dout(dc::filtration, "After addition: " << bdry);
+ }
+ Dout(dc::filtration, "Finished with " << *j << ": " << *(j->pair()));
+ }
+ paired = true;
+}
+
+template<class S, class FS, class V>
+bool
+Filtration<S, FS, V>::
+is_paired() const
+{ return paired; }
+
+/**
+ * Transposes simplices at i and i+1, and records the knee in the vineyard if there is a change in pairing.
+ * Returns true if the pairing changed.
+ */
+template<class S, class FS, class V>
+bool
+Filtration<S,FS,V>::
+transpose(Index i, bool maintain_lazy)
+{
+ AssertMsg(vineyard() != 0, "We must have a vineyard for transpositions");
+
+ Index i_orig = i++;
+
+ AssertMsg(i_orig->pair() != i, "Transposing simplices must not be paired");
+ bool result = transpose_simplices(i_orig, maintain_lazy);
+ AssertMsg(i_orig == boost::next(i), "Wrong indices after transposition");
+
+ if (result) vineyard()->switched(i, i_orig);
+ return result;
+}
+
+template<class S, class FS, class V>
+typename Filtration<S, FS, V>::Index
+Filtration<S, FS, V>::
+append(const Simplex& s)
+{
+ Index i = push_back(FiltrationSimplex(s));
+ return i;
+}
+
+template<class S, class FS, class V>
+typename Filtration<S, FS, V>::Index
+Filtration<S, FS, V>::
+insert(Index prior, const Simplex& s)
+{
+ Index i = Parent::insert(prior, FiltrationSimplex(s));
+ paired = false;
+
+ return i;
+}
+
+template<class S, class FS, class V>
+typename Filtration<S, FS, V>::const_Index
+Filtration<S, FS, V>::
+get_index(const Simplex& s) const
+{
+ typename SimplexMap::const_iterator i = inverse_simplices.find(s);
+ if (i == inverse_simplices.end())
+ return end();
+ else
+ return i->second;
+}
+
+template<class S, class FS, class V>
+typename Filtration<S, FS, V>::Index
+Filtration<S, FS, V>::
+get_index(const Simplex& s)
+{
+ typename SimplexMap::const_iterator i = inverse_simplices.find(s);
+ if (i == inverse_simplices.end())
+ return end();
+ else
+ return i->second;
+}
+
+template<class S, class FS, class V>
+void
+Filtration<S, FS, V>::
+fill_simplex_index_map()
+{
+ for (Index i = begin(); i != end(); ++i)
+ inverse_simplices[*i] = i;
+}
+
+template<class S, class FS, class V>
+std::ostream&
+Filtration<S, FS, V>::
+operator<<(std::ostream& out) const
+{
+ out << "Pairing: " << std::endl;
+ for (const_Index i = begin(); i != end(); ++i)
+ {
+ out << "(" << *i << ", " << *(i->pair()) << "): ";
+ out << i->cycle() << std::endl;
+ }
+ out << std::endl << std::endl;
+
+ return out;
+}
+
+
+/* Filtration Protected */
+/// Transposes simplices at i and i+1. Returns true if the pairing switched.
+template<class S, class FS, class V>
+bool
+Filtration<S,FS,V>::
+transpose_simplices(Index i, bool maintain_lazy)
+{
+ AssertMsg(is_paired(), "Pairing must be computed before transpositions");
+ Count("SimplexTransposition");
+
+ Index i_prev = i++;
+
+ if (i_prev->dimension() != i->dimension())
+ {
+ swap(i_prev, i);
+ Dout(dc::transpositions, "Different dimension");
+ Count("Case DiffDim");
+ return false;
+ }
+
+ bool si = i_prev->sign(), sii = i->sign();
+ if (si && sii)
+ {
+ Dout(dc::transpositions, "Trail prev: " << i_prev->trail());
+
+ // Case 1
+ TrailIterator i_in_i_prev = std::find(i_prev->trail().begin(), i_prev->trail().end(), i);
+ if (i_in_i_prev != i_prev->trail().end())
+ {
+ Dout(dc::transpositions, "Case 1, U[i,i+1] = 1");
+ i_prev->trail().erase(i_in_i_prev);
+ }
+
+ Index k = i_prev->pair();
+ Index l = i->pair();
+
+ // Explicit treatment of unpaired simplex
+ if (l == i)
+ {
+ swap(i_prev, i);
+ Dout(dc::transpositions, "Case 1.2 --- unpaired");
+ Dout(dc::transpositions, *i_prev);
+ Count("Case 1.2");
+ return false;
+ } else if (k == i_prev)
+ {
+ if (std::find(l->cycle().begin(), l->cycle().end(), i_prev) == l->cycle().end())
+ {
+ // Case 1.2
+ swap(i_prev, i);
+ Dout(dc::transpositions, "Case 1.2 --- unpaired");
+ Dout(dc::transpositions, *i_prev);
+ Count("Case 1.2");
+ return false;
+ } else
+ {
+ // Case 1.1.2 --- special version (plain swap, but pairing switches)
+ swap(i_prev, i);
+ pairing_switch(i_prev, i);
+ Dout(dc::transpositions, "Case 1.1.2 --- unpaired");
+ Dout(dc::transpositions, *i_prev);
+ Count("Case 1.1.2");
+ return true;
+ }
+ }
+
+ Dout(dc::transpositions, "l cycle: " << l->cycle());
+ if (std::find(l->cycle().begin(), l->cycle().end(), i_prev) == l->cycle().end())
+ {
+ // Case 1.2
+ if (maintain_lazy)
+ {
+ TrailIterator k_in_l = std::find(l->trail().begin(), l->trail().end(), k);
+ if (k_in_l != l->trail().end())
+ {
+ l->trail().add(k->trail(), Filtration::get_consistency_cmp()); // Add row k to l
+ k->cycle().add(l->cycle(), Filtration::get_consistency_cmp()); // Add column l to k
+ }
+ }
+ swap(i_prev, i);
+ Dout(dc::transpositions, "Case 1.2");
+ Count("Case 1.2");
+ return false;
+ } else
+ {
+ // Case 1.1
+ if (trails_cmp(k,l))
+ {
+ // Case 1.1.1
+ swap(i_prev, i);
+ l->cycle().add(k->cycle(), Filtration::get_consistency_cmp()); // Add column k to l
+ k->trail().add(l->trail(), Filtration::get_consistency_cmp()); // Add row l to k
+ Dout(dc::transpositions, "Case 1.1.1");
+ Count("Case 1.1.1");
+ return false;
+ } else
+ {
+ // Case 1.1.2
+ swap(i_prev, i);
+ k->cycle().add(l->cycle(), Filtration::get_consistency_cmp()); // Add column l to k
+ l->trail().add(k->trail(), Filtration::get_consistency_cmp()); // Add row k to l
+ pairing_switch(i_prev, i);
+ Dout(dc::transpositions, "Case 1.1.2");
+ Count("Case 1.1.2");
+ return true;
+ }
+ }
+ } else if (!si && !sii)
+ {
+ // Case 2
+ if (std::find(i_prev->trail().begin(), i_prev->trail().end(), i) == i_prev->trail().end())
+ {
+ // Case 2.2
+ swap(i_prev, i);
+ Dout(dc::transpositions, "Case 2.2");
+ Count("Case 2.2");
+ return false;
+ } else
+ {
+ // Case 2.1
+ Index low_i = i_prev->pair();
+ Index low_ii = i->pair();
+ i_prev->trail().add(i->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
+ i->cycle().add(i_prev->cycle(), Filtration::get_consistency_cmp()); // Add column i_prev to i
+ swap(i_prev, i);
+ if (Filtration::get_trails_cmp()(low_ii, low_i))
+ {
+ // Case 2.1.2
+ i_prev->cycle().add(i->cycle(), Filtration::get_consistency_cmp()); // Add column i to i_prev (after transposition)
+ i->trail().add(i_prev->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
+ pairing_switch(i_prev, i);
+ Dout(dc::transpositions, "Case 2.1.2");
+ Count("Case 2.1.2");
+ return true;
+ }
+
+ // Case 2.1.1
+ Dout(dc::transpositions, "Case 2.1.1");
+ Count("Case 2.1.1");
+ return false;
+ }
+ } else if (!si && sii)
+ {
+ // Case 3
+ if (std::find(i_prev->trail().begin(), i_prev->trail().end(), i) == i_prev->trail().end())
+ {
+ // Case 3.2
+ swap(i_prev, i);
+ Dout(dc::transpositions, "Case 3.2");
+ Count("Case 3.2");
+ return false;
+ } else
+ {
+ // Case 3.1
+ i_prev->trail().add(i->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
+ i->cycle().add(i_prev->cycle(), Filtration::get_consistency_cmp()); // Add column i_prev to i
+ swap(i_prev, i);
+ i_prev->cycle().add(i->cycle(), Filtration::get_consistency_cmp()); // Add column i_prev to i (after transposition)
+ i->trail().add(i_prev->trail(), Filtration::get_consistency_cmp()); // Add row i to i_prev
+ pairing_switch(i_prev, i);
+ Dout(dc::transpositions, "Case 3.1");
+ Count("Case 3.1");
+ return true;
+ }
+ } else if (si && !sii)
+ {
+ // Case 4
+ TrailIterator i_in_i_prev = std::find(i_prev->trail().begin(), i_prev->trail().end(), i);
+ if (i_in_i_prev != i_prev->trail().end())
+ {
+ Dout(dc::transpositions, "Case 4, U[i,i+1] = 1");
+ i_prev->trail().erase(i_in_i_prev);
+ }
+ swap(i_prev, i);
+ Dout(dc::transpositions, "Case 4");
+ Count("Case 4");
+ return false;
+ }
+
+ return false; // to avoid compiler complaints, should never reach this point
+}
+
+
+/* Filtration Private */
+template<class S, class FS, class V>
+void
+Filtration<S, FS, V>::
+init_cycle_trail(Index j)
+{
+ typename Simplex::Cycle bdry = j->boundary();
+
+ for (typename Simplex::Cycle::const_iterator cur = bdry.begin(); cur != bdry.end(); ++cur)
+ {
+ Dout(dc::filtration, "Appending in init_cycle_trail(): " << *cur);
+ AssertMsg(get_index(*cur) != end(), "Non-existent simplex in the cycle");
+ j->cycle().append(get_index(*cur), get_consistency_cmp());
+ }
+ j->trail().append(j, get_consistency_cmp());
+ j->set_pair(j);
+}
+
+/// Update the pairing, so that whoever was paired with i is now paired with j and vice versa.
+template<class S, class FS, class V>
+void
+Filtration<S,FS,V>::
+pairing_switch(Index i, Index j)
+{
+ Index i_pair = i->pair();
+ Index j_pair = j->pair();
+
+ if (i_pair == i)
+ j->set_pair(j);
+ else
+ {
+ j->set_pair(i_pair);
+ i_pair->set_pair(j);
+ }
+
+ if (j_pair == j)
+ i->set_pair(i);
+ else
+ {
+ i->set_pair(j_pair);
+ j_pair->set_pair(i);
+ }
+}
+
+/* Serialization */
+template<class S, class FS, class V>
+template<class Archive>
+void
+Filtration<S, FS, V>::
+save(Archive& ar, version_type ) const
+{
+ ar << BOOST_SERIALIZATION_NVP(paired);
+ ar << BOOST_SERIALIZATION_NVP(cycles_cmp);
+ ar << BOOST_SERIALIZATION_NVP(trails_cmp);
+ ar << BOOST_SERIALIZATION_NVP(consistency_cmp);
+
+ SizeType sz = size();
+ ar << make_nvp("size", sz);
+ Dout(dc::filtration, "Size: " << sz);
+
+ /* Record integer indices */
+ IndexIntMap index_map; SizeType i = 0;
+ for (const_Index cur = begin(); cur != end(); ++cur)
+ { index_map[cur] = i++; }
+
+ /* Save the simplices */
+ int count = 0;
+ for (const_Index cur = begin(); cur != end(); ++cur)
+ {
+ count++;
+ // FIXME
+ //FiltrationSimplexSerialization simplex = FiltrationSimplexSerialization(*cur, index_map);
+ //ar << make_nvp("FiltrationSimplex", simplex);
+ }
+ Dout(dc::filtration, count << " simplices serialized");
+}
+
+template<class S, class FS, class V>
+template<class Archive>
+void
+Filtration<S, FS, V>::
+load(Archive& ar, version_type )
+{
+ Dout(dc::filtration, "Starting to read filtration");
+ ar >> BOOST_SERIALIZATION_NVP(paired);
+ ar >> BOOST_SERIALIZATION_NVP(cycles_cmp);
+ ar >> BOOST_SERIALIZATION_NVP(trails_cmp);
+ ar >> BOOST_SERIALIZATION_NVP(consistency_cmp);
+ Dout(dc::filtration, "In Filtration: first block read");
+
+ SizeType sz;
+ ar >> make_nvp("size", sz);
+ Dout(dc::filtration, "In Filtration: size read " << sz);
+
+ IndexVector index_vector(sz);
+ for (SizeType i = 0; i < sz; ++i)
+ {
+ index_vector[i] = append(Simplex());
+ }
+
+ int count = 0;
+ for (SizeType i = 0; i < sz; ++i)
+ {
+ // FIXME
+ //FiltrationSimplexSerialization simplex;
+ //ar >> make_nvp("FiltrationSimplex", simplex);
+ count++;
+ Dout(dc::filtration, "In Filtration: simplex read (" << count << ")");
+ //simplex.set_filtration_simplex(*index_vector[i], index_vector);
+ }
+ Dout(dc::filtration, "In Filtration: simplices read");
+}
+
+template<class S, class FS, class V>
+std::ostream&
+operator<<(std::ostream& out, const Filtration<S, FS, V>& f)
+{ return f.operator<<(out); }
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/filtrationcontainer.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,45 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2006
+ */
+
+#ifndef __FILTRATIONCONTAINER_H__
+#define __FILTRATIONCONTAINER_H__
+
+#include "utilities/consistencylist.h"
+#include "cycle.h"
+
+/**
+ * FiltrationContainer class. Serves as a parent of Filtration that
+ * describes the container functionality. Used by FiltrationSimplex
+ * to get Cycle representation.
+ */
+template<class FltrSmplx>
+class FiltrationContainer: public ConsistencyList<FltrSmplx>
+{
+ public:
+ typedef FltrSmplx FiltrationSimplex;
+ typedef ConsistencyList<FiltrationSimplex> ConsistencyList;
+
+ /// \name Cycles and Trails
+ /// @{
+ /// Index is and therfore acts like an iterator. The name is preserved for historical reasons.
+ typedef typename ConsistencyList::iterator Index;
+ /// const_Index is a const_iterator
+ typedef typename ConsistencyList::const_iterator const_Index;
+ /// @}
+
+ /// \name Cycles and Trails
+ /// @{
+ typedef typename ConsistencyList::GreaterThanComparison CyclesComparator;
+ typedef typename ConsistencyList::LessThanComparison TrailsComparator;
+ typedef typename ConsistencyList::ConsistencyComparison ConsistencyComparator;
+ typedef ::Cycle<Index, CyclesComparator, ConsistencyComparator> Cycle;
+ typedef ::Cycle<Index, TrailsComparator, ConsistencyComparator> Trail;
+ /// @}
+
+ template<class U>
+ struct rebind { typedef FiltrationContainer<U> other; };
+};
+
+#endif // __FILTRATIONCONTAINER_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/filtrationsimplex.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,89 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2006
+ */
+
+#ifndef __FILTRATIONSIMPLEX_H__
+#define __FILTRATIONSIMPLEX_H__
+
+#include "utilities/sys.h"
+#include "utilities/debug.h"
+
+#include "filtrationcontainer.h"
+#include "vineyard.h"
+#include "utilities/types.h"
+
+#include <list>
+
+#if 0
+#include <boost/serialization/access.hpp>
+#include <boost/serialization/nvp.hpp>
+#include <boost/serialization/list.hpp>
+#endif
+
+/**
+ * Evaluator is a base class for the structures that are able to return a value
+ * given a simplex.
+ */
+template<class Smplx>
+class Evaluator
+{
+ public:
+ typedef Smplx Simplex;
+
+ virtual RealType time() { return 0; }
+ virtual RealType value(const Simplex& s) { return 0; }
+};
+
+/**
+ * FiltrationSimplex stores information needed for the RU-decomposition:
+ * cycle (column of R), trail (row of U), and pair.
+ */
+template<class Smplx>
+class FiltrationSimplex: public Smplx
+{
+ public:
+ typedef Smplx Simplex;
+ typedef FiltrationSimplex<Simplex> Self;
+ typedef FiltrationContainer<Self> Container;
+ typedef Simplex Parent;
+
+ typedef Vine<Simplex> Vine;
+ typedef typename Container::Cycle Cycle;
+ typedef typename Container::Trail Trail;
+ typedef typename Container::Index Index;
+
+ typedef Evaluator<Simplex> Evaluator;
+
+ FiltrationSimplex(const Simplex& s):
+ Simplex(s), vine_(0) {}
+
+
+ /// \name Core functionality
+ /// @{
+ void set_pair(Index pair) { pair_ = pair; }
+ bool sign() const { return cycles_column.empty(); }
+ bool is_paired() const { return pair() != pair()->pair(); }
+ void set_vine(Vine* v) { vine_ = v; }
+ using Parent::dimension;
+ /// @}
+
+
+ /// \name Accessors
+ /// @{
+ Cycle& cycle() { return cycles_column; }
+ Trail& trail() { return trails_row; }
+ const Cycle& cycle() const { return cycles_column; }
+ const Trail& trail() const { return trails_row; }
+ Index pair() const { return pair_; }
+ Vine* vine() const { return vine_; }
+ /// @}
+
+ private:
+ Cycle cycles_column;
+ Trail trails_row;
+ Index pair_;
+ Vine* vine_;
+};
+
+#endif // __FILTRATIONSIMPLEX_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/lowerstarfiltration.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,114 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2005 -- 2006
+ */
+
+#ifndef __LOWERSTARFILTRATION_H__
+#define __LOWERSTARFILTRATION_H__
+
+#include "utilities/sys.h"
+#include "utilities/debug.h"
+
+#include "filtration.h"
+#include "simplex.h"
+#include "utilities/consistencylist.h"
+#include <boost/utility.hpp>
+#include <list>
+#include "utilities/types.h"
+
+#include <boost/serialization/access.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/serialization/map.hpp>
+#include <boost/serialization/base_object.hpp>
+#include <boost/serialization/nvp.hpp>
+
+
+template<class VI,
+ class Smplx = SimplexWithAttachment<VI>,
+ class FltrSmplx = FiltrationSimplex<Smplx>,
+ class Vnrd = Vineyard<FltrSmplx> >
+class LowerStarFiltration: public Filtration<Smplx, FltrSmplx, Vnrd>
+{
+ public:
+ // Treat VertexIndex as an iterator
+ typedef VI VertexIndex;
+ typedef Smplx Simplex;
+ typedef Filtration<Simplex> Parent;
+ typedef typename Parent::Vineyard Vineyard;
+
+ typedef typename Parent::Index Index;
+ typedef typename Parent::const_Index const_Index;
+ typedef typename Parent::Cycle Cycle;
+ typedef typename Parent::Trail Trail;
+ typedef typename Simplex::Cycle SimplexBoundaryCycle;
+
+ struct VertexDescriptor;
+ typedef ConsistencyList<VertexDescriptor> VertexOrder;
+ typedef typename VertexOrder::iterator VertexOrderIndex;
+ typedef typename VertexOrder::const_iterator const_VertexOrderIndex;
+ typedef typename VertexOrder::LessThanComparison VertexOrderComparison;
+ struct SimplexAttachmentComparison;
+
+ public:
+ template<class VertexCmp>
+ LowerStarFiltration(VertexIndex begin, VertexIndex end, const VertexCmp& cmp, Vineyard* vineyard);
+
+ using Parent::size;
+ using Parent::begin;
+ using Parent::end;
+ VertexIndex num_vertices() const { return vertex_order.size(); }
+ const VertexOrderComparison&
+ get_vertex_cmp() const { return vertex_cmp; }
+
+ Index append(const Simplex& s);
+ bool transpose_vertices(const VertexOrderIndex& voi);
+
+ protected:
+ /// Hint function: if unsure, should return true
+ virtual bool neighbors(VertexIndex v1, VertexIndex v2) const { return true; }
+
+ private:
+ bool transpose(Index i);
+ void assert_pairing(Index i);
+
+ private:
+ VertexOrder vertex_order;
+ VertexOrderComparison vertex_cmp;
+
+ /* Serialization */
+ protected:
+ LowerStarFiltration() {}
+
+ private:
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void save(Archive& ar, version_type ) const { ar << BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent); }
+
+ template<class Archive>
+ void load(Archive& ar, version_type );
+
+ BOOST_SERIALIZATION_SPLIT_MEMBER()
+};
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+struct LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::VertexDescriptor
+{
+ VertexDescriptor(VertexIndex vi, Index si):
+ vertex_index(vi), simplex_index(si)
+ {}
+
+ VertexIndex vertex_index;
+ Index simplex_index;
+};
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+struct LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::SimplexAttachmentComparison
+{
+ bool operator()(const Simplex& first, const Simplex& second) const;
+ VertexOrderComparison vertex_cmp;
+};
+
+#include "lowerstarfiltration.hpp"
+
+#endif // __LOWERSTARFILTRATION_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/lowerstarfiltration.hpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,217 @@
+/* Implementations */
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+template<class VertexCmp>
+LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
+LowerStarFiltration(VertexIndex begin, VertexIndex end, const VertexCmp& cmp, Vineyard* vineyard):
+ Parent(vineyard)
+{
+ // Record VertexIndexes in a temporary list
+ typedef std::list<VertexIndex> VertexIndexList;
+ VertexIndexList tmp_list;
+ while (begin != end)
+ tmp_list.push_back(begin++);
+
+ // Sort the temporary list
+ tmp_list.sort(cmp);
+
+ // Record vertex order
+ for(typename VertexIndexList::const_iterator cur = tmp_list.begin(); cur != tmp_list.end(); ++cur)
+ (*cur)->set_order(vertex_order.push_back(VertexDescriptor(*cur, Parent::append(Simplex(*cur)))));
+}
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+typename LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::Index
+LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
+append(const Simplex& s)
+{
+ AssertMsg(s.dimension() != 0, "All vertices must have been inserted in the constructor");
+
+ // Find the highest vertex
+ typename Simplex::VertexContainer::const_iterator cur = s.vertices().begin(), max = cur++;
+ for (; cur != s.vertices().end(); ++cur)
+ if (!vertex_cmp((*cur)->get_order(), (*max)->get_order()))
+ max = cur;
+
+ Index ms = (*max)->get_order()->simplex_index; Index prior;
+ do { prior = ms++; } while (ms->dimension() <= s.dimension() && ms != Parent::end() && ms->get_attachment() == *max);
+
+ Index i = Parent::insert(prior, s);
+ i->set_attachment(*max);
+
+ return i;
+}
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+bool
+LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::SimplexAttachmentComparison::
+operator()(const Simplex& first, const Simplex& second) const
+{
+ int cmp = vertex_cmp.compare(first.get_attachment()->get_order(), second.get_attachment()->get_order());
+ if (cmp == 0)
+ return first.dimension() < second.dimension();
+ else
+ return cmp == -1;
+}
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+bool
+LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
+transpose_vertices(const VertexOrderIndex& order)
+{
+ Count("VertexTransposition");
+
+#if COUNTERS
+ if ((counters.lookup("VertexTransposition") % 1000000) == 0)
+ {
+ Dout(dc::lsfiltration, "Vertex transpositions: " << counters.lookup("VertexTransposition"));
+ Dout(dc::lsfiltration, "Simplex transpositions: " << counters.lookup("SimplexTransposition"));
+ Dout(dc::lsfiltration, "Attachment changed: " << counters.lookup("ChangedAttachment"));
+ Dout(dc::lsfiltration, "Regular disconnected: " << counters.lookup("RegularDisconnected"));
+ Dout(dc::lsfiltration, "Pairing Changed: " << counters.lookup("ChangedPairing"));
+ Dout(dc::lsfiltration, "------------------------");
+ }
+#endif // COUNTERS
+
+ Dout(dc::lsfiltration, "Transposing vertices (" << order->vertex_index << ", "
+ << boost::next(order)->vertex_index << ")");
+
+ Index i = order->simplex_index;
+ Index i_prev = boost::prior(i);
+ Index i_next = boost::next(order)->simplex_index;
+ Index i_next_prev = boost::prior(i_next); // transpositions are done in terms of the first index in the pair
+ Index j = boost::next(i_next);
+
+ const VertexIndex& v_i = order->vertex_index;
+ const VertexIndex& v_i_next = boost::next(order)->vertex_index;
+ bool nbghrs = neighbors(v_i, v_i_next);
+
+ bool result = false;
+
+ // First, move the vertex --- this can be sped up if we devise special "vertex transpose" operation
+ while (i_next_prev != i_prev)
+ {
+ result |= transpose(i_next_prev);
+ i_next_prev = boost::prior(i_next);
+ }
+ Dout(dc::lsfiltration, "Done moving the vertex");
+
+ // Second, move the simplices attached to it
+ Dout(dc::lsfiltration, "Moving attached simplices");
+ while (j != Parent::end() && j->get_attachment() == v_i_next)
+ {
+ Dout(dc::lsfiltration, " Considering " << *j);
+ if (nbghrs && j->contains(v_i)) // short circuit
+ {
+ Count("ChangedAttachment");
+ Dout(dc::lsfiltration, " Attachment changed for " << *j);
+ j->set_attachment(v_i);
+ ++j;
+ continue;
+ }
+
+ Index j_prev = j; ++j;
+ while ((--j_prev)->get_attachment() != v_i_next) // i.e., until we have reached v_i_next
+ // (and the simplices that follow it) again
+ {
+ Dout(dc::lsfiltration, " Moving: " << *j_prev << ", " << *boost::next(j_prev));
+ AssertMsg(j_prev->get_attachment() == v_i, "Simplex preceding the one being moved must be attached to v_i");
+ result |= transpose(j_prev);
+ --j_prev;
+ }
+ }
+ Dout(dc::lsfiltration, "Done moving attached simplices");
+ vertex_order.swap(order, boost::next(order));
+
+ return result;
+}
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+bool
+LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
+transpose(Index i)
+{
+ Index j = boost::next(i);
+
+ Dout(dc::lsfiltration, " Transposing (" << *i << ", " << *(i->pair()) << ") and ("
+ << *j << ", " << *(j->pair()) << ")");
+
+ assert_pairing(i);
+ assert_pairing(j);
+
+ bool res = Parent::transpose(i, false);
+ Dout(dc::lsfiltration, " " << *j << ": " << *(j->pair()) << ", " << *i << ": " << *(i->pair()));
+
+ assert_pairing(j);
+ assert_pairing(i);
+
+ return res;
+}
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+void
+LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
+assert_pairing(Index i)
+{
+#ifndef NDEBUG
+ AssertMsg(i != Parent::end(), "Cannot assert pairing of end()");
+ if (!i->sign())
+ {
+ if (i->pair() != i->cycle().top(Parent::get_cycles_cmp()))
+ {
+ Dout(dc::lsfiltration, "i (negative): " << *i);
+ Dout(dc::lsfiltration, "pair(i): " << *(i->pair()));
+ Dout(dc::lsfiltration, "i->cycle().top(): " << *(i->cycle().top(Parent::get_cycles_cmp())));
+ DoutFatal(dc::fatal, "Pairing not matching the matrix at " << *i);
+ }
+ } else
+ {
+ if (i->pair() != i)
+ {
+ if (i->pair()->cycle().top(Parent::get_cycles_cmp()) != i)
+ {
+ Dout(dc::lsfiltration, "i (positive): " << *i);
+ Dout(dc::lsfiltration, "pair(i): " << *(i->pair()));
+ Dout(dc::lsfiltration, "pair(i)->cycle(): " << i->pair()->cycle());
+ Dout(dc::lsfiltration, "pair->cycle().top(): " << *(i->pair()->cycle().top(Parent::get_cycles_cmp())));
+ DoutFatal(dc::fatal, "Pairing not matching the matrix at " << *(i->pair()));
+ }
+ }
+ }
+#endif
+}
+
+
+template<class VI, class Smplx, class FltrSmplx, class Vnrd>
+template<class Archive>
+void
+LowerStarFiltration<VI,Smplx,FltrSmplx,Vnrd>::
+load(Archive& ar, version_type )
+{
+/*
+ ar >> BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
+
+ // Count the number of vertices
+ VertexIndex num_vertices = 0;
+ for (Index cur = begin(); cur != end(); ++cur)
+ if (dimension(cur) == 0)
+ num_vertices++;
+
+ // Second pass to record vertex_order
+ vertex_order.resize(num_vertices);
+ inverse_vertex_order.resize(num_vertices);
+ num_vertices = 0;
+ for (Index cur = begin(); cur != end(); ++cur)
+ {
+ if (dimension(cur) == 0)
+ {
+ vertex_order[num_vertices].index = cur;
+ vertex_order[num_vertices].vertex_index = *(cur->get_vertices().begin());
+ inverse_vertex_order[vertex_order[num_vertices].vertex_index] = num_vertices;
+ ++num_vertices;
+ }
+ }
+*/
+}
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/simplex.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,170 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2005 -- 2006
+ */
+
+#ifndef __SIMPLEX_H__
+#define __SIMPLEX_H__
+
+#include "utilities/sys.h"
+#include "utilities/debug.h"
+
+#include <set>
+#include <list>
+#include <iostream>
+
+#include "utilities/types.h"
+
+#include <boost/serialization/access.hpp>
+
+
+/**
+ * SimplexWithVertices is a basic simplex class. It stores vertices of a given type,
+ * and knows how to compute its own boundary. It should probably be used as a base
+ * class for any explicit simplex representation.
+ */
+template<class V>
+class SimplexWithVertices
+{
+ public:
+ typedef V Vertex;
+ typedef SimplexWithVertices<Vertex> Self;
+
+ typedef std::set<Vertex> VertexContainer;
+ typedef std::list<Self> Cycle;
+
+ /// \name Constructors
+ /// @{
+ SimplexWithVertices() {}
+ SimplexWithVertices(const Self& s):
+ vertices_(s.vertices_) {}
+ template<class Iterator>
+ SimplexWithVertices(Iterator bg, Iterator end):
+ vertices_(bg, end) {}
+ SimplexWithVertices(const VertexContainer& v):
+ vertices_(v) {}
+ SimplexWithVertices(Vertex v):
+ vertices_() { vertices_.insert(v); }
+ /// @}
+
+ /// \name Core
+ /// @{
+ Cycle boundary() const;
+ Dimension dimension() const { return vertices_.size()-1; }
+ /// @}
+
+ /// \name Vertex manipulation
+ /// @{
+ bool contains(const Vertex& v) const { return (vertices_.find(v) != vertices_.end()); }
+ const VertexContainer& vertices() const { return vertices_; }
+ void add(const Vertex& v) { vertices_.insert(v); }
+ /// @}
+
+ /// \name Assignment and comparison
+ /// Gives an ordering on simplices (for example, so that simplices can be used as keys for std::map)
+ /// @{
+ const Self& operator=(const Self& s) { vertices_ = s.vertices_; return *this; }
+ bool operator==(const Self& s) const { return vertices_ == s.vertices_; }
+ bool operator<(const Self& s) const { return vertices_ < s.vertices_; }
+ /// @}
+
+ std::ostream& operator<<(std::ostream& out) const;
+
+ private:
+ VertexContainer vertices_;
+
+ private:
+ /* Serialization */
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar, version_type );
+};
+
+/**
+ * SimplexWithValue explicitly adds a RealType value to the SimplexWithVertices.
+ */
+template<class Vert>
+class SimplexWithValue: public SimplexWithVertices<Vert>
+{
+ public:
+ typedef Vert Vertex;
+ typedef RealType Value;
+ typedef SimplexWithValue<Vertex> Self;
+ typedef SimplexWithVertices<Vertex> Parent;
+
+ typedef typename Parent::VertexContainer VertexContainer;
+
+ /// \name Constructors
+ /// @{
+ SimplexWithValue(Value value = 0): val(value) {}
+ SimplexWithValue(const Self& s):
+ Parent(s), val(s.val) {}
+ SimplexWithValue(const Parent& s, Value value = 0):
+ Parent(s), val(value) {}
+ template<class Iterator>
+ SimplexWithValue(Iterator bg, Iterator end, Value value = 0):
+ Parent(bg, end), val(value) {}
+ SimplexWithValue(const VertexContainer& v, Value value = 0):
+ Parent(v), val(value) {}
+ /// @}
+
+ /// \name Core
+ /// @{
+ void set_value(Value value) { val = value; }
+ Value get_value() const { return val; }
+ /// @}
+
+ const Self& operator=(const Self& s);
+ std::ostream& operator<<(std::ostream& out) const;
+
+ private:
+ Value val;
+
+ /* Serialization */
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar, version_type );
+};
+
+/**
+ * SimplexWithAttachment stores the vertex to which the simplex is attached (meant for lower-star filtrations)
+ */
+template<typename V>
+class SimplexWithAttachment: public SimplexWithVertices<V>
+{
+ public:
+ typedef V VertexIndex;
+ typedef SimplexWithVertices<VertexIndex> Parent;
+
+ /// \name Constructors
+ /// @{
+ SimplexWithAttachment():
+ attachment(VertexIndex()) {}
+ template<class Iterator>
+ SimplexWithAttachment(Iterator bg, Iterator end):
+ Parent(bg, end) {}
+ SimplexWithAttachment(const Parent& s):
+ Parent(s) {}
+ SimplexWithAttachment(VertexIndex vi):
+ Parent(vi), attachment(vi) {}
+ /// @}
+
+ void set_attachment(VertexIndex v) { attachment = v; }
+ VertexIndex get_attachment() const { return attachment; }
+
+ private:
+ VertexIndex attachment;
+
+ private:
+ // Serialization
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar, version_type );
+};
+
+#include "simplex.hpp"
+
+#endif // __SIMPLEX_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/simplex.hpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,94 @@
+#include <boost/serialization/base_object.hpp>
+#include <boost/serialization/set.hpp>
+#include <boost/serialization/nvp.hpp>
+
+
+/* Implementations */
+
+/* SimplexWithVertices */
+template<class V>
+typename SimplexWithVertices<V>::Cycle
+SimplexWithVertices<V>::
+boundary() const
+{
+ Cycle bdry;
+ if (dimension() == 0) return bdry;
+
+ for (typename VertexContainer::const_iterator cur = vertices_.begin(); cur != vertices_.end(); ++cur)
+ {
+ bdry.push_back(*this);
+ Self& s = bdry.back();
+ s.vertices_.erase(*cur);
+ }
+
+ return bdry;
+}
+
+template<class V>
+std::ostream&
+SimplexWithVertices<V>::
+operator<<(std::ostream& out) const
+{
+ for (typename VertexContainer::const_iterator cur = vertices_.begin(); cur != vertices_.end(); ++cur)
+ out << *cur << ' ';
+
+ return out;
+}
+
+template<class V>
+template<class Archive>
+void
+SimplexWithVertices<V>::
+serialize(Archive& ar, version_type )
+{ ar & BOOST_SERIALIZATION_NVP(vertices_); }
+
+template<class V>
+std::ostream& operator<<(std::ostream& out, const SimplexWithVertices<V>& s)
+{ return s.operator<<(out); }
+
+
+/* SimplexWithValue */
+template<class V>
+std::ostream&
+SimplexWithValue<V>::
+operator<<(std::ostream& out) const
+{
+ Parent::operator<<(out);
+ out << "(val = " << val << ")";
+ return out;
+}
+
+template<class V>
+const typename SimplexWithValue<V>::Self&
+SimplexWithValue<V>::
+operator=(const Self& s)
+{
+ Parent::operator=(s);
+ val = s.val;
+ return *this;
+}
+
+template<class V>
+template<class Archive>
+void
+SimplexWithValue<V>::
+serialize(Archive& ar, version_type )
+{
+ ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
+ ar & BOOST_SERIALIZATION_NVP(val);
+}
+
+template<typename V>
+template<class Archive>
+void
+SimplexWithAttachment<V>::
+serialize(Archive& ar, version_type )
+{
+ ar & BOOST_SERIALIZATION_BASE_OBJECT_NVP(Parent);
+ ar & BOOST_SERIALIZATION_NVP(attachment);
+}
+
+
+template<class V>
+std::ostream& operator<<(std::ostream& out, const SimplexWithValue<V>& s)
+{ return s.operator<<(out); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/vineyard.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,145 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2005 -- 2006
+ */
+
+#ifndef __VINEYARD_H__
+#define __VINEYARD_H__
+
+#include "utilities/types.h"
+#include <list>
+#include <string>
+
+#include <boost/serialization/access.hpp>
+#include <boost/serialization/vector.hpp>
+#include <boost/serialization/nvp.hpp>
+#include <boost/serialization/list.hpp>
+#include <boost/serialization/is_abstract.hpp>
+
+
+template<class Smplx> class Knee;
+template<class Smplx> class Vine;
+
+/**
+ * Vineyard class. Keeps track of vines and knees. switched() is the key function called
+ * by filtration when pairing switches after a Filtration::transpose().
+ */
+template<class FltrSmplx>
+class Vineyard
+{
+ public:
+ typedef FltrSmplx FiltrationSimplex;
+ typedef typename FiltrationSimplex::Simplex Simplex;
+ typedef Vine<Simplex> Vine;
+ typedef Knee<Simplex> Knee;
+ typedef std::list<Vine> VineList;
+ typedef std::vector<VineList> VineListVector;
+ typedef typename FiltrationSimplex::Cycle Cycle;
+
+ typedef typename FiltrationSimplex::Index Index;
+ typedef typename FiltrationSimplex::Evaluator Evaluator;
+
+ public:
+ Vineyard(Evaluator* eval = 0):
+ evaluator(eval) {}
+
+ void start_vines(Index bg, Index end);
+ void switched(Index i, Index j);
+ void record_diagram(Index bg, Index end);
+
+ void set_evaluator(Evaluator* eval) { evaluator = eval; }
+
+ void save_edges(const std::string& filename) const;
+
+ protected:
+ typename Knee::SimplexList resolve_cycle(Index i) const;
+
+ private:
+ void record_knee(Index i);
+ void start_vine(Index i);
+
+ private:
+ VineListVector vines;
+ Evaluator* evaluator;
+};
+
+/**
+ * Knee class stores the knee in R^3 as well as the cycle that is associated with the Simplex starting from the Knee.
+ */
+template<class S>
+class Knee
+{
+ public:
+ typedef S Simplex;
+ typedef std::list<Simplex> SimplexList;
+
+ RealType birth;
+ RealType death;
+ RealType time;
+ SimplexList cycle;
+
+ // Default parameters for serialization
+ Knee(RealType b = 0, RealType d = 0, RealType t = 0):
+ birth(b), death(d), time(t)
+ {}
+ Knee(const Knee& other):
+ birth(other.birth), death(other.death), time(other.time)
+ {}
+
+ bool is_diagonal() const { return birth == death; }
+ bool is_infinite() const { return (death == Infinity) || (birth == Infinity); }
+ void set_cycle(const SimplexList& lst) { cycle = lst; }
+
+ std::ostream& operator<<(std::ostream& out) const { return out << "(" << birth << ", "
+ << death << ", "
+ << time << ")"; }
+
+ private:
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar, version_type );
+};
+
+template<class S>
+std::ostream& operator<<(std::ostream& out, const Knee<S>& k) { return k.operator<<(out); }
+
+/**
+ * Vine is a list of Knees
+ */
+template<class S>
+class Vine: public std::list<Knee<S> >
+{
+ public:
+ typedef S Simplex;
+ typedef Knee<Simplex> Knee;
+ typedef std::list<Knee> VineRepresentation;
+ typedef typename VineRepresentation::const_iterator const_knee_iterator;
+
+ Vine() {}
+ Vine(const Knee& k) { add(k); }
+
+ void add(RealType b, RealType d, RealType t) { push_back(Knee(b,d,t)); }
+ void add(const Knee& k) { push_back(k); }
+
+ using VineRepresentation::begin;
+ using VineRepresentation::end;
+ using VineRepresentation::front;
+ using VineRepresentation::back;
+ using VineRepresentation::size;
+ using VineRepresentation::empty;
+
+ protected:
+ using VineRepresentation::push_back;
+
+ private:
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar, version_type );
+};
+
+
+#include "vineyard.hpp"
+
+#endif // __VINEYARD_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/topology/vineyard.hpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,157 @@
+/* Implementations */
+
+#include <fstream>
+#include <sstream>
+
+template<class FS>
+void
+Vineyard<FS>::
+start_vines(Index bg, Index end)
+{
+ AssertMsg(evaluator != 0, "Cannot start vines with a null evaluator");
+ for (Index cur = bg; cur != end; ++cur)
+ {
+ if (!cur->sign()) continue;
+ Dimension dim = cur->dimension();
+
+ if (dim >= vines.size())
+ {
+ AssertMsg(dim == vines.size(), "New dimension has to be contiguous");
+ vines.push_back(std::list<Vine>());
+ }
+
+ start_vine(cur);
+ record_knee(cur);
+ }
+}
+
+template<class FS>
+void
+Vineyard<FS>::
+switched(Index i, Index j)
+{
+ Vine* i_vine = i->vine();
+ Vine* j_vine = j->vine();
+ i->set_vine(j_vine);
+ j->set_vine(i_vine);
+
+ // Since the pairing has already been updated, the following assertions should be true
+ AssertMsg(i->vine() == i->pair()->vine(), "i's vine must match the vine of its pair");
+ AssertMsg(j->vine() == j->pair()->vine(), "j's vine must match the vine of its pair");
+
+ if (!i->sign()) i = i->pair();
+ if (!j->sign()) j = j->pair();
+ record_knee(i);
+ record_knee(j);
+}
+
+template<class FS>
+void
+Vineyard<FS>::
+start_vine(Index i)
+{
+ Dout(dc::vineyard, "Starting new vine");
+ AssertMsg(i->sign(), "Can only start vines for positive simplices");
+
+ Dimension dim = i->dimension();
+ vines[dim].push_back(Vine());
+ i->set_vine(&vines[dim].back());
+ i->pair()->set_vine(i->vine());
+}
+
+/// Records the current diagram in the vineyard
+template<class FS>
+void
+Vineyard<FS>::
+record_diagram(Index bg, Index end)
+{
+ Dout(dc::vineyard, "Entered: record_diagram()");
+ AssertMsg(evaluator != 0, "Cannot record diagram with a null evaluator");
+
+ for (Index i = bg; i != end; ++i)
+ {
+ AssertMsg(i->vine() != 0, "Cannot process a null vine in record_diagram");
+ if (!i->sign()) continue;
+ record_knee(i);
+ }
+}
+
+
+template<class FS>
+void
+Vineyard<FS>::
+save_edges(const std::string& filename) const
+{
+ for (unsigned int i = 0; i < vines.size(); ++i)
+ {
+ std::ostringstream os; os << i;
+ std::string fn = filename + os.str() + ".edg";
+ std::ofstream out(fn.c_str());
+ for (typename VineList::const_iterator vi = vines[i].begin(); vi != vines[i].end(); ++vi)
+ for (typename Vine::const_iterator ki = vi->begin(), kiprev = ki++; ki != vi->end(); kiprev = ki++)
+ {
+ if (kiprev->is_infinite() || ki->is_infinite()) continue;
+ out << kiprev->birth << ' ' << kiprev->death << ' ' << kiprev->time << std::endl;
+ out << ki->birth << ' ' << ki->death << ' ' << ki->time << std::endl;
+ }
+ out.close();
+ }
+}
+
+/// Records a knee for the given simplex
+template<class FS>
+void
+Vineyard<FS>::
+record_knee(Index i)
+{
+ Dout(dc::vineyard, "Entered record_knee()");
+ AssertMsg(evaluator != 0, "Cannot record knee with a null evaluator");
+ AssertMsg(i->vine() != 0, "Cannot add a knee to a null vine");
+ AssertMsg(i->sign(), "record_knee() must be called on a positive simplex");
+
+ if (!i->is_paired())
+ i->vine()->add(evaluator->value(*i), Infinity, evaluator->time());
+ else
+ {
+ Dout(dc::vineyard, "Creating knee");
+ Knee k(evaluator->value(*i), evaluator->value(*(i->pair())), evaluator->time());
+ Dout(dc::vineyard, "Knee created: " << k);
+
+ if (!k.is_diagonal() || i->vine()->empty()) // non-diagonal k, or empty vine
+ {
+ Dout(dc::vineyard, "Extending a vine");
+ i->vine()->add(k);
+ }
+ else if (i->vine()->back().is_diagonal()) // last knee is diagonal
+ {
+ AssertMsg(i->vine()->size() == 1, "Only first knee may be diagonal for a live vine");
+ Dout(dc::vineyard, "Overwriting first diagonal knee");
+ i->vine()->back() = k;
+ } else // finish this vine
+ {
+ Dout(dc::vineyard, "Finishing a vine");
+ i->vine()->add(k);
+ start_vine(i);
+ i->vine()->add(k);
+ }
+ }
+
+ i->vine()->back().set_cycle(resolve_cycle(i));
+ Dout(dc::vineyard, "Leaving record_knee()");
+}
+
+template<class FS>
+typename Vineyard<FS>::Knee::SimplexList
+Vineyard<FS>::
+resolve_cycle(Index i) const
+{
+ Dout(dc::vineyard, "Entered resolve_cycle");
+ const Cycle& cycle = i->cycle();
+
+ // Resolve simplices
+ typename Knee::SimplexList lst;
+ for (typename Cycle::const_iterator cur = cycle.begin(); cur != cycle.end(); ++cur)
+ lst.push_back(**cur);
+
+ return lst;
+}
--- a/include/types.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,18 +0,0 @@
-#ifndef __TYPES_H__
-#define __TYPES_H__
-
-#include <limits>
-
-/* Types */
-typedef bool Sign;
-typedef short int Dimension;
-const Sign POS = true;
-const Sign NEG = false;
-typedef double RealType;
-typedef unsigned int SizeType;
-
-static RealType Infinity = std::numeric_limits<RealType>::infinity();
-
-typedef const unsigned int& version_type;
-
-#endif // __TYPES_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/circular_list.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,259 @@
+/**
+ * Singly-linked circular list implementation by Donovan Rebbechi <elflord@pegasus.rutgers.edu>.
+ * Tiny modifications by DM to make ISO C++ compliant (i.e., so that the compiler stops complaining),
+ * added size(), and boost serialization
+ */
+
+#ifndef __CIRCULAR_LIST_H__
+#define __CIRCULAR_LIST_H__
+
+#include <iterator>
+
+#include <boost/serialization/access.hpp>
+#include <boost/serialization/split_member.hpp>
+#include <boost/serialization/nvp.hpp>
+#include <boost/serialization/binary_object.hpp>
+
+#include "types.h"
+
+
+template <class T>
+class List
+{
+ struct Node
+ {
+ Node(const T& x,Node* y = 0):m_data(x),m_next(y){}
+ T m_data;
+ Node* m_next;
+
+ private:
+ // Serialization
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar, version_type )
+ {
+ ar & make_nvp("data", m_data);
+ ar & make_nvp("next", m_next);
+ }
+ };
+
+ Node* m_node;
+ size_t sz;
+
+ private:
+ // Serialization
+ friend class boost::serialization::access;
+
+ template<class Archive>
+ void serialize(Archive& ar, version_type )
+ { ar & make_nvp("root", m_node); }
+
+public:
+ class const_iterator;
+
+ class iterator
+ : public std::iterator<std::forward_iterator_tag, T>
+ {
+ Node* m_rep;
+ public:
+ friend class List;
+ friend class const_iterator;
+ typedef T value_type;
+ typedef T& reference;
+ typedef T* pointer;
+ typedef int difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+
+ inline iterator(Node* x=0):m_rep(x){}
+ inline iterator(const iterator& x):m_rep(x.m_rep) {}
+ inline iterator(const const_iterator& x):m_rep(const_cast<Node*>(x.m_rep)) {} // not very safe
+ inline iterator& operator=(const iterator& x)
+ {
+ m_rep=x.m_rep; return *this;
+ }
+ inline iterator& operator++()
+ {
+ m_rep = m_rep->m_next; return *this;
+ }
+ inline iterator operator++(int)
+ {
+ iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
+ }
+ inline reference operator*() const { return m_rep->m_next->m_data; }
+ inline pointer operator->() const { return m_rep->m_next; }
+ inline bool operator==(const iterator& x) const
+ {
+ return m_rep == x.m_rep;
+ }
+ inline bool operator!=(const iterator& x) const
+ {
+ return m_rep != x.m_rep;
+ }
+
+ };
+
+ class const_iterator
+ : public std::iterator<std::forward_iterator_tag, const T>
+ {
+ const Node* m_rep;
+ public:
+ friend class List;
+ friend class iterator;
+ typedef T value_type;
+ typedef T& reference;
+ typedef T* pointer;
+ typedef int difference_type;
+ typedef std::forward_iterator_tag iterator_category;
+ inline const_iterator(const Node* x=0):m_rep(x){}
+ inline const_iterator(const const_iterator& x):m_rep(x.m_rep) {}
+ inline const_iterator(const iterator& x):m_rep(x.m_rep){}
+ inline const_iterator& operator=(const const_iterator& x)
+ {
+ m_rep=x.m_rep; return *this;
+ }
+ inline const_iterator& operator=(const iterator& x)
+ {
+ m_rep=x.m_rep; return *this;
+ }
+ inline const_iterator& operator++()
+ {
+ m_rep = m_rep->m_next; return *this;
+ }
+ inline const_iterator operator++(int)
+ {
+ const_iterator tmp(*this); m_rep = m_rep->m_next; return tmp;
+ }
+ inline reference operator*() const { return m_rep->m_next->m_data; }
+ inline pointer operator->() const { return m_rep->m_next; }
+ inline bool operator==(const const_iterator& x) const
+ {
+ return m_rep == x.m_rep;
+ }
+ inline bool operator!=(const const_iterator& x) const
+ {
+ return m_rep != x.m_rep;
+ }
+ };
+
+ typedef T& reference;
+ typedef const T& const_reference;
+ typedef T* pointer;
+ typedef const T* const_pointer;
+
+ List() : m_node(new Node(T())), sz(0) { m_node->m_next = m_node; }
+
+ List(const List& L) : m_node(new Node(T())), sz(L.sz)
+ {
+ m_node->m_next=m_node;
+ for ( const_iterator i = L.begin(); i!= L.end(); ++i )
+ push_front(*i);
+ reverse();
+ }
+
+ void reverse()
+ {
+ if (empty())
+ return;
+ Node* new_m_node = m_node->m_next->m_next;
+ Node* p = m_node; Node* i = m_node->m_next; Node* n;
+ do
+ {
+ n = i->m_next;
+ i->m_next = p;
+ p = i; i = n;
+ }
+ while (p!=m_node);
+ m_node = new_m_node;
+ }
+
+ void swap(List& x)
+ {
+ std::swap(m_node, x.m_node);
+ std::swap(sz, x.sz);
+ }
+
+ List& operator=(const List& x)
+ {
+ List tmp(x);
+ swap(tmp);
+ return *this;
+ }
+
+ ~List() { clear(); delete m_node; }
+ void clear() { while (!empty()) pop_front(); sz = 0; }
+
+
+ inline size_t size() const { return sz; }
+
+ inline void push_front(const T&x)
+ {
+ insert (begin(),x);
+ }
+ inline void push_back(const T& x)
+ {
+ insert (end(),x);
+ }
+ inline void pop_front()
+ {
+ erase(begin());
+ }
+ inline bool empty() const { return m_node == m_node->m_next; }
+
+ inline T& front() { return *begin(); }
+ inline const T& front() const { return *begin(); }
+ inline T& back() { return m_node->m_data; }
+ inline const T& back() const { return m_node->m_data; }
+
+ inline iterator begin() { return iterator(m_node->m_next); }
+ inline iterator end() { return iterator(m_node); }
+ inline const_iterator begin() const
+ {
+ return const_iterator(m_node->m_next);
+ }
+ inline const_iterator end() const
+ {
+ return const_iterator(m_node);
+ }
+
+ iterator erase (iterator x)
+ {
+ if (x == end())
+ return x;
+
+ if (x.m_rep->m_next == m_node)
+ m_node = x.m_rep;
+
+ Node* tmp = x.m_rep->m_next;
+ x.m_rep->m_next = x.m_rep->m_next->m_next;
+ delete tmp;
+ --sz;
+
+ return x;
+ }
+
+ iterator insert (iterator x, const T& y)
+ {
+ Node* tmp = new Node(y,x.m_rep->m_next);
+ if (x.m_rep == m_node) // if inserting before end
+ m_node = tmp;
+ x.m_rep->m_next = tmp;
+ ++sz;
+
+ return x++; // x points to the new data, return it, and slide it over
+ }
+
+ // rotate x to beginning
+ void rotate (iterator x)
+ {
+ if (x == end())
+ return;
+ Node* sentinel = m_node->m_next;
+ m_node->m_next = m_node->m_next->m_next;
+ sentinel->m_next = x.m_rep->m_next;
+ x.m_rep->m_next = sentinel;
+ m_node = x.m_rep;
+ }
+};
+
+#endif // __CIRCULAR_LIST_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/consistencylist.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,225 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2006
+ */
+
+#ifndef __CONSISTENCYLIST_H__
+#define __CONSISTENCYLIST_H__
+
+#include "orderlist.h"
+
+#include <iterator>
+#include <iostream>
+#include <list>
+#include "types.h"
+
+#include <boost/utility.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+//#include <boost/type_traits/is_convertible.hpp>
+//#include <boost/utility/enable_if.hpp>
+
+
+template<class T> struct ConsistencyListNode;
+template<class T> class ConsistencyListIterator;
+template<class T> class const_ConsistencyListIterator;
+
+/**
+ * ConsistencyList adds consistency order to OrderList which remains unchanged
+ * through the lifetime of the list.
+ */
+template<class T>
+class ConsistencyList: public OrderList<ConsistencyListNode<T> >
+{
+ public:
+ class OrderComparison;
+ class LessThanComparison;
+ class GreaterThanComparison;
+ class ConsistencyComparison;
+
+ /// \name Comparison types
+ /// @{
+ // Explicit typedefs for Doxygen
+ typedef LessThanComparison LessThanComparison;
+ typedef GreaterThanComparison GreaterThanComparison;
+ typedef ConsistencyComparison ConsistencyComparison;
+ /// @}
+
+ typedef ConsistencyListNode<T> NodeType;
+ typedef ConsistencyList<T> Self;
+ typedef OrderList<NodeType > Parent;
+
+ typedef T value_type;
+ typedef T& reference;
+ typedef const T& const_reference;
+ typedef ConsistencyListIterator<T> iterator;
+ typedef const_ConsistencyListIterator<T> const_iterator;
+
+ ConsistencyList(): sz(0) {}
+ ~ConsistencyList() { clear(); }
+
+ /// \name Order operations
+ void swap(iterator i, iterator j); ///< Exchanges the order of simplices pointed to by i and j
+ template<class BinaryPredicate>
+ void sort(BinaryPredicate cmp); ///< Sorts the elements in accordance with cmp
+
+ /// \name Container operations
+ /// @{
+ // Explicit calls instead of using declarations for Doxygen
+ iterator push_back(const_reference x);
+ iterator insert(iterator predecessor, const_reference x); ///< Inserts x immediately after predecessor (has to be a valid iterator)
+ void erase(iterator x) { Parent::erase(x.get_base()); --sz; }
+
+ void clear() { return Parent::clear(); }
+ bool empty() const { return Parent::empty(); }
+ SizeType size() const { return sz; }
+ iterator begin() { return iterator(Parent::begin()); }
+ const_iterator begin() const { return const_iterator(Parent::begin()); }
+ iterator end() { return iterator(Parent::end()); }
+ const_iterator end() const { return const_iterator(Parent::end()); }
+ reference back() { return Parent::back(); }
+ const_reference back() const { return Parent::back(); }
+ void pop_back() { return Parent::pop_back(); }
+
+ iterator last() { return iterator(boost::prior(end())); }
+ const_iterator last() const { return const_iterator(boost::prior(end())); }
+ /// @}
+
+ private:
+ unsigned int sz;
+};
+
+/// Basic comparison that LessThan and GreaterThan derive from
+template<class T>
+class ConsistencyList<T>::OrderComparison
+{
+ public:
+ typedef typename ConsistencyList<T>::const_iterator ComparableType;
+
+ int compare(ComparableType a, ComparableType b) const; /// (-1,0,1) = a (precedes, ==, succeeds) b
+};
+
+/// Determines if the first element is less than the second one
+template<class T>
+class ConsistencyList<T>::LessThanComparison: public OrderComparison
+{
+ public:
+ typedef OrderComparison Parent;
+ typedef typename Parent::ComparableType ComparableType;
+
+ int compare(ComparableType a, ComparableType b) const;
+ bool operator()(ComparableType a, ComparableType b) const;
+};
+
+/// Determines if the first element is greater than the second one
+template<class T>
+class ConsistencyList<T>::GreaterThanComparison: public OrderComparison
+{
+ public:
+ typedef OrderComparison Parent;
+ typedef typename Parent::ComparableType ComparableType;
+
+ int compare(ComparableType a, ComparableType b) const;
+ bool operator()(ComparableType a, ComparableType b) const;
+};
+
+/// Determines the order of the two elements in the consistency order (that doesn't change during the execution)
+template<class T>
+class ConsistencyList<T>::ConsistencyComparison
+{
+ public:
+ typedef typename ConsistencyList<T>::const_iterator ComparableType;
+
+ int compare(ComparableType a, ComparableType b) const; ///< (-1,0,1) = a (precedes, ==, succeeds) b
+ bool operator()(ComparableType a, ComparableType b) const;
+};
+
+/// Structure storing auxilliary information requred for each node of ConsistencyList
+template<class T>
+struct ConsistencyListNode
+{
+ ConsistencyListNode(const T& d, unsigned int c):
+ data(d), consistency(c)
+ {}
+
+ T data;
+ OrderType consistency;
+
+ std::ostream& operator<<(std::ostream& out) const { return out << data << ": " << consistency; }
+};
+
+template<class T>
+std::ostream& operator<<(std::ostream& out, const ConsistencyListNode<T>& n) { return n.operator<<(out); }
+
+template<class T>
+class ConsistencyListIterator: public boost::iterator_adaptor<ConsistencyListIterator<T>,
+ typename ConsistencyList<T>::Parent::iterator,
+ T>
+{
+ private:
+ struct enabler {};
+
+ public:
+ typedef typename ConsistencyList<T>::Parent ConsistencyListParent;
+ typedef boost::iterator_adaptor<ConsistencyListIterator<T>,
+ typename ConsistencyListParent::iterator,
+ T> Parent;
+ typedef typename Parent::reference reference;
+ typedef typename Parent::base_type base_type;
+
+ ConsistencyListIterator() {}
+ ConsistencyListIterator(const typename ConsistencyListParent::iterator& iter):
+ ConsistencyListIterator::iterator_adaptor_(iter)
+ {}
+ ConsistencyListIterator(const ConsistencyListIterator<T>& other):
+ ConsistencyListIterator::iterator_adaptor_(other.base())
+ {}
+
+ private:
+ friend class boost::iterator_core_access;
+ reference dereference() const { return Parent::base_reference()->data; }
+ base_type& get_base() { return Parent::base_reference(); }
+
+ friend class ConsistencyList<T>;
+};
+
+template<class T>
+class const_ConsistencyListIterator: public boost::iterator_adaptor<const_ConsistencyListIterator<T>,
+ typename ConsistencyList<T>::Parent::const_iterator,
+ const T>
+{
+ private:
+ struct enabler {};
+
+ public:
+ typedef typename ConsistencyList<T>::Parent ConsistencyListParent;
+ typedef boost::iterator_adaptor<const_ConsistencyListIterator<T>,
+ typename ConsistencyListParent::const_iterator,
+ const T> Parent;
+ typedef typename Parent::reference reference;
+ typedef typename Parent::base_type base_type;
+
+ const_ConsistencyListIterator() {}
+ const_ConsistencyListIterator(const typename ConsistencyListParent::const_iterator& iter):
+ const_ConsistencyListIterator::iterator_adaptor_(iter)
+ {}
+ const_ConsistencyListIterator(const const_ConsistencyListIterator<T>& other):
+ const_ConsistencyListIterator::iterator_adaptor_(other.base())
+ {}
+ const_ConsistencyListIterator(const ConsistencyListIterator<T>& other):
+ const_ConsistencyListIterator::iterator_adaptor_(other.base())
+ {}
+
+ private:
+ friend class boost::iterator_core_access;
+ reference dereference() const { return Parent::base_reference()->data; }
+ const base_type&
+ get_base() { return Parent::base_reference(); }
+
+ friend class ConsistencyList<T>::OrderComparison;
+ friend class ConsistencyList<T>::ConsistencyComparison;
+};
+
+
+#include "consistencylist.hpp"
+
+#endif // __CONSISTENCYLIST_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/consistencylist.hpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,86 @@
+/* Implementations */
+
+template<class T>
+void
+ConsistencyList<T>::
+swap(iterator i, iterator j)
+{
+ Parent::swap(i.get_base(),j.get_base());
+}
+
+template<class T>
+template<class BinaryPredicate>
+void
+ConsistencyList<T>::
+sort(BinaryPredicate cmp)
+{
+ Parent::sort(cmp);
+ OrderType cur_order = 0;
+ for (typename Parent::iterator cur = begin(); cur != end(); ++cur)
+ cur->consistency = cur_order++;
+}
+
+
+template<class T>
+typename ConsistencyList<T>::iterator
+ConsistencyList<T>::
+push_back(const_reference x)
+{
+ ++sz;
+ return Parent::push_back(NodeType(x, sz));
+}
+
+template<class T>
+typename ConsistencyList<T>::iterator
+ConsistencyList<T>::
+insert(iterator p, const_reference x)
+{
+ ++sz;
+ return Parent::insert(p.get_base(), NodeType(x, sz));
+}
+
+
+/* OrderComparison */
+template<class T>
+int
+ConsistencyList<T>::
+OrderComparison::compare(ComparableType a, ComparableType b) const
+{
+ typename Parent::OrderComparison cmp;
+ return cmp.compare(a.get_base(), b.get_base());
+}
+
+
+/* LessThanComparison */
+template<class T>
+int ConsistencyList<T>::LessThanComparison::compare(ComparableType a, ComparableType b) const
+{ return Parent::compare(a,b); }
+
+template<class T>
+bool ConsistencyList<T>::LessThanComparison::operator()(ComparableType a, ComparableType b) const
+{ return compare(a,b) == -1; }
+
+
+/* GreaterThanComparison */
+template<class T>
+int ConsistencyList<T>::GreaterThanComparison::compare(ComparableType a, ComparableType b) const
+{ return -Parent::compare(a,b); }
+
+template<class T>
+bool ConsistencyList<T>::GreaterThanComparison::operator()(ComparableType a, ComparableType b) const
+{ return compare(a,b) == -1; }
+
+
+/* ConsistencyComparison */
+template<class T>
+int ConsistencyList<T>::ConsistencyComparison::compare(ComparableType a, ComparableType b) const
+{
+ if (a.get_base()->consistency < b.get_base()->consistency) return -1;
+ else if (a.get_base()->consistency == b.get_base()->consistency) return 0;
+ else return 1;
+}
+
+template<class T>
+bool ConsistencyList<T>::ConsistencyComparison::operator()(ComparableType a, ComparableType b) const
+{ return compare(a,b) == -1; }
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/counter.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,68 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2005 -- 2006
+ */
+
+#ifndef __COUNTER_H__
+#define __COUNTER_H__
+
+/* This should be integrated with the logging facilities. Written in the same framework. */
+
+#include <map>
+#include <string>
+#include <iostream>
+
+#ifndef COUNTERS
+#define Count(x)
+#define CountNum(x,y)
+#else // COUNTERS
+#define Count(x) counters.inc(x)
+#define CountNum(x,y) counters.inc(x,y)
+#endif
+
+typedef unsigned long CounterType;
+typedef std::string KeyType;
+
+class CounterFactory
+{
+ private:
+ typedef std::map<int, CounterType> CountersMap;
+ typedef std::map<KeyType, CountersMap> KeyMap;
+ KeyMap ctrs;
+
+ public:
+ ~CounterFactory()
+ {
+#ifdef COUNTERS
+ std::cout << "Counters:" << std::endl;
+ for (KeyMap::const_iterator cur = ctrs.begin(); cur != ctrs.end(); ++cur)
+ {
+ std::cout << cur->first << ": ";
+ if (cur->second.size() == 1)
+ {
+ std::cout << cur->second.begin()->second << std::endl;
+ continue;
+ }
+ std::cout << std::endl;
+ for (CountersMap::const_iterator ccur = cur->second.begin();
+ ccur != cur->second.end();
+ ++ccur)
+ std::cout << " " << ccur->first << ": " << ccur->second << std::endl;
+ }
+#endif // COUNTERS
+ }
+
+ void inc(const KeyType& key, int num = 0)
+ {
+ ctrs[key][num]++;
+ }
+
+ CounterType lookup(const KeyType& key, int num = 0) const
+ {
+ return const_cast<KeyMap&>(ctrs)[key][num];
+ }
+};
+
+static CounterFactory counters;
+
+#endif // __COUNTER_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/debug.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,90 @@
+#ifndef DEBUG_H
+#define DEBUG_H
+
+#ifndef CWDEBUG
+
+#include <iostream> // std::cerr
+#include <cstdlib> // std::exit, EXIT_FAILURE
+#include <cassert>
+
+#define AllocTag1(p)
+#define AllocTag2(p, desc)
+#define AllocTag_dynamic_description(p, data)
+#define AllocTag(p, data)
+#define Debug(STATEMENT...)
+#define Dout(cntrl, data)
+#define DoutFatal(cntrl, data) LibcwDoutFatal(, , cntrl, data)
+#define ForAllDebugChannels(STATEMENT...)
+#define ForAllDebugObjects(STATEMENT...)
+#define LibcwDebug(dc_namespace, STATEMENT...)
+#define LibcwDout(dc_namespace, d, cntrl, data)
+#define LibcwDoutFatal(dc_namespace, d, cntrl, data) do { ::std::cerr << data << ::std::endl; ::std::exit(EXIT_FAILURE); } while(1)
+#define LibcwdForAllDebugChannels(dc_namespace, STATEMENT...)
+#define LibcwdForAllDebugObjects(dc_namespace, STATEMENT...)
+#define NEW(x) new x
+#define CWDEBUG_ALLOC 0
+#define CWDEBUG_MAGIC 0
+#define CWDEBUG_LOCATION 0
+#define CWDEBUG_LIBBFD 0
+#define CWDEBUG_DEBUG 0
+#define CWDEBUG_DEBUGOUTPUT 0
+#define CWDEBUG_DEBUGM 0
+#define CWDEBUG_DEBUGT 0
+#define CWDEBUG_MARKER 0
+#define AssertMsg(TEST,MSG)
+//#define AssertMsg(TEST,STRM,MSG)
+
+
+#else // CWDEBUG
+
+// This must be defined before <libcwd/debug.h> is included and must be the
+// name of the namespace containing your `dc' (Debug Channels) namespace
+// (see below). You can use any namespace(s) you like, except existing
+// namespaces (like ::, ::std and ::libcwd).
+#define DEBUGCHANNELS ::dionysus::debug::channels
+#include <libcwd/debug.h>
+
+namespace dionysus
+{
+ namespace debug
+ {
+ void init(void); // Initialize debugging code from main().
+ void init_thread(void); // Initialize debugging code from new threads.
+
+ namespace channels // This is the DEBUGCHANNELS namespace, see above.
+ {
+ namespace dc // 'dc' is defined inside DEBUGCHANNELS.
+ {
+ using namespace libcwd::channels::dc;
+ using libcwd::channel_ct;
+
+ // Add the declaration of new debug channels here
+ // and add their definition in a custom debug.cc file.
+ extern channel_ct filtration;
+ extern channel_ct transpositions;
+ extern channel_ct vineyard;
+ extern channel_ct cycle;
+ extern channel_ct lsfiltration;
+ extern channel_ct orderlist;
+ } // namespace dc
+ } // namespace DEBUGCHANNELS
+ }
+}
+
+
+#define AssertMsg(TEST,MSG) \
+ ( (TEST) ? (void)0 \
+ : (std::cerr << __FILE__ ":" << __LINE__ \
+ << ": Assertion failed " #TEST \
+ << " - " << MSG << std::endl,abort()))
+/*
+#define AssertMsg(TEST,STRM,MSG) \
+ ( (TEST) ? (void)0 \
+ : (DoutFatal(STRM, __FILE__ "(" << __LINE__ \
+ << "): Assertion failed " #TEST \
+ << MSG << std::endl)))
+*/
+
+#endif // CWDEBUG
+
+#endif // DEBUG_H
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/eventqueue.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,71 @@
+#ifndef __EVENTQUEUE_H__
+#define __EVENTQUEUE_H__
+
+#include <list>
+#include <functional>
+#include <boost/utility.hpp>
+
+#include <iostream>
+#include <cassert> // TODO: switch to internal debugging system
+#include <string>
+
+// TODO: change inefficient list-based implementation to something heap-based
+// Need a queue that supports deleting arbitrary items (given by iterator),
+// and maintaining correctness of iterators when different operations (notably
+// remove and update are performed)
+
+template<class Event_, class EventComparison_>
+class EventQueue
+{
+
+ public:
+ typedef Event_ Event;
+ typedef EventComparison_ EventComparison;
+
+ typedef std::list<Event> QueueRepresentation;
+ typedef typename QueueRepresentation::iterator iterator;
+ typedef typename QueueRepresentation::const_iterator const_iterator;
+
+ EventQueue() {}
+
+ const_iterator top() const { assert(!empty()); return queue_.begin(); }
+ iterator top() { assert(!empty()); return queue_.begin(); }
+ iterator push(Event e) { queue_.push_front(e); iterator i = top(); update(i); return i; }
+ void pop() { assert(!empty()); queue_.erase(queue_.begin()); }
+ void remove(iterator i) { queue_.erase(i); }
+ void update(iterator i);
+
+ iterator end() { return queue_.end(); }
+ const_iterator end() const { return queue_.end(); }
+ bool empty() const { return queue_.empty(); }
+ size_t size() const { return queue_.size(); }
+
+ std::ostream& print(std::ostream& out, const std::string& prefix) const;
+
+ private:
+ QueueRepresentation queue_;
+};
+
+
+template<class Event_, class EventComparison_>
+void
+EventQueue<Event_, EventComparison_>::
+update(iterator i)
+{
+ QueueRepresentation tmp;
+ tmp.splice(tmp.end(), queue_, i);
+ iterator pos = std::find_if(queue_.begin(), queue_.end(), std::not1(std::bind2nd(EventComparison(), *i)));
+ queue_.splice(pos, tmp);
+}
+
+template<class Event_, class EventComparison_>
+std::ostream&
+EventQueue<Event_, EventComparison_>::
+print(std::ostream& out, const std::string& prefix) const
+{
+ for (typename QueueRepresentation::const_iterator cur = queue_.begin(); cur != queue_.end(); ++cur)
+ (*cur)->print(out << prefix) << std::endl;
+ return out;
+}
+
+#endif // __EVENTQUEUE_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/orderlist.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,212 @@
+/*
+ * Author: Dmitriy Morozov
+ * Department of Computer Science, Duke University, 2006
+ *
+ * Implements the simplified order list data strcutre given in ``Two Simplified
+ * Algorithms for Maintaining Order in a List'' by Bender et al.
+ *
+ * Indirection is not implemented, so the insertion cost is amortized O(log n),
+ * while comparison and deletion are O(1).
+ */
+
+#ifndef __ORDERLIST_H__
+#define __ORDERLIST_H__
+
+#include "sys.h"
+#include "debug.h"
+
+#include <iterator>
+#include <iostream>
+#include <list>
+
+#include "types.h"
+//#include "counter.h"
+
+#include <boost/utility.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+//#include <boost/type_traits/is_convertible.hpp>
+//#include <boost/utility/enable_if.hpp>
+
+
+typedef unsigned int OrderType;
+
+template<class T> struct OrderListNode;
+template<class T> class OrderListIterator;
+template<class T> class const_OrderListIterator;
+
+/**
+ * OrderList stores a list of objects while maintaining their total order under
+ * the operations of insert(), swap(), and delete(). push_back() is provided for
+ * uniformity, OrderComparison member class carries out comparison of the
+ * elements.
+ */
+template<class T>
+class OrderList: public std::list<OrderListNode<T> >
+{
+ public:
+ class OrderComparison;
+
+ /// OrderComparison type
+ typedef OrderComparison OrderComparison;
+
+ typedef OrderListNode<T> NodeType;
+ typedef OrderList<T> Self;
+ typedef std::list<NodeType > Parent;
+
+ typedef T value_type;
+ typedef T& reference;
+ typedef const T& const_reference;
+ typedef OrderListIterator<T> iterator;
+ typedef const_OrderListIterator<T> const_iterator;
+
+ OrderList() {}
+ ~OrderList() { clear(); }
+
+ /// \name Order operations
+ void swap(iterator i, iterator j); ///< Exchanges the order of simplices pointed to by i and j
+ template<class BinaryPredicate>
+ void sort(BinaryPredicate cmp); ///< Sorts the elements in accordance with cmp
+
+ /// \name Container operations
+ /// @{
+ // Explicit calls instead of using declarations for Doxygen
+ iterator push_back(const_reference x);
+ iterator insert(iterator predecessor, const_reference x); ///< Inserts x immediately after predecessor (has to be a valid iterator)
+ void erase(iterator x) { Parent::erase(x.get_base()); }
+
+ void clear() { return Parent::clear(); }
+ bool empty() const { return Parent::empty(); }
+ SizeType size() const { return Parent::size(); }
+ iterator begin() { return iterator(Parent::begin()); }
+ const_iterator begin() const { return const_iterator(Parent::begin()); }
+ iterator end() { return iterator(Parent::end()); }
+ const_iterator end() const { return const_iterator(Parent::end()); }
+ reference back() { return Parent::back(); }
+ const_reference back() const { return Parent::back(); }
+ void pop_back() { return Parent::pop_back(); }
+
+ iterator last() { return iterator(boost::prior(end())); }
+ const_iterator last() const { return const_iterator(boost::prior(end())); }
+ /// @}
+
+ /// \name Debugging operations
+ /// @{
+ void show_elements() const;
+ /// @}
+
+ private:
+ static const float density_threshold = 1.2;
+};
+
+/// Basic comparison that LessThan and GreaterThan derive from
+template<class T>
+class OrderList<T>::OrderComparison
+{
+ public:
+ typedef typename OrderList<T>::const_iterator ComparableType;
+ int compare(ComparableType a, ComparableType b) const; /// (-1,0,1) = a (precedes, ==, succeeds) b
+ bool operator()(ComparableType a, ComparableType b) const;
+};
+
+/// Structure storing auxilliary information requred for each node of OrderList
+template<class T>
+struct OrderListNode
+{
+ OrderListNode(const T& d, unsigned int t):
+ data(d), tag(t)
+ {}
+
+ T data;
+ OrderType tag;
+
+ std::ostream& operator<<(std::ostream& out) const { return out << data << ": " << tag; }
+};
+
+template<class T, class BinaryPredicate>
+class OrderListNodeComparison
+{
+ public:
+ typedef OrderListNode<T> Node;
+ OrderListNodeComparison(BinaryPredicate cmp): cmp_(cmp) {}
+ bool operator()(const Node& a, const Node& b) const { return cmp_(a.data, b.data); }
+
+ private:
+ BinaryPredicate cmp_;
+};
+
+template<class T>
+std::ostream& operator<<(std::ostream& out, const OrderListNode<T>& n) { return n.operator<<(out); }
+
+template<class T>
+class OrderListIterator: public boost::iterator_adaptor<OrderListIterator<T>,
+ typename OrderList<T>::Parent::iterator,
+ T>
+{
+ private:
+ struct enabler {};
+
+ public:
+ typedef typename OrderList<T>::Parent OrderListParent;
+ typedef boost::iterator_adaptor<OrderListIterator<T>,
+ typename OrderListParent::iterator,
+ T> Parent;
+ typedef typename Parent::reference reference;
+ typedef typename Parent::base_type base_type;
+
+ OrderListIterator() {}
+ OrderListIterator(const typename OrderListParent::iterator& iter):
+ OrderListIterator::iterator_adaptor_(iter)
+ {}
+ OrderListIterator(const OrderListIterator<T>& other):
+ OrderListIterator::iterator_adaptor_(other.base())
+ {}
+
+ private:
+ friend class boost::iterator_core_access;
+ reference dereference() const { return Parent::base_reference()->data; }
+ base_type& get_base() { return Parent::base_reference(); }
+
+ friend class OrderList<T>;
+};
+
+template<class T>
+class const_OrderListIterator: public boost::iterator_adaptor<const_OrderListIterator<T>,
+ typename OrderList<T>::Parent::const_iterator,
+ const T>
+{
+ private:
+ struct enabler {};
+
+ public:
+ typedef typename OrderList<T>::Parent OrderListParent;
+ typedef boost::iterator_adaptor<const_OrderListIterator<T>,
+ typename OrderListParent::const_iterator,
+ const T> Parent;
+ typedef typename Parent::reference reference;
+ typedef typename Parent::base_type base_type;
+
+ const_OrderListIterator() {}
+ const_OrderListIterator(const typename OrderListParent::const_iterator& iter):
+ const_OrderListIterator::iterator_adaptor_(iter)
+ {}
+ const_OrderListIterator(const const_OrderListIterator<T>& other):
+ const_OrderListIterator::iterator_adaptor_(other.base())
+ {}
+ const_OrderListIterator(const OrderListIterator<T>& other):
+ const_OrderListIterator::iterator_adaptor_(other.base())
+ {}
+
+ private:
+ friend class boost::iterator_core_access;
+ reference dereference() const { return Parent::base_reference()->data; }
+ const base_type&
+ get_base() { return Parent::base_reference(); }
+
+ friend class OrderList<T>;
+ friend class OrderList<T>::OrderComparison;
+};
+
+
+#include "orderlist.hpp"
+
+#endif // __ORDERLIST_H__
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/orderlist.hpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,118 @@
+/* Implementations */
+
+template<class T>
+void
+OrderList<T>::
+swap(iterator i, iterator j)
+{
+ typename Parent::iterator i_base = i.get_base();
+ typename Parent::iterator j_base = j.get_base();
+ std::swap(i_base->tag, j_base->tag);
+
+ // Exchange the actual elements in the list --- so that iterators behave as expected
+ typename Parent::iterator after_j = boost::next(j_base);
+ Parent::splice(i_base, *this, j_base);
+ Parent::splice(after_j, *this, i_base);
+}
+
+template<class T>
+template<class BinaryPredicate>
+void
+OrderList<T>::
+sort(BinaryPredicate cmp)
+{
+ Parent::sort(OrderListNodeComparison<T, BinaryPredicate>(cmp));
+ OrderType cur_order = 0;
+ for (typename Parent::iterator cur = Parent::begin(); cur != Parent::end(); ++cur)
+ cur->tag = cur_order++;
+}
+
+template<class T>
+typename OrderList<T>::iterator
+OrderList<T>::
+push_back(const_reference x)
+{
+ if (empty())
+ Parent::push_back(NodeType(x, 0));
+ else
+ Parent::push_back(NodeType(x, last().get_base()->tag + 1));
+
+ return last();
+}
+
+template<class T>
+typename OrderList<T>::iterator
+OrderList<T>::
+insert(iterator p, const_reference x)
+{
+ typename Parent::iterator p_base = p.get_base();
+ OrderType tag = (p_base++)->tag + 1;
+ typename Parent::iterator new_base = Parent::insert(p_base, NodeType(x, tag));
+
+ if (p_base->tag != tag)
+ return iterator(new_base);
+
+ // Find non-overflowing region
+ unsigned int num_elements = 1, maximum = 1, lower = tag, upper = tag, level = 0;
+ float inv_density = 1;
+ typename Parent::iterator prev = p_base, next = p_base;
+ --(--prev); ++next; // move prev back twice to skip over the newly inserted element
+
+ do
+ {
+ lower &= ~(1 << level);
+ upper |= (1 << level);
+ maximum <<= 1; inv_density *= density_threshold;
+ ++level;
+
+ while (prev != Parent::end() && prev->tag >= lower) { --prev; ++num_elements; }
+ while (next != Parent::end() && next->tag <= upper) { ++next; ++num_elements; }
+ } while (inv_density * num_elements >= maximum);
+ ++num_elements; // for the extra element inserted
+
+ Dout(dc::orderlist, num_elements << ", " << lower << ", " << upper);
+ Dout(dc::orderlist, "prev is at the end: " << (prev == Parent::end()));
+ Dout(dc::orderlist, "next is at the end: " << (next == Parent::end()));
+
+ // Reorder
+ AssertMsg((upper - lower + 1)/num_elements > 0, "Spacing between new tags must be non-zero");
+ for (unsigned int i = 0; i < num_elements; ++i)
+ {
+ (++prev)->tag = lower + i*((upper - lower + 1)/num_elements);
+ Dout(dc::orderlist, prev->tag);
+ AssertMsg(prev->tag != 0 || prev == Parent::begin(), "Cannot assign 0 tag except at the beginning of OrderList");
+ }
+
+ AssertMsg(++prev == next, "prev + num_elements != next in OrderList::insert()");
+
+ return iterator(new_base);
+}
+
+template<class T>
+void
+OrderList<T>::
+show_elements() const
+{
+ for (const_iterator cur = begin(); cur != end(); ++cur)
+ std::cout << *(cur.get_base()) << std::endl;
+ std::cout << std::endl;
+}
+
+/* OrderComparison */
+template<class T>
+int
+OrderList<T>::OrderComparison::
+compare(ComparableType a, ComparableType b) const
+{
+ if (a.get_base()->tag == b.get_base()->tag) return 0;
+ if (a.get_base()->tag < b.get_base()->tag) return -1;
+ return 1;
+}
+
+template<class T>
+bool
+OrderList<T>::OrderComparison::
+operator()(ComparableType a, ComparableType b) const
+{
+ return (compare(a,b) < 0);
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/sys.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,26 @@
+// sys.h
+//
+// This header file is included at the top of every source file,
+// before any other header file.
+// It is intended to add defines that are needed globally and
+// to work around Operating System dependend incompatibilities.
+
+// EXAMPLE: If you use autoconf you can add the following here.
+// #ifdef HAVE_CONFIG_H
+// #include "config.h"
+// #endif
+
+// EXAMPLE: You could add stuff like this here too
+// (Otherwise add -DCWDEBUG to your CFLAGS).
+// #if defined(WANTSDEBUGGING) && defined(HAVE_LIBCWD_BLAHBLAH)
+// #define CWDEBUG
+// #endif
+
+// The following is the libcwd related mandatory part.
+// It must be included before any system header file is included!
+#ifdef CWDEBUG
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+#include <libcwd/sys.h>
+#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/include/utilities/types.h Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,18 @@
+#ifndef __TYPES_H__
+#define __TYPES_H__
+
+#include <limits>
+
+/* Types */
+typedef bool Sign;
+typedef short int Dimension;
+const Sign POS = true;
+const Sign NEG = false;
+typedef double RealType;
+typedef unsigned int SizeType;
+
+static RealType Infinity = std::numeric_limits<RealType>::infinity();
+
+typedef const unsigned int& version_type;
+
+#endif // __TYPES_H__
--- a/include/vineyard.h Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,145 +0,0 @@
-/*
- * Author: Dmitriy Morozov
- * Department of Computer Science, Duke University, 2005 -- 2006
- */
-
-#ifndef __VINEYARD_H__
-#define __VINEYARD_H__
-
-#include "types.h"
-#include <list>
-#include <string>
-
-#include <boost/serialization/access.hpp>
-#include <boost/serialization/vector.hpp>
-#include <boost/serialization/nvp.hpp>
-#include <boost/serialization/list.hpp>
-#include <boost/serialization/is_abstract.hpp>
-
-
-template<class Smplx> class Knee;
-template<class Smplx> class Vine;
-
-/**
- * Vineyard class. Keeps track of vines and knees. switched() is the key function called
- * by filtration when pairing switches after a Filtration::transpose().
- */
-template<class FltrSmplx>
-class Vineyard
-{
- public:
- typedef FltrSmplx FiltrationSimplex;
- typedef typename FiltrationSimplex::Simplex Simplex;
- typedef Vine<Simplex> Vine;
- typedef Knee<Simplex> Knee;
- typedef std::list<Vine> VineList;
- typedef std::vector<VineList> VineListVector;
- typedef typename FiltrationSimplex::Cycle Cycle;
-
- typedef typename FiltrationSimplex::Index Index;
- typedef typename FiltrationSimplex::Evaluator Evaluator;
-
- public:
- Vineyard(Evaluator* eval = 0):
- evaluator(eval) {}
-
- void start_vines(Index bg, Index end);
- void switched(Index i, Index j);
- void record_diagram(Index bg, Index end);
-
- void set_evaluator(Evaluator* eval) { evaluator = eval; }
-
- void save_edges(const std::string& filename) const;
-
- protected:
- typename Knee::SimplexList resolve_cycle(Index i) const;
-
- private:
- void record_knee(Index i);
- void start_vine(Index i);
-
- private:
- VineListVector vines;
- Evaluator* evaluator;
-};
-
-/**
- * Knee class stores the knee in R^3 as well as the cycle that is associated with the Simplex starting from the Knee.
- */
-template<class S>
-class Knee
-{
- public:
- typedef S Simplex;
- typedef std::list<Simplex> SimplexList;
-
- RealType birth;
- RealType death;
- RealType time;
- SimplexList cycle;
-
- // Default parameters for serialization
- Knee(RealType b = 0, RealType d = 0, RealType t = 0):
- birth(b), death(d), time(t)
- {}
- Knee(const Knee& other):
- birth(other.birth), death(other.death), time(other.time)
- {}
-
- bool is_diagonal() const { return birth == death; }
- bool is_infinite() const { return (death == Infinity) || (birth == Infinity); }
- void set_cycle(const SimplexList& lst) { cycle = lst; }
-
- std::ostream& operator<<(std::ostream& out) const { return out << "(" << birth << ", "
- << death << ", "
- << time << ")"; }
-
- private:
- friend class boost::serialization::access;
-
- template<class Archive>
- void serialize(Archive& ar, version_type );
-};
-
-template<class S>
-std::ostream& operator<<(std::ostream& out, const Knee<S>& k) { return k.operator<<(out); }
-
-/**
- * Vine is a list of Knees
- */
-template<class S>
-class Vine: public std::list<Knee<S> >
-{
- public:
- typedef S Simplex;
- typedef Knee<Simplex> Knee;
- typedef std::list<Knee> VineRepresentation;
- typedef typename VineRepresentation::const_iterator const_knee_iterator;
-
- Vine() {}
- Vine(const Knee& k) { add(k); }
-
- void add(RealType b, RealType d, RealType t) { push_back(Knee(b,d,t)); }
- void add(const Knee& k) { push_back(k); }
-
- using VineRepresentation::begin;
- using VineRepresentation::end;
- using VineRepresentation::front;
- using VineRepresentation::back;
- using VineRepresentation::size;
- using VineRepresentation::empty;
-
- protected:
- using VineRepresentation::push_back;
-
- private:
- friend class boost::serialization::access;
-
- template<class Archive>
- void serialize(Archive& ar, version_type );
-};
-
-
-#include "vineyard.hpp"
-
-#endif // __VINEYARD_H__
--- a/include/vineyard.hpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,157 +0,0 @@
-/* Implementations */
-
-#include <fstream>
-#include <sstream>
-
-template<class FS>
-void
-Vineyard<FS>::
-start_vines(Index bg, Index end)
-{
- AssertMsg(evaluator != 0, "Cannot start vines with a null evaluator");
- for (Index cur = bg; cur != end; ++cur)
- {
- if (!cur->sign()) continue;
- Dimension dim = cur->dimension();
-
- if (dim >= vines.size())
- {
- AssertMsg(dim == vines.size(), "New dimension has to be contiguous");
- vines.push_back(std::list<Vine>());
- }
-
- start_vine(cur);
- record_knee(cur);
- }
-}
-
-template<class FS>
-void
-Vineyard<FS>::
-switched(Index i, Index j)
-{
- Vine* i_vine = i->vine();
- Vine* j_vine = j->vine();
- i->set_vine(j_vine);
- j->set_vine(i_vine);
-
- // Since the pairing has already been updated, the following assertions should be true
- AssertMsg(i->vine() == i->pair()->vine(), "i's vine must match the vine of its pair");
- AssertMsg(j->vine() == j->pair()->vine(), "j's vine must match the vine of its pair");
-
- if (!i->sign()) i = i->pair();
- if (!j->sign()) j = j->pair();
- record_knee(i);
- record_knee(j);
-}
-
-template<class FS>
-void
-Vineyard<FS>::
-start_vine(Index i)
-{
- Dout(dc::vineyard, "Starting new vine");
- AssertMsg(i->sign(), "Can only start vines for positive simplices");
-
- Dimension dim = i->dimension();
- vines[dim].push_back(Vine());
- i->set_vine(&vines[dim].back());
- i->pair()->set_vine(i->vine());
-}
-
-/// Records the current diagram in the vineyard
-template<class FS>
-void
-Vineyard<FS>::
-record_diagram(Index bg, Index end)
-{
- Dout(dc::vineyard, "Entered: record_diagram()");
- AssertMsg(evaluator != 0, "Cannot record diagram with a null evaluator");
-
- for (Index i = bg; i != end; ++i)
- {
- AssertMsg(i->vine() != 0, "Cannot process a null vine in record_diagram");
- if (!i->sign()) continue;
- record_knee(i);
- }
-}
-
-
-template<class FS>
-void
-Vineyard<FS>::
-save_edges(const std::string& filename) const
-{
- for (int i = 0; i < vines.size(); ++i)
- {
- std::ostringstream os; os << i;
- std::string fn = filename + os.str() + ".edg";
- std::ofstream out(fn.c_str());
- for (typename VineList::const_iterator vi = vines[i].begin(); vi != vines[i].end(); ++vi)
- for (typename Vine::const_iterator ki = vi->begin(), kiprev = ki++; ki != vi->end(); kiprev = ki++)
- {
- if (kiprev->is_infinite() || ki->is_infinite()) continue;
- out << kiprev->birth << ' ' << kiprev->death << ' ' << kiprev->time << std::endl;
- out << ki->birth << ' ' << ki->death << ' ' << ki->time << std::endl;
- }
- out.close();
- }
-}
-
-/// Records a knee for the given simplex
-template<class FS>
-void
-Vineyard<FS>::
-record_knee(Index i)
-{
- Dout(dc::vineyard, "Entered record_knee()");
- AssertMsg(evaluator != 0, "Cannot record knee with a null evaluator");
- AssertMsg(i->vine() != 0, "Cannot add a knee to a null vine");
- AssertMsg(i->sign(), "record_knee() must be called on a positive simplex");
-
- if (!i->is_paired())
- i->vine()->add(evaluator->value(*i), Infinity, evaluator->time());
- else
- {
- Dout(dc::vineyard, "Creating knee");
- Knee k(evaluator->value(*i), evaluator->value(*(i->pair())), evaluator->time());
- Dout(dc::vineyard, "Knee created: " << k);
-
- if (!k.is_diagonal() || i->vine()->empty()) // non-diagonal k, or empty vine
- {
- Dout(dc::vineyard, "Extending a vine");
- i->vine()->add(k);
- }
- else if (i->vine()->back().is_diagonal()) // last knee is diagonal
- {
- AssertMsg(i->vine()->size() == 1, "Only first knee may be diagonal for a live vine");
- Dout(dc::vineyard, "Overwriting first diagonal knee");
- i->vine()->back() = k;
- } else // finish this vine
- {
- Dout(dc::vineyard, "Finishing a vine");
- i->vine()->add(k);
- start_vine(i);
- i->vine()->add(k);
- }
- }
-
- i->vine()->back().set_cycle(resolve_cycle(i));
- Dout(dc::vineyard, "Leaving record_knee()");
-}
-
-template<class FS>
-typename Vineyard<FS>::Knee::SimplexList
-Vineyard<FS>::
-resolve_cycle(Index i) const
-{
- Dout(dc::vineyard, "Entered resolve_cycle");
- const Cycle& cycle = i->cycle();
-
- // Resolve simplices
- typename Knee::SimplexList lst;
- for (typename Cycle::const_iterator cur = cycle.begin(); cur != cycle.end(); ++cur)
- lst.push_back(**cur);
-
- return lst;
-}
--- a/tests/CMakeLists.txt Sun Jul 01 00:00:00 2007 -0400
+++ b/tests/CMakeLists.txt Tue Aug 14 17:15:08 2007 -0400
@@ -1,8 +1,1 @@
-set (targets
- test-consistencylist
- test-orderlist)
-
-foreach (t ${targets})
- add_executable (${t} ${t}.cpp ${external_sources})
- target_link_libraries (${t} ${libraries})
-endforeach (t ${targets})
+add_subdirectory (utilities)
--- a/tests/test-consistencylist.cpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,57 +0,0 @@
-#include "consistencylist.h"
-#include <iostream>
-
-typedef ConsistencyList<int> OList;
-typedef OList::OrderComparison Comparison;
-typedef OList::iterator iterator;
-
-int main()
-{
-#ifdef CWDEBUG
- dionysus::debug::init();
-
- //Debug(dc::orderlist.on());
-#endif
-
- OList list; Comparison cmp;
- iterator i20 = list.push_back(20);
- iterator i50 = list.push_back(50);
- list.show_elements();
-
- iterator i30 = list.insert(i20, 30);
- list.show_elements();
-
- iterator i40 = list.insert(i30, 40);
- iterator i60 = list.insert(i50, 60);
- list.show_elements();
-
- iterator i70 = list.push_back(70);
- iterator i45 = list.insert(i40,45);
- iterator i25 = list.insert(i20,25);
- iterator i35 = list.insert(i30,35);
- iterator i55 = list.insert(i50,55);
- iterator i65 = list.insert(i60,65);
- iterator i57 = list.insert(i55,57);
- std::cout << "Before swaps" << std::endl;
- list.show_elements();
-
- list.swap(i45, i50);
- list.swap(i45, i65);
- std::cout << "After swaps" << std::endl;
- list.show_elements();
-
- std::cout << *(++list.end()) << std::endl;
- std::cout << *(--list.end()) << std::endl;
- std::cout << std::endl;
-
- for (int i = 0; i < 100000; ++i)
- {
- list.insert(i20,i);
- }
- list.show_elements();
-
- std::cout << "20 < 30: " << cmp.compare(i20,i30) << std::endl;
- std::cout << "60 < 40: " << cmp.compare(i60,i40) << std::endl;
- std::cout << "50 < 70: " << cmp.compare(i50,i70) << std::endl;
- std::cout << "60 < 70: " << cmp.compare(i60,i70) << std::endl;
-}
--- a/tests/test-orderlist.cpp Sun Jul 01 00:00:00 2007 -0400
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,49 +0,0 @@
-#include "orderlist.h"
-#include <iostream>
-
-typedef OrderList<int> OList;
-typedef OList::OrderComparison Comparison;
-typedef OList::iterator iterator;
-
-int main()
-{
-#ifdef CWDEBUG
- dionysus::debug::init();
-
- Debug(dc::orderlist.on());
-#endif
-
- OList list; Comparison cmp;
- iterator i20 = list.push_back(20);
- iterator i50 = list.push_back(50);
- list.show_elements();
-
- iterator i30 = list.insert(i20, 30);
- list.show_elements();
-
- iterator i40 = list.insert(i30, 40);
- iterator i60 = list.insert(i50, 60);
- list.show_elements();
-
- iterator i70 = list.push_back(70);
- iterator i45 = list.insert(i40,45);
- iterator i25 = list.insert(i20,25);
- iterator i35 = list.insert(i30,35);
- iterator i55 = list.insert(i50,55);
- iterator i65 = list.insert(i60,65);
- iterator i57 = list.insert(i55,57);
- list.show_elements();
-
- std::cout << *(++list.end()) << std::endl;
- std::cout << *(--list.end()) << std::endl;
- std::cout << std::endl;
-
- std::cout << "20 < 30: " << cmp.compare(i20,i30) << std::endl;
- std::cout << "60 < 40: " << cmp.compare(i60,i40) << std::endl;
- std::cout << "50 < 70: " << cmp.compare(i50,i70) << std::endl;
- std::cout << "60 < 70: " << cmp.compare(i60,i70) << std::endl;
- std::cout << std::endl;
-
- std::cout << "60 < 40: " << cmp(i60, i40) << std::endl;
- std::cout << "60 < 70: " << cmp(i60, i70) << std::endl;
-}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/utilities/CMakeLists.txt Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,8 @@
+set (targets
+ test-consistencylist
+ test-orderlist)
+
+foreach (t ${targets})
+ add_executable (${t} ${t}.cpp ${external_sources})
+ target_link_libraries (${t} ${libraries})
+endforeach (t ${targets})
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/utilities/test-consistencylist.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,57 @@
+#include "utilities/consistencylist.h"
+#include <iostream>
+
+typedef ConsistencyList<int> OList;
+typedef OList::OrderComparison Comparison;
+typedef OList::iterator iterator;
+
+int main()
+{
+#ifdef CWDEBUG
+ dionysus::debug::init();
+
+ //Debug(dc::orderlist.on());
+#endif
+
+ OList list; Comparison cmp;
+ iterator i20 = list.push_back(20);
+ iterator i50 = list.push_back(50);
+ list.show_elements();
+
+ iterator i30 = list.insert(i20, 30);
+ list.show_elements();
+
+ iterator i40 = list.insert(i30, 40);
+ iterator i60 = list.insert(i50, 60);
+ list.show_elements();
+
+ iterator i70 = list.push_back(70);
+ iterator i45 = list.insert(i40,45);
+ iterator i25 = list.insert(i20,25);
+ iterator i35 = list.insert(i30,35);
+ iterator i55 = list.insert(i50,55);
+ iterator i65 = list.insert(i60,65);
+ iterator i57 = list.insert(i55,57);
+ std::cout << "Before swaps" << std::endl;
+ list.show_elements();
+
+ list.swap(i45, i50);
+ list.swap(i45, i65);
+ std::cout << "After swaps" << std::endl;
+ list.show_elements();
+
+ std::cout << *(++list.end()) << std::endl;
+ std::cout << *(--list.end()) << std::endl;
+ std::cout << std::endl;
+
+ for (int i = 0; i < 100000; ++i)
+ {
+ list.insert(i20,i);
+ }
+ list.show_elements();
+
+ std::cout << "20 < 30: " << cmp.compare(i20,i30) << std::endl;
+ std::cout << "60 < 40: " << cmp.compare(i60,i40) << std::endl;
+ std::cout << "50 < 70: " << cmp.compare(i50,i70) << std::endl;
+ std::cout << "60 < 70: " << cmp.compare(i60,i70) << std::endl;
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/utilities/test-orderlist.cpp Tue Aug 14 17:15:08 2007 -0400
@@ -0,0 +1,49 @@
+#include "utilities/orderlist.h"
+#include <iostream>
+
+typedef OrderList<int> OList;
+typedef OList::OrderComparison Comparison;
+typedef OList::iterator iterator;
+
+int main()
+{
+#ifdef CWDEBUG
+ dionysus::debug::init();
+
+ Debug(dc::orderlist.on());
+#endif
+
+ OList list; Comparison cmp;
+ iterator i20 = list.push_back(20);
+ iterator i50 = list.push_back(50);
+ list.show_elements();
+
+ iterator i30 = list.insert(i20, 30);
+ list.show_elements();
+
+ iterator i40 = list.insert(i30, 40);
+ iterator i60 = list.insert(i50, 60);
+ list.show_elements();
+
+ iterator i70 = list.push_back(70);
+ iterator i45 = list.insert(i40,45);
+ iterator i25 = list.insert(i20,25);
+ iterator i35 = list.insert(i30,35);
+ iterator i55 = list.insert(i50,55);
+ iterator i65 = list.insert(i60,65);
+ iterator i57 = list.insert(i55,57);
+ list.show_elements();
+
+ std::cout << *(++list.end()) << std::endl;
+ std::cout << *(--list.end()) << std::endl;
+ std::cout << std::endl;
+
+ std::cout << "20 < 30: " << cmp.compare(i20,i30) << std::endl;
+ std::cout << "60 < 40: " << cmp.compare(i60,i40) << std::endl;
+ std::cout << "50 < 70: " << cmp.compare(i50,i70) << std::endl;
+ std::cout << "60 < 70: " << cmp.compare(i60,i70) << std::endl;
+ std::cout << std::endl;
+
+ std::cout << "60 < 40: " << cmp(i60, i40) << std::endl;
+ std::cout << "60 < 70: " << cmp(i60, i70) << std::endl;
+}