对于AF、RI以及Rep exposure的心得体会（复习笔记一）

对于AF、RI以及Rep exposure的心得体会（复习笔记一）
一、A与R
先介绍两个空间：
R： 表示值（rep值）的空间由实际实现实体的值组成。ADT将作为单个对象实现，但更常见的是需要一个小的对象网络，因此其值通常相当复杂。

A： 抽象值的空间由类型设计为支持的值组成。它们是柏拉图式的实体，不存在如前所述，但它们是我们希望将抽象类型的元素视为该类型的客户机的方式。

对于这两个空间，通俗易懂一点的讲，R为开发者所使用的空间，而A是客户所看到的空间。分别对应了代码端以及实际对象。

引入一个规约进行举例：

 In a Store, there are some kinds of items to sell. Each item has a price.
 * 
 * However, there are some special offers, and a special offer consists of one
 * or more different kinds of items with a sale price.
 * 
 * You are given the each item's price, a set of special offers, and the number
 * we need to buy for each item. The job is to output the lowest price you have
 * to pay for exactly certain items as given, where you could make optimal use
 * of the special offers.
 * 
 * Each special offer is represented in the form of an array, the last number
 * represents the price you need to pay for this special offer, other numbers
 * represents how many specific items you could get if you buy this offer.
 * 
 * You could use any of special offers as many times as you want.
 * 
 * Example 1:
 * 
 * Input: [2,5], [[3,0,5],[1,2,10]], [3,2] Output: 14
 * 
 * Explanation:
 * 
 * There are two kinds of items, A and B. Their prices are $2 and $5
 * respectively.
 * 
 * In special offer 1, you can pay $5 for 3A and 0B
 * 
 * In special offer 2, you can pay $10 for 1A and 2B.
 * 
 * You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer
 * #2), and $4 for 2A.
 * 
 * Example 2:
 * 
 * Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] Output: 11
 * 
 * Explanation:
 * 
 * The price of A is $2, and $3 for B, $4 for C.
 * 
 * You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
 * 
 * You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer
 * #1), and $3 for 1B, $4 for 1C.
 * 
 * You cannot add more items, though only $9 for 2A ,2B and 1C.
 * 
 * 
 * Note:
 * 
 * 1. There are at most 6 kinds of items, 100 special offers.
 * 
 * 2. For each item, you need to buy at most 6 of them.
 * 
 * 3. You are not allowed to buy more items than you want, even if that would
 * lower the overall price.

在这其中，显而易见的是用户所能看到的空间。也就是实体对象：购买商品的个数，购买商品的种类，以及购买商品的特惠套餐，以及顾客的需求数目等等。这也是我们的A空间。
而这个空间是程序员所不能写入代码的空间，因此就需要一个R空间与它进行映射，从而形成了我们的代码，也就是我们的数据结构，也就是R空间。
如下面代码所示，函数传入的三个参数就分别对应了我们想要看到的三种A空间元素：商品种类价格，商品特惠套餐以及用户所需数目。

public class LowestPrice {

	public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
		return shopping(price, special, needs);
	}

	public int shopping(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
		try {
			if(price.size() > 6) {
				throw new RIException("输入的price多于6种，不符合要求");
			}
			if(special.size() > 100) {
				throw new RIException("输入special多余100种，不符合要求");
			}
			if(needs.size()!=price.size()) {
				throw new RIException("输入的price与nends关系不符合输入要求,种类数目不一样");
			}
		}catch(RIException ex) {
			ex.printStackTrace(System.out);
			return -1;
		}
		int j = 0, res = dot(needs, price);
		if(res == 0) {
			return 0;
		}
		for (List<Integer> s : special) {
			List<Integer> clone = new ArrayList<>(needs);
			for (j = 0; j < needs.size(); j++) {
				int diff = clone.get(j) - s.get(j);
				if (diff < 0)
					break;
				clone.set(j, diff);
			}
			if (j == needs.size())
				res = Math.min(res, s.get(j) + shopping(price, special, clone));
		}
		return res;
	}

	public int dot(List<Integer> a, List<Integer> b) {
		int sum = 0;
		for (int i = 0; i < a.size(); i++) {
			sum += a.get(i) * b.get(i);
		}
		return sum;
	}
}

二、AF
AF又叫抽象函数。
抽象函数：R和A之间映射关系的函数，即如何去解释R中的每一个值为A中的每一个值。
AF : R → A
AF：满射、非单射、未必双射→R中的部分值并非合法的，在A中无映射值。
先不谈AF的映射合法性，从上面的例子来看，AF也就是从List price, List<List> special, List needs向商品种类价格，商品特惠套餐以及用户所需数目的一组一一映射。
从而撰写AF：

		/**
		 * Abstraction function：
		 * price:商品各个种类及其价格，其中种类是key，而价格是value
		 * special:商品的各种优惠套餐，每个数组的前n（n为商品种类）个
		 * 			为商品个数，第n+1个为套餐价格
		 * needs:分别为每种商品的客户所需数目
		 */

三、RI
RI：将rep值映射到布尔值的rep不变量
RI : R → boolean
对于代表值r，RI（r）是真的，如果且仅当r由AF映射
换句话说，RI告诉我们给定的rep值是否格式良好；或者，可以将RI看作一个集合：它是定义AF的rep值的子集。

总的来说，可以把RI看成一个描述合法化的不变量，即描述AF中所合法的东西。回归上面所说的A空间，RI就是去除了A空间中的不合法化的对象，并让程序员有所实现。
因此，我们根据规约中对于合法性要求的一部分，对于RI进行撰写，首先看规约中对于合法性的要求：

/** 
* Note:
 * 
 * 1. There are at most 6 kinds of items, 100 special offers.
 * 
 * 2. For each item, you need to buy at most 6 of them.
 * 
 * 3. You are not allowed to buy more items than you want, even if that would
 * lower the overall price.
 * /

因此我们得知了对于传入参数List price, List<List> special, List needs的要求，撰写RI：

		/**
		 * Representation invariant：	
		 * price的元素个数多余6个；
		 * special的元素个数少于等于100个
		 * needs中的元素不能大于6
		 */

并在代码中进行相应的实现与检查：

try {
			if(price.size() > 6) {
				throw new RIException("输入的price多于6种，不符合要求");
			}
			if(special.size() > 100) {
				throw new RIException("输入special多余100种，不符合要求");
			}
			if(needs.size()!=price.size()) {
				throw new RIException("输入的price与nends关系不符合输入要求,
										种类数目不一样");
			}
			for(int i = 0;i<needs.size();i++) {
				if(needs.get(i) > 6) {
					throw new RIException("买的商品数目过多");
				}
			}
		}catch(RIException ex) {
			ex.printStackTrace(System.out);
			return -1;
		}

四、Documenting rep exposure safety argument
表示泄漏的安全声明。
这是一个注释，它检查rep的每个部分，查看处理该部分rep的代码（特别是有关参数和来自客户机的返回值的代码，因为这是rep公开发生的地方），并给出代码不公开rep的原因。
给出理由，证明代码并未对外泄露其内部表示——自证清白。