Связь списков

struct TStruct {
std::string * m_String_1;
std::string * m_String_2;
}

std::string ** arr_Type_1_Strings;
unsigned int Type1StringsCount;
std::string ** arr_Type_2_Strings;
unsigned int Type2StringsCount;

arr_Type_1_Strings

 (TStruct *tmpStruct=new TStruct)

tmpStruct->m_String_X = указатель на элемент массива где находится добавляемая строка.

 (std::string**)malloc(...)

arr_Type_X_Strings[number]=new std::string;

for(unsigned int i=Type1StringsCount;i>@index;i--){
     *arr_Type_X_Strings[i]=*arr_Type_X_Strings[i-1];
}

arr_Type_X_Strings[@index]=@Str2Add;

*arr_Type_X_Strings[i]=*arr_Type_X_Strings[i-1];

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>

#include <ctime>
#include <cstdlib>
#include <iostream>
#include <string>
 
// ñóùíîñòü "âëàäåëåö"
class Owner {
 public:
  Owner(const std::string &name, const std::string &address)
    : name(name), address(address) {}
  const std::string &getName() const { return name; }
  const std::string &getAddress() const { return address; }
 private:
  // ñëåäóþùèå äâå ñòðîêè çîðêî ñëåäÿò, ÷òîáû
  // íå áûëî âûçîâîâ êîíñòðóêòîðà êîïèðîâàíèÿ è îïåðàòîðà ïðèñâàèâàíèÿ
  Owner(const Owner&);
  Owner &operator=(const Owner&);
  const std::string name;
  const std::string address;
};
 
// ñóùíîñòü "êîìïàíèÿ"
class Company {
 public:
  Company(const std::string &name) : name(name) {}
  const std::string &getName() const { return name; }
 private:
  // ñëåäóþùèå äâå ñòðîêè çîðêî ñëåäÿò, ÷òîáû
  // íå áûëî âûçîâîâ êîíñòðóêòîðà êîïèðîâàíèÿ è îïåðàòîðà ïðèñâàèâàíèÿ
  Company(const Company&);
  Company &operator=(const Company&);
  const std::string name;
};
 
// ñóùíîñòü "âëàäåëåö ôèðìû"
class CompanyOwner {
 public:
  CompanyOwner(const Company &company, const Owner &owner)
    : company(company), owner(owner) {}
  const Company &getCompany() const { return company; }
  const Owner &getOwner() const { return owner; }
 private:
  // ñëåäóþùèå äâå ñòðîêè çîðêî ñëåäÿò, ÷òîáû
  // íå áûëî âûçîâîâ êîíñòðóêòîðà êîïèðîâàíèÿ è îïåðàòîðà ïðèñâàèâàíèÿ
  CompanyOwner(const CompanyOwner&);
  CompanyOwner &operator=(const CompanyOwner&);
  const Company &company;
  const Owner &owner;
};
 
// ïîíàäîáÿòñÿ îïåðàòîðû âûâîäà, ÷òîáû óäîáíî âûâîäèòü ñóùíîñòè
std::ostream &operator<<(std::ostream &stream, const Owner &owner) {
  return stream << "Owner{" <<
    "name='" << owner.getName() << "'," <<
    "address='" << owner.getAddress() << "'}";
}
std::ostream &operator<<(std::ostream &stream, const Company &company) {
  return stream << "Company{" <<
    "name='" << company.getName() << "'}";
}
std::ostream &operator<<(std::ostream &stream, const CompanyOwner &companyOwner) {
  return stream << "CompanyOwner{" <<
    "company=" << companyOwner.getCompany() << "," <<
    "owner=" << companyOwner.getOwner() << "}";
}
 
// äëÿ ïîèñêîâûõ àëãîðèòìîâ ïîíàäîáÿòñÿ îïåðàòîðû ñðàâíåíèÿ.
// äîñòàòî÷íî îïåðàöèè "ìåíüøå"
bool operator<(const Owner &a, const Owner &b) {
  return (a.getName() < b.getName()) ||
    (!(b.getName() < a.getName()) && a.getAddress() < b.getAddress());
}
bool operator<(const Company &a, const Company &b) {
  return (a.getName() < b.getName());
}
bool operator<(const CompanyOwner &a, const CompanyOwner &b) {
  if (&a.getCompany() != &b.getCompany()) {
    return true;
  }
  return (a.getCompany() < b.getCompany()) || 
    (!(b.getCompany() < a.getCompany()) && a.getOwner() < b.getOwner());
}
 
// ôóíêöèÿ äëÿ ñðàâíåíèÿ çíà÷åíèé, ïåðåäàííûõ ÷åðåç òèïèçèîâàííûé óêàçàòåëü
template<class T>
bool lesserByPointer(const T *a, const T *b) {
  return *a < *b;
}
 
