Найти партнера по танцам: максимально 10 пунктов.
Нужно построить эффективную систему регистрации, которая будет регистрировать одиночных танцоров и присутствующих для них подходящих партнеров.
Необходимо 2 регистра: в одном пары, которые уже танцуют вместе, а другой – танцоры, которые еще не нашли себе пару (одиночки). Необходимо создать функцию регистрации партнеров для одиночных танцоров.
При регистрации нового танцора ему ищется подходящий партнер из регистра одиночек (по очереди). При поиске рассчитывается, что мужчина должен быть выше, чем женщина.
И Так:
- Если регистрируется мужчина, то ему ищется женщина, которая ниже его, но самая высокая в очереди.
- Если регистрируется женщина, то ей ищется мужчина, который выше ее, но самый короткий в очереди.
- если в очереди нету подходящих партнеров, то человека добавляют в очередь.
Требования:
- каждый танцор характеризуется уникальным идентификатором, полом( true - мужчина, false - женщина) и ростом.
-Если партнер находится, то он удаляется с очереди и возвращаются данные пары. Если партнер не нашелся, то танцора добавляют в очередь и возвращается 0.
-Сложность регистрации – O(lg n), где n –это количество танцоров в очереди и это реализовано в бинарном дереве поиска
- Бинарное дерево поиска нужно реализировать самостоятельно на основе примитивных данных базы
-10 пунктов : если используется сбалансированное дерево
-8 пунктов: если используется не сбалансированное.
Советы:
-дерево поиска реализовать в отдельном классе
Projekt name: HW01
Package name: dancers
Interface:
--------------------------------------------------------------------------------------------------------
package dancers;
/**
* API specification for the objects
* representing various dancers.
*/
public interface IDancer {
public int getID();
public boolean isMale();
public int getHeight();
}
----------------------------------------------------------------------------------------------------------------
package dancers;
import java. util. AbstractMap. SimpleEntry;
import java. util. List;
/**
* API specification for the
* functional call to be tested.
* IMPORTANT! You *HAVE* to implement
* the class named Dancers implementing
* this interface in your solution.
*/
public interface IDancers {
public SimpleEntry<IDancer, IDancer> findPartnerFor(IDancer d)
throws IllegalArgumentException;
/*
* Returns waiting list as an array (both men and women)
* Ordered shortest --> longest
* If man and woman are having the same height,
* then ordering should be man, woman
*/
public List<IDancer> returnWaitingList();
}
-----------------------------------------------------------------------------------------
package dancers;
import java. util. AbstractMap. SimpleEntry;
import java. util. List;
public class Dancers implements IDancers {
@Override
public SimpleEntry<IDancer, IDancer> findPartnerFor(IDancer d)
throws IllegalArgumentException {
// TODO Auto-generated method stub
return null;
}
@Override
public List<IDancer> returnWaitingList() {
// TODO Auto-generated method stub
return null;
}
}
