1#ifndef SOURCEMETA_CORE_JSON_OBJECT_H_
2#define SOURCEMETA_CORE_JSON_OBJECT_H_
8#include <initializer_list>
15namespace sourcemeta::core {
19template <
typename Key,
typename Value,
typename Hash>
class JSONObject {
21 JSONObject() =
default;
24 using mapped_type = Value;
25 using hash_type = Hash::HashType;
26 using pair_value_type = std::pair<key_type, mapped_type>;
28 using KeyView = std::basic_string_view<
typename Key::value_type,
29 typename Key::traits_type>;
32 JSONObject(std::initializer_list<pair_value_type> entries) : data_{} {
33 this->data_.reserve(entries.size());
34 for (
auto &&entry : entries) {
35 this->
emplace(std::move(entry.first), std::move(entry.second));
63 const hash_type key_hash)
const ->
bool {
67 return this->hash == key_hash &&
68 (HASHER.is_perfect(key_hash) || this->first == key);
81 using underlying_type = std::vector<Entry>;
82 using value_type = underlying_type::value_type;
83 using size_type = underlying_type::size_type;
84 using difference_type = underlying_type::difference_type;
85 using allocator_type = underlying_type::allocator_type;
86 using reference = underlying_type::reference;
87 using const_reference = underlying_type::const_reference;
88 using pointer = underlying_type::pointer;
89 using const_pointer = underlying_type::const_pointer;
90 using const_iterator = underlying_type::const_iterator;
104 if (this->data_.size() != other.data_.size()) {
105 return this->data_.size() < other.data_.size();
108 const Key *decisive_key{
nullptr};
109 bool decision{
false};
110 for (
const auto &entry : this->data_) {
111 const auto match{other.find(entry.first)};
112 const bool differs{match == other.cend() ||
113 !(entry.second == match->second)};
114 if (differs && (decisive_key ==
nullptr || entry.first < *decisive_key)) {
115 decisive_key = &entry.first;
116 decision = match == other.cend() || entry.second < match->second;
123 for (
const auto &entry : other.data_) {
124 if (this->
find(entry.first) == this->cend() &&
125 (decisive_key ==
nullptr || entry.first < *decisive_key)) {
126 decisive_key = &entry.first;
134 auto operator<=(
const JSONObject<Key, Value, Hash> &other)
const noexcept
136 return !(other < *
this);
138 auto operator>(
const JSONObject<Key, Value, Hash> &other)
const noexcept
140 return other < *
this;
142 auto operator>=(
const JSONObject<Key, Value, Hash> &other)
const noexcept
144 return !(*
this < other);
147 auto operator==(
const JSONObject<Key, Value, Hash> &other)
const noexcept
149 if (this->
size() != other.size()) {
153 for (
const auto &entry : this->data_) {
154 const auto *result{other.try_at(entry.first, entry.hash)};
155 if ((result ==
nullptr) || *result != entry.second) {
163 auto operator!=(
const JSONObject<Key, Value, Hash> &other)
const noexcept
166 [[nodiscard]]
auto begin() const noexcept -> const_iterator {
167 return this->data_.begin();
170 [[nodiscard]]
auto end() const noexcept -> const_iterator {
171 return this->data_.end();
174 [[nodiscard]]
auto cbegin() const noexcept -> const_iterator {
175 return this->data_.cbegin();
178 [[nodiscard]]
auto cend() const noexcept -> const_iterator {
179 return this->data_.cend();
190 [[nodiscard]]
static constexpr auto hash(
const Key &key)
noexcept
196 template <
typename T>
197 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
198 [[nodiscard]]
static constexpr auto hash(T key)
noexcept -> hash_type {
199 return HASHER(key.data(), key.size());
203 [[nodiscard]]
static constexpr auto hash(
const char *raw_data,
204 const std::size_t raw_size)
noexcept
206 return HASHER(raw_data, raw_size);
210 [[nodiscard]]
auto find(
const Key &key)
const -> const_iterator {
211 return this->
find(key, this->
hash(key));
215 template <
typename T>
216 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
217 [[nodiscard]]
auto find(T key)
const -> const_iterator {
218 return this->
find(key, this->
hash(key));
238 [[nodiscard]]
auto find(
const Key &key,
const hash_type key_hash)
const
240 assert(this->
hash(key) == key_hash);
243 if (this->HASHER.is_perfect(key_hash)) {
244 for (size_type index = 0; index < this->
size(); index++) {
245 if (this->data_[index].
hash == key_hash) {
246 auto iterator{this->cbegin()};
247 std::advance(iterator, index);
252 for (size_type index = 0; index < this->
size(); index++) {
253 if (this->data_[index].
hash == key_hash &&
254 this->data_[index].first == key) {
255 auto iterator{this->cbegin()};
256 std::advance(iterator, index);
268 template <
typename T>
269 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
270 [[nodiscard]]
auto find(T key,
const hash_type key_hash)
const
272 assert(this->
hash(key) == key_hash);
275 if (this->HASHER.is_perfect(key_hash)) {
276 for (size_type index = 0; index < this->
size(); index++) {
277 if (this->data_[index].
hash == key_hash) {
278 auto iterator{this->cbegin()};
279 std::advance(iterator, index);
284 for (size_type index = 0; index < this->
size(); index++) {
285 if (this->data_[index].
hash == key_hash &&
286 this->data_[index].first == key) {
287 auto iterator{this->cbegin()};
288 std::advance(iterator, index);
298 [[nodiscard]]
auto defines(
const Key &key,
const hash_type
hash)
const
303 if (this->HASHER.is_perfect(
hash)) {
304 for (
const auto &entry : *
this) {
305 if (entry.hash ==
hash) {
310 for (
const auto &entry : *
this) {
311 if (entry.hash ==
hash && entry.first == key) {
321 template <
typename T>
322 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
323 [[nodiscard]]
auto defines(T key,
const hash_type
hash)
const ->
bool {
327 if (this->HASHER.is_perfect(
hash)) {
328 for (
const auto &entry : *
this) {
329 if (entry.hash ==
hash) {
334 for (
const auto &entry : *
this) {
335 if (entry.hash ==
hash && entry.first == key) {
345 [[nodiscard]]
auto size() const -> std::
size_t {
return this->data_.size(); }
348 [[nodiscard]]
auto empty() const ->
bool {
return this->data_.empty(); }
351 auto reserve(
const size_type capacity) ->
void {
352 this->data_.reserve(capacity);
356 [[nodiscard]]
auto at(
const size_type index)
const ->
const Entry & {
357 assert(index < this->data_.size());
358 return this->data_[index];
362 [[nodiscard]]
auto at(
const Key &key,
const hash_type key_hash)
const
363 ->
const mapped_type & {
364 assert(this->
hash(key) == key_hash);
367 if (this->HASHER.is_perfect(key_hash)) {
368 for (
const auto &entry : *
this) {
369 if (entry.hash == key_hash) {
374 for (
const auto &entry : *
this) {
375 if (entry.hash == key_hash && entry.first == key) {
385 template <
typename T>
386 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
387 [[nodiscard]]
auto at(T key,
const hash_type key_hash)
const
388 ->
const mapped_type & {
389 assert(this->
hash(key) == key_hash);
392 if (this->HASHER.is_perfect(key_hash)) {
393 for (
const auto &entry : *
this) {
394 if (entry.hash == key_hash) {
399 for (
const auto &entry : *
this) {
400 if (entry.hash == key_hash && entry.first == key) {
410 auto at(
const Key &key,
const hash_type key_hash) -> mapped_type & {
411 assert(this->
hash(key) == key_hash);
414 if (this->HASHER.is_perfect(key_hash)) {
415 for (
auto &entry : this->data_) {
416 if (entry.hash == key_hash) {
421 for (
auto &entry : this->data_) {
422 if (entry.hash == key_hash && entry.first == key) {
432 template <
typename T>
433 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
434 auto at(T key,
const hash_type key_hash) -> mapped_type & {
435 assert(this->
hash(key) == key_hash);
438 if (this->HASHER.is_perfect(key_hash)) {
439 for (
auto &entry : this->data_) {
440 if (entry.hash == key_hash) {
445 for (
auto &entry : this->data_) {
446 if (entry.hash == key_hash && entry.first == key) {
456 [[nodiscard]]
auto try_at(
const Key &key,
const hash_type key_hash)
458 assert(this->
hash(key) == key_hash);
461 if (this->HASHER.is_perfect(key_hash)) {
462 for (
auto &entry : this->data_) {
463 if (entry.hash == key_hash) {
464 return &entry.second;
468 for (
auto &entry : this->data_) {
469 if (entry.hash == key_hash && entry.first == key) {
470 return &entry.second;
479 template <
typename T>
480 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
481 [[nodiscard]]
auto try_at(T key,
const hash_type key_hash) -> mapped_type * {
482 assert(this->
hash(key) == key_hash);
485 if (this->HASHER.is_perfect(key_hash)) {
486 for (
auto &entry : this->data_) {
487 if (entry.hash == key_hash) {
488 return &entry.second;
492 for (
auto &entry : this->data_) {
493 if (entry.hash == key_hash && entry.first == key) {
494 return &entry.second;
503 [[nodiscard]]
auto try_at(
const Key &key,
const hash_type key_hash)
const
504 ->
const mapped_type * {
505 assert(this->
hash(key) == key_hash);
508 if (this->HASHER.is_perfect(key_hash)) {
509 for (size_type index = 0; index < this->
size(); index++) {
510 if (this->data_[index].
hash == key_hash) {
511 return &this->data_[index].second;
515 for (size_type index = 0; index < this->
size(); index++) {
516 if (this->data_[index].
hash == key_hash &&
517 this->data_[index].first == key) {
518 return &this->data_[index].second;
527 template <
typename T>
528 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
529 [[nodiscard]]
auto try_at(T key,
const hash_type key_hash)
const
530 ->
const mapped_type * {
531 assert(this->
hash(key) == key_hash);
534 if (this->HASHER.is_perfect(key_hash)) {
535 for (size_type index = 0; index < this->
size(); index++) {
536 if (this->data_[index].
hash == key_hash) {
537 return &this->data_[index].second;
541 for (size_type index = 0; index < this->
size(); index++) {
542 if (this->data_[index].
hash == key_hash &&
543 this->data_[index].first == key) {
544 return &this->data_[index].second;
554 [[nodiscard]]
auto try_at(
const Key &key,
const hash_type key_hash,
555 size_type &start)
const ->
const mapped_type * {
556 assert(this->
hash(key) == key_hash);
557 const auto object_size{this->
size()};
558 const auto scan_start{start};
559 assert(scan_start <= object_size);
563 if (this->HASHER.is_perfect(key_hash)) {
564 for (size_type index = scan_start; index < object_size; index++) {
565 if (this->data_[index].
hash == key_hash) {
567 return &this->data_[index].second;
571 for (size_type index = 0; index < scan_start; index++) {
572 if (this->data_[index].
hash == key_hash) {
574 return &this->data_[index].second;
578 for (size_type index = scan_start; index < object_size; index++) {
579 if (this->data_[index].
hash == key_hash &&
580 this->data_[index].first == key) {
582 return &this->data_[index].second;
586 for (size_type index = 0; index < scan_start; index++) {
587 if (this->data_[index].
hash == key_hash &&
588 this->data_[index].first == key) {
590 return &this->data_[index].second;
600 template <
typename T>
601 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
602 [[nodiscard]]
auto try_at(T key,
const hash_type key_hash,
603 size_type &start)
const ->
const mapped_type * {
604 assert(this->
hash(key) == key_hash);
605 const auto object_size{this->
size()};
606 const auto scan_start{start};
607 assert(scan_start <= object_size);
611 if (this->HASHER.is_perfect(key_hash)) {
612 for (size_type index = scan_start; index < object_size; index++) {
613 if (this->data_[index].
hash == key_hash) {
615 return &this->data_[index].second;
619 for (size_type index = 0; index < scan_start; index++) {
620 if (this->data_[index].
hash == key_hash) {
622 return &this->data_[index].second;
626 for (size_type index = scan_start; index < object_size; index++) {
627 if (this->data_[index].
hash == key_hash &&
628 this->data_[index].first == key) {
630 return &this->data_[index].second;
634 for (size_type index = 0; index < scan_start; index++) {
635 if (this->data_[index].
hash == key_hash &&
636 this->data_[index].first == key) {
638 return &this->data_[index].second;
648 const Key &suffix) -> hash_type {
649 const auto key_hash{this->
hash(key)};
650 const auto suffix_hash{this->
hash(suffix)};
656 auto insertion_point{this->data_.end()};
658 if (this->HASHER.is_perfect(key_hash)) {
659 for (
auto iterator = this->data_.begin(); iterator != this->data_.end();
661 if (iterator->hash == key_hash) {
662 iterator->second = value;
665 if (insertion_point == this->data_.end() &&
666 iterator->hash == suffix_hash && iterator->first == suffix) {
667 insertion_point = iterator;
671 for (
auto iterator = this->data_.begin(); iterator != this->data_.end();
673 if (iterator->hash == key_hash && iterator->first == key) {
674 iterator->second = value;
677 if (insertion_point == this->data_.end() &&
678 iterator->hash == suffix_hash && iterator->first == suffix) {
679 insertion_point = iterator;
684 this->data_.insert(insertion_point, {key, value, key_hash});
689 auto emplace(Key &&key, mapped_type &&value) -> hash_type {
690 const auto key_hash{this->
hash(key)};
692 if (this->HASHER.is_perfect(key_hash)) {
693 for (
auto &entry : this->data_) {
694 if (entry.hash == key_hash) {
695 entry.second = std::move(value);
700 for (
auto &entry : this->data_) {
701 if (entry.hash == key_hash && entry.first == key) {
702 entry.second = std::move(value);
708 this->data_.push_back({std::move(key), std::move(value), key_hash});
713 auto emplace(
const Key &key, mapped_type &&value) -> hash_type {
714 const auto key_hash{this->
hash(key)};
716 if (this->HASHER.is_perfect(key_hash)) {
717 for (
auto &entry : this->data_) {
718 if (entry.hash == key_hash) {
719 entry.second = std::move(value);
724 for (
auto &entry : this->data_) {
725 if (entry.hash == key_hash && entry.first == key) {
726 entry.second = std::move(value);
732 this->data_.push_back({key, std::move(value), key_hash});
737 auto emplace(
const Key &key,
const mapped_type &value) -> hash_type {
738 const auto key_hash{this->
hash(key)};
740 if (this->HASHER.is_perfect(key_hash)) {
741 for (
auto &entry : this->data_) {
742 if (entry.hash == key_hash) {
743 entry.second = value;
748 for (
auto &entry : this->data_) {
749 if (entry.hash == key_hash && entry.first == key) {
750 entry.second = value;
756 this->data_.push_back({key, value, key_hash});
762 const auto key_hash{this->
hash(key)};
763 this->data_.push_back({std::move(key), std::move(value), key_hash});
769 const auto key_hash{this->
hash(key)};
770 this->data_.push_back({key, std::move(value), key_hash});
777 const hash_type key_hash) -> mapped_type & {
778 this->data_.push_back({std::move(key), std::move(value), key_hash});
779 return this->data_.back().second;
784 const hash_type key_hash) ->
void {
785 this->data_.push_back({key, std::move(value), key_hash});
789 [[nodiscard]]
auto back_key() const noexcept -> const Key & {
790 assert(!this->data_.empty());
791 return this->data_.back().first;
795 auto clear() noexcept ->
void { this->data_.clear(); }
801 auto rename(
const Key &key,
const hash_type key_hash, Key &&target,
802 const hash_type target_hash) ->
void {
803 this->
erase(target, target_hash);
805 if (this->HASHER.is_perfect(key_hash)) {
806 for (
auto &entry : this->data_) {
807 if (entry.hash == key_hash) {
808 entry.first = std::move(target);
809 entry.hash = target_hash;
814 for (
auto &entry : this->data_) {
815 if (entry.hash == key_hash && entry.first == key) {
816 entry.first = std::move(target);
817 entry.hash = target_hash;
825 auto erase(
const Key &key,
const hash_type key_hash) -> size_type {
826 assert(this->
hash(key) == key_hash);
827 const auto current_size{this->
size()};
829 if (this->HASHER.is_perfect(key_hash)) {
830 for (
auto iterator = this->data_.begin(); iterator != this->data_.end();
832 if (iterator->hash == key_hash) {
833 this->data_.erase(iterator);
834 return current_size - 1;
838 for (
auto iterator = this->data_.begin(); iterator != this->data_.end();
840 if (iterator->hash == key_hash && iterator->first == key) {
841 this->data_.erase(iterator);
842 return current_size - 1;
851 template <
typename T>
852 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
853 auto erase(T key,
const hash_type key_hash) -> size_type {
854 assert(this->
hash(key) == key_hash);
855 const auto current_size{this->
size()};
857 if (this->HASHER.is_perfect(key_hash)) {
858 for (
auto iterator = this->data_.begin(); iterator != this->data_.end();
860 if (iterator->hash == key_hash) {
861 this->data_.erase(iterator);
862 return current_size - 1;
866 for (
auto iterator = this->data_.begin(); iterator != this->data_.end();
868 if (iterator->hash == key_hash && iterator->first == key) {
869 this->data_.erase(iterator);
870 return current_size - 1;
879 auto erase(
const Key &key) -> size_type {
880 return this->
erase(key, this->
hash(key));
884 template <
typename T>
885 requires std::same_as<std::remove_cvref_t<T>,
KeyView>
887 return this->
erase(key, this->
hash(key));
891 template <
typename Compare>
auto reorder(
const Compare &compare) ->
void {
892 std::sort(this->data_.begin(), this->data_.end(),
893 [&compare](
const auto &left,
const auto &right) ->
auto {
894 return compare(left.first, right.first);
905#pragma warning(disable : 4251)
907 static constexpr Hash HASHER{};
908 underlying_type data_;
static constexpr auto hash(const Key &key) noexcept -> hash_type
Compute a hash for a key.
Definition json_object.h:190
auto emplace_assume_new(Key &&key, mapped_type &&value) -> hash_type
Emplace an object property assuming the key does not already exist.
Definition json_object.h:761
auto try_at(T key, const hash_type key_hash, size_type &start) const -> const mapped_type *
Definition json_object.h:602
auto clear() noexcept -> void
Remove every property in the object.
Definition json_object.h:795
auto try_at(const Key &key, const hash_type key_hash) const -> const mapped_type *
Try to access an object entry by its underlying positional index.
Definition json_object.h:503
auto at(T key, const hash_type key_hash) const -> const mapped_type &
Access an object entry by its key name.
Definition json_object.h:387
auto at(const size_type index) const -> const Entry &
Access an object entry by its underlying positional index.
Definition json_object.h:356
auto reserve(const size_type capacity) -> void
Reserve capacity for a given number of entries.
Definition json_object.h:351
auto try_at(const Key &key, const hash_type key_hash) -> mapped_type *
Try to access an object entry by its key name.
Definition json_object.h:456
auto emplace(String &&key, mapped_type &&value) -> hash_type
Definition json_object.h:689
static constexpr auto hash(const char *raw_data, const std::size_t raw_size) noexcept -> hash_type
Compute a hash from raw data.
Definition json_object.h:203
auto emplace(const Key &key, const mapped_type &value) -> hash_type
Emplace an object property.
Definition json_object.h:737
auto empty() const -> bool
Check if the object is empty.
Definition json_object.h:348
auto try_emplace_before(const Key &key, const mapped_type &value, const Key &suffix) -> hash_type
Try to emplace a property before another property.
Definition json_object.h:647
auto at(T key, const hash_type key_hash) -> mapped_type &
Access an object entry by its key name.
Definition json_object.h:434
auto find(T key) const -> const_iterator
Attempt to find an entry by key.
Definition json_object.h:217
static constexpr auto hash(T key) noexcept -> hash_type
Compute a hash for a key.
Definition json_object.h:198
auto reorder(const Compare &compare) -> void
Reorder object properties by keys according to a comparator function.
Definition json_object.h:891
auto try_at(T key, const hash_type key_hash) -> mapped_type *
Try to access an object entry by its key name.
Definition json_object.h:481
auto defines(const Key &key, const hash_type hash) const -> bool
Check if an entry with the given key exists.
Definition json_object.h:298
auto find(const Key &key, const hash_type key_hash) const -> const_iterator
Definition json_object.h:238
auto erase(const Key &key) -> size_type
Erase an object property.
Definition json_object.h:879
auto find(const Key &key) const -> const_iterator
Attempt to find an entry by key.
Definition json_object.h:210
auto at(const Key &key, const hash_type key_hash) const -> const mapped_type &
Access an object entry by its key name.
Definition json_object.h:362
auto emplace_assume_new(Key &&key, mapped_type &&value, const hash_type key_hash) -> mapped_type &
Definition json_object.h:776
JSONObject(std::initializer_list< pair_value_type > entries)
Construct an object from a list of key and value pairs.
Definition json_object.h:32
auto emplace_assume_new(const Key &key, mapped_type &&value, const hash_type key_hash) -> void
Emplace an object property with a pre-computed hash.
Definition json_object.h:783
auto erase(T key) -> size_type
Erase an object property.
Definition json_object.h:886
auto try_at(T key, const hash_type key_hash) const -> const mapped_type *
Try to access an object entry by its underlying positional index.
Definition json_object.h:529
auto back_key() const noexcept -> const Key &
Get the key of the last-inserted property.
Definition json_object.h:789
auto emplace_assume_new(const Key &key, mapped_type &&value) -> hash_type
Emplace an object property assuming the key does not already exist.
Definition json_object.h:768
auto at(const Key &key, const hash_type key_hash) -> mapped_type &
Access an object entry by its key name.
Definition json_object.h:410
auto defines(T key, const hash_type hash) const -> bool
Check if an entry with the given key exists.
Definition json_object.h:323
auto rename(const Key &key, const hash_type key_hash, Key &&target, const hash_type target_hash) -> void
Rename an object property in place.
Definition json_object.h:801
std::basic_string_view< typename Key::value_type, typename Key::traits_type > KeyView
The string view type used to look up object keys.
Definition json_object.h:28
auto size() const -> std::size_t
Check the size of the object.
Definition json_object.h:345
auto erase(const String &key, const hash_type key_hash) -> size_type
Definition json_object.h:825
auto erase(T key, const hash_type key_hash) -> size_type
Erase an object property.
Definition json_object.h:853
auto try_at(const Key &key, const hash_type key_hash, size_type &start) const -> const mapped_type *
Definition json_object.h:554
auto emplace(const Key &key, mapped_type &&value) -> hash_type
Emplace an object property.
Definition json_object.h:713
auto find(T key, const hash_type key_hash) const -> const_iterator
Definition json_object.h:270
A single object property entry.
Definition json_object.h:40
mapped_type second
The property value.
Definition json_object.h:44
auto key_equals(const KeyView key, const hash_type key_hash) const -> bool
Definition json_object.h:62
hash_type hash
The precomputed hash of the property key.
Definition json_object.h:46
key_type first
The property key.
Definition json_object.h:42