// îáîáùåííûé áèíàðíûé ïîèñê
template <class ForwardIterator, class T, class Compare>
ForwardIterator lowerBound (ForwardIterator first, ForwardIterator last,
  const T& val, Compare comp) {
  size_t count = last - first;
  while (count>0)
  {
    ForwardIterator it = first;
    size_t step=count/2;
    it += step;
    if (comp(*it, val)) {
      first = ++it;
      count -= step + 1;
    } else {
      count = step;
    }
  }
  return first;
}
 
// âñïîìîãàòåëüíàÿ ñóùíîñòü, ïîçâîëÿþùàÿ õðàíèòü òèïèçèðîâàííûå óêàçàòåëè
template <class T, bool repetitionsAllowed = false>
class Storage {
 public:
  Storage() : size(0), capacity(1000), capacityIncrement(100),
    data(new T*[capacity]) {}
  virtual ~Storage() {
    clear();
    delete [] data;
  }
  const T *add(T *value) {
    checkCapacity();
    T **position = lowerBound(data, data + size, value, lesserByPointer<T>);
    if (!repetitionsAllowed && position < end() && !(*value < **position)) {
      return *position;
    } else {
      for (T **i = data + size; i > position; --i) {
        *i = *(i - 1);
      }
      *position = value;
      ++size;
    }
    return *position;
  }
  T *remove(const T *value) {
    T **position = lowerBound(data, data + size, value, lesserByPointer<T>);
    if (position < end() && !(*value < **position)) {
      T *result = *position;
      for (T **i = position; i < end() - 1; ++i) {
        *i = *(i + 1);
      }
      --size;
      return result;
    } else {
      return 0;
    }
  }
  const T *operator[](size_t i) const {
    return data[i];
  }
  T * const *find(T *value) const {
    T **position = lowerBound(data, data + size, value, lesserByPointer<T>);
    if (position < end() && !(*value < **position)) {
      return position;
    } else {
      return end();
    }
  }
  size_t getCapacityIncrement() const { return capacityIncrement; }
  void setCapacityIncrement(size_t capacityIncrement) {
    this->capacityIncrement = capacityIncrement;
  }
  size_t getSize() const { return size; }
  void clear() {
    size = 0;
  }
  T * const *begin() const { return data; }
  T * const *end() const { return data + size; }
 protected:
  void checkCapacity() {
    if (capacity <= size - 1) {
      capacity += getCapacityIncrement();
      T **newData = new T*[capacity];
      for (int i = 0; i < size; ++i) {
        newData[i] = data[i];
      }
      delete [] data;
      data = newData;
    }
  }
 private:
  // ñëåäóþùèå äâå ñòðîêè çîðêî ñëåäÿò, ÷òîáû
  // íå áûëî âûçîâîâ êîíñòðóêòîðà êîïèðîâàíèÿ è îïåðàòîðà ïðèñâàèâàíèÿ
  Storage(const Storage&);
  Storage &operator=(const Storage&);
  size_t size;
  size_t capacity;
  size_t capacityIncrement;
  T **data;
};
 
// ñóùíîñòü, õðàíÿùàÿ âëàäåëüöåâ
class OwnerSource {
 public:
  OwnerSource() : storage() {}
  virtual ~OwnerSource() {
    for (Owner * const *i = storage.begin(); i != storage.end(); ++i) {
      delete *i;
    }
    storage.clear();
  }
  bool add(const std::string &name, const std::string &address) {
    Owner *owner = new Owner(name, address);
    const Owner *result = storage.add(owner);
    if (result != owner) {
      delete owner;
      return false;
    } else {
      return true;
    }
  }
  bool remove(const std::string &name, const std::string &address) {
    Owner owner(name, address);
    const Owner *removed = storage.remove(&owner);    
    bool result = removed != 0;
    delete removed;
    return result;
  }
  bool contains(const std::string &name, const std::string &address) const {
    Owner object(name, address);
    return storage.find(&object) != storage.end();
  }
  size_t getSize() const {
    return storage.getSize();
  }
  const Owner &operator[](size_t position) const {
    return *storage[position];
  }
 private:
  // ñëåäóþùèå äâå ñòðîêè çîðêî ñëåäÿò, ÷òîáû
  // íå áûëî âûçîâîâ êîíñòðóêòîðà êîïèðîâàíèÿ è îïåðàòîðà ïðèñâàèâàíèÿ
  OwnerSource(const OwnerSource&);
  OwnerSource &operator=(const OwnerSource&);
  Storage<Owner, false> storage;
};
 
