# data structure for intervals

This topic is 4574 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi guys, I have a question on a mock exam and it is "Describe clearly your chosen data structure for representing intervals". Obviously they will probably ask a similar question on the real exam. So i'm trying to work out what it means. It's worth 5 marks! :O Now, i'm assuming I need 5 bullet points about it. However, I'm unsure what exactly the question means? All i can think of is that it is a list lol. It forms part of a larger question which is a data abstraction for 'intervals'. I will quickly brief you on it.. Now, I have created a constructor called make-interval which accepts a lower endpoint l and an upper endpoint u and a predicate c which defines the ordering of interval elements, and returns an interval. Here is my constructor: (define [make-interval c l u] (if (c l u) (if (string? l) (cons l (make-interval c (string (integer->char (+ 1 (char->integer (string-ref l 0))))) u)) (cons l (make-interval c (+ 1 l) u)) ) empty)) Examples: (make-interval string-leq? "a" "e") .. the result is '("a" "b" "c" "d" "e") (make-interval <= 1 5) .. the result is '(1 2 3 4 5) Surprisingly, it works. (assuming that string-leq is a predicate that determines whether the lower endpoint letter is less than the upper endpoints letter. Again, the question "Describe clearly your chosen data structure for representing intervals" arises... Please give me some pointers as to how to answer this question, as I have no idea what it is asking me. Thanks for everything, :)

##### Share on other sites
Quote:
 Original post by petemurraySurprisingly, it works.

EDIT: I'm unclear as to what's going on, sorry. Anyone else? As a response purely to your topic: std::pair<int, int> in C++'s STL.

##### Share on other sites
Describe clearly your chosen data structure for intervals.

That is the question. I must answer it, but I'm unsure how to?
It says describe, so it must be worded.

##### Share on other sites
I suspect there's something you're misunderstanding about the question, but it's hard to say without more context. What operations should an interval support? Does it only have to work for integers and characters, like your make-interval does?

##### Share on other sites
yes only intervals and characters.

ALl i could think of was that it is a list of numbers that are ordered from the lowest point to the highest point. The make-interval constructor only works for string-leq? or <= predicates.

Not sure what else to say :S

##### Share on other sites
Does the larger question you mentioned require you to implement other functionality
on top of your interval representation?
Let's say you wanted to write a function "contains" that would check if a value is inside
an interval. With your make-interval, contains would have to search through the list, and
it wouldn't work for fractional values.
It helps to think about data types in terms of the things you want to do with them. So if the operations on intervals were e.g. min, max, and contains, think about the minimum amount of information you need to put into your interval implementation to make those operations work.

##### Share on other sites
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.4

I doubt you'll find a better explanation.

##### Share on other sites
Hmm so for 5 bullet points how would you describe the data abstraction of the make-rat example on the above website that you provided? lol

1. 1
2. 2
Rutin
21
3. 3
4. 4
A4L
15
5. 5
khawk
14

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633742
• Total Posts
3013630
×