.. _chapter_atombondtraversal:

********************************************************************************
Atom and Bond Traversal
********************************************************************************

**OEChem TK*** molecules contain atoms and bonds which have APIs described
by the :oe:cls:`OEAtomBase<OEChem::OEAtomBase>` and
:oe:cls:`OEBondBase<OEChem::OEBondBase>` abstract base-classes
respectively.  Atoms and bonds in **OEChem TK** can **only** be created and
destroyed in the context of an **OEChem TK** molecule.  While they can be
accessed as pointers through various member functions of molecules,
their memory is owned by the molecules and they are deallocated during
the molecules' destruction.  Attempting to use references to atoms or
bonds of a molecule after the molecule has gone out of scope results
in undefined behavior.

.. _section_atombondtraversal_iter:

Iterators
================================================================================

The standard way of processing each item or member of a set or
collection in **OEChem TK** is by the use of an iterator. The use of
iterators is a common abstraction (or design pattern) in object
oriented programming because it hides the way the collection/container
is implemented from the user. Hence a set of atoms could be
implemented internally as an array, a linked list, a hash table, or any
similar data structure, but its behavior to the programmer is
independent of the actual implementation. An iterator can be thought
of as a current position indicator.

.. oe:language:: c++

   **OEChem TK** iterators make use of C++'s template mechanism. The use of
   templates allows the functionality of an iterator to be specified
   (implemented) independently of the type of the collection being
   iterated over. An iterator over a type ``T``, has the type
   ``OEIter<T>``. Hence, an iterator over the atoms of a molecule
   (represented by :ref:`OEAtomBase <OEChem_OEAtomBase>`) has the type
   ``OEIter<OEAtomBase>`` and an iterator over the bonds of a molecule
   has type ``OEIter<OEBondBase>``.

   The three most common operations of an :ref:`OEIter <OESystem_OEIter>` are
   assignment, testing, and increment.  These three iterator methods
   allow **OEChem TK** iterators to resemble conventional ``for`` loops in high
   level programming languages.  Assignment specifies which
   collection/container the iterator is intended to loop over, testing
   determines whether the iterator has seen all of the items, and
   increment advances the iterator to the next position.

   One possible source of confusion is that most functions and methods
   that return an iterator actually return a result of type
   :oe:cls:`OEIterBase\<T><OESystem::OEIterBase>` rather than
   :oe:cls:`OEIter\<T><OESystem::OEIter>`. The template class
   :oe:cls:`OEIterBase\<T><OESystem::OEIterBase>` is an internal
   abstraction used by **OEChem TK**, and should be treated as an opaque type
   by the user.  Suffice it to say that values of type
   :oe:cls:`OEIterBase\<T><OESystem::OEIterBase>` can be assigned to
   variables of type :oe:cls:`OEIter\<T><OESystem::OEIter>` as created by
   the user.

   Another technical point is that **OEChem TK** iterators only support the
   prefix ``++`` operator, and not the suffix ``++`` operator.  This
   means that in order to advance the iterator, users must write ``++i``
   and not ``i++``.  This is actually a performance issue, since in C and
   C++ the operator ``i++`` must make a copy of its argument.  This is to
   support the syntax ``j = i++`` where ``j`` is assigned the value of
   ``i`` before the increment.  This copying may potentially be expensive
   and must be performed even if the value is not assigned.  For
   primitive types such as integers, most C/C++ compilers can determine
   the value is not used and optimize ``i++`` to ``++i``.  However, for
   C++ classes, most compilers are unable to perform this optimization,
   hence ``++i`` is the preferred idiom.  Even if **OEChem TK** changed the
   semantics of ``i++`` to perform the same thing as ``++i`` and return
   the value after the increment, the ``i++`` form is marginally less
   efficient (requiring an "invisible" integer argument to be passed to
   the operator).  Hence OpenEye's policy is to only implement the
   "correct" behavior and hope that users of **OEChem TK** will adopt ``++i``
   even for integer loops as good coding style.

   Finally, the template :ref:`OEIter <OESystem_OEIter>` is defined in the
   ``OESystem`` namespace rather than the ``OEChem`` namespace.  This is
   because iterators (like random number generators) are not chemistry
   specific, and the use of two namespaces makes this explicit.  It does
   however mean that ``using namespace OESystem;`` is required, as shown
   in our examples.

.. oe:language:: python
   
   **OEChem TK** makes extensive effort to support the Python iteration syntax. 
    
   .. code-block:: python

      for x in y:
          # do something with x

   The normal Python user does not have to care that an iterator
   is providing this convenient, yet powerful, abstraction. 

.. oe:language:: java

   **OEChem TK** makes extensive effort to support the Java iteration syntax. 
    
   .. code-block:: java

      for (MyType obj : list)
        obj.DoSomething();