// ñóùíîñòü, õðàíÿùàÿ êîìïàíèè
class CompanySource {
 public:
  CompanySource() : storage() {}
  virtual ~CompanySource() {
    for (Company * const *i = storage.begin(); i != storage.end(); ++i) {
      delete *i;
    }
    storage.clear();
  }
  bool add(const std::string &name) {
    Company *object = new Company(name);
    const Company *result = storage.add(object);
    if (result != object) {
      delete object;
      return false;
    } else {
      return true;
    }
  }
  // ïîñêîëüó â êîìïàíèÿõ âîçìîæíû ïîâòîðåíèÿ,
  // ýëåìåíò óäàëÿåòñÿ ïî èíäåêñó
  void remove(int i) {
    Company *removed = storage.remove(storage[i]);
    delete removed;
  }
  size_t getSize() const {
    return storage.getSize();
  }
  const Company &operator[](size_t position) const {
    return *storage[position];
  }
 private:
  // ñëåäóþùèå äâå ñòðîêè çîðêî ñëåäÿò, ÷òîáû
  // íå áûëî âûçîâîâ êîíñòðóêòîðà êîïèðîâàíèÿ è îïåðàòîðà ïðèñâàèâàíèÿ
  CompanySource(const CompanySource&);
  CompanySource &operator=(const CompanySource&);
  Storage<Company, true> storage;
};
 
// ñóùíîñòü, õðàíÿùàÿ ñâÿçè êîìïàíèÿ-âëàäåëåö
class CompanyOwnerSource {
 public:
  CompanyOwnerSource() : storage() {}
  virtual ~CompanyOwnerSource() {
    for (CompanyOwner * const *i = storage.begin(); i != storage.end(); ++i) {
      delete *i;
    }
    storage.clear();
  }
  bool add(const Company &company, const Owner &owner) {
    CompanyOwner *object = new CompanyOwner(company, owner);
    const CompanyOwner *result = storage.add(object);
    if (result != object) {
      delete object;
      return false;
    } else {
      return true;
    }
  }
  bool remove(const Company &company, const Owner &owner) {
    CompanyOwner object(company, owner);
    const CompanyOwner *removed = storage.remove(&object);
    bool result = removed != 0;
    delete removed;
    return result;
  }
  bool contains(const Company &company, const Owner &owner) const {
    CompanyOwner object(company, owner);
    return storage.find(&object) != storage.end();
  }
  size_t getSize() const {
    return storage.getSize();
  }
  const CompanyOwner &operator[](size_t position) const {
    return *storage[position];
  }
 private:
  // ñëåäóþùèå äâå ñòðîêè çîðêî ñëåäÿò, ÷òîáû
  // íå áûëî âûçîâîâ êîíñòðóêòîðà êîïèðîâàíèÿ è îïåðàòîðà ïðèñâàèâàíèÿ
  CompanyOwnerSource(const CompanyOwnerSource&);
  CompanyOwnerSource &operator=(const CompanyOwnerSource&);
  Storage<CompanyOwner, false> storage;
};
 
int main(int argc, char **argv) {
  srand(time(0));
  
  OwnerSource owners; // èñòî÷íèê äàííûõ î âëàäåëüöàõ
  owners.add("Ivan", "Lenina 12");
  owners.add("Petr", "Tupik 9");
  owners.add("Ivan", "Lenina 12");  // íå áóäåò äîáàâëåí
  owners.add("Vladimir", "Ilyicha 73");
  owners.add("Ivan", "Stalina 33");
  owners.add("Petr", "Tupik 33");
  owners.remove("Petr", "Tupik 9"); // óäàëåíèå ýëåìåíòà
  owners.add("Alexandr", "Soyuza 1");
  owners.add("Zinaida", "Joka 8");
  owners.add("Anna", "Mendelya 42");
  // âûâîä ýëåìåíòîâ
  for (int i = 0; i < owners.getSize(); ++i) {
    std::cout << owners[i] << std::endl;
  }
 
  CompanySource companies; // èñòî÷íèê äàííûõ î êîìïàíèÿõ
  companies.add("vector");
  companies.add("vector");
  companies.add("iwai");
  companies.add("nobie");
  companies.remove(2);     // óäàëåíèå ïî èíäåêñó
  companies.add("vector");
  
  for (int i = 0; i < companies.getSize(); ++i) {
    std::cout << companies[i] << std::endl;
  }
 
  CompanyOwnerSource companyOwners;
  for (int i = 0; i < companies.getSize(); ++i) {
    std::cout << "adding for " << companies[i] << std::endl;
    for (int j = 0; j < owners.getSize(); ++j) {
      companyOwners.add(companies[i], owners[rand() % owners.getSize()]);
    }
  }
  
  for (int i = 0; i < companyOwners.getSize(); ++i) {
    std::cout << companyOwners[i] << std::endl;
  }
  
  return 0;
}

#ifndef __PROGTEST__
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
#endif /* __PROGTEST__ */
 
 
class CEntity;
class CEntities;
class CCompanyIndex;
class CIterator;
 
