3.2 循环迭代器（Circulator）

1. 理论基础

1.1 循环数据结构的数学定义

在计算几何中，许多拓扑结构具有天然的循环特性：多边形的顶点序列、面的边界边、顶点的one-ring邻居等。传统STL迭代器在end()处终止，而循环迭代器（Circulator）在到达末尾时自动回到起点，形成循环遍历。

定义 1.1（Circulator）：设 $C$ 是一个类型，如果满足以下条件，则称 $C$ 为Circulator：

支持解引用操作： $* c \to T$
支持递增操作： $+ + c \to C &$
范围 $[c, c)$ 表示整个循环结构
不存在独立的终止迭代器

定义 1.2（Circulator类别）：

Forward_circulator: 支持前向遍历（++）
Bidirectional_circulator: 支持双向遍历（++和--）
Random_access_circulator: 支持随机访问（[]、+、-）

1.2 Circulator与Iterator的数学对比

特性	Iterator	Circulator
定义域	$[b e g in, e n d)$	循环群 $Z_{n}$
终止条件	$i t == e n d$	用户决定循环次数
空范围判断	$b e g in == e n d$	$c == n u llpt r$
大小计算	$e n d - b e g in$	完整遍历计数
数学结构	区间	循环群

定理 1.1（Circulator的群结构）：设 $C$ 是一个Forward_circulator， $n = circulator_size (c)$ ，则操作 $+ +$ 在 $C$ 上生成一个阶为 $n$ 的循环群。

1.3 半边结构中的循环遍历

在半边数据结构（HalfedgeDS）中，存在三种基本的循环遍历：

面边界遍历（Face boundary traversal）：绕面的边界半边循环，使用 next() 操作。
顶点one-ring遍历（Vertex one-ring traversal）：绕顶点的邻接面循环，使用 opposite()->next() 操作。
边遍历（Edge traversal）：遍历所有边（半边对），使用 opposite() 操作。

2. 架构分析

2.1 Circulator概念层次

Circulator概念体系
├── Circulator_tag（标记类）
│   ├── Forward_circulator_tag
│   ├── Bidirectional_circulator_tag
│   └── Random_access_circulator_tag
│
├── Circulator_traits<C>（特征类）
│   ├── category: Iterator_tag | Circulator_tag
│   ├── iterator_category
│   ├── circulator_category
│   ├── value_type
│   ├── reference
│   ├── pointer
│   ├── difference_type
│   └── size_type
│
└── 适配器类
    ├── Circulator_from_iterator<I>
    ├── Circulator_from_container<C>
    ├── Container_from_circulator<C>
    └── Iterator_from_circulator<C>

2.2 Circulator核心接口

namespace CGAL {
 
// Circulator类别标记
struct Forward_circulator_tag {};
struct Bidirectional_circulator_tag : public Forward_circulator_tag {};
struct Random_access_circulator_tag : public Bidirectional_circulator_tag {};
 
// Circulator特征类
template<typename C>
struct Circulator_traits {
    typedef typename internal::Get_category<
        typename iterator_traits::iterator_category
    >::type category;
    
    typedef typename iterator_traits::value_type        value_type;
    typedef typename iterator_traits::reference         reference;
    typedef typename iterator_traits::pointer           pointer;
    typedef typename iterator_traits::difference_type   difference_type;
    typedef typename iterator_traits::iterator_category iterator_category;
    
    typedef typename I_Circulator_size_traits<
        category, C>::size_type size_type;
};
 
// 编译时Circulator检查
template <class C>
void Assert_circulator(const C &) {
    typedef typename Circulator_traits<C>::category category;
    static_assert(std::is_convertible<category, Circulator_tag>::value);
}
 
} // namespace CGAL

2.3 适配器设计模式

CGAL提供了多种Circulator适配器，用于在不同表示之间转换：

适配器	功能	使用场景
`Circulator_from_iterator<I>`	将迭代器范围转换为Circulator	为STL容器提供Circulator接口
`Circulator_from_container<C>`	从容器的begin/end创建Circulator	快速包装容器
`Container_from_circulator<C>`	将Circulator转换为STL范围	使用STL算法处理Circulator
`Iterator_from_circulator<C>`	Circulator转迭代器	需要end()标记的场景

3. 实现细节

3.1 Circulator_from_iterator实现

// 文件: CGAL/circulator.h
 
