1. Implement a new version of the Sparse Life Grid ADT from Chapter 4 to use a sorted list and the binary search to locate the occupied cells.
2. A colormap is a lookup table or color palette containing a limited set of colors. Early color graphics cards could only display up to 256 unique colors at one time. Colormaps were used to specify which 256 colors should be used to display color images on such a device. Software applications were responsible for mapping each color in the image that was to be displayed to a color in the limited color set specified by the colormap. We can define a Colormap ADT for storing a limited set of colors and for use in mapping one of the 16.7+ million colors possible in the discrete RGB color space to a color in the colormap. Given the description below of various operations, implement the Colormap ADT using a 1-D array structure.
* ColorMap( k ): Creates a new empty colormap that is capable of storing up to k colors.
* length (): Returns the number of colors currently stored in the colormap.
* contains ( color ): Determines if the given color is contained in the colormap.
* add( color ): Adds the given color to the colormap. Only one instance of each color can be added to the colormap. In addition, a color cannot be added to a full colormap.
* remove ( color ): Removes the given color from the colormap. The color must be contained in the colormap in order to be removed.
* map( color ): Maps the given color to an entry in the colormap and returns that color. A common approach is to map the color to its nearest neighbor in the colormap. The nearest neighbor of a color is the entry in the colormap that has the minimum Euclidean distance squared between the two colors. If there is more than one nearest neighbor in the colormap, only one is returned. In addition, the colormap must contain at least one color in order to perform the mapping operation.
* iterator (): Creates and returns an iterator object that can be used to iterate over the colors in the colormap.