Iterator pattern

Posted on 2015-04-17 | In Design Pattern | Comments:

Iterator pattern

假设有两个餐厅，它们各自的菜单组织形式不同。

public class MenuItem {
	String name;
	String description;
	boolean vegetarian;
	double price;
 
	public MenuItem(String name, 
	                String description, 
	                boolean vegetarian, 
	                double price) 
	{
		this.name = name;
		this.description = description;
		this.vegetarian = vegetarian;
		this.price = price;
	}
  
	public String getName() {
		return name;
	}
  
	public String getDescription() {
		return description;
	}
  
	public double getPrice() {
		return price;
	}
  
	public boolean isVegetarian() {
		return vegetarian;
	}
}

public class PanackeHouseMenue {
	ArrayList menuItems;
	...
}

public class DinerMenu {
	MenuItem[] menuItems;
}

当遍历菜单时，我们需要提供两个方法遍历两种菜单，使系统变得复杂化。如果需要增加一种新的菜单，需要修改前面的很多代码，造成难以维护。

定义迭代器模式

这里我们可以把遍历封装起来，让每个类提供相同的方法遍历它自己的元素。外部客户只管调用这些方法来遍历，而不必直到内部是如何实现的。且由于所有类都提供同样的遍历方法，降低的复杂性，使得系统容易扩展和修改。

迭代其模式提供一种同一的方法顺序访问一个聚合对象中的各个元素，而由不暴露其内部的表示。把遍历的任务交给迭代器，而不是聚合对象上，这样简化了聚合对象的接口和实现，也满足了单一责任原则：一个类应该只负责一个职责，并只有一个引起变化的原因。

Design_pattern_iterator_1

public interface Iterator {
	boolean hasNext();
	Object next();
}

public class DinerMenuIterator implements Iterator {
	MenuItem[] items;
	int position = 0;
 
	public DinerMenuIterator(MenuItem[] items) {
		this.items = items;
	}
 
	public Object next() {
		MenuItem menuItem = items[position];
		position = position + 1;
		return menuItem;
	}
 
	public boolean hasNext() {
		if (position >= items.length || items[position] == null) {
			return false;
		} else {
			return true;
		}
	}
}

public class PancakeHouseMenuIterator implements Iterator {
	ArrayList items;
	int position = 0;
 
	public PancakeHouseMenuIterator(ArrayList items) {
		this.items = items;
	}
 
	public Object next() {
		Object object = items.get(position);
		position = position + 1;
		return object;
	}
 
	public boolean hasNext() {
		if (position >= items.size()) {
			return false;
		} else {
			return true;
		}
	}
}

public class DinerMenu implements Menu {
	static final int MAX_ITEMS = 6;
	int numberOfItems = 0;
	MenuItem[] menuItems;
  
	public DinerMenu() {
		menuItems = new MenuItem[MAX_ITEMS];
 
		addItem("Vegetarian BLT",
			"(Fakin') Bacon with lettuce & tomato on whole wheat", true, 2.99);
		addItem("BLT",
			"Bacon with lettuce & tomato on whole wheat", false, 2.99);
		addItem("Soup of the day",
			"Soup of the day, with a side of potato salad", false, 3.29);
		addItem("Hotdog",
			"A hot dog, with saurkraut, relish, onions, topped with cheese",
			false, 3.05);
		addItem("Steamed Veggies and Brown Rice",
			"Steamed vegetables over brown rice", true, 3.99);
		addItem("Pasta",
			"Spaghetti with Marinara Sauce, and a slice of sourdough bread",
			true, 3.89);
	}
  
	public void addItem(String name, String description, 
	                     boolean vegetarian, double price) 
	{
		MenuItem menuItem = new MenuItem(name, description, vegetarian, price);
		if (numberOfItems >= MAX_ITEMS) {
			System.err.println("Sorry, menu is full!  Can't add item to menu");
		} else {
			menuItems[numberOfItems] = menuItem;
			numberOfItems = numberOfItems + 1;
		}
	}
 
	public MenuItem[] getMenuItems() {
		return menuItems;
	}
  
	public Iterator createIterator() {
		return new DinerMenuIterator(menuItems);
	}
 
	// other menu methods here
}

public class PancakeHouseMenu implements Menu {
	ArrayList menuItems;
 
	public PancakeHouseMenu() {
		menuItems = new ArrayList();
    
		addItem("K&B's Pancake Breakfast", 
			"Pancakes with scrambled eggs, and toast", 
			true,
			2.99);
 
		addItem("Regular Pancake Breakfast", 
			"Pancakes with fried eggs, sausage", 
			false,
			2.99);
 
		addItem("Blueberry Pancakes",
			"Pancakes made with fresh blueberries",
			true,
			3.49);
 
		addItem("Waffles",
			"Waffles, with your choice of blueberries or strawberries",
			true,
			3.59);
	}

	public void addItem(String name, String description,
	                    boolean vegetarian, double price)
	{
		MenuItem menuItem = new MenuItem(name, description, vegetarian, price);
		menuItems.add(menuItem);
	}
 
	public ArrayList getMenuItems() {
		return menuItems;
	}
  
	public Iterator createIterator() {
		return new PancakeHouseMenuIterator(menuItems);
	}
  
	public String toString() {
		return "Objectville Pancake House Menu";
	}

	// other menu methods here
}

public class Waitress {
	PancakeHouseMenu pancakeHouseMenu;
	DinerMenu dinerMenu;
 
	public Waitress(PancakeHouseMenu pancakeHouseMenu, DinerMenu dinerMenu) {
		this.pancakeHouseMenu = pancakeHouseMenu;
		this.dinerMenu = dinerMenu;
	}
 
	public void printMenu() {
		Iterator pancakeIterator = pancakeHouseMenu.createIterator();
		Iterator dinerIterator = dinerMenu.createIterator();

		System.out.println("MENU\n----\nBREAKFAST");
		printMenu(pancakeIterator);
		System.out.println("\nLUNCH");
		printMenu(dinerIterator);
	}
 
