Repository: idaholab/MontePy

Issue:
Remove O(N^2) operation from NumberedObjectCollection
**Is your feature request related to a problem? Please describe.**

I was analyzing some data from parsing times and found that we have O(N^2) scaling despite fixing #510. After some investigation I found the culprit is in `NumberedObjectCollections.append`. This runs through all of `self.numbers` every time which is a generator over the entire list.... O(N^2).

So this should be eliminated.

**Describe the solution you'd like**

A few solutions.

1. Remove this operation from `read_input` and do a bulk add that is optimized
2. Make `NumberedObjectCollection` a lot more like dicts, and rely on `__num_cache` a lot more. Through the number property we guarantee that numbers are always update for objects tied to problem. So maybe we use this O(n^2) operation only as a last resot.




Discussion:

Patch:
diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
index c636a23f..630f96d9 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -49,7 +49,8 @@ jobs:
 
   test:
     runs-on: ubuntu-latest
-    permissions: write-all
+    permissions: 
+      actions: write
     strategy:
       matrix:
         python-version: ["3.9", "3.10", "3.11", "3.12", "3.13"]
@@ -91,6 +92,7 @@ jobs:
         uses: coverallsapp/github-action@v2
         with:
           file: coverage.xml
+          github-token: ${{ secrets.github_token }}
 
 
   doc-test:
diff --git a/doc/source/changelog.rst b/doc/source/changelog.rst
index f15a4d77..2125a2e1 100644
--- a/doc/source/changelog.rst
+++ b/doc/source/changelog.rst
@@ -15,6 +15,7 @@ MontePy Changelog
 **Performance Improvement**
 
 * Fixed cyclic memory reference that lead to memory leak in ``copy.deepcopy`` (:issue:`514`).
+* Fixed O(N<sup>2</sup>) operation in how append works for object collections like Cells (:issue:`556`).
 
 **Bug Fixes**
 
@@ -23,8 +24,11 @@ MontePy Changelog
 * Fixed bug with having a shortcut in a cell fill (:issue:`552`).
 * Fixed bug where file streams couldn't actually be read (:pull:`553`).
 
+**Support**
+
+* Added support for Python 3.13, and removed support for Python 3.8, and officially added support NumPy 1 & 2 (:pull:`548`).
+
 0.4 releases
-============
 
 0.4.1
 --------------
diff --git a/montepy/cell.py b/montepy/cell.py
index 2ff512fb..e5901b01 100644
--- a/montepy/cell.py
+++ b/montepy/cell.py
@@ -20,13 +20,6 @@ from montepy.universe import Universe
 from montepy.utilities import *
 
 
-def _number_validator(self, number):
-    if number <= 0:
-        raise ValueError("number must be > 0")
-    if self._problem:
-        self._problem.cells.check_number(number)
-
-
 def _link_geometry_to_cell(self, geom):
     geom._cell = self
     geom._add_new_children_to_cell(geom)
@@ -313,15 +306,6 @@ class Cell(Numbered_MCNP_Object):
         """
         pass
 
-    @make_prop_val_node("_number", int, validator=_number_validator)
-    def number(self):
-        """
-        The current cell number that will be written out to a new input.
-
-        :rtype: int
-        """
-        pass
-
     @make_prop_pointer("_material", (Material, type(None)), deletable=True)
     def material(self):
         """
diff --git a/montepy/data_inputs/material.py b/montepy/data_inputs/material.py
index b5cf3f98..b019ff36 100644
--- a/montepy/data_inputs/material.py
+++ b/montepy/data_inputs/material.py
@@ -15,13 +15,6 @@ import re
 import warnings
 
 
-def _number_validator(self, number):
-    if number <= 0:
-        raise ValueError("number must be > 0")
-    if self._problem:
-        self._problem.materials.check_number(number)
-
-
 class Material(data_input.DataInputAbstract, Numbered_MCNP_Object):
     """
     A class to represent an MCNP material.
@@ -90,15 +83,6 @@ class Material(data_input.DataInputAbstract, Numbered_MCNP_Object):
         """
         pass
 
-    @make_prop_val_node("_number", int, validator=_number_validator)
-    def number(self):
-        """
-        The number to use to identify the material by
-
-        :rtype: int
-        """
-        pass
-
     @property
     def is_atom_fraction(self):
         """
diff --git a/montepy/data_inputs/transform.py b/montepy/data_inputs/transform.py
index 4628f088..d4917642 100644
--- a/montepy/data_inputs/transform.py
+++ b/montepy/data_inputs/transform.py
@@ -9,11 +9,6 @@ import numpy as np
 import re
 
 
-def _enforce_number(self, val):
-    if val <= 0:
-        raise ValueError(f"Transform number must be > 0. {val} given.")
-
-
 class Transform(data_input.DataInputAbstract, Numbered_MCNP_Object):
     """
     Input to represent a transform input (TR).