.. oe:language:: csharp

   **OEChem TK** makes extensive effort to support the Java iteration syntax. 
    
   .. code-block:: csharp

      foreach (MyType obj in list)
        obj.DoSomething();
     

   So the normal C# user does not have to care that an iterator is
   providing this convenient, yet powerful, abstraction.
   
.. _section_atombondtraversal_molatombond:

Atom and Bond Iteration 
================================================================================

:oe:src:`Listing 1<SNIPPET-LoopingOverMolAtomsBonds>` shows the minimal use of
**OEChem TK**'s iterators.  These examples use the
:oe:cls:`OEMolBase<OEChem::OEMolBase>` methods
:oe:meth:`GetAtoms<OEChem::OEMolBase::GetAtoms>` and
:oe:meth:`GetBonds<OEChem::OEMolBase::GetBonds>`, which return
iterators over the atoms and bonds of a molecule, respectively.

.. oe:source:: LoopingOverMolAtomsBonds.cpp
   :language: c++
   :caption:  Using iterators to loop over atoms and bonds
   :refnum:   1
   :frag:     SNIPPET

.. oe:source:: LoopingOverMolAtomsBonds.py
   :language: python
   :caption:  Using iterators to loop over atoms and bonds
   :refnum:   1
   :frag:     SNIPPET

.. oe:source:: LoopingOverMolAtomsBonds.java
   :language: java
   :caption:  Using iterators to loop over atoms and bonds
   :refnum:   1
   :frag:     SNIPPET

.. oe:source:: LoopingOverMolAtomsBonds.cs
   :language: csharp
   :caption:  Using iterators to loop over atoms and bonds
   :refnum:   1
   :frag:     SNIPPET

.. oe:language:: c++

   One point to notice is that once again C++'s destructors mean that it is not
   necessary to explicitly deallocate or destroy the iterator after use.  
   Once the variable goes out of scope, it is cleaned up automatically.

.. note::

   :oe:src:`Listing 1<SNIPPET-LoopingOverMolAtomsBonds>` introduced the
   :oe:meth:`GetAtomicNum<OEChem::OEAtomBase::GetAtomicNum>` and
   :oe:meth:`GetOrder<OEChem::OEBondBase::GetOrder>` methods.  These and
   other :ref:`OEAtomBase <OEChem_OEAtomBase>` and :ref:`OEBondBase <OEChem_OEBondBase>`
   methods will be covered in more detail in chapters
   :ref:`chapter_atomproperties` and :ref:`chapter_bondproperties`,
   respectively.


.. _section_atombondtraversal_atombond:

Bonds of an Atom Iteration
================================================================================

The exact same idiom is used for iterating over the bonds attached to
an atom.  The :oe:meth:`GetBonds<OEChem::OEAtomBase::GetBonds>` method
returns an iterator over the bonds connected to that
atom. :oe:src:`Listing 2<SNIPPET-LoopingOverBonds>` shows how to use this
iterator to determine the explicit degree of an atom, *i.e.* the
number of bonds to it, not including bonds to implicit hydrogen atoms.

.. oe:source:: LoopingOverBonds.cpp
   :language: c++
   :caption:  Looping over the bonds of an atom
   :refnum:   2
   :frag:     SNIPPET

.. oe:source:: LoopingOverBonds.py
   :language: python
   :caption:  Looping over the bonds of an atom
   :refnum:   2
   :frag:     SNIPPET

.. oe:source:: LoopingOverBonds.java
   :language: java
   :caption:  Looping over the bonds of an atom
   :refnum:   2
   :frag:     SNIPPET

.. oe:source:: LoopingOverBonds.cs
   :language: csharp
   :caption:  Looping over the bonds of an atom
   :refnum:   2
   :frag:     SNIPPET

.. _section_atombondtraversal_nbr:

Atom Neighbor Iteration
================================================================================

Often it is not the bonds around the atoms that you wish to loop over,
but the neighboring atoms.  One way to do this would be to use the
:oe:meth:`GetBonds<OEChem::OEAtomBase::GetBonds>` method described in
the previous section and use the
:oe:meth:`GetNbr<OEChem::OEBondBase::GetNbr>` method on each
:oe:cls:`OEBondBase<OEChem::OEBondBase>` to get the atom across the
bond from the input atom.

.. oe:source:: LoopingOverNeighbors1.cpp
   :language: c++
   :caption:  Finding the neighbors of an atom (version 1)
   :refnum:   3
   :frag:     SNIPPET

.. oe:source:: LoopingOverNeighbors1.py
   :language: python
   :caption:  Finding the neighbors of an atom (version 1)
   :refnum:   3
   :frag:     SNIPPET

.. oe:source:: LoopingOverNeighbors1.java
   :language: java
   :caption:  Finding the neighbors of an atom (version 1)
   :refnum:   3
   :frag:     SNIPPET