	private void printMenu(Iterator iterator) {
		while (iterator.hasNext()) {
			MenuItem menuItem = (MenuItem)iterator.next();
			System.out.print(menuItem.getName() + ", ");
			System.out.print(menuItem.getPrice() + " -- ");
			System.out.println(menuItem.getDescription());
		}
	}
 
	public void printVegetarianMenu() {
		printVegetarianMenu(pancakeHouseMenu.createIterator());
		printVegetarianMenu(dinerMenu.createIterator());
	}
 
	public boolean isItemVegetarian(String name) {
		Iterator breakfastIterator = pancakeHouseMenu.createIterator();
		if (isVegetarian(name, breakfastIterator)) {
			return true;
		}
		Iterator dinnerIterator = dinerMenu.createIterator();
		if (isVegetarian(name, dinnerIterator)) {
			return true;
		}
		return false;
	}


	private void printVegetarianMenu(Iterator iterator) {
		while (iterator.hasNext()) {
			MenuItem menuItem = (MenuItem)iterator.next();
			if (menuItem.isVegetarian()) {
				System.out.print(menuItem.getName());
				System.out.println("\t\t" + menuItem.getPrice());
				System.out.println("\t" + menuItem.getDescription());
			}
		}
	}

	private boolean isVegetarian(String name, Iterator iterator) {
		while (iterator.hasNext()) {
			MenuItem menuItem = (MenuItem)iterator.next();
			if (menuItem.getName().equals(name)) {
				if (menuItem.isVegetarian()) {
					return true;
				}
			}
		}
		return false;
	}

通过迭代器，我们可以很容易的新增菜单：

public class CafeMenu implements Menu {
	Hashtable menuItems = new Hashtable();
  
	public CafeMenu() {
		addItem("Veggie Burger and Air Fries",
			"Veggie burger on a whole wheat bun, lettuce, tomato, and fries",
			true, 3.99);
		addItem("Soup of the day",
			"A cup of the soup of the day, with a side salad",
			false, 3.69);
		addItem("Burrito",
			"A large burrito, with whole pinto beans, salsa, guacamole",
			true, 4.29);
	}
 
	public void addItem(String name, String description, 
	                     boolean vegetarian, double price) 
	{
		MenuItem menuItem = new MenuItem(name, description, vegetarian, price);
		menuItems.put(menuItem.getName(), menuItem);
	}
 
	public Hashtable getItems() {
		return menuItems;
	}
  
	public Iterator createIterator() {
		return menuItems.values().iterator();
	}
}

public class Waitress {
	Menu pancakeHouseMenu;
	Menu dinerMenu;
	Menu cafeMenu;
 
	public Waitress(Menu pancakeHouseMenu, Menu dinerMenu, Menu cafeMenu) {
		this.pancakeHouseMenu = pancakeHouseMenu;
		this.dinerMenu = dinerMenu;
		this.cafeMenu = cafeMenu;
	}
 
	public void printMenu() {
		Iterator pancakeIterator = pancakeHouseMenu.createIterator();
		Iterator dinerIterator = dinerMenu.createIterator();
		Iterator cafeIterator = cafeMenu.createIterator();

		System.out.println("MENU\n----\nBREAKFAST");
		printMenu(pancakeIterator);
		System.out.println("\nLUNCH");
		printMenu(dinerIterator);
		System.out.println("\nDINNER");
		printMenu(cafeIterator);
	}
 
	private void printMenu(Iterator iterator) {
		while (iterator.hasNext()) {
			MenuItem menuItem = (MenuItem)iterator.next();
			System.out.print(menuItem.getName() + ", ");
			System.out.print(menuItem.getPrice() + " -- ");
			System.out.println(menuItem.getDescription());
		}
	}
 
	public void printVegetarianMenu() {
		System.out.println("\nVEGETARIAN MENU\n---------------");
		printVegetarianMenu(pancakeHouseMenu.createIterator());
		printVegetarianMenu(dinerMenu.createIterator());
		printVegetarianMenu(cafeMenu.createIterator());
	}
 
	public boolean isItemVegetarian(String name) {
		Iterator pancakeIterator = pancakeHouseMenu.createIterator();
		if (isVegetarian(name, pancakeIterator)) {
			return true;
		}
		Iterator dinerIterator = dinerMenu.createIterator();
		if (isVegetarian(name, dinerIterator)) {
			return true;
		}
		Iterator cafeIterator = cafeMenu.createIterator();
		if (isVegetarian(name, cafeIterator)) {
			return true;
		}
		return false;
	}


	private void printVegetarianMenu(Iterator iterator) {
		while (iterator.hasNext()) {
			MenuItem menuItem = (MenuItem)iterator.next();
			if (menuItem.isVegetarian()) {
				System.out.print(menuItem.getName() + ", ");
				System.out.print(menuItem.getPrice() + " -- ");
				System.out.println(menuItem.getDescription());
			}
		}
	}

	private boolean isVegetarian(String name, Iterator iterator) {
		while (iterator.hasNext()) {
			MenuItem menuItem = (MenuItem)iterator.next();
			if (menuItem.getName().equals(name)) {
				if (menuItem.isVegetarian()) {
					return true;
				}
			}
		}
		return false;
	}
}

目前在菜单增加时，遍历菜单的方法不需要再修改。但是我们需要单独管理这些菜单，而不是能够讲它们也聚合在一起作为一个单独的聚合对象管理，通过使用基类List可以部分改进该，但是我们仍然无法在菜单里增加子菜单，也就是层级模式。

Design_pattern_iterator_2

Design_pattern_iterator_3

组合模式

这时我们可以使用组合模式解决这个难题：

定义组合模式

组合模式允许我们将组合对象组合成树形结构来表现”整体/部分”层次结构。组合能够让客户以一致的方式处理个别对象以及对象组合。

Design_pattern_iterator_4

Design_pattern_iterator_5

这里我们使用组合设计菜单：

Design_pattern_iterator_6

public abstract class MenuComponent {
   
	public void add(MenuComponent menuComponent) {
		throw new UnsupportedOperationException();
	}
	public void remove(MenuComponent menuComponent) {
		throw new UnsupportedOperationException();
	}
	public MenuComponent getChild(int i) {
		throw new UnsupportedOperationException();
	}
  