/**
 * @CEntity
 *
 * Represents some entity with basic control over it. 
 * Has an array of links to other entities.
 * Array of links is an array of pointers.
 * @WARNING Size of pointers array only grows up!
 * 
 * @friends CEntities
 * 
 * @constructor Entity() - basic constructor
 * @destructor ~Entity() - basic destructor
 * @method void AddLink( CEntity * NewEntity ) - adds link
 * @method void DelLink( CEntity * DelEntity ) - deletes link
 * @method  int GetLinksCount()const - returns number of active links
 *
 * @param std::string m_Name name value 
 * @param std::string m_Address address value 
 * @param int iLinksCount number of active links
 * @param CEntity ** m_Links an array of pointers to other entities
 */
class CEntity {
public:
 
    /**
     * Basic Constructor
     */
    CEntity() {
        m_Name = "";
        m_Address = "";
        m_Links = NULL;
        iLinksCount = 0;
        iLinksSize = 0;
    };
 
    /**
     * Basic Destructor
     */
    ~CEntity() {
        free(m_Links);
    };
 
    /**
     * Finds if link to requested entity exists in array and returns its index
     * @WARNING uses linear search algorithm
     * @param CEntity * FindEntity - pointer to CEntity which have to be found
     * @param  int & pos - position where link is.
     */
    bool SearchLink(CEntity * FindEntity, int & pos) {
 
        for (int i = 0; i < iLinksCount; i++) {
            if (m_Links[i] == FindEntity) {
                pos = i;
                return true;
                break;
            }
        }
        return false;
    }
 
    /**
     * Adds link to some entity to m_Links array, also resizing it
     * @param CEntity * NewEntity - pointer to CEntity
     */
    void AddLink(CEntity * NewEntity) {
        if (iLinksCount >= iLinksSize) {
            ++iLinksSize *= 2;
            m_Links = (CEntity**) realloc(m_Links, sizeof (CEntity*)*(iLinksSize + 1));
        }
        m_Links[iLinksCount++] = NewEntity;
    };
 
    /**
     * Finds and deletes link to some entity from m_Links array, 
     * without resizing it!@WARNING uses linear search algorithm
     * @param CEntity * DelEntity - pointer to CEntity which have to be deleted
     */
    void DelLink(CEntity * DelEntity) {
        int pos;
        if (SearchLink(DelEntity, pos)) {
            for (int i = pos; i < iLinksCount - 1; i++) {
                m_Links[i] = m_Links[i + 1];
            }
            iLinksCount--;
            m_Links[iLinksCount] = NULL;
        }
    };
 
    /**
     * Returns number of linked entities
     * @return int iLinksCount - number of existing links
     */
    int GetLinksCount()const {
        return iLinksCount;
    };
 
    friend class CEntities;
    friend class CIterator;
    friend class CCompanyIndex;
private:
 
    std::string m_Name;
    std::string m_Address;
    CEntity ** m_Links;
    int iLinksCount;
    int iLinksSize;
};
 
/**
 * @CEntities
 *
 * Represents CEntity Array of entities with advanced control over it.
 * Stores all entities in an alphabetical order using both m_Name and m_Address strings for sorting.
 * @WARNING Size of pointers (to entities) array only grows up!
 * 
 * 
 * @constructor CEntities() - basic constructor
 * @destructor ~CEntities() - basic destructor
 * @method bool Add - adds link and returns pointer to it
 * @method bool Del - deletes enity and returns true or false if entity was not found
 * @method CEntity * Search - returns pointer to entity or NULL if don't exists
 * 
 * @param CEntity ** InstancesArray array of pointers to entities
 * @param int iInstancesCount number of active entities
 * @param int iInstancesSize physical size of pointers array, grows in a geometrical progression with q = 2.0
 */
class CEntities {
public:
 
    /**
     * Basic Constructor which alocates memory for 1000 new instances of CEntity, also calling their constructors
     */
    CEntities() {
        iInstancesSize = 100;
        iInstancesCount = 0;
        InstancesArray = NULL;
        InstancesArray = (CEntity**) realloc(InstancesArray, sizeof (CEntity*) * iInstancesSize);
        for (int i = 0; i < iInstancesSize; i++) {
            InstancesArray[i] = new CEntity;
        }
    };
 
    /**
     * Basic Destructor - calls destructor for every entity and then frees all allocated for pointers array memory
     */
    ~CEntities() {
        for (int i = 0; i < iInstancesSize; i++) {
            delete InstancesArray[i];
        }
        free(InstancesArray);
    };
 
