// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

// WARNING, this entire header is generated by
// utils/generate_width_estimation_table.py
// DO NOT MODIFY!

// UNICODE, INC. LICENSE AGREEMENT - DATA FILES AND SOFTWARE
//
// See Terms of Use <https://www.unicode.org/copyright.html>
// for definitions of Unicode Inc.'s Data Files and Software.
//
// NOTICE TO USER: Carefully read the following legal agreement.
// BY DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING UNICODE INC.'S
// DATA FILES ("DATA FILES"), AND/OR SOFTWARE ("SOFTWARE"),
// YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE
// TERMS AND CONDITIONS OF THIS AGREEMENT.
// IF YOU DO NOT AGREE, DO NOT DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE
// THE DATA FILES OR SOFTWARE.
//
// COPYRIGHT AND PERMISSION NOTICE
//
// Copyright (c) 1991-2022 Unicode, Inc. All rights reserved.
// Distributed under the Terms of Use in https://www.unicode.org/copyright.html.
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of the Unicode data files and any associated documentation
// (the "Data Files") or Unicode software and any associated documentation
// (the "Software") to deal in the Data Files or Software
// without restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, and/or sell copies of
// the Data Files or Software, and to permit persons to whom the Data Files
// or Software are furnished to do so, provided that either
// (a) this copyright and permission notice appear with all copies
// of the Data Files or Software, or
// (b) this copyright and permission notice appear in associated
// Documentation.
//
// THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF
// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
// WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT OF THIRD PARTY RIGHTS.
// IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS
// NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL
// DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
// DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
// TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THE DATA FILES OR SOFTWARE.
//
// Except as contained in this notice, the name of a copyright holder
// shall not be used in advertising or otherwise to promote the sale,
// use or other dealings in these Data Files or Software without prior
// written authorization of the copyright holder.

#ifndef _LIBCPP___FORMAT_WIDTH_ESTIMATION_TABLE_H
#define _LIBCPP___FORMAT_WIDTH_ESTIMATION_TABLE_H

#include <__algorithm/ranges_upper_bound.h>
#include <__config>
#include <__cstddef/ptrdiff_t.h>
#include <cstdint>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_BEGIN_NAMESPACE_STD

#if _LIBCPP_STD_VER >= 20

