15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2006 The RE2 Authors. All Rights Reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// license that can be found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DESCRIPTION 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SparseArray<T>(m) is a map from integers in [0, m) to T values. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// It requires (sizeof(T)+sizeof(int))*m memory, but it provides 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// fast iteration through the elements in the array and fast clearing 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// of the array. The array has a concept of certain elements being 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// uninitialized (having no value). 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Insertion and deletion are constant time operations. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Allocating the array is a constant time operation 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// when memory allocation is a constant time operation. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Clearing the array is a constant time operation (unusual!). 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Iterating through the array is an O(n) operation, where n 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// is the number of items in the array (not O(m)). 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The array iterator visits entries in the order they were first 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// inserted into the array. It is safe to add items to the array while 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// using an iterator: the iterator will visit indices added to the array 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// during the iteration, but will not re-visit indices whose values 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// change after visiting. Thus SparseArray can be a convenient 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// implementation of a work queue. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The SparseArray implementation is NOT thread-safe. It is up to the 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// caller to make sure only one thread is accessing the array. (Typically 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// these arrays are temporary values and used in situations where speed is 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// important.) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The SparseArray interface does not present all the usual STL bells and 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// whistles. 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Implemented with reference to Briggs & Torczon, An Efficient 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Representation for Sparse Sets, ACM Letters on Programming Languages 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and Systems, Volume 2, Issue 1-4 (March-Dec. 1993), pp. 59-69. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Briggs & Torczon popularized this technique, but it had been known 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// long before their paper. They point out that Aho, Hopcroft, and 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Ullman's 1974 Design and Analysis of Computer Algorithms and Bentley's 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 1986 Programming Pearls both hint at the technique in exercises to the 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// reader (in Aho & Hopcroft, exercise 2.12; in Bentley, column 1 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// exercise 8). 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Briggs & Torczon describe a sparse set implementation. I have 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// trivially generalized it to create a sparse array (actually the original 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// target of the AHU and Bentley exercises). 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// IMPLEMENTATION 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SparseArray uses a vector dense_ and an array sparse_to_dense_, both of 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// size max_size_. At any point, the number of elements in the sparse array is 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// size_. 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The vector dense_ contains the size_ elements in the sparse array (with 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// their indices), 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the order that the elements were first inserted. This array is dense: 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the size_ pairs are dense_[0] through dense_[size_-1]. 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The array sparse_to_dense_ maps from indices in [0,m) to indices in 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// [0,size_). 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For indices present in the array, dense_[sparse_to_dense_[i]].index_ == i. 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For indices not present in the array, sparse_to_dense_ can contain 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// any value at all, perhaps outside the range [0, size_) but perhaps not. 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The lax requirement on sparse_to_dense_ values makes clearing 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the array very easy: set size_ to 0. Lookups are slightly more 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// complicated. An index i has a value in the array if and only if: 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// sparse_to_dense_[i] is in [0, size_) AND 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// dense_[sparse_to_dense_[i]].index_ == i. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If both these properties hold, only then it is safe to refer to 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// dense_[sparse_to_dense_[i]].value_ 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// as the value associated with index i. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// To insert a new entry, set sparse_to_dense_[i] to size_, 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// initialize dense_[size_], and then increment size_. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Deletion of specific values from the array is implemented by 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// swapping dense_[size_-1] and the dense_ being deleted and then 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// updating the appropriate sparse_to_dense_ entries. 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// To make the sparse array as efficient as possible for non-primitive types, 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// elements may or may not be destroyed when they are deleted from the sparse 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// array through a call to erase(), erase_existing() or resize(). They 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// immediately become inaccessible, but they are only guaranteed to be 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// destroyed when the SparseArray destructor is called. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef RE2_UTIL_SPARSE_ARRAY_H__ 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define RE2_UTIL_SPARSE_ARRAY_H__ 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/util.h" 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SparseArray { 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SparseArray(); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SparseArray(int max_size); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~SparseArray(); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // IndexValue pairs: exposed in SparseArray::iterator. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class IndexValue; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef IndexValue value_type; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename vector<IndexValue>::iterator iterator; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename vector<IndexValue>::const_iterator const_iterator; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline const IndexValue& iv(int i) const; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the number of entries in the array. 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int size() const { 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return size_; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Iterate over the array. 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator begin() { 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_.begin(); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator end() { 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_.begin() + size_; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator begin() const { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_.begin(); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator end() const { 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_.begin() + size_; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Change the maximum size of the array. 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Invalidates all iterators. 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void resize(int max_size); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the maximum size of the array. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Indices can be in the range [0, max_size). 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_size() const { 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return max_size_; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Clear the array. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void clear() { 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_ = 0; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check whether index i is in the array. 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline bool has_index(int i) const; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Comparison function for sorting. 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Can sort the sparse array so that future iterations 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will visit indices in increasing order using 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // sort(arr.begin(), arr.end(), arr.less); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool less(const IndexValue& a, const IndexValue& b); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Set the value at index i to v. 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline iterator set(int i, Value v); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pair<iterator, bool> insert(const value_type& new_value); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the value at index i 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // or defaultv if index i is not initialized in the array. 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline Value get(int i, Value defaultv) const; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator find(int i); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const_iterator find(int i) const; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Change the value at index i to v. 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fast but unsafe: only use if has_index(i) is true. 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline iterator set_existing(int i, Value v); 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Set the value at the new index i to v. 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fast but unsafe: only use if has_index(i) is false. 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline iterator set_new(int i, Value v); 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the value at index i from the array.. 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fast but unsafe: only use if has_index(i) is true. 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline Value get_existing(int i) const; 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Erasing items from the array during iteration is in general 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // NOT safe. There is one special case, which is that the current 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // index-value pair can be erased as long as the iterator is then 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // checked for being at the end before being incremented. 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For example: 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for (i = m.begin(); i != m.end(); ++i) { 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if (ShouldErase(i->index(), i->value())) { 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // m.erase(i->index()); 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // --i; 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // } 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // } 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Except in the specific case just described, elements must 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // not be erased from the array (including clearing the array) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // while iterators are walking over the array. Otherwise, 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the iterators could walk past the end of the array. 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Erases the element at index i from the array. 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void erase(int i); 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Erases the element at index i from the array. 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fast but unsafe: only use if has_index(i) is true. 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void erase_existing(int i); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Add the index i to the array. 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Only use if has_index(i) is known to be false. 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Since it doesn't set the value associated with i, 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this function is private, only intended as a helper 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for other methods. 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void create_index(int i); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In debug mode, verify that some invariant properties of the class 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // are being maintained. This is called at the end of the constructor 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and at the beginning and end of all public non-const member functions. 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline void DebugCheckInvariants() const; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int size_; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_size_; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int* sparse_to_dense_; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<IndexValue> dense_; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool valgrind_; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_EVIL_CONSTRUCTORS(SparseArray); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SparseArray<Value>::SparseArray() 2345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : size_(0), max_size_(0), sparse_to_dense_(NULL), dense_(), 2355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) valgrind_(RunningOnValgrindOrMemorySanitizer()) {} 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// IndexValue pairs: exposed in SparseArray::iterator. 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class SparseArray<Value>::IndexValue { 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) friend class SparseArray; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef int first_type; 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef Value second_type; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndexValue() {} 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndexValue(int index, const Value& value) : second(value), index_(index) {} 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int index() const { return index_; } 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value value() const { return second; } 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Provide the data in the 'second' member so that the utilities 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // in map-util work. 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Value second; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int index_; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const typename SparseArray<Value>::IndexValue& 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SparseArray<Value>::iv(int i) const { 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(i, 0); 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(i, size_); 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_[i]; 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Change the maximum size of the array. 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Invalidates all iterators. 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SparseArray<Value>::resize(int new_max_size) { 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (new_max_size > max_size_) { 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int* a = new int[new_max_size]; 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (sparse_to_dense_) { 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memmove(a, sparse_to_dense_, max_size_*sizeof a[0]); 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Don't need to zero the memory but appease Valgrind. 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (valgrind_) { 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = max_size_; i < new_max_size; i++) 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) a[i] = 0xababababU; 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete[] sparse_to_dense_; 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sparse_to_dense_ = a; 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dense_.resize(new_max_size); 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size_ = new_max_size; 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (size_ > max_size_) 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_ = max_size_; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Check whether index i is in the array. 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SparseArray<Value>::has_index(int i) const { 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(i, 0); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(i, max_size_); 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (static_cast<uint>(i) >= max_size_) { 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Unsigned comparison avoids checking sparse_to_dense_[i] < 0. 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (uint)sparse_to_dense_[i] < (uint)size_ && 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dense_[sparse_to_dense_[i]].index_ == i; 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Set the value at index i to v. 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typename SparseArray<Value>::iterator SparseArray<Value>::set(int i, Value v) { 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (static_cast<uint>(i) >= max_size_) { 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Semantically, end() would be better here, but we already know 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the user did something stupid, so begin() insulates them from 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // dereferencing an invalid pointer. 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return begin(); 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!has_index(i)) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) create_index(i); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return set_existing(i, v); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)pair<typename SparseArray<Value>::iterator, bool> SparseArray<Value>::insert( 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const value_type& new_value) { 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pair<typename SparseArray<Value>::iterator, bool> p; 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (has_index(new_value.index_)) { 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = make_pair(dense_.begin() + sparse_to_dense_[new_value.index_], false); 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = make_pair(set_new(new_value.index_, new_value.second), true); 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Value SparseArray<Value>::get(int i, Value defaultv) const { 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!has_index(i)) 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return defaultv; 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return get_existing(i); 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typename SparseArray<Value>::iterator SparseArray<Value>::find(int i) { 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (has_index(i)) 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_.begin() + sparse_to_dense_[i]; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return end(); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typename SparseArray<Value>::const_iterator 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SparseArray<Value>::find(int i) const { 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (has_index(i)) { 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_.begin() + sparse_to_dense_[i]; 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return end(); 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typename SparseArray<Value>::iterator 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SparseArray<Value>::set_existing(int i, Value v) { 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(has_index(i)); 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dense_[sparse_to_dense_[i]].second = v; 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_.begin() + sparse_to_dense_[i]; 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typename SparseArray<Value>::iterator 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SparseArray<Value>::set_new(int i, Value v) { 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (static_cast<uint>(i) >= max_size_) { 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Semantically, end() would be better here, but we already know 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the user did something stupid, so begin() insulates them from 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // dereferencing an invalid pointer. 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return begin(); 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!has_index(i)); 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) create_index(i); 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return set_existing(i, v); 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Value SparseArray<Value>::get_existing(int i) const { 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(has_index(i)); 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return dense_[sparse_to_dense_[i]].second; 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SparseArray<Value>::erase(int i) { 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (has_index(i)) 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) erase_existing(i); 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SparseArray<Value>::erase_existing(int i) { 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(has_index(i)); 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int di = sparse_to_dense_[i]; 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (di < size_ - 1) { 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dense_[di] = dense_[size_ - 1]; 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sparse_to_dense_[dense_[di].index_] = di; 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_--; 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SparseArray<Value>::create_index(int i) { 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!has_index(i)); 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(size_, max_size_); 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sparse_to_dense_[i] = size_; 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dense_[size_].index_ = i; 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_++; 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> SparseArray<Value>::SparseArray(int max_size) { 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_size_ = max_size; 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sparse_to_dense_ = new int[max_size]; 4225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) valgrind_ = RunningOnValgrindOrMemorySanitizer(); 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dense_.resize(max_size); 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Don't need to zero the new memory, but appease Valgrind. 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (valgrind_) { 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < max_size; i++) { 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sparse_to_dense_[i] = 0xababababU; 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dense_[i].index_ = 0xababababU; 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_ = 0; 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> SparseArray<Value>::~SparseArray() { 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DebugCheckInvariants(); 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) delete[] sparse_to_dense_; 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> void SparseArray<Value>::DebugCheckInvariants() const { 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(0, size_); 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(size_, max_size_); 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(size_ == 0 || sparse_to_dense_ != NULL); 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Comparison function for sorting. 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Value> bool SparseArray<Value>::less(const IndexValue& a, 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const IndexValue& b) { 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return a.index_ < b.index_; 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace re2 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // RE2_UTIL_SPARSE_ARRAY_H__ 455