Aluode/PerceptionLabPortable

1"""
2Uses C++ map containers for fast dict-like behavior with keys being
3integers, and values float.
4"""
5# Authors: The scikit-learn developers
6# SPDX-License-Identifier: BSD-3-Clause
7
8# C++
9from cython.operator cimport dereference as deref, preincrement as inc
10from libcpp.utility cimport pair
11from libcpp.map cimport map as cpp_map
12
13import numpy as np
14
15from ._typedefs cimport float64_t, intp_t
16
17
18###############################################################################
19# An object to be used in Python
20
21# Lookup is faster than dict (up to 10 times), and so is full traversal
22# (up to 50 times), and assignment (up to 6 times), but creation is
23# slower (up to 3 times). Also, a large benefit is that memory
24# consumption is reduced a lot compared to a Python dict
25
26cdef class IntFloatDict:
27
28    def __init__(
29        self,
30        intp_t[:] keys,
31        float64_t[:] values,
32    ):
33        cdef int i
34        cdef int size = values.size
35        # Should check that sizes for keys and values are equal, and
36        # after should boundcheck(False)
37        for i in range(size):
38            self.my_map[keys[i]] = values[i]
39
40    def __len__(self):
41        return self.my_map.size()
42
43    def __getitem__(self, int key):
44        cdef cpp_map[intp_t, float64_t].iterator it = self.my_map.find(key)
45        if it == self.my_map.end():
46            # The key is not in the dict
47            raise KeyError('%i' % key)
48        return deref(it).second
49
50    def __setitem__(self, int key, float value):
51        self.my_map[key] = value
52
53    # Cython 0.20 generates buggy code below. Commenting this out for now
54    # and relying on the to_arrays method
55    # def __iter__(self):
56    #     cdef cpp_map[intp_t, float64_t].iterator it = self.my_map.begin()
57    #     cdef cpp_map[intp_t, float64_t].iterator end = self.my_map.end()
58    #     while it != end:
59    #         yield deref(it).first, deref(it).second
60    #         inc(it)
61
62    def __iter__(self):
63        cdef int size = self.my_map.size()
64        cdef intp_t [:] keys = np.empty(size, dtype=np.intp)
65        cdef float64_t [:] values = np.empty(size, dtype=np.float64)
66        self._to_arrays(keys, values)
67        cdef int idx
68        cdef intp_t key
69        cdef float64_t value
70        for idx in range(size):
71            key = keys[idx]
72            value = values[idx]
73            yield key, value
74
75    def to_arrays(self):
76        """Return the key, value representation of the IntFloatDict
77           object.
78
79           Returns
80           =======
81           keys : ndarray, shape (n_items, ), dtype=int
82                The indices of the data points
83           values : ndarray, shape (n_items, ), dtype=float
84                The values of the data points
85        """
86        cdef int size = self.my_map.size()
87        keys = np.empty(size, dtype=np.intp)
88        values = np.empty(size, dtype=np.float64)
89        self._to_arrays(keys, values)
90        return keys, values
91
92    cdef _to_arrays(self, intp_t [:] keys, float64_t [:] values):
93        # Internal version of to_arrays that takes already-initialized arrays
94        cdef cpp_map[intp_t, float64_t].iterator it = self.my_map.begin()
95        cdef cpp_map[intp_t, float64_t].iterator end = self.my_map.end()
96        cdef int index = 0
97        while it != end:
98            keys[index] = deref(it).first
99            values[index] = deref(it).second
100            inc(it)
101            index += 1
102
103    def update(self, IntFloatDict other):
104        cdef cpp_map[intp_t, float64_t].iterator it = other.my_map.begin()
105        cdef cpp_map[intp_t, float64_t].iterator end = other.my_map.end()
106        while it != end:
107            self.my_map[deref(it).first] = deref(it).second
108            inc(it)
109
110    def copy(self):
111        cdef IntFloatDict out_obj = IntFloatDict.__new__(IntFloatDict)
112        # The '=' operator is a copy operator for C++ maps
113        out_obj.my_map = self.my_map
114        return out_obj
115
116    def append(self, intp_t key, float64_t value):
117        # Construct our arguments
118        cdef pair[intp_t, float64_t] args
119        args.first = key
120        args.second = value
121        self.my_map.insert(args)
122
123
124###############################################################################
125# operation on dict
126
127def argmin(IntFloatDict d):
128    cdef cpp_map[intp_t, float64_t].iterator it = d.my_map.begin()
129    cdef cpp_map[intp_t, float64_t].iterator end = d.my_map.end()
130    cdef intp_t min_key = -1
131    cdef float64_t min_value = np.inf
132    while it != end:
133        if deref(it).second < min_value:
134            min_value = deref(it).second
135            min_key = deref(it).first
136        inc(it)
137    return min_key, min_value
138