# HG changeset patch
# User klao
# Date 1082167068 0
# Node ID e4ab32225f1cfddbd2b0434368284987a1fec095
# Parent  538ff3ce9f68ac4d0fdd945c42ca3b73e256c78d
A generic map with value type [0, N) where N is a small integer.
Can enumerate keys with a given value.

diff -r 538ff3ce9f68 -r e4ab32225f1c src/work/klao/Makefile
--- a/src/work/klao/Makefile	Sat Apr 17 01:50:23 2004 +0000
+++ b/src/work/klao/Makefile	Sat Apr 17 01:57:48 2004 +0000
@@ -1,4 +1,4 @@
-BINARIES = path_test map_test minlengthpaths
+BINARIES = path_test map_test iter_map_test
 INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,johanna,akos}
 include ../makefile
 
diff -r 538ff3ce9f68 -r e4ab32225f1c src/work/klao/iter_map.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/klao/iter_map.h	Sat Apr 17 01:57:48 2004 +0000
@@ -0,0 +1,121 @@
+// -*- c++ -*- //
+
+#ifndef HUGO_ITER_MAP
+#define HUGO_ITER_MAP
+
+#include <vector>
+#include <algorithm>
+// for uint8_t
+#include <stdint.h>
+// for memset
+#include <cstring>
+
+
+namespace hugo {
+
+
+  /// \todo Decide whether we need all the range checkings!!!
+
+  template<typename KeyIntMap, uint8_t N>
+  class IterableMap {
+  public:
+
+    typedef typename KeyIntMap::KeyType KeyType;
+    typedef uint8_t ValueType;
+
+    typedef typename std::vector<KeyType>::const_iterator iterator;
+
+  protected:
+    KeyIntMap &base;
+    std::vector<KeyType> data;
+    size_t bounds[N];
+
+    uint8_t find(size_t a) const {
+      uint8_t n=0;
+      for(; n<N && bounds[n]<=a; ++n);
+      return n;
+    }
+
+    void half_swap(size_t &a, size_t b) {
+      if(a != b) {
+	base.set(data[b],a);
+	data[a] = data[b];
+	a = b;
+      }
+    }
+
+    size_t move(size_t a, uint8_t m, uint8_t n) {
+      if(m != n) {
+	size_t orig_a = a;
+	KeyType orig_key = data[a];
+	while(m > n) {
+	  --m;
+	  half_swap(a, bounds[m]++);
+	}
+	while(m < n) {
+	  half_swap(a, --bounds[m]);
+	  ++m;
+	}
+	if(a != orig_a) {
+	  base.set(orig_key, a);
+	  data[a]=orig_key;
+	}
+      }
+      return a;
+    }
+
+  public:
+    
+    IterableMap(KeyIntMap &_base) : base(_base) {
+      memset(bounds, 0, sizeof(bounds));
+      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
+    }
+
+    uint8_t operator[](const KeyType& k) const {
+      return find(base[k]);
+    }
+
+    void set(const KeyType& k, uint8_t n) {
+      size_t a = base[k];
+      if(a < bounds[N-1]) {
+	base.set(k, move(a, find(a), n));
+      }
+    }
+
+    void insert(const KeyType& k, uint8_t n) {
+      if(n<N) {
+	data.push_back(k);
+	base.set(k, move(bounds[N-1]++, N-1, n));
+      }
+    }
+
+    iterator begin(uint8_t n) const {
+      if(n < N)
+	return data.begin() + (n ? bounds[n-1] : 0);
+      else
+	return data.end();
+    }
+
+    iterator end(uint8_t n) const {
+      if(n < N)
+	return data.begin() + bounds[n];
+      else
+	return data.end();
+    }
+
+    size_t size(uint8_t n) const {
+      if(n < N)
+	return bounds[n] - (n ? bounds[n-1] : 0);
+      else
+	return 0;
+    }
+    
+    size_t size() const {
+      // assert(bounds[N-1] == data.size());
+      return bounds[N-1];
+    }
+
+  };
+
+}
+#endif
diff -r 538ff3ce9f68 -r e4ab32225f1c src/work/klao/iter_map_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/klao/iter_map_test.cc	Sat Apr 17 01:57:48 2004 +0000
@@ -0,0 +1,117 @@
+#include <iter_map.h>
+#include <maps.h>
+
+#include <iostream>
+
+using namespace hugo;
+using namespace std;
+
+const int N = 3;
+
+typedef StdMap<int,int> BaseMap;
+typedef IterableMap<BaseMap, N> TestMap;
+
+
+void print(TestMap const& m) {
+  cout << "Size of the map: " << m.size() << endl;
+  for(int i=0; i<N; ++i) {
+    cout << "  Class " << i << ". (size=" << m.size(i) << "): " << flush;
+    cout << "    ";
+    for(TestMap::iterator j = m.begin(i); j!=m.end(i); ++j) {
+      cout << " " << *j;
+    }
+    cout << endl;
+  }
+}
+
+
+
+int main() {
+
+  BaseMap base(344);
+  TestMap test(base);
+
+
+  print(test);
+
+  cout << "Inserting 12 to class 2...\n";
+  test.insert(12,2);
+  print(test);
+
+
+  cout << "Inserting 22 to class 2...\n";
+  test.insert(22,2);
+  print(test);
+
+  cout << "Testing some map values:\n";
+  cout << " 12: " << int(test[12]) << endl;
+
+  cout << "Inserting 10 to class 0...\n";
+  test.insert(10,0);
+  print(test);
+
+  cout << "Testing some map values:\n";
+  cout << " 12: " << int(test[12]) << endl;
+
+  cout << "Inserting 11 to class 1...\n";
+  test.insert(11,1);
+  print(test);
+
+  cout << "Testing some map values:\n";
+  cout << " 12: " << int(test[12]) << endl;
+  cout << " 22: " << int(test[22]) << endl;
+  cout << " 10: " << int(test[10]) << endl;
+  cout << " 11: " << int(test[11]) << endl;
+  cout << " 42: " << int(test[42]) << endl;
+
+  cout << "Inserting 21 to class 1...\n";
+  test.insert(21,1);
+  print(test);
+
+  cout << "Inserting 20 to class 1...\n";
+  test.insert(20,0);
+  print(test);
+
+  cout << "Testing some map values:\n";
+  cout << " 12: " << int(test[12]) << endl;
+  cout << " 22: " << int(test[22]) << endl;
+  cout << " 10: " << int(test[10]) << endl;
+  cout << " 20: " << int(test[20]) << endl;
+  cout << " 11: " << int(test[11]) << endl;
+  cout << " 21: " << int(test[21]) << endl;
+  cout << " 42: " << int(test[42]) << endl;
+
+  cout << "Setting 20 to class 2...\n";
+  test.set(20,2);
+  print(test);
+  
+  cout << "Setting 10 to class 1...\n";
+  test.set(10,1);
+  print(test);
+  
+  cout << "Setting 11 to class 1...\n";
+  test.set(11,1);
+  print(test);
+  
+  cout << "Setting 12 to class 1...\n";
+  test.set(12,1);
+  print(test);
+  
+  cout << "Setting 21 to class 2...\n";
+  test.set(21,2);
+  print(test);
+  
+  cout << "Setting 22 to class 2...\n";
+  test.set(22,2);
+  print(test);
+  
+  cout << "Testing some map values:\n";
+  cout << " 12: " << int(test[12]) << endl;
+  cout << " 22: " << int(test[22]) << endl;
+  cout << " 10: " << int(test[10]) << endl;
+  cout << " 20: " << int(test[20]) << endl;
+  cout << " 11: " << int(test[11]) << endl;
+  cout << " 21: " << int(test[21]) << endl;
+  cout << " 42: " << int(test[42]) << endl;
+
+}
diff -r 538ff3ce9f68 -r e4ab32225f1c src/work/klao/minlengthpaths.cc
--- a/src/work/klao/minlengthpaths.cc	Sat Apr 17 01:50:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,127 +0,0 @@
-// -*- c++ -*-
-//#include <iostream>
-//#include <vector>
-//#include <string>
-
-#include <list_graph.h>
-#include <minlengthpaths.h>
-
-using namespace hugo;
-
-
-int main()
-{
-
-  
-  typedef ListGraph::Node Node;
-  typedef ListGraph::Edge Edge;
-
-  ListGraph graph;
-
-  /*
-  //Marci példája
-
-
-  NodeIt s=graph.addNode();
-  NodeIt v1=graph.addNode();
-  NodeIt v2=graph.addNode();
-  NodeIt v3=graph.addNode();
-  NodeIt v4=graph.addNode();
-  NodeIt t=graph.addNode();
-  
-
-  EdgeIt s_v1=graph.addEdge(s, v1);
-  EdgeIt s_v2=graph.addEdge(s, v2);
-  EdgeIt v1_v2=graph.addEdge(v1, v2);
-  EdgeIt v2_v1=graph.addEdge(v2, v1);
-  EdgeIt v1_v3=graph.addEdge(v1, v3);
-  EdgeIt v3_v2=graph.addEdge(v3, v2);
-  EdgeIt v2_v4=graph.addEdge(v2, v4);
-  EdgeIt v4_v3=graph.addEdge(v4, v3);
-  EdgeIt v3_t=graph.addEdge(v3, t);
-  EdgeIt v4_t=graph.addEdge(v4, t);
-
-  ListGraph::EdgeMap<int> length(graph);
-
-  length.set(s_v1, 16);
-  length.set(s_v2, 13);
-  length.set(v1_v2, 10);
-  length.set(v2_v1, 4);
-  length.set(v1_v3, 12);
-  length.set(v3_v2, 9);
-  length.set(v2_v4, 14);
-  length.set(v4_v3, 7);
-  length.set(v3_t, 20);
-  length.set(v4_t, 4);
-  */
-
-
-  //Ahuja könyv példája
-
-  Node s=graph.addNode();
-  Node v2=graph.addNode();
-  Node v3=graph.addNode();
-  Node v4=graph.addNode();
-  Node v5=graph.addNode();
-  Node t=graph.addNode();
-
-  Edge s_v2=graph.addEdge(s, v2);
-  Edge s_v3=graph.addEdge(s, v3);
-  Edge v2_v4=graph.addEdge(v2, v4);
-  Edge v2_v5=graph.addEdge(v2, v5);
-  Edge v3_v5=graph.addEdge(v3, v5);
-  Edge v4_t=graph.addEdge(v4, t);
-  Edge v5_t=graph.addEdge(v5, t);
-  
-  //Kis modositas
-  //edge_iterator v2_s=graph.add_edge(v2, s);
-
-  ListGraph::EdgeMap<int> length(graph);
-
-  length.set(s_v2, 10);
-  length.set(s_v3, 10);
-  length.set(v2_v4, 5);
-  length.set(v2_v5, 8);
-  length.set(v3_v5, 5);
-  length.set(v4_t, 8);
-  length.set(v5_t, 8);
-
-  //Kis modositas
-  //length.put(v2_s, 100);
- 
-
-
-
-  /*Egyszerű példa
-  NodeIt s=flow_test.add_node();
-  NodeIt v1=flow_test.add_node();
-  NodeIt v2=flow_test.add_node();
-  NodeIt t=flow_test.add_node();
-  
-  node_property_vector<list_graph, std::string> node_name(flow_test);
-  node_name.put(s, "s");
-  node_name.put(v1, "v1");
-  node_name.put(v2, "v2");
-  node_name.put(t, "t");
-
-  edge_iterator s_v1=flow_test.add_edge(s, v1);
-  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
-  edge_iterator v2_t=flow_test.add_edge(v2, t);
-
-  edge_property_vector<list_graph, int> length(flow_test); 
-    
-  length.put(s_v1, 16);
-  length.put(v1_v2, 10);
-  length.put(v2_t, 4);
-  */
-
-  std::cout << "Suurballe algorithm test..." << std::endl;
-
-  
-  int k=3;
-  MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
-    surb_test(graph, length);
-  std::cout << surb_test.run(s,t,k) << std::endl;
-
-  return 0;
-}
diff -r 538ff3ce9f68 -r e4ab32225f1c src/work/klao/minlengthpaths.h
--- a/src/work/klao/minlengthpaths.h	Sat Apr 17 01:50:23 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,134 +0,0 @@
-// -*- c++ -*-
-#ifndef HUGO_MINLENGTHPATHS_H
-#define HUGO_MINLENGTHPATHS_H
-
-///\file
-///\brief An algorithm for finding k paths of minimal total length.
-
-#include <iostream>
-#include <dijkstra.h>
-#include <graph_wrapper.h>
-#include <maps.h>
-
-namespace hugo {
-
-
-  ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
-  /// of minimal total length 
-  ///
-  /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
-  /// an algorithm which finds k edge-disjoint paths
-  /// from a given source node to a given target node in an
-  /// edge-weighted directed graph having minimal total weigth (length).
-
-  template <typename Graph, typename LengthMap>
-  class MinLengthPaths {
-
-    typedef typename LengthMap::ValueType Length;
-
-    typedef typename Graph::Node Node;
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::Edge Edge;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    typedef typename Graph::EdgeMap<int> EdgeIntMap;
-
-    typedef ConstMap<Edge,int> ConstMap;
-
-    typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
-
-
-    class ModLengthMap {   
-      typedef typename ResGraphType::NodeMap<Length> NodeMap;
-      const ResGraphType& G;
-      const EdgeIntMap& rev;
-      const LengthMap &ol;
-      const NodeMap &pot;
-    public :
-      typedef typename LengthMap::KeyType KeyType;
-      typedef typename LengthMap::ValueType ValueType;
-
-      ValueType operator[](typename ResGraphType::Edge e) const {     
-	if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
-	  ///\TODO This has to be removed
-	  std::cout<<"Negative length!!"<<std::endl;
-	}
-	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
-      }     
-
-      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 
-		   const LengthMap &o,  const NodeMap &p) : 
-	G(_G), rev(_rev), ol(o), pot(p){}; 
-    };
-    
-
-    const Graph& G;
-    const LengthMap& length;
-
-    //auxiliary variable
-    //The value is 1 iff the edge is reversed
-    EdgeIntMap reversed; 
-
-    
-  public :
-
-
-    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
-      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
-
-    ///Runs the algorithm
-    
-    ///Runs the algorithm
-    ///Returns k if there are at least k edge-disjoint paths from s to t.
-    ///Otherwise it returns the number of edge-disjoint paths from s to t.
-    int run(Node s, Node t, int k) {
-      ConstMap const1map(1);
-
-      ResGraphType res_graph(G, reversed, const1map);
-
-      //Initialize the copy of the Dijkstra potential to zero
-      typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
-      ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
-
-      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
-      
-      for (int i=0; i<k; ++i){
-	dijkstra.run(s);
-	if (!dijkstra.reached(t)){
-	  //There is no k path from s to t
-	  /// \TODO mit keresett itt ez a ++?
-	  return i;
-	};
-	
-	{
-	  //We have to copy the potential
-	  typename ResGraphType::NodeIt n;
-	  for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
-	      dijkstra_dist[n] += dijkstra.distMap()[n];
-	  }
-	}
-
-
-	//Reversing the sortest path
-	Node n=t;
-	Edge e;
-	while (n!=s){
-	  e = dijkstra.pred(n);
-	  n = dijkstra.predNode(n);
-	  reversed[e] = 1-reversed[e];
-	}
-
-	  
-      }
-      return k;
-    }
-
-
-
-
-
-  }; //class MinLengthPaths
-
-
-} //namespace hugo
-
-#endif //HUGO_MINLENGTHPATHS_H
diff -r 538ff3ce9f68 -r e4ab32225f1c src/work/makefile
--- a/src/work/makefile	Sat Apr 17 01:50:23 2004 +0000
+++ b/src/work/makefile	Sat Apr 17 01:57:48 2004 +0000
@@ -1,7 +1,7 @@
 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
 CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
 
-BINARIES ?= bin_heap_demo iterator_bfs_demo
+BINARIES ?= bin_heap_demo
 
 # Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam
 # ismert rendszeren :-)  (Misi)