1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// Standalone implementation of iterator utilities.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIBC_SRC___SUPPORT_CPP_ITERATOR_H
15#define LLVM_LIBC_SRC___SUPPORT_CPP_ITERATOR_H
16
17#include <stddef.h> // For ptrdiff_t
18
19#include "hdr/types/size_t.h"
20#include "src/__support/CPP/type_traits/enable_if.h"
21#include "src/__support/CPP/type_traits/is_convertible.h"
22#include "src/__support/CPP/type_traits/is_same.h"
23#include "src/__support/macros/attributes.h"
24#include "src/__support/macros/config.h"
25
26namespace LIBC_NAMESPACE_DECL {
27namespace cpp {
28
29struct input_iterator_tag {};
30struct random_access_iterator_tag : input_iterator_tag {};
31
32template <typename T> struct iterator_traits;
33template <typename T> struct iterator_traits<T *> {
34 using difference_type = ptrdiff_t;
35 using value_type = T;
36 using pointer = T *;
37 using reference = T &;
38 using iterator_category = random_access_iterator_tag;
39};
40
41template <typename Iter> class reverse_iterator {
42 Iter current;
43
44public:
45 using iterator_type = Iter;
46 using difference_type = typename iterator_traits<Iter>::difference_type;
47 using value_type = typename iterator_traits<Iter>::value_type;
48 using pointer = typename iterator_traits<Iter>::pointer;
49 using reference = typename iterator_traits<Iter>::reference;
50
51 LIBC_INLINE constexpr reverse_iterator() : current() {}
52 LIBC_INLINE constexpr explicit reverse_iterator(Iter it) : current(it) {}
53
54 template <typename Other,
55 cpp::enable_if_t<!cpp::is_same_v<Iter, Other> &&
56 cpp::is_convertible_v<const Other &, Iter>,
57 int> = 0>
58 LIBC_INLINE constexpr reverse_iterator(const reverse_iterator<Other> &other)
59 : current(other.base()) {}
60
61 template <typename Other,
62 cpp::enable_if_t<!cpp::is_same_v<Iter, Other> &&
63 cpp::is_convertible_v<const Other &, Iter>,
64 int> = 0>
65 LIBC_INLINE constexpr explicit reverse_iterator(const Other &it)
66 : current(it) {}
67
68 LIBC_INLINE friend constexpr bool operator==(const reverse_iterator &lhs,
69 const reverse_iterator &rhs) {
70 return lhs.base() == rhs.base();
71 }
72
73 LIBC_INLINE friend constexpr bool operator!=(const reverse_iterator &lhs,
74 const reverse_iterator &rhs) {
75 return lhs.base() != rhs.base();
76 }
77
78 LIBC_INLINE friend constexpr bool operator<(const reverse_iterator &lhs,
79 const reverse_iterator &rhs) {
80 return lhs.base() > rhs.base();
81 }
82
83 LIBC_INLINE friend constexpr bool operator<=(const reverse_iterator &lhs,
84 const reverse_iterator &rhs) {
85 return lhs.base() >= rhs.base();
86 }
87
88 LIBC_INLINE friend constexpr bool operator>(const reverse_iterator &lhs,
89 const reverse_iterator &rhs) {
90 return lhs.base() < rhs.base();
91 }
92
93 LIBC_INLINE friend constexpr bool operator>=(const reverse_iterator &lhs,
94 const reverse_iterator &rhs) {
95 return lhs.base() <= rhs.base();
96 }
97
98 LIBC_INLINE constexpr iterator_type base() const { return current; }
99
100 LIBC_INLINE constexpr reference operator*() const {
101 Iter tmp = current;
102 return *--tmp;
103 }
104
105 LIBC_INLINE constexpr pointer operator->() const {
106 Iter tmp = current;
107 return --tmp;
108 }
109
110 LIBC_INLINE constexpr reference operator[](difference_type n) const {
111 return *(*this + n);
112 }
113
114 LIBC_INLINE constexpr reverse_iterator &operator--() {
115 ++current;
116 return *this;
117 }
118
119 LIBC_INLINE constexpr reverse_iterator operator--(int) {
120 reverse_iterator tmp(*this);
121 ++current;
122 return tmp;
123 }
124
125 LIBC_INLINE constexpr reverse_iterator &operator++() {
126 --current;
127 return *this;
128 }
129
130 LIBC_INLINE constexpr reverse_iterator operator++(int) {
131 reverse_iterator tmp(*this);
132 --current;
133 return tmp;
134 }
135
136 LIBC_INLINE constexpr reverse_iterator operator+(difference_type n) const {
137 return reverse_iterator(current - n);
138 }
139
140 LIBC_INLINE constexpr reverse_iterator &operator+=(difference_type n) {
141 current -= n;
142 return *this;
143 }
144
145 LIBC_INLINE constexpr reverse_iterator operator-(difference_type n) const {
146 return reverse_iterator(current + n);
147 }
148
149 LIBC_INLINE constexpr reverse_iterator &operator-=(difference_type n) {
150 current += n;
151 return *this;
152 }
153
154 LIBC_INLINE friend constexpr difference_type
155 operator-(const reverse_iterator &lhs, const reverse_iterator &rhs) {
156 return rhs.base() - lhs.base();
157 }
158};
159
160namespace cpp_internal {
161
162template <typename It>
163LIBC_INLINE constexpr size_t distance(It first, It last,
164 random_access_iterator_tag) {
165 return last - first;
166}
167
168template <typename It>
169LIBC_INLINE constexpr auto distance(It first, It last, input_iterator_tag) {
170 size_t n = 0;
171 for (; first != last; ++first)
172 ++n;
173 return n;
174}
175
176} // namespace cpp_internal
177
178template <typename It> LIBC_INLINE constexpr auto distance(It first, It last) {
179 return cpp_internal::distance(
180 first, last, typename iterator_traits<It>::iterator_category{});
181}
182
183} // namespace cpp
184} // namespace LIBC_NAMESPACE_DECL
185
186#endif // LLVM_LIBC_SRC___SUPPORT_CPP_ITERATOR_H
187