operations_research Namespace Reference

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. More...

Classes
class	AdjustablePriorityQueue
class	Bitmap
struct	CallbackUtils_
class	ConstIter
class	MutableIter
	Note: this class is not compatible with sets (operator* returns a non-const reference). More...
class	ConstReverseIter
class	MutableReverseIter
class	Eraser
	This class performs an iterator-friendly erasure: the element pointed at gets removed from the container and the iterator remains valid and points to the next element. More...
class	Eraser< std::vector< T > >
	This version of the Eraser works for vectors. More...
class	Eraser< std::deque< T > >
	This version of the Eraser works for deques. More...
class	File
class	FileLineReader
	The FileLineReader class will read a text file specified by 'filename' line by line. More...
class	DateLogger
class	MathUtil
class	ACMRandom
	ACM minimal standard random number generator. (re-entrant.). More...
class	RecordWriter
	This class appends a protocol buffer to a file in a binary format. More...
class	RecordReader
	This class reads a protocol buffer from a file. More...
class	scoped_ptr
	A scoped_ptr<T> is like a T*, except that the destructor of scoped_ptr<T> automatically deletes the pointer it holds (if any). More...
class	scoped_array
	scoped_array<C> is like scoped_ptr<C>, except that the caller must allocate with new [] and the destructor deletes objects with delete []. More...
class	ScopedPtrMallocFree
	This class wraps the c library function free() in a class that can be passed as a template argument to scoped_ptr_malloc below. More...
class	scoped_ptr_malloc
	scoped_ptr_malloc<> is similar to scoped_ptr<>, but it accepts a second template argument, the functor used to free the object. More...
class	sparsetable
	This class implement a simple block based sparse vector. More...
class	StringPiece
class	WallTimer
class	CycleTimer
	This class of timer is very precise and potentially more expensive than the WallTimer class. More...
Functions
static void	mix (uint32 &a, uint32 &b, uint32 &c)
static void	mix (uint64 &a, uint64 &b, uint64 &c)
std::string	StrCat (const StringPiece &p1, const StringPiece &p2)
	StrCat.