@@ -109,16 +104,6 @@ class Transform(data_input.DataInputAbstract, Numbered_MCNP_Object):
         """
         pass
 
-    @make_prop_val_node("_number", (int, float), int, _enforce_number)
-    def number(self):
-        """
-        The transform number for this transform
-
-        :rtype: int
-
-        """
-        pass
-
     @make_prop_val_node("_old_number")
     def old_number(self):
         """
diff --git a/montepy/mcnp_problem.py b/montepy/mcnp_problem.py
index add3bde2..24585584 100644
--- a/montepy/mcnp_problem.py
+++ b/montepy/mcnp_problem.py
@@ -40,7 +40,7 @@ class MCNP_Problem:
         surface.Surface: Surfaces,
         Material: Materials,
         transform.Transform: Transforms,
-        montepy.universe: Universes,
+        montepy.universe.Universe: Universes,
     }
 
     def __init__(self, destination):
diff --git a/montepy/numbered_mcnp_object.py b/montepy/numbered_mcnp_object.py
index 9b1632fe..9d79ee6c 100644
--- a/montepy/numbered_mcnp_object.py
+++ b/montepy/numbered_mcnp_object.py
@@ -5,11 +5,33 @@ import itertools
 from montepy.errors import NumberConflictError
 from montepy.mcnp_object import MCNP_Object
 import montepy
+from montepy.utilities import *
+
+
+def _number_validator(self, number):
+    if number < 0:
+        raise ValueError("number must be >= 0")
+    if self._problem:
+        obj_map = montepy.MCNP_Problem._NUMBERED_OBJ_MAP
+        try:
+            collection_type = obj_map[type(self)]
+        except KeyError as e:
+            found = False
+            for obj_class in obj_map:
+                if isinstance(self, obj_class):
+                    collection_type = obj_map[obj_class]
+                    found = True
+                    break
+            if not found:
+                raise e
+        collection = getattr(self._problem, collection_type.__name__.lower())
+        collection.check_number(number)
+        collection._update_number(self.number, number, self)
 
 
 class Numbered_MCNP_Object(MCNP_Object):
-    @property
-    @abstractmethod
+
+    @make_prop_val_node("_number", int, validator=_number_validator)
     def number(self):
         """
         The current number of the object that will be written out to a new input.
diff --git a/montepy/numbered_object_collection.py b/montepy/numbered_object_collection.py
index 0896b678..abe74394 100644
--- a/montepy/numbered_object_collection.py
+++ b/montepy/numbered_object_collection.py
@@ -113,7 +113,6 @@ class NumberedObjectCollection(ABC):
 
         :rtype: generator
         """
-        self.__num_cache
         for obj in self._objects:
             # update cache every time we go through all objects
             self.__num_cache[obj.number] = obj
@@ -128,11 +127,36 @@ class NumberedObjectCollection(ABC):
         """
         if not isinstance(number, int):
             raise TypeError("The number must be an int")
-        if number in self.numbers:
+        conflict = False
+        # only can trust cache if being
+        if self._problem:
+            if number in self.__num_cache:
+                conflict = True
+        else:
+            if number in self.numbers:
+                conflict = True
+        if conflict:
             raise NumberConflictError(
                 f"Number {number} is already in use for the collection: {type(self)} by {self[number]}"
             )
 
+    def _update_number(self, old_num, new_num, obj):
+        """
+        Updates the number associated with a specific object in the internal cache.
+
+        :param old_num: the previous number the object had.
+        :type old_num: int
+        :param new_num: the number that is being set to.
+        :type new_num: int
+        :param obj: the object being updated.
+        :type obj: self._obj_class
+        """
+        # don't update numbers you don't own
+        if self.__num_cache.get(old_num, None) is not obj:
+            return
+        self.__num_cache.pop(old_num, None)
+        self.__num_cache[new_num] = obj
+
     @property
     def objects(self):
         """
@@ -177,22 +201,25 @@ class NumberedObjectCollection(ABC):
         """
         if not isinstance(other_list, (list, type(self))):
             raise TypeError("The extending list must be a list")
+        if self._problem:
+            nums = set(self.__num_cache)
+        else:
+            nums = set(self.numbers)
         for obj in other_list:
             if not isinstance(obj, self._obj_class):
                 raise TypeError(
                     "The object in the list {obj} is not of type: {self._obj_class}"
                 )
-            if obj.number in self.numbers:
+            if obj.number in nums:
                 raise NumberConflictError(
                     (
                         f"When adding to {type(self)} there was a number collision due to "
                         f"adding {obj} which conflicts with {self[obj.number]}"
                     )
                 )
-            # if this number is a ghost; remove it.
-            else:
-                self.__num_cache.pop(obj.number, None)
+            nums.add(obj.number)
         self._objects.extend(other_list)
+        self.__num_cache.update({obj.number: obj for obj in other_list})
         if self._problem:
             for obj in other_list:
                 obj.link_to_problem(self._problem)
@@ -295,15 +322,8 @@ class NumberedObjectCollection(ABC):
         """
         if not isinstance(obj, self._obj_class):
             raise TypeError(f"object being appended must be of type: {self._obj_class}")