	public String getName() {
		throw new UnsupportedOperationException();
	}
	public String getDescription() {
		throw new UnsupportedOperationException();
	}
	public double getPrice() {
		throw new UnsupportedOperationException();
	}
	public boolean isVegetarian() {
		throw new UnsupportedOperationException();
	}
  
	public void print() {
		throw new UnsupportedOperationException();
	}
}

public class MenuItem extends MenuComponent {
	String name;
	String description;
	boolean vegetarian;
	double price;
    
	public MenuItem(String name, 
	                String description, 
	                boolean vegetarian, 
	                double price) 
	{ 
		this.name = name;
		this.description = description;
		this.vegetarian = vegetarian;
		this.price = price;
	}
  
	public String getName() {
		return name;
	}
  
	public String getDescription() {
		return description;
	}
  
	public double getPrice() {
		return price;
	}
  
	public boolean isVegetarian() {
		return vegetarian;
	}
  
	public void print() {
		System.out.print("  " + getName());
		if (isVegetarian()) {
			System.out.print("(v)");
		}
		System.out.println(", " + getPrice());
		System.out.println("     -- " + getDescription());
	}
}

public class Menu extends MenuComponent {
	ArrayList menuComponents = new ArrayList();
	String name;
	String description;
  
	public Menu(String name, String description) {
		this.name = name;
		this.description = description;
	}
 
	public void add(MenuComponent menuComponent) {
		menuComponents.add(menuComponent);
	}
 
	public void remove(MenuComponent menuComponent) {
		menuComponents.remove(menuComponent);
	}
 
	public MenuComponent getChild(int i) {
		return (MenuComponent)menuComponents.get(i);
	}
 
	public String getName() {
		return name;
	}
 
	public String getDescription() {
		return description;
	}
 
	public void print() {
		System.out.print("\n" + getName());
		System.out.println(", " + getDescription());
		System.out.println("---------------------");
  
		Iterator iterator = menuComponents.iterator();
		while (iterator.hasNext()) {
			MenuComponent menuComponent = 
				(MenuComponent)iterator.next();
			menuComponent.print();
		}
	}
}

public class Waitress {
	MenuComponent allMenus;
 
	public Waitress(MenuComponent allMenus) {
		this.allMenus = allMenus;
	}
 
	public void printMenu() {
		allMenus.print();
	}
}

public class MenuTestDrive {
	public static void main(String args[]) {
		MenuComponent pancakeHouseMenu = 
			new Menu("PANCAKE HOUSE MENU", "Breakfast");
		MenuComponent dinerMenu = 
			new Menu("DINER MENU", "Lunch");
		MenuComponent cafeMenu = 
			new Menu("CAFE MENU", "Dinner");
		MenuComponent dessertMenu = 
			new Menu("DESSERT MENU", "Dessert of course!");
		MenuComponent coffeeMenu = new Menu("COFFEE MENU", "Stuff to go with your afternoon coffee");
  
		MenuComponent allMenus = new Menu("ALL MENUS", "All menus combined");
  
		allMenus.add(pancakeHouseMenu);
		allMenus.add(dinerMenu);
		allMenus.add(cafeMenu);
  
		pancakeHouseMenu.add(new MenuItem(
			"K&B's Pancake Breakfast", 
			"Pancakes with scrambled eggs, and toast", 
			true,
			2.99));
		pancakeHouseMenu.add(new MenuItem(
			"Regular Pancake Breakfast", 
			"Pancakes with fried eggs, sausage", 
			false,
			2.99));
		pancakeHouseMenu.add(new MenuItem(
			"Blueberry Pancakes",
			"Pancakes made with fresh blueberries, and blueberry syrup",
			true,
			3.49));
		pancakeHouseMenu.add(new MenuItem(
			"Waffles",
			"Waffles, with your choice of blueberries or strawberries",
			true,
			3.59));

		dinerMenu.add(new MenuItem(
			"Vegetarian BLT",
			"(Fakin') Bacon with lettuce & tomato on whole wheat", 
			true, 
			2.99));
		dinerMenu.add(new MenuItem(
			"BLT",
			"Bacon with lettuce & tomato on whole wheat", 
			false, 
			2.99));
		dinerMenu.add(new MenuItem(
			"Soup of the day",
			"A bowl of the soup of the day, with a side of potato salad", 
			false, 
			3.29));
		dinerMenu.add(new MenuItem(
			"Hotdog",
			"A hot dog, with saurkraut, relish, onions, topped with cheese",
			false, 
			3.05));
		dinerMenu.add(new MenuItem(
			"Steamed Veggies and Brown Rice",
			"Steamed vegetables over brown rice", 
			true, 
			3.99));
 
		dinerMenu.add(new MenuItem(
			"Pasta",
			"Spaghetti with Marinara Sauce, and a slice of sourdough bread",
			true, 
			3.89));
   
		dinerMenu.add(dessertMenu);
  
		dessertMenu.add(new MenuItem(
			"Apple Pie",
			"Apple pie with a flakey crust, topped with vanilla icecream",
			true,
			1.59));
  
		dessertMenu.add(new MenuItem(
			"Cheesecake",
			"Creamy New York cheesecake, with a chocolate graham crust",
			true,
			1.99));
		dessertMenu.add(new MenuItem(
			"Sorbet",
			"A scoop of raspberry and a scoop of lime",
			true,
			1.89));

		cafeMenu.add(new MenuItem(
			"Veggie Burger and Air Fries",
			"Veggie burger on a whole wheat bun, lettuce, tomato, and fries",
			true, 
			3.99));
		cafeMenu.add(new MenuItem(
			"Soup of the day",
			"A cup of the soup of the day, with a side salad",
			false, 
			3.69));
		cafeMenu.add(new MenuItem(
			"Burrito",
			"A large burrito, with whole pinto beans, salsa, guacamole",
			true, 
			4.29));

		cafeMenu.add(coffeeMenu);

		coffeeMenu.add(new MenuItem(
			"Coffee Cake",
			"Crumbly cake topped with cinnamon and walnuts",
			true,
			1.59));
		coffeeMenu.add(new MenuItem(
			"Bagel",
			"Flavors include sesame, poppyseed, cinnamon raisin, pumpkin",
			false,
			0.69));
		coffeeMenu.add(new MenuItem(
			"Biscotti",
			"Three almond or hazelnut biscotti cookies",
			true,
			0.89));
 
		Waitress waitress = new Waitress(allMenus);
   
		waitress.printMenu();
	}
}

组合模式和组合迭代器

递归实现：

public class MenuItem extends MenuComponent {
	// 其他部分不需要改动
 	public Iterator createIterator() {
		return new NullIterator();
	}
}

public class Menu extends MenuComponent {
  	// 其他部分不需要改动
	public Iterator createIterator() {
		return new CompositeIterator(menuComponents.iterator());
	}
}

public class NullIterator implements Iterator {
   
