docs/dev/_modules/collections.html - arrow-site - Git at Google


 <!DOCTYPE html>


 <html lang="en" data-content_root="../" >

   <head>
     <meta charset="utf-8" />
     <meta name="viewport" content="width=device-width, initial-scale=1.0" />
     <title>collections &#8212; Apache Arrow v24.0.0.dev285</title>


   <script data-cfasync="false">
     document.documentElement.dataset.mode = localStorage.getItem("mode") || "";
     document.documentElement.dataset.theme = localStorage.getItem("theme") || "";
   </script>
   <!--
     this give us a css class that will be invisible only if js is disabled
   -->
   <noscript>
     <style>
       .pst-js-only { display: none !important; }

     </style>
   </noscript>

   <!-- Loaded before other Sphinx assets -->
   <link href="../_static/styles/theme.css?digest=8878045cc6db502f8baf" rel="stylesheet" />
 <link href="../_static/styles/pydata-sphinx-theme.css?digest=8878045cc6db502f8baf" rel="stylesheet" />

     <link rel="stylesheet" type="text/css" href="../_static/pygments.css?v=03e43079" />
     <link rel="stylesheet" type="text/css" href="../_static/copybutton.css?v=76b2166b" />
     <link rel="stylesheet" type="text/css" href="../_static/sphinx-design.min.css?v=95c83b7e" />
     <link rel="stylesheet" type="text/css" href="../_static/theme_overrides.css?v=8dcd28dc" />

   <!-- So that users can add custom icons -->
   <script src="../_static/scripts/fontawesome.js?digest=8878045cc6db502f8baf"></script>
   <!-- Pre-loaded scripts that we'll load fully later -->
   <link rel="preload" as="script" href="../_static/scripts/bootstrap.js?digest=8878045cc6db502f8baf" />
 <link rel="preload" as="script" href="../_static/scripts/pydata-sphinx-theme.js?digest=8878045cc6db502f8baf" />

     <script src="../_static/documentation_options.js?v=d1837f39"></script>
     <script src="../_static/doctools.js?v=fd6eb6e6"></script>
     <script src="../_static/sphinx_highlight.js?v=6ffebe34"></script>
     <script src="../_static/clipboard.min.js?v=a7894cd8"></script>
     <script src="../_static/copybutton.js?v=3bb21c8c"></script>
     <script src="../_static/design-tabs.js?v=f930bc37"></script>
     <script type="module">import mermaid from "https://cdn.jsdelivr.net/npm/mermaid@11.12.1/dist/mermaid.esm.min.mjs";


 const initStyles = () => {
     const defaultStyle = document.createElement('style');
     defaultStyle.textContent = `pre.mermaid {
     /* Same as .mermaid-container > pre */
     display: block;
     width: 100%;
 }

 pre.mermaid > svg {
     /* Same as .mermaid-container > pre > svg */
     height: 500px;
     width: 100%;
     max-width: 100% !important;
 }`;
     document.head.appendChild(defaultStyle);

     const fullscreenStyle = document.createElement('style');
     fullscreenStyle.textContent = `.mermaid-container {
     display: flex;
     flex-direction: row;
     width: 100%;
 }

 .mermaid-container > pre {
     display: block;
     width: 100%;
 }

 .mermaid-container > pre > svg {
     height: 500px;
     width: 100%;
     max-width: 100% !important;
 }

 .mermaid-fullscreen-btn {
     width: 28px;
     height: 28px;
     background: rgba(255, 255, 255, 0.95);
     border: 1px solid rgba(0, 0, 0, 0.3);
     border-radius: 4px;
     cursor: pointer;
     display: flex;
     align-items: center;
     justify-content: center;
     transition: all 0.2s;
     box-shadow: 0 2px 6px rgba(0, 0, 0, 0.2);
     font-size: 14px;
     line-height: 1;
     padding: 0;
     color: #333;
 }

 .mermaid-fullscreen-btn:hover {
     opacity: 100% !important;
     background: rgba(255, 255, 255, 1);
     box-shadow: 0 3px 10px rgba(0, 0, 0, 0.3);
     transform: scale(1.1);
 }

 .mermaid-fullscreen-btn.dark-theme {
     background: rgba(50, 50, 50, 0.95);
     border: 1px solid rgba(255, 255, 255, 0.3);
     color: #e0e0e0;
 }

 .mermaid-fullscreen-btn.dark-theme:hover {
     background: rgba(60, 60, 60, 1);
     box-shadow: 0 3px 10px rgba(255, 255, 255, 0.2);
 }

 .mermaid-fullscreen-modal {
     display: none;
     position: fixed !important;
     top: 0 !important;
     left: 0 !important;
     width: 95vw;
     height: 100vh;
     background: rgba(255, 255, 255, 0.98);
     z-index: 9999;
     padding: 20px;
     overflow: auto;
 }

 .mermaid-fullscreen-modal.dark-theme {
     background: rgba(0, 0, 0, 0.98);
 }

 .mermaid-fullscreen-modal.active {
     display: flex;
     align-items: center;
     justify-content: center;
 }

 .mermaid-container-fullscreen {
     position: relative;
     width: 95vw;
     height: 90vh;
     max-width: 95vw;
     max-height: 90vh;
     background: white;
     border-radius: 8px;
     padding: 20px;
     box-shadow: 0 10px 40px rgba(0, 0, 0, 0.3);
     overflow: auto;
     display: flex;
     align-items: center;
     justify-content: center;
 }

 .mermaid-container-fullscreen.dark-theme {
     background: #1a1a1a;
     box-shadow: 0 10px 40px rgba(0, 0, 0, 0.8);
 }

 .mermaid-container-fullscreen pre.mermaid {
     width: 100%;
     height: 100%;
     display: flex;
     align-items: center;
     justify-content: center;
 }

 .mermaid-container-fullscreen .mermaid svg {
     height: 100% !important;
     width: 100% !important;
     cursor: grab;
 }

 .mermaid-fullscreen-close {
     position: fixed !important;
     top: 20px !important;
     right: 20px !important;
     width: 40px;
     height: 40px;
     background: rgba(255, 255, 255, 0.95);
     border: 1px solid rgba(0, 0, 0, 0.2);
     border-radius: 50%;
     cursor: pointer;
     z-index: 10000;
     display: flex;
     align-items: center;
     justify-content: center;
     box-shadow: 0 4px 12px rgba(0, 0, 0, 0.3);
     transition: all 0.2s;
     font-size: 24px;
     line-height: 1;
     color: #333;
 }

 .mermaid-fullscreen-close:hover {
     background: white;
     box-shadow: 0 6px 16px rgba(0, 0, 0, 0.4);
     transform: scale(1.1);
 }

 .mermaid-fullscreen-close.dark-theme {
     background: rgba(50, 50, 50, 0.95);
     border: 1px solid rgba(255, 255, 255, 0.2);
     color: #e0e0e0;
 }

 .mermaid-fullscreen-close.dark-theme:hover {
     background: rgba(60, 60, 60, 1);
     box-shadow: 0 6px 16px rgba(255, 255, 255, 0.2);
 }

 .mermaid-fullscreen-modal .mermaid-fullscreen-btn {
     display: none !important;
 }`;
     document.head.appendChild(fullscreenStyle);
 }

 // Detect if page has dark background
 const isDarkTheme = () => {
     // We use a set of heuristics:
     // 1. Check for common dark mode classes or attributes
     // 2. Check computed background color brightness
     if (document.documentElement.classList.contains('dark') ||
         document.documentElement.getAttribute('data-theme') === 'dark' ||
         document.body.classList.contains('dark') ||
         document.body.getAttribute('data-theme') === 'dark') {
         // console.log("Dark theme detected via class/attribute");
         return true;
     }
     if (document.documentElement.classList.contains('light') ||
         document.documentElement.getAttribute('data-theme') === 'light' ||
         document.body.classList.contains('light') ||
         document.body.getAttribute('data-theme') === 'light') {
         // console.log("Light theme detected via class/attribute");
         return false;
     }
     if (window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches) {
         // console.log("Dark theme detected via prefers-color-scheme");
         return true;
     }
     const bgColor = window.getComputedStyle(document.body).backgroundColor;
     const match = bgColor.match(/rgb\((\d+),\s*(\d+),\s*(\d+)/);
     if (match) {
         const r = parseInt(match[1]);
         const g = parseInt(match[2]);
         const b = parseInt(match[3]);
         const brightness = (r * 299 + g * 587 + b * 114) / 1000;
         // console.log("Background color brightness:", brightness);
         return brightness < 128;
     }
     // console.log("No dark or light theme detected, defaulting to light theme");
     return false;
 };

 let darkTheme = isDarkTheme();
 let modal = null;
 let modalContent = null;
 let previousScrollOffset = [window.scrollX, window.scrollY];

 const runMermaid = async (rerun) => {
     console.log("Running mermaid diagrams, rerun =", rerun);
     // clear all existing mermaid charts
     let all_mermaids = document.querySelectorAll(".mermaid");

     if (rerun) {
         all_mermaids.forEach((el) => {
             if(!el.hasAttribute("data-original-code")) {
                 // store original code
                 // console.log(`Storing original code for first run: `, el.innerHTML);
                 el.setAttribute('data-original-code', el.innerHTML);
             }
             if(el.getAttribute("data-processed") === "true") {
                 // remove and restore original
                 el.removeAttribute("data-processed");
                 // console.log(`Restoring original code for re-run: `, el.getAttribute('data-original-code'));
                 el.innerHTML = el.getAttribute('data-original-code');
             } else {
                 // store original code
                 // console.log(`Storing original code for re-run: `, el.innerHTML);
                 el.setAttribute('data-original-code', el.innerHTML);
             }
         });
         await mermaid.run();
     }

     all_mermaids = document.querySelectorAll(".mermaid");
     const mermaids_processed = document.querySelectorAll(".mermaid[data-processed='true']");

     if ("False" === "True") {
         const mermaids_to_add_zoom = -1 === -1 ? all_mermaids.length : -1;
         if(mermaids_to_add_zoom > 0) {
             var svgs = d3.selectAll("");
             if(all_mermaids.length !== mermaids_processed.length) {
                 setTimeout(() => runMermaid(false), 200);
                 return;
             } else if(svgs.size() !== mermaids_to_add_zoom) {
                 setTimeout(() => runMermaid(false), 200);
                 return;
             } else {
                 svgs.each(function() {
                     var svg = d3.select(this);
                     svg.html("<g class='wrapper'>" + svg.html() + "</g>");
                     var inner = svg.select("g");
                     var zoom = d3.zoom().on("zoom", function(event) {
                         inner.attr("transform", event.transform);
                     });
                     svg.call(zoom);
                 });
             }
         }
     } else if(all_mermaids.length !== mermaids_processed.length) {
         // Wait for mermaid to process all diagrams
         setTimeout(() => runMermaid(false), 200);
         return;
     }

     // Stop here if not adding fullscreen capability
     if ("True" !== "True") return;

     if (modal !== null ) {
         // Destroy existing modal
         modal.remove();
         modal = null;
         modalContent = null;
     }

     modal = document.createElement('div');
     modal.className = 'mermaid-fullscreen-modal' + (darkTheme ? ' dark-theme' : '');
     modal.setAttribute('role', 'dialog');
     modal.setAttribute('aria-modal', 'true');
     modal.setAttribute('aria-label', 'Fullscreen diagram viewer');
     modal.innerHTML = `
         <button class="mermaid-fullscreen-close${darkTheme ? ' dark-theme' : ''}" aria-label="Close fullscreen">✕</button>
         <div class="mermaid-container-fullscreen${darkTheme ? ' dark-theme' : ''}"></div>
     `;
     document.body.appendChild(modal);

     modalContent = modal.querySelector('.mermaid-container-fullscreen');
     const closeBtn = modal.querySelector('.mermaid-fullscreen-close');

     const closeModal = () => {
         modal.classList.remove('active');
         modalContent.innerHTML = '';
         document.body.style.overflow = ''
         window.scrollTo({left: previousScrollOffset[0], top: previousScrollOffset[1], behavior: 'instant'});
     };

     closeBtn.addEventListener('click', closeModal);
     modal.addEventListener('click', (e) => {
         if (e.target === modal) closeModal();
     });
     document.addEventListener('keydown', (e) => {
         if (e.key === 'Escape' && modal.classList.contains('active')) {
             closeModal();
         }
     });

     document.querySelectorAll('.mermaid').forEach((mermaidDiv) => {
         if (mermaidDiv.parentNode.classList.contains('mermaid-container') ||
             mermaidDiv.closest('.mermaid-fullscreen-modal')) {
             // Already processed, adjust button class if needed
             const existingBtn = mermaidDiv.parentNode.querySelector('.mermaid-fullscreen-btn');
             if (existingBtn) {
                 existingBtn.className = 'mermaid-fullscreen-btn' + (darkTheme ? ' dark-theme' : '');
             }
             return;
         }

         const container = document.createElement('div');
         container.className = 'mermaid-container';
         mermaidDiv.parentNode.insertBefore(container, mermaidDiv);
         container.appendChild(mermaidDiv);

         const fullscreenBtn = document.createElement('button');
         fullscreenBtn.className = 'mermaid-fullscreen-btn' + (darkTheme ? ' dark-theme' : '');
         fullscreenBtn.setAttribute('aria-label', 'View diagram in fullscreen');
         fullscreenBtn.textContent = '⛶';
         fullscreenBtn.style.opacity = '50%';

         // Calculate dynamic position based on diagram's margin and padding
         const diagramStyle = window.getComputedStyle(mermaidDiv);
         const marginTop = parseFloat(diagramStyle.marginTop) || 0;
         const marginRight = parseFloat(diagramStyle.marginRight) || 0;
         const paddingTop = parseFloat(diagramStyle.paddingTop) || 0;
         const paddingRight = parseFloat(diagramStyle.paddingRight) || 0;
         fullscreenBtn.style.top = `${marginTop + paddingTop + 4}px`;
         fullscreenBtn.style.right = `${marginRight + paddingRight + 4}px`;

         fullscreenBtn.addEventListener('click', () => {
             previousScrollOffset = [window.scroll, window.scrollY];
             const clone = mermaidDiv.cloneNode(true);
             modalContent.innerHTML = '';
             modalContent.appendChild(clone);

             const svg = clone.querySelector('svg');
             if (svg) {
                 svg.removeAttribute('width');
                 svg.removeAttribute('height');
                 svg.style.width = '100%';
                 svg.style.height = 'auto';
                 svg.style.maxWidth = '100%';
                 svg.style.sdisplay = 'block';

                 if ("False" === "True") {
                     setTimeout(() => {
                         const g = svg.querySelector('g');
                         if (g) {
                             var svgD3 = d3.select(svg);
                             svgD3.html("<g class='wrapper'>" + svgD3.html() + "</g>");
                             var inner = svgD3.select("g");
                             var zoom = d3.zoom().on("zoom", function(event) {
                                 inner.attr("transform", event.transform);
                             });
                             svgD3.call(zoom);
                         }
                     }, 100);
                 }
             }

             modal.classList.add('active');
             document.body.style.overflow = 'hidden';
         });
         container.appendChild(fullscreenBtn);
     });
 };

 const load = async () => {
     initStyles();

     await runMermaid(true);

     const reRunIfThemeChanges = async () => {
         const newDarkTheme = isDarkTheme();
         if (newDarkTheme !== darkTheme) {
             darkTheme = newDarkTheme;
             console.log("Theme change detected, re-running mermaid with", darkTheme ? "dark" : "default", "theme");
             await mermaid.initialize(
                 {...JSON.parse(
                     `{"startOnLoad": false}`
                 ),
                 ...{ darkMode: darkTheme, theme: darkTheme ? 'dark' : 'default' },
                 }
             );
             await runMermaid(true);
         }
     };

     // Update theme classes when theme changes
     const themeObserver = new MutationObserver(reRunIfThemeChanges);
     themeObserver.observe(document.documentElement, {
         attributes: true,
         attributeFilter: ['class', 'style', 'data-theme']
     });
     themeObserver.observe(document.body, {
         attributes: true,
         attributeFilter: ['class', 'style', 'data-theme']
     });
 };


 console.log("Initializing mermaid with", darkTheme ? "dark" : "default", "theme");
 mermaid.initialize(
     {...JSON.parse(
         `{"startOnLoad": false}`
     ),
     ...{ darkMode: darkTheme, theme: darkTheme ? 'dark' : 'default' },
     }
 );

 window.addEventListener("load", load);
 window.runMermaid = runMermaid;</script>
     <script>DOCUMENTATION_OPTIONS.pagename = '_modules/collections';</script>
     <script>
         DOCUMENTATION_OPTIONS.theme_version = '0.16.1';
         DOCUMENTATION_OPTIONS.theme_switcher_json_url = '/docs/_static/versions.json';
         DOCUMENTATION_OPTIONS.theme_switcher_version_match = 'dev/';
         DOCUMENTATION_OPTIONS.show_version_warning_banner =
             true;
         </script>
     <link rel="canonical" href="https://arrow.apache.org/docs/_modules/collections.html" />
     <link rel="icon" href="../_static/favicon.ico"/>
     <link rel="index" title="Index" href="../genindex.html" />
     <link rel="search" title="Search" href="../search.html" />

   <meta name="viewport" content="width=device-width, initial-scale=1"/>
   <meta name="docsearch:language" content="en"/>
   <meta name="docsearch:version" content="24.0.0.dev285" />

   <!-- Matomo -->
   <script>
     var _paq = window._paq = window._paq || [];
     /* tracker methods like "setCustomDimension" should be called before "trackPageView" */
     /* We explicitly disable cookie tracking to avoid privacy issues */
     _paq.push(['disableCookies']);
     _paq.push(['trackPageView']);
     _paq.push(['enableLinkTracking']);
     (function() {
       var u="https://analytics.apache.org/";
       _paq.push(['setTrackerUrl', u+'matomo.php']);
       _paq.push(['setSiteId', '20']);
       var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0];
       g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s);
     })();
   </script>
   <!-- End Matomo Code -->

   </head>


   <body data-bs-spy="scroll" data-bs-target=".bd-toc-nav" data-offset="180" data-bs-root-margin="0px 0px -60%" data-default-mode="">


   <div id="pst-skip-link" class="skip-link d-print-none"><a href="#main-content">Skip to main content</a></div>

   <div id="pst-scroll-pixel-helper"></div>

   <button type="button" class="btn rounded-pill" id="pst-back-to-top">
     <i class="fa-solid fa-arrow-up"></i>Back to top</button>


   <dialog id="pst-search-dialog">

 <form class="bd-search d-flex align-items-center"
       action="../search.html"
       method="get">
   <i class="fa-solid fa-magnifying-glass"></i>
   <input type="search"
          class="form-control"
          name="q"
          placeholder="Search the docs ..."
          aria-label="Search the docs ..."
          autocomplete="off"
          autocorrect="off"
          autocapitalize="off"
          spellcheck="false"/>
   <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd>K</kbd></span>
 </form>
   </dialog>

   <div class="pst-async-banner-revealer d-none">
   <aside id="bd-header-version-warning" class="d-none d-print-none" aria-label="Version warning"></aside>
 </div>


     <header class="bd-header navbar navbar-expand-lg bd-navbar d-print-none">
 <div class="bd-header__inner bd-page-width">
   <button class="pst-navbar-icon sidebar-toggle primary-toggle" aria-label="Site navigation">
     <span class="fa-solid fa-bars"></span>
   </button>


   <div class=" navbar-header-items__start">

       <div class="navbar-item">


 <a class="navbar-brand logo" href="../index.html">


     <img src="../_static/arrow.png" class="logo__image only-light" alt="Apache Arrow v24.0.0.dev285 - Home"/>
     <img src="../_static/arrow-dark.png" class="logo__image only-dark pst-js-only" alt="Apache Arrow v24.0.0.dev285 - Home"/>


 </a></div>

   </div>

   <div class=" navbar-header-items">

     <div class="me-auto navbar-header-items__center">

         <div class="navbar-item">
 <nav>
   <ul class="bd-navbar-elements navbar-nav">

 <li class="nav-item ">
   <a class="nav-link nav-internal" href="../format/index.html">
     Specifications
   </a>
 </li>


 <li class="nav-item ">
   <a class="nav-link nav-internal" href="../developers/index.html">
     Development
   </a>
 </li>


 <li class="nav-item ">
   <a class="nav-link nav-internal" href="../implementations.html">
     Implementations
   </a>
 </li>

   </ul>
 </nav></div>

     </div>


     <div class="navbar-header-items__end">

         <div class="navbar-item navbar-persistent--container">


 <button class="btn search-button-field search-button__button pst-js-only" title="Search" aria-label="Search" data-bs-placement="bottom" data-bs-toggle="tooltip">
  <i class="fa-solid fa-magnifying-glass"></i>
  <span class="search-button__default-text">Search</span>
  <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd class="kbd-shortcut__modifier">K</kbd></span>
 </button>
         </div>


         <div class="navbar-item"><div class="kapa-ai-bot">
     <script
         async
         src="https://widget.kapa.ai/kapa-widget.bundle.js"
         data-website-id="9db461d5-ac77-4b3f-a5c5-75efa78339d2"
         data-project-name="Apache Arrow"
         data-project-color="#000000"
         data-project-logo="https://arrow.apache.org/img/arrow-logo_chevrons_white-txt_black-bg.png"
         data-modal-disclaimer="This is a custom LLM with access to all [Arrow documentation](https://arrow.apache.org/docs/). Please include the language you are using in your question, e.g., Python, C++, Java, R, etc."
         data-consent-required="true"
         data-user-analytics-cookie-enabled="false"
         data-consent-screen-disclaimer="By clicking &quot;I agree, let's chat&quot;, you consent to the use of the AI assistant in accordance with kapa.ai's [Privacy Policy](https://www.kapa.ai/content/privacy-policy). This service uses reCAPTCHA, which requires your consent to Google's [Privacy Policy](https://policies.google.com/privacy) and [Terms of Service](https://policies.google.com/terms). By proceeding, you explicitly agree to both kapa.ai's and Google's privacy policies."
     ></script>

 </div>

 </div>

         <div class="navbar-item">
 <div class="version-switcher__container dropdown pst-js-only">
   <button id="pst-version-switcher-button-2"
     type="button"
     class="version-switcher__button btn btn-sm dropdown-toggle"
     data-bs-toggle="dropdown"
     aria-haspopup="listbox"
     aria-controls="pst-version-switcher-list-2"
     aria-label="Version switcher list"
   >
     Choose version  <!-- this text may get changed later by javascript -->
     <span class="caret"></span>
   </button>
   <div id="pst-version-switcher-list-2"
     class="version-switcher__menu dropdown-menu list-group-flush py-0"
     role="listbox" aria-labelledby="pst-version-switcher-button-2">
     <!-- dropdown will be populated by javascript on page load -->
   </div>
 </div></div>

         <div class="navbar-item">

 <button class="btn btn-sm nav-link pst-navbar-icon theme-switch-button pst-js-only" aria-label="Color mode" data-bs-title="Color mode"  data-bs-placement="bottom" data-bs-toggle="tooltip">
   <i class="theme-switch fa-solid fa-sun                fa-lg" data-mode="light" title="Light"></i>
   <i class="theme-switch fa-solid fa-moon               fa-lg" data-mode="dark"  title="Dark"></i>
   <i class="theme-switch fa-solid fa-circle-half-stroke fa-lg" data-mode="auto"  title="System Settings"></i>
 </button></div>

         <div class="navbar-item"><ul class="navbar-icon-links"
     aria-label="Icon Links">
         <li class="nav-item">


           <a href="https://github.com/apache/arrow" title="GitHub" class="nav-link pst-navbar-icon" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><i class="fa-brands fa-square-github fa-lg" aria-hidden="true"></i>
             <span class="sr-only">GitHub</span></a>
         </li>
         <li class="nav-item">


           <a href="https://www.linkedin.com/company/apache-arrow/" title="LinkedIn" class="nav-link pst-navbar-icon" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><i class="fa-brands fa-linkedin fa-lg" aria-hidden="true"></i>
             <span class="sr-only">LinkedIn</span></a>
         </li>
         <li class="nav-item">


           <a href="https://bsky.app/profile/arrow.apache.org" title="BlueSky" class="nav-link pst-navbar-icon" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><i class="fa-brands fa-bluesky fa-lg" aria-hidden="true"></i>
             <span class="sr-only">BlueSky</span></a>
         </li>
 </ul></div>

     </div>

   </div>


     <div class="navbar-persistent--mobile">

 <button class="btn search-button-field search-button__button pst-js-only" title="Search" aria-label="Search" data-bs-placement="bottom" data-bs-toggle="tooltip">
  <i class="fa-solid fa-magnifying-glass"></i>
  <span class="search-button__default-text">Search</span>
  <span class="search-button__kbd-shortcut"><kbd class="kbd-shortcut__modifier">Ctrl</kbd>+<kbd class="kbd-shortcut__modifier">K</kbd></span>
 </button>
     </div>


 </div>

     </header>


   <div class="bd-container">
     <div class="bd-container__inner bd-page-width">


       <dialog id="pst-primary-sidebar-modal"></dialog>
       <div id="pst-primary-sidebar" class="bd-sidebar-primary bd-sidebar hide-on-wide">


   <div class="sidebar-header-items sidebar-primary__section">


       <div class="sidebar-header-items__center">


             <div class="navbar-item">
 <nav>
   <ul class="bd-navbar-elements navbar-nav">

 <li class="nav-item ">
   <a class="nav-link nav-internal" href="../format/index.html">
     Specifications
   </a>
 </li>


 <li class="nav-item ">
   <a class="nav-link nav-internal" href="../developers/index.html">
     Development
   </a>
 </li>


 <li class="nav-item ">
   <a class="nav-link nav-internal" href="../implementations.html">
     Implementations
   </a>
 </li>

   </ul>
 </nav></div>


       </div>


       <div class="sidebar-header-items__end">

           <div class="navbar-item"><div class="kapa-ai-bot">
     <script
         async
         src="https://widget.kapa.ai/kapa-widget.bundle.js"
         data-website-id="9db461d5-ac77-4b3f-a5c5-75efa78339d2"
         data-project-name="Apache Arrow"
         data-project-color="#000000"
         data-project-logo="https://arrow.apache.org/img/arrow-logo_chevrons_white-txt_black-bg.png"
         data-modal-disclaimer="This is a custom LLM with access to all [Arrow documentation](https://arrow.apache.org/docs/). Please include the language you are using in your question, e.g., Python, C++, Java, R, etc."
         data-consent-required="true"
         data-user-analytics-cookie-enabled="false"
         data-consent-screen-disclaimer="By clicking &quot;I agree, let's chat&quot;, you consent to the use of the AI assistant in accordance with kapa.ai's [Privacy Policy](https://www.kapa.ai/content/privacy-policy). This service uses reCAPTCHA, which requires your consent to Google's [Privacy Policy](https://policies.google.com/privacy) and [Terms of Service](https://policies.google.com/terms). By proceeding, you explicitly agree to both kapa.ai's and Google's privacy policies."
     ></script>

 </div>

 </div>

           <div class="navbar-item">
 <div class="version-switcher__container dropdown pst-js-only">
   <button id="pst-version-switcher-button-3"
     type="button"
     class="version-switcher__button btn btn-sm dropdown-toggle"
     data-bs-toggle="dropdown"
     aria-haspopup="listbox"
     aria-controls="pst-version-switcher-list-3"
     aria-label="Version switcher list"
   >
     Choose version  <!-- this text may get changed later by javascript -->
     <span class="caret"></span>
   </button>
   <div id="pst-version-switcher-list-3"
     class="version-switcher__menu dropdown-menu list-group-flush py-0"
     role="listbox" aria-labelledby="pst-version-switcher-button-3">
     <!-- dropdown will be populated by javascript on page load -->
   </div>
 </div></div>

           <div class="navbar-item">

 <button class="btn btn-sm nav-link pst-navbar-icon theme-switch-button pst-js-only" aria-label="Color mode" data-bs-title="Color mode"  data-bs-placement="bottom" data-bs-toggle="tooltip">
   <i class="theme-switch fa-solid fa-sun                fa-lg" data-mode="light" title="Light"></i>
   <i class="theme-switch fa-solid fa-moon               fa-lg" data-mode="dark"  title="Dark"></i>
   <i class="theme-switch fa-solid fa-circle-half-stroke fa-lg" data-mode="auto"  title="System Settings"></i>
 </button></div>

           <div class="navbar-item"><ul class="navbar-icon-links"
     aria-label="Icon Links">
         <li class="nav-item">


           <a href="https://github.com/apache/arrow" title="GitHub" class="nav-link pst-navbar-icon" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><i class="fa-brands fa-square-github fa-lg" aria-hidden="true"></i>
             <span class="sr-only">GitHub</span></a>
         </li>
         <li class="nav-item">


           <a href="https://www.linkedin.com/company/apache-arrow/" title="LinkedIn" class="nav-link pst-navbar-icon" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><i class="fa-brands fa-linkedin fa-lg" aria-hidden="true"></i>
             <span class="sr-only">LinkedIn</span></a>
         </li>
         <li class="nav-item">


           <a href="https://bsky.app/profile/arrow.apache.org" title="BlueSky" class="nav-link pst-navbar-icon" rel="noopener" target="_blank" data-bs-toggle="tooltip" data-bs-placement="bottom"><i class="fa-brands fa-bluesky fa-lg" aria-hidden="true"></i>
             <span class="sr-only">BlueSky</span></a>
         </li>
 </ul></div>

       </div>

   </div>


   <div class="sidebar-primary-items__end sidebar-primary__section">
       <div class="sidebar-primary-item">
 <div id="ethical-ad-placement"
       class="flat"
       data-ea-publisher="readthedocs"
       data-ea-type="readthedocs-sidebar"
       data-ea-manual="true">
 </div></div>
   </div>


       </div>

       <main id="main-content" class="bd-main" role="main">


           <div class="bd-content">
             <div class="bd-article-container">

               <div class="bd-header-article d-print-none">
 <div class="header-article-items header-article__inner">

     <div class="header-article-items__start">

         <div class="header-article-item">

 <nav aria-label="Breadcrumb" class="d-print-none">
   <ul class="bd-breadcrumbs">

     <li class="breadcrumb-item breadcrumb-home">
       <a href="../index.html" class="nav-link" aria-label="Home">
         <i class="fa-solid fa-home"></i>
       </a>
     </li>

     <li class="breadcrumb-item"><a href="index.html" class="nav-link">Module code</a></li>

     <li class="breadcrumb-item active" aria-current="page"><span class="ellipsis">collections</span></li>
   </ul>
 </nav>
 </div>

     </div>


 </div>
 </div>


 <div id="searchbox"></div>
                 <article class="bd-article">

   <h1>Source code for collections</h1><div class="highlight"><pre>
 <span></span><span class="sd">&#39;&#39;&#39;This module implements specialized container datatypes providing</span>
 <span class="sd">alternatives to Python&#39;s general purpose built-in containers, dict,</span>
 <span class="sd">list, set, and tuple.</span>

 <span class="sd">* namedtuple   factory function for creating tuple subclasses with named fields</span>
 <span class="sd">* deque        list-like container with fast appends and pops on either end</span>
 <span class="sd">* ChainMap     dict-like class for creating a single view of multiple mappings</span>
 <span class="sd">* Counter      dict subclass for counting hashable objects</span>
 <span class="sd">* OrderedDict  dict subclass that remembers the order entries were added</span>
 <span class="sd">* defaultdict  dict subclass that calls a factory function to supply missing values</span>
 <span class="sd">* UserDict     wrapper around dictionary objects for easier dict subclassing</span>
 <span class="sd">* UserList     wrapper around list objects for easier list subclassing</span>
 <span class="sd">* UserString   wrapper around string objects for easier string subclassing</span>

 <span class="sd">&#39;&#39;&#39;</span>

 <span class="n">__all__</span> <span class="o">=</span> <span class="p">[</span>
     <span class="s1">&#39;ChainMap&#39;</span><span class="p">,</span>
     <span class="s1">&#39;Counter&#39;</span><span class="p">,</span>
     <span class="s1">&#39;OrderedDict&#39;</span><span class="p">,</span>
     <span class="s1">&#39;UserDict&#39;</span><span class="p">,</span>
     <span class="s1">&#39;UserList&#39;</span><span class="p">,</span>
     <span class="s1">&#39;UserString&#39;</span><span class="p">,</span>
     <span class="s1">&#39;defaultdict&#39;</span><span class="p">,</span>
     <span class="s1">&#39;deque&#39;</span><span class="p">,</span>
     <span class="s1">&#39;namedtuple&#39;</span><span class="p">,</span>
 <span class="p">]</span>

 <span class="kn">import</span><span class="w"> </span><span class="nn">_collections_abc</span>
 <span class="kn">import</span><span class="w"> </span><span class="nn">sys</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="nn">_sys</span>

 <span class="n">_sys</span><span class="o">.</span><span class="n">modules</span><span class="p">[</span><span class="s1">&#39;collections.abc&#39;</span><span class="p">]</span> <span class="o">=</span> <span class="n">_collections_abc</span>
 <span class="n">abc</span> <span class="o">=</span> <span class="n">_collections_abc</span>

 <span class="kn">from</span><span class="w"> </span><span class="nn">itertools</span><span class="w"> </span><span class="kn">import</span> <span class="n">chain</span> <span class="k">as</span> <span class="n">_chain</span>
 <span class="kn">from</span><span class="w"> </span><span class="nn">itertools</span><span class="w"> </span><span class="kn">import</span> <span class="n">repeat</span> <span class="k">as</span> <span class="n">_repeat</span>
 <span class="kn">from</span><span class="w"> </span><span class="nn">itertools</span><span class="w"> </span><span class="kn">import</span> <span class="n">starmap</span> <span class="k">as</span> <span class="n">_starmap</span>
 <span class="kn">from</span><span class="w"> </span><span class="nn">keyword</span><span class="w"> </span><span class="kn">import</span> <span class="n">iskeyword</span> <span class="k">as</span> <span class="n">_iskeyword</span>
 <span class="kn">from</span><span class="w"> </span><span class="nn">operator</span><span class="w"> </span><span class="kn">import</span> <span class="n">eq</span> <span class="k">as</span> <span class="n">_eq</span>
 <span class="kn">from</span><span class="w"> </span><span class="nn">operator</span><span class="w"> </span><span class="kn">import</span> <span class="n">itemgetter</span> <span class="k">as</span> <span class="n">_itemgetter</span>
 <span class="kn">from</span><span class="w"> </span><span class="nn">reprlib</span><span class="w"> </span><span class="kn">import</span> <span class="n">recursive_repr</span> <span class="k">as</span> <span class="n">_recursive_repr</span>
 <span class="kn">from</span><span class="w"> </span><span class="nn">_weakref</span><span class="w"> </span><span class="kn">import</span> <span class="n">proxy</span> <span class="k">as</span> <span class="n">_proxy</span>

 <span class="k">try</span><span class="p">:</span>
     <span class="kn">from</span><span class="w"> </span><span class="nn">_collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">deque</span>
 <span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
     <span class="k">pass</span>
 <span class="k">else</span><span class="p">:</span>
     <span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableSequence</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">deque</span><span class="p">)</span>

 <span class="k">try</span><span class="p">:</span>
     <span class="kn">from</span><span class="w"> </span><span class="nn">_collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">_deque_iterator</span>
 <span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
     <span class="k">pass</span>

 <span class="k">try</span><span class="p">:</span>
     <span class="kn">from</span><span class="w"> </span><span class="nn">_collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">defaultdict</span>
 <span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
     <span class="k">pass</span>


 <span class="c1">################################################################################</span>
 <span class="c1">### OrderedDict</span>
 <span class="c1">################################################################################</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">_OrderedDictKeysView</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">KeysView</span><span class="p">):</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">yield from</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">)</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">_OrderedDictItemsView</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">ItemsView</span><span class="p">):</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">):</span>
             <span class="k">yield</span> <span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">[</span><span class="n">key</span><span class="p">])</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">_OrderedDictValuesView</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">ValuesView</span><span class="p">):</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">):</span>
             <span class="k">yield</span> <span class="bp">self</span><span class="o">.</span><span class="n">_mapping</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">_Link</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
     <span class="vm">__slots__</span> <span class="o">=</span> <span class="s1">&#39;prev&#39;</span><span class="p">,</span> <span class="s1">&#39;next&#39;</span><span class="p">,</span> <span class="s1">&#39;key&#39;</span><span class="p">,</span> <span class="s1">&#39;__weakref__&#39;</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">OrderedDict</span><span class="p">(</span><span class="nb">dict</span><span class="p">):</span>
     <span class="s1">&#39;Dictionary that remembers insertion order&#39;</span>
     <span class="c1"># An inherited dict maps keys to values.</span>
     <span class="c1"># The inherited dict provides __getitem__, __len__, __contains__, and get.</span>
     <span class="c1"># The remaining methods are order-aware.</span>
     <span class="c1"># Big-O running times for all methods are the same as regular dictionaries.</span>

     <span class="c1"># The internal self.__map dict maps keys to links in a doubly linked list.</span>
     <span class="c1"># The circular doubly linked list starts and ends with a sentinel element.</span>
     <span class="c1"># The sentinel element never gets deleted (this simplifies the algorithm).</span>
     <span class="c1"># The sentinel is in self.__hardroot with a weakref proxy in self.__root.</span>
     <span class="c1"># The prev links are weakref proxies (to prevent circular references).</span>
     <span class="c1"># Individual links are kept alive by the hard reference in self.__map.</span>
     <span class="c1"># Those hard references disappear when a key is deleted from an OrderedDict.</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__new__</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
         <span class="s2">&quot;Create the ordered dict object and set up the underlying structures.&quot;</span>
         <span class="bp">self</span> <span class="o">=</span> <span class="nb">dict</span><span class="o">.</span><span class="fm">__new__</span><span class="p">(</span><span class="bp">cls</span><span class="p">)</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">__hardroot</span> <span class="o">=</span> <span class="n">_Link</span><span class="p">()</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">__root</span> <span class="o">=</span> <span class="n">root</span> <span class="o">=</span> <span class="n">_proxy</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__hardroot</span><span class="p">)</span>
         <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">__map</span> <span class="o">=</span> <span class="p">{}</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="o">=</span><span class="p">(),</span> <span class="o">/</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Initialize an ordered dictionary.  The signature is the same as</span>
 <span class="sd">        regular dictionaries.  Keyword argument order is preserved.</span>
 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">__update</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span>
                     <span class="n">dict_setitem</span><span class="o">=</span><span class="nb">dict</span><span class="o">.</span><span class="fm">__setitem__</span><span class="p">,</span> <span class="n">proxy</span><span class="o">=</span><span class="n">_proxy</span><span class="p">,</span> <span class="n">Link</span><span class="o">=</span><span class="n">_Link</span><span class="p">):</span>
         <span class="s1">&#39;od.__setitem__(i, y) &lt;==&gt; od[i]=y&#39;</span>
         <span class="c1"># Setting a new item creates a new link at the end of the linked list,</span>
         <span class="c1"># and the inherited dictionary is updated with the new key/value pair.</span>
         <span class="k">if</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">link</span> <span class="o">=</span> <span class="n">Link</span><span class="p">()</span>
             <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
             <span class="n">last</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
             <span class="n">link</span><span class="o">.</span><span class="n">prev</span><span class="p">,</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span><span class="p">,</span> <span class="n">link</span><span class="o">.</span><span class="n">key</span> <span class="o">=</span> <span class="n">last</span><span class="p">,</span> <span class="n">root</span><span class="p">,</span> <span class="n">key</span>
             <span class="n">last</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link</span>
             <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">proxy</span><span class="p">(</span><span class="n">link</span><span class="p">)</span>
         <span class="n">dict_setitem</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">dict_delitem</span><span class="o">=</span><span class="nb">dict</span><span class="o">.</span><span class="fm">__delitem__</span><span class="p">):</span>
         <span class="s1">&#39;od.__delitem__(y) &lt;==&gt; del od[y]&#39;</span>
         <span class="c1"># Deleting an existing item uses self.__map to find the link which gets</span>
         <span class="c1"># removed by updating the links in the predecessor and successor nodes.</span>
         <span class="n">dict_delitem</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">)</span>
         <span class="n">link</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
         <span class="n">link_prev</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">prev</span>
         <span class="n">link_next</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span>
         <span class="n">link_prev</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link_next</span>
         <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">link_prev</span>
         <span class="n">link</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="kc">None</span>
         <span class="n">link</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="kc">None</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;od.__iter__() &lt;==&gt; iter(od)&#39;</span>
         <span class="c1"># Traverse the linked list in order.</span>
         <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
         <span class="n">curr</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span>
         <span class="k">while</span> <span class="n">curr</span> <span class="ow">is</span> <span class="ow">not</span> <span class="n">root</span><span class="p">:</span>
             <span class="k">yield</span> <span class="n">curr</span><span class="o">.</span><span class="n">key</span>
             <span class="n">curr</span> <span class="o">=</span> <span class="n">curr</span><span class="o">.</span><span class="n">next</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__reversed__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;od.__reversed__() &lt;==&gt; reversed(od)&#39;</span>
         <span class="c1"># Traverse the linked list in reverse order.</span>
         <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
         <span class="n">curr</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
         <span class="k">while</span> <span class="n">curr</span> <span class="ow">is</span> <span class="ow">not</span> <span class="n">root</span><span class="p">:</span>
             <span class="k">yield</span> <span class="n">curr</span><span class="o">.</span><span class="n">key</span>
             <span class="n">curr</span> <span class="o">=</span> <span class="n">curr</span><span class="o">.</span><span class="n">prev</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;od.clear() -&gt; None.  Remove all items from od.&#39;</span>
         <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
         <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span>
         <span class="nb">dict</span><span class="o">.</span><span class="n">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">popitem</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">last</span><span class="o">=</span><span class="kc">True</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Remove and return a (key, value) pair from the dictionary.</span>

 <span class="sd">        Pairs are returned in LIFO order if last is true or FIFO order if false.</span>
 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s1">&#39;dictionary is empty&#39;</span><span class="p">)</span>
         <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
         <span class="k">if</span> <span class="n">last</span><span class="p">:</span>
             <span class="n">link</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
             <span class="n">link_prev</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">prev</span>
             <span class="n">link_prev</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
             <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">link_prev</span>
         <span class="k">else</span><span class="p">:</span>
             <span class="n">link</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span>
             <span class="n">link_next</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span>
             <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link_next</span>
             <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span>
         <span class="n">key</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">key</span>
         <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
         <span class="n">value</span> <span class="o">=</span> <span class="nb">dict</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">move_to_end</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">last</span><span class="o">=</span><span class="kc">True</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Move an existing element to the end (or beginning if last is false).</span>

 <span class="sd">        Raise KeyError if the element does not exist.</span>
 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="n">link</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
         <span class="n">link_prev</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">prev</span>
         <span class="n">link_next</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span>
         <span class="n">soft_link</span> <span class="o">=</span> <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span>
         <span class="n">link_prev</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link_next</span>
         <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">link_prev</span>
         <span class="n">root</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__root</span>
         <span class="k">if</span> <span class="n">last</span><span class="p">:</span>
             <span class="n">last</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">prev</span>
             <span class="n">link</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">last</span>
             <span class="n">link</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">root</span>
             <span class="n">root</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">soft_link</span>
             <span class="n">last</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link</span>
         <span class="k">else</span><span class="p">:</span>
             <span class="n">first</span> <span class="o">=</span> <span class="n">root</span><span class="o">.</span><span class="n">next</span>
             <span class="n">link</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">root</span>
             <span class="n">link</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">first</span>
             <span class="n">first</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">soft_link</span>
             <span class="n">root</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__sizeof__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="n">sizeof</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">getsizeof</span>
         <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>                       <span class="c1"># number of links including root</span>
         <span class="n">size</span> <span class="o">=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">)</span>            <span class="c1"># instance dictionary</span>
         <span class="n">size</span> <span class="o">+=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="p">)</span> <span class="o">*</span> <span class="mi">2</span>          <span class="c1"># internal dict and inherited dict</span>
         <span class="n">size</span> <span class="o">+=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__hardroot</span><span class="p">)</span> <span class="o">*</span> <span class="n">n</span>     <span class="c1"># link objects</span>
         <span class="n">size</span> <span class="o">+=</span> <span class="n">sizeof</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">__root</span><span class="p">)</span> <span class="o">*</span> <span class="n">n</span>         <span class="c1"># proxy objects</span>
         <span class="k">return</span> <span class="n">size</span>

     <span class="n">update</span> <span class="o">=</span> <span class="n">__update</span> <span class="o">=</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="o">.</span><span class="n">update</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">keys</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s2">&quot;D.keys() -&gt; a set-like object providing a view on D&#39;s keys&quot;</span>
         <span class="k">return</span> <span class="n">_OrderedDictKeysView</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">items</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s2">&quot;D.items() -&gt; a set-like object providing a view on D&#39;s items&quot;</span>
         <span class="k">return</span> <span class="n">_OrderedDictItemsView</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">values</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s2">&quot;D.values() -&gt; an object providing a view on D&#39;s values&quot;</span>
         <span class="k">return</span> <span class="n">_OrderedDictValuesView</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="fm">__ne__</span> <span class="o">=</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="o">.</span><span class="fm">__ne__</span>

     <span class="n">__marker</span> <span class="o">=</span> <span class="nb">object</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="n">__marker</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;od.pop(k[,d]) -&gt; v, remove specified key and return the corresponding</span>
 <span class="sd">        value.  If key is not found, d is returned if given, otherwise KeyError</span>
 <span class="sd">        is raised.</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="n">marker</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__marker</span>
         <span class="n">result</span> <span class="o">=</span> <span class="nb">dict</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">marker</span><span class="p">)</span>
         <span class="k">if</span> <span class="n">result</span> <span class="ow">is</span> <span class="ow">not</span> <span class="n">marker</span><span class="p">:</span>
             <span class="c1"># The same as in __delitem__().</span>
             <span class="n">link</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__map</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
             <span class="n">link_prev</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">prev</span>
             <span class="n">link_next</span> <span class="o">=</span> <span class="n">link</span><span class="o">.</span><span class="n">next</span>
             <span class="n">link_prev</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">link_next</span>
             <span class="n">link_next</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="n">link_prev</span>
             <span class="n">link</span><span class="o">.</span><span class="n">prev</span> <span class="o">=</span> <span class="kc">None</span>
             <span class="n">link</span><span class="o">.</span><span class="n">next</span> <span class="o">=</span> <span class="kc">None</span>
             <span class="k">return</span> <span class="n">result</span>
         <span class="k">if</span> <span class="n">default</span> <span class="ow">is</span> <span class="n">marker</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">default</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">setdefault</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Insert key with a value of default if key is not in the dictionary.</span>

 <span class="sd">        Return the value for key if key is in the dictionary, else default.</span>
 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
             <span class="k">return</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
         <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">default</span>
         <span class="k">return</span> <span class="n">default</span>

     <span class="nd">@_recursive_repr</span><span class="p">()</span>
     <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;od.__repr__() &lt;==&gt; repr(od)&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="p">:</span>
             <span class="k">return</span> <span class="s1">&#39;</span><span class="si">%s</span><span class="s1">()&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="p">,)</span>
         <span class="k">return</span> <span class="s1">&#39;</span><span class="si">%s</span><span class="s1">(</span><span class="si">%r</span><span class="s1">)&#39;</span> <span class="o">%</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="p">,</span> <span class="nb">dict</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__reduce__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Return state information for pickling&#39;</span>
         <span class="n">state</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__getstate__</span><span class="p">()</span>
         <span class="k">if</span> <span class="n">state</span><span class="p">:</span>
             <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">state</span><span class="p">,</span> <span class="nb">tuple</span><span class="p">):</span>
                 <span class="n">state</span><span class="p">,</span> <span class="n">slots</span> <span class="o">=</span> <span class="n">state</span>
             <span class="k">else</span><span class="p">:</span>
                 <span class="n">slots</span> <span class="o">=</span> <span class="p">{}</span>
             <span class="n">state</span> <span class="o">=</span> <span class="n">state</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
             <span class="n">slots</span> <span class="o">=</span> <span class="n">slots</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
             <span class="k">for</span> <span class="n">k</span> <span class="ow">in</span> <span class="nb">vars</span><span class="p">(</span><span class="n">OrderedDict</span><span class="p">()):</span>
                 <span class="n">state</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span>
                 <span class="n">slots</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">k</span><span class="p">,</span> <span class="kc">None</span><span class="p">)</span>
             <span class="k">if</span> <span class="n">slots</span><span class="p">:</span>
                 <span class="n">state</span> <span class="o">=</span> <span class="n">state</span><span class="p">,</span> <span class="n">slots</span>
             <span class="k">else</span><span class="p">:</span>
                 <span class="n">state</span> <span class="o">=</span> <span class="n">state</span> <span class="ow">or</span> <span class="kc">None</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">,</span> <span class="p">(),</span> <span class="n">state</span><span class="p">,</span> <span class="kc">None</span><span class="p">,</span> <span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;od.copy() -&gt; a shallow copy of od&#39;</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="nd">@classmethod</span>
     <span class="k">def</span><span class="w"> </span><span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="n">value</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Create a new ordered dictionary with keys from iterable and values set to value.</span>
 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="bp">self</span> <span class="o">=</span> <span class="bp">cls</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
             <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;od.__eq__(y) &lt;==&gt; od==y.  Comparison to another OD is order-sensitive</span>
 <span class="sd">        while comparison to a regular mapping is order-insensitive.</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">OrderedDict</span><span class="p">):</span>
             <span class="k">return</span> <span class="nb">dict</span><span class="o">.</span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span> <span class="ow">and</span> <span class="nb">all</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">_eq</span><span class="p">,</span> <span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">))</span>
         <span class="k">return</span> <span class="nb">dict</span><span class="o">.</span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ior__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__or__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">dict</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">new</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
         <span class="n">new</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">new</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ror__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">dict</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">new</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
         <span class="n">new</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">new</span>


 <span class="k">try</span><span class="p">:</span>
     <span class="kn">from</span><span class="w"> </span><span class="nn">_collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">OrderedDict</span>
 <span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
     <span class="c1"># Leave the pure Python version in place.</span>
     <span class="k">pass</span>


 <span class="c1">################################################################################</span>
 <span class="c1">### namedtuple</span>
 <span class="c1">################################################################################</span>

 <span class="k">try</span><span class="p">:</span>
     <span class="kn">from</span><span class="w"> </span><span class="nn">_collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">_tuplegetter</span>
 <span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
     <span class="n">_tuplegetter</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">index</span><span class="p">,</span> <span class="n">doc</span><span class="p">:</span> <span class="nb">property</span><span class="p">(</span><span class="n">_itemgetter</span><span class="p">(</span><span class="n">index</span><span class="p">),</span> <span class="n">doc</span><span class="o">=</span><span class="n">doc</span><span class="p">)</span>

 <span class="k">def</span><span class="w"> </span><span class="nf">namedtuple</span><span class="p">(</span><span class="n">typename</span><span class="p">,</span> <span class="n">field_names</span><span class="p">,</span> <span class="o">*</span><span class="p">,</span> <span class="n">rename</span><span class="o">=</span><span class="kc">False</span><span class="p">,</span> <span class="n">defaults</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">module</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
 <span class="w">    </span><span class="sd">&quot;&quot;&quot;Returns a new subclass of tuple with named fields.</span>

 <span class="sd">    &gt;&gt;&gt; Point = namedtuple(&#39;Point&#39;, [&#39;x&#39;, &#39;y&#39;])</span>
 <span class="sd">    &gt;&gt;&gt; Point.__doc__                   # docstring for the new class</span>
 <span class="sd">    &#39;Point(x, y)&#39;</span>
 <span class="sd">    &gt;&gt;&gt; p = Point(11, y=22)             # instantiate with positional args or keywords</span>
 <span class="sd">    &gt;&gt;&gt; p[0] + p[1]                     # indexable like a plain tuple</span>
 <span class="sd">    33</span>
 <span class="sd">    &gt;&gt;&gt; x, y = p                        # unpack like a regular tuple</span>
 <span class="sd">    &gt;&gt;&gt; x, y</span>
 <span class="sd">    (11, 22)</span>
 <span class="sd">    &gt;&gt;&gt; p.x + p.y                       # fields also accessible by name</span>
 <span class="sd">    33</span>
 <span class="sd">    &gt;&gt;&gt; d = p._asdict()                 # convert to a dictionary</span>
 <span class="sd">    &gt;&gt;&gt; d[&#39;x&#39;]</span>
 <span class="sd">    11</span>
 <span class="sd">    &gt;&gt;&gt; Point(**d)                      # convert from a dictionary</span>
 <span class="sd">    Point(x=11, y=22)</span>
 <span class="sd">    &gt;&gt;&gt; p._replace(x=100)               # _replace() is like str.replace() but targets named fields</span>
 <span class="sd">    Point(x=100, y=22)</span>

 <span class="sd">    &quot;&quot;&quot;</span>

     <span class="c1"># Validate the field names.  At the user&#39;s option, either generate an error</span>
     <span class="c1"># message or automatically replace the field name with a valid name.</span>
     <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">field_names</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
         <span class="n">field_names</span> <span class="o">=</span> <span class="n">field_names</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="s1">&#39;,&#39;</span><span class="p">,</span> <span class="s1">&#39; &#39;</span><span class="p">)</span><span class="o">.</span><span class="n">split</span><span class="p">()</span>
     <span class="n">field_names</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="nb">str</span><span class="p">,</span> <span class="n">field_names</span><span class="p">))</span>
     <span class="n">typename</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">intern</span><span class="p">(</span><span class="nb">str</span><span class="p">(</span><span class="n">typename</span><span class="p">))</span>

     <span class="k">if</span> <span class="n">rename</span><span class="p">:</span>
         <span class="n">seen</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">name</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">field_names</span><span class="p">):</span>
             <span class="k">if</span> <span class="p">(</span><span class="ow">not</span> <span class="n">name</span><span class="o">.</span><span class="n">isidentifier</span><span class="p">()</span>
                 <span class="ow">or</span> <span class="n">_iskeyword</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>
                 <span class="ow">or</span> <span class="n">name</span><span class="o">.</span><span class="n">startswith</span><span class="p">(</span><span class="s1">&#39;_&#39;</span><span class="p">)</span>
                 <span class="ow">or</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">seen</span><span class="p">):</span>
                 <span class="n">field_names</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;_</span><span class="si">{</span><span class="n">index</span><span class="si">}</span><span class="s1">&#39;</span>
             <span class="n">seen</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>

     <span class="k">for</span> <span class="n">name</span> <span class="ow">in</span> <span class="p">[</span><span class="n">typename</span><span class="p">]</span> <span class="o">+</span> <span class="n">field_names</span><span class="p">:</span>
         <span class="k">if</span> <span class="nb">type</span><span class="p">(</span><span class="n">name</span><span class="p">)</span> <span class="ow">is</span> <span class="ow">not</span> <span class="nb">str</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;Type names and field names must be strings&#39;</span><span class="p">)</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="n">name</span><span class="o">.</span><span class="n">isidentifier</span><span class="p">():</span>
             <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s1">&#39;Type names and field names must be valid &#39;</span>
                              <span class="sa">f</span><span class="s1">&#39;identifiers: </span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
         <span class="k">if</span> <span class="n">_iskeyword</span><span class="p">(</span><span class="n">name</span><span class="p">):</span>
             <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s1">&#39;Type names and field names cannot be a &#39;</span>
                              <span class="sa">f</span><span class="s1">&#39;keyword: </span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>

     <span class="n">seen</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
     <span class="k">for</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">field_names</span><span class="p">:</span>
         <span class="k">if</span> <span class="n">name</span><span class="o">.</span><span class="n">startswith</span><span class="p">(</span><span class="s1">&#39;_&#39;</span><span class="p">)</span> <span class="ow">and</span> <span class="ow">not</span> <span class="n">rename</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s1">&#39;Field names cannot start with an underscore: &#39;</span>
                              <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
         <span class="k">if</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">seen</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Encountered duplicate field name: </span><span class="si">{</span><span class="n">name</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
         <span class="n">seen</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">name</span><span class="p">)</span>

     <span class="n">field_defaults</span> <span class="o">=</span> <span class="p">{}</span>
     <span class="k">if</span> <span class="n">defaults</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
         <span class="n">defaults</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">(</span><span class="n">defaults</span><span class="p">)</span>
         <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">defaults</span><span class="p">)</span> <span class="o">&gt;</span> <span class="nb">len</span><span class="p">(</span><span class="n">field_names</span><span class="p">):</span>
             <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="s1">&#39;Got more default values than field names&#39;</span><span class="p">)</span>
         <span class="n">field_defaults</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span><span class="nb">reversed</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="nb">zip</span><span class="p">(</span><span class="nb">reversed</span><span class="p">(</span><span class="n">field_names</span><span class="p">),</span>
                                                 <span class="nb">reversed</span><span class="p">(</span><span class="n">defaults</span><span class="p">)))))</span>

     <span class="c1"># Variables used in the methods and docstrings</span>
     <span class="n">field_names</span> <span class="o">=</span> <span class="nb">tuple</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">_sys</span><span class="o">.</span><span class="n">intern</span><span class="p">,</span> <span class="n">field_names</span><span class="p">))</span>
     <span class="n">num_fields</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">field_names</span><span class="p">)</span>
     <span class="n">arg_list</span> <span class="o">=</span> <span class="s1">&#39;, &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">field_names</span><span class="p">)</span>
     <span class="k">if</span> <span class="n">num_fields</span> <span class="o">==</span> <span class="mi">1</span><span class="p">:</span>
         <span class="n">arg_list</span> <span class="o">+=</span> <span class="s1">&#39;,&#39;</span>
     <span class="n">repr_fmt</span> <span class="o">=</span> <span class="s1">&#39;(&#39;</span> <span class="o">+</span> <span class="s1">&#39;, &#39;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">name</span><span class="si">}</span><span class="s1">=%r&#39;</span> <span class="k">for</span> <span class="n">name</span> <span class="ow">in</span> <span class="n">field_names</span><span class="p">)</span> <span class="o">+</span> <span class="s1">&#39;)&#39;</span>
     <span class="n">tuple_new</span> <span class="o">=</span> <span class="nb">tuple</span><span class="o">.</span><span class="fm">__new__</span>
     <span class="n">_dict</span><span class="p">,</span> <span class="n">_tuple</span><span class="p">,</span> <span class="n">_len</span><span class="p">,</span> <span class="n">_map</span><span class="p">,</span> <span class="n">_zip</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">,</span> <span class="nb">tuple</span><span class="p">,</span> <span class="nb">len</span><span class="p">,</span> <span class="nb">map</span><span class="p">,</span> <span class="nb">zip</span>

     <span class="c1"># Create all the named tuple methods to be added to the class namespace</span>

     <span class="n">namespace</span> <span class="o">=</span> <span class="p">{</span>
         <span class="s1">&#39;_tuple_new&#39;</span><span class="p">:</span> <span class="n">tuple_new</span><span class="p">,</span>
         <span class="s1">&#39;__builtins__&#39;</span><span class="p">:</span> <span class="p">{},</span>
         <span class="s1">&#39;__name__&#39;</span><span class="p">:</span> <span class="sa">f</span><span class="s1">&#39;namedtuple_</span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">&#39;</span><span class="p">,</span>
     <span class="p">}</span>
     <span class="n">code</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;lambda _cls, </span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">: _tuple_new(_cls, (</span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">))&#39;</span>
     <span class="fm">__new__</span> <span class="o">=</span> <span class="nb">eval</span><span class="p">(</span><span class="n">code</span><span class="p">,</span> <span class="n">namespace</span><span class="p">)</span>
     <span class="fm">__new__</span><span class="o">.</span><span class="vm">__name__</span> <span class="o">=</span> <span class="s1">&#39;__new__&#39;</span>
     <span class="fm">__new__</span><span class="o">.</span><span class="vm">__doc__</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;Create new instance of </span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">(</span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">)&#39;</span>
     <span class="k">if</span> <span class="n">defaults</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
         <span class="fm">__new__</span><span class="o">.</span><span class="vm">__defaults__</span> <span class="o">=</span> <span class="n">defaults</span>

     <span class="nd">@classmethod</span>
     <span class="k">def</span><span class="w"> </span><span class="nf">_make</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">):</span>
         <span class="n">result</span> <span class="o">=</span> <span class="n">tuple_new</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">)</span>
         <span class="k">if</span> <span class="n">_len</span><span class="p">(</span><span class="n">result</span><span class="p">)</span> <span class="o">!=</span> <span class="n">num_fields</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Expected </span><span class="si">{</span><span class="n">num_fields</span><span class="si">}</span><span class="s1"> arguments, got </span><span class="si">{</span><span class="nb">len</span><span class="p">(</span><span class="n">result</span><span class="p">)</span><span class="si">}</span><span class="s1">&#39;</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="n">_make</span><span class="o">.</span><span class="vm">__func__</span><span class="o">.</span><span class="vm">__doc__</span> <span class="o">=</span> <span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Make a new </span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1"> object from a sequence &#39;</span>
                               <span class="s1">&#39;or iterable&#39;</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">_replace</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
         <span class="n">result</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">_make</span><span class="p">(</span><span class="n">_map</span><span class="p">(</span><span class="n">kwds</span><span class="o">.</span><span class="n">pop</span><span class="p">,</span> <span class="n">field_names</span><span class="p">,</span> <span class="bp">self</span><span class="p">))</span>
         <span class="k">if</span> <span class="n">kwds</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">TypeError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Got unexpected field names: </span><span class="si">{</span><span class="nb">list</span><span class="p">(</span><span class="n">kwds</span><span class="p">)</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="n">_replace</span><span class="o">.</span><span class="vm">__doc__</span> <span class="o">=</span> <span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Return a new </span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1"> object replacing specified &#39;</span>
                         <span class="s1">&#39;fields with new values&#39;</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Return a nicely formatted representation string&#39;</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span> <span class="o">+</span> <span class="n">repr_fmt</span> <span class="o">%</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">_asdict</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Return a new dict which maps field names to their values.&#39;</span>
         <span class="k">return</span> <span class="n">_dict</span><span class="p">(</span><span class="n">_zip</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">_fields</span><span class="p">,</span> <span class="bp">self</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__getnewargs__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Return self as a plain tuple.  Used by copy and pickle.&#39;</span>
         <span class="k">return</span> <span class="n">_tuple</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="c1"># Modify function metadata to help with introspection and debugging</span>
     <span class="k">for</span> <span class="n">method</span> <span class="ow">in</span> <span class="p">(</span>
         <span class="fm">__new__</span><span class="p">,</span>
         <span class="n">_make</span><span class="o">.</span><span class="vm">__func__</span><span class="p">,</span>
         <span class="n">_replace</span><span class="p">,</span>
         <span class="fm">__repr__</span><span class="p">,</span>
         <span class="n">_asdict</span><span class="p">,</span>
         <span class="n">__getnewargs__</span><span class="p">,</span>
     <span class="p">):</span>
         <span class="n">method</span><span class="o">.</span><span class="vm">__qualname__</span> <span class="o">=</span> <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">.</span><span class="si">{</span><span class="n">method</span><span class="o">.</span><span class="vm">__name__</span><span class="si">}</span><span class="s1">&#39;</span>

     <span class="c1"># Build-up the class namespace dictionary</span>
     <span class="c1"># and use type() to build the result class</span>
     <span class="n">class_namespace</span> <span class="o">=</span> <span class="p">{</span>
         <span class="s1">&#39;__doc__&#39;</span><span class="p">:</span> <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="n">typename</span><span class="si">}</span><span class="s1">(</span><span class="si">{</span><span class="n">arg_list</span><span class="si">}</span><span class="s1">)&#39;</span><span class="p">,</span>
         <span class="s1">&#39;__slots__&#39;</span><span class="p">:</span> <span class="p">(),</span>
         <span class="s1">&#39;_fields&#39;</span><span class="p">:</span> <span class="n">field_names</span><span class="p">,</span>
         <span class="s1">&#39;_field_defaults&#39;</span><span class="p">:</span> <span class="n">field_defaults</span><span class="p">,</span>
         <span class="s1">&#39;__new__&#39;</span><span class="p">:</span> <span class="fm">__new__</span><span class="p">,</span>
         <span class="s1">&#39;_make&#39;</span><span class="p">:</span> <span class="n">_make</span><span class="p">,</span>
         <span class="s1">&#39;__replace__&#39;</span><span class="p">:</span> <span class="n">_replace</span><span class="p">,</span>
         <span class="s1">&#39;_replace&#39;</span><span class="p">:</span> <span class="n">_replace</span><span class="p">,</span>
         <span class="s1">&#39;__repr__&#39;</span><span class="p">:</span> <span class="fm">__repr__</span><span class="p">,</span>
         <span class="s1">&#39;_asdict&#39;</span><span class="p">:</span> <span class="n">_asdict</span><span class="p">,</span>
         <span class="s1">&#39;__getnewargs__&#39;</span><span class="p">:</span> <span class="n">__getnewargs__</span><span class="p">,</span>
         <span class="s1">&#39;__match_args__&#39;</span><span class="p">:</span> <span class="n">field_names</span><span class="p">,</span>
     <span class="p">}</span>
     <span class="k">for</span> <span class="n">index</span><span class="p">,</span> <span class="n">name</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">field_names</span><span class="p">):</span>
         <span class="n">doc</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">intern</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Alias for field number </span><span class="si">{</span><span class="n">index</span><span class="si">}</span><span class="s1">&#39;</span><span class="p">)</span>
         <span class="n">class_namespace</span><span class="p">[</span><span class="n">name</span><span class="p">]</span> <span class="o">=</span> <span class="n">_tuplegetter</span><span class="p">(</span><span class="n">index</span><span class="p">,</span> <span class="n">doc</span><span class="p">)</span>

     <span class="n">result</span> <span class="o">=</span> <span class="nb">type</span><span class="p">(</span><span class="n">typename</span><span class="p">,</span> <span class="p">(</span><span class="nb">tuple</span><span class="p">,),</span> <span class="n">class_namespace</span><span class="p">)</span>

     <span class="c1"># For pickling to work, the __module__ variable needs to be set to the frame</span>
     <span class="c1"># where the named tuple is created.  Bypass this step in environments where</span>
     <span class="c1"># sys._getframe is not defined (Jython for example) or sys._getframe is not</span>
     <span class="c1"># defined for arguments greater than 0 (IronPython), or where the user has</span>
     <span class="c1"># specified a particular module.</span>
     <span class="k">if</span> <span class="n">module</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
         <span class="k">try</span><span class="p">:</span>
             <span class="n">module</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">_getframemodulename</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="ow">or</span> <span class="s1">&#39;__main__&#39;</span>
         <span class="k">except</span> <span class="ne">AttributeError</span><span class="p">:</span>
             <span class="k">try</span><span class="p">:</span>
                 <span class="n">module</span> <span class="o">=</span> <span class="n">_sys</span><span class="o">.</span><span class="n">_getframe</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span><span class="o">.</span><span class="n">f_globals</span><span class="o">.</span><span class="n">get</span><span class="p">(</span><span class="s1">&#39;__name__&#39;</span><span class="p">,</span> <span class="s1">&#39;__main__&#39;</span><span class="p">)</span>
             <span class="k">except</span> <span class="p">(</span><span class="ne">AttributeError</span><span class="p">,</span> <span class="ne">ValueError</span><span class="p">):</span>
                 <span class="k">pass</span>
     <span class="k">if</span> <span class="n">module</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
         <span class="n">result</span><span class="o">.</span><span class="vm">__module__</span> <span class="o">=</span> <span class="n">module</span>

     <span class="k">return</span> <span class="n">result</span>


 <span class="c1">########################################################################</span>
 <span class="c1">###  Counter</span>
 <span class="c1">########################################################################</span>

 <span class="k">def</span><span class="w"> </span><span class="nf">_count_elements</span><span class="p">(</span><span class="n">mapping</span><span class="p">,</span> <span class="n">iterable</span><span class="p">):</span>
     <span class="s1">&#39;Tally elements from the iterable.&#39;</span>
     <span class="n">mapping_get</span> <span class="o">=</span> <span class="n">mapping</span><span class="o">.</span><span class="n">get</span>
     <span class="k">for</span> <span class="n">elem</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
         <span class="n">mapping</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">mapping_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>

 <span class="k">try</span><span class="p">:</span>                                    <span class="c1"># Load C helper function if available</span>
     <span class="kn">from</span><span class="w"> </span><span class="nn">_collections</span><span class="w"> </span><span class="kn">import</span> <span class="n">_count_elements</span>
 <span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
     <span class="k">pass</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">Counter</span><span class="p">(</span><span class="nb">dict</span><span class="p">):</span>
 <span class="w">    </span><span class="sd">&#39;&#39;&#39;Dict subclass for counting hashable items.  Sometimes called a bag</span>
 <span class="sd">    or multiset.  Elements are stored as dictionary keys and their counts</span>
 <span class="sd">    are stored as dictionary values.</span>

 <span class="sd">    &gt;&gt;&gt; c = Counter(&#39;abcdeabcdabcaba&#39;)  # count elements from a string</span>

 <span class="sd">    &gt;&gt;&gt; c.most_common(3)                # three most common elements</span>
 <span class="sd">    [(&#39;a&#39;, 5), (&#39;b&#39;, 4), (&#39;c&#39;, 3)]</span>
 <span class="sd">    &gt;&gt;&gt; sorted(c)                       # list all unique elements</span>
 <span class="sd">    [&#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;]</span>
 <span class="sd">    &gt;&gt;&gt; &#39;&#39;.join(sorted(c.elements()))   # list elements with repetitions</span>
 <span class="sd">    &#39;aaaaabbbbcccdde&#39;</span>
 <span class="sd">    &gt;&gt;&gt; sum(c.values())                 # total of all counts</span>
 <span class="sd">    15</span>

 <span class="sd">    &gt;&gt;&gt; c[&#39;a&#39;]                          # count of letter &#39;a&#39;</span>
 <span class="sd">    5</span>
 <span class="sd">    &gt;&gt;&gt; for elem in &#39;shazam&#39;:           # update counts from an iterable</span>
 <span class="sd">    ...     c[elem] += 1                # by adding 1 to each element&#39;s count</span>
 <span class="sd">    &gt;&gt;&gt; c[&#39;a&#39;]                          # now there are seven &#39;a&#39;</span>
 <span class="sd">    7</span>
 <span class="sd">    &gt;&gt;&gt; del c[&#39;b&#39;]                      # remove all &#39;b&#39;</span>
 <span class="sd">    &gt;&gt;&gt; c[&#39;b&#39;]                          # now there are zero &#39;b&#39;</span>
 <span class="sd">    0</span>

 <span class="sd">    &gt;&gt;&gt; d = Counter(&#39;simsalabim&#39;)       # make another counter</span>
 <span class="sd">    &gt;&gt;&gt; c.update(d)                     # add in the second counter</span>
 <span class="sd">    &gt;&gt;&gt; c[&#39;a&#39;]                          # now there are nine &#39;a&#39;</span>
 <span class="sd">    9</span>

 <span class="sd">    &gt;&gt;&gt; c.clear()                       # empty the counter</span>
 <span class="sd">    &gt;&gt;&gt; c</span>
 <span class="sd">    Counter()</span>

 <span class="sd">    Note:  If a count is set to zero or reduced to zero, it will remain</span>
 <span class="sd">    in the counter until the entry is deleted or the counter is cleared:</span>

 <span class="sd">    &gt;&gt;&gt; c = Counter(&#39;aaabbc&#39;)</span>
 <span class="sd">    &gt;&gt;&gt; c[&#39;b&#39;] -= 2                     # reduce the count of &#39;b&#39; by two</span>
 <span class="sd">    &gt;&gt;&gt; c.most_common()                 # &#39;b&#39; is still in, but its count is zero</span>
 <span class="sd">    [(&#39;a&#39;, 3), (&#39;c&#39;, 1), (&#39;b&#39;, 0)]</span>

 <span class="sd">    &#39;&#39;&#39;</span>
     <span class="c1"># References:</span>
     <span class="c1">#   http://en.wikipedia.org/wiki/Multiset</span>
     <span class="c1">#   http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html</span>
     <span class="c1">#   http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm</span>
     <span class="c1">#   http://code.activestate.com/recipes/259174/</span>
     <span class="c1">#   Knuth, TAOCP Vol. II section 4.6.3</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">iterable</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Create a new, empty Counter object.  And if given, count elements</span>
 <span class="sd">        from an input iterable.  Or, initialize the count from another mapping</span>
 <span class="sd">        of elements to their counts.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter()                           # a new, empty counter</span>
 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;gallahad&#39;)                 # a new counter from an iterable</span>
 <span class="sd">        &gt;&gt;&gt; c = Counter({&#39;a&#39;: 4, &#39;b&#39;: 2})           # a new counter from a mapping</span>
 <span class="sd">        &gt;&gt;&gt; c = Counter(a=4, b=2)                   # a new counter from keyword args</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="nb">super</span><span class="p">()</span><span class="o">.</span><span class="fm">__init__</span><span class="p">()</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">iterable</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__missing__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="s1">&#39;The count of elements not in the Counter is zero.&#39;</span>
         <span class="c1"># Needed so that self[missing_item] does not raise KeyError</span>
         <span class="k">return</span> <span class="mi">0</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">total</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Sum of the counts&#39;</span>
         <span class="k">return</span> <span class="nb">sum</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">values</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">most_common</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;List the n most common elements and their counts from the most</span>
 <span class="sd">        common to the least.  If n is None, then list all element counts.</span>

 <span class="sd">        &gt;&gt;&gt; Counter(&#39;abracadabra&#39;).most_common(3)</span>
 <span class="sd">        [(&#39;a&#39;, 5), (&#39;b&#39;, 2), (&#39;r&#39;, 2)]</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="c1"># Emulate Bag.sortedByCount from Smalltalk</span>
         <span class="k">if</span> <span class="n">n</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
             <span class="k">return</span> <span class="nb">sorted</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">(),</span> <span class="n">key</span><span class="o">=</span><span class="n">_itemgetter</span><span class="p">(</span><span class="mi">1</span><span class="p">),</span> <span class="n">reverse</span><span class="o">=</span><span class="kc">True</span><span class="p">)</span>

         <span class="c1"># Lazy import to speedup Python startup time</span>
         <span class="kn">import</span><span class="w"> </span><span class="nn">heapq</span>
         <span class="k">return</span> <span class="n">heapq</span><span class="o">.</span><span class="n">nlargest</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">(),</span> <span class="n">key</span><span class="o">=</span><span class="n">_itemgetter</span><span class="p">(</span><span class="mi">1</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">elements</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Iterator over elements repeating each as many times as its count.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;ABCABC&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; sorted(c.elements())</span>
 <span class="sd">        [&#39;A&#39;, &#39;A&#39;, &#39;B&#39;, &#39;B&#39;, &#39;C&#39;, &#39;C&#39;]</span>

 <span class="sd">        Knuth&#39;s example for prime factors of 1836:  2**2 * 3**3 * 17**1</span>

 <span class="sd">        &gt;&gt;&gt; import math</span>
 <span class="sd">        &gt;&gt;&gt; prime_factors = Counter({2: 2, 3: 3, 17: 1})</span>
 <span class="sd">        &gt;&gt;&gt; math.prod(prime_factors.elements())</span>
 <span class="sd">        1836</span>

 <span class="sd">        Note, if an element&#39;s count has been set to zero or is a negative</span>
 <span class="sd">        number, elements() will ignore it.</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="c1"># Emulate Bag.do from Smalltalk and Multiset.begin from C++.</span>
         <span class="k">return</span> <span class="n">_chain</span><span class="o">.</span><span class="n">from_iterable</span><span class="p">(</span><span class="n">_starmap</span><span class="p">(</span><span class="n">_repeat</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()))</span>

     <span class="c1"># Override dict methods where necessary</span>

     <span class="nd">@classmethod</span>
     <span class="k">def</span><span class="w"> </span><span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="n">v</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="c1"># There is no equivalent method for counters because the semantics</span>
         <span class="c1"># would be ambiguous in cases such as Counter.fromkeys(&#39;aaabbc&#39;, v=2).</span>
         <span class="c1"># Initializing counters to zero values isn&#39;t necessary because zero</span>
         <span class="c1"># is already the default value for counter lookups.  Initializing</span>
         <span class="c1"># to one is easily accomplished with Counter(set(iterable)).  For</span>
         <span class="c1"># more exotic cases, create a dictionary first using a dictionary</span>
         <span class="c1"># comprehension or dict.fromkeys().</span>
         <span class="k">raise</span> <span class="ne">NotImplementedError</span><span class="p">(</span>
             <span class="s1">&#39;Counter.fromkeys() is undefined.  Use Counter(iterable) instead.&#39;</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">update</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">iterable</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Like dict.update() but add counts instead of replacing them.</span>

 <span class="sd">        Source can be an iterable, a dictionary, or another Counter instance.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;which&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c.update(&#39;witch&#39;)           # add elements from another iterable</span>
 <span class="sd">        &gt;&gt;&gt; d = Counter(&#39;watch&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c.update(d)                 # add elements from another counter</span>
 <span class="sd">        &gt;&gt;&gt; c[&#39;h&#39;]                      # four &#39;h&#39; in which, witch, and watch</span>
 <span class="sd">        4</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="c1"># The regular dict.update() operation makes no sense here because the</span>
         <span class="c1"># replace behavior results in some of the original untouched counts</span>
         <span class="c1"># being mixed-in with all of the other counts for a mismash that</span>
         <span class="c1"># doesn&#39;t have a straight-forward interpretation in most counting</span>
         <span class="c1"># contexts.  Instead, we implement straight-addition.  Both the inputs</span>
         <span class="c1"># and outputs are allowed to contain zero and negative counts.</span>

         <span class="k">if</span> <span class="n">iterable</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
             <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">iterable</span><span class="p">,</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">Mapping</span><span class="p">):</span>
                 <span class="k">if</span> <span class="bp">self</span><span class="p">:</span>
                     <span class="n">self_get</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">get</span>
                     <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">iterable</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
                         <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span> <span class="o">+</span> <span class="n">self_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span>
                 <span class="k">else</span><span class="p">:</span>
                     <span class="c1"># fast path when counter is empty</span>
                     <span class="nb">super</span><span class="p">()</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">iterable</span><span class="p">)</span>
             <span class="k">else</span><span class="p">:</span>
                 <span class="n">_count_elements</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">iterable</span><span class="p">)</span>
         <span class="k">if</span> <span class="n">kwds</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">kwds</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">subtract</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">iterable</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Like dict.update() but subtracts counts instead of replacing them.</span>
 <span class="sd">        Counts can be reduced below zero.  Both the inputs and outputs are</span>
 <span class="sd">        allowed to contain zero and negative counts.</span>

 <span class="sd">        Source can be an iterable, a dictionary, or another Counter instance.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;which&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c.subtract(&#39;witch&#39;)             # subtract elements from another iterable</span>
 <span class="sd">        &gt;&gt;&gt; c.subtract(Counter(&#39;watch&#39;))    # subtract elements from another counter</span>
 <span class="sd">        &gt;&gt;&gt; c[&#39;h&#39;]                          # 2 in which, minus 1 in witch, minus 1 in watch</span>
 <span class="sd">        0</span>
 <span class="sd">        &gt;&gt;&gt; c[&#39;w&#39;]                          # 1 in which, minus 1 in witch, minus 1 in watch</span>
 <span class="sd">        -1</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="n">iterable</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
             <span class="n">self_get</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">get</span>
             <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">iterable</span><span class="p">,</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">Mapping</span><span class="p">):</span>
                 <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">iterable</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
                     <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">self_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">-</span> <span class="n">count</span>
             <span class="k">else</span><span class="p">:</span>
                 <span class="k">for</span> <span class="n">elem</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
                     <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">self_get</span><span class="p">(</span><span class="n">elem</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
         <span class="k">if</span> <span class="n">kwds</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">subtract</span><span class="p">(</span><span class="n">kwds</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Return a shallow copy.&#39;</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__reduce__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">,</span> <span class="p">(</span><span class="nb">dict</span><span class="p">(</span><span class="bp">self</span><span class="p">),)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">elem</span><span class="p">):</span>
         <span class="s1">&#39;Like dict.__delitem__() but does not raise KeyError for missing values.&#39;</span>
         <span class="k">if</span> <span class="n">elem</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
             <span class="nb">super</span><span class="p">()</span><span class="o">.</span><span class="fm">__delitem__</span><span class="p">(</span><span class="n">elem</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="p">:</span>
             <span class="k">return</span> <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="si">}</span><span class="s1">()&#39;</span>
         <span class="k">try</span><span class="p">:</span>
             <span class="c1"># dict() preserves the ordering returned by most_common()</span>
             <span class="n">d</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">most_common</span><span class="p">())</span>
         <span class="k">except</span> <span class="ne">TypeError</span><span class="p">:</span>
             <span class="c1"># handle case where values are not orderable</span>
             <span class="n">d</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
         <span class="k">return</span> <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="si">}</span><span class="s1">(</span><span class="si">{</span><span class="n">d</span><span class="si">!r}</span><span class="s1">)&#39;</span>

     <span class="c1"># Multiset-style mathematical operations discussed in:</span>
     <span class="c1">#       Knuth TAOCP Volume II section 4.6.3 exercise 19</span>
     <span class="c1">#       and at http://en.wikipedia.org/wiki/Multiset</span>
     <span class="c1">#</span>
     <span class="c1"># Outputs guaranteed to only include positive counts.</span>
     <span class="c1">#</span>
     <span class="c1"># To strip negative and zero counts, add-in an empty counter:</span>
     <span class="c1">#       c += Counter()</span>
     <span class="c1">#</span>
     <span class="c1"># Results are ordered according to when an element is first</span>
     <span class="c1"># encountered in the left operand and then by the order</span>
     <span class="c1"># encountered in the right operand.</span>
     <span class="c1">#</span>
     <span class="c1"># When the multiplicities are all zero or one, multiset operations</span>
     <span class="c1"># are guaranteed to be equivalent to the corresponding operations</span>
     <span class="c1"># for regular sets.</span>
     <span class="c1">#     Given counter multisets such as:</span>
     <span class="c1">#         cp = Counter(a=1, b=0, c=1)</span>
     <span class="c1">#         cq = Counter(c=1, d=0, e=1)</span>
     <span class="c1">#     The corresponding regular sets would be:</span>
     <span class="c1">#         sp = {&#39;a&#39;, &#39;c&#39;}</span>
     <span class="c1">#         sq = {&#39;c&#39;, &#39;e&#39;}</span>
     <span class="c1">#     All of the following relations would hold:</span>
     <span class="c1">#         set(cp + cq) == sp | sq</span>
     <span class="c1">#         set(cp - cq) == sp - sq</span>
     <span class="c1">#         set(cp | cq) == sp | sq</span>
     <span class="c1">#         set(cp &amp; cq) == sp &amp; sq</span>
     <span class="c1">#         (cp == cq) == (sp == sq)</span>
     <span class="c1">#         (cp != cq) == (sp != sq)</span>
     <span class="c1">#         (cp &lt;= cq) == (sp &lt;= sq)</span>
     <span class="c1">#         (cp &lt; cq) == (sp &lt; sq)</span>
     <span class="c1">#         (cp &gt;= cq) == (sp &gt;= sq)</span>
     <span class="c1">#         (cp &gt; cq) == (sp &gt; sq)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="s1">&#39;True if all counts agree. Missing counts are treated as zero.&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="k">return</span> <span class="nb">all</span><span class="p">(</span><span class="bp">self</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="o">==</span> <span class="n">other</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span> <span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="n">c</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ne__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="s1">&#39;True if any counts disagree. Missing counts are treated as zero.&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="k">return</span> <span class="ow">not</span> <span class="bp">self</span> <span class="o">==</span> <span class="n">other</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__le__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="s1">&#39;True if all counts in self are a subset of those in other.&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="k">return</span> <span class="nb">all</span><span class="p">(</span><span class="bp">self</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="o">&lt;=</span> <span class="n">other</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span> <span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="n">c</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__lt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="s1">&#39;True if all counts in self are a proper subset of those in other.&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="k">return</span> <span class="bp">self</span> <span class="o">&lt;=</span> <span class="n">other</span> <span class="ow">and</span> <span class="bp">self</span> <span class="o">!=</span> <span class="n">other</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ge__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="s1">&#39;True if all counts in self are a superset of those in other.&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="k">return</span> <span class="nb">all</span><span class="p">(</span><span class="bp">self</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="o">&gt;=</span> <span class="n">other</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">)</span> <span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="n">c</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__gt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="s1">&#39;True if all counts in self are a proper superset of those in other.&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="k">return</span> <span class="bp">self</span> <span class="o">&gt;=</span> <span class="n">other</span> <span class="ow">and</span> <span class="bp">self</span> <span class="o">!=</span> <span class="n">other</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__add__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Add counts from two counters.</span>

 <span class="sd">        &gt;&gt;&gt; Counter(&#39;abbb&#39;) + Counter(&#39;bcc&#39;)</span>
 <span class="sd">        Counter({&#39;b&#39;: 4, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="n">newcount</span> <span class="o">=</span> <span class="n">count</span> <span class="o">+</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
             <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="k">if</span> <span class="n">elem</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span> <span class="ow">and</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__sub__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39; Subtract count, but keep only results with positive counts.</span>

 <span class="sd">        &gt;&gt;&gt; Counter(&#39;abbbc&#39;) - Counter(&#39;bccd&#39;)</span>
 <span class="sd">        Counter({&#39;b&#39;: 2, &#39;a&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="n">newcount</span> <span class="o">=</span> <span class="n">count</span> <span class="o">-</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
             <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="k">if</span> <span class="n">elem</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span> <span class="ow">and</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span> <span class="o">-</span> <span class="n">count</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__or__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Union is the maximum of value in either of the input counters.</span>

 <span class="sd">        &gt;&gt;&gt; Counter(&#39;abbb&#39;) | Counter(&#39;bcc&#39;)</span>
 <span class="sd">        Counter({&#39;b&#39;: 3, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="n">other_count</span> <span class="o">=</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
             <span class="n">newcount</span> <span class="o">=</span> <span class="n">other_count</span> <span class="k">if</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="n">other_count</span> <span class="k">else</span> <span class="n">count</span>
             <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="k">if</span> <span class="n">elem</span> <span class="ow">not</span> <span class="ow">in</span> <span class="bp">self</span> <span class="ow">and</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__and__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39; Intersection is the minimum of corresponding counts.</span>

 <span class="sd">        &gt;&gt;&gt; Counter(&#39;abbb&#39;) &amp; Counter(&#39;bcc&#39;)</span>
 <span class="sd">        Counter({&#39;b&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">Counter</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="n">other_count</span> <span class="o">=</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
             <span class="n">newcount</span> <span class="o">=</span> <span class="n">count</span> <span class="k">if</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="n">other_count</span> <span class="k">else</span> <span class="n">other_count</span>
             <span class="k">if</span> <span class="n">newcount</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">newcount</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__pos__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Adds an empty counter, effectively stripping negative and zero counts&#39;</span>
         <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="k">if</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">count</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__neg__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Subtracts from an empty counter.  Strips positive and zero counts,</span>
 <span class="sd">        and flips the sign on negative counts.</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="n">result</span> <span class="o">=</span> <span class="n">Counter</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="k">if</span> <span class="n">count</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
                 <span class="n">result</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span> <span class="o">-</span> <span class="n">count</span>
         <span class="k">return</span> <span class="n">result</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">_keep_positive</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Internal method to strip elements with a negative or zero count&#39;&#39;&#39;</span>
         <span class="n">nonpositive</span> <span class="o">=</span> <span class="p">[</span><span class="n">elem</span> <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">()</span> <span class="k">if</span> <span class="ow">not</span> <span class="n">count</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">]</span>
         <span class="k">for</span> <span class="n">elem</span> <span class="ow">in</span> <span class="n">nonpositive</span><span class="p">:</span>
             <span class="k">del</span> <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__iadd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Inplace add from another counter, keeping only positive counts.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbb&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c += Counter(&#39;bcc&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c</span>
 <span class="sd">        Counter({&#39;b&#39;: 4, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">+=</span> <span class="n">count</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__isub__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Inplace subtract counter, but keep only results with positive counts.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbbc&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c -= Counter(&#39;bccd&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c</span>
 <span class="sd">        Counter({&#39;b&#39;: 2, &#39;a&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">-=</span> <span class="n">count</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ior__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Inplace union is the maximum of value from either counter.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbb&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c |= Counter(&#39;bcc&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c</span>
 <span class="sd">        Counter({&#39;b&#39;: 3, &#39;c&#39;: 2, &#39;a&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">other_count</span> <span class="ow">in</span> <span class="n">other</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="n">count</span> <span class="o">=</span> <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
             <span class="k">if</span> <span class="n">other_count</span> <span class="o">&gt;</span> <span class="n">count</span><span class="p">:</span>
                 <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">other_count</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__iand__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Inplace intersection is the minimum of corresponding counts.</span>

 <span class="sd">        &gt;&gt;&gt; c = Counter(&#39;abbb&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c &amp;= Counter(&#39;bcc&#39;)</span>
 <span class="sd">        &gt;&gt;&gt; c</span>
 <span class="sd">        Counter({&#39;b&#39;: 1})</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">for</span> <span class="n">elem</span><span class="p">,</span> <span class="n">count</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">items</span><span class="p">():</span>
             <span class="n">other_count</span> <span class="o">=</span> <span class="n">other</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span>
             <span class="k">if</span> <span class="n">other_count</span> <span class="o">&lt;</span> <span class="n">count</span><span class="p">:</span>
                 <span class="bp">self</span><span class="p">[</span><span class="n">elem</span><span class="p">]</span> <span class="o">=</span> <span class="n">other_count</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">_keep_positive</span><span class="p">()</span>


 <span class="c1">########################################################################</span>
 <span class="c1">###  ChainMap</span>
 <span class="c1">########################################################################</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">ChainMap</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="p">):</span>
 <span class="w">    </span><span class="sd">&#39;&#39;&#39; A ChainMap groups multiple dicts (or other mappings) together</span>
 <span class="sd">    to create a single, updateable view.</span>

 <span class="sd">    The underlying mappings are stored in a list.  That list is public and can</span>
 <span class="sd">    be accessed or updated using the *maps* attribute.  There is no other</span>
 <span class="sd">    state.</span>

 <span class="sd">    Lookups search the underlying mappings successively until a key is found.</span>
 <span class="sd">    In contrast, writes, updates, and deletions only operate on the first</span>
 <span class="sd">    mapping.</span>

 <span class="sd">    &#39;&#39;&#39;</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">maps</span><span class="p">):</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;Initialize a ChainMap by setting *maps* to the given mappings.</span>
 <span class="sd">        If no mappings are provided, a single empty dictionary is used.</span>

 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">maps</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">maps</span><span class="p">)</span> <span class="ow">or</span> <span class="p">[{}]</span>          <span class="c1"># always at least one map</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__missing__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="k">for</span> <span class="n">mapping</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">:</span>
             <span class="k">try</span><span class="p">:</span>
                 <span class="k">return</span> <span class="n">mapping</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>             <span class="c1"># can&#39;t use &#39;key in mapping&#39; with defaultdict</span>
             <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
                 <span class="k">pass</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="fm">__missing__</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>            <span class="c1"># support subclasses that define __missing__</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">get</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span> <span class="k">else</span> <span class="n">default</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="nb">set</span><span class="p">()</span><span class="o">.</span><span class="n">union</span><span class="p">(</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">))</span>     <span class="c1"># reuses stored hash values if possible</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="n">d</span> <span class="o">=</span> <span class="p">{}</span>
         <span class="k">for</span> <span class="n">mapping</span> <span class="ow">in</span> <span class="nb">map</span><span class="p">(</span><span class="nb">dict</span><span class="o">.</span><span class="n">fromkeys</span><span class="p">,</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)):</span>
             <span class="n">d</span> <span class="o">|=</span> <span class="n">mapping</span>                        <span class="c1"># reuses stored hash values if possible</span>
         <span class="k">return</span> <span class="nb">iter</span><span class="p">(</span><span class="n">d</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">any</span><span class="p">(</span><span class="n">key</span> <span class="ow">in</span> <span class="n">m</span> <span class="k">for</span> <span class="n">m</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__bool__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">any</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)</span>

     <span class="nd">@_recursive_repr</span><span class="p">()</span>
     <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="sa">f</span><span class="s1">&#39;</span><span class="si">{</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="vm">__name__</span><span class="si">}</span><span class="s1">(</span><span class="si">{</span><span class="s2">&quot;, &quot;</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="nb">repr</span><span class="p">,</span><span class="w"> </span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">))</span><span class="si">}</span><span class="s1">)&#39;</span>

     <span class="nd">@classmethod</span>
     <span class="k">def</span><span class="w"> </span><span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="n">value</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="o">/</span><span class="p">):</span>
         <span class="s1">&#39;Create a new ChainMap with keys from iterable and values set to value.&#39;</span>
         <span class="k">return</span> <span class="bp">cls</span><span class="p">(</span><span class="nb">dict</span><span class="o">.</span><span class="n">fromkeys</span><span class="p">(</span><span class="n">iterable</span><span class="p">,</span> <span class="n">value</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]&#39;</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">copy</span><span class="p">(),</span> <span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">1</span><span class="p">:])</span>

     <span class="n">__copy__</span> <span class="o">=</span> <span class="n">copy</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">new_child</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">m</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>      <span class="c1"># like Django&#39;s Context.push()</span>
 <span class="w">        </span><span class="sd">&#39;&#39;&#39;New ChainMap with a new map followed by all previous maps.</span>
 <span class="sd">        If no map is provided, an empty dict is used.</span>
 <span class="sd">        Keyword arguments update the map or new empty dict.</span>
 <span class="sd">        &#39;&#39;&#39;</span>
         <span class="k">if</span> <span class="n">m</span> <span class="ow">is</span> <span class="kc">None</span><span class="p">:</span>
             <span class="n">m</span> <span class="o">=</span> <span class="n">kwargs</span>
         <span class="k">elif</span> <span class="n">kwargs</span><span class="p">:</span>
             <span class="n">m</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">kwargs</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">m</span><span class="p">,</span> <span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">)</span>

     <span class="nd">@property</span>
     <span class="k">def</span><span class="w"> </span><span class="nf">parents</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>                          <span class="c1"># like Django&#39;s Context.pop()</span>
         <span class="s1">&#39;New ChainMap from maps[1:].&#39;</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="o">*</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">1</span><span class="p">:])</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">value</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="k">try</span><span class="p">:</span>
             <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="n">key</span><span class="p">]</span>
         <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Key not found in the first mapping: </span><span class="si">{</span><span class="n">key</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">popitem</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.&#39;</span>
         <span class="k">try</span><span class="p">:</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">popitem</span><span class="p">()</span>
         <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="s1">&#39;No keys found in the first mapping.&#39;</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
         <span class="s1">&#39;Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].&#39;</span>
         <span class="k">try</span><span class="p">:</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">key</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">)</span>
         <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
             <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="sa">f</span><span class="s1">&#39;Key not found in the first mapping: </span><span class="si">{</span><span class="n">key</span><span class="si">!r}</span><span class="s1">&#39;</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="s1">&#39;Clear maps[0], leaving maps[1:] intact.&#39;</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ior__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__or__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">Mapping</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">m</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
         <span class="n">m</span><span class="o">.</span><span class="n">maps</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">m</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ror__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="ow">not</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">_collections_abc</span><span class="o">.</span><span class="n">Mapping</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">NotImplemented</span>
         <span class="n">m</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
         <span class="k">for</span> <span class="n">child</span> <span class="ow">in</span> <span class="nb">reversed</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">maps</span><span class="p">):</span>
             <span class="n">m</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">child</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">m</span><span class="p">)</span>


 <span class="c1">################################################################################</span>
 <span class="c1">### UserDict</span>
 <span class="c1">################################################################################</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">UserDict</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableMapping</span><span class="p">):</span>

     <span class="c1"># Start by filling-out the abstract methods</span>
     <span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="nb">dict</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="p">{}</span>
         <span class="k">if</span> <span class="nb">dict</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="nb">dict</span><span class="p">)</span>
         <span class="k">if</span> <span class="n">kwargs</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="n">kwargs</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">:</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
         <span class="k">if</span> <span class="nb">hasattr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">,</span> <span class="s2">&quot;__missing__&quot;</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="fm">__missing__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">)</span>
         <span class="k">raise</span> <span class="ne">KeyError</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">item</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">iter</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="c1"># Modify __contains__ and get() to work like dict</span>
     <span class="c1"># does when __missing__ is present.</span>
     <span class="k">def</span><span class="w"> </span><span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
         <span class="k">return</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">get</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">default</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="k">if</span> <span class="n">key</span> <span class="ow">in</span> <span class="bp">self</span><span class="p">:</span>
             <span class="k">return</span> <span class="bp">self</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
         <span class="k">return</span> <span class="n">default</span>


     <span class="c1"># Now, add the methods in dicts but not in MutableMapping</span>
     <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__or__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserDict</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">|</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">dict</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">|</span> <span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">NotImplemented</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ror__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserDict</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">data</span> <span class="o">|</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">dict</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span> <span class="o">|</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">NotImplemented</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ior__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserDict</span><span class="p">):</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">|=</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span>
         <span class="k">else</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">|=</span> <span class="n">other</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__copy__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="n">inst</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="fm">__new__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">)</span>
         <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">)</span>
         <span class="c1"># Create a copy and avoid triggering descriptors</span>
         <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">]</span><span class="o">.</span><span class="n">copy</span><span class="p">()</span>
         <span class="k">return</span> <span class="n">inst</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">if</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span> <span class="ow">is</span> <span class="n">UserDict</span><span class="p">:</span>
             <span class="k">return</span> <span class="n">UserDict</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">copy</span><span class="p">())</span>
         <span class="kn">import</span><span class="w"> </span><span class="nn">copy</span>
         <span class="n">data</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>
         <span class="k">try</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="p">{}</span>
             <span class="n">c</span> <span class="o">=</span> <span class="n">copy</span><span class="o">.</span><span class="n">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
         <span class="k">finally</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="n">data</span>
         <span class="n">c</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
         <span class="k">return</span> <span class="n">c</span>

     <span class="nd">@classmethod</span>
     <span class="k">def</span><span class="w"> </span><span class="nf">fromkeys</span><span class="p">(</span><span class="bp">cls</span><span class="p">,</span> <span class="n">iterable</span><span class="p">,</span> <span class="n">value</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="n">d</span> <span class="o">=</span> <span class="bp">cls</span><span class="p">()</span>
         <span class="k">for</span> <span class="n">key</span> <span class="ow">in</span> <span class="n">iterable</span><span class="p">:</span>
             <span class="n">d</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="n">value</span>
         <span class="k">return</span> <span class="n">d</span>


 <span class="c1">################################################################################</span>
 <span class="c1">### UserList</span>
 <span class="c1">################################################################################</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">UserList</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">MutableSequence</span><span class="p">):</span>
 <span class="w">    </span><span class="sd">&quot;&quot;&quot;A more or less complete user-defined wrapper around list objects.&quot;&quot;&quot;</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">initlist</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="p">[]</span>
         <span class="k">if</span> <span class="n">initlist</span> <span class="ow">is</span> <span class="ow">not</span> <span class="kc">None</span><span class="p">:</span>
             <span class="c1"># XXX should this accept an arbitrary sequence?</span>
             <span class="k">if</span> <span class="nb">type</span><span class="p">(</span><span class="n">initlist</span><span class="p">)</span> <span class="o">==</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">):</span>
                 <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">initlist</span>
             <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">initlist</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
                 <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span> <span class="o">=</span> <span class="n">initlist</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span>
             <span class="k">else</span><span class="p">:</span>
                 <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">initlist</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__lt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__le__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__gt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ge__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;=</span> <span class="bp">self</span><span class="o">.</span><span class="n">__cast</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__cast</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">return</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span> <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">)</span> <span class="k">else</span> <span class="n">other</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
         <span class="k">return</span> <span class="n">item</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="nb">slice</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
         <span class="k">else</span><span class="p">:</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__setitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">item</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__delitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">):</span>
         <span class="k">del</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">]</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__add__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="nb">list</span><span class="p">(</span><span class="n">other</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__radd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="nb">list</span><span class="p">(</span><span class="n">other</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__iadd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+=</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span>
         <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)):</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+=</span> <span class="n">other</span>
         <span class="k">else</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+=</span> <span class="nb">list</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__mul__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">*</span> <span class="n">n</span><span class="p">)</span>

     <span class="fm">__rmul__</span> <span class="o">=</span> <span class="fm">__mul__</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__imul__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">*=</span> <span class="n">n</span>
         <span class="k">return</span> <span class="bp">self</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__copy__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="n">inst</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="o">.</span><span class="fm">__new__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">)</span>
         <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">)</span>
         <span class="c1"># Create a copy and avoid triggering descriptors</span>
         <span class="n">inst</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__dict__</span><span class="p">[</span><span class="s2">&quot;data&quot;</span><span class="p">][:]</span>
         <span class="k">return</span> <span class="n">inst</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">append</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">insert</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">insert</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">item</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">pop</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">i</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">pop</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">remove</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">remove</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">clear</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">clear</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">copy</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">count</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">count</span><span class="p">(</span><span class="n">item</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">index</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">item</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">index</span><span class="p">(</span><span class="n">item</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">reverse</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">reverse</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">sort</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
         <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">sort</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">extend</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserList</span><span class="p">):</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">other</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">else</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">extend</span><span class="p">(</span><span class="n">other</span><span class="p">)</span>


 <span class="c1">################################################################################</span>
 <span class="c1">### UserString</span>
 <span class="c1">################################################################################</span>

 <span class="k">class</span><span class="w"> </span><span class="nc">UserString</span><span class="p">(</span><span class="n">_collections_abc</span><span class="o">.</span><span class="n">Sequence</span><span class="p">):</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">seq</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">seq</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="n">seq</span>
         <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">seq</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="n">seq</span><span class="o">.</span><span class="n">data</span><span class="p">[:]</span>
         <span class="k">else</span><span class="p">:</span>
             <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">=</span> <span class="nb">str</span><span class="p">(</span><span class="n">seq</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">str</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__int__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">int</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__float__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">float</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__complex__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">complex</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__hash__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">hash</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">__getnewargs__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[:],)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__eq__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">==</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">==</span> <span class="n">string</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__lt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;</span> <span class="n">string</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__le__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;=</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&lt;=</span> <span class="n">string</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__gt__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;</span> <span class="n">string</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__ge__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">string</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">string</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;=</span> <span class="n">string</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">&gt;=</span> <span class="n">string</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__contains__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">char</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">char</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">char</span> <span class="o">=</span> <span class="n">char</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="n">char</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__len__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__getitem__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">index</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">[</span><span class="n">index</span><span class="p">])</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__add__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">elif</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="n">other</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">+</span> <span class="nb">str</span><span class="p">(</span><span class="n">other</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__radd__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">other</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">other</span><span class="p">,</span> <span class="nb">str</span><span class="p">):</span>
             <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="n">other</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="nb">str</span><span class="p">(</span><span class="n">other</span><span class="p">)</span> <span class="o">+</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__mul__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">n</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">*</span> <span class="n">n</span><span class="p">)</span>

     <span class="fm">__rmul__</span> <span class="o">=</span> <span class="fm">__mul__</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__mod__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">args</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span> <span class="o">%</span> <span class="n">args</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="fm">__rmod__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">template</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="nb">str</span><span class="p">(</span><span class="n">template</span><span class="p">)</span> <span class="o">%</span> <span class="bp">self</span><span class="p">)</span>

     <span class="c1"># the following methods are defined in alphabetical order:</span>
     <span class="k">def</span><span class="w"> </span><span class="nf">capitalize</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">capitalize</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">casefold</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">casefold</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">center</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">center</span><span class="p">(</span><span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">count</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">sub</span> <span class="o">=</span> <span class="n">sub</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">count</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">removeprefix</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">prefix</span><span class="p">,</span> <span class="o">/</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">prefix</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">prefix</span> <span class="o">=</span> <span class="n">prefix</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">removeprefix</span><span class="p">(</span><span class="n">prefix</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">removesuffix</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">suffix</span><span class="p">,</span> <span class="o">/</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">suffix</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">suffix</span> <span class="o">=</span> <span class="n">suffix</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">removesuffix</span><span class="p">(</span><span class="n">suffix</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">encode</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">encoding</span><span class="o">=</span><span class="s1">&#39;utf-8&#39;</span><span class="p">,</span> <span class="n">errors</span><span class="o">=</span><span class="s1">&#39;strict&#39;</span><span class="p">):</span>
         <span class="n">encoding</span> <span class="o">=</span> <span class="s1">&#39;utf-8&#39;</span> <span class="k">if</span> <span class="n">encoding</span> <span class="ow">is</span> <span class="kc">None</span> <span class="k">else</span> <span class="n">encoding</span>
         <span class="n">errors</span> <span class="o">=</span> <span class="s1">&#39;strict&#39;</span> <span class="k">if</span> <span class="n">errors</span> <span class="ow">is</span> <span class="kc">None</span> <span class="k">else</span> <span class="n">errors</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">encode</span><span class="p">(</span><span class="n">encoding</span><span class="p">,</span> <span class="n">errors</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">endswith</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">suffix</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">endswith</span><span class="p">(</span><span class="n">suffix</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">expandtabs</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">tabsize</span><span class="o">=</span><span class="mi">8</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">expandtabs</span><span class="p">(</span><span class="n">tabsize</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">find</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">sub</span> <span class="o">=</span> <span class="n">sub</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">find</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">format</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">/</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwds</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">format_map</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">mapping</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">format_map</span><span class="p">(</span><span class="n">mapping</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">index</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">index</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isalpha</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isalpha</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isalnum</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isalnum</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isascii</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isascii</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isdecimal</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isdecimal</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isdigit</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isdigit</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isidentifier</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isidentifier</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">islower</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">islower</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isnumeric</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isnumeric</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isprintable</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isprintable</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isspace</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isspace</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">istitle</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">istitle</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">isupper</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">isupper</span><span class="p">()</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">join</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">seq</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">seq</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">ljust</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">ljust</span><span class="p">(</span><span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">lower</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">lower</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">lstrip</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">chars</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">lstrip</span><span class="p">(</span><span class="n">chars</span><span class="p">))</span>

     <span class="n">maketrans</span> <span class="o">=</span> <span class="nb">str</span><span class="o">.</span><span class="n">maketrans</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">partition</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">partition</span><span class="p">(</span><span class="n">sep</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">replace</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">old</span><span class="p">,</span> <span class="n">new</span><span class="p">,</span> <span class="n">maxsplit</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">old</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">old</span> <span class="o">=</span> <span class="n">old</span><span class="o">.</span><span class="n">data</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">new</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">new</span> <span class="o">=</span> <span class="n">new</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="n">old</span><span class="p">,</span> <span class="n">new</span><span class="p">,</span> <span class="n">maxsplit</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">rfind</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
         <span class="k">if</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">UserString</span><span class="p">):</span>
             <span class="n">sub</span> <span class="o">=</span> <span class="n">sub</span><span class="o">.</span><span class="n">data</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rfind</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">rindex</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rindex</span><span class="p">(</span><span class="n">sub</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">rjust</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rjust</span><span class="p">(</span><span class="n">width</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">rpartition</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rpartition</span><span class="p">(</span><span class="n">sep</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">rstrip</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">chars</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rstrip</span><span class="p">(</span><span class="n">chars</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">split</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">maxsplit</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">split</span><span class="p">(</span><span class="n">sep</span><span class="p">,</span> <span class="n">maxsplit</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">rsplit</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">sep</span><span class="o">=</span><span class="kc">None</span><span class="p">,</span> <span class="n">maxsplit</span><span class="o">=-</span><span class="mi">1</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">rsplit</span><span class="p">(</span><span class="n">sep</span><span class="p">,</span> <span class="n">maxsplit</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">splitlines</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">keepends</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">splitlines</span><span class="p">(</span><span class="n">keepends</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">startswith</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">prefix</span><span class="p">,</span> <span class="n">start</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">end</span><span class="o">=</span><span class="n">_sys</span><span class="o">.</span><span class="n">maxsize</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">startswith</span><span class="p">(</span><span class="n">prefix</span><span class="p">,</span> <span class="n">start</span><span class="p">,</span> <span class="n">end</span><span class="p">)</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">strip</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">chars</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">strip</span><span class="p">(</span><span class="n">chars</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">swapcase</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">swapcase</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">title</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">title</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">translate</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">*</span><span class="n">args</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">translate</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">))</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">upper</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">upper</span><span class="p">())</span>

     <span class="k">def</span><span class="w"> </span><span class="nf">zfill</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">width</span><span class="p">):</span>
         <span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="vm">__class__</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">data</span><span class="o">.</span><span class="n">zfill</span><span class="p">(</span><span class="n">width</span><span class="p">))</span>
 </pre></div>

                 </article>


                 <footer class="prev-next-footer d-print-none">

 <div class="prev-next-area">
 </div>
                 </footer>

             </div>


           </div>
           <footer class="bd-footer-content">

           </footer>

       </main>
     </div>
   </div>

   <!-- Scripts loaded after <body> so the DOM is not blocked -->
   <script defer src="../_static/scripts/bootstrap.js?digest=8878045cc6db502f8baf"></script>
 <script defer src="../_static/scripts/pydata-sphinx-theme.js?digest=8878045cc6db502f8baf"></script>

   <footer class="bd-footer">
 <div class="bd-footer__inner bd-page-width">

     <div class="footer-items__start">

         <div class="footer-item">

   <p class="copyright">

       © Copyright 2016-2026 Apache Software Foundation.
 Apache Arrow, Arrow, Apache, the Apache logo, and the Apache Arrow project logo are either registered trademarks or trademarks of The Apache Software Foundation in the United States and other countries.
       <br/>

   </p>
 </div>

         <div class="footer-item">

   <p class="sphinx-version">
     Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 9.1.0.
     <br/>
   </p>
 </div>

     </div>


     <div class="footer-items__end">

         <div class="footer-item">
 <p class="theme-version">
   <!-- # L10n: Setting the PST URL as an argument as this does not need to be localized -->
   Built with the <a href="https://pydata-sphinx-theme.readthedocs.io/en/stable/index.html">PyData Sphinx Theme</a> 0.16.1.
 </p></div>

     </div>

 </div>

   </footer>
   </body>
 </html>