.. oe:source:: LoopingOverNeighbors1.cs
   :language: csharp
   :caption:  Finding the neighbors of an atom (version 1)
   :refnum:   3
   :frag:     SNIPPET

However this can be done even more conveniently using the 
:oe:meth:`GetAtoms<OEChem::OEAtomBase::GetAtoms>` method of an 
:oe:cls:`OEAtomBase<OEChem::OEAtomBase>` directly, which allows 
loops over the neighbor atoms.

.. oe:source:: LoopingOverNeighbors2.cpp
   :language: c++
   :caption:  Finding the neighbors of an atom (version 2)
   :refnum:   4
   :frag:     SNIPPET

.. oe:source:: LoopingOverNeighbors2.py
   :language: python
   :caption:  Finding the neighbors of an atom (version 2)
   :refnum:   4
   :frag:     SNIPPET

.. oe:source:: LoopingOverNeighbors2.java
   :language: java
   :caption:  Finding the neighbors of an atom (version 2)
   :refnum:   4
   :frag:     SNIPPET

.. oe:source:: LoopingOverNeighbors2.cs
   :language: csharp
   :caption:  Finding the neighbors of an atom (version 2)
   :refnum:   4
   :frag:     SNIPPET

.. _section_atombondtraversal_subset:

Atom or Bond Subset Iteration
================================================================================

.. index:: predicate

It can sometimes be useful to loop over a subset of the atoms or bonds
of a molecule.  Traditionally, this is done with *if* statements
inside a loop, but it can sometimes be cleaner and more convenient to
subset the members being looped over inside the iterator itself.  To
do this, many of **OEChem TK**'s iterator generation functions (such as
:oe:meth:`GetAtoms<OEChem::OEMolBase::GetAtoms>`) can take an argument
which determines which subset of the object to loop over (these
functions are called *functors* are detailed in the chapter
:ref:`chapter_predicates`).  The details of these functions are not
important here.  Instead, a programmer can simply use the predefined
functors to control their loops.
:oe:src:`Listing 5<SNIPPET-LoopingOverCarbon>` shows the use of the predicate
:oe:cls:`OEHasAtomicNum<OEChem::OEHasAtomicNum>` to loop over only
carbon atoms in a molecule.

.. oe:source:: LoopingOverCarbon.cpp
   :language: c++
   :caption:  Looping over carbon atoms only
   :refnum:   5
   :frag:     SNIPPET

.. oe:source:: LoopingOverCarbon.py
   :language: python
   :caption:  Looping over carbon atoms only
   :refnum:   5
   :frag:     SNIPPET

.. oe:source:: LoopingOverCarbon.java
   :language: java
   :caption:  Looping over carbon atoms only
   :refnum:   5
   :frag:     SNIPPET

.. oe:source:: LoopingOverCarbon.cs
   :language: csharp
   :caption:  Looping over carbon atoms only
   :refnum:   5
   :frag:     SNIPPET

.. seealso::

   For a complete list of built-in predicates, see 
   :ref:`section_predicates_builtin` section.


Iterator Methods
================================================================================

.. oe:language:: c++

   The preceding examples show how to use an **OEChem TK** iterator to loop
   over objects. **OEChem TK** iterators provide four operators to allow
   the user to access the object at the current iterator position.

   The implicit cast :oe:meth:`operator A *<OESystem::OEIter::operator A *>`
   or :oe:meth:`operator-><OESystem::OEIter::operator->>` may be
   used to get a pointer to the current object. Also,
   :oe:meth:`operator*<OESystem::OEIter::operator*>` may be used to get
   a reference to the current object.

   For example, if variable ``iter`` has type ``OEIter<T>``, then
   ``(T*)iter`` is a pointer to the current object of type ``T *``,
   and ``*iter`` is a reference to the current object of type ``T&``.
   These operators mean that in most cases an **OEChem TK** iterator
   :oe:cls:`OEIter\<T><OESystem::OEIter>` behaves identically to a ``T *``.

   The following two examples demonstrate how iterators and pointers
   behave similarly. They are functionally equivalent. The only
   difference is that the second example assigns the iterator to an
   :oe:cls:`OEAtomBase<OEChem::OEAtomBase>` pointer before calling the
   :oe:meth:`GetAtomicNum<OEChem::OEAtomBase::GetAtomicNum>` method.
   
   .. list-table::
   
      * - .. oe:source:: ListingAtomicNumbers.cpp
             :language: c++
             :caption:  Dereferencing iterators   
             :frag:     SNIPPET

        - .. oe:source:: ListingAtomicNumbersPtr.cpp
             :language: c++
             :caption:  Assigning iterators to pointers 
             :frag:     SNIPPET

   The implicit cast of :oe:cls:`OEIter\<T><OESystem::OEIter>` to ``T*``
   is most useful when passing the object to a function which takes
   ``T`` by pointer.

   .. oe:source:: PassingIters.cpp
      :language: c++
      :caption:  Passing iterators to functions
      :frag:     SNIPPET