template<typename I>
class Circulator_from_iterator {
public:
    typedef I iterator;
    typedef Circulator_from_iterator<I> Self;
    typedef std::iterator_traits<I> traits;
    
    typedef typename traits::value_type         value_type;
    typedef typename traits::reference          reference;
    typedef typename traits::pointer            pointer;
    typedef typename traits::difference_type    difference_type;
    typedef typename I_Circulator_from_iterator_traits<
        typename traits::iterator_category>::iterator_category iterator_category;
    typedef typename I_Circulator_size_traits<
        iterator_category, Self>::size_type size_type;
 
private:
    iterator begin;     // 范围起始
    iterator end;       // 范围终止（past-the-end）
    iterator current;   // 当前位置
 
public:
    // 默认构造函数：空Circulator
    Circulator_from_iterator() : begin(), end(), current() {}
    
    // 从范围构造
    Circulator_from_iterator(const I& b, const I& e, const I& cur = b)
        : begin(b), end(e), current(cur) {}
    
    // 复制并重新定位
    Circulator_from_iterator(const Self& d, const I& cur)
        : begin(d.begin), end(d.end), current(cur) {}
 
    // 解引用
    reference operator*() const { return *current; }
    pointer operator->() const { return &*current; }
    
    // 前向操作
    Self& operator++() {
        ++current;
        if (current == end) current = begin;
        return *this;
    }
    
    Self operator++(int) {
        Self tmp = *this;
        ++*this;
        return tmp;
    }
    
    // 双向操作
    Self& operator--() {
        if (current == begin) current = end;
        --current;
        return *this;
    }
    
    Self operator--(int) {
        Self tmp = *this;
        --*this;
        return tmp;
    }
    
    // 比较操作
    bool operator==(const Self& c) const { return current == c.current; }
    bool operator!=(const Self& c) const { return !(*this == c); }
    
    // 辅助函数
    iterator current_iterator() const { return current; }
    bool is_empty() const { return begin == end; }
    
    // 随机访问操作（仅当底层迭代器支持时）
    Self& operator+=(difference_type n) {
        difference_type len = end - begin;
        difference_type pos = current - begin;
        pos = (pos + n) % len;
        if (pos < 0) pos += len;
        current = begin + pos;
        return *this;
    }
    
    Self operator+(difference_type n) const {
        Self tmp = *this;
        return tmp += n;
    }
    
    // 获取最小Circulator（用于size计算）
    Self min_circulator() const {
        // 返回指向最小元素的Circulator
        iterator min_it = begin;
        for (iterator it = begin; it != end; ++it) {
            if (*it < *min_it) min_it = it;
        }
        return Self(begin, end, min_it);
    }
};

3.2 Container_from_circulator实现

// 文件: CGAL/circulator.h
 
template<typename C>
class Container_from_circulator {
public:
    typedef C Circulator;
    typedef typename C::value_type value_type;
    typedef typename C::reference reference;
    typedef typename C::pointer pointer;
    typedef typename C::difference_type difference_type;
    typedef typename C::size_type size_type;
    
    // 内部迭代器类
    class iterator {
        const C* anchor;    // 锚点Circulator
        C current;          // 当前Circulator
        int winding;        // 绕数（winding number）
        
    public:
        iterator() : anchor(nullptr), winding(0) {}
        
        iterator(const C& c, int w = 0) 
            : anchor(&c), current(c), winding(w) {}
        
        reference operator*() const { return *current; }
        pointer operator->() const { return &*current; }
        
        iterator& operator++() {
            ++current;
            if (current == *anchor) ++winding;
            return *this;
        }
        
        iterator operator++(int) {
            iterator tmp = *this;
            ++*this;
            return tmp;
        }
        
        iterator& operator--() {
            if (current == *anchor) --winding;
            --current;
            return *this;
        }
        
        iterator operator--(int) {
            iterator tmp = *this;
            --*this;
            return tmp;
        }
        
        bool operator==(const iterator& i) const {
            return winding == i.winding && current == i.current;
        }
        
        bool operator!=(const iterator& i) const {
            return !(*this == i);
        }
        
        // 随机访问操作
        iterator& operator+=(difference_type n) {
            if (n > 0) {
                for (difference_type i = 0; i < n; ++i) ++*this;
            } else if (n < 0) {
                for (difference_type i = 0; i < -n; ++i) --*this;
            }
            return *this;
        }
        
