From d069d90980d9bf0af1f414c4f7584295dca50c44 Mon Sep 17 00:00:00 2001 From: lonkaars Date: Sun, 5 Feb 2023 19:17:12 +0100 Subject: week 1 deel 2 --- algo1w1/IntOrderedArray.cpp | 83 +++++++++++ algo1w1/IntOrderedArray.h | 24 +++ algo1w1/NAW.cpp | 18 +++ algo1w1/NAW.h | 6 + algo1w1/NAWOrderedArray.cpp | 67 +++++++++ algo1w1/NAWOrderedArray.h | 22 +++ algo1w1/class-diagram.svg | 354 +++++++++++++++++++------------------------- algo1w1/main.cpp | 56 ++++--- 8 files changed, 407 insertions(+), 223 deletions(-) create mode 100644 algo1w1/IntOrderedArray.cpp create mode 100644 algo1w1/IntOrderedArray.h create mode 100644 algo1w1/NAWOrderedArray.cpp create mode 100644 algo1w1/NAWOrderedArray.h diff --git a/algo1w1/IntOrderedArray.cpp b/algo1w1/IntOrderedArray.cpp new file mode 100644 index 0000000..d84401f --- /dev/null +++ b/algo1w1/IntOrderedArray.cpp @@ -0,0 +1,83 @@ +#include "IntOrderedArray.h" +#include + +IntOrderedArray::IntOrderedArray() { +} + + +IntOrderedArray::~IntOrderedArray() { +} + +void IntOrderedArray::exploreBinarySearch(int searchKey) const { + int lowerBound = 0; + int upperBound = _collectionSize - 1; + int curIn; + while(1) { + curIn = (lowerBound + upperBound ) / 2; + if(_collection[curIn] == searchKey) + return (void) curIn; // found it + else if(lowerBound > upperBound) { + std::cout << "[" << lowerBound << ", " << upperBound << "]" << std::endl; + return (void) _collectionSize; // can’t find it + } + else // divide range + { + if(_collection[curIn] < searchKey) + lowerBound = curIn + 1; // it’s in upper half + else + upperBound = curIn - 1; // it’s in lower half + } // end find() + } +} + +/* + * vul hieronder de tabel in voor vraag 3.b + * + * waarde lowerbound upprbound + * ~~~~~~~~~ + * 0 [0, -1] + * 2 [1, 0] + * 4 [2, 1] + * 5 [2, 1] + * 23 [6, 5] + * 26 [6, 5] + * 30 [7, 6] + */ + +/* + * formuleer hieronder het antwoord op vraag 3.c + * + * in een ideale wereld waar alle array's alle elementen bevatten die je maar + * zou willen zoeken zou de index van het nummer dat je zoekt tussen upperBound + * en lowerBound liggen, e.g. "4" zou tussen 3 en 6 liggen met index 1 en 2. + */ + +int IntOrderedArray::getLastElementSmallerOrEqualTo(int) const { + return -1; +} + +void IntOrderedArray::moveElementsOnePositionToRight(int) { + // deze code wordt nergens gebruikt(?) +} + +int IntOrderedArray::quickInsert(int value) { + int i; + // find insert index + for (i = 0; i < _collectionSize; i++) { + if (_collection[i] > value) break; + } + // shift elements + for (int k = _collectionSize; k >= i; k--) { + if (k == 0) continue; + _collection[k] = _collection[k-1]; + } + _collectionSize++; + _collection[i] = value; + return i; +} + +void IntOrderedArray::showAll() const { + for (unsigned i = 0; i < _collectionSize; i++) { + printf("%02d: %d\n", i, _collection[i]); + } +} diff --git a/algo1w1/IntOrderedArray.h b/algo1w1/IntOrderedArray.h new file mode 100644 index 0000000..914e59f --- /dev/null +++ b/algo1w1/IntOrderedArray.h @@ -0,0 +1,24 @@ +#pragma once + +class IntOrderedArray { +public: + IntOrderedArray(); + virtual ~IntOrderedArray(); + +public: + virtual void exploreBinarySearch(int) const; + +public: + virtual int getLastElementSmallerOrEqualTo(int) const; + virtual void moveElementsOnePositionToRight(int); + + virtual int quickInsert(int); + +public: + virtual void showAll() const; + +private: + int _collection[20] = { 0 }; + unsigned _collectionSize = 0; +}; + diff --git a/algo1w1/NAW.cpp b/algo1w1/NAW.cpp index 72b1b29..907ad21 100644 --- a/algo1w1/NAW.cpp +++ b/algo1w1/NAW.cpp @@ -11,6 +11,16 @@ NAW::NAW(const std::string& naam, const std::string& adres, const std::string& w NAW::~NAW() { } +int NAW::compareTo(const NAW& other) const { + int c; + c = getPlaats().compare(other.getPlaats()); + if (c != 0) return c; + c = getNaam().compare(other.getNaam()); + if (c != 0) return c; + c = getAdres().compare(other.getAdres()); + return c; +} + const std::string& NAW::getNaam() const { return _naam; } const std::string& NAW::getAdres() const { return _adres; } const std::string& NAW::getPlaats() const { return _woonplaats; } @@ -22,3 +32,11 @@ void NAW::setPlaats(const std::string& woonplaats) { _woonplaats = woonplaats; } bool NAW::heeftNaam(const std::string& naam) const { return getNaam().compare(naam) == 0; } bool NAW::heeftAdres(const std::string& adres) const { return getAdres().compare(adres) == 0; } bool NAW::heeftPlaats(const std::string& woonplaats) const { return getPlaats().compare(woonplaats) == 0; } + +std::ostream& operator << (std::ostream& output, const NAW& naw) { + output << + "naam: " << naw.getNaam() << std::endl << + "adres: " << naw.getAdres() << std::endl << + "plaats: " << naw.getPlaats() << std::endl; + return output; +} diff --git a/algo1w1/NAW.h b/algo1w1/NAW.h index ad38133..75fd2c6 100644 --- a/algo1w1/NAW.h +++ b/algo1w1/NAW.h @@ -9,6 +9,9 @@ public: NAW(const std::string&, const std::string&, const std::string&); virtual ~NAW(); +public: + int compareTo(const NAW&) const; + public: virtual const std::string& getNaam() const; virtual const std::string& getAdres() const; @@ -24,6 +27,9 @@ public: virtual bool heeftAdres(const std::string&) const; virtual bool heeftPlaats(const std::string&) const; +public: + friend std::ostream& operator << (std::ostream& output, const NAW& naw); + private: std::string _naam, _adres, _woonplaats; }; diff --git a/algo1w1/NAWOrderedArray.cpp b/algo1w1/NAWOrderedArray.cpp new file mode 100644 index 0000000..6bce0cc --- /dev/null +++ b/algo1w1/NAWOrderedArray.cpp @@ -0,0 +1,67 @@ +#include "NAWOrderedArray.h" +#include "NAW.h" +#include +#include + +NAWOrderedArray::NAWOrderedArray() { } + +NAWOrderedArray::~NAWOrderedArray() { } + +int NAWOrderedArray::find(const NAW& naw) const { + unsigned tail = 0, head = _nawCollectionSize; // range is tail to head non-inclusive + unsigned max_attempts = log2(_nawCollectionSize) + 1; // return -1 infinite loop failsafe + for (unsigned x = 0; x < max_attempts; x++) { + unsigned guess = (head + tail) / 2; // take middle index + int diff = _nawCollection[guess]->compareTo(naw); + if (diff > 0) head = guess; // lower half (too high) + else if (diff < 0) tail = guess; // upper half (too low) + else return guess; // index found if compareTo(...) -> 0 + } + return -1; // infinite loop failsafe +} + +int NAWOrderedArray::add(const NAW& naw) { + int i; + // find insert index + for (i = 0; i < _nawCollectionSize; i++) { + if (_nawCollection[i]->compareTo(naw) > 0) break; + } + // shift elements + for (int k = _nawCollectionSize; k >= i; k--) { + if (k == 0) continue; + // std::cout << "moving [" << k-1 << "] to [" << k << "]" << std::endl; + _nawCollection[k] = _nawCollection[k-1]; + } + _nawCollectionSize++; + // std::cout << "inserting into [" << i << "]" << std::endl; + _nawCollection[i] = new NAW(naw); + return i; +} + +int NAWOrderedArray::remove(const NAW& naw) { + int i = find(naw); + // shift elements + for (int k = i; k < _nawCollectionSize; k++) + _nawCollection[k] = _nawCollection[k + 1]; + + _nawCollectionSize--; + return i; +} + +int NAWOrderedArray::replace(const NAW& cOld, const NAW& cNew) { + bool opdrachtBeschrijvingIsDuidelijk = false; // true om de array opnieuw te sorteren na vervangen + int i = find(cOld); + if (i < 0) return -1; + if (opdrachtBeschrijvingIsDuidelijk == false) { + _nawCollection[i] = new NAW(cNew); + } else { + remove(cOld); + add(cNew); + } + return i; +} + +void NAWOrderedArray::showAll() const { + for (unsigned i = 0; i < _nawCollectionSize; i++) + std::cout << *_nawCollection[i] << std::endl; +} diff --git a/algo1w1/NAWOrderedArray.h b/algo1w1/NAWOrderedArray.h new file mode 100644 index 0000000..f21bb1a --- /dev/null +++ b/algo1w1/NAWOrderedArray.h @@ -0,0 +1,22 @@ +#pragma once + +class NAW; + +class NAWOrderedArray { +public: + NAWOrderedArray(); + virtual ~NAWOrderedArray(); + +public: + virtual int find(const NAW&) const; + virtual int add(const NAW&); + virtual int remove(const NAW&); + virtual int replace(const NAW& cOld, const NAW& cNew); + +public: + virtual void showAll() const; + +private: + const NAW* _nawCollection[20] = { nullptr }; + unsigned _nawCollectionSize = 0; +}; diff --git a/algo1w1/class-diagram.svg b/algo1w1/class-diagram.svg index 0d0758a..f2740bc 100644 --- a/algo1w1/class-diagram.svg +++ b/algo1w1/class-diagram.svg @@ -1,6 +1,6 @@ - Qt SVG Document Generated with Qt @@ -18,592 +18,544 @@ font-family="Sans Serif" font-size="12" font-weight="400" font-style="normal" > - - - + - - - - - - - - - -0..20 +_nawCollection - - - - + - - - - --_nawCollection +0..20 - - - - + - - -NAWArray +NAW - - + - - - - _nawCollection : const NAW*[20] + >- _naam : string - - - _nawCollectionSize : unsigned + >- _adres : string - - - +- _woonplaats : string - - + - - -+ NAWArray() «constructor» - - + ~NAWArray() «destructor» + >+ NAW() «constructor» - - + add( : const NAW&) + >+ NAW( : const std::string&, : const std::string&, : const std::string&) «constructor» - - + zoekOpEersteNaam( : const std::string&) : int + >+ ~NAW() «destructor» - - + zoekOpEersteAdres( : const std::string&) : int + >+ compareTo( : const NAW&) : int - - + zoekOpEerstePlaats( : const std::string&) : int + >+ getNaam() : const std::string& - - + zoekOpEersteAdresEnPlaats( : const std::string&, : const std::string&) : int + >+ getAdres() : const std::string& - - + verwijderEersteMetNaam( : const std::string&) : int + >+ getPlaats() : const std::string& - - + verwijderLaatsteMetNaam( : const std::string&) : int + >+ setNaam( : const std::string&) - - + verwijderAllenMetNaam( : const std::string&) : int + >+ setAdres( : const std::string&) - - + verwijderEersteMetAdresEnPlaats( : const std::string&, : const std::string&) : int + >+ setPlaats( : const std::string&) - - + verwijderAllenMetAdresEnPlaats( : const std::string&, : const std::string&) : int - - - - - - - - - - - - - - - - - - - - - - - - - -NAW + >+ heeftNaam( : const std::string&) : bool - - - ++ heeftAdres( : const std::string&) : bool - - -- _naam : string ++ heeftPlaats( : const std::string&) : bool - - -- _adres : string - - -- _woonplaats : string - - - + - - +NAWOrderedArray - + - -+ NAW() «constructor» - - -+ NAW( : const std::string&, : const std::string&, : const std::string&) «constructor» +- _nawCollection : const NAW*[20] - - -+ ~NAW() «destructor» +- _nawCollectionSize : unsigned - - -+ getNaam() : const std::string& + - - -+ getAdres() : const std::string& - - -+ getPlaats() : const std::string& ++ NAWOrderedArray() «constructor» - - -+ setNaam( : const std::string&) ++ ~NAWOrderedArray() «destructor» - - -+ setAdres( : const std::string&) ++ find( : const NAW&) : int - - -+ setPlaats( : const std::string&) ++ add( : const NAW&) : int - - -+ heeftNaam( : const std::string&) : bool ++ remove( : const NAW&) : int - - -+ heeftAdres( : const std::string&) : bool ++ replace(cOld : const NAW&, cNew : const NAW&) : int - - -+ heeftPlaats( : const std::string&) : bool ++ showAll() - - @@ -613,7 +565,7 @@ font-family="Sans Serif" font-size="12" font-weight="400" font-style="normal" > - diff --git a/algo1w1/main.cpp b/algo1w1/main.cpp index 9b737e5..80451a2 100644 --- a/algo1w1/main.cpp +++ b/algo1w1/main.cpp @@ -1,11 +1,21 @@ -#include "NAWArray.h" +#include "NAWOrderedArray.h" #include "NAW.h" +#include "IntOrderedArray.h" + #include #include +void testNAWOrderedArray(); +void testIntOrderedArray(); + int main() { - NAWArray array; + testNAWOrderedArray(); + return 0; +} + +void testNAWOrderedArray() { + NAWOrderedArray array; for (int n = 0; n < 10; n++) { std::stringstream naam, adres, plaats; @@ -17,25 +27,27 @@ int main() { array.add({ naam.str(), adres.str(), plaats.str() }); } - std::cout << array.zoekOpEersteNaam("avans 4") << std::endl; - std::cout << array.zoekOpEersteNaam("avans 34") << std::endl; - std::cout << array.zoekOpEersteAdres("onderwijsboulevard 7") << std::endl; - std::cout << array.zoekOpEersteAdres("onderwijsboulevard 37") << std::endl; - std::cout << array.zoekOpEerstePlaats("den bosch 2") << std::endl; - std::cout << array.zoekOpEerstePlaats("den bosch 83") << std::endl; - std::cout << array.zoekOpEersteAdresEnPlaats("onderwijsboulevard 7", "den bosch 7") << std::endl; - std::cout << array.zoekOpEersteAdresEnPlaats("onderwijsboulevard 7", "den bosch 8") << std::endl; - - std::cout << array.verwijderEersteMetNaam("avans 4") << std::endl; - std::cout << array.verwijderEersteMetNaam("avans 34") << std::endl; - std::cout << array.verwijderLaatsteMetNaam("avans 5") << std::endl; - std::cout << array.verwijderLaatsteMetNaam("avans 34") << std::endl; - std::cout << array.verwijderAllenMetNaam("avans 5") << std::endl; - std::cout << array.verwijderAllenMetNaam("avans 34") << std::endl; - std::cout << array.verwijderEersteMetAdresEnPlaats("onderwijsboulevard 7", "den bosch 7") << std::endl; - std::cout << array.verwijderEersteMetAdresEnPlaats("onderwijsboulevard 7", "den bosch 8") << std::endl; - std::cout << array.verwijderAllenMetAdresEnPlaats("onderwijsboulevard 8", "den bosch 8") << std::endl; - std::cout << array.verwijderAllenMetAdresEnPlaats("onderwijsboulevard 9", "den bosch 8") << std::endl; + std::cout << array.find({"avans 7","onderwijsboulevard 7","den bosch 7"}) << std::endl; + std::cout << array.find({"avans 7","onderwijsboulevard 8","den bosch 9"}) << std::endl; + std::cout << array.add({"avans 7","onderwijsboulevard 8","den bosch 9"}) << std::endl; +// std::cout << array.add({"avans 7","onderwijsboulevard 8","den bosch 9"}) << std::endl; // niet-gedefinieerd requirement... + std::cout << array.remove({"avans 7","onderwijsboulevard 8","den bosch 9"}) << std::endl; + std::cout << array.remove({"avans 7","onderwijsboulevard 8","den bosch 9"}) << std::endl; + std::cout << array.replace({"avans 7","onderwijsboulevard 7","den bosch 7"}, {"avans 17","onderwijsboulevard 18","den bosch 19"}) << std::endl; + std::cout << array.replace({"avans 1","onderwijsboulevard 2","den bosch 3"}, {"avans 17","onderwijsboulevard 18","den bosch 19"}) << std::endl; - return 0; + array.showAll(); +} + +void testIntOrderedArray() { + IntOrderedArray array; + + for (int n = 1; n <= 10; n++) { + if ((n&1) == 0) + array.quickInsert(n+10); + else + array.quickInsert(n); + } + + array.showAll(); } -- cgit v1.2.3