    /**
     * @Add
     * 
     * Adds new entity to instances array, and returns true, or returns false and do nothing if such a pair exists
     * 
     * @param const std::string & oName - entity name value
     * @param const std::string & oAddr - enity address value
     */
    CEntity* Add(const std::string& Name,
            const std::string& Addr) {
        int pos = -1;
        if (FindPair(Name, Addr, pos)) {
            //        cout << "Exists" << endl;
            return NULL;
        }
        //     else {
        //        cout << "Don't exists" << endl;
        //    }
        //    cout << "Inserting to " << pos << endl;
        if (iInstancesCount >= iInstancesSize) {
            iInstancesSize *= 1.5;
            InstancesArray = (CEntity**) realloc(InstancesArray, sizeof (CEntity*) * iInstancesSize);
            for (int i = iInstancesCount; i < iInstancesSize; i++) {
                InstancesArray[i] = new CEntity;
            }
        }
        delete InstancesArray[iInstancesCount];
        for (int i = iInstancesCount; i > pos; i--) {
            InstancesArray[i] = InstancesArray[i - 1];
        }
        iInstancesCount++;
        InstancesArray[pos] = new CEntity;
        InstancesArray[pos]->m_Name = Name;
        InstancesArray[pos]->m_Address = Addr;
        return InstancesArray[pos];
    }
 
    /**
     * @Del
     * 
     * Finds by requested pair of strings an entity, deletes it and returns true or false if entity was not found
     * 
     * @param const std::string & oName - entity name value
     * @param const std::string & oAddr - enity address value
     */
    bool Del(const std::string & oName,
            const std::string & oAddr) {
        int pos = -1;
        if (!FindPair(oName, oAddr, pos)) {
            //        cout << "Exists" << endl;
            return false;
        }
        delete InstancesArray[pos];
        for (int i = pos; i < iInstancesCount - 1; i++) {
            InstancesArray[i] = InstancesArray[i + 1];
        }
        iInstancesCount--;
        InstancesArray[iInstancesCount] = new CEntity;
        return true;
    }
 
    /**
     * @Search
     * 
     * Looking for requested pair of name and adress
     * 
     * @return pointer to CEntity or NULL if don't exists
     */
    CEntity * Search(const std::string & oName,
            const std::string & oAddr)const {
        int pos = -1;
        if (!FindPair(oName, oAddr, pos)) {
            return NULL;
        }
        return InstancesArray[pos];
    }
    friend class CCompanyIndex;
private:
 
    /**
     * @GetFirstAddrPosition
     * 
     * Looking for requested Address in entities array
     * sets index of first element with requested Address on requested interval 
     * or index where it should be if there is no entity with such an address 
     * on such interval
     * 
     * @return true if requested string found or false if not
     */
    bool GetFirstAddrPosition(const std::string& Str2Find,
            int f,
            int Size,
            int& pos)const {
        int l = f;
        int r = Size;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (Str2Find.compare(InstancesArray[m]->m_Address) > 0) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        pos = l;
        if (Str2Find.compare(InstancesArray[l]->m_Address) == 0) {
            return true;
        }
        return false;
    }
 
    /**
     * @GetLastAddrPosition
     * 
     * Looking for requested Address in entities array
     * sets index of last element with requested Address on requested interval 
     * or index where it should be if there is no entity with such an address 
     * on such interval
     * 
     * @return true if requested string found or false if not
     */
    bool GetLastAddrPosition(const std::string& Str2Find,
            int f,
            int Size,
            int& pos)const {
        int l = f;
        int r = Size;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (!(Str2Find.compare(InstancesArray[m]->m_Address) < 0)) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        pos = l;
        if (Str2Find.compare(InstancesArray[l - 1]->m_Address) == 0) {
            return true;
        }
        return false;
    }
 
    /**
     * @GetFirstNamePosition
     * 
     * Looking for requested Name in entities array
     * sets index of first element with requested Name on requested interval 
     * or index where it should be if there is no entity with such a Name
     * on such interval
     * 
     * @return true if requested string found or false if not
     */
    bool GetFirstNamePosition(const std::string& Str2Find,
            int f,
            int Size,
            int& pos)const {
        int l = f;
        int r = Size;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (Str2Find.compare(InstancesArray[m]->m_Name) > 0) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        pos = l;
        if (Str2Find.compare(InstancesArray[l]->m_Name) == 0) {
            return true;
        }
        return false;
    }
 
    /**
     * @GetLastNamePosition
     * 
     * Looking for requested Address in entities array
     * sets index of last element with requested Address on requested interval 
     * or index where it should be if there is no entity with such a Name
     * on such interval
     * 
     * @return true if requested string found or false if not
     */
    bool GetLastNamePosition(const std::string& Str2Find,
            int f,
            int Size,
            int& pos)const {
        int l = f;
        int r = Size;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (!(Str2Find.compare(InstancesArray[m]->m_Name) < 0)) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        pos = l;
        if (Str2Find.compare(InstancesArray[l - 1]->m_Name) == 0) {
            return true;
        }
        return false;
    }
 