        difference_type operator-(const iterator& i) const {
            // 计算两个迭代器之间的距离
            if (winding != i.winding) {
                return (winding - i.winding) * circulator_size(*anchor)
                     + (current - i.current);
            }
            return current - i.current;
        }
    };
    
    typedef iterator const_iterator;
 
private:
    C anchor;
 
public:
    Container_from_circulator() {}
    explicit Container_from_circulator(const C& c) : anchor(c) {}
    
    iterator begin() const { return iterator(anchor, 0); }
    iterator end() const { 
        // end()的winding为1，表示完成一圈
        return iterator(anchor, 1); 
    }
    
    bool empty() const { return anchor.is_empty(); }
    size_type size() const { return circulator_size(anchor); }
};

3.3 半边结构中的Circulator应用

// 文件: CGAL/HalfedgeDS_iterator.h
 
// 面边界Circulator
template<typename H>
class Face_circulator {
    typedef Face_circulator<H> Self;
public:
    typedef H Halfedge_handle;
    typedef typename H::value_type value_type;
    typedef typename H::reference reference;
    typedef typename H::pointer pointer;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef Bidirectional_circulator_tag iterator_category;
 
private:
    Halfedge_handle start;   // 起始半边
    Halfedge_handle current; // 当前半边
 
public:
    Face_circulator() : start(), current() {}
    
    explicit Face_circulator(Halfedge_handle h) 
        : start(h), current(h) {}
    
    reference operator*() const { return *current; }
    pointer operator->() const { return &*current; }
    
    // 绕面遍历：使用next()
    Self& operator++() {
        current = current->next();
        return *this;
    }
    
    Self operator++(int) {
        Self tmp = *this;
        ++*this;
        return tmp;
    }
    
    Self& operator--() {
        current = current->prev();
        return *this;
    }
    
    Self operator--(int) {
        Self tmp = *this;
        --*this;
        return tmp;
    }
    
    // 检查是否完成完整循环
    bool operator==(const Self& c) const { return current == c.current; }
    bool operator!=(const Self& c) const { return !(*this == c); }
    
    // 获取当前半边
    Halfedge_handle halfedge() const { return current; }
    
    // 获取顶点
    auto vertex() const { return current->vertex(); }
    
    // 获取对边
    auto opposite() const { return current->opposite(); }
};
 
// 顶点one-ring Circulator
template<typename H>
class Vertex_circulator {
    typedef Vertex_circulator<H> Self;
public:
    typedef H Halfedge_handle;
    typedef typename H::value_type value_type;
    typedef typename H::reference reference;
    typedef typename H::pointer pointer;
    typedef Bidirectional_circulator_tag iterator_category;
 
private:
    Halfedge_handle start;   // 起始半边（指向中心顶点的半边）
    Halfedge_handle current; // 当前半边
 
public:
    Vertex_circulator() : start(), current() {}
    
    // 从指向中心顶点的半边构造
    explicit Vertex_circulator(Halfedge_handle h) 
        : start(h), current(h) {}
    
    reference operator*() const { return *current; }
    pointer operator->() const { return &*current; }
    
    // 绕顶点遍历：opposite() -> next()
    Self& operator++() {
        current = current->opposite()->next();
        return *this;
    }
    
    Self operator++(int) {
        Self tmp = *this;
        ++*this;
        return tmp;
    }
    
    Self& operator--() {
        current = current->prev()->opposite();
        return *this;
    }
    
    Self operator--(int) {
        Self tmp = *this;
        --*this;
        return tmp;
    }
    
    bool operator==(const Self& c) const { return current == c.current; }
    bool operator!=(const Self& c) const { return !(*this == c); }
    
    Halfedge_handle halfedge() const { return current; }
    
    // 获取相邻顶点（不是中心顶点）
    auto vertex() const { return current->opposite()->vertex(); }
    
    // 获取相邻面
    auto face() const { return current->face(); }
};

4. 使用示例

4.1 示例1：多边形顶点循环遍历

#include <CGAL/circulator.h>
#include <vector>
#include <iostream>
#include <math>
 
typedef std::pair<double, double> Point_2;
 
// 计算多边形面积（使用Circulator）
template<typename Circulator>
double polygon_area(Circulator c) {
    double area = 0.0;
    Circulator start = c;
    
    do {
        Circulator next = c;
        ++next;
        // 叉积公式: (x1*y2 - x2*y1) / 2
        area += (*c).first * (*next).second - (*next).first * (*c).second;
        ++c;
    } while (c != start);
    
    return std::abs(area) / 2.0;
}
 