-        if obj.number in self.numbers:
-            raise NumberConflictError(
-                (
-                    "There was a numbering conflict when attempting to add "
-                    f"{obj} to {type(self)}. Conflict was with {self[obj.number]}"
-                )
-            )
-        else:
-            self.__num_cache[obj.number] = obj
+        self.check_number(obj.number)
+        self.__num_cache[obj.number] = obj
         self._objects.append(obj)
         if self._problem:
             obj.link_to_problem(self._problem)
@@ -368,8 +388,12 @@ class NumberedObjectCollection(ABC):
         if step is None:
             step = self.step
         number = start_num
-        while number in self.numbers:
-            number += step
+        while True:
+            try:
+                self.check_number(number)
+                break
+            except NumberConflictError:
+                number += step
         return number
 
     def next_number(self, step=1):
@@ -450,29 +474,7 @@ class NumberedObjectCollection(ABC):
         return len(self._objects)
 
     def __iadd__(self, other):
-        if not isinstance(other, (type(self), list)):
-            raise TypeError(f"Appended item must be a list or of type {type(self)}")
-        for obj in other:
-            if not isinstance(obj, self._obj_class):
-                raise TypeError(
-                    f"Appended object {obj} must be of type: {self._obj_class}"
-                )
-        if isinstance(other, type(self)):
-            other_list = other.objects
-        else:
-            other_list = other
-        for obj in other_list:
-            if obj.number in self.numbers:
-                raise NumberConflictError(
-                    (
-                        "There was a numbering conflict when attempting to add "
-                        f"{obj} to {type(self)}. Conflict was with {self[obj.number]}"
-                    )
-                )
-            else:
-                self.__num_cache[obj.number] = obj
-        for obj in other_list:
-            self.append(obj)
+        self.extend(other)
         return self
 
     def __contains__(self, other):
diff --git a/montepy/surfaces/surface.py b/montepy/surfaces/surface.py
index 4fe55ffd..9612b750 100644
--- a/montepy/surfaces/surface.py
+++ b/montepy/surfaces/surface.py
@@ -11,11 +11,6 @@ from montepy.utilities import *
 import re
 
 
-def _enforce_numbers(self, value):
-    if value <= 0:
-        raise ValueError(f"The number be greater than 0; {value} given.")
-
-
 class Surface(Numbered_MCNP_Object):
     """
     Object to hold a single MCNP surface
@@ -194,15 +189,6 @@ class Surface(Numbered_MCNP_Object):
         """
         pass
 
-    @make_prop_val_node("_number", int, validator=_enforce_numbers)
-    def number(self):
-        """
-        The surface number to use.
-
-        :rtype: int
-        """
-        pass
-
     @property
     def cells(self):
         """
diff --git a/montepy/universe.py b/montepy/universe.py
index 0e699c09..68064303 100644
--- a/montepy/universe.py
+++ b/montepy/universe.py
@@ -21,7 +21,7 @@ class Universe(Numbered_MCNP_Object):
             raise TypeError("number must be int")
         if number < 0:
             raise ValueError(f"Universe number must be ≥ 0. {number} given.")
-        self._number = number
+        self._number = montepy.input_parser.syntax_node.ValueNode(number, int)
 
         class Parser:
             def parse(self, token_gen, input):
@@ -62,26 +62,6 @@ class Universe(Numbered_MCNP_Object):
         for cell in cells:
             cell.universe = self
 
-    @property
-    def number(self):
-        """
-        The number for this Universe.
-
-        Universe 0 is protected, and a Universe cannot be set 0,
-        if it is not already Universe 0.
-        """
-        return self._number
-
-    @number.setter
-    def number(self, number):
-        if not isinstance(number, int):
-            raise TypeError("number must be int")
-        if number <= 0:
-            raise ValueError("Universe number must be > 0")
-        if self._problem:
-            self._problem.universes.check_number(number)
-        self._number = number
-
     @property
     def old_number(self):
         """


Test patch:
diff --git a/tests/test_integration.py b/tests/test_integration.py
index d8087e13..c5fa2194 100644
--- a/tests/test_integration.py
+++ b/tests/test_integration.py
@@ -822,7 +822,7 @@ def test_universe_number_collision():
     with pytest.raises(montepy.errors.NumberConflictError):
         problem.universes[0].number = 350
 
-    with pytest.raises(ValueError):
+    with pytest.raises(montepy.errors.NumberConflictError):
         problem.universes[350].number = 0