	public Object next() {
		return null;
	}
  
	public boolean hasNext() {
		return false;
	}
   
	public void remove() {
		throw new UnsupportedOperationException();
	}
}

public class CompositeIterator implements Iterator {
	Stack stack = new Stack();
   
	public CompositeIterator(Iterator iterator) {
		stack.push(iterator);
	}
   
	public Object next() {
		if (hasNext()) {
			Iterator iterator = (Iterator) stack.peek();
			MenuComponent component = (MenuComponent) iterator.next();
			if (component instanceof Menu) {
				stack.push(component.createIterator());
			} 
			return component;
		} else {
			return null;
		}
	}
  
	public boolean hasNext() {
		if (stack.empty()) {
			return false;
		} else {
			Iterator iterator = (Iterator) stack.peek();
			if (!iterator.hasNext()) {
				stack.pop();
				return hasNext();
			} else {
				return true;
			}
		}
	}
   
	public void remove() {
		throw new UnsupportedOperationException();
	}
}

Template method pattern

Posted on 2015-03-21 | In Design Pattern | Comments:

模板方法模式

前面的内容都是关于封装的，包括封装对象创建、方法掉有那个、复杂接口等。
这里介绍的模板方法模式同样是用于封装，封装的对象是算法块，使得子类可以任何时候将自己挂进运算里，无需重写算法流程。

模板方法模式在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类中。模板方法使得子类可以在不改变算法结构的情况下，重新插入新的算法实现。

模板就是一个方法，更具体地说，这个方法将算法定义一组步骤，其中的任何步骤都可以是抽象的，由子类负责实现。这样可以确保算法的结构保持不变，同时由子类提供部分实现。

Design_pattern_templatemethod_1

Design_pattern_templatemethod_2

Design_pattern_templatemethod_3

注意到上面的类提供了一个钩子，钩子是一种被声明在抽象类中的方法，但是只有空的或默认的实现。钩子的存在可以让子类有能力对算法的不同点进行挂钩，子类也可以不选择挂钩。

Design_pattern_templatemethod_4

public abstract class CaffeineBeverageWithHook {
 
	void prepareRecipe() {
		boilWater();
		brew();
		pourInCup();
		if (customerWantsCondiments()) {
			addCondiments();
		}
	}
 
	abstract void brew();
 
	abstract void addCondiments();
 
	void boilWater() {
		System.out.println("Boiling water");
	}
 
	void pourInCup() {
		System.out.println("Pouring into cup");
	}
 
	boolean customerWantsCondiments() {
		return true;
	}
}

为了使用钩子，我们可以在子类覆盖它。在上面的例子中，钩子用来决定是否执行模板方法的某部分算法。

public class CoffeeWithHook extends CaffeineBeverageWithHook {
 
	public void brew() {
		System.out.println("Dripping Coffee through filter");
	}
 
	public void addCondiments() {
		System.out.println("Adding Sugar and Milk");
	}
 
	public boolean customerWantsCondiments() {

		String answer = getUserInput();

		if (answer.toLowerCase().startsWith("y")) {
			return true;
		} else {
			return false;
		}
	}
 
	private String getUserInput() {
		String answer = null;

		System.out.print("Would you like milk and sugar with your coffee (y/n)? ");

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		try {
			answer = in.readLine();
		} catch (IOException ioe) {
			System.err.println("IO error trying to read your answer");
		}
		if (answer == null) {
			return "no";
		}
		return answer;
	}
}

模板方法同样应用了一个设计原则：好莱坞原则。
别调用我们，我们会调用你。

好莱坞原则可以防止依赖腐败。当高层组件依赖底层组件，而底层组件又依赖高层组件，而高层组件有依赖边侧组件，而边侧组件有依赖底层组件时，依赖腐败就产生了。

在好莱坞原则下，我们允许底层组件将自己挂钩到系统上，但是有高层组件巨鼎什么时候和怎样使用这些底层组件。换句话说，也就是，高层组件对待低层组件的方式是”别调用我们，我们会调用你”。

Design_pattern_templatemethod_5

当我们设计模板方法模式时，我们告诉子，”不要调用我们，我们会调用你。”

Design_pattern_templatemethod_6

在Java中一个实际的例子是sort()方法的实现，sort原则上允许对任何类型的数组进行排序，只要该类实现了compareTo()方法，也就是在sort中使用模板方法，在实际使用中调用相应类的实现。

public class Duck implements Comparable {
	String name;
	int weight;
  
	public Duck(String name, int weight) {
		this.name = name;
		this.weight = weight;
	}
 
	public String toString() {
		return name + " weighs " + weight;
	}
 
 
  
	public int compareTo(Object object) {
 
		Duck otherDuck = (Duck)object;
  
		if (this.weight < otherDuck.weight) {
			return -1;
		} else if (this.weight == otherDuck.weight) {
			return 0;
		} else { // this.weight > otherDuck.weight
			return 1;
		}
	}
}

public class DuckSortTestDrive {

	public static void main(String[] args) {
		Duck[] ducks = { 
						new Duck("Daffy", 8), 
						new Duck("Dewey", 2),
						new Duck("Howard", 7),
						new Duck("Louie", 2),
						new Duck("Donald", 10), 
						new Duck("Huey", 2)
		 };

		System.out.println("Before sorting:");
		display(ducks);

		Arrays.sort(ducks);
 
		System.out.println("\nAfter sorting:");
		display(ducks);
	}

