Абстрактные типы данных 1. Абстрактная дата Date dt1, dt2; dt1 = new Date(1, Date.MARCH, 2006); dt2 = (Date)dt1.clone(); dt2.add(300); // 1.03.2006 + 300. - презентация

1 Абстрактные типы данных 1. Абстрактная дата Date dt1, dt2; dt1 = new Date(1, Date.MARCH, 2006); dt2 = (Date)dt1.clone(); dt2.add(300); // дней while (dt2.after(dt1)) dt2.add(0, -1, 0); CloneableComparable clone()compareTo() Date before() after()... Date1 clone() compareTo() before()... Date2 clone() compareTo() before()...

2 public interface Date extends Cloneable, Comparable { // Cloneable redefinition Object clone(); // Comparing int compareTo(Date d); boolean before(Date d); boolean after(Date d); // Access to attributes int year(); int month(); int date(); int day(); // Date arithmetic void add(int days); void add(int years, int months, int days); Date cloneAndAdd(int days); Date cloneAndAdd(int years, int months, int days); int dateDiff(Date dt); } Описание абстрактной даты

3 Реализация даты public class Date1 implements Date { int year, // from 0 to 3000 month, // from 0 to 11 date; // from 1 to 31 // Constructors public Date1(int year, int month, int date) { this.year = year; this.month = month; this.date = date; } public Date1(Date src) { this(src.getYear(), src.getMonth(), src.getDate()); } // Cloneable redefinition public Object clone() { return new Date1(this); } // Comparing public int compareTo(Date d) { return ((year - d.getYear())

4 2. Абстрактный список public interface List { // Elements counting boolean isEmpty(); int size(); // Access to elements Object first(); Object last(); // Changes in list Object addFirst(Object o); Object addLast(Object o); Object removeFirst(); Object removeLast(); // List iteration void iterate(Visitor visitor); Iterator iterator(); } } 123…n firstlast

5 Возможные реализации списков n first last Связанный списокМассив first = 0 last

6 Реализация в виде связанного списка public class LinkedList implements List { private static class ListNode { Object info; ListNode next, pred; ListNode(Object o) { this(o, null, null); } ListNode(Object o, ListNode n, ListNode p) { info = o; next = n; pred = p; } } ListNode first = null, last = null; int count = 0; public LinkedList() {} public Object first() { return this.first.info; } public Object last() { return this.last.info; } public boolean isEmpty() { return count == 0; } public int size() { return count; } public Object addFirst(Object obj) { ListNode newNode = new ListNode(obj, first, null); if (first == null) last = newNode; else first.pred = newNode; first = newNode; count++; return obj; }

7 Реализация в виде массива public class ArrayList implements List { private Object[] array = null; private int ptrStart = 0; private int ptrEnd = 0; private int count = 0; public ArrayList() { array = new Object[10]; } public Object first() { return array[ptrStart]; } public Object last() { return array[ptrEnd == 0 ? array.length-1 : ptrEnd-1]; } public boolean isEmpty() { return count == 0; } public int size() { return count; } public Object addLast(Object o) { if (count == array.length) enlarge(10); if (ptrEnd == array.length) ptrEnd = 1; else ptrEnd++; array[ptrEnd-1] = o; count++; return null; } public Object removeLast() { if (--ptrEnd < 0) ptrEnd = array.length-1; count--; return array[ptrEnd]; }

8 Итерация элементов сложной структуры Внутренний итератор: public interface Visitor { void visit(Object node); } public class Printer implements Visitor { public void visit(Object node) { System.out.print(node); } } public static void main(String[] args) { List lst =...; lst.iterate(new Printer()); } public interface List {... void iterate(Visitor visitor); } public class LinkedList implements List {... public void iterate(Visitor visitor) { for (ListNode current = first; current != null; current = current.next) { visitor.visit(current.info); }

9 Внешний итератор: public static void main(String[] args) { List lst =...; Iterator it = lst.iterator(); for (Object nextObj = it.begin(); nextObj != it.end(); nextObj = it.next()) { System.out.print(" " + nextObj); } public static void main(String[] args) { List lst =...; for (Iterator it = lst.iterator(); it.hasNext(); ) { Object nextObj = it.next(); System.out.print(" " + nextObj); } public interface Iterator { boolean hasNext(); void next(); } void remove(); public interface List {... Iterator iterator(); }

10 Реализация внешнего итератора для связанного списка: public class LinkedList implements List {... public Iterator iterator() { return new ListIterator(); } private class ListIterator implements Iterator { ListNode current = first; ListNode toRemove = null; public boolean hasNext() { return current != null; } public Object next() { if (current == null) throw new NoSuchElementException("ListIterator"); toRemove = current; Object ret = current.info; current = current.next; return ret; } public void remove() { if (toRemove == null) throw new IllegalStateException("ListIterator"); ListNode pred = toRemove.pred; if (pred == null) first = current; else pred.next = current; if (current != null) current.pred = pred; toRemove = null; count--; }