#!/usr/bin/env python

# The contents of this file are subject to the BitTorrent Open Source License
# Version 1.1 (the License).  You may not copy or use this file, in either
# source code or executable form, except in compliance with the License.  You
# may obtain a copy of the License at http://www.bittorrent.com/license/.
#
# Software distributed under the License is distributed on an AS IS basis,
# WITHOUT WARRANTY OF ANY KIND, either express or implied.  See the License
# for the specific language governing rights and limitations under the
# License.
#
# By David Harrison

# I was playing with doctest when I wrote this.  I still haven't
# decided how useful doctest is as opposed to implementing unit tests
# directly.  --Dave

if __name__ == '__main__':
    import sys
    sys.path = ['.','..'] + sys.path  # HACK to simplify unit testing.

from BTL.translation import _

class BEGIN:    # represents special BEGIN location before first next.
    pass

from UserDict import DictMixin
from cmap_swig import *
import sys
from weakref import WeakKeyDictionary
LEAK_TEST = False

class CMap(object,DictMixin):  
    """In-order mapping. Provides same operations and behavior as a dict,
       but provides in-order iteration.  Additionally provides operations to
       find the nearest key <= or >= a given key.

       This provides a significantly wider set of operations than
       berkeley db BTrees, but it provides no means for persistence.

       LIMITATION: The key must be a python numeric type, e.g., an integer
       or a float.  The value can be any python object.

         Operation:       Time                 Applicable
                          Complexity:          Methods:
         ---------------------------------------------------
         Item insertion:  O(log n)             append, __setitem__
         Item deletion:   O(log n + k)         __delitem__, erase   
         Key search:      O(log n)             __getitem__, get, find, 
                                               __contains__
         Value search:    n/a
         Iteration step:  amortized O(1),      next, prev
                          worst-case O(log n)
         Memory:          O(n)

       n = number of elements in map.  k = number of iterators pointing
       into map.  CMap assumes there are few iterators in existence at 
       any given time. 
       
       Iterators are not invalidated by insertions.  Iterators are
       invalidated by deletions only when the key-value pair
       referenced is deleted.  Deletion has a '+k' because the
       __delitem__ searches linearly through the set of iterators
       pointing into this map to find any iterator pointing at the
       deleted item and then invalidates the iterator.

       This class is backed by the C++ STL map class, but conforms
       to the Python container interface."""

    class _AbstractIterator:
        """Iterates over elements in the map in order."""

        def __init__(self, m, si = BEGIN ): # "s.." implies swig object.
            """Creates an iterator pointing to element si in map m.
            
               Do not instantiate directly.  Use iterkeys, itervalues, or
               iteritems.

               The _AbstractIterator takes ownership of any C++ iterator
               (i.e., the swig object 'si') and will deallocate it when
               the iterator is deallocated.

               Examples of typical behavior:

               >>> from CMap import *
               >>> m = CMap()
               >>> m[12] = 6
               >>> m[9] = 4
               >>> for k in m:
               ...     print int(k)
               ...
               9
               12
               >>>

               Example edge cases (empty map):

               >>> from CMap import *
               >>> m = CMap()
               >>> try:
               ...     i = m.__iter__()
               ...     i.value()
               ... except IndexError:
               ...     print 'IndexError.'
               ...
               IndexError.
               >>> try:
               ...     i.next()
               ... except StopIteration:
               ...     print 'stopped'
               ...
               stopped

               @param map: CMap.
               @param node: Node that this iterator will point at.  If None
                 then the iterator points to end().  If BEGIN
                 then the iterator points to one before the beginning.
             """
            assert isinstance(m, CMap)
            assert not isinstance(si, CMap._AbstractIterator)
            if si == None:
                self._si = map_end(m._smap)
            else:
                self._si = si           # C++ iterator wrapped by swig.
            self._map = m
            m._iterators[self] = 1      # using map as set of weak references.

        def __hash__(self):
            return id(self)
        
        def __cmp__(self, other):
            if not self._si or not other._si:
                raise RuntimeError( _("invalid iterator") )
            if self._si == BEGIN and other._si == BEGIN: return 0
            if self._si == BEGIN and other._si != BEGIN: return -1
            elif self._si != BEGIN and other._si == BEGIN: return 1

            return iter_cmp(self._map._smap, self._si, other._si )

        def at_begin(self):
            """equivalent to self == m.begin() where m is a CMap.
            
                 >>> from CMap import CMap
                 >>> m = CMap()
                 >>> i = m.begin()
                 >>> i == m.begin()
                 True
                 >>> i.at_begin()
                 True
                 >>> i == m.end()   # no elements so begin()==end()
                 True
                 >>> 
i.at_end()
                 True
                 >>> m[6] = 'foo'   # insertion does not invalidate iterators.
                 >>> i = m.begin()
                 >>> i == m.end()
                 False
                 >>> i.value()
                 'foo'
                 >>> try:           # test at_begin when not at beginning.
                 ...    i.next()
                 ... except StopIteration:
                 ...    print 'ok'
                 ok
                 >>> i.at_begin()
                 False
                     
                 
            """
            if not self._si:
                raise RuntimeError( _("invalid iterator") )
            if self._si == BEGIN:  # BEGIN is one before begin().  Yuck!!
                return False
            return map_iter_at_begin(self._map._smap, self._si)
        
        def at_end(self):
            """equivalent to self == m.end() where m is a CMap, but
               at_end is faster because it avoids the dynamic memory
               alloation in m.end().

                 >>> from CMap import CMap
                 >>> m = CMap()
                 >>> m[6] = 'foo'
                 >>> i = m.end()   # test when at end.
                 >>> i == m.end()
                 True
                 >>> i.at_end()
                 True
                 >>> int(i.prev())
                 6
                 >>> i.at_end()    # testing when not at end.
                 False

               """
            if not self._si:
                raise RuntimeError( _("invalid iterator") )
            if self._si == BEGIN:
                return False
            return map_iter_at_end(self._map._smap, self._si)
        
        def key(self):
            """@return: the key of the key-value pair referenced by this
                   iterator.
            """
            if not self._si:
                raise RuntimeError( _("invalid iterator") )
            if self._si == BEGIN:
                raise IndexError(_("Cannot dereference iterator until after "
                                 "first call to .next."))
            elif map_iter_at_end(self._map._smap, self._si):
                raise IndexError()
            
            return iter_key(self._si)

        def value(self):
            """@return: the value of the key-value pair currently referenced
                   by this iterator.
            """
