Programowanie abstrakcyjne : przestrzenie z relacją sąsiedztwa

Przykład: przestrzenie z relacją sąsiedztwa


Operacja "owijania" zbioru

Operacja "owijania" zbioru jest zdefiniowana następująco:
Algorytm może wyglądać następująco
  1. Wejście: zbiór A
  2. Utwórz pusty zbiór Z
  3. Dla każdego p punktu z A
  4. Dla każdego punktu q w sąsiedztwie p wstaw q do Z
  5. Zwróć sumę mnogościową A i Z

Koncept zbioru

Koncept przestrzeni z relacją sąsiedztwa

Koncept boolable (dla punktu) w C++0x

concept boolable<typename T>{
  operator bool(T&);
}

Koncept zbioru w C++0x

concept SetConcept<typename Set>{
  typename Space=Set::Space;
  typename Point=Set::Space::Point;
  Set::Set(const Space&); // konstruktor zbioru pustego
  Set::Set(const Set&);   // konstruktor kopiujący
  Space Set::getSpace();
  int Set::cardinality();
  // operacje mnogościowe
  Set Set::operator+=(const Set&);
  Set Set::operator-=(const Set&);
  Set Set::operator*=(const Set&);
  Set& Set::insert(Point);
  Set& Set::remove(Point);
  bool Set::contains(Point);
}

Koncept generatora punktów w C++0x

concept PointGenretatorConcept<typename PtGen>{
  typename Set=PtGen::Space::Set;
  typename Point=PtGen::Space::Point;
  requires boolable<Point>;
  PtGen::PtGen(const Set&);
  Point getPoint();
}

Koncept generatora sąsiadów w C++0x

concept NeighborGenretatorConcept<typename NeighbGen>{
  typename Set=NeighbGen::Space::Set;
  typename Point=NeighbGen::Space::Point;
  requires boolable<Point>;
  NeighbGen::NeighbGen(const Space&,const Point&);
  Point getPoint();
}

Koncept przestrzeni z sąsiedztwem w C++0x

concept NeighborSpaceConcept<typename Space>{
  typename Set=Space::Set;
  typename Point=Space::Point;
  typename PtGen=Space::PtGen;
  typename NeighbGen=Space::NeighbGen;
  requires SetConcept<Set>;
  requires PointGenretatorConcept<PtGen>;
  requires NeighborGenretatorConcept<NeighbGen>;
  void Space::putPoint(std::ostream& s,const Point& p);
  void Space::getPoint(std::istream& s,const Point& p);
}

Szablon funkcji wrap() oparty o koncept przestrzeni z sąsiedztwem

template<SetConcept Set> requires SpaceConcept<Set::Space>
Set wrap(const Set& set){
  typedef typename Set::Space Space;
  typedef typename Space::PtGen PtGen;
  typedef typename Space::NeighbGen NeighbGen;
  Set s(set.getSpace());
  Set c(set);
  PtGen pg(set);
  while(Point p=pg.getPoint()){
    NeighbGen ng(set,p);
    while(Point r=ng.getPoint()){
      s.insert(r);
    }
  }
  c+=s;
  return c;
}

Interfejsy dla ograniczeń generyków w C#

Dziedziczenie parametryzowane

Przykład zastosowania: zbiór w konkretnej przestrzeni

Abstrakcyjna implementacja operacji w przestrzeni z sąsiedztwem w C++

Abstrakcyjna implementacja operacji w przestrzeni z sąsiedztwem w C#

Implementacje zbioru

Dwie implementacje zbioru w C++

Dwie implementacje zbioru w C#

Przestrzeń X4d(p)


Przestrzeń X8d(p)


Przestrzeń X18d(p)


Przestrzeń X6


Implementacja przestrzeni X8d(p), X18d(p), X4d(p) i X6

Implementacja przestrzeni X8d(p), X18d(p), X4d(p) i X6 w C++

Implementacja przestrzeni X8d(p), X18d(p), X4d(p) i X6 w C#

Pliki z funkcjami pomocniczymi i plik główny w C++

Pliki z funkcjami pomocniczymi i plik główny w C#