// 计算多边形周长
template<typename Circulator>
double polygon_perimeter(Circulator c) {
    double perimeter = 0.0;
    Circulator start = c;
    
    do {
        Circulator next = c;
        ++next;
        double dx = (*next).first - (*c).first;
        double dy = (*next).second - (*c).second;
        perimeter += std::sqrt(dx * dx + dy * dy);
        ++c;
    } while (c != start);
    
    return perimeter;
}
 
int main() {
    // 创建多边形顶点（正方形）
    std::vector<Point_2> polygon = {
        {0.0, 0.0},
        {1.0, 0.0},
        {1.0, 1.0},
        {0.0, 1.0}
    };
    
    // 使用Circulator_from_iterator创建Circulator
    typedef CGAL::Circulator_from_iterator<std::vector<Point_2>::iterator>
        Polygon_circulator;
    
    Polygon_circulator circ(polygon.begin(), polygon.end());
    
    std::cout << "Polygon vertices (2 rounds):" << std::endl;
    int count = 0;
    Polygon_circulator c = circ;
    do {
        std::cout << "  (" << (*c).first << ", " << (*c).second << ")" << std::endl;
        ++c;
        ++count;
    } while (c != circ && count < 8);  // 遍历两圈
    
    std::cout << "\nArea: " << polygon_area(circ) << std::endl;
    std::cout << "Perimeter: " << polygon_perimeter(circ) << std::endl;
    
    return 0;
}

4.2 示例2：面的邻居遍历（Surface_mesh）

#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Face_index Face_index;
typedef Mesh::Halfedge_index Halfedge_index;
typedef Mesh::Vertex_index Vertex_index;
 
// 获取面的邻居数量
std::size_t count_face_neighbors(const Mesh& mesh, Face_index f) {
    std::size_t count = 0;
    
    // 遍历面的所有半边
    for (Halfedge_index h : mesh.halfedges_around_face(mesh.halfedge(f))) {
        Halfedge_index opp = mesh.opposite(h);
        if (!mesh.is_border(opp)) {
            ++count;
        }
    }
    
    return count;
}
 
// 打印面的所有邻居
template<typename Mesh>
void print_face_neighbors(const Mesh& mesh, typename Mesh::Face_index f) {
    std::cout << "Face " << f << " neighbors:" << std::endl;
    
    for (auto h : mesh.halfedges_around_face(mesh.halfedge(f))) {
        auto opp = mesh.opposite(h);
        if (!mesh.is_border(opp)) {
            auto neighbor_face = mesh.face(opp);
            std::cout << "  - Face " << neighbor_face << std::endl;
        } else {
            std::cout << "  - Border edge" << std::endl;
        }
    }
}
 
// 计算顶点的度数（邻居顶点数）
template<typename Mesh>
std::size_t vertex_degree(const Mesh& mesh, typename Mesh::Vertex_index v) {
    std::size_t degree = 0;
    
    // 使用Surface_mesh的circulator遍历one-ring
    for (auto h : mesh.halfedges_around_target(mesh.halfedge(v))) {
        (void)h;  // 仅计数
        ++degree;
    }
    
    return degree;
}
 
// 计算顶点one-ring的平均边长
template<typename Mesh>
double average_edge_length(const Mesh& mesh, typename Mesh::Vertex_index v) {
    double total_length = 0.0;
    std::size_t count = 0;
    
    auto point = mesh.point(v);
    
    for (auto h : mesh.halfedges_around_target(mesh.halfedge(v))) {
        auto neighbor = mesh.source(h);
        auto neighbor_point = mesh.point(neighbor);
        total_length += CGAL::sqrt(CGAL::squared_distance(point, neighbor_point));
        ++count;
    }
    
    return count > 0 ? total_length / count : 0.0;
}
 