	public static void display(Duck[] ducks) {
		for (int i = 0; i < ducks.length; i++) {
			System.out.println(ducks[i]);
		}
	}
}

模板方法、策略、工厂方法比较：

模板方法：子类决定如何实现算法中的某些步骤。
策略：封装可互换的行为，然后使用委托来决定要采用哪一个行为。
工厂方法：由子类决定实例化哪个具体类。

区间调度问题详解

Posted on 2015-03-15 | In DSA | Comments:

区间调度问题详解

这里是一个区间调度问题的总结学习，主要参考区间调度问题详解，思路方面原文已经非常清晰，这里就不在赘述，请直接参考原文。

最多区间调度

Greedy

const int MAX_N=100000;
//输入
int N,S[MAX_N],T[MAX_N];

//用于对工作排序的pair数组
pair<int,int> itv[MAX_N];

void solve()
{
    //对pair进行的是字典序比较，为了让结束时间早的工作排在前面，把T存入first，//把S存入second
    for(int i=0;i<N;i++)
    {
	    itv[i].first=T[i];
	    itv[i].second=S[i];
    }

    sort(itv,itv+N);

    //t是最后所选工作的结束时间
    int ans=0,t=0;
    for(int i=0;i<N;i++)
    {
	    if(t<itv[i].second)//判断区间是否重叠
	    {
		    ans++;
		    t=itv[i].first;
	    }
    }

    printf(“%d\n”,ans);
}

void solve()
{
	//1. 对所有的区间进行排序
	sort_all_intervals();

	//2. 按照动态规划求最优解
	dp[0]=1;
	for (int i = 1; i < intervals.size(); i++) 
       {
		//1. 选择第i个区间
		k=find_nonoverlap_pos();
		if(k>=0) dp[i]=dp[k]+1;
		//2. 不选择第i个区间
		dp[i]=max{dp[i],dp[j]};
	}
}

最大区间调度

public int getMaxWorkingTime(List<Interval> intervals) {
		if(intervals==null || intervals.size()==0) return 0;
		Collections.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval i1, Interval i2) {
				return i1.getEndHour() != i2.getEndHour() ? i1.getEndHour() - i2.getEndHour() : i1.getEndMinute() - i2.getEndMinute();
			}
		});
		int[] maxTimes = new int[intervals.size()];
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<intervals.size(); i++) {
			Interval interval = intervals.get(i);
			int passMax = i>0 ? maxTimes[i-1] : 0;
			int takeMax = interval.getIntervalMinute();
			int lastIndex = binarySearchLastNorConflict(intervals, i-1, interval.getBeginMinuteUnit());
			takeMax += (lastIndex>=0 ? maxTimes[lastIndex] : 0);
			maxTimes[i] = Math.max(passMax, takeMax);
			if(maxTimes[i]>max) max = maxTimes[i];
		}
		return max;
	}
	
	public int binarySearchLastNorConflict(List<Interval> intervals, int right, int time) {
		int left = 0;
		while(left<=right) {
			int mid = (left + right) / 2;
			if(intervals.get(mid).getEndMinuteUnit()<=time) left = mid + 1;
			else right = mid - 1;
		}
		return right;
	}

带权的区间调度

const int MAX_N=100000;
//输入
int N,S[MAX_N],T[MAX_N];

//用于对工作排序的pair数组
pair<int,int> itv[MAX_N];

void solve()
{
    //对pair进行的是字典序比较，为了让结束时间早的工作排在前面，把T存入first，//把S存入second
    for(int i=0;i<N;i++)
    {
	    itv[i].first=T[i];
	    itv[i].second=S[i];
    }

    sort(itv,itv+N);

    dp[0] = (itv[0].first-itv[0].second)*V[0];
    for (int i = 1; i < N; i++)
    {
	    int max;

	    //select the ith interval
	    int nonOverlap = lower_bound(itv, itv[i].second)-1;
	    if (nonOverlap >= 0)
		    max = dp[nonOverlap] + (itv[i].first-itv[i].second)*V[i];
	    else
		    max = (itv[i].first-itv[i].second)*V[i];

	    //do not select the ith interval
	    dp[i] = max>dp[i-1]?max:dp[i-1];
    }
    printf(“%d\n”,dp[N-1]);
}

最小区间覆盖

将剩余的区间和新的左端点比较并选择右端点最大的区间，修改左端点，这时左端点就会变为end4，I4添加到最小覆盖区间中。依次处理剩余的区间，我们就获得了最优解

const int MAX_N=100000;
//输入
int N,S[MAX_N],T[MAX_N];

//用于对工作排序的pair数组
pair<int,int> itv[MAX_N];

int solve(int s,int t)
{
    for(int i=0;i<N;i++)
    {
	    itv[i].first=S[i];
	    itv[i].second=T[i];
    }

    //按照开始时间排序
    sort(itv,itv+N);

    int ans=0,max_right=0;
    for (int i = 0; i < N; )
    {
	    //从开始时间在s左侧的区间中挑出最大的结束时间
	    while(itv[i].first<=s)
	    {
		    if(max_right<itv[i].end) max_right=itv[i].end;
		    i++;
	    }	

	    if(max_right>s) 
        {
             s=max_right;
             ans++;
            if(s>=t) return ans;
        }
	    else //如果分界线左侧的区间不能覆盖s，则不可能有区间组合覆盖给定范围
	    {
                return -1;
	    }
    }
}

最大区间重叠（最少工人调度）

这里实际的代码是leetcode的minimal meeting room问题，但本质上就是最大区间重叠问题。

public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        // 用堆来管理房间的结束时间
        PriorityQueue<Integer> endTimes = new PriorityQueue<Integer>();
        endTimes.offer(intervals[0].end);
        for(int i = 1; i < intervals.length; i++){
            // 如果当前时间段的开始时间大于最早结束的时间，则可以更新这个最早的结束时间为当前时间段的结束时间，如果小于的话，就加入一个新的结束时间，表示新的房间
            if(intervals[i].start >= endTimes.peek()){
                endTimes.poll();
            }
            endTimes.offer(intervals[i].end);
        }
        // 有多少结束时间就有多少房间
        return endTimes.size();
    }
}

Adapter pattern

Posted on 2015-03-10 | In Design Pattern | Comments:

适配器模式

适配器模式是个相当好理解的模式，可以参考生活中的电源适配器。

Design_pattern_adapter_1

假设已有一个软件系统，我们希望它能和一个新的厂商类库搭配使用，但是这个新厂商所设计的接口和旧厂商的接口不同。

Design_pattern_adapter_2

这时我们就可以写一个类，实现新厂商接口，但真正提供服务是被封装的旧厂商(反过来也可以，甚至是双向适配器)。外部客户只需要调用新厂商接口，而不需要直到内部是谁实现的。这个适配器相当于一个中间人，将客户锁发出的请求转成厂商类所能理解的请求。

Design_pattern_adapter_3

Design_pattern_adapter_4

假设我们缺少鸭子对象，需要使用火鸡对象来冒充鸭子。我们可以这样做：

public interface Duck {
	public void quack();
	public void fly();
}

public class MallardDuck implements Duck {
	public void quack() {
		System.out.println("Quack");
	}
 
	public void fly() {
		System.out.println("I'm flying");
	}
}

public interface Turkey {
	public void gobble();
	public void fly();
}

public class WildTurkey implements Turkey {
	public void gobble() {
		System.out.println("Gobble gobble");
	}
 
	public void fly() {
		System.out.println("I'm flying a short distance");
	}
}

写个适配器：

public class TurkeyAdapter implements Duck {
	Turkey turkey;
 
	public TurkeyAdapter(Turkey turkey) {
		this.turkey = turkey;
	}
    
	public void quack() {
		turkey.gobble();
	}
  
	public void fly() {
		for(int i=0; i < 5; i++) {
			turkey.fly();
		}
	}
}

public class DuckTestDrive {
	public static void main(String[] args) {
		MallardDuck duck = new MallardDuck();
 
		WildTurkey turkey = new WildTurkey();
		Duck turkeyAdapter = new TurkeyAdapter(turkey);
   
		System.out.println("The Turkey says...");
		turkey.gobble();
		turkey.fly();
 
		System.out.println("\nThe Duck says...");
		testDuck(duck);
  
		System.out.println("\nThe TurkeyAdapter says...");
		testDuck(turkeyAdapter);
	}
 
	static void testDuck(Duck duck) {
		duck.quack();
		duck.fly();
	}
}

这里鸭子是目标接口，火鸡就是被适配者。

客户使用适配器的过程如下：

客户通过目标接口调用适配器的方法对适配器发出请求。
适配器使用陪被适配者接口执行请求。
客户收到调用的结果，但并未察觉这一切是适配器在起转换作用。

同样的，我们也可以写一个适配器将鸭子转为火鸡。

定义适配器模式

适配器模式将一个类的接口，转换为客户期望的另一个接口。适配器让原本接口不兼容的类可以互相合作。

同样适配器可以将改变的部分封装起来，被适配者接口改变时，客户端代码也不需要修改。

Design_pattern_adapter_5

对象适配器和类适配器

适配器主要有两类：对象适配器和类适配器。前面在鸭子的例子使用的是对象适配器。对象适配器使用的是组合，而类适配器使用的是继承(多继承)。

Design_pattern_adapter_6

Java的枚举器

Design_pattern_adapter_7

Design_pattern_adapter_8

public class EnumerationIterator implements Iterator {
	Enumeration enumeration;
 
	public EnumerationIterator(Enumeration enumeration) {
		this.enumeration = enumeration;
	}
 
	public boolean hasNext() {
		return enumeration.hasMoreElements();
	}
 
	public Object next() {
		return enumeration.nextElement();
	}
 
	public void remove() {
		throw new UnsupportedOperationException();
	}
}

public class EnumerationIteratorTestDrive {
	public static void main (String args[]) {
		Vector v = new Vector(Arrays.asList(args));
		Iterator iterator = new EnumerationIterator(v.elements());
		while (iterator.hasNext()) {
			System.out.println(iterator.next());
		}
	}
}

比较装饰器、适配器和外观：

装饰者：不改变接口，但加入责任
适配器：将一个接口转成另一个接口
外观：让接口更简单

外观模式

外观模式的意图是简化接口，而适配器的意图是将接口转换。使用外观模式，我们通过创建一个接口简化而统一的类，用来包装子系统中一个或多个复杂的类。

外观模式提供了一个统一的接口，用来访问子系统中的一群接口。外观定义了一个高层接口，让子系统更容易使用。

Design_pattern_adapter_10

这也符合了OO的另一个设计原则：最少知识原则
最少知识原则：只和你的密友谈话。

这个原则希望我们在设计中，不要让太多的类耦合在一起，免得修改系统中的一部分，会信息到更多的部分。我们需要尽量使类对其他类对象的依赖尽可能的少。除了上面的外观模式，另一个指导原则就是：就任何对象而言，在该对象的方法内，我们只应该调用属于一下范围的方法：

该对象本身
被当做方法的参数而传递进来的对象
此方法所创建或实例化的任何对象
对象的任何组件(组合方式的成员变量)

Design_pattern_adapter_11

Design_pattern_adapter_12

JUnit_JUnit基本使用

Posted on 2015-03-07 | In java | Comments:

参考JUnit入门教程(一), JUnit。

Hello world

编写functional code

public class Calculator {   
  
    public int plus(int x, int y) {  
        return x + y;  
    }  
    public int subtraction(int x, int y) {  
        return x - y;  
    }  
    public int multiplication(int x, int y) {  
        return x * y;  
    }  
    public int division(int x, int y) {  
        return x / y;  
    }  
}

编写单元测试类

import static org.junit.Assert.*; //注意这边,静态导入  
  
import org.junit.Ignore;  
import org.junit.Test;  
  
import com.zjw.junit4.Calculator;  
  
public class TestCalculator {  
  
    @Test  
    public void testPlus() {  
        Calculator cal = new Calculator();  
        assertEquals(cal.plus(5, 5), 10);  
    }  
  
    @Test  
    public void testSubtraction() {  
        Calculator cal = new Calculator();  
        assertEquals(cal.subtraction(5, 5), 0);  
    }  
  
