1 #!/usr/bin/env python 2 3 """ 4 Managing and presenting periods of time. 5 6 Copyright (C) 2014, 2015 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 from bisect import bisect_left, bisect_right, insort_left 23 from datetime import date, datetime, timedelta 24 from imiptools.dates import format_datetime, get_datetime, \ 25 get_datetime_attributes, \ 26 get_recurrence_start, get_recurrence_start_point, \ 27 get_start_of_day, \ 28 get_tzid, \ 29 to_timezone, to_utc_datetime 30 31 def ifnone(x, y): 32 if x is None: return y 33 else: return x 34 35 class Comparable: 36 37 "A date/datetime wrapper that allows comparisons with other types." 38 39 def __init__(self, dt): 40 self.dt = dt 41 42 def __cmp__(self, other): 43 dt = None 44 odt = None 45 46 # Find any dates/datetimes. 47 48 if isinstance(self.dt, date): 49 dt = self.dt 50 if isinstance(other, date): 51 odt = other 52 elif isinstance(other, Comparable): 53 if isinstance(other.dt, date): 54 odt = other.dt 55 else: 56 other = other.dt 57 58 if dt and odt: 59 return cmp(dt, odt) 60 elif dt: 61 return other.__rcmp__(dt) 62 elif odt: 63 return self.dt.__cmp__(odt) 64 else: 65 return self.dt.__cmp__(other) 66 67 class PointInTime: 68 69 "A base class for special values." 70 71 pass 72 73 class StartOfTime(PointInTime): 74 75 "A special value that compares earlier than other values." 76 77 def __cmp__(self, other): 78 if isinstance(other, StartOfTime): 79 return 0 80 else: 81 return -1 82 83 def __rcmp__(self, other): 84 return -self.__cmp__(other) 85 86 def __nonzero__(self): 87 return False 88 89 class EndOfTime(PointInTime): 90 91 "A special value that compares later than other values." 92 93 def __cmp__(self, other): 94 if isinstance(other, EndOfTime): 95 return 0 96 else: 97 return 1 98 99 def __rcmp__(self, other): 100 return -self.__cmp__(other) 101 102 def __nonzero__(self): 103 return False 104 105 class PeriodBase: 106 107 "A basic period abstraction." 108 109 def as_tuple(self): 110 return self.start, self.end 111 112 def __hash__(self): 113 return hash((self.get_start(), self.get_end())) 114 115 def __cmp__(self, other): 116 117 "Return a comparison result against 'other' using points in time." 118 119 if isinstance(other, PeriodBase): 120 return cmp( 121 (Comparable(ifnone(self.get_start_point(), StartOfTime())), Comparable(ifnone(self.get_end_point(), EndOfTime()))), 122 (Comparable(ifnone(other.get_start_point(), StartOfTime())), Comparable(ifnone(other.get_end_point(), EndOfTime()))) 123 ) 124 else: 125 return 1 126 127 def overlaps(self, other): 128 return Comparable(ifnone(self.get_end_point(), EndOfTime())) > Comparable(ifnone(other.get_start_point(), StartOfTime())) and \ 129 Comparable(ifnone(self.get_start_point(), StartOfTime())) < Comparable(ifnone(other.get_end_point(), EndOfTime())) 130 131 def get_key(self): 132 return self.get_start(), self.get_end() 133 134 # Datetime and metadata methods. 135 136 def get_start(self): 137 return self.start 138 139 def get_end(self): 140 return self.end 141 142 def get_start_attr(self): 143 return get_datetime_attributes(self.start, self.tzid) 144 145 def get_end_attr(self): 146 return get_datetime_attributes(self.end, self.tzid) 147 148 def get_start_item(self): 149 return self.get_start(), self.get_start_attr() 150 151 def get_end_item(self): 152 return self.get_end(), self.get_end_attr() 153 154 def get_start_point(self): 155 return self.start 156 157 def get_end_point(self): 158 return self.end 159 160 def get_duration(self): 161 return self.get_end_point() - self.get_start_point() 162 163 class Period(PeriodBase): 164 165 "A simple period abstraction." 166 167 def __init__(self, start, end, tzid=None, origin=None): 168 169 """ 170 Initialise a period with the given 'start' and 'end', having a 171 contextual 'tzid', if specified, and an indicated 'origin'. 172 173 All metadata from the start and end points are derived from the supplied 174 dates/datetimes. 175 """ 176 177 if isinstance(start, (date, PointInTime)): self.start = start 178 else: self.start = get_datetime(start) or StartOfTime() 179 if isinstance(end, (date, PointInTime)): self.end = end 180 else: self.end = get_datetime(end) or EndOfTime() 181 self.tzid = tzid 182 self.origin = origin 183 184 def as_tuple(self): 185 return self.start, self.end, self.tzid, self.origin 186 187 def __repr__(self): 188 return "Period%r" % (self.as_tuple(),) 189 190 # Datetime and metadata methods. 191 192 def get_tzid(self): 193 return get_tzid(self.get_start_attr(), self.get_end_attr()) or self.tzid 194 195 def get_start_point(self): 196 start = self.get_start() 197 if isinstance(start, PointInTime): return start 198 else: return to_utc_datetime(start, self.get_tzid()) 199 200 def get_end_point(self): 201 end = self.get_end() 202 if isinstance(end, PointInTime): return end 203 else: return to_utc_datetime(end, self.get_tzid()) 204 205 # Period and event recurrence logic. 206 207 def is_replaced(self, recurrenceids): 208 209 """ 210 Return whether this period refers to one of the 'recurrenceids'. 211 The 'recurrenceids' should be normalised to UTC datetimes according to 212 time zone information provided by their objects or be floating dates or 213 datetimes requiring conversion using contextual time zone information. 214 """ 215 216 for recurrenceid in recurrenceids: 217 if self.is_affected(recurrenceid): 218 return recurrenceid 219 return None 220 221 def is_affected(self, recurrenceid): 222 223 """ 224 Return whether this period refers to 'recurrenceid'. The 'recurrenceid' 225 should be normalised to UTC datetimes according to time zone information 226 provided by their objects. Otherwise, this period's contextual time zone 227 information is used to convert any date or floating datetime 228 representation to a point in time. 229 """ 230 231 if not recurrenceid: 232 return None 233 d = get_recurrence_start(recurrenceid) 234 dt = get_recurrence_start_point(recurrenceid, self.tzid) 235 if self.get_start() == d or self.get_start_point() == dt: 236 return recurrenceid 237 return None 238 239 class FreeBusyPeriod(PeriodBase): 240 241 "A free/busy record abstraction." 242 243 def __init__(self, start, end, uid=None, transp=None, recurrenceid=None, summary=None, organiser=None, expires=None): 244 245 """ 246 Initialise a free/busy period with the given 'start' and 'end' points, 247 plus any 'uid', 'transp', 'recurrenceid', 'summary' and 'organiser' 248 details. 249 250 An additional 'expires' parameter can be used to indicate an expiry 251 datetime in conjunction with free/busy offers made when countering 252 event proposals. 253 """ 254 255 self.start = isinstance(start, datetime) and start or get_datetime(start) 256 self.end = isinstance(end, datetime) and end or get_datetime(end) 257 self.uid = uid 258 self.transp = transp 259 self.recurrenceid = recurrenceid 260 self.summary = summary 261 self.organiser = organiser 262 self.expires = expires 263 264 def as_tuple(self, strings_only=False): 265 266 """ 267 Return the initialisation parameter tuple, converting false value 268 parameters to strings if 'strings_only' is set to a true value. 269 """ 270 271 null = lambda x: (strings_only and [""] or [x])[0] 272 return ( 273 strings_only and format_datetime(self.get_start_point()) or self.start, 274 strings_only and format_datetime(self.get_end_point()) or self.end, 275 self.uid or null(self.uid), 276 self.transp or strings_only and "OPAQUE" or None, 277 self.recurrenceid or null(self.recurrenceid), 278 self.summary or null(self.summary), 279 self.organiser or null(self.organiser), 280 self.expires or null(self.expires) 281 ) 282 283 def __cmp__(self, other): 284 285 """ 286 Compare this object to 'other', employing the uid if the periods 287 involved are the same. 288 """ 289 290 result = PeriodBase.__cmp__(self, other) 291 if result == 0 and isinstance(other, FreeBusyPeriod): 292 return cmp((self.uid, self.recurrenceid), (other.uid, other.recurrenceid)) 293 else: 294 return result 295 296 def get_key(self): 297 return self.uid, self.recurrenceid, self.get_start() 298 299 def __repr__(self): 300 return "FreeBusyPeriod%r" % (self.as_tuple(),) 301 302 # Period and event recurrence logic. 303 304 def is_replaced(self, recurrences): 305 306 """ 307 Return whether this period refers to one of the 'recurrences'. 308 The 'recurrences' must be UTC datetimes corresponding to the start of 309 the period described by a recurrence. 310 """ 311 312 for recurrence in recurrences: 313 if self.is_affected(recurrence): 314 return True 315 return False 316 317 def is_affected(self, recurrence): 318 319 """ 320 Return whether this period refers to 'recurrence'. The 'recurrence' must 321 be a UTC datetime corresponding to the start of the period described by 322 a recurrence. 323 """ 324 325 return recurrence and self.get_start_point() == recurrence 326 327 class RecurringPeriod(Period): 328 329 """ 330 A period with iCalendar metadata attributes and origin information from an 331 object. 332 """ 333 334 def __init__(self, start, end, tzid=None, origin=None, start_attr=None, end_attr=None): 335 Period.__init__(self, start, end, tzid, origin) 336 self.start_attr = start_attr 337 self.end_attr = end_attr 338 339 def get_start_attr(self): 340 return self.start_attr 341 342 def get_end_attr(self): 343 return self.end_attr 344 345 def as_tuple(self): 346 return self.start, self.end, self.tzid, self.origin, self.start_attr, self.end_attr 347 348 def __repr__(self): 349 return "RecurringPeriod%r" % (self.as_tuple(),) 350 351 # Time and period management. 352 353 def can_schedule(freebusy, periods, uid, recurrenceid): 354 355 """ 356 Return whether the 'freebusy' list can accommodate the given 'periods' 357 employing the specified 'uid' and 'recurrenceid'. 358 """ 359 360 for conflict in have_conflict(freebusy, periods, True): 361 if conflict.uid != uid or conflict.recurrenceid != recurrenceid: 362 return False 363 364 return True 365 366 def have_conflict(freebusy, periods, get_conflicts=False): 367 368 """ 369 Return whether any period in 'freebusy' overlaps with the given 'periods', 370 returning a collection of such overlapping periods if 'get_conflicts' is 371 set to a true value. 372 """ 373 374 conflicts = set() 375 for p in periods: 376 overlapping = period_overlaps(freebusy, p, get_conflicts) 377 if overlapping: 378 if get_conflicts: 379 conflicts.update(overlapping) 380 else: 381 return True 382 383 if get_conflicts: 384 return conflicts 385 else: 386 return False 387 388 def insert_period(freebusy, period): 389 390 "Insert into 'freebusy' the given 'period'." 391 392 i = bisect_left(freebusy, period) 393 if i == len(freebusy): 394 freebusy.append(period) 395 elif freebusy[i] != period: 396 freebusy.insert(i, period) 397 398 def remove_period(freebusy, uid, recurrenceid=None): 399 400 """ 401 Remove from 'freebusy' all periods associated with 'uid' and 'recurrenceid' 402 (which if omitted causes the "parent" object's periods to be referenced). 403 """ 404 405 removed = False 406 i = 0 407 while i < len(freebusy): 408 fb = freebusy[i] 409 if fb.uid == uid and fb.recurrenceid == recurrenceid: 410 del freebusy[i] 411 removed = True 412 else: 413 i += 1 414 415 return removed 416 417 def remove_additional_periods(freebusy, uid, recurrenceids=None): 418 419 """ 420 Remove from 'freebusy' all periods associated with 'uid' having a 421 recurrence identifier indicating an additional or modified period. 422 423 If 'recurrenceids' is specified, remove all periods associated with 'uid' 424 that do not have a recurrence identifier in the given list. 425 """ 426 427 i = 0 428 while i < len(freebusy): 429 fb = freebusy[i] 430 if fb.uid == uid and fb.recurrenceid and ( 431 recurrenceids is None or 432 recurrenceids is not None and fb.recurrenceid not in recurrenceids 433 ): 434 del freebusy[i] 435 else: 436 i += 1 437 438 def remove_affected_period(freebusy, uid, start): 439 440 """ 441 Remove from 'freebusy' a period associated with 'uid' that provides an 442 occurrence starting at the given 'start' (provided by a recurrence 443 identifier, converted to a datetime). A recurrence identifier is used to 444 provide an alternative time period whilst also acting as a reference to the 445 originally-defined occurrence. 446 """ 447 448 search = Period(start, start) 449 found = bisect_left(freebusy, search) 450 451 while found < len(freebusy): 452 fb = freebusy[found] 453 454 # Stop looking if the start no longer matches the recurrence identifier. 455 456 if fb.get_start_point() != search.get_start_point(): 457 return 458 459 # If the period belongs to the parent object, remove it and return. 460 461 if not fb.recurrenceid and uid == fb.uid: 462 del freebusy[found] 463 break 464 465 # Otherwise, keep looking for a matching period. 466 467 found += 1 468 469 def periods_from(freebusy, period): 470 471 "Return the entries in 'freebusy' at or after 'period'." 472 473 first = bisect_left(freebusy, period) 474 return freebusy[first:] 475 476 def periods_until(freebusy, period): 477 478 "Return the entries in 'freebusy' before 'period'." 479 480 last = bisect_right(freebusy, Period(period.get_end(), period.get_end(), period.get_tzid())) 481 return freebusy[:last] 482 483 def get_overlapping(freebusy, period): 484 485 """ 486 Return the entries in 'freebusy' providing periods overlapping with 487 'period'. 488 """ 489 490 # Find the range of periods potentially overlapping the period in the 491 # free/busy collection. 492 493 startpoints = periods_until(freebusy, period) 494 495 # Find the range of periods potentially overlapping the period in a version 496 # of the free/busy collection sorted according to end datetimes. 497 498 endpoints = [(Period(fb.get_end_point(), fb.get_end_point()), fb) for fb in startpoints] 499 endpoints.sort() 500 first = bisect_left(endpoints, (Period(period.get_start_point(), period.get_start_point()),)) 501 endpoints = endpoints[first:] 502 503 overlapping = set() 504 505 for p, fb in endpoints: 506 if fb.overlaps(period): 507 overlapping.add(fb) 508 509 overlapping = list(overlapping) 510 overlapping.sort() 511 return overlapping 512 513 def period_overlaps(freebusy, period, get_periods=False): 514 515 """ 516 Return whether any period in 'freebusy' overlaps with the given 'period', 517 returning a collection of overlapping periods if 'get_periods' is set to a 518 true value. 519 """ 520 521 overlapping = get_overlapping(freebusy, period) 522 523 if get_periods: 524 return overlapping 525 else: 526 return len(overlapping) != 0 527 528 def remove_overlapping(freebusy, period): 529 530 "Remove from 'freebusy' all periods overlapping with 'period'." 531 532 overlapping = get_overlapping(freebusy, period) 533 534 if overlapping: 535 for fb in overlapping: 536 freebusy.remove(fb) 537 538 def replace_overlapping(freebusy, period, replacements): 539 540 """ 541 Replace existing periods in 'freebusy' within the given 'period', using the 542 given 'replacements'. 543 """ 544 545 remove_overlapping(freebusy, period) 546 for replacement in replacements: 547 insert_period(freebusy, replacement) 548 549 def coalesce_freebusy(freebusy): 550 551 "Coalesce the periods in 'freebusy'." 552 553 if not freebusy: 554 return freebusy 555 556 fb = [] 557 start = freebusy[0].get_start_point() 558 end = freebusy[0].get_end_point() 559 560 for period in freebusy[1:]: 561 if period.get_start_point() > end: 562 fb.append(FreeBusyPeriod(start, end)) 563 start = period.get_start_point() 564 end = period.get_end_point() 565 else: 566 end = max(end, period.get_end_point()) 567 568 fb.append(FreeBusyPeriod(start, end)) 569 return fb 570 571 def invert_freebusy(freebusy): 572 573 "Return the free periods from 'freebusy'." 574 575 if not freebusy: 576 return None 577 578 fb = coalesce_freebusy(freebusy) 579 free = [] 580 start = fb[0].get_end_point() 581 582 for period in fb[1:]: 583 free.append(FreeBusyPeriod(start, period.get_start_point())) 584 start = period.get_end_point() 585 586 return free 587 588 # Period layout. 589 590 def get_scale(periods, tzid, view_period=None): 591 592 """ 593 Return a time scale from the given list of 'periods'. 594 595 The given 'tzid' is used to make sure that the times are defined according 596 to the chosen time zone. 597 598 An optional 'view_period' is used to constrain the scale to the given 599 period. 600 601 The returned scale is a mapping from time to (starting, ending) tuples, 602 where starting and ending are collections of periods. 603 """ 604 605 scale = {} 606 view_start = view_period and to_timezone(view_period.get_start_point(), tzid) or None 607 view_end = view_period and to_timezone(view_period.get_end_point(), tzid) or None 608 609 for p in periods: 610 611 # Add a point and this event to the starting list. 612 613 start = to_timezone(p.get_start(), tzid) 614 start = view_start and max(start, view_start) or start 615 if not scale.has_key(start): 616 scale[start] = [], [] 617 scale[start][0].append(p) 618 619 # Add a point and this event to the ending list. 620 621 end = to_timezone(p.get_end(), tzid) 622 if not view_end or end < view_end: 623 if not scale.has_key(end): 624 scale[end] = [], [] 625 scale[end][1].append(p) 626 627 return scale 628 629 class Point: 630 631 "A qualified point in time." 632 633 PRINCIPAL, REPEATED = 0, 1 634 635 def __init__(self, point, indicator=None): 636 self.point = point 637 self.indicator = indicator or self.PRINCIPAL 638 639 def __hash__(self): 640 return hash((self.point, self.indicator)) 641 642 def __cmp__(self, other): 643 if isinstance(other, Point): 644 return cmp((self.point, self.indicator), (other.point, other.indicator)) 645 elif isinstance(other, datetime): 646 return cmp(self.point, other) 647 else: 648 return 1 649 650 def __eq__(self, other): 651 return self.__cmp__(other) == 0 652 653 def __ne__(self, other): 654 return not self == other 655 656 def __lt__(self, other): 657 return self.__cmp__(other) < 0 658 659 def __le__(self, other): 660 return self.__cmp__(other) <= 0 661 662 def __gt__(self, other): 663 return not self <= other 664 665 def __ge__(self, other): 666 return not self < other 667 668 def __repr__(self): 669 return "Point(%r, Point.%s)" % (self.point, self.indicator and "REPEATED" or "PRINCIPAL") 670 671 def get_slots(scale): 672 673 """ 674 Return an ordered list of time slots from the given 'scale'. 675 676 Each slot is a tuple containing details of a point in time for the start of 677 the slot, together with a list of parallel event periods. 678 679 Each point in time is described as a Point representing the actual point in 680 time together with an indicator of the nature of the point in time (as a 681 principal point in a time scale or as a repeated point used to terminate 682 events occurring for an instant in time). 683 """ 684 685 slots = [] 686 active = [] 687 688 points = scale.items() 689 points.sort() 690 691 for point, (starting, ending) in points: 692 ending = set(ending) 693 instants = ending.intersection(starting) 694 695 # Discard all active events ending at or before this start time. 696 # Free up the position in the active list. 697 698 for t in ending.difference(instants): 699 i = active.index(t) 700 active[i] = None 701 702 # For each event starting at the current point, fill any newly-vacated 703 # position or add to the end of the active list. 704 705 for t in starting: 706 try: 707 i = active.index(None) 708 active[i] = t 709 except ValueError: 710 active.append(t) 711 712 # Discard vacant positions from the end of the active list. 713 714 while active and active[-1] is None: 715 active.pop() 716 717 # Add an entry for the time point before "instants". 718 719 slots.append((Point(point), active[:])) 720 721 # Discard events ending at the same time as they began. 722 723 if instants: 724 for t in instants: 725 i = active.index(t) 726 active[i] = None 727 728 # Discard vacant positions from the end of the active list. 729 730 while active and active[-1] is None: 731 active.pop() 732 733 # Add another entry for the time point after "instants". 734 735 slots.append((Point(point, Point.REPEATED), active[:])) 736 737 return slots 738 739 def add_day_start_points(slots, tzid): 740 741 """ 742 Introduce into the 'slots' any day start points required by multi-day 743 periods. The 'tzid' is required to make sure that appropriate time zones 744 are chosen and not necessarily those provided by the existing time points. 745 """ 746 747 new_slots = [] 748 current_date = None 749 previously_active = [] 750 751 for point, active in slots: 752 start_of_day = get_start_of_day(point.point, tzid) 753 this_date = point.point.date() 754 755 # For each new day, add a slot for the start of the day where periods 756 # are active and where no such slot already exists. 757 758 if this_date != current_date: 759 760 # Fill in days where events remain active. 761 762 if current_date: 763 current_date += timedelta(1) 764 while current_date < this_date: 765 new_slots.append((Point(get_start_of_day(current_date, tzid)), previously_active)) 766 current_date += timedelta(1) 767 else: 768 current_date = this_date 769 770 # Add any continuing periods. 771 772 if point.point != start_of_day: 773 new_slots.append((Point(start_of_day), previously_active)) 774 775 # Add the currently active periods at this point in time. 776 777 previously_active = active 778 779 for t in new_slots: 780 insort_left(slots, t) 781 782 def add_slots(slots, points): 783 784 """ 785 Introduce into the 'slots' entries for those in 'points' that are not 786 already present, propagating active periods from time points preceding 787 those added. 788 """ 789 790 new_slots = [] 791 792 for point in points: 793 i = bisect_left(slots, (point,)) # slots is [(point, active)...] 794 if i < len(slots) and slots[i][0] == point: 795 continue 796 797 new_slots.append((point, i > 0 and slots[i-1][1] or [])) 798 799 for t in new_slots: 800 insort_left(slots, t) 801 802 def partition_by_day(slots): 803 804 """ 805 Return a mapping from dates to time points provided by 'slots'. 806 """ 807 808 d = {} 809 810 for point, value in slots: 811 day = point.point.date() 812 if not d.has_key(day): 813 d[day] = [] 814 d[day].append((point, value)) 815 816 return d 817 818 def add_empty_days(days, tzid, start=None, end=None): 819 820 """ 821 Add empty days to 'days' between busy days, and optionally from the given 822 'start' day and until the given 'end' day. 823 """ 824 825 last_day = start - timedelta(1) 826 all_days = days.keys() 827 all_days.sort() 828 829 for day in all_days: 830 if last_day: 831 empty_day = last_day + timedelta(1) 832 while empty_day < day: 833 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 834 empty_day += timedelta(1) 835 last_day = day 836 837 if end: 838 empty_day = last_day + timedelta(1) 839 while empty_day < end: 840 days[empty_day] = [(Point(get_start_of_day(empty_day, tzid)), None)] 841 empty_day += timedelta(1) 842 843 def get_spans(slots): 844 845 "Inspect the given 'slots', returning a mapping of period keys to spans." 846 847 points = [point for point, active in slots] 848 spans = {} 849 850 for _point, active in slots: 851 for p in active: 852 if p: 853 key = p.get_key() 854 start_slot = bisect_left(points, p.get_start()) 855 end_slot = bisect_left(points, p.get_end()) 856 spans[key] = end_slot - start_slot 857 858 return spans 859 860 def update_freebusy(freebusy, periods, transp, uid, recurrenceid, summary, organiser, expires=None): 861 862 """ 863 Update the free/busy details with the given 'periods', 'transp' setting, 864 'uid' plus 'recurrenceid' and 'summary' and 'organiser' details. 865 866 An optional 'expires' datetime string indicates the expiry time of any 867 free/busy offer. 868 """ 869 870 remove_period(freebusy, uid, recurrenceid) 871 872 for p in periods: 873 insert_period(freebusy, FreeBusyPeriod(p.get_start_point(), p.get_end_point(), uid, transp, recurrenceid, summary, organiser, expires)) 874 875 # vim: tabstop=4 expandtab shiftwidth=4