Iterators  offer a much wider range of iteration possibilities. For
example, the iterator can be reused by using the
:oe:meth:`ToFirst<OESystem::OEIter::ToFirst>` method. Or, the order of
iteration can be rearranged with the
:oe:meth:`Sort<OESystem::OEIter::Sort>` method.

.. oe:language:: c++ 

   The following table describes the full set of features offered by
   iterators.

   .. list-table::
      :header-rows: 1

      * - Description
        - C++ Code
      * - Increment
        - :oe:meth:`++i<OESystem::OEIter::operator++>`
      * - Increment by n
        - :oe:meth:`i += n<OESystem::OEIter::operator+=>`
      * - Decrement
        - :oe:meth:`--i<OESystem::OEIter::operator-->`
      * - Decrement by n
        - :oe:meth:`i -= n<OESystem::OEIter::operator-=>`
      * - Go to first
        - :oe:meth:`i.ToFirst()<OESystem::OEIter::ToFirst>`
      * - Go to last
        - :oe:meth:`i.ToLast()<OESystem::OEIter::ToLast>`
      * - Access current object
        - :oe:meth:`i->MethodName()<OESystem::OEIter::operator->>`
      * - Validity
        - :oe:meth:`if ((bool)i)<OESystem::OEIter::operator bool>`
      * - Sorting
        - :oe:meth:`i.Sort(predicate)<OESystem::OEIter::Sort>`

.. oe:language:: python java csharp

   The following table describes how to use the same rich set of
   iterator operations that C++ offers.

.. oe:language:: python

   ================= ================= =================
   Description       C++               Python           
   ================= ================= =================
   Increment         ``++i``           ``i.Next()``     
   Increment by n    ``i += n``        ``i.Next(n)``    
   Decrement         ``--i``           ``i.Prev()``     
   Decrement by n    ``i -= n``        ``i.Prev(n)``    
   Go to first       ``i.ToFirst()``   ``i.ToFirst()``  
   Go to last        ``i.ToLast()``    ``i.ToLast()``   
   Current Access    ``operator->``    ``i.Target()``   
   Validity          ``operator bool`` ``i.IsValid()``  
   ================= ================= =================


.. oe:language:: java

   ================== ================== ==================
   Description        C+ +               Java              
   ================== ================== ==================
   Increment          ``++i``            ``i.Increment()`` 
   Increment by n     ``i += n``         ``i.Increment(n)``
   Decrement          ``--i``            ``i.Decrement()`` 
   Decrement by n     ``i -= n``         ``i.Decrement(n)``
   Go to first        ``i.ToFirst()``    ``i.ToFirst()``   
   Go to last         ``i.ToLast()``     ``i.ToLast()``    
   Current Access     ``operator->``     ``i.Target()``    
   Validity           ``operator bool``  ``i.IsValid()``   
   ================== ================== ==================

.. oe:language:: csharp

   ================== ================== ==================
   Description        C+ +               C#
   ================== ================== ==================
   Increment          ``++i``            ``i.Increment()`` 
   Increment by n     ``i += n``         ``i.Increment(n)``
   Decrement          ``--i``            ``i.Decrement()`` 
   Decrement by n     ``i -= n``         ``i.Decrement(n)``
   Go to first        ``i.ToFirst()``    ``i.ToFirst()``   
   Go to last         ``i.ToLast()``     ``i.ToLast()``    
   Current Access     ``operator->``     ``i.Target()``    
   Validity           ``operator bool``  ``i.IsValid()``   
   ================== ================== ==================


:oe:src:`Listing 6<SNIPPET-ReverseIteration>` shows how to use an
:ref:`OEAtomBase <OEChem_OEAtomBase>` iterator to loop over the atoms in a
molecule in reverse order and print their atomic numbers.

.. note::

   The order of the atoms returned by
   :oe:meth:`OEChem::OEMolBase::GetAtoms` can be controlled by
   :oe:meth:`OEChem::OEMolBase::OrderAtoms`.

.. oe:source:: ReverseIteration.cpp
   :language: c++
   :caption:  Looping over atoms in reverse order
   :refnum:   6
   :frag:     SNIPPET

.. oe:source:: ReverseIteration.py
   :language: python
   :caption:  Looping over atoms in reverse order
   :refnum:   6
   :frag:     SNIPPET

.. oe:source:: ReverseIteration.java
   :language: java
   :caption:  Looping over atoms in reverse order
   :refnum:   6
   :frag:     SNIPPET

.. oe:source:: ReverseIteration.cs
   :language: csharp
   :caption:  Looping over atoms in reverse order
   :refnum:   6
   :frag:     SNIPPET
