Container ClassesSelect Container ClassJava ContainersJava ListJava SetJava MapC++ ContainerC++ VectorC++ ListC++ Vector of ObjectsCollision DetectionLaw of ReflectionCollision between two CirclesCollision between Circle and SquareKnown ProblemCreate New C++ ContainersBinary Search TreeTraverse TreeYHL Container Class 1ECE 462Object-Oriented Programmingusing C++ and JavaContainer ClassesYung-Hsiang [email protected] Container Class 2Why Container Classes?• Many programs require arrays, vectors, lists, queues, stacks, sets ... to store information.• Both C++ and Java provide container classes that automatically manage memory: allocate additional memory when more elements are added.• The supported container classes greatly reduce the amount of code needed by programmers and improve productivity.• Container classes and OOP are closely related: – a container can hold objects of derived classes– polymorphism properly invokes the correct methodsYHL Container Class 3Container Class (For Code Reuse)• A container needs to be able to hold items of different types (i.e. classes). Examples– list of strings, integers, floating points, student objects– queues of customer objects, car objects– maps: name → address, student ID → name, course title → classroom• C++ standard template library (STL) and Java container classes provide such functionality.YHL Container Class 4Select Container Class• random or sequential accesses?• allow unique or duplicate items?• O(1) or O(N) for array-like access (using [index])• efficient insert / delete?–front– end–middle• Java containers cannot store primitive types (int, char, float ...) and can store objects only. C++ containers can store primitives.YHL Container Class 5Efficiency O(1)O(N)O(N)insert/delete in middleO(1)O(1)+O(1)+insert/delete at endO(1)O(1)+O(N)insert/delete at frontO(N)O(1)O(1)array-like accesslistdequevectoroperationN: current number of itemsYHL Container Class 6Java ContainersYHL Container Class 7Java ListYHL Container Class 8YHL Container Class 9Interface and Class• A Java interface serves as an abstract class and cannot be instantiated. • An interface can be implemented by classes.• Typically, an interface is a common base for several related classes, for example, interface List as the base of ArrayList, LinkedList, Stack, and Vector.YHL Container Class 10YHL Container Class 11YHL Container Class 12YHL Container Class 13YHL Container Class 14YHL Container Class 15Java SetYHL Container Class 16YHL Container Class 17YHL Container Class 18no duplicate element in Setelements sortedYHL Container Class 19Java MapYHL Container Class 20Map (Hash Table)• array: integer → element (object)• map: key (object, integer, or string ...) → value (object)•example:–name → phone number– student ID → department– city name → zip code• Keys must be unique and do not have to be continuous (unlike array indexes). Values do not have to be unique.YHL Container Class 21Java MapHistogram of WordsYHL Container Class 22YHL Container Class 23YHL Container Class 24YHL Container Class 25YHL Container Class 26YHL Container Class 27YHL Container Class 28C++ Container(Standard Template Library)YHL Container Class 29C++ VectorYHL Container Class 30YHL Container Class 31YHL Container Class 32C++ Vectorcontiguous memory • efficient access (array-like [index])• efficient insert / delete at the end (allocate more memory occasionally)• inefficient insert / delete at the front (allocate memory for every insertion)• automatic expand / shrink allocated memory (allocate more than necessary to reduce allocation / release / copy overhead)• occasional copying of the whole vectorYHL Container Class 33C++ Iteratorpointer to traverse a vector or other STL (standard template library) containervector<int> v;cout << "\nvector size is: " << v.size() << endl;vector<int>::iterator p = v.begin();while ( p != v.end() ) {cout << *p << " "; p++;}YHL Container Class 34C++ ListYHL Container Class 35YHL Container Class 36YHL Container Class 37YHL Container Class 38YHL Container Class 39C++ Vector of ObjectsYHL Container Class 40YHL Container Class 41YHL Container Class 42YHL Container Class 43YHL Container Class 44YHL Container Class 45Self TestYHL Collision Detection 1ECE 462Object-Oriented Programmingusing C++ and JavaCollision DetectionYung-Hsiang [email protected] Collision Detection 2Collision DetectionAlmost every interactive game requires collision detection: a bullet hits a player, an airplane lands on a runway, a ball hits a brick, and a Tetrix piece hits a wallYHL Collision Detection 3Law of Reflection• N: normal vector• I: incident vector• R: reflection vector• α : angle between N and I• β : angle between N and R• Law of ReflectionNIRαβα = βYHL Collision Detection 4Calculate R• Suppose N, I, and R are unit vectors, i.e. |N| = |I| = |R| = 1• R + (- I) = 2 (N ⋅ (- I)) N⇒ The sum of R and (-I) has the same direction as N⇒ The length is twice the inner product of N and (-I).R = 2 (N ⋅ (- I)) N + I = - 2 (N ⋅ I) N + IN-IRαβYHL Collision Detection 5Collision between two CirclesN = (x1, y1) - (x2, y2)C1 is moving.(x1, y1)(x2, y2)IRYHL Collision Detection 6Collision between Circle and Square• approximate by using two squares• if the bounding square of the circle intersects with the square ⇒ collision• if the intersection is tall ⇒ collide horizontally(x1, y1)(x2, y2)IRNYHL Collision Detection 7YHL Collision Detection 8YHL Collision Detection 9YHL Collision Detection 10YHL Collision Detection 11YHL Collision Detection 12YHL Collision Detection 13YHL Collision Detection 14YHL Collision Detection 15YHL Collision Detection 16YHL Collision Detection 17YHL Collision Detection 18YHL Collision Detection 19YHL Collision Detection 20YHL Collision Detection 21YHL Collision Detection 22YHL Collision Detection 23YHL Collision Detection 24YHL Collision Detection 25YHL Collision Detection 26YHL Collision Detection 27Known Problem 1• When the ball moves towards the gap between two bricks, brick 1 may be eliminated first even though the ball would actually hit brick 2 first.• This can happen because – brick 1 precedes brick 2 in the brick list so brick 1 is checked first– the ball moves in discrete steps (one pixel length each time).• Solution: ignore. This is not easily noticeable when the ball moves fast.1 2YHL Collision Detection 28Known Problem 2• Once the ball