    /**
     * @FindPair
     * 
     * Looking for requested pair of name and adress setting index in array where such an entity is or should be
     * method FindPair returns true if there is CEntity with such a Str2Find1 and 
     * Str2Find2, or false if there is no such pair
     * in both cases returns position, using reference int&pos, 
     * where this entity already is or should be
     * 
     * @return true if exists or false if it doesn't
     */
    bool FindPair(const std::string& Str2Find1,
            const std::string& Str2Find2,
            int& pos)const {
 
        int InsertPositionFirstArg = 0;
        int InsertPositionSecondArg = 0;
        bool IfFoundFirstArg = false;
        bool IfFoundSecondArg = false;
        bool PairExists = true;
        std::string SearchQuery1 = Str2Find1;
        std::string SearchQuery2 = Str2Find2;
        int FirstElement = 0;
        int ElementAgainstLast = iInstancesCount;
        IfFoundFirstArg = GetFirstNamePosition(SearchQuery1, FirstElement, ElementAgainstLast, InsertPositionFirstArg);
        if (IfFoundFirstArg) {
            //cout << "First entity for String \"" << SearchQuery1 << "\" Found on index: " << InsertPositionFirstArg << endl;
            IfFoundSecondArg = GetLastNamePosition(SearchQuery1, FirstElement, ElementAgainstLast, InsertPositionSecondArg);
            if (IfFoundSecondArg) {
                //cout << "Last entity for String \"" << SearchQuery1 << "\" Found on index: " << InsertPositionSecondArg - 1 << endl;
                IfFoundFirstArg = GetFirstAddrPosition(SearchQuery2, InsertPositionFirstArg, InsertPositionSecondArg, InsertPositionFirstArg);
                if (IfFoundFirstArg) {
                    //cout << "First entity for String \"" << SearchQuery2 << "\" Found on index: " << InsertPositionFirstArg << endl;
                    IfFoundSecondArg = GetLastAddrPosition(SearchQuery2, InsertPositionFirstArg, InsertPositionSecondArg, InsertPositionSecondArg);
                    if (IfFoundSecondArg) {
                        //cout << "Last entity for String \"" << SearchQuery2 << "\" Found on index: " << InsertPositionSecondArg - 1 << endl;
                    } else {
                        PairExists = false;
                        //cout << "Last entity for String \"" << SearchQuery2 << "\" was NOT found; insert it to index: " << InsertPositionSecondArg - 1 << endl;
                    }
                } else {
                    PairExists = false;
                    //cout << "Last entity for String \"" << SearchQuery2 << "\" was NOT found; insert it to index: " << InsertPositionFirstArg << endl;
                }
            } else {
                PairExists = false;
                //cout << "Last entity for String \"" << SearchQuery1 << "\" was NOT found; insert it to index: " << InsertPositionSecondArg - 1 << endl;
            }
        } else {
            PairExists = false;
            //cout << "First entity for String \"" << SearchQuery1 << "\" was NOT found; insert it to index: " << InsertPositionFirstArg << endl;
        }
        int ins;
        if (IfFoundFirstArg && IfFoundSecondArg) {
            ins = (InsertPositionSecondArg < InsertPositionFirstArg) ? InsertPositionSecondArg : InsertPositionFirstArg;
        } else {
            ins = (IfFoundFirstArg) ? InsertPositionSecondArg : InsertPositionFirstArg;
        }
        //cout << "pair exists ? - " << PairExists << endl;
        //cout << "insert at the end = " << ins << endl;
        pos = ins;
        return PairExists;
    }
 
    /**
     * @Print
     * 
     * Prints out all current instances
     */
    void Print() {
        for (int i = 0; i < iInstancesCount; i++) {
            std::cout << "[" << i << "]\t" << InstancesArray[i]->m_Name << "\t" << InstancesArray[i]->m_Address << std::endl;
        }
    };
    CEntity ** InstancesArray;
    int iInstancesCount;
    int iInstancesSize;
 
};
 
class CIterator {
public:
 
    CIterator() {
        iEntitiesCount = 0;
        Current = 0;
        Entities = NULL;
    };
 
    ~CIterator() {
        free(Entities);
    };
 
    bool AtEnd(void) const {
        bool b = (Current == iEntitiesCount);
        return b;
    };
 
    void Next(void) {
        Current++;
    };
 
    const string & Name(void) const {
        return Entities[Current]->m_Name;
    };
 
    const string & Address(void) const {
        return Entities[Current]->m_Address;
    };
 
    void AddEntity(CEntity * NewEntity) {
        Entities = (CEntity**) realloc(Entities, sizeof (CEntity*)*(iEntitiesCount + 1));
        Entities[iEntitiesCount] = NewEntity;
        iEntitiesCount++;
    };
private:
    CEntity ** Entities;
    int iEntitiesCount;
    int Current;
 
};
 
