I have a class "City"
public final class City {
private final String name;
private final String state;
private final int population;
public City(String name, String state, int population) {
this.name = name;
this.state = state;
this.population = population;
}
public String getName() {
return name;
}
public String getState() {
return state;
}
public int getPopulation() {
return population;
}
@Override
public String toString() {
return "City [name=" name ", state=" state ", population=" population "]";
}
}
And a class that implements Observable (not needed for this). This observable class holds an array list "List cityList" that has the data for all the cities that have been reported.
My new class, "TopFiveCities" is supposed to:
"implement a getter method getTopFive() returning a list with the five top cities (in terms of population) received. The list is sorted from higher to lower numbers. The returned list must be a copy of the list kept by the observer"
Aside from just getting the top 5 list, I also need to know how to make a copy of that list from the observer
This is what I have:
public class TopFiveCities
implements Observer {
// THIS ALSO DOESN'T WORK UNLESS THE LIST IS STATIC
// SO HOW CAN I MAKE A COPY OF THE LIST FROM OBSERVER?
private List<City> list = new ArrayList<>(CensusOffice.cityList);
public List<City> getTopFive() {
Collections.sort(list, new Comparator<City>() {
@Override
public int compare(City o1, City o2) {
return Integer.compare(o1.getPopulation(), o2.getPopulation());
}
});
return list;
}
public void update(Observable observable) {
if (!(observable instanceof Observable)) {
throw new IllegalArgumentException();
}
}
}
With this, when one of the sample outputs should be: "City [name=Chicago, state=IL, population=2746388]" I just receive a list of ALL of the cities sorted by population from LOWEST to HIGHEST. Any help?
CodePudding user response：
int order = requestedOrder.equals("asc") ? 1 : -1;
Collections.sort(list, new Comparator<CustomObj>() {
public int compare(CustomObj first, CustomObj scnd) {
return first.getComparableParam().compareTo(scnd.getComparableParam()) * order;
}
});
I just copied and passed this code block from recommended stackover page in the comment. Of you want ascending order simply change it. In your code order will be -1.
Simply you need to multiply by -1.
return Integer.compare(o1.getPopulation(), o2.getPopulation()) * -1;
After this you can sublist it.
You keep the list as global variable it can be reached from update method but it does not change if class is singleton except for update method. Your update method can change it by notifying
In update method you can simply clear and add new list by list.addAll
CodePudding user response：
You can just use a Stream, use a Comparator to sort the stream, limit the number of element and convert the elements to a new list:
List<City> top5citiesByPopulation = cities.stream()
.sorted(Comparator.comparing(City::getPopulation).reversed())
.limit(5)
.collect(Collectors.toList());
CodePudding user response：
Since this is a schoolwork assignment, I’ll describe the pieces but let you assemble them into final code.
I have a class "City"
You could more briefly define that class as a record.
City ( String name, String state, int population ) {}
holds an array list "List cityList"
List < City > cities = new ArrayList<>();
getting the top 5 list
Sort the list by using a reverse comparator. You can make a comparator for sorting by using a method reference for the accessor “getter” method. But be aware that records do not use the word “get” by default as their accessor, they use simply the name of the property.
cities.sort( Comparator.comparing( City :: population ).reversed() ) ;
For an unmodifiable list, call List.of or List.copyOf.
List#subset gives you a list with some of the elements of the original. But beware: the resulting list is based on a view of the original list. The subset is not separate and independent. To get a separate list, pass to List.copyOf or pass to the constructor of another List implementation.
List< City > topFivePop = List.copyOf( subset ) ;
CodePudding user response：
This problem doesn't require sorting the whole given list, which will have a time complexity of O(n log n).
Basically, the task is somewhat similar to finding the maximum element in the list that can be done in O(n) time with a single pass through the given list.
The most suitable approach for this problem is a partial sorting, and the best performance that could be achieved is the middle-ground between O(n) and O(n log n).
In order to find 5 maximum elements in a list, we can maintain a collection that will store in sorted order up to 5 previously encountered elements with maximum values.
Elements that are lover than the smallest element in the collection will be discarded automatically if the collection is already of size 5. Only new elements with a value higher than the smallest element's value will trigger reordering of this tiny collection. I.e. the data will be sorted partially instead of sorting the whole data set.
In the implementation below for as collection that will store 5 max elements, I've chosen a PriorityQueue.
According to the documentation it's methods have the following time complexity.
this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
I.e. adding of a new element and removing the first element both will perform in logarithmic time, and accessing the smallest value in the queue with the method element() with done in O(1) time (almost immediately).
The PriorityQueue is encapsulated inside a generic class, which constructor expects as parameters a Comparator<T> and a desired maximum size of the queue (i.e. a number of max elements that needs to be found).
The queue itself doesn't exposed to the outside classes. Method addItem() processing the given element and getFirstN returns a sorted immutable list.
Comparator in the code below is implemented using the static method comparingInt(). You could also implement Comparator in a "classical way" (pre-Java 8) by providing the behavior for it's abstract method compare() either by using a lambda expression or within an anonymous inner class.
public class FirstN<T> {
private final Queue<T> queue;
private final Comparator<T> comparator;
private final int capacity;
public FirstN(Comparator<T> comparator, int capacity) {
this.queue = new PriorityQueue<>(comparator);
this.comparator = comparator;
this.capacity = capacity;
}
public boolean addItem(T item) {
if (capacity == queue.size() && comparator.compare(item, queue.element()) <= 0) {
return false; // queue is full and the given item is smaller than the lowerest element in the queue
}
if (capacity == queue.size() && comparator.compare(item, queue.element()) > 0) {
queue.remove(); // removing the first element if it's smaller than the given item
}
return queue.add(item); // adding the given item
}
public List<T> getFirstN() {
List<T> result = new ArrayList<>(queue);
result.sort(comparator.reversed());
return List.copyOf(result); // immutable list
}
}
main()
public static void main(String[] args) {
List<City> cities = List.of(
new City("Austin", "Texas", 1028225),
new City("Los Angeles", "California", 3985516),
new City("San Diego", "California", 1429653),
new City("Houston", "Texas", 2325353),
new City("Phoenix", "Arizona", 1759943),
new City("New York City", "New York", 8177025),
new City("San Antonio", "Texas", 1598964),
new City("Philadelphia", "Pennsylvania", 1585480),
new City("San Diego", "California", 1429653),
new City("Chicago", "Illinois", 2671635),
new City("Dallas", "Texas", 1348886));
FirstN<City> top5Cities =
new FirstN<>(Comparator.comparingInt(City::getPopulation), 5);
for (City next: cities) {
top5Cities.addItem(next);
}
List<City> result = top5Cities.getFirstN(); // contains 5 biggest US cities
result.forEach(System.out::println); // printing the result
}
Output
City [name=New York City, state=New York, population=8177025]
City [name=Los Angeles, state=California, population=3985516]
City [name=Chicago, state=Illinois, population=2671635]
City [name=Houston, state=Texas, population=2325353]
City [name=Phoenix, state=Arizona, population=1759943]