int main() {
    Mesh mesh;
    
    // 创建一个简单的四面体
    Vertex_index v0 = mesh.add_vertex(Point_3(0, 0, 0));
    Vertex_index v1 = mesh.add_vertex(Point_3(1, 0, 0));
    Vertex_index v2 = mesh.add_vertex(Point_3(0, 1, 0));
    Vertex_index v3 = mesh.add_vertex(Point_3(0, 0, 1));
    
    // 添加面
    mesh.add_face(v0, v1, v2);
    mesh.add_face(v0, v1, v3);
    mesh.add_face(v0, v2, v3);
    mesh.add_face(v1, v2, v3);
    
    std::cout << "Mesh has " << mesh.number_of_faces() << " faces" << std::endl;
    
    // 遍历所有面并打印邻居信息
    for (auto f : mesh.faces()) {
        std::cout << "\n";
        print_face_neighbors(mesh, f);
        std::cout << "  Number of neighbors: " << count_face_neighbors(mesh, f) << std::endl;
    }
    
    // 打印顶点信息
    std::cout << "\nVertex information:" << std::endl;
    for (auto v : mesh.vertices()) {
        std::cout << "Vertex " << v << ":" << std::endl;
        std::cout << "  Degree: " << vertex_degree(mesh, v) << std::endl;
        std::cout << "  Avg edge length: " << average_edge_length(mesh, v) << std::endl;
    }
    
    return 0;
}

4.3 示例3：自定义Circulator实现

#include <CGAL/circulator.h>
#include <vector>
#include <iostream>
#include <memory>
 
// 环形缓冲区（Circular Buffer）实现
template<typename T>
class Circular_buffer {
    std::vector<T> data;
    std::size_t head;  // 写入位置
    std::size_t tail;  // 读取位置
    std::size_t count; // 当前元素数
    
public:
    explicit Circular_buffer(std::size_t capacity) 
        : data(capacity), head(0), tail(0), count(0) {}
    
    void push(const T& value) {
        data[head] = value;
        head = (head + 1) % data.size();
        if (count < data.size()) {
            ++count;
        } else {
            tail = head;  // 覆盖旧数据
        }
    }
    
    bool empty() const { return count == 0; }
    std::size_t size() const { return count; }
    std::size_t capacity() const { return data.size(); }
    
    // Circulator声明
    class circulator;
    friend class circulator;
    
    class circulator {
        typedef circulator Self;
    public:
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef std::ptrdiff_t difference_type;
        typedef std::size_t size_type;
        typedef CGAL::Bidirectional_circulator_tag iterator_category;
        
    private:
        Circular_buffer* buffer;
        std::size_t pos;
        
    public:
        circulator() : buffer(nullptr), pos(0) {}
        
        circulator(Circular_buffer* b, std::size_t p) 
            : buffer(b), pos(p) {}
        
        reference operator*() const {
            return buffer->data[pos];
        }
        
        pointer operator->() const {
            return &buffer->data[pos];
        }
        
        Self& operator++() {
            pos = (pos + 1) % buffer->capacity();
            return *this;
        }
        
        Self operator++(int) {
            Self tmp = *this;
            ++*this;
            return tmp;
        }
        
        Self& operator--() {
            pos = (pos + buffer->capacity() - 1) % buffer->capacity();
            return *this;
        }
        
        Self operator--(int) {
            Self tmp = *this;
            --*this;
            return tmp;
        }
        
        bool operator==(const Self& c) const {
            return buffer == c.buffer && pos == c.pos;
        }
        
        bool operator!=(const Self& c) const {
            return !(*this == c);
        }
        
        // 获取当前索引
        std::size_t index() const { return pos; }
    };
    
    circulator begin() {
        return circulator(this, tail);
    }
    
    // 遍历所有元素
    template<typename Func>
    void for_each(Func f) {
        if (empty()) return;
        auto c = begin();
        std::size_t n = 0;
        do {
            f(*c);
            ++c;
            ++n;
        } while (n < count);
    }
};
 
int main() {
    Circular_buffer<int> buffer(5);
    
    // 添加元素
    for (int i = 1; i <= 7; ++i) {
        buffer.push(i);
        std::cout << "Pushed: " << i << ", Size: " << buffer.size() << std::endl;
    }
    
    // 使用Circulator遍历
    std::cout << "\nBuffer contents (using circulator):" << std::endl;
    auto circ = buffer.begin();
    for (std::size_t i = 0; i < buffer.size(); ++i) {
        std::cout << *circ << " ";
        ++circ;
    }
    std::cout << std::endl;
    
    // 使用for_each遍历
    std::cout << "\nUsing for_each:" << std::endl;
    buffer.for_each([](int x) {
        std::cout << x << " ";
    });
    std::cout << std::endl;
    
    // 使用Container_from_circulator与STL算法
    typedef Circular_buffer<int>::circulator Circ;
    CGAL::Container_from_circulator<Circ> container(buffer.begin());
    
    std::cout << "\nUsing STL find:" << std::endl;
    auto it = std::find(container.begin(), container.end(), 6);
    if (it != container.end()) {
        std::cout << "Found 6!" << std::endl;
    }
    
    return 0;
}