class CCompanyIndex {
public:
 
    CCompanyIndex() {
        Owners = new CEntities;
        Companies = new CEntities;
    };
 
    ~CCompanyIndex() {
        delete Owners;
        delete Companies;
    }
    ;
 
    bool Add(const string & oName,
            const string & oAddr,
            const string & cName,
            const string & cAddr);
 
    bool Del(const string & oName,
            const string & oAddr,
            const string & cName,
            const string & cAddr);
 
    CIterator * SearchOwner(const string & oName,
            const string & oAddr) const;
 
    CIterator * SearchCompany(const string & cName,
            const string & cAddr) const;
 
    void Print() {
 
 
        Owners->Print();
 
 
 
        Companies->Print();
 
    }
private:
 
    CEntities * Owners;
    CEntities * Companies;
 
};
 
bool CCompanyIndex::Add(const std::string& oName, const std::string& oAddr, const std::string& cName, const std::string& cAddr) {
    /**Metoda Add(oName, oAddr, cName, cAddr) přidá do existující databáze další záznam. 
     * Metoda vrací hodnotu true, pokud byl do záznam přidán, nebo hodnotu false, 
     * pokud přidán nebyl 
     * (protože již v databázi existoval záznam o tom, že daný majitel vlastní podíl v zadané firmě.). 
     * Parametry oName a oAddr reprezentují jméno a adresu vlastníka, parametry cName a cAddr udávají název a adresu firmy.
     */
    CEntity * Owner = Owners->Search(oName, oAddr);
    CEntity * Company = Companies->Search(cName, cAddr);
    if ((Owner != NULL)&&(Company != NULL)) {
        //look for link between them
        int pos;
        if (Owner->SearchLink(Company, pos)) {
            return false; //link was found
        }
    }
    if ((Owner == NULL)) {
        if ((Owner = Owners->Add(oName, oAddr)) == NULL) {
            return false;
        }
 
 
    }
    if ((Company == NULL)) {
        if ((Company = Companies->Add(cName, cAddr)) == NULL) {
            return false;
        }
    }
    Owner->AddLink(Company);
    Company->AddLink(Owner);
 
 
 
    return true;
}
 
bool CCompanyIndex::Del(const string & oName,
        const string & oAddr,
        const string & cName,
        const string & cAddr) {
    /**Metoda Del (oName, oAddr, cName, cAddr) odstraní záznam z databáze. 
     * Pokud byl záznam skutečně odstraněn, vrátí metoda hodnotu true. 
     * Pokud záznam neodstraní (protože zadaný majitel neměl v zadané firmě podíl), 
     * vrátí metoda hodnotu false.
     */
    CEntity * Owner = Owners->Search(oName, oAddr);
    CEntity * Company = Companies->Search(cName, cAddr);
    if ((Owner != NULL)) {
        if (Company != NULL) {
            int pos;
            if (Owner->SearchLink(Company, pos)) {
                //link was found
                Owner->DelLink(Company);
                Company->DelLink(Owner);
                if (Owner->GetLinksCount() == 0) {
                    Owners->Del(oName, oAddr);
                }
                if (Company->GetLinksCount() == 0) {
                    Companies->Del(cName, cAddr);
                }
                return true; //deleted
            } else {
                return false; //there is no link between company and owner
            }
        } else {
            return false; //there is no company
        }
    } else {
        return false; //there is no owner
    }
    return false;
}
 
CIterator * CCompanyIndex::SearchOwner(const string & oName,
        const string & oAddr) const {
    /*Metoda SearchOwner (oName, oAddr) zjistí seznam všech firem, ve kterých má zadaný majitel podíl. 
     * Pokud zadaný majitel nemá podíl v žádné firmě, metoda vrátí návratovou hodnotu NULL. 
     * Pokud zadaný majitel má nějaký podíl v nějaké firmě, metoda vrátí dynamicky alokovanou instanci třídy CIterator, 
     * která obsahuje seznam všech firem, kde má zadaný majitel nějaký podíl. 
     * Po zpracování výsledku volající uvolní předanou instanci CIterator voláním delete.
     */
    CEntity * Owner = Owners->Search(oName, oAddr);
    if ((Owner == NULL)) {
        return NULL;
    }
    if ((Owner->GetLinksCount() == 0)) {
        return NULL;
    }
    CIterator * it = new CIterator;
    for (int i = 0; i < Owner->GetLinksCount(); i++) {
        it->AddEntity(Owner->m_Links[i]);
    }
    return it;
}
 
