lemon-0.x: comparison src/work/deba/array_map

equal deleted inserted replaced

-:89a38e4d06ea
+:bcf19ace03ff
+// -*- c++ -*-
 #ifndef ARRAY_MAP_H
 #define ARRAY_MAP_H
 #include <memory>
+#include "extended_pair.h"
-#include <iostream>
-using namespace std;
 namespace hugo {
 template <typename MapRegistry> class ArrayMapFactory {
 typedef typename MapRegistry::Key Key;
 typedef typename MapRegistry::KeyIt KeyIt;
 typedef typename MapRegistry::MapBase MapBase;
-template <typename V, typename A = std::allocator<V> > class Map : public MapBase {
+template <typename V, typename A = std::allocator<V> >
+class Map : public MapBase {
 public:
 typedef V Value;
 typedef A Allocator;
 Map() : values(0), capacity(0) {}
 Map(const Graph& g, MapRegistry& r) : MapBase(g, r) {
-	int max_id = -1;
+	allocate_memory();
-	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
-	  int id = getGraph()->id(it);
-	  if (id > max_id) {
-	    max_id = id;
-	  }
-	}
-	if (max_id == -1) {
-	  capacity = 0;
-	  values = 0;
-	  return;
-	}
-	capacity = 1;
-	while (capacity <= max_id) {
-	  capacity <<= 1;
-	}
-	values = allocator.allocate(capacity);
 	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	  int id = getGraph()->id(it);
 	  allocator.construct(&(values[id]), Value());
 	}
 }
 Map(const Graph& g, MapRegistry& r, const Value& v) : MapBase(g, r) {
-	int max_id = -1;
+	allocate_memory();
-	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
-	  int id = getGraph()->id(it);
-	  if (id > max_id) {
-	    max_id = id;
-	  }
-	}
-	if (max_id == -1) {
-	  capacity = 0;
-	  values = 0;
-	  return;
-	}
-	capacity = 1;
-	while (capacity <= max_id) {
-	  capacity <<= 1;
-	}
-	values = allocator.allocate(capacity);
 	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	  int id = getGraph()->id(it);
 	  allocator.construct(&(values[id]), v);
 	}
 }
 	  int id = getGraph()->id(it);
 	  allocator.construct(&(values[id]), copy.values[id]);
 	}
 }
-template <typename CMap> Map(const CMap& copy) : MapBase(copy) {
+template <typename CMap> Map(const CMap& copy)
+	: capacity(0), values(0), MapBase(copy) {
 	if (getGraph()) {
-	  init();
+	  allocate_memory();
 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	    set(it, copy[it]);
 	  }
 	}
 }
 	if (getGraph()) {
 	  destroy();
 	}
 	this->MapBase::operator=(copy);
 	if (getGraph()) {
-	  init();
+	  allocate_memory();
 	  for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
 	    set(it, copy[it]);
 	  }
 	}
 }
 virtual ~Map() {
 	if (capacity != 0) {
 	  destroy();
 	  allocator.deallocate(values, capacity);
 void erase(const Key& key) {
 	int id = getGraph()->id(key);
 	allocator.destroy(&(values[id]));
 }
-/** Compatible iterator with the stl maps' iterators.
-*  It iterates on pairs of a key and a value.
-*/
 class iterator {
 	friend class Map;
 	friend class const_iterator;
-	private:
+private:
 	/** Private constructor to initalize the the iterators returned
 	 *  by the begin() and end().
 	 */
 	iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
-	public:
+public:
 	/** Default constructor.
 	 */
 	iterator() {}
+	typedef extended_pair<const Key&, const Key&,
+			      Value&, Value&> Reference;
 	/** Dereference operator for map.
 	 */
-	std::pair<const Key, Value> operator*() {
+	Reference operator*() {
-	  return std::pair<const Key, Value>(it, (*map)[it]);
+	  return Reference(it, (*map)[it]);
 	}
+	class Pointer {
+	  friend class iterator;
+	private:
+	  Reference data;
+	  Pointer(const Key& key, Value& val) : data(key, val) {}
+	public:
+	  Reference* operator->() {return &data;}
+	};
 	/** Arrow operator for map.
 	 */
-	std::pair<const Key, Value>* operator->() {
+	Pointer operator->() {
-	  static std::pair<const Key, Value> tmp = operator*();
+	  return Pointer(it, ((*map)[it]));
-	  return &tmp;
 	}
 	/** The pre increment operator of the map.
 	 */
 	iterator& operator++() {
 	/** The not-equality operator of the map.
 	 */
 	bool operator!=(const_iterator p_it) {
 	  return !(*this == p_it);
 	}
-	private:
+private:
 	Map* map;
 	KeyIt it;
 };
 /** Returns the begin iterator of the map.
 }
 class const_iterator {
 	friend class Map;
 	friend class iterator;
-	private:
+private:
 	/** Private constructor to initalize the the iterators returned
 	 *  by the begin() and end().
 	 */
-	const_iterator (Map& pmap, const KeyIt& pit) : map(&pmap), it(pit) {}
+	const_iterator (const Map& pmap, const KeyIt& pit)
+	  : map(&pmap), it(pit) {}
-	public:
+public:
 	/** Default constructor.
 	 */
 	const_iterator() {}
 	/** Constructor to convert iterator to const_iterator.
 	 */
-	const_iterator(iterator p_it) {
+	const_iterator(iterator p_it) : map(p_it.map), it(p_it.it) {}
-	  it = p_it.it;
-	}
+	typedef extended_pair<const Key&, const Key&,
+	  const Value&, const Value&> Reference;
 	/** Dereference operator for map.
 	 */
-	std::pair<const Key, const Value> operator*() const {
+	Reference operator*() {
-	  return std::pair<const Key, const Value>(it, (*map)[it]);
+	  return Reference(it, (*map)[it]);
 	}
+	class Pointer {
+	  friend class const_iterator;
+	private:
+	  Reference data;
+	  Pointer(const Key& key, const Value& val) : data(key, val) {}
+	public:
+	  Reference* operator->() {return &data;}
+	};
 	/** Arrow operator for map.
 	 */
-	std::pair<const Key, const Value>* operator->() const {
+	Pointer operator->() {
-	  static std::pair<const Key, const Value> tmp = operator*();
+	  return Pointer(it, ((*map)[it]));
-	  return &tmp;
 	}
 	/** The pre increment operator of the map.
 	 */
 	const_iterator& operator++() {
 	 */
 	bool operator!=(const_iterator p_it) {
 	  return !(*this == p_it);
 	}
-	private:
+private:
 	const Map* map;
 	KeyIt it;
 };
 /** Returns the begin const_iterator of the map.
 */
 const_iterator end() const {
 	return const_iterator(*this, INVALID);
 }
 private:
+void allocate_memory() {
+	int max_id = -1;
+	for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
+	  int id = getGraph()->id(it);
+	  if (id > max_id) {
+	    max_id = id;
+	  }
+	}
+	if (max_id == -1) {
+	  capacity = 0;
+	  values = 0;
+	  return;
+	}
+	capacity = 1;
+	while (capacity <= max_id) {
+	  capacity <<= 1;
+	}
+	values = allocator.allocate(capacity);
+}
 int capacity;
 Value* values;
 Allocator allocator;
 };
 };

changeset 755	a8c2e828ce0b
parent 702	4207f82a1778
child 921	818510fa3d99