4.4 示例4：双向Circulator和随机访问Circulator

#include <CGAL/circulator.h>
#include <vector>
#include <iostream>
#include <algorithm>
 
// 双向Circulator示例：双向链表节点
template<typename T>
struct Doubly_linked_node {
    T value;
    Doubly_linked_node* prev;
    Doubly_linked_node* next;
    
    Doubly_linked_node(const T& v) : value(v), prev(nullptr), next(nullptr) {}
};
 
template<typename T>
class Doubly_linked_list {
    Doubly_linked_node<T>* head;
    std::size_t count;
    
public:
    Doubly_linked_list() : head(nullptr), count(0) {}
    
    ~Doubly_linked_list() {
        if (!head) return;
        auto current = head;
        do {
            auto next = current->next;
            delete current;
            current = next;
        } while (current != head);
    }
    
    void push_back(const T& value) {
        auto node = new Doubly_linked_node<T>(value);
        if (!head) {
            node->prev = node->next = node;
            head = node;
        } else {
            node->next = head;
            node->prev = head->prev;
            head->prev->next = node;
            head->prev = node;
        }
        ++count;
    }
    
    // 双向Circulator
    class circulator {
        typedef circulator Self;
    public:
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef std::ptrdiff_t difference_type;
        typedef std::size_t size_type;
        typedef CGAL::Bidirectional_circulator_tag iterator_category;
        
    private:
        Doubly_linked_node<T>* node;
        
    public:
        circulator() : node(nullptr) {}
        explicit circulator(Doubly_linked_node<T>* n) : node(n) {}
        
        reference operator*() const { return node->value; }
        pointer operator->() const { return &node->value; }
        
        Self& operator++() {
            node = node->next;
            return *this;
        }
        
        Self operator++(int) {
            Self tmp = *this;
            ++*this;
            return tmp;
        }
        
        Self& operator--() {
            node = node->prev;
            return *this;
        }
        
        Self operator--(int) {
            Self tmp = *this;
            --*this;
            return tmp;
        }
        
        bool operator==(const Self& c) const { return node == c.node; }
        bool operator!=(const Self& c) const { return !(*this == c); }
        
        Doubly_linked_node<T>* base() const { return node; }
    };
    
    circulator begin() { return circulator(head); }
    std::size_t size() const { return count; }
    bool empty() const { return count == 0; }
};
 
// 随机访问Circulator示例：循环数组
template<typename T>
class Circular_array {
    std::vector<T> data;
    
public:
    explicit Circular_array(std::size_t n) : data(n) {}
    
    T& operator[](std::size_t i) { return data[i]; }
    const T& operator[](std::size_t i) const { return data[i]; }
    std::size_t size() const { return data.size(); }
    
    // 随机访问Circulator
    class circulator {
        typedef circulator Self;
    public:
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef std::ptrdiff_t difference_type;
        typedef std::size_t size_type;
        typedef CGAL::Random_access_circulator_tag iterator_category;
        
    private:
        Circular_array* array;
        std::size_t pos;
        
    public:
        circulator() : array(nullptr), pos(0) {}
        circulator(Circular_array* a, std::size_t p) : array(a), pos(p) {}
        
        reference operator*() const { return (*array)[pos]; }
        pointer operator->() const { return &(*array)[pos]; }
        
        Self& operator++() {
            pos = (pos + 1) % array->size();
            return *this;
        }
        
        Self operator++(int) {
            Self tmp = *this;
            ++*this;
            return tmp;
        }
        
        Self& operator--() {
            pos = (pos + array->size() - 1) % array->size();
            return *this;
        }
        
        Self operator--(int) {
            Self tmp = *this;
            --*this;
            return tmp;
        }
        
        // 随机访问操作
        Self& operator+=(difference_type n) {
            auto size = static_cast<difference_type>(array->size());
            pos = (pos + n) % size;
            if (pos < 0) pos += size;
            return *this;
        }
        