CIterator * CCompanyIndex::SearchCompany(const string & cName,
        const string & cAddr) const {
    /*Metoda SearchOwner (oName, oAddr) zjistí seznam všech firem, ve kterých má zadaný majitel podíl. 
     * Pokud zadaný majitel nemá podíl v žádné firmě, metoda vrátí návratovou hodnotu NULL. 
     * Pokud zadaný majitel má nějaký podíl v nějaké firmě, metoda vrátí dynamicky alokovanou instanci třídy CIterator, 
     * která obsahuje seznam všech firem, kde má zadaný majitel nějaký podíl. 
     * Po zpracování výsledku volající uvolní předanou instanci CIterator voláním delete.
     */
    CEntity * Company = Companies->Search(cName, cAddr);
    if ((Company == NULL)) {
        return NULL;
    }
    if ((Company->GetLinksCount() == 0)) {
        return NULL;
    }
    CIterator * it = new CIterator;
    for (int i = 0; i < Company->GetLinksCount(); i++) {
        it->AddEntity(Company->m_Links[i]);
    }
    return it;
}
 
 
 
 
#ifndef __PROGTEST__
 
string randomString(int seed)
{
    int len = seed % 25 + 5;
    string retValue = "";
    for (int i = 0; i < len; i++)
        retValue += (char)((i*seed + (seed+i)*(seed-i) + i) % 78 + 48);
    return retValue;        
}
 
void  showResults ( CIterator * it )
{
    if (it == NULL)
        cout << "NULL" << endl;
    else
        while ( ! it -> AtEnd () )
        {
            cout << it -> Name ();
            cout<< it -> Address () << endl;
            it -> Next ();
        }
}
 
int main()
{
 
    CIterator * it;
    bool        status=false;
    CCompanyIndex  b1;
    status = b1 . Add ( "Smith", "Oak road", "ACME, Ltd.", "One ACME road" );
    // status = true
    status = b1 . Add ( "Brown", "Second street", "ACME, Ltd.", "Mountain road" );
    // status = true
    status = b1 . Add ( "Hacker", "5-th avenue", "Forks and Knives, Ltd.", "Cutlery avenue" );
    // status = true
    status = b1 . Add ( "Hacker", "7-th avenue", "Child toys, Inc.", "Red light district" );
    // status = true
    status = b1 . Add ( "Smith", "Oak road", "ACME, Ltd.", "Mountain road" );
    // status = true
    status = b1 . Add ( "Hacker", "5-th avenue", "ACME, Ltd.", "One ACME road" );
    // status = true
    status = b1 . Add ( "Hacker", "7-th avenue", "ACME, Ltd.", "Mountain road" );
    // status = true
 
    for (int i = 0; i < 5000; i++)
        b1.Add(randomString(i+545), randomString(i+327), randomString(i+248), randomString(i+532));
 
    for (int i = 0; i < 1238; i++)
        b1.Add(randomString(i+123), randomString(i+584), randomString(i+338), randomString(i+225));
 
    for (int i = 0; i < 300; i++)
        b1.Add("Fred", "CubeGarden", randomString(i+338), randomString(i+225));
 
    it = b1 . SearchOwner ( "Fred", "CubeGarden" );
    showResults ( it );
 
    it = b1 . SearchOwner ( "Brown", "Second street" );
    showResults ( it );
    /*
    ----8<----8<----8<----8<----
    ACME, Ltd., Mountain road
    ----8<----8<----8<----8<----
    */
    delete it;
    it = b1 . SearchOwner ( "Hacker", "Oak road" );
    showResults ( it );
 
    // it = NULL
    it = b1 . SearchOwner ( "Hacker", "7-th avenue" );
    showResults ( it );
    /*
    ----8<----8<----8<----8<----
    Child toys, Inc., Red light district
    ACME, Ltd., Mountain road
    ----8<----8<----8<----8<----
    */
    delete it;
    it = b1 . SearchCompany ( "ACME, Ltd.", "Mountain road" );
    showResults ( it );
    /*
    ----8<----8<----8<----8<----
    Hacker, 7-th avenue
    Brown, Second street
    Smith, Oak road
    ----8<----8<----8<----8<----
    */
    delete it;
    it = b1 . SearchCompany ( "Child toys, Inc.", "Mountain road" );
    showResults ( it );
    // it = NULL
    status = b1 . Del ( "Smith", "Oak road", "Child toys, Inc.", "Red light district" );
    // status = false
    status = b1 . Del ( "Smith", "Oak road", "ACME, Ltd.", "Mountain road" );
    // status = true
    it = b1 . SearchOwner ( "Smith", "Oak road" );
    showResults ( it );
    /*
    ----8<----8<----8<----8<----
    ACME, Ltd., One ACME road
    ----8<----8<----8<----8<----
    */
    delete it;
    status = b1 . Add ( "Smith", "Oak road", "ACME, Ltd.", "One ACME road" );
    // status = false
 
    return 0;
}
 
#endif /*__PROGTEST__*/