    @Ignore  
    @Test  
    public void testMultiplication() {  
        Calculator cal = new Calculator();  
        assertTrue(cal.multiplication(5, 5) > 20);  
    }  
  
    @Test(expected = java.lang.ArithmeticException.class, timeout = 50)  
    public void testDivision() {  
        Calculator cal = new Calculator();  
        assertEquals(cal.division(8, 0), 4);   
    }  
}

可以看到每个测试都创建了一个实例，但其实这是没有必要的，我们可以是使用@BeforeClass在所有测试方法执行之前创建实例。

import static org.junit.Assert.*;  
  
import org.junit.BeforeClass;  
import org.junit.Ignore;  
import org.junit.Test;  
  
import com.zjw.junit4.Calculator;  
  
public class TestCalculator {  
      
    private static Calculator cal;  
          
    @BeforeClass  
    public static void beforeClass(){ //静态方法  
        cal=new Calculator();  
    }  
      
    @Test  
    public void testPlus() {  
        assertEquals(cal.plus(5, 5), 10);  
    }  
  
    @Test  
    public void testSubtraction() {  
        assertEquals(cal.subtraction(5, 5), 0);  
    }  
  
    @Ignore  
    @Test  
    public void testMultiplication() {  
        assertTrue(cal.multiplication(5, 5) > 20);  
    }  
  
    @Test(expected = java.lang.ArithmeticException.class, timeout = 50)  
    public void testDivision() {  
        assertEquals(cal.division(8, 0), 4);  
    }  
}

测试

使用Elipse可以直接使用Run as的JUnit test。
也可以编码执行测试：

import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
import org.junit.runner.notification.Failure;

public class TestRunner {
   public static void main(String[] args) {
      Result result = JUnitCore.runClasses(TestCalculator.class);
      for (Failure failure : result.getFailures()) {
         System.out.println(failure.toString());
      }
      System.out.println(result.wasSuccessful());
   }
}

一些JUnit 4的Annoation

@Test: 测试方法(expected=XXException.class, timeout=xxx)
@Ignore: 忽略测试方法
@Before: 每一个测试方法之前运行
@After: 每一个测试方法之后运行
@BeforeClass: 所有测试开始之前运行,别忘了方法是静态的，相当于JUnit 3中的setUp()方法。
@AfterClass: 所有测试结束之后运行，相当于JUnit 3中的tearDown()方法。

@Test设置了expected=XXException.class时，这个异常发生后，为测试成功。设置了timeout时，超过时间为测试失败。

Settings

测试类放在test包中
类名用TestXXX
方法用test方法名命名

JUnit类

Junit 4可以是使用基于标注的方式来设置测试，但是同样可以使用继承TestCase。才外还有几个重要的JUnit类，虽然在JUnit 4中很多时候不必显示使用，但是必须要要了解。

一些重要的类如下：

类	功能
Assert	assert 方法的集合
TestCase	一个定义了运行多重测试的固定装置
TestResult	TestResult 集合了执行测试样例的所有结果
TestSuite	TestSuite 是测试的集合

Assert

public class Assert extends java.lang.Object

这个类提供了一系列的编写测试的有用的声明方法。只有失败的声明方法才会被记录。Assert 类的重要方法列式如下：

方法	描述
void assertEquals(boolean expected, boolean actual)	检查两个变量或者等式是否平衡
void assertFalse(boolean condition)	检查条件是假的
void assertNotNull(Object object)	检查对象不是空的
void assertNull(Object object)	检查对象是空的
void assertTrue(boolean condition)	检查条件为真
void fail()	在没有报告的情况下使测试不通过
void assertArrayEquals(expectedArray, resultArray)
assertArrayEquals()	方法检查两个数组是否相等

TestCase 类

下面介绍的是 org.junit.TestCaset 类：

public abstract class TestCase extends Assert implements Test

测试样例定义了运行多重测试的固定格式。TestCase 类的一些重要方法列式如下：

方法	描述
int countTestCases()	为被run(TestResult result) 执行的测试案例计数
TestResult createResult()	创建一个默认的 TestResult 对象
String getName()	获取 TestCase 的名称
TestResult run()	一个运行这个测试的方便的方法，收集由TestResult 对象产生的结果
void run(TestResult result)	在 TestResult 中运行测试案例并收集结果
void setName(String name)	设置 TestCase 的名称
void setUp()	创建固定装置，例如，打开一个网络连接
void tearDown()	拆除固定装置，例如，关闭一个网络连接
String toString()	返回测试案例的一个字符串表示

TestResult 类

下面定义的是 org.junit.TestResult 类：

public class TestResult extends Object
TestResult类收集所有执行测试案例的结果。它是收集参数层面的一个实例。这个实验框架区分失败和错误。失败是可以预料的并且可以通过假设来检查。错误是不可预料的问题就像ArrayIndexOutOfBoundsException。

TestResult 类的一些重要方法列式如下：

方法	描述
void addError(Test test, Throwable t)	在错误列表中加入一个错误
void addFailure(Test test, AssertionFailedError t)	在失败列表中加入一个失败
void endTest(Test test)	显示测试被编译的这个结果
int errorCount()	获取被检测出错误的数量
Enumeration errors()	返回错误的详细信息
int failureCount()	获取被检测出的失败的数量
void run(TestCase test)	运行 TestCase
int int runCount()	获得运行测试的数量
void startTest(Test test)	声明一个测试即将开始
void stop()	标明测试必须停止

TestSuite 类

下面定义的是 org.junit.TestSuite 类：

public class TestSuite extends Object implements Test

TestSuite类是测试的组成部分。它运行了很多的测试案例。TestSuite 类的一些重要方法列式如下：

方法	描述
void addTest(Test test)	在套中加入测试。
void addTestSuite(Class<? extends TestCase> testClass)	将已经给定的类中的测试加到套中。
int countTestCases()	对这个测试即将运行的测试案例进行计数
String getName()	返回套的名称。
void run(TestResult result)	在 TestResult 中运行测试并收集结果。
void setName(String name)	设置套的名称。
Test testAt(int index)	在给定的目录中返回测试。
int testCount()		返回套中测试的数量。
static Test warning(String message)	返回会失败的测试并且记录警告信息。