        Self operator+(difference_type n) const {
            Self tmp = *this;
            return tmp += n;
        }
        
        Self& operator-=(difference_type n) {
            return operator+=(-n);
        }
        
        Self operator-(difference_type n) const {
            Self tmp = *this;
            return tmp -= n;
        }
        
        difference_type operator-(const Self& c) const {
            return static_cast<difference_type>(pos) - 
                   static_cast<difference_type>(c.pos);
        }
        
        reference operator[](difference_type n) const {
            return *(*this + n);
        }
        
        bool operator==(const Self& c) const { 
            return array == c.array && pos == c.pos; 
        }
        
        bool operator!=(const Self& c) const { return !(*this == c); }
        bool operator<(const Self& c) const { return pos < c.pos; }
        bool operator>(const Self& c) const { return pos > c.pos; }
        
        // 获取最小Circulator（用于size计算）
        Self min_circulator() const {
            return Self(array, 0);
        }
    };
    
    circulator begin() { return circulator(this, 0); }
};
 
int main() {
    // 测试双向Circulator
    std::cout << "=== Doubly Linked List (Bidirectional Circulator) ===" << std::endl;
    Doubly_linked_list<int> list;
    for (int i = 1; i <= 5; ++i) {
        list.push_back(i);
    }
    
    auto circ = list.begin();
    std::cout << "Forward traversal: ";
    for (int i = 0; i < 10; ++i) {
        std::cout << *circ << " ";
        ++circ;
    }
    std::cout << std::endl;
    
    std::cout << "Backward traversal: ";
    for (int i = 0; i < 10; ++i) {
        std::cout << *circ << " ";
        --circ;
    }
    std::cout << std::endl;
    
    // 测试随机访问Circulator
    std::cout << "\n=== Circular Array (Random Access Circulator) ===" << std::endl;
    Circular_array<int> arr(5);
    for (std::size_t i = 0; i < 5; ++i) {
        arr[i] = static_cast<int>(i + 1) * 10;
    }
    
    auto arr_circ = arr.begin();
    std::cout << "Random access [0]: " << arr_circ[0] << std::endl;
    std::cout << "Random access [3]: " << arr_circ[3] << std::endl;
    std::cout << "Random access [7] (wraps): " << arr_circ[7] << std::endl;
    
    std::cout << "\nJump +3: ";
    arr_circ += 3;
    std::cout << *arr_circ << std::endl;
    
    std::cout << "Jump -2: ";
    arr_circ -= 2;
    std::cout << *arr_circ << std::endl;
    
    // 使用CGAL工具函数
    std::cout << "\nCirculator size: " << CGAL::circulator_size(arr.begin()) << std::endl;
    
    return 0;
}

5. 复杂度分析

5.1 时间复杂度

操作	Forward	Bidirectional	Random Access
构造	O(1)	O(1)	O(1)
解引用(*)	O(1)	O(1)	O(1)
递增(++)	O(1)	O(1)	O(1)
递减(—)	N/A	O(1)	O(1)
随机访问[n]	O(n)	O(n)	O(1)
距离计算	O(n)	O(n)	O(1)
circulator_size	O(n)	O(n)	O(1)
min_circulator	O(n)	O(n)	O(1)

5.2 空间复杂度

Circulator类型	额外空间	说明
Circulator_from_iterator	3 × sizeof(I)	begin, end, current
Circulator_from_container	sizeof(C*) + sizeof(Iter)	容器指针和迭代器
Container_from_circulator	sizeof(C) + sizeof(int)	锚点和绕数
自定义Face_circulator	2 × sizeof(H)	start和current
自定义Vertex_circulator	2 × sizeof(H)	start和current

5.3 与标准Iterator的对比

特性	Iterator	Circulator
终止条件	end()标记	循环回到起点
空范围	begin == end	nullptr或is_empty()
大小计算	end - begin	完整遍历或min_circulator
适用场景	线性容器	循环拓扑结构
STL算法兼容	直接兼容	需要Container_from_circulator

6. 关键文件位置

文件路径	说明
`STL_Extension/include/CGAL/circulator.h`	Circulator核心定义和适配器
`STL_Extension/include/CGAL/circulator_bases.h`	Circulator基类和标记
`STL_Extension/include/CGAL/Circulator_identity.h`	恒等Circulator适配器
`STL_Extension/include/CGAL/Circulator_on_node.h`	节点Circulator
`STL_Extension/include/CGAL/Circulator_project.h`	投影Circulator
`HalfedgeDS/include/CGAL/HalfedgeDS_iterator.h`	半边结构专用Circulator
`Surface_mesh/include/CGAL/Surface_mesh.h`	Surface_mesh的Circulator接口