namespace __width_estimation_table {

/// The entries of the characters with an estimated width of 2.
///
/// Contains the entries for [format.string.std]/12
///  -  Any code point with the East_Asian_Width="W" or East_Asian_Width="F"
///     Derived Extracted Property as described by UAX #44
/// - U+4DC0 - U+4DFF (Yijing Hexagram Symbols)
/// - U+1F300 - U+1F5FF (Miscellaneous Symbols and Pictographs)
/// - U+1F900 - U+1F9FF (Supplemental Symbols and Pictographs)
///
/// The data is generated from
/// - https://www.unicode.org/Public/UCD/latest/ucd/EastAsianWidth.txt
/// - The "overrides" in [format.string.std]/12
///
/// The format of EastAsianWidth.txt is two fields separated by a semicolon.
/// Field 0: Unicode code point value or range of code point values
/// Field 1: East_Asian_Width property, consisting of one of the following values:
///         "A", "F", "H", "N", "Na", "W"
///  - All code points, assigned or unassigned, that are not listed
///      explicitly are given the value "N".
///  - The unassigned code points in the following blocks default to "W":
///         CJK Unified Ideographs Extension A: U+3400..U+4DBF
///         CJK Unified Ideographs:             U+4E00..U+9FFF
///         CJK Compatibility Ideographs:       U+F900..U+FAFF
///  - All undesignated code points in Planes 2 and 3, whether inside or
///      outside of allocated blocks, default to "W":
///         Plane 2:                            U+20000..U+2FFFD
///         Plane 3:                            U+30000..U+3FFFD
///
/// The table is similar to the table
///  __extended_grapheme_custer_property_boundary::__entries
/// which explains the details of these classes. The only difference is this
/// table lacks a property, thus having more bits available for the size.
///
/// The maximum code point that has an estimated width of 2 is U+3FFFD. This
/// value can be encoded in 18 bits. Thus the upper 3 bits of the code point
/// are always 0. These 3 bits are used to enlarge the offset range. This
/// optimization reduces the table in Unicode 15 from 184 to 104 entries,
/// saving 320 bytes.
///
/// The data has 2 values:
/// - bits [0, 13] The size of the range, allowing 16384 elements.
/// - bits [14, 31] The lower bound code point of the range. The upper bound of
///   the range is lower bound + size.
_LIBCPP_HIDE_FROM_ABI inline constexpr uint32_t __entries[110] = {
    0x0440005f /* 00001100 - 0000115f [   96] */, //
    0x08c68001 /* 0000231a - 0000231b [    2] */, //
    0x08ca4001 /* 00002329 - 0000232a [    2] */, //
    0x08fa4003 /* 000023e9 - 000023ec [    4] */, //
    0x08fc0000 /* 000023f0 - 000023f0 [    1] */, //
    0x08fcc000 /* 000023f3 - 000023f3 [    1] */, //
    0x097f4001 /* 000025fd - 000025fe [    2] */, //
    0x09850001 /* 00002614 - 00002615 [    2] */, //
    0x098c0007 /* 00002630 - 00002637 [    8] */, //
    0x0992000b /* 00002648 - 00002653 [   12] */, //
    0x099fc000 /* 0000267f - 0000267f [    1] */, //
    0x09a28005 /* 0000268a - 0000268f [    6] */, //
    0x09a4c000 /* 00002693 - 00002693 [    1] */, //
    0x09a84000 /* 000026a1 - 000026a1 [    1] */, //
    0x09aa8001 /* 000026aa - 000026ab [    2] */, //
    0x09af4001 /* 000026bd - 000026be [    2] */, //
    0x09b10001 /* 000026c4 - 000026c5 [    2] */, //
    0x09b38000 /* 000026ce - 000026ce [    1] */, //
    0x09b50000 /* 000026d4 - 000026d4 [    1] */, //
    0x09ba8000 /* 000026ea - 000026ea [    1] */, //
    0x09bc8001 /* 000026f2 - 000026f3 [    2] */, //
    0x09bd4000 /* 000026f5 - 000026f5 [    1] */, //
    0x09be8000 /* 000026fa - 000026fa [    1] */, //
    0x09bf4000 /* 000026fd - 000026fd [    1] */, //
    0x09c14000 /* 00002705 - 00002705 [    1] */, //
    0x09c28001 /* 0000270a - 0000270b [    2] */, //
    0x09ca0000 /* 00002728 - 00002728 [    1] */, //
    0x09d30000 /* 0000274c - 0000274c [    1] */, //
    0x09d38000 /* 0000274e - 0000274e [    1] */, //
    0x09d4c002 /* 00002753 - 00002755 [    3] */, //
    0x09d5c000 /* 00002757 - 00002757 [    1] */, //
    0x09e54002 /* 00002795 - 00002797 [    3] */, //
    0x09ec0000 /* 000027b0 - 000027b0 [    1] */, //
    0x09efc000 /* 000027bf - 000027bf [    1] */, //
    0x0ac6c001 /* 00002b1b - 00002b1c [    2] */, //
    0x0ad40000 /* 00002b50 - 00002b50 [    1] */, //
    0x0ad54000 /* 00002b55 - 00002b55 [    1] */, //
    0x0ba00019 /* 00002e80 - 00002e99 [   26] */, //
    0x0ba6c058 /* 00002e9b - 00002ef3 [   89] */, //
    0x0bc000d5 /* 00002f00 - 00002fd5 [  214] */, //
    0x0bfc004e /* 00002ff0 - 0000303e [   79] */, //
    0x0c104055 /* 00003041 - 00003096 [   86] */, //
    0x0c264066 /* 00003099 - 000030ff [  103] */, //
    0x0c41402a /* 00003105 - 0000312f [   43] */, //
    0x0c4c405d /* 00003131 - 0000318e [   94] */, //
    0x0c640055 /* 00003190 - 000031e5 [   86] */, //
    0x0c7bc02f /* 000031ef - 0000321e [   48] */, //
    0x0c880027 /* 00003220 - 00003247 [   40] */, //
    0x0c943fff /* 00003250 - 0000724f [16384] */, //
    0x1c94323c /* 00007250 - 0000a48c [12861] */, //
    0x29240036 /* 0000a490 - 0000a4c6 [   55] */, //
    0x2a58001c /* 0000a960 - 0000a97c [   29] */, //
    0x2b002ba3 /* 0000ac00 - 0000d7a3 [11172] */, //
    0x3e4001ff /* 0000f900 - 0000faff [  512] */, //
    0x3f840009 /* 0000fe10 - 0000fe19 [   10] */, //
    0x3f8c0022 /* 0000fe30 - 0000fe52 [   35] */, //
    0x3f950012 /* 0000fe54 - 0000fe66 [   19] */, //
    0x3f9a0003 /* 0000fe68 - 0000fe6b [    4] */, //
    0x3fc0405f /* 0000ff01 - 0000ff60 [   96] */, //
    0x3ff80006 /* 0000ffe0 - 0000ffe6 [    7] */, //
    0x5bf80004 /* 00016fe0 - 00016fe4 [    5] */, //
    0x5bfc0001 /* 00016ff0 - 00016ff1 [    2] */, //
    0x5c0017f7 /* 00017000 - 000187f7 [ 6136] */, //
    0x620004d5 /* 00018800 - 00018cd5 [ 1238] */, //
    0x633fc009 /* 00018cff - 00018d08 [   10] */, //
    0x6bfc0003 /* 0001aff0 - 0001aff3 [    4] */, //
    0x6bfd4006 /* 0001aff5 - 0001affb [    7] */, //
    0x6bff4001 /* 0001affd - 0001affe [    2] */, //
    0x6c000122 /* 0001b000 - 0001b122 [  291] */, //
    0x6c4c8000 /* 0001b132 - 0001b132 [    1] */, //
    0x6c540002 /* 0001b150 - 0001b152 [    3] */, //
    0x6c554000 /* 0001b155 - 0001b155 [    1] */, //
    0x6c590003 /* 0001b164 - 0001b167 [    4] */, //
    0x6c5c018b /* 0001b170 - 0001b2fb [  396] */, //
    0x74c00056 /* 0001d300 - 0001d356 [   87] */, //
    0x74d80016 /* 0001d360 - 0001d376 [   23] */, //
    0x7c010000 /* 0001f004 - 0001f004 [    1] */, //
    0x7c33c000 /* 0001f0cf - 0001f0cf [    1] */, //
    0x7c638000 /* 0001f18e - 0001f18e [    1] */, //
    0x7c644009 /* 0001f191 - 0001f19a [   10] */, //
    0x7c800002 /* 0001f200 - 0001f202 [    3] */, //
    0x7c84002b /* 0001f210 - 0001f23b [   44] */, //
    0x7c900008 /* 0001f240 - 0001f248 [    9] */, //
    0x7c940001 /* 0001f250 - 0001f251 [    2] */, //
    0x7c980005 /* 0001f260 - 0001f265 [    6] */, //
    0x7cc0034f /* 0001f300 - 0001f64f [  848] */, //
    0x7da00045 /* 0001f680 - 0001f6c5 [   70] */, //
    0x7db30000 /* 0001f6cc - 0001f6cc [    1] */, //
    0x7db40002 /* 0001f6d0 - 0001f6d2 [    3] */, //
    0x7db54002 /* 0001f6d5 - 0001f6d7 [    3] */, //
    0x7db70003 /* 0001f6dc - 0001f6df [    4] */, //
    0x7dbac001 /* 0001f6eb - 0001f6ec [    2] */, //
    0x7dbd0008 /* 0001f6f4 - 0001f6fc [    9] */, //
    0x7df8000b /* 0001f7e0 - 0001f7eb [   12] */, //
    0x7dfc0000 /* 0001f7f0 - 0001f7f0 [    1] */, //
    0x7e4000ff /* 0001f900 - 0001f9ff [  256] */, //
    0x7e9c000c /* 0001fa70 - 0001fa7c [   13] */, //
    0x7ea00009 /* 0001fa80 - 0001fa89 [   10] */, //
    0x7ea3c037 /* 0001fa8f - 0001fac6 [   56] */, //
    0x7eb3800e /* 0001face - 0001fadc [   15] */, //
    0x7eb7c00a /* 0001fadf - 0001fae9 [   11] */, //
    0x7ebc0008 /* 0001faf0 - 0001faf8 [    9] */, //
    0x80003fff /* 00020000 - 00023fff [16384] */, //
    0x90003fff /* 00024000 - 00027fff [16384] */, //
    0xa0003fff /* 00028000 - 0002bfff [16384] */, //
    0xb0003ffd /* 0002c000 - 0002fffd [16382] */, //
    0xc0003fff /* 00030000 - 00033fff [16384] */, //
    0xd0003fff /* 00034000 - 00037fff [16384] */, //
    0xe0003fff /* 00038000 - 0003bfff [16384] */, //
    0xf0003ffd /* 0003c000 - 0003fffd [16382] */};

/// The upper bound entry of EastAsianWidth.txt.
///
/// Values greater than this value may have more than 18 significant bits.
/// They always have a width of 1. This property makes it possible to store
/// the table in its compact form.
inline constexpr uint32_t __table_upper_bound = 0x0003fffd;

/// Returns the estimated width of a Unicode code point.
///
/// \\pre The code point is a valid Unicode code point.
[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr int __estimated_width(const char32_t __code_point) noexcept {
  // Since __table_upper_bound contains the unshifted range do the
  // comparison without shifting.
  if (__code_point > __table_upper_bound) [[unlikely]]
    return 1;

  // When the code-point is less than the first element in the table
  // the lookup is quite expensive. Since quite some scripts are in
  // that range, it makes sense to validate that first.
  // The std_format_spec_string_unicode benchmark gives a measurable
  // improvement.
  if (__code_point < (__entries[0] >> 14))
    return 1;

  ptrdiff_t __i = std::ranges::upper_bound(__entries, (__code_point << 14) | 0x3fffu) - __entries;
  if (__i == 0)
    return 1;

  --__i;
  uint32_t __upper_bound = (__entries[__i] >> 14) + (__entries[__i] & 0x3fffu);
  return 1 + (__code_point <= __upper_bound);
}

} // namespace __width_estimation_table

#endif // _LIBCPP_STD_VER >= 20

_LIBCPP_END_NAMESPACE_STD

#endif // _LIBCPP___FORMAT_WIDTH_ESTIMATION_TABLE_H