import junit.framework.*;
public class JunitTestSuite {
   public static void main(String[] a) {
      // add the test's in the suite
      TestSuite suite = new TestSuite(TestJunit1.class, TestJunit2.class, TestJunit3.class );
      TestResult result = new TestResult();
      suite.run(result);
      System.out.println("Number of test cases = " + result.runCount());
    }
}

测试

JUnitCore

测试用例是使用 JUnitCore 类来执行的。JUnitCore 是运行测试的外观类。它支持运行 JUnit 4 测试, JUnit 3.8.x 测试,或者他们的混合。要从命令行运行测试，可以运行 java org.junit.runner.JUnitCore 。对于只有一次的测试运行，可以使用静态方法 runClasses(Class[])。

下面是 org.junit.runner.JUnitCore 类的声明：
public class JUnitCore extends java.lang.Object

套件测试

测试套件意味着捆绑几个单元测试用例并且一起执行他们。在 JUnit 中，@RunWith 和 @Suite 注释用来运行套件测试。这个教程将向您展示一个例子，其中含有两个测试样例 TestJunit1 & TestJunit2 类，我们将使用测试套件一起运行他们。

public class MessageUtil {

   private String message;

   //Constructor
   //@param message to be printed
   public MessageUtil(String message){
      this.message = message; 
   }

   // prints the message
   public String printMessage(){
      System.out.println(message);
      return message;
   }   

   // add "Hi!" to the message
   public String salutationMessage(){
      message = "Hi!" + message;
      System.out.println(message);
      return message;
   }   
}

Test Case类

import org.junit.Test;
import org.junit.Ignore;
import static org.junit.Assert.assertEquals;

public class TestJunit1 {

   String message = "Robert";   
   MessageUtil messageUtil = new MessageUtil(message);

   @Test
   public void testPrintMessage() { 
      System.out.println("Inside testPrintMessage()");    
      assertEquals(message, messageUtil.printMessage());     
   }
}

import org.junit.Test;
import org.junit.Ignore;
import static org.junit.Assert.assertEquals;

public class TestJunit2 {

   String message = "Robert";   
   MessageUtil messageUtil = new MessageUtil(message);

   @Test
   public void testSalutationMessage() {
      System.out.println("Inside testSalutationMessage()");
      message = "Hi!" + "Robert";
      assertEquals(message,messageUtil.salutationMessage());
   }
}

使用 Test Suite 类

创建一个 java 类。
在类中附上 @RunWith(Suite.class) 注释。
使用 @Suite.SuiteClasses 注释给 JUnit 测试类加上引用。

import org.junit.runner.RunWith;
import org.junit.runners.Suite;
@RunWith(Suite.class)
@Suite.SuiteClasses({
   TestJunit1.class,
   TestJunit2.class
})
public class JunitTestSuite {   
}

创建Test Runner类：

import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
import org.junit.runner.notification.Failure;

public class TestRunner {
   public static void main(String[] args) {
      Result result = JUnitCore.runClasses(JunitTestSuite.class);
      for (Failure failure : result.getFailures()) {
         System.out.println(failure.toString());
      }
      System.out.println(result.wasSuccessful());
   }
}

时间测试和异常测试

@Test: 测试方法(expected=XXException.class, timeout=xxx)

@Test设置了expected=XXException.class时，这个异常发生后，为测试成功。设置了timeout时，超过时间为测试失败。

参数化测试

Junit 4 引入了一个新的功能参数化测试。参数化测试允许开发人员使用不同的值反复运行同一个测试。你将遵循 5 个步骤来创建参数化测试。

用 @RunWith(Parameterized.class) 来注释 test 类。
创建一个由 @Parameters 注释的公共的静态方法，它返回一个对象的集合(数组)来作为测试数据集合。
创建一个公共的构造函数，它接受和一行测试数据相等同的东西。
为每一列测试数据创建一个实例变量。
用实例变量作为测试数据的来源来创建你的测试用例。
一旦每一行数据出现测试用例将被调用。让我们看看活动中的参数化测试。

public class PrimeNumberChecker {
   public Boolean validate(final Integer primeNumber) {
      for (int i = 2; i < (primeNumber / 2); i++) {
         if (primeNumber % i == 0) {
            return false;
         }
      }
      return true;
   }
}

创建 Parameterized Test Case 类

import java.util.Arrays;
import java.util.Collection;

import org.junit.Test;
import org.junit.Before;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;
import org.junit.runner.RunWith;
import static org.junit.Assert.assertEquals;

@RunWith(Parameterized.class)
public class PrimeNumberCheckerTest {
   private Integer inputNumber;
   private Boolean expectedResult;
   private PrimeNumberChecker primeNumberChecker;

   @Before
   public void initialize() {
      primeNumberChecker = new PrimeNumberChecker();
   }

   // Each parameter should be placed as an argument here
   // Every time runner triggers, it will pass the arguments
   // from parameters we defined in primeNumbers() method
   public PrimeNumberCheckerTest(Integer inputNumber, 
      Boolean expectedResult) {
      this.inputNumber = inputNumber;
      this.expectedResult = expectedResult;
   }

   @Parameterized.Parameters
   public static Collection primeNumbers() {
      return Arrays.asList(new Object[][] {
         { 2, true },
         { 6, false },
         { 19, true },
         { 22, false },
         { 23, true }
      });
   }

   // This test will run 4 times since we have 5 parameters defined
   @Test
   public void testPrimeNumberChecker() {
      System.out.println("Parameterized Number is : " + inputNumber);
      assertEquals(expectedResult, 
      primeNumberChecker.validate(inputNumber));
   }
}

创建 TestRunner 类

import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
import org.junit.runner.notification.Failure;

public class TestRunner {
   public static void main(String[] args) {
      Result result = JUnitCore.runClasses(PrimeNumberCheckerTest.class);
      for (Failure failure : result.getFailures()) {
         System.out.println(failure.toString());
      }
      System.out.println(result.wasSuccessful());
   }
}

Parameterized Number is : 2
Parameterized Number is : 6
Parameterized Number is : 19
Parameterized Number is : 22
Parameterized Number is : 23
true

整合Ant, Maven

参考JUnit.