7. 最佳实践

7.1 使用建议

选择合适的Circulator类别：
- 仅需要前向遍历：使用Forward_circulator
- 需要双向遍历：使用Bidirectional_circulator
- 需要随机访问：使用Random_access_circulator

使用Container_from_circulator与STL算法协作：

CGAL::Container_from_circulator<Circ> container(circ);
std::sort(container.begin(), container.end());

注意Circulator的生命周期： Circulator不拥有底层数据，确保底层结构在使用期间有效。

使用CGAL_For_all宏简化循环：

CGAL_For_all(circ1, circ2) {
    // 处理*circ1
}

7.2 常见陷阱

无限循环：

// 错误：没有终止条件
while (true) { ++circ; }
 
// 正确：检查是否回到起点
auto start = circ;
do { ++circ; } while (circ != start);

空Circulator检查：

// 错误：直接解引用
*circ;
 
// 正确：先检查
if (!circ.is_empty()) *circ;

随机访问Circulator的size计算：使用min_circulator()获取最小元素位置，以便正确计算size。

Chunibyo

Explorer

3.2 循环迭代器（Circulator）

3.2 循环迭代器（Circulator）

1. 理论基础

1.1 循环数据结构的数学定义

1.2 Circulator与Iterator的数学对比

1.3 半边结构中的循环遍历

2. 架构分析

2.1 Circulator概念层次

2.2 Circulator核心接口

2.3 适配器设计模式

3. 实现细节

3.1 Circulator_from_iterator实现

3.2 Container_from_circulator实现

3.3 半边结构中的Circulator应用

4. 使用示例

4.1 示例1：多边形顶点循环遍历

4.2 示例2：面的邻居遍历（Surface_mesh）

4.3 示例3：自定义Circulator实现

4.4 示例4：双向Circulator和随机访问Circulator

5. 复杂度分析

5.1 时间复杂度

5.2 空间复杂度

5.3 与标准Iterator的对比

6. 关键文件位置

7. 最佳实践

7.1 使用建议

7.2 常见陷阱

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

3.2 循环迭代器（Circulator）

3.2 循环迭代器（Circulator） §

1. 理论基础 §

1.1 循环数据结构的数学定义 §

1.2 Circulator与Iterator的数学对比 §

1.3 半边结构中的循环遍历 §

2. 架构分析 §

2.1 Circulator概念层次 §

2.2 Circulator核心接口 §

2.3 适配器设计模式 §

3. 实现细节 §

3.1 Circulator_from_iterator实现 §

3.2 Container_from_circulator实现 §

3.3 半边结构中的Circulator应用 §

4. 使用示例 §

4.1 示例1：多边形顶点循环遍历 §

4.2 示例2：面的邻居遍历（Surface_mesh） §

4.3 示例3：自定义Circulator实现 §

4.4 示例4：双向Circulator和随机访问Circulator §

5. 复杂度分析 §

5.1 时间复杂度 §

5.2 空间复杂度 §

5.3 与标准Iterator的对比 §

6. 关键文件位置 §

7. 最佳实践 §

7.1 使用建议 §

7.2 常见陷阱 §

Graph View

Table of Contents

Backlinks

3.2 循环迭代器（Circulator）

1. 理论基础

1.1 循环数据结构的数学定义

1.2 Circulator与Iterator的数学对比

1.3 半边结构中的循环遍历

2. 架构分析

2.1 Circulator概念层次

2.2 Circulator核心接口

2.3 适配器设计模式

3. 实现细节

3.1 Circulator_from_iterator实现

3.2 Container_from_circulator实现

3.3 半边结构中的Circulator应用

4. 使用示例

4.1 示例1：多边形顶点循环遍历

4.2 示例2：面的邻居遍历（Surface_mesh）

4.3 示例3：自定义Circulator实现

4.4 示例4：双向Circulator和随机访问Circulator

5. 复杂度分析

5.1 时间复杂度

5.2 空间复杂度

5.3 与标准Iterator的对比

6. 关键文件位置

7. 最佳实践

7.1 使用建议

7.2 常见陷阱