lemon: comparison lemon/bits/array

equal deleted inserted replaced

-:b90a191eb6d8
+:e0be5f078348
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
-* This file is a part of LEMON, a generic C++ optimization library
+* This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 ///
 /// \brief Graph map based on the array storage.
 ///
 /// The ArrayMap template class is graph map structure what
 /// automatically updates the map when a key is added to or erased from
 /// the map. This map uses the allocators to implement
 /// the container functionality.
 ///
 /// The template parameters are the Graph the current Item type and
 /// the Value type of the map.
 template <typename _Graph, typename _Item, typename _Value>
 class ArrayMap
 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
 public:
 /// The graph type of the maps.
 typedef _Graph Graph;
 /// The item type of the map.
 typedef _Item Item;
 /// The reference map tag.
 typedef True ReferenceMapTag;
 /// The notifier type.
 typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 /// The MapBase of the Map which imlements the core regisitry function.
 typedef typename Notifier::ObserverBase Parent;
 private:
 typedef std::allocator<Value> Allocator;
 public:
 Parent::attach(graph.notifier(Item()));
 allocate_memory();
 Notifier* nf = Parent::notifier();
 Item it;
 for (nf->first(it); it != INVALID; nf->next(it)) {
-	int id = nf->id(it);;
+int id = nf->id(it);;
-	allocator.construct(&(values[id]), Value());
+allocator.construct(&(values[id]), Value());
 }
 }
 /// \brief Constructor to use default value to initialize the map.
 ///
 /// It constructs a map and initialize all of the the map.
 ArrayMap(const Graph& graph, const Value& value) {
 Parent::attach(graph.notifier(Item()));
 allocate_memory();
 Notifier* nf = Parent::notifier();
 Item it;
 for (nf->first(it); it != INVALID; nf->next(it)) {
-	int id = nf->id(it);;
+int id = nf->id(it);;
-	allocator.construct(&(values[id]), value);
+allocator.construct(&(values[id]), value);
 }
 }
 /// \brief Constructor to copy a map of the same map type.
 ///
 /// Constructor to copy a map of the same map type.
 ArrayMap(const ArrayMap& copy) : Parent() {
 if (copy.attached()) {
-	attach(*copy.notifier());
+attach(*copy.notifier());
 }
 capacity = copy.capacity;
 if (capacity == 0) return;
 values = allocator.allocate(capacity);
 Notifier* nf = Parent::notifier();
 Item it;
 for (nf->first(it); it != INVALID; nf->next(it)) {
-	int id = nf->id(it);;
+int id = nf->id(it);;
-	allocator.construct(&(values[id]), copy.values[id]);
+allocator.construct(&(values[id]), copy.values[id]);
 }
 }
 /// \brief Assign operator.
 ///
 /// This operator assigns for each item in the map the
 /// value mapped to the same item in the copied map.
 /// The parameter map should be indiced with the same
 /// itemset because this assign operator does not change
 /// the container of the map.
 ArrayMap& operator=(const ArrayMap& cmap) {
 return operator=<ArrayMap>(cmap);
 }
 /// \brief Template assign operator.
 ///
 /// The given parameter should be conform to the ReadMap
 /// concecpt and could be indiced by the current item set of
 /// the NodeMap. In this case the value for each item
 /// is assigned by the value of the given ReadMap.
 template <typename CMap>
 ArrayMap& operator=(const CMap& cmap) {
 checkConcept<concepts::ReadMap<Key, _Value>, CMap>();
 const typename Parent::Notifier* nf = Parent::notifier();
 Item it;
 }
 return *this;
 }
 /// \brief The destructor of the map.
 ///
 /// The destructor of the map.
 virtual ~ArrayMap() {
 if (attached()) {
-	clear();
+clear();
-	detach();
+detach();
 }
 }
 protected:
 using Parent::attach;
 using Parent::detach;
 using Parent::attached;
 public:
 /// \brief The subscript operator.
 ///
 /// The subscript operator. The map can be subscripted by the
 /// actual keys of the graph.
 Value& operator[](const Key& key) {
 int id = Parent::notifier()->id(key);
 return values[id];
 }
 /// \brief The const subscript operator.
 ///
 /// The const subscript operator. The map can be subscripted by the
 /// actual keys of the graph.
 const Value& operator[](const Key& key) const {
 int id = Parent::notifier()->id(key);
 return values[id];
 }
 /// \brief Setter function of the map.
 ///
 /// Setter function of the map. Equivalent with map[key] = val.
 /// This is a compatibility feature with the not dereferable maps.
 void set(const Key& key, const Value& val) {
 (*this)[key] = val;
 }
 protected:
 /// \brief Adds a new key to the map.
 ///
 /// It adds a new key to the map. It called by the observer notifier
 /// and it overrides the add() member function of the observer base.
 virtual void add(const Key& key) {
 Notifier* nf = Parent::notifier();
 int id = nf->id(key);
 if (id >= capacity) {
-	int new_capacity = (capacity == 0 ? 1 : capacity);
+int new_capacity = (capacity == 0 ? 1 : capacity);
-	while (new_capacity <= id) {
+while (new_capacity <= id) {
-	  new_capacity <<= 1;
+new_capacity <<= 1;
-	}
+}
-	Value* new_values = allocator.allocate(new_capacity);
+Value* new_values = allocator.allocate(new_capacity);
-	Item it;
+Item it;
-	for (nf->first(it); it != INVALID; nf->next(it)) {
+for (nf->first(it); it != INVALID; nf->next(it)) {
-	  int jd = nf->id(it);;
+int jd = nf->id(it);;
-	  if (id != jd) {
+if (id != jd) {
-	    allocator.construct(&(new_values[jd]), values[jd]);
+allocator.construct(&(new_values[jd]), values[jd]);
-	    allocator.destroy(&(values[jd]));
+allocator.destroy(&(values[jd]));
-	  }
+}
-	}
+}
-	if (capacity != 0) allocator.deallocate(values, capacity);
+if (capacity != 0) allocator.deallocate(values, capacity);
-	values = new_values;
+values = new_values;
-	capacity = new_capacity;
+capacity = new_capacity;
 }
 allocator.construct(&(values[id]), Value());
 }
 /// \brief Adds more new keys to the map.
 ///
 /// It adds more new keys to the map. It called by the observer notifier
 /// and it overrides the add() member function of the observer base.
 virtual void add(const std::vector<Key>& keys) {
 Notifier* nf = Parent::notifier();
 int max_id = -1;
 for (int i = 0; i < int(keys.size()); ++i) {
-	int id = nf->id(keys[i]);
+int id = nf->id(keys[i]);
-	if (id > max_id) {
+if (id > max_id) {
-	  max_id = id;
+max_id = id;
-	}
+}
 }
 if (max_id >= capacity) {
-	int new_capacity = (capacity == 0 ? 1 : capacity);
+int new_capacity = (capacity == 0 ? 1 : capacity);
-	while (new_capacity <= max_id) {
+while (new_capacity <= max_id) {
-	  new_capacity <<= 1;
+new_capacity <<= 1;
-	}
+}
-	Value* new_values = allocator.allocate(new_capacity);
+Value* new_values = allocator.allocate(new_capacity);
-	Item it;
+Item it;
-	for (nf->first(it); it != INVALID; nf->next(it)) {
+for (nf->first(it); it != INVALID; nf->next(it)) {
-	  int id = nf->id(it);
+int id = nf->id(it);
-	  bool found = false;
+bool found = false;
-	  for (int i = 0; i < int(keys.size()); ++i) {
+for (int i = 0; i < int(keys.size()); ++i) {
-	    int jd = nf->id(keys[i]);
+int jd = nf->id(keys[i]);
-	    if (id == jd) {
+if (id == jd) {
-	      found = true;
+found = true;
-	      break;
+break;
-	    }
+}
-	  }
+}
-	  if (found) continue;
+if (found) continue;
-	  allocator.construct(&(new_values[id]), values[id]);
+allocator.construct(&(new_values[id]), values[id]);
-	  allocator.destroy(&(values[id]));
+allocator.destroy(&(values[id]));
-	}
+}
-	if (capacity != 0) allocator.deallocate(values, capacity);
+if (capacity != 0) allocator.deallocate(values, capacity);
-	values = new_values;
+values = new_values;
-	capacity = new_capacity;
+capacity = new_capacity;
 }
 for (int i = 0; i < int(keys.size()); ++i) {
-	int id = nf->id(keys[i]);
+int id = nf->id(keys[i]);
-	allocator.construct(&(values[id]), Value());
+allocator.construct(&(values[id]), Value());
 }
 }
 /// \brief Erase a key from the map.
 ///
 /// Erase a key from the map. It called by the observer notifier
 /// and it overrides the erase() member function of the observer base.
 virtual void erase(const Key& key) {
 int id = Parent::notifier()->id(key);
 allocator.destroy(&(values[id]));
 }
 /// \brief Erase more keys from the map.
 ///
 /// Erase more keys from the map. It called by the observer notifier
 /// and it overrides the erase() member function of the observer base.
 virtual void erase(const std::vector<Key>& keys) {
 for (int i = 0; i < int(keys.size()); ++i) {
-	int id = Parent::notifier()->id(keys[i]);
+int id = Parent::notifier()->id(keys[i]);
-	allocator.destroy(&(values[id]));
+allocator.destroy(&(values[id]));
 }
 }
 /// \brief Buildes the map.
 ///
 /// It buildes the map. It called by the observer notifier
 /// and it overrides the build() member function of the observer base.
 virtual void build() {
 Notifier* nf = Parent::notifier();
 allocate_memory();
 Item it;
 for (nf->first(it); it != INVALID; nf->next(it)) {
-	int id = nf->id(it);;
+int id = nf->id(it);;
-	allocator.construct(&(values[id]), Value());
+allocator.construct(&(values[id]), Value());
 }
 }
 /// \brief Clear the map.
 ///
 /// It erase all items from the map. It called by the observer notifier
 /// and it overrides the clear() member function of the observer base.
 virtual void clear() {
 Notifier* nf = Parent::notifier();
 if (capacity != 0) {
-	Item it;
+Item it;
-	for (nf->first(it); it != INVALID; nf->next(it)) {
+for (nf->first(it); it != INVALID; nf->next(it)) {
-	  int id = nf->id(it);
+int id = nf->id(it);
-	  allocator.destroy(&(values[id]));
+allocator.destroy(&(values[id]));
-	}
+}
-	allocator.deallocate(values, capacity);
+allocator.deallocate(values, capacity);
-	capacity = 0;
+capacity = 0;
 }
 }
 private:
 void allocate_memory() {
 int max_id = Parent::notifier()->maxId();
 if (max_id == -1) {
-	capacity = 0;
+capacity = 0;
-	values = 0;
+values = 0;
-	return;
+return;
 }
 capacity = 1;
 while (capacity <= max_id) {
-	capacity <<= 1;
+capacity <<= 1;
 }
 values = allocator.allocate(capacity);
 }
 int capacity;
 Value* values;
 Allocator allocator;
 };
 }
 #endif

changeset 209	765619b7cbb2
parent 107	31a2e6d28f61
child 263	be8a861d3bb7