/* */ #ifndef D_INDEXED_LIST_H #define D_INDEXED_LIST_H #include "common.h" #include #include #include #include #include namespace aria2 { template struct IndexedListIterator { typedef IndexedListIterator iterator; typedef IndexedListIterator const_iterator; typedef typename SeqIteratorType::iterator_category iterator_category; typedef ValueType value_type; typedef PointerType pointer; typedef ReferenceType reference; typedef typename SeqType::size_type size_type; typedef typename SeqType::difference_type difference_type; typedef IndexedListIterator SelfType; IndexedListIterator() {} IndexedListIterator(const iterator& other) : p(other.p) {} IndexedListIterator(const SeqIteratorType& p) : p(p) {} reference operator*() const { return (*p).second; } pointer operator->() const { return &(*p).second; } SelfType& operator++() { ++p; return *this; } SelfType operator++(int) { SelfType copy = *this; ++*this; return copy; } SelfType& operator--() { --p; return *this; } SelfType operator--(int) { SelfType copy = *this; --*this; return copy; } SelfType& operator+=(difference_type n) { std::advance(p, n); return *this; } SelfType operator+(difference_type n) const { SelfType copy = *this; return copy += n; } SelfType& operator-=(difference_type n) { std::advance(p, -n); return *this; } SelfType operator-(difference_type n) const { SelfType copy = *this; return copy -= n; } reference operator[](size_type n) const { return p[n].second; } SeqIteratorType p; }; template bool operator==(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p == rhs.p; } template bool operator==(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p == rhs.p; } template bool operator!=(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p != rhs.p; } template bool operator!=(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p != rhs.p; } template bool operator<(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p < rhs.p; } template bool operator<(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p < rhs.p; } template bool operator>(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p > rhs.p; } template bool operator>(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p > rhs.p; } template bool operator<=(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p <= rhs.p; } template bool operator<=(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p <= rhs.p; } template bool operator>=(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p >= rhs.p; } template bool operator>=(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return lhs.p >= rhs.p; } template IndexedListIterator operator+(typename IndexedListIterator::difference_type n, const IndexedListIterator& lhs) { return lhs + n; } template typename IndexedListIterator::difference_type operator-(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return typename IndexedListIterator::difference_type (lhs.p - rhs.p); } template typename IndexedListIterator::difference_type operator-(const IndexedListIterator& lhs, const IndexedListIterator& rhs) { return typename IndexedListIterator::difference_type (lhs.p - rhs.p); } template class IndexedList { public: IndexedList() {} ~IndexedList() {} typedef KeyType key_type; typedef ValuePtrType value_type; typedef std::unordered_map IndexType; typedef std::deque> SeqType; typedef IndexedListIterator iterator; typedef IndexedListIterator const_iterator; ValuePtrType& operator[](size_t n) { return seq_[n].second; } const ValuePtrType& operator[](size_t n) const { return seq_[n].second; } // Inserts (|key|, |value|) to the end of the list. If the same key // has been already added, this function fails. This function // returns true if it succeeds. Complexity: O(1) bool push_back(KeyType key, ValuePtrType value) { auto i = index_.find(key); if(i == std::end(index_)) { index_.insert({key, value}); seq_.emplace_back(key, value); return true; } else { return false; } } // Inserts (|key|, |value|) to the front of the list. If the same // key has been already added, this function fails. This function // returns true if it succeeds. Complexity: O(1) bool push_front(KeyType key, ValuePtrType value) { auto i = index_.find(key); if(i == std::end(index_)) { index_.insert({key, value}); seq_.emplace_front(key, value); return true; } else { return false; } } // Inserts (|key|, |value|) to the position |dest|. If the same key // has been already added, this function fails. This function // returns the iterator to the newly added element if it is // succeeds, or end(). Complexity: O(N) iterator insert(size_t dest, KeyType key, ValuePtrType value) { if(dest > size()) { return std::end(seq_); } auto i = index_.find(key); if(i == std::end(index_)) { auto j = std::begin(seq_); std::advance(j, dest); index_.insert({key, value}); return iterator(seq_.insert(j, {key, value})); } else { return iterator(std::end(seq_)); } } // Inserts (|key|, |value|) to the position |dest|. If the same key // has been already added, this function fails. This function // returns the iterator to the newly added element if it is // succeeds, or end(). Complexity: O(1) if inserted to the first or // last, otherwise O(N) iterator insert(iterator dest, KeyType key, ValuePtrType value) { auto i = index_.find(key); if(i == std::end(index_)) { index_.insert({key, value}); return iterator(seq_.insert(dest.p, {key, value})); } else { return iterator(std::end(seq_)); } } // Inserts values in iterator range [first, last). The key for each // value is retrieved by functor |keyFunc|. The insertion position // is given by |dest|. template void insert(iterator dest, KeyFunc keyFunc, InputIterator first, InputIterator last) { std::vector v; v.reserve(std::distance(first, last)); for(; first != last; ++first) { auto key = keyFunc(*first); auto i = index_.find(key); if(i == std::end(index_)) { index_.insert({key, *first}); v.emplace_back(key, *first); } } seq_.insert(dest.p, std::begin(v), std::end(v)); } template void insert(size_t pos, KeyFunc keyFunc, InputIterator first, InputIterator last) { if(pos > size()) { return; } std::vector v; v.reserve(std::distance(first, last)); for(; first != last; ++first) { auto key = keyFunc(*first); auto i = index_.find(key); if(i == std::end(index_)) { index_.insert({key, *first}); v.emplace_back(key, *first); } } seq_.insert(std::begin(seq_) + pos, std::begin(v), std::end(v)); } // Removes |key| from the list. If the element is not found, this // function fails. This function returns true if it // succeeds. Complexity: O(N) bool remove(KeyType key) { auto i = index_.find(key); if(i == std::end(index_)) { return false; } for(auto j = std::begin(seq_), eoj = std::end(seq_); j != eoj; ++j) { if((*j).first == key) { seq_.erase(j); break; } } index_.erase(i); return true; } // Removes element pointed by iterator |k| from the list. If the // iterator must be valid. This function returns the iterator // pointing to the element following the erased element. Complexity: // O(N) iterator erase(iterator k) { index_.erase((*k.p).first); return iterator(seq_.erase(k.p)); } // Removes elements for which Pred returns true. The pred is called // against each each element once per each. template void remove_if(Pred pred) { auto first = std::begin(seq_), last = std::end(seq_); for(; first != last && !pred((*first).second); ++first); if(first == last) { return; } index_.erase((*first).first); auto store = first; ++first; for(; first != last; ++first) { if(pred((*first).second)) { index_.erase((*first).first); } else { *store++ = *first; } } seq_.erase(store, last); } // Removes element at the front of the list. If the list is empty, // this function fails. This function returns true if it // succeeds. Complexity: O(1) bool pop_front() { if(seq_.empty()) { return false; } index_.erase(seq_.front().first); seq_.pop_front(); return true; } // Moves element with |key| to the specified position. If |how| is // OFFSET_MODE_CUR, the element is moved to the position |offset| // relative to the current position. If |how| is OFFSET_MODE_SET, // the element is moved to the position |offset|. If |how| is // OFFSET_MODE_END, the element is moved to the position |offset| // relative to the end of the list. This function returns the // position the elment is moved to if it succeeds, or -1 if no // element with |key| is found or |how| is invalid. Complexity: // O(N) ssize_t move(KeyType key, ssize_t offset, OffsetMode how) { auto idxent = index_.find(key); if(idxent == std::end(index_)) { return -1; } auto x = std::begin(seq_), eseq = std::end(seq_); for(; x != eseq; ++x) { if((*x).first == (*idxent).first) { break; } } ssize_t xp = std::distance(std::begin(seq_), x); ssize_t size = index_.size(); ssize_t dest; if(how == OFFSET_MODE_CUR) { if(offset > 0) { dest = std::min(xp+offset, static_cast(size-1)); } else { dest = std::max(xp+offset, static_cast(0)); } } else { if(how == OFFSET_MODE_END) { dest = std::min(size-1+offset, size-1); } else if(how == OFFSET_MODE_SET) { dest = std::min(offset, size-1); } else { return -1; } dest = std::max(dest, static_cast(0)); } auto d = std::begin(seq_); std::advance(d, dest); if(xp < dest) { std::rotate(x, x+1, d+1); } else { std::rotate(d, x, x+1); } return dest; } // Returns the value associated by |key|. If it is not found, // returns ValuePtrType(). Complexity: O(1) ValuePtrType get(KeyType key) const { auto idxent = index_.find(key); if(idxent == std::end(index_)) { return ValuePtrType(); } else { return (*idxent).second; } } size_t size() const { return index_.size(); } size_t empty() const { return index_.empty(); } iterator begin() { return iterator(std::begin(seq_)); } iterator end() { return iterator(std::end(seq_)); } const_iterator begin() const { return const_iterator(std::begin(seq_)); } const_iterator end() const { return const_iterator(std::end(seq_)); } // Removes all elements from the list. void clear() { index_.clear(); seq_.clear(); } private: SeqType seq_; IndexType index_; }; } // namespace aria2 #endif // D_INDEXED_LIST_H