std::string	StrCat (const StringPiece &p1, const StringPiece &p2, const StringPiece &p3)
std::string	StrCat (const StringPiece &p1, const StringPiece &p2, const StringPiece &p3, const StringPiece &p4)
std::string	StrCat (const StringPiece &p1, const StringPiece &p2, const StringPiece &p3, const StringPiece &p4, const StringPiece &p5)
std::string	StrCat (int64 a1, const StringPiece &p2)
std::string	StrCat (const StringPiece &p1, int64 a2)
template<class Collection>
const Collection::value_type::second_type &	FindWithDefault (const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
	Perform a lookup in a map or hash_map.
template<class Collection>
const Collection::value_type::second_type *	FindOrNull (const Collection &collection, const typename Collection::value_type::first_type &key)
	Perform a lookup in a map or hash_map.
template<class Collection>
Collection::value_type::second_type *	FindOrNull (Collection &collection, const typename Collection::value_type::first_type &key)
	Perform a lookup in a map or hash_map.
template<class Collection>
const Collection::value_type::second_type	FindPtrOrNull (const Collection &collection, const typename Collection::value_type::first_type &key)
	Perform a lookup in a map or hash_map whose values are pointers.
template<class Collection, class Key, class Value>
bool	InsertOrUpdate (Collection *const collection, const Key &key, const Value &value)
	Change the value associated with a particular key in a map or hash_map.
template<class Collection, class Key, class Value>
bool	InsertIfNotPresent (Collection *const collection, const Key &key, const Value &value)
	Insert a new key and value into a map or hash_map.
template<class Collection>
void	InsertOrDie (Collection *const collection, const typename Collection::value_type &value)
	Inserts a new pair<key,value> into a map or hash_map.
template<class Collection>
void	InsertOrDie (Collection *const collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &data)
	Inserts a new key/value into a map or hash_map.
template<class Collection, class Key, class Value>
bool	FindCopy (const Collection &collection, const Key &key, Value *const value)
	Perform a lookup in map or hash_map.
template<class Collection, class Key>
bool	ContainsKey (const Collection &collection, const Key &key)
	Test to see if a set, map, hash_set or hash_map contains a particular key.
template<class Collection>
const Collection::value_type::second_type &	FindOrDie (const Collection &collection, const typename Collection::value_type::first_type &key)
static uint32	Word32At (const char *ptr)
template<class C>
scoped_ptr< C >	make_scoped_ptr (C *param)
template<class C>
void	swap (scoped_ptr< C > &p1, scoped_ptr< C > &p2)
	Free functions.
template<class C>
bool	operator== (C *p1, const scoped_ptr< C > &p2)
template<class C>
bool	operator!= (C *p1, const scoped_ptr< C > &p2)
template<class C>
void	swap (scoped_array< C > &p1, scoped_array< C > &p2)
	Free functions.
template<class C>
bool	operator== (C *p1, const scoped_array< C > &p2)
template<class C>
bool	operator!= (C *p1, const scoped_array< C > &p2)
template<class C, class FP>
void	swap (scoped_ptr_malloc< C, FP > &a, scoped_ptr_malloc< C, FP > &b)
template<class C, class FP>
bool	operator== (C *p, const scoped_ptr_malloc< C, FP > &b)
template<class C, class FP>
bool	operator!= (C *p, const scoped_ptr_malloc< C, FP > &b)
template<typename ITR>
static void	SplitStringToIteratorUsing (const std::string &full, const char *delim, ITR &result)
	SplitStringUsing() Split a string using a character delimiter.
void	SplitStringUsing (const std::string &full, const char *delim, std::vector< std::string > *res)
	SplitStringUsing() Split a string using a character delimiter.
template<class ForwardIterator>
void	STLDeleteContainerPointers (ForwardIterator begin, ForwardIterator end)
	STLDeleteContainerPointers() For a range within a container of pointers, calls delete (non-array version) on these pointers.
template<class ForwardIterator>
void	STLDeleteContainerPairSecondPointers (ForwardIterator begin, ForwardIterator end)
	STLDeleteContainerPairSecondPointers() For a range within a container of pairs, calls delete (non-array version) on the SECOND item in the pairs.
void	STLStringResizeUninitialized (std::string *s, size_t new_size)
char *	string_as_array (std::string *str)
	Return a mutable char* pointing to a string's internal buffer, which may not be null-terminated.
template<class T>
void	STLDeleteElements (T *container)
	STLDeleteElements() deletes all the elements in an STL container and clears the container.
template<class T>
void	STLDeleteValues (T *v)
	Given an STL container consisting of (key, value) pairs, STLDeleteValues deletes all the "value" components and clears the container.
void	StringAppendV (std::string *const dst, const char *const format, va_list ap)
std::string	StringPrintf (const char *const format,...)
void	SStringPrintf (std::string *const dst, const char *const format,...)
void	StringAppendF (std::string *const dst, const char *const format,...)
int32	strto32 (const char *nptr, char **endptr, int base)
	Conversions to a 32-bit integer can pass the call to strto[u]l on 32-bit platforms, but need a little extra work on 64-bit platforms.
uint32	strtou32 (const char *nptr, char **endptr, int base)
int64	strto64 (const char *nptr, char **endptr, int base)
	For now, long long is 64-bit on all the platforms we care about, so these functions can simply pass the call to strto[u]ll.
uint64	strtou64 (const char *nptr, char **endptr, int base)
int32	atoi32 (const char *nptr)
	Although it returns an int, atoi() is implemented in terms of strtol, and so has differing overflow and underflow behavior.
int64	atoi64 (const char *nptr)
int32	atoi32 (const std::string &s)
	Convenience versions of the above that take a string argument.
int64	atoi64 (const std::string &s)
bool	HasSuffixString (const StringPiece &str, const StringPiece &suffix)
	HasSuffixString() Return true if str ends in suffix.
int64	GetProcessMemoryUsage ()
	GetProcessMemoryUsage.
static int64	TimevalToUsec (const timeval &tv)

---

Detailed Description

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. This file defines some IO interfaces to compatible with Google IO specifications.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Hash maps and hash sets are compiler dependant.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. This is an implementation designed to match the anticipated future TR2 implementation of the scoped_ptr class, and its closely-related brethren, scoped_array, scoped_ptr_malloc, and make_scoped_ptr.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. < _MSC_VER

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A string-like object that points to a sized piece of memory.

Functions or methods may use const StringPiece& parameters to accept either a "const char*" or a "string" value that will be implicitly converted to a StringPiece. The implicit conversion means that it is often appropriate to include this .h file in other files rather than forward-declaring StringPiece as would be appropriate for most other Google classes.

Systematic usage of StringPiece is encouraged as it will reduce unnecessary conversions from "const char*" to "string" and back again.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. For strtol* functions.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Mac OS X WINDOWS

---

Function Documentation

int32 operations_research::atoi32

(

const std::string &

s

)

[inline]

Convenience versions of the above that take a string argument.

Definition at line 61 of file strtoint.h.

int32 operations_research::atoi32

(

const char *

nptr

)

[inline]

Although it returns an int, atoi() is implemented in terms of strtol, and so has differing overflow and underflow behavior.

atol is the same.

Definition at line 52 of file strtoint.h.

int64 operations_research::atoi64

(

const std::string &

s

)

[inline]

Definition at line 65 of file strtoint.h.

int64 operations_research::atoi64

(

const char *

nptr

)

[inline]

Definition at line 56 of file strtoint.h.

template<class Collection, class Key>

bool operations_research::ContainsKey	(	const Collection &	collection,
		const Key &	key
	)			[inline]

Test to see if a set, map, hash_set or hash_map contains a particular key.

Returns true if the key is in the collection.

Definition at line 149 of file map-util.h.

template<class Collection, class Key, class Value>

bool operations_research::FindCopy	(	const Collection &	collection,
		const Key &	key,
		Value *const	value
	)			[inline]

Perform a lookup in map or hash_map.

If the key is present and value is non-NULL then a copy of the value associated with the key is made into *value. Returns whether key was present.

Definition at line 133 of file map-util.h.

template<class Collection>

const Collection::value_type::second_type& operations_research::FindOrDie	(	const Collection &	collection,
		const typename Collection::value_type::first_type &	key
	)			[inline]

Definition at line 156 of file map-util.h.

template<class Collection>

Collection::value_type::second_type* operations_research::FindOrNull	(	Collection &	collection,
		const typename Collection::value_type::first_type &	key
	)			[inline]

Perform a lookup in a map or hash_map.

Same as above but the returned pointer is not const and can be used to change the stored value.

Parameters:

collection

NOLINT

Definition at line 55 of file map-util.h.

template<class Collection>

const Collection::value_type::second_type* operations_research::FindOrNull	(	const Collection &	collection,
		const typename Collection::value_type::first_type &	key
	)			[inline]

Perform a lookup in a map or hash_map.

If the key is present a const pointer to the associated value is returned, otherwise a NULL pointer is returned.

Definition at line 41 of file map-util.h.

template<class Collection>

const Collection::value_type::second_type operations_research::FindPtrOrNull	(	const Collection &	collection,
		const typename Collection::value_type::first_type &	key
	)			[inline]

Perform a lookup in a map or hash_map whose values are pointers.

If the key is present a const pointer to the associated value is returned, otherwise a NULL pointer is returned. This function does not distinguish between a missing key and a key mapped to a NULL value.

Definition at line 71 of file map-util.h.

template<class Collection>

const Collection::value_type::second_type& operations_research::FindWithDefault	(	const Collection &	collection,
		const typename Collection::value_type::first_type &	key,
		const typename Collection::value_type::second_type &	value
	)			[inline]

Perform a lookup in a map or hash_map.

If the key is present in the map then the value associated with that key is returned, otherwise the value passed as a default is returned.

Definition at line 26 of file map-util.h.

int64 operations_research::GetProcessMemoryUsage

(

)

GetProcessMemoryUsage.

Returns the memory usage of the process.

Mac OS X LINUX WINDOWS < Unknown, returning 0.

Definition at line 75 of file sysinfo.cc.

bool operations_research::HasSuffixString	(	const StringPiece &	str,
		const StringPiece &	suffix
	)			[inline]

HasSuffixString() Return true if str ends in suffix.

Definition at line 26 of file strutil.h.

template<class Collection, class Key, class Value>

bool operations_research::InsertIfNotPresent	(	Collection *const	collection,
		const Key &	key,
		const Value &	value
	)			[inline]

Insert a new key and value into a map or hash_map.

If the key is not present in the map the key and value are inserted, otherwise nothing happens. True indicates that an insert took place, false indicates the key was already present.

Definition at line 102 of file map-util.h.

template<class Collection>

void operations_research::InsertOrDie	(	Collection *const	collection,
		const typename Collection::value_type::first_type &	key,
		const typename Collection::value_type::second_type &	data
	)			[inline]

Inserts a new key/value into a map or hash_map.

Dies if the key is already present.

Definition at line 121 of file map-util.h.

template<class Collection>

void operations_research::InsertOrDie	(	Collection *const	collection,
		const typename Collection::value_type &	value
	)			[inline]

Inserts a new pair<key,value> into a map or hash_map.

Insert a new key into a set or hash_set. Dies if the key is already present.

Definition at line 113 of file map-util.h.

template<class Collection, class Key, class Value>

bool operations_research::InsertOrUpdate	(	Collection *const	collection,
		const Key &	key,
		const Value &	value
	)			[inline]

Change the value associated with a particular key in a map or hash_map.

If the key is not present in the map the key and value are inserted, otherwise the value is updated to be a copy of the value provided. True indicates that an insert took place, false indicates an update.

Definition at line 85 of file map-util.h.

template<class C>

scoped_ptr< C > operations_research::make_scoped_ptr

(

C *

param

)

[inline]

Definition at line 145 of file scoped_ptr.h.

static void operations_research::mix	(	uint64 &	a,
		uint64 &	b,
		uint64 &	c
	)			[inline, static]

Definition at line 46 of file hash.h.

static void operations_research::mix	(	uint32 &	a,
		uint32 &	b,
		uint32 &	c
	)			[inline, static]

Definition at line 34 of file hash.h.

template<class C, class FP>

bool operations_research::operator!=	(	C *	p,
		const scoped_ptr_malloc< C, FP > &	b
	)			[inline]

Definition at line 376 of file scoped_ptr.h.

template<class C>

bool operations_research::operator!=	(	C *	p1,
		const scoped_array< C > &	p2
	)			[inline]

Definition at line 255 of file scoped_ptr.h.

template<class C>

bool operations_research::operator!=	(	C *	p1,
		const scoped_ptr< C > &	p2
	)			[inline]

Definition at line 140 of file scoped_ptr.h.

template<class C, class FP>

bool operations_research::operator==	(	C *	p,
		const scoped_ptr_malloc< C, FP > &	b
	)			[inline]

Definition at line 371 of file scoped_ptr.h.

template<class C>

bool operations_research::operator==	(	C *	p1,
		const scoped_array< C > &	p2
	)			[inline]

Definition at line 250 of file scoped_ptr.h.

template<class C>

bool operations_research::operator==	(	C *	p1,
		const scoped_ptr< C > &	p2
	)			[inline]

Definition at line 135 of file scoped_ptr.h.

template<typename ITR>

static void operations_research::SplitStringToIteratorUsing	(	const std::string &	full,
		const char *	delim,
		ITR &	result
	)			[inline, static]

SplitStringUsing() Split a string using a character delimiter.

Append the components to 'result'.

Note: For multi-character delimiters, this routine will split on *ANY* of the characters in the string, not the entire string as a single delimiter.

Definition at line 30 of file split.cc.

void operations_research::SplitStringUsing	(	const std::string &	full,
		const char *	delim,
		std::vector< std::string > *	res
	)

SplitStringUsing() Split a string using a character delimiter.

Append the components to 'result'. If there are consecutive delimiters, this function skips over all of them.

Definition at line 63 of file split.cc.

void operations_research::SStringPrintf	(	std::string *const	dst,
		const char *const	format,
			...
	)

Definition at line 87 of file stringprintf.cc.

template<class ForwardIterator>

void operations_research::STLDeleteContainerPairSecondPointers	(	ForwardIterator	begin,
		ForwardIterator	end
	)			[inline]

STLDeleteContainerPairSecondPointers() For a range within a container of pairs, calls delete (non-array version) on the SECOND item in the pairs.

NOTE: Like STLDeleteContainerPointers, deleting behind the iterator. Deleting the value does not always invalidate the iterator, but it may do so if the key is a pointer into the value object.

Definition at line 48 of file stl_util.h.

template<class ForwardIterator>

void operations_research::STLDeleteContainerPointers	(	ForwardIterator	begin,
		ForwardIterator	end
	)			[inline]

STLDeleteContainerPointers() For a range within a container of pointers, calls delete (non-array version) on these pointers.

NOTE: for these three functions, we could just implement a DeleteObject functor and then call for_each() on the range and functor, but this requires us to pull in all of algorithm.h, which seems expensive. For hash_[multi]set, it is important that this deletes behind the iterator because the hash_set may call the hash function on the iterator when it is advanced, which could result in the hash function trying to deference a stale pointer.

Definition at line 32 of file stl_util.h.

template<class T>

void operations_research::STLDeleteElements

(

T *

container

)

[inline]

STLDeleteElements() deletes all the elements in an STL container and clears the container.

This function is suitable for use with a vector, set, hash_set, or any other STL container which defines sensible begin(), end(), and clear() methods.

If container is NULL, this function is a no-op.

As an alternative to calling STLDeleteElements() directly, consider ElementDeleter (defined below), which ensures that your container's elements are deleted when the ElementDeleter goes out of scope.

Definition at line 88 of file stl_util.h.

template<class T>

void operations_research::STLDeleteValues

(

T *

v

)

[inline]

Given an STL container consisting of (key, value) pairs, STLDeleteValues deletes all the "value" components and clears the container.

Does nothing in the case it's given a NULL pointer.

Definition at line 99 of file stl_util.h.

void operations_research::STLStringResizeUninitialized	(	std::string *	s,
		size_t	new_size
	)			[inline]

Definition at line 57 of file stl_util.h.

std::string operations_research::StrCat	(	const StringPiece &	p1,
		int64	a2
	)

Definition at line 64 of file join.cc.

std::string operations_research::StrCat	(	int64	a1,
		const StringPiece &	p2
	)

Definition at line 60 of file join.cc.

std::string operations_research::StrCat	(	const StringPiece &	p1,
		const StringPiece &	p2,
		const StringPiece &	p3,
		const StringPiece &	p4,
		const StringPiece &	p5
	)

Definition at line 47 of file join.cc.

std::string operations_research::StrCat	(	const StringPiece &	p1,
		const StringPiece &	p2,
		const StringPiece &	p3,
		const StringPiece &	p4
	)

Definition at line 36 of file join.cc.

std::string operations_research::StrCat	(	const StringPiece &	p1,
		const StringPiece &	p2,
		const StringPiece &	p3
	)

Definition at line 27 of file join.cc.

std::string operations_research::StrCat	(	const StringPiece &	p1,
		const StringPiece &	p2
	)

StrCat.

Definition at line 21 of file join.cc.

char* operations_research::string_as_array

(

std::string *

str

)

[inline]

Return a mutable char* pointing to a string's internal buffer, which may not be null-terminated.

Writing through this pointer will modify the string.

string_as_array(&str)[i] is valid for 0 <= i < str.size() until the next call to a string method that invalidates iterators.

As of 2006-04, there is no standard-blessed way of getting a mutable reference to a string's internal buffer. However, issue 530 (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530) proposes this as the method. According to Matt Austern, this should already work on all current implementations.

Definition at line 73 of file stl_util.h.

void operations_research::StringAppendF	(	std::string *const	dst,
		const char *const	format,
			...
	)

Definition at line 95 of file stringprintf.cc.

void operations_research::StringAppendV	(	std::string *const	dst,
		const char *const	format,
		va_list	ap
	)

Definition at line 23 of file stringprintf.cc.

std::string operations_research::StringPrintf	(	const char *const	format,
			...
	)

Definition at line 78 of file stringprintf.cc.

int32 operations_research::strto32	(	const char *	nptr,
		char **	endptr,
		int	base
	)			[inline]

Conversions to a 32-bit integer can pass the call to strto[u]l on 32-bit platforms, but need a little extra work on 64-bit platforms.

Definition at line 24 of file strtoint.h.

int64 operations_research::strto64	(	const char *	nptr,
		char **	endptr,
		int	base
	)			[inline]

For now, long long is 64-bit on all the platforms we care about, so these functions can simply pass the call to strto[u]ll.

Definition at line 34 of file strtoint.h.

uint32 operations_research::strtou32	(	const char *	nptr,
		char **	endptr,
		int	base
	)			[inline]

Definition at line 28 of file strtoint.h.

uint64 operations_research::strtou64	(	const char *	nptr,
		char **	endptr,
		int	base
	)			[inline]

Definition at line 42 of file strtoint.h.

template<class C, class FP>

void operations_research::swap	(	scoped_ptr_malloc< C, FP > &	a,
		scoped_ptr_malloc< C, FP > &	b
	)			[inline]

Definition at line 366 of file scoped_ptr.h.

template<class C>

void operations_research::swap	(	scoped_array< C > &	p1,
		scoped_array< C > &	p2
	)			[inline]

Free functions.

Definition at line 245 of file scoped_ptr.h.

template<class C>

void operations_research::swap	(	scoped_ptr< C > &	p1,
		scoped_ptr< C > &	p2
	)			[inline]

Free functions.

Definition at line 130 of file scoped_ptr.h.

static int64 operations_research::@43::TimevalToUsec

(

const timeval &

tv

)

[inline, static]

Definition at line 33 of file timer.cc.

static uint32 operations_research::@26::Word32At

(

const char *

ptr

)

[inline, static]

Definition at line 64 of file random.cc.